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

Passenger-oriented rolling stock scheduling in the metro system with multiple depots: Network flow based approaches

Author

Listed:
  • Wang, Entai
  • Yang, Lixing
  • Yin, Jiateng
  • Zhang, Jinlei
  • Gao, Ziyou

Abstract

This study investigates a rolling stock scheduling problem on a metro line with multiple depots. Two novel optimization models, i.e., an arc-based and a path-based network-flow models, are formulated with the aim of improving the service level and reducing the operation cost simultaneously, in which the flexible train composition mode is also taken into consideration to well match the transport capacity and time-varying passenger demand. To solve the proposed models, a branch-and-price (B&P) approach is designed to find the near optimal operation schemes, in which the column generation is used to solve the relaxed problem at each node of the searching tree, where a dynamic programming approach is embedded to solve the pricing sub-problem associated with each depot to generate promising paths (columns) for each rolling stock unit, and then the branch-and-bound (B&B) procedure is incorporated to find integral solutions. To test the performance of the proposed approaches, a series of numerical experiments are conducted both on small-scale and real-life cases of the Beijing metro Batong line with historically recorded passenger data. The computation results have verified the improved operational efficiency and a better service level of the solutions found by our proposed approaches.

Suggested Citation

  • Wang, Entai & Yang, Lixing & Yin, Jiateng & Zhang, Jinlei & Gao, Ziyou, 2024. "Passenger-oriented rolling stock scheduling in the metro system with multiple depots: Network flow based approaches," Transportation Research Part B: Methodological, Elsevier, vol. 180(C).
    • Handle: RePEc:eee:transb:v:180:y:2024:i:c:s0191261524000092
    DOI: 10.1016/j.trb.2024.102885
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261524000092
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2024.102885?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. Zhong, Qingwei & Lusby, Richard M. & Larsen, Jesper & Zhang, Yongxiang & Peng, Qiyuan, 2019. "Rolling stock scheduling with maintenance requirements at the Chinese High-Speed Railway," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 24-44.
    2. 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.
    3. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    4. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    5. Luis Cadarso & Ángel Marín, 2012. "Integration of timetable planning and rolling stock in rapid transit networks," Annals of Operations Research, Springer, vol. 199(1), pages 113-135, October.
    6. 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.
    7. 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.
    8. 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.
    9. Shang, Pan & Li, Ruimin & Guo, Jifu & Xian, Kai & Zhou, Xuesong, 2019. "Integrating Lagrangian and Eulerian observations for passenger flow state estimation in an urban rail transit network: A space-time-state hyper network-based assignment approach," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 135-167.
    10. Canca, David & Andrade-Pineda, José Luis & De los Santos, Alicia & Calle, Marcos, 2018. "The Railway Rapid Transit frequency setting problem with speed-dependent operation costs," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 494-519.
    11. 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.
    12. 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.
    13. Wang, Yihui & Zhao, Kangqi & D’Ariano, Andrea & Niu, Ru & Li, Shukai & Luan, Xiaojie, 2021. "Real-time integrated train rescheduling and rolling stock circulation planning for a metro line under disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 152(C), pages 87-117.
    14. Zhu, Yongqiu & Goverde, Rob M.P., 2019. "Railway timetable rescheduling with flexible stopping and flexible short-turning during disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 149-181.
    15. Zhou, Housheng & Qi, Jianguo & Yang, Lixing & Shi, Jungang & Pan, Hanchuan & Gao, Yuan, 2022. "Joint optimization of train timetabling and rolling stock circulation planning: A novel flexible train composition mode," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 352-385.
    16. 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.
    17. 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.
    18. Fioole, Pieter-Jan & Kroon, Leo & Maroti, Gabor & Schrijver, Alexander, 2006. "A rolling stock circulation model for combining and splitting of passenger trains," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1281-1297, October.
    19. Szymula, Christopher & Bešinović, Nikola, 2020. "Passenger-centered vulnerability assessment of railway networks," Transportation Research Part B: Methodological, Elsevier, vol. 136(C), pages 30-61.
    20. Wang, Yihui & D’Ariano, Andrea & Yin, Jiateng & Meng, Lingyun & Tang, Tao & Ning, Bin, 2018. "Passenger demand oriented train scheduling and rolling stock circulation planning for an urban rail transit line," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 193-227.
    21. 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.
    22. Erwin Abbink & Bianca van den Berg & Leo Kroon & Marc Salomon, 2004. "Allocation of Railway Rolling Stock for Passenger Trains," Transportation Science, INFORMS, vol. 38(1), pages 33-41, February.
    23. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    24. 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.
    25. Valentina Cacchiani & Alberto Caprara & Paolo Toth, 2019. "An Effective Peak Period Heuristic for Railway Rolling Stock Planning," Transportation Science, INFORMS, vol. 53(3), pages 746-762, May.
    26. Gao, Yuan & Schmidt, Marie & Yang, Lixing & Gao, Ziyou, 2020. "A branch-and-price approach for trip sequence planning of high-speed train units," Omega, Elsevier, vol. 92(C).
    27. Gábor Maróti & Leo Kroon, 2005. "Maintenance Routing for Train Units: The Transition Model," Transportation Science, INFORMS, vol. 39(4), pages 518-525, November.
    28. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    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. Yang, Lin & Gao, Yuan & D’Ariano, Andrea & Xu, Suxiu, 2024. "Integrated optimization of train timetable and train unit circulation for a Y-type urban rail transit system with flexible train composition mode," Omega, Elsevier, vol. 122(C).
    2. Zhao, Yaqiong & Li, Dewei & Yin, Yonghao & Zhao, Xiaoli, 2023. "Integrated optimization of demand-driven timetable, train formation plan and rolling stock circulation with variable running times and dwell times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    3. 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.
    4. 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.
    5. Yuan, Jiawei & Gao, Yuan & Li, Shukai & Liu, Pei & Yang, Lixing, 2022. "Integrated optimization of train timetable, rolling stock assignment and short-turning strategy for a metro line," European Journal of Operational Research, Elsevier, vol. 301(3), pages 855-874.
    6. Zhou, Housheng & Qi, Jianguo & Yang, Lixing & Shi, Jungang & Pan, Hanchuan & Gao, Yuan, 2022. "Joint optimization of train timetabling and rolling stock circulation planning: A novel flexible train composition mode," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 352-385.
    7. Pan, Hanchuan & Yang, Lixing & Liang, Zhe, 2023. "Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: A column-generation-based approach," European Journal of Operational Research, Elsevier, vol. 305(1), pages 184-206.
    8. Gao, Yuan & Xia, Jun & D’Ariano, Andrea & Yang, Lixing, 2022. "Weekly rolling stock planning in Chinese high-speed rail networks," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 295-322.
    9. 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.
    10. Chai, Simin & Yin, Jiateng & D’Ariano, Andrea & Liu, Ronghui & Yang, Lixing & Tang, Tao, 2024. "A branch-and-cut algorithm for scheduling train platoons in urban rail networks," Transportation Research Part B: Methodological, Elsevier, vol. 181(C).
    11. Wang, Xuekai & D’Ariano, Andrea & Su, Shuai & Tang, Tao, 2023. "Cooperative train control during the power supply shortage in metro system: A multi-agent reinforcement learning approach," Transportation Research Part B: Methodological, Elsevier, vol. 170(C), pages 244-278.
    12. 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.
    13. Chen, Zebin & Li, Shukai & D’Ariano, Andrea & Yang, Lixing, 2022. "Real-time optimization for train regulation and stop-skipping adjustment strategy of urban rail transit lines," Omega, Elsevier, vol. 110(C).
    14. 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).
    15. 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.
    16. Gao, Yuan & Schmidt, Marie & Yang, Lixing & Gao, Ziyou, 2020. "A branch-and-price approach for trip sequence planning of high-speed train units," Omega, Elsevier, vol. 92(C).
    17. Yuan, Yin & Li, Shukai & Yang, Lixing & Gao, Ziyou, 2022. "Real-time optimization of train regulation and passenger flow control for urban rail transit network under frequent disturbances," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    18. 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.
    19. Niu, Huimin & Zhou, Xuesong & Tian, Xiaopeng, 2018. "Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 70-101.
    20. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Tao, Siyu & Zhang, Bojian & Peng, Qiyuan, 2024. "A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems," Transportation Research Part B: Methodological, Elsevier, vol. 183(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:180:y:2024:i:c:s0191261524000092. 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.