Assigning locomotives and cars to a set of scheduled trains is a complex but important problem for passenger railways. This task is normally carried out in several phases in which an increasing level of details is considered. This paper describes a modeling and solution methodology for a car assignment problem that arises when individual car routings that satisfy all operational constraints must be determined. This methodology considers typical constraints such as maintenance requirements but also more complex constraints such as minimum connection times that depend on the positions of the individual cars in a train consist. The problem is solved heuristically by a branch-and-bound method in which the linear relaxations are solved by column generation. Simulation experiments performed on realistic data show that the solution approach yields good quality solutions in very short computing times. A software system based on this approach is now being evaluated by VIA Rail Canada.
Published October 2000 , 30 pages