A Branch-and-Price algorithm for railway rolling stock rescheduling

How to best reschedule their fleet of rolling stock units during a disruption is an optimization problem regularly faced by railway operators. Despite the problem’s high complexity, it is still usually solved manually. In this paper the authors propose a path based mathematical formulation and solve it using a Branch-and-Price algorithm. The authors demonstrate that, unlike flow based approaches, the authors' formulation is more easily extended to handle certain families of constraints, such as train unit maintenance restrictions. The proposed algorithm is benchmarked on several real-life instances provided by the suburban railway operator in Copenhagen, DSB S-tog. When used in combination with a lower bound method taken from the literature the authors show that near-optimal solutions to this rescheduling problem can be found within a few seconds. Furthermore, the authors show that the proposed methodology can be used, with minor modification, on a tactical planning level, where it produces near-optimal rolling stock schedules in minutes of central processing unit (CPU) time.

• Record URL:
  https://doi.org/10.1016/j.trb.2017.03.003
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S0191261516307275
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Lusby, Richard M
  • Haahr, Jørgen Thorlund
  • Larsen, Jesper
  • Pisinger, David
• Publication Date: 2017-5

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 228-250
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 99
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Algorithms; Linear programming; Mixed integer programming; Optimization; Rolling stock; Schedules; Service disruption
• Uncontrolled Terms: Branch and price algorithms
• Geographic Terms: Copenhagen (Denmark)
• Subject Areas: Operations and Traffic Management; Planning and Forecasting; Railroads;

Filing Info

• Accession Number: 01635470
• Record Type: Publication
• Files: TRIS
• Created Date: Apr 25 2017 5:00PM