Locomotive assignment with heterogeneous consists at Canadian National North America

The problem of assigning locomotives to train-segments is very important for railway companies, in view of the high cost of operating locomotives. The problem considered in this paper is to provide sufficient power to pull trains on fixed schedules, using heterogeneous consists. A list of preferred locomotives exists for each train-segment. The power required to pull a train-segment is determined according to the train's weight and length, as well as the route segment on which it must travel. Finally, locomotives requiring inspection must be sent to appropriate shops within a given time limit. This problem has been modeled as a multi-commodity flow problem with supplementary constraints. Since this is a very large scale scheduling problem (some 1300 locomotives and 2000 trains in one week) and it includes a wide range of supplementary restrictions, the problem has been decomposed into smaller overlapping problems involving 500 to 1000 trains. Each smaller problem is then solved using a Dantzig–Wolfe decomposition method, where subproblems are formulated as constrained or unconstrained shortest path problems depending on the locomotive state. Numerical experiments have been conducted using actual data from the Canadian National North America railway company. Our results indicate a 7% improvement over the current solution in effect at the company.