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

Combined line planning and train timetabling for strongly heterogeneous railway lines with direct connections

Author

Listed:
  • Yan, Fei
  • Goverde, Rob M.P.

Abstract

Rail systems have been developing rapidly in recent years aiming at satisfying the growing passenger demand and shortening passenger travel time. The line planning problem (LPP) and train timetabling problem (TTP) are two key issues at the strategic level and tactical level, laying the foundation of a high-level service quality for railway operation. In this paper, a multi-frequency LPP (MF-LPP) model and a multi-period TTP (MP-TTP) model are introduced for direct connections, with consideration of both periodic and aperiodic nature to meet strongly heterogeneous train services and reduce the capacity loss of train operating companies. A combined LPP and TTP method is designed considering timetable robustness, timetable regularity, and passenger travel time. For a given line pool, a multi-objective mixed integer linear programming model for the MF-LPP is formulated to obtain a line plan with multiple line frequencies by minimizing travel time, empty-seat-hour and the number of lines. Using the acquired line plan from the previous step, a MP-TTP model is proposed to achieve the minimal travel time, the maximal timetable robustness and the minimal number of overtakings. The two models work iteratively with designed feedback constraints to find a better plan for the rail transport system. Numerical experiments are applied to verify the performance of the proposed model and solution approach.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:127:y:2019:i:c:p:20-46
    DOI: 10.1016/j.trb.2019.06.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517311797
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2019.06.010?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. Kroon, Leo & Maróti, Gábor & Helmrich, Mathijn Retel & Vromans, Michiel & Dekker, Rommert, 2008. "Stochastic improvement of cyclic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 42(6), pages 553-570, July.
    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. Bussieck, Michael R. & Kreuzer, Peter & Zimmermann, Uwe T., 1997. "Optimal lines for railway systems," European Journal of Operational Research, Elsevier, vol. 96(1), pages 54-63, January.
    4. Goossens, Jan-Willem & van Hoesel, Stan & Kroon, Leo, 2006. "On solving multi-type railway line planning problems," European Journal of Operational Research, Elsevier, vol. 168(2), pages 403-424, January.
    5. Goverde, Rob M.P., 2007. "Railway timetable stability analysis using max-plus system theory," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 179-201, February.
    6. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    7. Mor Kaspi & Tal Raviv, 2013. "Service-Oriented Line Planning and Timetabling for Passenger Trains," Transportation Science, INFORMS, vol. 47(3), pages 295-311, August.
    8. Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    9. Ralf Borndörfer & Martin Grötschel & Marc E. Pfetsch, 2007. "A Column-Generation Approach to Line Planning in Public Transport," Transportation Science, INFORMS, vol. 41(1), pages 123-132, February.
    10. Michael R. Bussieck & Thomas Lindner & Marco E. Lübbecke, 2004. "A fast algorithm for near cost optimal line plans," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 59(2), pages 205-220, June.
    11. Christian Liebchen, 2007. "Periodic Timetable Optimization in Public Transport," Operations Research Proceedings, in: Karl-Heinz Waldmann & Ulrike M. Stocker (ed.), Operations Research Proceedings 2006, pages 29-36, Springer.
    12. Laura Galli & Sebastian Stiller, 2018. "Modern Challenges in Timetabling," International Series in Operations Research & Management Science, in: Ralf Borndörfer & Torsten Klug & Leonardo Lamorgese & Carlo Mannino & Markus Reuther & Thomas Schlec (ed.), Handbook of Optimization in the Railway Industry, chapter 0, pages 117-140, Springer.
    13. 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.
    14. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    15. Jan-Willem Goossens & Stan van Hoesel & Leo Kroon, 2004. "A Branch-and-Cut Approach for Solving Railway Line-Planning Problems," Transportation Science, INFORMS, vol. 38(3), pages 379-393, August.
    16. 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.
    17. Claessens, M. T. & van Dijk, N. M. & Zwaneveld, P. J., 1998. "Cost optimal allocation of rail passenger lines," European Journal of Operational Research, Elsevier, vol. 110(3), pages 474-489, November.
    18. 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.
    19. Ralf Borndörfer & Heide Hoppmann & Marika Karbstein, 2017. "Passenger routing for periodic timetable optimization," Public Transport, Springer, vol. 9(1), pages 115-135, July.
    20. Dejan Jovanović & Patrick T. Harker, 1991. "Tactical Scheduling of Rail Operations: The SCAN I System," Transportation Science, INFORMS, vol. 25(1), pages 46-64, February.
    21. 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.
    22. 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.
    23. Sparing, Daniel & Goverde, Rob M.P., 2017. "A cycle time optimization model for generating stable periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 198-223.
    24. Zhao, Wei & Xu, Liangjie & Dong, Zhijie Sasha & Qi, Bozhao & Qin, Lingqiao & BinRan,, 2018. "Improving transfer feasibility for older travelers inside high-speed train station," Transportation Research Part A: Policy and Practice, Elsevier, vol. 113(C), pages 302-317.
    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. Wenliang Zhou & Jing Kang & Jin Qin & Sha Li & Yu Huang, 2022. "Robust Optimization of High-Speed Railway Train Plan Based on Multiple Demand Scenarios," Mathematics, MDPI, vol. 10(8), pages 1-26, April.
    2. Han Zheng & Junhua Chen & Zhaocha Huang & Jianhao Zhu, 2022. "Joint Optimization of Multi-Cycle Timetable Considering Supply-to-Demand Relationship and Energy Consumption for Rail Express," Mathematics, MDPI, vol. 10(21), pages 1-29, November.
    3. Ruxin Wang & Lei Nie & Yuyan Tan, 2020. "Evaluating Line Capacity with an Analytical UIC Code 406 Compression Method and Blocking Time Stairway," Energies, MDPI, vol. 13(7), pages 1-16, April.
    4. Maciej Kruszyna, 2022. "NOAH as an Innovative Tool for Modeling the Use of Suburban Railways," Sustainability, MDPI, vol. 15(1), pages 1-17, December.
    5. 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.
    6. Tatsuki Yamauchi & Mizuyo Takamatsu & Shinji Imahori, 2023. "Optimizing train stopping patterns for congestion management," Public Transport, Springer, vol. 15(1), pages 1-29, March.
    7. 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.
    8. Yan, Fei & Bešinović, Nikola & Goverde, Rob M.P., 2019. "Multi-objective periodic railway timetabling on dense heterogeneous railway corridors," Transportation Research Part B: Methodological, Elsevier, vol. 125(C), pages 52-75.
    9. Wanqi Wang & Yun Bao & Sihui Long, 2022. "Rescheduling Urban Rail Transit Trains to Serve Passengers from Uncertain Delayed High-Speed Railway Trains," Sustainability, MDPI, vol. 14(9), pages 1-20, May.
    10. Jinfei Wu & Xinghua Shan & Jingxia Sun & Shengyuan Weng & Shuo Zhao, 2023. "Daily Line Planning Optimization for High-Speed Railway Lines," Sustainability, MDPI, vol. 15(4), pages 1-20, February.
    11. 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.
    12. Polinder, Gert-Jaap & Schmidt, Marie & Huisman, Dennis, 2021. "Timetabling for strategic passenger railway planning," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 111-135.

    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. 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.
    2. 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).
    3. Tatsuki Yamauchi & Mizuyo Takamatsu & Shinji Imahori, 2023. "Optimizing train stopping patterns for congestion management," Public Transport, Springer, vol. 15(1), pages 1-29, March.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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).
    9. Wenliang Zhou & Yujun Huang & Naijie Chai & Bo Li & Xiang Li, 2022. "A Line Planning Optimization Model for High-Speed Railway Network Merging Newly-Built Railway Lines," Mathematics, MDPI, vol. 10(17), pages 1-34, September.
    10. 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.
    11. Jinfei Wu & Xinghua Shan & Jingxia Sun & Shengyuan Weng & Shuo Zhao, 2023. "Daily Line Planning Optimization for High-Speed Railway Lines," Sustainability, MDPI, vol. 15(4), pages 1-20, February.
    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. Wenliang Zhou & Wenzhuang Fan & Xiaorong You & Lianbo Deng, 2019. "Demand-Oriented Train Timetabling Integrated with Passenger Train-Booking Decisions," Sustainability, MDPI, vol. 11(18), pages 1-34, September.
    14. 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.
    15. Schiewe, Alexander & Schiewe, Philine & Schmidt, Marie, 2019. "The line planning routing game," European Journal of Operational Research, Elsevier, vol. 274(2), pages 560-573.
    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. Jonas Harbering, 2017. "Delay resistant line planning with a view towards passenger transfers," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(3), pages 467-496, October.
    18. Tangjian Wei & Feng Shi & Guangming Xu, 2019. "Estimation of Time-Varying Passenger Demand for High Speed Rail System," Complexity, Hindawi, vol. 2019, pages 1-24, March.
    19. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    20. Hartleb, Johann & Schmidt, Marie, 2022. "Railway timetabling with integrated passenger distribution," European Journal of Operational Research, Elsevier, vol. 298(3), pages 953-966.

    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:127:y:2019:i:c:p:20-46. 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.