Groupe d’études et de recherche en analyse des décisions

G-2014-54

Locomotive assignment under consist busting and maintenance constraints

, et

We propose a new large scale optimization model, named TS_LAP, for the locomotive assignment problem (LAP), which relies on train strings or consist travel plans, i.e., sequences of trains assigned to the same consist. Although several algorithms have been developed for LAP, including exact mathematics models, approximate dynamic programming and heuristics, previously published optimization algorithms all suffer from scalability or accuracy issues. In addition, each of the previously proposed optimization models lacks part of the constraints that are necessary in real-world train/locomotive assignments, e.g., maintenance shop constraints or consist-busting avoidance. We propose a train string based LAP model, which includes those constraints and which can efficiently be solved using large scale optimization techniques, namely column generation techniques. Numerical results are conducted on the railway network infrastructure of Canada Pacific Railway, with up to 1,394 trains and 9 types of locomotives over a two-week time period. We investigate the impact of the size of the locomotive fleet on the consist busting and the deadheading operations.

, 24 pages