IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v305y2023i1p184-206.html

Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: A column-generation-based approach

Author

Listed:
  • Pan, Hanchuan
  • Yang, Lixing
  • Liang, Zhe

Abstract

Train timetabling and rolling stock circulation planning are two important optimization problems that arise in the daily operations of urban rail transit lines. This study proposes a novel approach to simultaneously optimize the train timetable and rolling stock circulation plan with flexible train compositions on an urban rail transit line in order to better match the passenger demand and supplied transport capacity, and further improve operation flexibility and extract gains in efficiency, in which the dynamic passenger demand is particularly considered in the formulation process. We first propose two integer linear programming models that are formulated on time-space networks by considering flexible coupling/splitting activities. The models consist of restricted master problems for optimizing the total generalized cost and subproblems that are used to generate different train composition routes. An effective column-generation-based diving heuristic algorithm is developed to solve the problem of interest, and it is able to simultaneously obtain the train timetable and rolling stock circulation plan. Several sets of experimental scenarios, involving relatively small-scale cases and a case derived from real-world Shanghai Metro data, are tested to verify the effectiveness of the proposed model and algorithm.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:305:y:2023:i:1:p:184-206
    DOI: 10.1016/j.ejor.2022.05.039
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722004283
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.05.039?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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Han, Zhenyu & Han, Baoming & Li, Dewei & Ning, Shangbin & Yang, Ruixia & Yin, Yonghao, 2021. "Train timetabling in rail transit network under uncertain and dynamic demand using Advanced and Adaptive NSGA-II," Transportation Research Part B: Methodological, Elsevier, vol. 154(C), pages 65-99.
    3. Arianna Alfieri & Rutger Groot & Leo Kroon & Alexander Schrijver, 2006. "Efficient Circulation of Railway Rolling Stock," Transportation Science, INFORMS, vol. 40(3), pages 378-391, August.
    4. Hartleb, Johann & Schmidt, Marie, 2022. "Railway timetabling with integrated passenger distribution," European Journal of Operational Research, Elsevier, vol. 298(3), pages 953-966.
    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. 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.
    7. 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.
    8. Liang, Zhe & Xiao, Fan & Qian, Xiongwen & Zhou, Lei & Jin, Xianfei & Lu, Xuehua & Karichery, Sureshan, 2018. "A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility," Transportation Research Part B: Methodological, Elsevier, vol. 113(C), pages 70-90.
    9. Zhe Liang & Wanpracha Art Chaovalitwongse, 2013. "A Network-Based Model for the Integrated Weekly Aircraft Maintenance Routing and Fleet Assignment Problem," Transportation Science, INFORMS, vol. 47(4), pages 493-507, November.
    10. Zhe Liang & Wanpracha Art Chaovalitwongse & Elsayed A. Elsayed, 2014. "Sequence Assignment Model for the Flight Conflict Resolution Problem," Transportation Science, INFORMS, vol. 48(3), pages 334-350, August.
    11. Jian Gang Jin & Kwong Meng Teo & Amedeo R. Odoni, 2016. "Optimizing Bus Bridging Services in Response to Disruptions of Urban Transit Rail Networks," Transportation Science, INFORMS, vol. 50(3), pages 790-804, August.
    12. 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.
    13. 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.
    14. 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.
    15. LeBlanc, Larry J., 1988. "Transit system network design," Transportation Research Part B: Methodological, Elsevier, vol. 22(5), pages 383-390, October.
    16. Nejib Ben-Khedher & Josephine Kintanar & Cecile Queille & William Stripling, 1998. "Schedule Optimization at SNCF: From Conception to Day of Departure," Interfaces, INFORMS, vol. 28(1), pages 6-23, February.
    17. Lingaya, Norbert & Cordeau, Jean-Françcois & Desaulniers, Guy & Desrosiers, Jacques & Soumis, Françcois, 2002. "Operational car assignment at VIA Rail Canada," Transportation Research Part B: Methodological, Elsevier, vol. 36(9), pages 755-778, November.
    18. 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.
    19. 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.
    20. 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.
    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. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    23. Haahr, Jørgen T. & Wagenaar, Joris C. & Veelenturf, Lucas P. & Kroon, Leo G., 2016. "A comparison of two exact methods for passenger railway rolling stock (re)scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 91(C), pages 15-32.
    24. 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.
    25. 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.
    26. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2001. "Simultaneous Assignment of Locomotives and Cars to Passenger Trains," Operations Research, INFORMS, vol. 49(4), pages 531-548, August.
    27. Jacques Desrosiers & Marco E. Lübbecke, 2005. "A Primer in Column Generation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 1-32, Springer.
    28. Wang, Yihui & Tang, Tao & Ning, Bin & Meng, Lingyun, 2017. "Integrated optimization of regular train schedule and train circulation plan for urban rail transit lines," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 83-104.
    29. Yang, Lixing & Zhang, Yan & Li, Shukai & Gao, Yuan, 2016. "A two-stage stochastic optimization model for the transfer activity choice in metro networks," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 271-297.
    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. Zhou, Housheng & Wang, Hongyang & Wang, Hai & Qi, Jianguo & Yang, Lixing, 2026. "Seamless urban metro networks: A shared depot perspective on rolling stock scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 204(C).
    2. Wang, Yun & Zhou, Yu & Yang, Hai & Yu, Bin & Liu, Xiaobing, 2025. "Optimizing bus bridging services with mode choice in response to urban rail transit emergencies," European Journal of Operational Research, Elsevier, vol. 323(1), pages 108-124.
    3. 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).
    4. Weiya Chen & Qinyu Zhuo & Lu Zhang, 2023. "Modeling and Heuristically Solving Group Train Operation Scheduling for Heavy-Haul Railway Transportation," Mathematics, MDPI, vol. 11(11), pages 1-15, May.
    5. 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).
    6. Pan, Hanchuan & Yang, Lixing & Liang, Zhe & Yang, Hai, 2024. "New Exact Algorithm for the integrated train timetabling and rolling stock circulation planning problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 316(3), pages 906-929.
    7. Zhong, Linhuan & Liu, Yang & Xu, Guangming & Liu, Wei & Yang, Hai, 2025. "Train capacity optimization under stochastic demand: A flexible composition strategy with extra-long trains," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).
    8. Zhu, Jia Hui & Dollevoet, Twan & Huisman, Dennis, 2025. "An exact and heuristic framework for rolling stock rescheduling with railway infrastructure availability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 195(C).
    9. Liu, Xuan & Zhou, Min & Dong, Hairong, 2025. "Joint rescheduling for timetable and platform assignment of High-Speed Railways via graph neural network-based Deep Reinforcement Learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 202(C).
    10. Berktas, Nihal & Zografos, Konstantinos G., 2025. "Generic model for capacity allocation on transportation terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 196(C).
    11. Wang, Hongyang & Yang, Lixing & Zhang, Jinlei & Luo, Qin & Fan, Zhongsheng, 2024. "Real-time train timetabling with virtual coupling operations on a Y-type metro line," European Journal of Operational Research, Elsevier, vol. 319(1), pages 168-190.
    12. Zheng, Nan & Li, Shukai & Yuan, Yin & Xie, Dongfan, 2026. "Train timetable optimization for urban railway systems under the virtual formation mode combined with the rolling stock utilization strategy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 207(C).
    13. Wang, Yiran & Mo, Pengli & Chen, Jingxu & Liu, Zhiyuan, 2025. "Managing oversaturation in BRT corridors: A new approach of timetabling for resilience enhancement using a tailored integer L-shaped algorithm," European Journal of Operational Research, Elsevier, vol. 320(1), pages 219-238.
    14. Xu, Guangming & Zhong, Linhuan & Liu, Wei & Guo, Jing, 2024. "A flexible train composition strategy with extra-long trains for high-speed railway corridors with time-varying demand," Transportation Research Part B: Methodological, Elsevier, vol. 179(C).
    15. Sun, Xuting & Zhao, Xiaoyao & Chung, Sai-Ho & Ma, Hoi-Lam, 2025. "An interactive decision making framework design for the outsourcing cooperation between the service provider and the airline: An exact bilevel method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 199(C).
    16. Hongyang Wang & Lixing Yang & Housheng Zhou, 2025. "Enhancing Efficiency and Fairness: Rolling Stock Scheduling with Virtual Coupling and Short-Turning Strategies," Transportation Science, INFORMS, vol. 59(6), pages 1303-1328, November.
    17. Li, Tao & Li, Dewei & Ji, Haotian & Ma, Jialun, 2026. "Integrated optimization of train timetabling, stop planning, rolling stock maintenance and assignment with flexible train composition and short-turning strategies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 207(C).
    18. Xiu, Cong & Pan, Jinyi & D’Ariano, Andrea & Zhan, Shuguang & Tessitore, Marta Leonina & Peng, Qiyuan, 2025. "Integrated train rescheduling and passenger reassignment for disrupted high-speed railway networks: A hierarchical Benders decomposition and column generation approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 200(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. 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. 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.
    3. Pan, Hanchuan & Liu, Zhigang & Yang, Lixing & Liang, Zhe & Wu, Qiang & Li, Sijie, 2021. "A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    4. Wang, Hongyang & Yang, Lixing & Zhang, Jinlei & Luo, Qin & Fan, Zhongsheng, 2024. "Real-time train timetabling with virtual coupling operations on a Y-type metro line," European Journal of Operational Research, Elsevier, vol. 319(1), pages 168-190.
    5. 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.
    6. 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).
    7. Li, Tao & Li, Dewei & Ji, Haotian & Ma, Jialun, 2026. "Integrated optimization of train timetabling, stop planning, rolling stock maintenance and assignment with flexible train composition and short-turning strategies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 207(C).
    8. 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.
    9. 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).
    10. Pan, Hanchuan & Yang, Lixing & Liang, Zhe & Yang, Hai, 2024. "New Exact Algorithm for the integrated train timetabling and rolling stock circulation planning problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 316(3), pages 906-929.
    11. 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.
    12. Shuo Zhao & Jinfei Wu & Zhenyi Li & Ge Meng, 2022. "Train Operational Plan Optimization for Urban Rail Transit Lines Considering Circulation Balance," Sustainability, MDPI, vol. 14(9), pages 1-21, April.
    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. 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.
    15. 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).
    16. 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).
    17. Zheng, Nan & Li, Shukai & Yuan, Yin & Xie, Dongfan, 2026. "Train timetable optimization for urban railway systems under the virtual formation mode combined with the rolling stock utilization strategy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 207(C).
    18. 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).
    19. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhan, Shuguang & Peng, Qiyuan, 2024. "Joint rolling stock rotation planning and depot deadhead scheduling in complicated urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 314(2), pages 665-684.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:ejores:v:305:y:2023:i:1:p:184-206. 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/locate/eor .

    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.