IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v12y2020i3p1131-d316726.html
   My bibliography  Save this article

A Mixed Integer Linear Programming Method for Simultaneous Multi-Periodic Train Timetabling and Routing on a High-Speed Rail Network

Author

Listed:
  • Wenliang Zhou

    (School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

  • Xiaorong You

    (School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

  • Wenzhuang Fan

    (School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

Abstract

To avoid conflicts among trains at stations and provide passengers with a periodic train timetable to improve service level, this paper mainly focuses on the problem of multi-periodic train timetabling and routing by optimizing the routes of trains at stations and their entering time and leaving time on each chosen arrival–departure track at each visited station. Based on the constructed directed graph, including unidirectional and bidirectional tracks at stations and in sections, a mixed integer linear programming model with the goal of minimizing the total travel time of trains is formulated. Then, a strategy is introduced to reduce the number of constraints for improving the solved efficiency of the model. Finally, the performance, stability and practicability of the proposed method, as well as the impact of some main factors on the model are analyzed by numerous instances on both a constructed railway network and Guang-Zhu inter-city railway; they are solved using the commercial solver WebSphere ILOG CPLEX (International Business Machines Corporation, New York, NY, USA). Experimental results show that integrating multi-periodic train timetabling and routing can be conducive to improving the quality of a train timetable. Hence, good economic and social benefits for high-speed rail can be achieved, thus, further contributing to the sustained development of both high-speed railway systems and society.

Suggested Citation

  • Wenliang Zhou & Xiaorong You & Wenzhuang Fan, 2020. "A Mixed Integer Linear Programming Method for Simultaneous Multi-Periodic Train Timetabling and Routing on a High-Speed Rail Network," Sustainability, MDPI, vol. 12(3), pages 1-34, February.
    • Handle: RePEc:gam:jsusta:v:12:y:2020:i:3:p:1131-:d:316726
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/12/3/1131/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/12/3/1131/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Zwaneveld, Peter J. & Kroon, Leo G. & van Hoesel, Stan P. M., 2001. "Routing trains through a railway station based on a node packing model," European Journal of Operational Research, Elsevier, vol. 128(1), pages 14-33, January.
    2. Gabrio Caimi & Dan Burkolter & Thomas Herrmann, 2005. "Finding Delay-Tolerant Train Routings through Stations," Operations Research Proceedings, in: Hein Fleuren & Dick Hertog & Peter Kort (ed.), Operations Research Proceedings 2004, pages 136-143, Springer.
    3. Alain Billionnet, 2003. "Using Integer Programming to Solve the Train-Platforming Problem," Transportation Science, INFORMS, vol. 37(2), pages 213-222, May.
    4. Zhou, Wenliang & Tian, Junli & Xue, Lijuan & Jiang, Min & Deng, Lianbo & Qin, Jin, 2017. "Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 144-173.
    5. Pellegrini, Paola & Marlière, Grégory & Rodriguez, Joaquin, 2014. "Optimal train routing and scheduling for managing traffic perturbations in complex junctions," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 58-80.
    6. Lee, Yusin & Chen, Chuen-Yih, 2009. "A heuristic for the train pathing and timetabling problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 837-851, September.
    7. 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.
    8. Xu, Xiaoming & Li, Keping & Yang, Lixing, 2015. "Scheduling heterogeneous train traffic on double tracks with efficient dispatching rules," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 364-384.
    9. Zhou, Wenliang & Teng, Hualiang, 2016. "Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 409-439.
    10. G. Caimi & F. Chudak & M. Fuchsberger & M. Laumanns & R. Zenklusen, 2011. "A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling," Transportation Science, INFORMS, vol. 45(2), pages 212-227, May.
    11. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    12. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    13. Mu, Shi & Dessouky, Maged, 2013. "Efficient dispatching rules on double tracks with heterogeneous train traffic," Transportation Research Part B: Methodological, Elsevier, vol. 51(C), pages 45-64.
    14. Leo G. Kroon & Leon W. P. Peeters, 2003. "A Variable Trip Time Model for Cyclic Railway Timetabling," Transportation Science, INFORMS, vol. 37(2), pages 198-212, May.
    15. Törnquist, Johanna & Persson, Jan A., 2007. "N-tracked railway traffic re-scheduling during disturbances," Transportation Research Part B: Methodological, Elsevier, vol. 41(3), pages 342-362, March.
    16. 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.
    17. Johnson, Daniel & Shires, Jeremy & Nash, Chris & Tyler, Jonathan, 2006. "Forecasting and appraising the impact of a regular interval timetable," Transport Policy, Elsevier, vol. 13(5), pages 349-366, September.
    18. Odijk, Michiel A., 1996. "A constraint generation algorithm for the construction of periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 30(6), pages 455-464, December.
    19. Mazzarello, Maura & Ottaviani, Ennio, 2007. "A traffic management system for real-time traffic optimisation in railways," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 246-274, February.
    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. Limsawasd, Charinee & Athigakunagorn, Nathee & Khathawatcharakun, Phattadon & Boonmee, Atiwat, 2022. "Skip-Stop Strategy Patterns optimization to enhance mass transit operation under physical distancing policy due to COVID-19 pandemic outbreak," Transport Policy, Elsevier, vol. 126(C), pages 225-238.
    2. Luetian Sun & Rui Song, 2022. "Improving Efficiency in Congested Traffic Networks: Pareto-Improving Reservations through Agent-Based Timetabling," Sustainability, MDPI, vol. 14(4), pages 1-24, February.
    3. Flavia Fechete & Anișor Nedelcu, 2022. "Multi-Objective Optimization of the Organization’s Performance for Sustainable Development," Sustainability, MDPI, vol. 14(15), pages 1-20, July.
    4. Manuel Blanco-Castillo & Adrián Fernández-Rodríguez & Antonio Fernández-Cardador & Asunción P. Cucala, 2022. "Eco-Driving in Railway Lines Considering the Uncertainty Associated with Climatological Conditions," Sustainability, MDPI, vol. 14(14), pages 1-26, July.
    5. Zeyu Wang & Leishan Zhou & Bin Guo & Xing Chen & Hanxiao Zhou, 2021. "An Efficient Hybrid Approach for Scheduling the Train Timetable for the Longer Distance High-Speed Railway," Sustainability, MDPI, vol. 13(5), pages 1-22, February.

    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. Zhou, Wenliang & Tian, Junli & Xue, Lijuan & Jiang, Min & Deng, Lianbo & Qin, Jin, 2017. "Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 144-173.
    2. Pellegrini, Paola & Rodriguez, Joaquin, 2013. "Single European Sky and Single European Railway Area: A system level analysis of air and rail transportation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 57(C), pages 64-86.
    3. Xiaoming Xu & Keping Li & Lixing Yang & Ziyou Gao, 2019. "An efficient train scheduling algorithm on a single-track railway system," Journal of Scheduling, Springer, vol. 22(1), pages 85-105, February.
    4. Samà, Marcella & Pellegrini, Paola & D’Ariano, Andrea & Rodriguez, Joaquin & Pacciarelli, Dario, 2016. "Ant colony optimization for the real-time train routing selection problem," Transportation Research Part B: Methodological, Elsevier, vol. 85(C), pages 89-108.
    5. Zhang, Yongxiang & D'Ariano, Andrea & He, Bisheng & Peng, Qiyuan, 2019. "Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 237-278.
    6. Zhang, Qin & Lusby, Richard Martin & Shang, Pan & Zhu, Xiaoning, 2022. "A heuristic approach to integrate train timetabling, platforming, and railway network maintenance scheduling decisions," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 210-238.
    7. Dewilde, Thijs & Sels, Peter & Cattrysse, Dirk & Vansteenwegen, Pieter, 2014. "Improving the robustness in railway station areas," European Journal of Operational Research, Elsevier, vol. 235(1), pages 276-286.
    8. Corman, Francesco & D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2010. "A tabu search algorithm for rerouting trains during rail operations," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 175-192, January.
    9. Yin, Jiateng & Tang, Tao & Yang, Lixing & Gao, Ziyou & Ran, Bin, 2016. "Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: An approximate dynamic programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 178-210.
    10. Tian, Xiaopeng & Niu, Huimin, 2020. "Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 143-173.
    11. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    12. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.
    13. Andrea D'Ariano & Francesco Corman & Dario Pacciarelli & Marco Pranzo, 2008. "Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time," Transportation Science, INFORMS, vol. 42(4), pages 405-419, November.
    14. Pellegrini, Paola & Pesenti, Raffaele & Rodriguez, Joaquin, 2019. "Efficient train re-routing and rescheduling: Valid inequalities and reformulation of RECIFE-MILP," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 33-48.
    15. Pellegrini, Paola & Marlière, Grégory & Rodriguez, Joaquin, 2014. "Optimal train routing and scheduling for managing traffic perturbations in complex junctions," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 58-80.
    16. Burdett, R.L. & Kozan, E., 2010. "A disjunctive graph model and framework for constructing new train schedules," European Journal of Operational Research, Elsevier, vol. 200(1), pages 85-98, January.
    17. Xu, Peijuan & Corman, Francesco & Peng, Qiyuan & Luan, Xiaojie, 2017. "A train rescheduling model integrating speed management during disruptions of high-speed traffic under a quasi-moving block system," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 638-666.
    18. Bettinelli, Andrea & Santini, Alberto & Vigo, Daniele, 2017. "A real-time conflict solution algorithm for the train rescheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 237-265.
    19. Yu-Jun Zheng, 2018. "Emergency Train Scheduling on Chinese High-Speed Railways," Transportation Science, INFORMS, vol. 52(5), pages 1077-1091, October.
    20. E. Ursavas & Stuart X. Zhu, 2018. "Integrated Passenger and Freight Train Planning on Shared-Use Corridors," Service Science, INFORMS, vol. 52(6), pages 1376-1390, December.

    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:gam:jsusta:v:12:y:2020:i:3:p:1131-:d:316726. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.