IDEAS home Printed from https://ideas.repec.org/p/ems/eureri/78317.html
   My bibliography  Save this paper

A Comparison of Two Exact Methods for Passenger Railway Rolling Stock (Re)Scheduling

Author

Listed:
  • Haahr, J.T.
  • Wagenaar, J.C.
  • Veelenturf, L.P.
  • Kroon, L.G.

Abstract

The assignment of rolling stock units to timetable services in passenger railways is an important optimization problem that has been addressed by many papers in different forms. Solution approaches have been proposed for different planning phases: strategic, tactical, and also operational planning. In this paper we compare two approaches within two operational planning phases (i.e. the daily and the real time planning). The first exact approach is based on a Mixed Integer Linear Program (MILP) which is solved using CPLEX. The second approach is an extension of a recently introduced column generation approach. In this paper, we benchmark the performance of the methods on networks of two countries (Denmark and The Netherlands). We use the approaches to make daily schedules and we test their real time applicability by performing tests with different disruption scenarios. The computational experiments demonstrate that both models can be used on both networks and are able to find optimal rolling stock circulations in the different planning phases. Furthermore, the results show that both approaches are sufficiently fast to be used in a real-time setting.

Suggested Citation

  • Haahr, J.T. & Wagenaar, J.C. & Veelenturf, L.P. & Kroon, L.G., 2015. "A Comparison of Two Exact Methods for Passenger Railway Rolling Stock (Re)Scheduling," ERIM Report Series Research in Management ERS-2015-007-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    • Handle: RePEc:ems:eureri:78317
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/78317/ERS-2015-007-LIS.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Balachandran Vaidyanathan & Ravindra K. Ahuja & James B. Orlin, 2008. "The Locomotive Routing Problem," Transportation Science, INFORMS, vol. 42(4), pages 492-507, November.
    2. Arianna Alfieri & Rutger Groot & Leo Kroon & Alexander Schrijver, 2006. "Efficient Circulation of Railway Rolling Stock," Transportation Science, INFORMS, vol. 40(3), pages 378-391, August.
    3. Nielsen, Lars Kjær & Kroon, Leo & Maróti, Gábor, 2012. "A rolling horizon approach for disruption management of railway rolling stock," European Journal of Operational Research, Elsevier, vol. 220(2), pages 496-509.
    4. Nielsen, L.K. & Maróti, G., 2009. "Disruption Management of Rolling Stock in Passenger Railway Transportation," ERIM Report Series Research in Management ERS-2009-046-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    5. Ravindra K. Ahuja & Jian Liu & James B. Orlin & Dushyant Sharma & Larry A. Shughart, 2005. "Solving Real-Life Locomotive-Scheduling Problems," Transportation Science, INFORMS, vol. 39(4), pages 503-517, November.
    6. Rouillon, Stéphane & Desaulniers, Guy & Soumis, François, 2006. "An extended branch-and-bound method for locomotive assignment," Transportation Research Part B: Methodological, Elsevier, vol. 40(5), pages 404-423, June.
    7. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    8. Jespersen-Groth, J. & Potthoff, D. & Clausen, J. & Huisman, D. & Kroon, L.G. & Maróti, G. & Nielsen, M.N., 2007. "Disruption management in passenger railway transportation," Econometric Institute Research Papers EI 2007-05, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Fioole, Pieter-Jan & Kroon, Leo & Maroti, Gabor & Schrijver, Alexander, 2006. "A rolling stock circulation model for combining and splitting of passenger trains," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1281-1297, October.
    10. Lingaya, Norbert & Cordeau, Jean-Françcois & Desaulniers, Guy & Desrosiers, Jacques & Soumis, Françcois, 2002. "Operational car assignment at VIA Rail Canada," Transportation Research Part B: Methodological, Elsevier, vol. 36(9), pages 755-778, November.
    11. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2001. "Simultaneous Assignment of Locomotives and Cars to Passenger Trains," Operations Research, INFORMS, vol. 49(4), pages 531-548, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Haahr, Jørgen T. & Wagenaar, Joris C. & Veelenturf, Lucas P. & Kroon, Leo G., 2016. "A comparison of two exact methods for passenger railway rolling stock (re)scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 91(C), pages 15-32.
    2. Lusby, Richard M. & Haahr, Jørgen Thorlund & Larsen, Jesper & Pisinger, David, 2017. "A Branch-and-Price algorithm for railway rolling stock rescheduling," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 228-250.
    3. Zhiyuan Lin & Raymond S. K. Kwan, 2016. "Local convex hulls for a special class of integer multicommodity flow problems," Computational Optimization and Applications, Springer, vol. 64(3), pages 881-919, July.
    4. Frisch, Sarah & Hungerländer, Philipp & Jellen, Anna & Primas, Bernhard & Steininger, Sebastian & Weinberger, Dominic, 2021. "Solving a real-world Locomotive Scheduling Problem with Maintenance Constraints," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 386-409.
    5. Prashant Premkumar & P. N. Ram Kumar, 2019. "Literature Review of Locomotive Assignment Problem from Service Operations Perspective: The Case of Indian Railways," IIM Kozhikode Society & Management Review, , vol. 8(1), pages 74-86, January.
    6. Hoogervorst, R. & Dollevoet, T.A.B. & Maróti, G. & Huisman, D., 2018. "Reducing Passenger Delays by Rolling Stock Rescheduling," Econometric Institute Research Papers EI2018-29, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    7. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    8. Lin, Boliang & Zhao, Yinan, 2021. "Synchronized optimization of EMU train assignment and second-level preventive maintenance scheduling," Reliability Engineering and System Safety, Elsevier, vol. 215(C).
    9. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    10. Wagenaar, Joris & Kroon, Leo & Fragkos, Ioannis, 2017. "Rolling stock rescheduling in passenger railway transportation using dead-heading trips and adjusted passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 140-161.
    11. Zhong, Qingwei & Lusby, Richard M. & Larsen, Jesper & Zhang, Yongxiang & Peng, Qiyuan, 2019. "Rolling stock scheduling with maintenance requirements at the Chinese High-Speed Railway," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 24-44.
    12. Prashant Premkumar & P. N. Ram Kumar, 2022. "Locomotive assignment problem: integrating the strategic, tactical and operational level aspects," Annals of Operations Research, Springer, vol. 315(2), pages 867-898, August.
    13. Nielsen, Lars Kjær & Kroon, Leo & Maróti, Gábor, 2012. "A rolling horizon approach for disruption management of railway rolling stock," European Journal of Operational Research, Elsevier, vol. 220(2), pages 496-509.
    14. Belgacem Bouzaiene-Ayari & Clark Cheng & Sourav Das & Ricardo Fiorillo & Warren B. Powell, 2016. "From Single Commodity to Multiattribute Models for Locomotive Optimization: A Comparison of Optimal Integer Programming and Approximate Dynamic Programming," Transportation Science, INFORMS, vol. 50(2), pages 366-389, May.
    15. Dauzère-Pérès, Stéphane & De Almeida, David & Guyon, Olivier & Benhizia, Faten, 2015. "A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 138-150.
    16. Gao, Yuan & Schmidt, Marie & Yang, Lixing & Gao, Ziyou, 2020. "A branch-and-price approach for trip sequence planning of high-speed train units," Omega, Elsevier, vol. 92(C).
    17. Sato, Keisuke & Fukumura, Naoto, 2012. "Real-time freight locomotive rescheduling and uncovered train detection during disruption," European Journal of Operational Research, Elsevier, vol. 221(3), pages 636-648.
    18. Dakic, Igor & Yang, Kaidi & Menendez, Monica & Chow, Joseph Y.J., 2021. "On the design of an optimal flexible bus dispatching system with modular bus units: Using the three-dimensional macroscopic fundamental diagram," Transportation Research Part B: Methodological, Elsevier, vol. 148(C), pages 38-59.
    19. Xueqiao Yu & Maoxiang Lang & Wenhui Zhang & Shiqi Li & Mingyue Zhang & Xiao Yu, 2019. "An Empirical Study on the Comprehensive Optimization Method of a Train Diagram of the China High Speed Railway Express," Sustainability, MDPI, vol. 11(7), pages 1-30, April.
    20. Camilo Ortiz-Astorquiza & Jean-François Cordeau & Emma Frejinger, 2021. "The Locomotive Assignment Problem with Distributed Power at the Canadian National Railway Company," Transportation Science, INFORMS, vol. 55(2), pages 510-531, March.

    More about this item

    Keywords

    rolling stock units; scheduling; rescheduling; optimization; railway rolling stock; MILP;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ems:eureri:78317. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/erimanl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.