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

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, the authors design a tractable integer linear program for the problem. The formulation is based on a time–space network representation of the problem that allows tracking of 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 the model is tractable despite its size and can be solved optimally within reasonable computing times. The authors' 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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01837543
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Feb 28 2022 9:40AM