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

Modeling the first train timetabling problem with minimal missed trains and synchronization time differences in subway networks

Author

Listed:
  • Kang, Liujiang
  • Zhu, Xiaoning
  • Sun, Huijun
  • Puchinger, Jakob
  • Ruthmair, Mario
  • Hu, Bin

Abstract

Urban railway transportation organization is a systematic activity that is usually composed of several stages, including network design, line planning, timetabling, rolling stock and staffing. In this paper, we study the optimization of first train timetables for an urban railway network that focuses on designing convenient and smooth timetables for morning passengers. We propose a mixed integer programming (MIP) model for minimizing train arrival time differences and the number of missed trains, i.e., the number of trains without transfers within a reasonable time at interchange stations as an alternative to minimize passenger transfer waiting times. This is interesting from the operator's point of view, and we show that both criteria are equivalent. Starting from an intuitive model for the first train transfer problem, we then linearize the non-linear constraints by utilizing problem specific knowledge. In addition, a local search algorithm is developed to solve the timetabling problem. Through computational experiments involving the Beijing subway system, we demonstrate the computational efficiency of the exact model and the heuristic approach. Finally, three practical suggestions are proposed for the operation and management of the urban railway transit system.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:93:y:2016:i:pa:p:17-36
    DOI: 10.1016/j.trb.2016.07.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515301144
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2016.07.006?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. Ibarra-Rojas, Omar J. & Rios-Solis, Yasmin A., 2012. "Synchronization of bus timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 599-614.
    2. Rachel C. W. Wong & Tony W. Y. Yuen & Kwok Wah Fung & Janny M. Y. Leung, 2008. "Optimizing Timetable Synchronization for Rail Mass Transit," Transportation Science, INFORMS, vol. 42(1), pages 57-69, February.
    3. 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.
    4. 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.
    5. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    6. Shafahi, Yousef & Khani, Alireza, 2010. "A practical model for transfer optimization in a transit network: Model formulations and solutions," Transportation Research Part A: Policy and Practice, Elsevier, vol. 44(6), pages 377-389, July.
    7. 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.
    8. 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.
    9. Ibarra-Rojas, Omar J. & Giesen, Ricardo & Rios-Solis, Yasmin A., 2014. "An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 35-46.
    10. Kang, Liujiang & Wu, Jianjun & Sun, Huijun & Zhu, Xiaoning & Gao, Ziyou, 2015. "A case study on the coordination of last trains for the Beijing subway network," Transportation Research Part B: Methodological, Elsevier, vol. 72(C), pages 112-127.
    11. Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    12. Ceder, A. & Golany, B. & Tal, O., 2001. "Creating bus timetables with maximal synchronization," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(10), pages 913-928, December.
    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. Leonardo Lamorgese & Carlo Mannino & Mauro Piacentini, 2016. "Optimal Train Dispatching by Benders’-Like Reformulation," Transportation Science, INFORMS, vol. 50(3), pages 910-925, August.
    15. 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.
    16. Kang, Liujiang & Wu, Jianjun & Sun, Huijun & Zhu, Xiaoning & Wang, Bo, 2015. "A practical model for last train rescheduling with train delay in urban railway transit networks," Omega, Elsevier, vol. 50(C), pages 29-42.
    17. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    18. 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.
    19. 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.
    20. Guihaire, Valérie & Hao, Jin-Kao, 2008. "Transit network design and scheduling: A global review," Transportation Research Part A: Policy and Practice, Elsevier, vol. 42(10), pages 1251-1273, December.
    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. Ying, Cheng-shuo & Chow, Andy H.F. & Nguyen, Hoa T.M. & Chin, Kwai-Sang, 2022. "Multi-agent deep reinforcement learning for adaptive coordinated metro service operations with flexible train composition," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 36-59.
    2. Kang, Liujiang & Zhu, Xiaoning & Sun, Huijun & Wu, Jianjun & Gao, Ziyou & Hu, Bin, 2019. "Last train timetabling optimization and bus bridging service management in urban railway transit networks," Omega, Elsevier, vol. 84(C), pages 31-44.
    3. Blanco, Víctor & Conde, Eduardo & Hinojosa, Yolanda & Puerto, Justo, 2020. "An optimization model for line planning and timetabling in automated urban metro subway networks. A case study," Omega, Elsevier, vol. 92(C).
    4. Kang, Liujiang & Sun, Huijun & Wu, Jianjun & Gao, Ziyou, 2020. "Last train station-skipping, transfer-accessible and energy-efficient scheduling in subway networks," Energy, Elsevier, vol. 206(C).
    5. Hu, Yuting & Li, Shukai & Dessouky, Maged M. & Yang, Lixing & Gao, Ziyou, 2022. "Computationally efficient train timetable generation of metro networks with uncertain transfer walking time to reduce passenger waiting time: A generalized Benders decomposition-based method," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 210-231.
    6. Mitra Heidari & Seyyed-Mahdi Hosseini-Motlagh & Nariman Nikoo, 2020. "A subway planning bi-objective multi-period optimization model integrating timetabling and vehicle scheduling: a case study of Tehran," Transportation, Springer, vol. 47(1), pages 417-443, February.
    7. Xuan Li & Toshiyuki Yamamoto & Tao Yan & Lili Lu & Xiaofei Ye, 2020. "First Train Timetabling for Urban Rail Transit Networks with Maximum Passenger Transfer Satisfaction," Sustainability, MDPI, vol. 12(10), pages 1-22, May.
    8. Kang, Liujiang & Li, Hao & Sun, Huijun & Wu, Jianjun & Cao, Zhiguang & Buhigiro, Nsabimana, 2021. "First train timetabling and bus service bridging in intermodal bus-and-train transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 443-462.
    9. 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.
    10. Huang, Kang & Wu, Jianjun & Sun, Huijun & Yang, Xin & Gao, Ziyou & Feng, Xujie, 2022. "Timetable synchronization optimization in a subway–bus network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    11. Zhou, Yu & Wang, Yun & Yang, Hai & Yan, Xuedong, 2019. "Last train scheduling for maximizing passenger destination reachability in urban rail transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 79-95.

    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. 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.
    2. Kang, Liujiang & Li, Hao & Sun, Huijun & Wu, Jianjun & Cao, Zhiguang & Buhigiro, Nsabimana, 2021. "First train timetabling and bus service bridging in intermodal bus-and-train transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 443-462.
    3. Guo, Xin & Sun, Huijun & Wu, Jianjun & Jin, Jiangang & Zhou, Jin & Gao, Ziyou, 2017. "Multiperiod-based timetable optimization for metro transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 46-67.
    4. Zhang, Di & Gao, Yuan & Yang, Lixing & Cui, Lixin, 2024. "Timetable synchronization of the last several trains at night in an urban rail transit network," European Journal of Operational Research, Elsevier, vol. 313(2), pages 494-512.
    5. 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.
    6. Kang, Liujiang & Zhu, Xiaoning & Sun, Huijun & Wu, Jianjun & Gao, Ziyou & Hu, Bin, 2019. "Last train timetabling optimization and bus bridging service management in urban railway transit networks," Omega, Elsevier, vol. 84(C), pages 31-44.
    7. 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.
    8. Pan Shang & Yu Yao & Liya Yang & Lingyun Meng & Pengli Mo, 2021. "Integrated Model for Timetabling and Circulation Planning on an Urban Rail Transit Line: a Coupled Network-Based Flow Formulation," Networks and Spatial Economics, Springer, vol. 21(2), pages 331-364, June.
    9. 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.
    10. 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).
    11. Yin, Jiateng & Wang, Miao & D’Ariano, Andrea & Zhang, Jinlei & Yang, Lixing, 2023. "Synchronization of train timetables in an urban rail network: A bi-objective optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    12. 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.
    13. 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.
    14. Blanco, Víctor & Conde, Eduardo & Hinojosa, Yolanda & Puerto, Justo, 2020. "An optimization model for line planning and timetabling in automated urban metro subway networks. A case study," Omega, Elsevier, vol. 92(C).
    15. Zhang, Quan & Li, Xuan & Yan, Tao & Lu, Lili & Shi, Yang, 2022. "Last train timetabling optimization for minimizing passenger transfer failures in urban rail transit networks: A time period based approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    16. Chu, James C. & Korsesthakarn, Kanticha & Hsu, Yu-Ting & Wu, Hua-Yen, 2019. "Models and a solution algorithm for planning transfer synchronization of bus timetables," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 247-266.
    17. Guo, Xin & Wu, Jianjun & Sun, Huijun & Yang, Xin & Jin, Jian Gang & Wang, David Z.W., 2020. "Scheduling synchronization in urban rail transit networks: Trade-offs between transfer passenger and last train operation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 463-490.
    18. Hu, Yuting & Li, Shukai & Dessouky, Maged M. & Yang, Lixing & Gao, Ziyou, 2022. "Computationally efficient train timetable generation of metro networks with uncertain transfer walking time to reduce passenger waiting time: A generalized Benders decomposition-based method," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 210-231.
    19. Kuo, Yong-Hong & Leung, Janny M.Y. & Yan, Yimo, 2023. "Public transport for smart cities: Recent innovations and future challenges," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1001-1026.
    20. Ansarilari, Zahra & Bodur, Merve & Shalaby, Amer, 2024. "A novel model for transfer synchronization in transit networks and a Lagrangian-based heuristic solution method," European Journal of Operational Research, Elsevier, vol. 317(1), pages 76-91.

    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:93:y:2016:i:pa:p:17-36. 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.