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

Train timetabling by skip-stop planning in highly congested lines

Author

Listed:
  • Jiang, Feng
  • Cacchiani, Valentina
  • Toth, Paolo

Abstract

We study the problem of scheduling passenger trains in a highly congested railway double-track line with the aim of increasing the number of scheduled trains. A feasible timetable of the trains currently scheduled in the network is given. Additional trains should be scheduled to meet the increasing passenger demand. To achieve this goal, we are allowed to increase the dwelling time of some trains at some stations, to let them stop at some additional stations and even to skip a few stops. Thereby, we need to take explicitly into account the deceleration and acceleration times that are needed by the train when it stops at a station. This problem integrates the choice of the train schedule with the choice of the train stops, the latter being usually made in the Line Planning process. To solve this problem, we propose a heuristic algorithm, extended from a previous method to include the new features of the studied application, and show its performance on real-world instances of the Chinese high-speed JingHu corridor (between Beijing and Shanghai) involving up to 387 trains.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:104:y:2017:i:c:p:149-174
    DOI: 10.1016/j.trb.2017.06.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517300656
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2017.06.018?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. Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    2. Leo Kroon & Dennis Huisman & Erwin Abbink & Pieter-Jan Fioole & Matteo Fischetti & Gábor Maróti & Alexander Schrijver & Adri Steenbeek & Roelof Ybema, 2009. "The New Dutch Timetable: The OR Revolution," Interfaces, INFORMS, vol. 39(1), pages 6-17, February.
    3. 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.
    4. 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.
    5. Li, Shukai & Dessouky, Maged M. & Yang, Lixing & Gao, Ziyou, 2017. "Joint optimal train regulation and passenger flow control strategy for high-frequency metro lines," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 113-137.
    6. Peer, Stefanie & Knockaert, Jasper & Verhoef, Erik T., 2016. "Train commuters’ scheduling preferences: Evidence from a large-scale peak avoidance experiment," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 314-333.
    7. 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.
    8. 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.
    9. 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.
    10. Gao, Yuan & Kroon, Leo & Schmidt, Marie & Yang, Lixing, 2016. "Rescheduling a metro line in an over-crowded situation after disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 425-449.
    11. 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.
    12. Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    13. 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.
    14. Burdett, R.L. & Kozan, E., 2009. "Techniques for inserting additional trains into existing timetables," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 821-836, September.
    15. 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.
    16. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    17. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    18. Kroon, L.G. & Huisman, D. & Abbink, E.J.W. & Fioole, P-J. & Fischetti, M. & Maróti, G. & Schrijver, A. & Steenbeek, A. & Ybema, R., 2008. "The new Dutch timetable: The OR revolution," Econometric Institute Research Papers EI 2008-19, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    19. 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.
    20. 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.
    21. 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.
    22. 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.
    23. Cacchiani, Valentina & Furini, Fabio & Kidd, Martin Philip, 2016. "Approaches to a real-world Train Timetabling Problem in a railway node," Omega, Elsevier, vol. 58(C), pages 97-110.
    24. Canca, David & Barrena, Eva & De-Los-Santos, Alicia & Andrade-Pineda, José Luis, 2016. "Setting lines frequency and capacity in dense railway rapid transit networks with simultaneous passenger assignment," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 251-267.
    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. 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. Shi, Jungang & Yang, Lixing & Yang, Jing & Gao, Ziyou, 2018. "Service-oriented train timetabling with collaborative passenger flow control on an oversaturated metro line: An integer linear optimization approach," Transportation Research Part B: Methodological, Elsevier, vol. 110(C), pages 26-59.
    3. Liang, Jinpeng & Zang, Guangzhi & Liu, Haitao & Zheng, Jianfeng & Gao, Ziyou, 2023. "Reducing passenger waiting time in oversaturated metro lines with passenger flow control policy," Omega, Elsevier, vol. 117(C).
    4. 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.
    5. 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.
    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. 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.
    8. Xue, Hongjiao & Jia, Limin & Li, Jian & Guo, Jianyuan, 2022. "Jointly optimized demand-oriented train timetable and passenger flow control strategy for a congested subway line under a short-turning operation pattern," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    9. 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.
    10. 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.
    11. Kang, Liujiang & Meng, Qiang, 2017. "Two-phase decomposition method for the last train departure time choice in subway networks," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 568-582.
    12. Kang, Liujiang & Zhu, Xiaoning & Sun, Huijun & Puchinger, Jakob & Ruthmair, Mario & Hu, Bin, 2016. "Modeling the first train timetabling problem with minimal missed trains and synchronization time differences in subway networks," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 17-36.
    13. 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.
    14. Huang, Yeran & Mannino, Carlo & Yang, Lixing & Tang, Tao, 2020. "Coupling time-indexed and big-M formulations for real-time train scheduling during metro service disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 38-61.
    15. Liu, Renming & Li, Shukai & Yang, Lixing, 2020. "Collaborative optimization for metro train scheduling and train connections combined with passenger flow control strategy," Omega, Elsevier, vol. 90(C).
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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).

    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:104:y:2017:i:c:p:149-174. 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.