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

Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition

Author

Listed:
  • Zhou, Wenliang
  • Tian, Junli
  • Xue, Lijuan
  • Jiang, Min
  • Deng, Lianbo
  • Qin, Jin

Abstract

To provide passengers with strict regularity of train operation, this research is devoted to modeling and solving the multi-periodic train timetabling problem to simultaneously optimize operation periods, arrival times, and departure times of all period types of trains on a double-track rail network. Based on the construction of a weighted directed graph, a multi-path searching model, namely, a 0-1 linear programming model, is built to minimize the total travel time of all period-types of trains subject to many operational constraints, including station parking capacity and train minimum load factors. After decomposing this model by introducing some Lagrangian multipliers to relax its complicated constraints, a solution algorithm, including a multi-path simultaneous searching sub-algorithm for each period-type of train, is designed to optimize both the feasible and dual solutions, which correspond to the upper and lower bounds, respectively. Finally, the performance, convergence, sensitivity, and practicability of our method are analyzed using many instances on both a small rail network and the high-speed railway between Beijing and Shanghai in China.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:105:y:2017:i:c:p:144-173
    DOI: 10.1016/j.trb.2017.08.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517301340
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2017.08.005?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. Matthew E. H. Petering & Mojtaba Heydar & Dietrich R. Bergmann, 2016. "Mixed-Integer Programming for Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming," Transportation Science, INFORMS, vol. 50(3), pages 892-909, August.
    2. 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.
    3. Niu, Huimin & Zhou, Xuesong & Gao, Ruhu, 2015. "Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints," Transportation Research Part B: Methodological, Elsevier, vol. 76(C), pages 117-135.
    4. Chang, Yu-Hern & Yeh, Chung-Hsing & Shen, Ching-Cheng, 2000. "A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 91-106, February.
    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. 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.
    9. 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.
    10. 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.
    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. Li, Xiang & Lo, Hong K., 2014. "Energy minimization in dynamic train scheduling and control for metro rail operations," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 269-284.
    13. Barrena, Eva & Canca, David & Coelho, Leandro C. & Laporte, Gilbert, 2014. "Single-line rail rapid transit timetabling under dynamic passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 134-150.
    14. Robenek, Tomáš & Maknoon, Yousef & Azadeh, Shadi Sharif & Chen, Jianghang & Bierlaire, Michel, 2016. "Passenger centric train timetabling problem," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 107-126.
    15. Ghoseiri, Keivan & Szidarovszky, Ferenc & Asgharpour, Mohammad Jawad, 2004. "A multi-objective train scheduling model and solution," Transportation Research Part B: Methodological, Elsevier, vol. 38(10), pages 927-952, December.
    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. 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.
    18. 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.
    19. Cacchiani, Valentina & Caprara, Alberto & Toth, Paolo, 2010. "Scheduling extra freight trains on railway networks," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 215-231, February.
    20. Dorfman, M. J. & Medanic, J., 2004. "Scheduling trains on a railway network using a discrete event model of railway traffic," Transportation Research Part B: Methodological, Elsevier, vol. 38(1), pages 81-98, January.
    21. Coviello, Nicola, 2015. "Modelling periodic operations on single track lines: Timetable design and stability evaluation," Research in Transportation Economics, Elsevier, vol. 54(C), pages 2-14.
    22. Jiang, Feng & Cacchiani, Valentina & Toth, Paolo, 2017. "Train timetabling by skip-stop planning in highly congested lines," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 149-174.
    23. Fu, Huiling & Nie, Lei & Meng, Lingyun & Sperry, Benjamin R. & He, Zhenhuan, 2015. "A hierarchical line planning approach for a large-scale high speed rail network: The China case," Transportation Research Part A: Policy and Practice, Elsevier, vol. 75(C), pages 61-83.
    24. 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.
    25. 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.
    26. 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.
    27. Thomas Lindner & Uwe Zimmermann, 2005. "Cost optimal periodic train scheduling," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 62(2), pages 281-295, November.
    28. Yin, Jiateng & Yang, Lixing & Tang, Tao & Gao, Ziyou & Ran, Bin, 2017. "Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: Mixed-integer linear programming approaches," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 182-213.
    29. 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.
    30. Higgins, A. & Kozan, E. & Ferreira, L., 1996. "Optimal scheduling of trains on a single line track," Transportation Research Part B: Methodological, Elsevier, vol. 30(2), pages 147-161, April.
    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. Han Zheng & Junhua Chen & Zhaocha Huang & Jianhao Zhu, 2022. "Joint Optimization of Multi-Cycle Timetable Considering Supply-to-Demand Relationship and Energy Consumption for Rail Express," Mathematics, MDPI, vol. 10(21), pages 1-29, November.
    2. Martin-Iradi, Bernardo & Ropke, Stefan, 2022. "A column-generation-based matheuristic for periodic and symmetric train timetabling with integrated passenger routing," European Journal of Operational Research, Elsevier, vol. 297(2), pages 511-531.
    3. 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.
    4. Amiri, Mohsen & Amin, Saman Hassanzadeh & Tavakkoli-Moghaddam, Reza, 2019. "A Lagrangean decomposition approach for a novel two-echelon node-based location-routing problem in an offshore oil and gas supply chain," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 96-114.
    5. Wenliang Zhou & Wenzhuang Fan & Xiaorong You & Lianbo Deng, 2019. "Demand-Oriented Train Timetabling Integrated with Passenger Train-Booking Decisions," Sustainability, MDPI, vol. 11(18), pages 1-34, September.
    6. Yang, Senyan & Ning, Lianju & Shang, Pan & (Carol) Tong, Lu, 2020. "Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    7. Robenek, Tomáš & Azadeh, Shadi Sharif & Maknoon, Yousef & de Lapparent, Matthieu & Bierlaire, Michel, 2018. "Train timetable design under elastic passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 19-38.
    8. 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.
    9. 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. 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.
    2. 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.
    3. 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.
    4. Jiang, Feng & Cacchiani, Valentina & Toth, Paolo, 2017. "Train timetabling by skip-stop planning in highly congested lines," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 149-174.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    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. Xu, Xiaoming & Li, Chung-Lun & Xu, Zhou, 2021. "Train timetabling with stop-skipping, passenger flow, and platform choice considerations," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 52-74.
    11. 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.
    12. 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.
    13. 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.
    14. Xie, J. & Wong, S.C. & Zhan, S. & Lo, S.M. & Chen, Anthony, 2020. "Train schedule optimization based on schedule-based stochastic passenger assignment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    15. Yin, Jiateng & Yang, Lixing & Tang, Tao & Gao, Ziyou & Ran, Bin, 2017. "Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: Mixed-integer linear programming approaches," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 182-213.
    16. Wenliang Zhou & Wenzhuang Fan & Xiaorong You & Lianbo Deng, 2019. "Demand-Oriented Train Timetabling Integrated with Passenger Train-Booking Decisions," Sustainability, MDPI, vol. 11(18), pages 1-34, September.
    17. 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.
    18. Yang, Lixing & Qi, Jianguo & Li, Shukai & Gao, Yuan, 2016. "Collaborative optimization for train scheduling and train stop planning on high-speed railways," Omega, Elsevier, vol. 64(C), pages 57-76.
    19. Yang, Xin & Chen, Anthony & Ning, Bin & Tang, Tao, 2016. "A stochastic model for the integrated optimization on metro timetable and speed profile with uncertain train mass," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 424-445.
    20. Julia Lange & Frank Werner, 2018. "Approaches to modeling train scheduling problems as job-shop problems with blocking constraints," Journal of Scheduling, Springer, vol. 21(2), pages 191-207, April.

    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:105:y:2017:i:c:p:144-173. 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.