IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v313y2024i1p207-224.html
   My bibliography  Save this article

Train stop scheduling problem: An exact approach using valid inequalities and polar duality

Author

Listed:
  • Hamid, Faiz
  • Agarwal, Yogesh K.

Abstract

Consider the problem of minimizing the number of train stops on a particular rail line. The objective is to assign passengers of each origin-destination pair to different trains in such a way that train capacity and passenger demand constraints are satisfied with minimal stoppages. The literature refers to this problem as the train stop scheduling problem. The problem has been extensively studied for decades, yet an exact solution approach has not been proposed. This paper proposes several valid inequalities to strengthen the mixed-integer programming formulation and solve the problem exactly in a reasonable amount of CPU time. The concept of polar duality has been utilized to find more complex valid inequalities which may be hard to find otherwise. Despite the problem’s high practical relevance, valid inequalities for the problem have not yet been studied in the literature. An aggregation procedure has been proposed to solve large size problem instances exactly. Computational study demonstrate the efficacy of the proposed valid inequalities.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:313:y:2024:i:1:p:207-224
    DOI: 10.1016/j.ejor.2023.07.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723005611
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.07.023?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. Ghoneim, N. S. A. & Wirasinghe, S. C., 1986. "Optimum zone structure during peak periods for existing urban rail lines," Transportation Research Part B: Methodological, Elsevier, vol. 20(1), pages 7-18, February.
    2. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    3. Gao, Yuan & Kroon, Leo & Schmidt, Marie & Yang, Lixing, 2016. "Rescheduling a metro line in an over-crowded situation after disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 425-449.
    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. 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.
    8. 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.
    9. Arjang A. Assad, 1982. "A Class of Train-Scheduling Problems," Transportation Science, INFORMS, vol. 16(3), pages 281-310, August.
    10. 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.
    11. 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.
    12. Eberlein, Xu Jun & Wilson, Nigel H. M. & Barnhart, Cynthia & Bernstein, David, 1998. "The real-time deadheading problem in transit operations control," Transportation Research Part B: Methodological, Elsevier, vol. 32(2), pages 77-100, February.
    13. Huiling Fu & Benjamin R. Sperry & Lei Nie, 2013. "Operational Impacts of Using Restricted Passenger Flow Assignment in High-Speed Train Stop Scheduling Problem," Mathematical Problems in Engineering, Hindawi, vol. 2013, pages 1-8, December.
    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. 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.
    16. Huiling Fu & Lei Nie & Benjamin R. Sperry & Zhenhuan He, 2012. "Train Stop Scheduling in a High-Speed Rail Network by Utilizing a Two-Stage Approach," Mathematical Problems in Engineering, Hindawi, vol. 2012, pages 1-11, November.
    17. 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.
    18. 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. 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. 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.
    3. Schiewe, Alexander & Schiewe, Philine & Schmidt, Marie, 2019. "The line planning routing game," European Journal of Operational Research, Elsevier, vol. 274(2), pages 560-573.
    4. 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.
    5. 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.
    6. 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).
    7. 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.
    8. Goerigk, Marc & Schmidt, Marie, 2017. "Line planning with user-optimal route choice," European Journal of Operational Research, Elsevier, vol. 259(2), pages 424-436.
    9. 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.
    10. Gattermann, P. & Schiewe, A. & Schmidt, M.E., 2014. "The line planning routing game," ERIM Report Series Research in Management ERS-2014-017-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    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. Mathias Michaelis & Anita Schöbel, 2009. "Integrating line planning, timetabling, and vehicle scheduling: a customer-oriented heuristic," Public Transport, Springer, vol. 1(3), pages 211-232, August.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. Tatsuki Yamauchi & Mizuyo Takamatsu & Shinji Imahori, 2023. "Optimizing train stopping patterns for congestion management," Public Transport, Springer, vol. 15(1), pages 1-29, March.
    19. David Canca & Belén Navarro-Carmona & Gabriel Villa & Alejandro Zarzo, 2023. "A Multilayer Network Approach for the Bimodal Bus–Pedestrian Line Planning Problem," Mathematics, MDPI, vol. 11(19), pages 1-36, October.
    20. 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.

    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:313:y:2024:i:1:p:207-224. 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.