IDEAS home Printed from https://ideas.repec.org/a/spr/pubtra/v9y2017i1d10.1007_s12469-016-0143-x.html
   My bibliography  Save this article

A branch-and-bound approach for robust railway timetabling

Author

Listed:
  • Gábor Maróti

    (VU University Amsterdam and Netherlands Railways)

Abstract

This paper studies the robust cyclic timetabling problem. The goal is to modify a given reference timetable to enhance its robustness against small stochastic disturbances. The robustness is measured by the expected total delay of the realised timetable. Kroon et al. (Transp Res Part B 42(6):553–570, 2008) propose a stochastic programming approach and implement it for Netherlands Railways (NS). While the model’s outcome is accepted by practitioners, relevant planning problems are rendered intractable by computation times of up to several days. In this paper we describe a Branch-and-Bound algorithm for solving the stochastic program of Kroon et al. (Transp Res Part B 42(6):553–570, 2008). We propose specific node selection rules, variable selection rules, constructive heuristics and lower bounds. We carry out computational tests on large real-life problem instances. The results confirm that our algorithm is able to considerably improve the robustness of the reference solutions. This is achieved with computation times of a few minutes. However, the weak lower bounds we use leave a considerable optimality gap. Therefore, our algorithm is best described as a heuristic solution method.

Suggested Citation

  • Gábor Maróti, 2017. "A branch-and-bound approach for robust railway timetabling," Public Transport, Springer, vol. 9(1), pages 73-94, July.
    • Handle: RePEc:spr:pubtra:v:9:y:2017:i:1:d:10.1007_s12469-016-0143-x
    DOI: 10.1007/s12469-016-0143-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12469-016-0143-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12469-016-0143-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kroon, Leo & Maróti, Gábor & Helmrich, Mathijn Retel & Vromans, Michiel & Dekker, Rommert, 2008. "Stochastic improvement of cyclic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 42(6), pages 553-570, July.
    2. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    3. Matteo Fischetti & Domenico Salvagnin & Arrigo Zanette, 2009. "Fast Approaches to Improve the Robustness of a Railway Timetable," Transportation Science, INFORMS, vol. 43(3), pages 321-335, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Reisch, Julian, 2020. "State of the art overview on automatic railway timetable generation and optimization," Discussion Papers 2020/20, Free University Berlin, School of Business & Economics.

    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. Schön, Cornelia & König, Eva, 2018. "A stochastic dynamic programming approach for delay management of a single train line," European Journal of Operational Research, Elsevier, vol. 271(2), pages 501-518.
    2. Hassini, Elkafi & Verma, Manish, 2016. "Disruption risk management in railroad networks: An optimization-based methodology and a case studyAuthor-Name: Azad, Nader," Transportation Research Part B: Methodological, Elsevier, vol. 85(C), pages 70-88.
    3. Zhang, Chuntian & Gao, Yuan & Yang, Lixing & Gao, Ziyou & Qi, Jianguo, 2020. "Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 64-92.
    4. Högdahl, Johan & Bohlin, Markus & Fröidh, Oskar, 2019. "A combined simulation-optimization approach for minimizing travel time and delays in railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 192-212.
    5. Sparing, Daniel & Goverde, Rob M.P., 2017. "A cycle time optimization model for generating stable periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 198-223.
    6. Lee, Yusin & Lu, Li-Sin & Wu, Mei-Ling & Lin, Dung-Ying, 2017. "Balance of efficiency and robustness in passenger railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 142-156.
    7. Cacchiani, Valentina & Qi, Jianguo & Yang, Lixing, 2020. "Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 136(C), pages 1-29.
    8. Jovanović, Predrag & Kecman, Pavle & Bojović, Nebojša & Mandić, Dragomir, 2017. "Optimal allocation of buffer times to increase train schedule robustness," European Journal of Operational Research, Elsevier, vol. 256(1), pages 44-54.
    9. Yang, Lixing & Zhou, Xuesong & Gao, Ziyou, 2014. "Credibility-based rescheduling model in a double-track railway network: a fuzzy reliable optimization approach," Omega, Elsevier, vol. 48(C), pages 75-93.
    10. Burggraeve, Sofie & Vansteenwegen, Pieter, 2017. "Robust routing and timetabling in complex railway stations," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 228-244.
    11. Lusby, Richard M. & Larsen, Jesper & Bull, Simon, 2018. "A survey on robustness in railway planning," European Journal of Operational Research, Elsevier, vol. 266(1), pages 1-15.
    12. Julius Pätzold, 2021. "Finding robust periodic timetables by integrating delay management," Public Transport, Springer, vol. 13(2), pages 349-374, June.
    13. Jiateng Yin & Lixing Yang & Xuesong Zhou & Tao Tang & Ziyou Gao, 2019. "Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 297-320, June.
    14. Harshad Khadilkar, 2017. "Data-Enabled Stochastic Modeling for Evaluating Schedule Robustness of Railway Networks," Transportation Science, INFORMS, vol. 51(4), pages 1161-1176, November.
    15. Nie, Wei & Li, Hao & Xiao, Na & Yang, Hao & Jiang, Zhishu & Buhigiro, Nsabimana, 2021. "Modeling and solving the last-shift period train scheduling problem in subway networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 569(C).
    16. Hörsting, Lena & Cleophas, Catherine, 2023. "Scheduling shared passenger and freight transport on a fixed infrastructure," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1158-1169.
    17. M. D. Yap & N. Oort & R. Nes & B. Arem, 2018. "Identification and quantification of link vulnerability in multi-level public transport networks: a passenger perspective," Transportation, Springer, vol. 45(4), pages 1161-1180, July.
    18. Maosheng Li & Zhengqiu Liu & Yonghong Zhang & Weijun Liu & Feng Shi, 2017. "Distribution analysis of train interval journey time employing the censored model with shifting character," Journal of Applied Statistics, Taylor & Francis Journals, vol. 44(4), pages 715-733, March.
    19. Yan, Fei & Goverde, Rob M.P., 2019. "Combined line planning and train timetabling for strongly heterogeneous railway lines with direct connections," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 20-46.
    20. Sels, P. & Dewilde, T. & Cattrysse, D. & Vansteenwegen, P., 2016. "Reducing the passenger travel time in practice by the automated construction of a robust railway timetable," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 124-156.

    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:spr:pubtra:v:9:y:2017:i:1:d:10.1007_s12469-016-0143-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.