Portal de Periódicos da CAPES

A time–space formulation for the locomotive routing problem at the Canadian National Railways

2021; Elsevier BV; Volume: 139; Linguagem: Inglês

10.1016/j.cor.2021.105629

1873-765X

Pedro L. Miranda, Jean‐François Cordeau, Emma Frejinger,

Maritime Ports and Logistics

This paper addresses the locomotive routing problem, a large-scale railway optimization problem that aims to determine the optimal sequence of trains to be followed by each locomotive in a given fleet, while considering locomotive maintenance over a weekly planning horizon. By using commodity aggregation and flow decomposition techniques, we design a tractable integer linear program for the problem. The formulation is based on a time–space network representation of the problem that allows us to track the maintenance status of specific locomotives over the planning horizon and to manage locomotive assignments to trains based on their current maintenance status. It also considers locomotive repositioning, train connections, and utilization of third-party locomotives (i.e., foreign power). Computational experiments on real instances from the Canadian National Railways show that our model is tractable despite its size and can be solved optimally within reasonable computing times. Our methodology performs favorably when compared to historical data supplied by the industrial partner. The solutions satisfy train schedules and locomotive maintenance while requiring fewer locomotives and less repositioning. • We study the locomotive routing problem in a major North American railroad company. • We formulate an integer linear programming model based on a time-space representation of the problem. • We assess the model performance and evaluate how variations in key parameters affect optimal solutions. • In contrast to historical data, our model attains solutions with fewer locomotives and less repositioning. • Our methodology is valuable to run multiple scenario analyses and support decision-making.