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

Railway line planning with passenger routing: Direct-service network representations and a two-phase solution approach

Author

Listed:
  • Yao, Zhiyuan
  • Nie, Lei
  • Fu, Huiling

Abstract

The railway line planning problem (LPP) plays a crucial role in determining the quality of services provided to passengers, as well as operation costs borne by railway companies. In periodic railway LPPs, it is common to consider passenger transfers between train lines to realize a general passenger travel cost setting in the railway system. While detecting passenger transfers requires incorporating passenger routing into mathematical formulations, thereby significantly complicating the problem. Studies on transfer-included LPPs are generally based on the Change&Go network that is constructed based on a pre-given line pool, which however is usually non-exhaustive due to computational intractability. To efficiently include passenger transfers in large-scale railway LPPs, this paper proposes a novel extended direct-service network representation of LPP, where lines are dynamically generated within the optimization process, and part of passenger transfers between lines can be precisely captured without the need for explicit modeling of passengers’ distribution on specific lines. A two-phase solution approach based on the representation is designed. The first phase formulates LPP with part of transfers as a path-based service network design model, solved using a branch-price-and-cut algorithm. The second phase conducts a neighborhood search around the first-phase solution to seek better ones when considering all passenger transfers. Numerical results showcase the good performance of the two-phase solution approach. It delivers optimal solutions in 18 out of 24 test instances for a small case and achieves optimality gaps within 2.85% across all small instances. The large case study of China’s Shandong high-speed railway network whose line pool size reaches millions demonstrates the scalability of the approach and its advantage over the traditional Change&Go method with partial line pools and an exact model developed in the paper.

Suggested Citation

  • Yao, Zhiyuan & Nie, Lei & Fu, Huiling, 2024. "Railway line planning with passenger routing: Direct-service network representations and a two-phase solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    • Handle: RePEc:eee:transb:v:186:y:2024:i:c:s0191261524001139
    DOI: 10.1016/j.trb.2024.102989
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261524001139
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2024.102989?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. Goerigk, Marc & Schmidt, Marie, 2017. "Line planning with user-optimal route choice," European Journal of Operational Research, Elsevier, vol. 259(2), pages 424-436.
    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. Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron, 2021. "Fixed-Charge Network Design Problems," Springer Books, in: Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron (ed.), Network Design with Applications to Transportation and Logistics, chapter 0, pages 15-28, Springer.
    4. 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.
    5. Bum Hwan Park & Yong-Il Seo & Sung-Pil Hong & Hag-Lae Rho, 2013. "Column Generation Approach To Line Planning With Various Halting Patterns — Application To The Korean High-Speed Railway," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 30(04), pages 1-19.
    6. 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.
    7. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    8. Chang, Yu-Hern & Yeh, Chung-Hsing & Shen, Ching-Cheng, 2000. "A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 91-106, February.
    9. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    10. 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.
    11. 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.
    12. Lin, Dung-Ying & Ku, Yu-Hsiung, 2014. "An implicit enumeration algorithm for the passenger service planning problem: Application to the Taiwan Railways Administration line," European Journal of Operational Research, Elsevier, vol. 238(3), pages 863-875.
    13. 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.
    14. Philine Gattermann & Jonas Harbering & Anita Schöbel, 2017. "Line pool generation," Public Transport, Springer, vol. 9(1), pages 7-32, July.
    15. Ruslan Sadykov & François Vanderbeck & Artur Pessoa & Issam Tahiri & Eduardo Uchoa, 2019. "Primal Heuristics for Branch and Price: The Assets of Diving Methods," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 251-267, April.
    16. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    17. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    18. 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.
    19. 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.
    20. Naga V. C. Gudapati & Enrico Malaguti & Michele Monaci, 2022. "Network Design with Service Requirements: Scaling-up the Size of Solvable Problems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2571-2582, September.
    21. Ralf Borndörfer & Martin Grötschel & Marc E. Pfetsch, 2008. "Models for Line Planning in Public Transport," Lecture Notes in Economics and Mathematical Systems, in: Mark Hickman & Pitu Mirchandani & Stefan Voß (ed.), Computer-aided Systems in Public Transport, pages 363-378, Springer.
    22. 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.
    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. Hu, Huaibin & Yue, Yixiang & Fu, Huiling & Li, Jiaxi, 2024. "How to optimize train lines for diverse passenger demands: A line planning approach providing matched train services for each O-D market," Transportation Research Part A: Policy and Practice, Elsevier, vol. 186(C).
    2. 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.
    3. 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).
    4. Hamid, Faiz & Agarwal, Yogesh K., 2024. "Train stop scheduling problem: An exact approach using valid inequalities and polar duality," European Journal of Operational Research, Elsevier, vol. 313(1), pages 207-224.
    5. Tatsuki Yamauchi & Mizuyo Takamatsu & Shinji Imahori, 2023. "Optimizing train stopping patterns for congestion management," Public Transport, Springer, vol. 15(1), pages 1-29, March.
    6. 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.
    7. 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.
    8. Schiewe, Alexander & Schiewe, Philine & Schmidt, Marie, 2019. "The line planning routing game," European Journal of Operational Research, Elsevier, vol. 274(2), pages 560-573.
    9. 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.
    10. Simon Bull & Jesper Larsen & Richard M. Lusby & Natalia J. Rezanova, 2019. "Optimising the travel time of a line plan," 4OR, Springer, vol. 17(3), pages 225-259, September.
    11. 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.
    12. Wenliang Zhou & Xiang Li & Xin Shi, 2023. "Joint Optimization of Time-Dependent Line Planning and Differential Pricing with Passenger Train Choice in High-Speed Railway Networks," Mathematics, MDPI, vol. 11(6), pages 1-28, March.
    13. 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.
    14. Goerigk, Marc & Schmidt, Marie, 2017. "Line planning with user-optimal route choice," European Journal of Operational Research, Elsevier, vol. 259(2), pages 424-436.
    15. Xin Zhang & Lei Nie & Xin Wu & Yu Ke, 2020. "How to Optimize Train Stops under Diverse Passenger Demand: a New Line Planning Method for Large-Scale High-Speed Rail Networks," Networks and Spatial Economics, Springer, vol. 20(4), pages 963-988, December.
    16. Shuo Zhao & Xiwei Mi & Zhenyi Li, 2019. "A Stop-Probability Approach for O-D Service Frequency on High-Speed Railway Lines," Sustainability, MDPI, vol. 11(24), pages 1-21, December.
    17. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Peng, Qiyuan, 2024. "Integrating train service route design with passenger flow allocation for an urban rail transit line," European Journal of Operational Research, Elsevier, vol. 313(1), pages 146-170.
    18. Guan, J.F. & Yang, Hai & Wirasinghe, S.C., 2006. "Simultaneous optimization of transit line configuration and passenger line assignment," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 885-902, December.
    19. 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.
    20. 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.

    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:186:y:2024:i:c:s0191261524001139. 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.