IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v38y2004i3p379-393.html
   My bibliography  Save this article

A Branch-and-Cut Approach for Solving Railway Line-Planning Problems

Author

Listed:
  • Jan-Willem Goossens

    (Department of Quantitative Economics, University of Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands)

  • Stan van Hoesel

    (Department of Quantitative Economics, University of Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands)

  • Leo Kroon

    (Rotterdam School of Management, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands)

Abstract

An important strategic phase in the planning process of a railway operator is the development of a line plan, i.e., a set of routes (paths) in a network of tracks, operated at a given hourly frequency. We consider a model formulation of the line-planning problem where total operating costs are to be minimized. This model is solved with a branch-and-cut approach, for which we develop a variety of valid inequalities and reduction methods. A computational study of five real-life instances based on examples from Netherlands Railways (NS) is included.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:38:y:2004:i:3:p:379-393
    DOI: 10.1287/trsc.1030.0051
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1030.0051
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1030.0051?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
    ---><---

    References listed on IDEAS

    as
    1. Goossens Jan-Willem & Hoesel Stan van & Kroon Leo, 2002. "On solving multi-type line planning problems," Research Memorandum 017, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Dietrich, B. L. & Escudero, L. F., 1994. "Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts," European Journal of Operational Research, Elsevier, vol. 73(3), pages 539-546, March.
    3. J. T. Linderoth & M. W. P. Savelsbergh, 1999. "A Computational Study of Search Strategies for Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 173-187, May.
    4. 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. 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.
    2. Bissan Ghaddar & Ignacio Gómez-Casares & Julio González-Díaz & Brais González-Rodríguez & Beatriz Pateiro-López & Sofía Rodríguez-Ballesteros, 2023. "Learning for Spatial Branching: An Algorithm Selection Approach," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1024-1043, September.
    3. Bugarinovic, Mirjana & Boskovic, Branislav, 2015. "A systems approach to access charges in unbundling railways," European Journal of Operational Research, Elsevier, vol. 240(3), pages 848-860.
    4. P. Herings & Kirsten Rohde, 2006. "Time-inconsistent preferences in a general equilibrium model," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(3), pages 591-619, November.
    5. Eliasson, Jonas & Börjesson, Maria, 2014. "On timetable assumptions in railway investment appraisal," Transport Policy, Elsevier, vol. 36(C), pages 118-126.
    6. Daniel Kowalczyk & Roel Leus & Christopher Hojny & Stefan Røpke, 2024. "A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1696-1714, December.
    7. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    8. 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.
    9. S. Göttlich & A. Potschka & C. Teuber, 2019. "A partial outer convexification approach to control transmission lines," Computational Optimization and Applications, Springer, vol. 72(2), pages 431-456, March.
    10. 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.
    11. Laureano Escudero & Javier Salmeron, 2005. "On a Fix-and-Relax Framework for a Class of Project Scheduling Problems," Annals of Operations Research, Springer, vol. 140(1), pages 163-188, November.
    12. Mohammad Sabbagh & Richard Soland, 2009. "An improved partial enumeration algorithm for integer programming problems," Annals of Operations Research, Springer, vol. 166(1), pages 147-161, February.
    13. 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.
    14. Canca, David & Barrena, Eva & De-Los-Santos, Alicia & Andrade-Pineda, José Luis, 2016. "Setting lines frequency and capacity in dense railway rapid transit networks with simultaneous passenger assignment," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 251-267.
    15. Goerigk, Marc & Schmidt, Marie, 2017. "Line planning with user-optimal route choice," European Journal of Operational Research, Elsevier, vol. 259(2), pages 424-436.
    16. 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).
    17. 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.
    18. Lluís-Miquel Munguía & Geoffrey Oxberry & Deepak Rajan & Yuji Shinano, 2019. "Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs," Computational Optimization and Applications, Springer, vol. 73(2), pages 575-601, June.
    19. 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.
    20. Yu Yang & Natashia Boland & Martin Savelsbergh, 2021. "Multivariable Branching: A 0-1 Knapsack Problem Case Study," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1354-1367, October.

    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:inm:ortrsc:v:38:y:2004:i:3:p:379-393. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.