IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v158y2022icp210-238.html
   My bibliography  Save this article

A heuristic approach to integrate train timetabling, platforming, and railway network maintenance scheduling decisions

Author

Listed:
  • Zhang, Qin
  • Lusby, Richard Martin
  • Shang, Pan
  • Zhu, Xiaoning

Abstract

Train timetabling, platforming, and network maintenance scheduling are three highly interdependent problems that are crucial in the planning of railway operations, and each is normally addressed separately. In this paper, we simultaneously optimize these problems for a high-speed railway network that is comprised of multiple railway lines and stations. We model the railway network on a mesoscopic level and formulate a 0–1 binary integer programming model that minimizes the total train weighted running cost and any deviation from ideal maintenance task start times. A heuristic procedure, which dynamically updates the available time windows for each of the trains, is used to control the number of train paths in the mathematical model. The mathematical model is repeatedly solved, and at each iteration we gradually modify the set of train paths available. Four different strategies to modify train time windows are used in the train path modification step and their selection depends on the solution to the mathematical model. Computational results for three networks of different sizes conclusively demonstrate that there is not only benefit in integrating these problems, with improvements of as much as 30%, but also that the proposed solution approach is highly effective. Compared to the commercial solver CPLEX, the proposed approach is able to more quickly find better quality solutions within a given time limit.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:158:y:2022:i:c:p:210-238
    DOI: 10.1016/j.trb.2022.02.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261522000212
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2022.02.002?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. Corman, Francesco & D’Ariano, Andrea & Marra, Alessio D. & Pacciarelli, Dario & Samà, Marcella, 2017. "Integrating train scheduling and delay management in real-time railway traffic control," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 213-239.
    2. Alain Billionnet, 2003. "Using Integer Programming to Solve the Train-Platforming Problem," Transportation Science, INFORMS, vol. 37(2), pages 213-222, May.
    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. Sels, P. & Vansteenwegen, P. & Dewilde, T. & Cattrysse, D. & Waquet, B. & Joubert, A., 2014. "The train platforming problem: The infrastructure management company perspective," Transportation Research Part B: Methodological, Elsevier, vol. 61(C), pages 55-72.
    5. 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.
    6. Meng, Lingyun & Zhou, Xuesong, 2019. "An integrated train service plan optimization model with variable demand: A team-based scheduling approach with dual cost information in a layered network," Transportation Research Part B: Methodological, Elsevier, vol. 125(C), pages 1-28.
    7. 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.
    8. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    9. 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.
    10. Zhu, Yongqiu & Goverde, Rob M.P., 2020. "Integrated timetable rescheduling and passenger reassignment during railway disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 282-314.
    11. Leonardo Lamorgese & Carlo Mannino, 2015. "An Exact Decomposition Approach for the Real-Time Train Dispatching Problem," Operations Research, INFORMS, vol. 63(1), pages 48-64, February.
    12. 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.
    13. Bešinović, Nikola & Goverde, Rob M.P. & Quaglietta, Egidio & Roberti, Roberto, 2016. "An integrated micro–macro approach to robust railway timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 14-32.
    14. 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.
    15. Zhang, Chuntian & Gao, Yuan & Yang, Lixing & Kumar, Uday & Gao, Ziyou, 2019. "Integrated optimization of train scheduling and maintenance planning on high-speed railway corridors," Omega, Elsevier, vol. 87(C), pages 86-104.
    16. Valentina Cacchiani & Alberto Caprara & Matteo Fischetti, 2012. "A Lagrangian Heuristic for Robustness, with an Application to Train Timetabling," Transportation Science, INFORMS, vol. 46(1), pages 124-133, February.
    17. Meng, Lingyun & Zhou, Xuesong, 2014. "Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 208-234.
    18. Zhan, Shuguang & Wong, S.C. & Lo, S.M., 2020. "Social equity-based timetabling and ticket pricing for high-speed railways," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 165-186.
    19. 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.
    20. Zhou, Xuesong & Zhong, Ming, 2005. "Bicriteria train scheduling for high-speed passenger railroad planning applications," European Journal of Operational Research, Elsevier, vol. 167(3), pages 752-771, December.
    21. Alberto Caprara & Laura Galli & Paolo Toth, 2011. "Solution of the Train Platforming Problem," Transportation Science, INFORMS, vol. 45(2), pages 246-257, May.
    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. Maciej Kruszyna, 2022. "NOAH as an Innovative Tool for Modeling the Use of Suburban Railways," Sustainability, MDPI, vol. 15(1), pages 1-17, December.
    2. Zhengwen Liao, 2023. "Rescheduling Out-of-Gauge Trains with Speed Restrictions and Temporal Blockades on the Opposite-Direction Track," Mathematics, MDPI, vol. 11(12), pages 1-26, June.
    3. Zhang, Chuntian & Gao, Yuan & Cacchiani, Valentina & Yang, Lixing & Gao, Ziyou, 2023. "Train rescheduling for large-scale disruptions in a large-scale railway network," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).

    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. Zhang, Chuntian & Gao, Yuan & Cacchiani, Valentina & Yang, Lixing & Gao, Ziyou, 2023. "Train rescheduling for large-scale disruptions in a large-scale railway network," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    2. 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.
    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. Zhang, Yongxiang & Peng, Qiyuan & Lu, Gongyuan & Zhong, Qingwei & Yan, Xu & Zhou, Xuesong, 2022. "Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 240-277.
    5. 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.
    6. Zhan, Shuguang & Wong, S.C. & Shang, Pan & Peng, Qiyuan & Xie, Jiemin & Lo, S.M., 2021. "Integrated railway timetable rescheduling and dynamic passenger routing during a complete blockage," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 86-123.
    7. Zhou, Leishan & Tong, Lu (Carol) & Chen, Junhua & Tang, Jinjin & Zhou, Xuesong, 2017. "Joint optimization of high-speed train timetables and speed profiles: A unified modeling approach using space-time-speed grid networks," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 157-181.
    8. Yidong Wang & Rui Song & Shiwei He & Zilong Song, 2022. "Train Routing and Track Allocation Optimization Model of Multi-Station High-Speed Railway Hub," Sustainability, MDPI, vol. 14(12), pages 1-21, June.
    9. Lu, Gongyuan & Ning, Jia & Liu, Xiaobo & Nie, Yu (Marco), 2022. "Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    10. 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.
    11. Mo, Pengli & D’Ariano, Andrea & Yang, Lixing & Veelenturf, Lucas P. & Gao, Ziyou, 2021. "An exact method for the integrated optimization of subway lines operation strategies with asymmetric passenger demand and operating costs," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 283-321.
    12. 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.
    13. 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.
    14. 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.
    15. Yin, Jiateng & D’Ariano, Andrea & Wang, Yihui & Yang, Lixing & Tang, Tao, 2021. "Timetable coordination in a rail transit network with time-dependent passenger demand," European Journal of Operational Research, Elsevier, vol. 295(1), pages 183-202.
    16. 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.
    17. Leonardo Lamorgese & Carlo Mannino & Mauro Piacentini, 2016. "Optimal Train Dispatching by Benders’-Like Reformulation," Transportation Science, INFORMS, vol. 50(3), pages 910-925, August.
    18. 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.
    19. König, Eva & Schön, Cornelia, 2021. "Railway delay management with passenger rerouting considering train capacity constraints," European Journal of Operational Research, Elsevier, vol. 288(2), pages 450-465.
    20. Gao, Yuan & Kroon, Leo & Yang, Lixing & Gao, Ziyou, 2018. "Three-stage optimization method for the problem of scheduling additional trains on a high-speed rail corridor," Omega, Elsevier, vol. 80(C), pages 175-191.

    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:eee:transb:v:158:y:2022:i:c:p:210-238. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.