Designing Railroad Operating Plans: A Dual Adjustment Method for Implementing Lagrangian Relaxation

The problem of determining optimal train connections, frequencies, and blocking and routing plans for freight cars in single-carload general commodity service is modeled as an all-integer linear programming problem. The objective is to minimize train cost, car time cost, and yard classification cost, subject to limits on train size, number of blocks formed by yard, and maximum origin-to-destination trip times. A Lagrangian relaxation technique is used to solve the problem. A dual adjustment procedure, which exploits the structure of the model, is used to implement the relaxation. This procedure makes it possible to efficiently obtain close-to-optimal solutions to problems of realistic size.