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

Train timetabling in rail transit network under uncertain and dynamic demand using Advanced and Adaptive NSGA-II

Author

Listed:
  • Han, Zhenyu
  • Han, Baoming
  • Li, Dewei
  • Ning, Shangbin
  • Yang, Ruixia
  • Yin, Yonghao

Abstract

It is critical to design an adaptable and stable train timetable for long-term use in rail transit network that not only meets the dynamicity of passenger demand in different hours within one day, but also meets the uncertainty of passenger demand in different days. In this study, a scenario-based train timetabling framework is constructed to classify the possibilities of passenger demand in multiple days into a set of scenarios based on profile and volume of passenger demand. On this basis, multi-scenario demand input method (MM) is introduced to deal with the uncertainty of passenger demand, which is different from one-scenario method (OM) and average-scenario method (AM). A MM-based mixed-integer linear programming model is formulated for the bi-objective train timetabling problem under uncertain and dynamic demand at acyclic network level, in which multi-scenario small-granularity passenger demand follows actual distribution processed from historical data. The two objectives are to minimize train service cost and penalized passenger waiting time from perspectives of enterprises and passengers. Advanced and Adaptive NSGA II (AANSGA-II) is proposed to cope with the high-complexity bi-objective problem, which applies advanced population sorting based on neighborhood distance, adaptive genetic operation based on scoring mechanism and improved population initialization based on boundary individuals. The model and algorithm are testified by a small-scale numerical experiment on a virtual line and a large-scale real-world instance in Shenyang Metro network. As a result, MM-based train timetables are generally better than AM-based and OM-based train timetables in reducing generalized cost and raising robustness. Besides, AANSGA-II is more applicable than NSGA-II and CPLEX in shortening computation time at the same time of improving computation result.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:154:y:2021:i:c:p:65-99
    DOI: 10.1016/j.trb.2021.10.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261521001867
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2021.10.002?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. 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).
    2. 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.
    3. Ying, Cheng-shuo & Chow, Andy H.F. & Chin, Kwai-Sang, 2020. "An actor-critic deep reinforcement learning approach for metro train scheduling with rolling stock circulation under stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 210-235.
    4. Masoud Shakibayifar & Erfan Hassannayebi & Hossein Jafary & Arman Sajedinejad, 2017. "Stochastic optimization of an urban rail timetable under time‐dependent and uncertain demand," Applied Stochastic Models in Business and Industry, John Wiley & Sons, vol. 33(6), pages 640-661, November.
    5. 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.
    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. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Erfan Hassannayebi & Seyed Hessameddin Zegordi & Masoud Yaghini & Mohammad Reza Amin-Naseri, 2017. "Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals," Transportation Planning and Technology, Taylor & Francis Journals, vol. 40(3), pages 278-304, April.
    12. Yang, Songpo & Liao, Feixiong & Wu, Jianjun & Timmermans, Harry J.P. & Sun, Huijun & Gao, Ziyou, 2020. "A bi-objective timetable optimization model incorporating energy allocation and passenger assignment in an energy-regenerative metro system," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 85-113.
    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. 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.
    2. Shi, Jungang & Yang, Jing & Yang, Lixing & Tao, Lefeng & Qiang, Shengjie & Di, Zhen & Guo, Junhua, 2023. "Safety-oriented train timetabling and stop planning with time-varying and elastic demand on overcrowded commuter metro lines," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    3. Zhichao Cao & Yuqing Wang & Zihao Yang & Changjun Chen & Silin Zhang, 2023. "Timetable Rescheduling Using Skip-Stop Strategy for Sustainable Urban Rail Transit," Sustainability, MDPI, vol. 15(19), pages 1-29, October.
    4. 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).

    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. Shi, Jungang & Yang, Jing & Yang, Lixing & Tao, Lefeng & Qiang, Shengjie & Di, Zhen & Guo, Junhua, 2023. "Safety-oriented train timetabling and stop planning with time-varying and elastic demand on overcrowded commuter metro lines," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    2. 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.
    3. Chen, Zhiwei & Li, Xiaopeng, 2021. "Designing corridor systems with modular autonomous vehicles enabling station-wise docking: Discrete modeling method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    4. 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).
    5. Pu, Song & Zhan, Shuguang, 2021. "Two-stage robust railway line-planning approach with passenger demand uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    6. Sadrani, Mohammad & Tirachini, Alejandro & Antoniou, Constantinos, 2022. "Vehicle dispatching plan for minimizing passenger waiting time in a corridor with buses of different sizes: Model formulation and solution approaches," European Journal of Operational Research, Elsevier, vol. 299(1), pages 263-282.
    7. 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.
    8. 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).
    9. 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.
    10. Huang, Yu & Zhou, Wenliang & Qin, Jin & Deng, Lianbo, 2023. "Optimization of energy-efficiency train schedule considering passenger demand and rolling stock circulation plan of subway line," Energy, Elsevier, vol. 275(C).
    11. 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.
    12. 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).
    13. 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).
    14. 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).
    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. Lu, Yahan & Yang, Lixing & Yang, Hai & Zhou, Housheng & Gao, Ziyou, 2023. "Robust collaborative passenger flow control on a congested metro line: A joint optimization with train timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 27-55.
    17. Wu, Yinghui & Yang, Hai & Zhao, Shuo & Shang, Pan, 2021. "Mitigating unfairness in urban rail transit operation: A mixed-integer linear programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 418-442.
    18. 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.
    19. 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).
    20. 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.

    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:154:y:2021:i:c:p:65-99. 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.