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. 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.
    2. 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.
    3. 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).
    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. 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. 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.
    4. Hejl, Lukáš & Šůcha, Přemysl & Novák, Antonín & Hanzálek, Zdeněk, 2022. "Minimizing the weighted number of tardy jobs on a single machine: Strongly correlated instances," European Journal of Operational Research, Elsevier, vol. 298(2), pages 413-424.
    5. Canca, David & Andrade-Pineda, José Luis & De los Santos, Alicia & Calle, Marcos, 2018. "The Railway Rapid Transit frequency setting problem with speed-dependent operation costs," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 494-519.
    6. Evelien van der Hurk & Haris N. Koutsopoulos & Nigel Wilson & Leo G. Kroon & Gábor Maróti, 2016. "Shuttle Planning for Link Closures in Urban Public Transport Networks," Transportation Science, INFORMS, vol. 50(3), pages 947-965, August.
    7. 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.
    8. Philine Gattermann & Jonas Harbering & Anita Schöbel, 2017. "Line pool generation," Public Transport, Springer, vol. 9(1), pages 7-32, July.
    9. 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.
    10. Eliasson, Jonas & Börjesson, Maria, 2014. "On timetable assumptions in railway investment appraisal," Transport Policy, Elsevier, vol. 36(C), pages 118-126.
    11. 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.
    12. Chu, James C. & Korsesthakarn, Kanticha & Hsu, Yu-Ting & Wu, Hua-Yen, 2019. "Models and a solution algorithm for planning transfer synchronization of bus timetables," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 247-266.
    13. 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.
    14. 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.
    15. 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.
    16. Brenda Dietrich, 2007. "Some of my favorite integer programming applications at IBM," Annals of Operations Research, Springer, vol. 149(1), pages 75-80, February.
    17. 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.
    18. Andrea Lodi & Giulia Zarpellon, 2017. "On learning and branching: a survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 207-236, July.
    19. 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.
    20. 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.

    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.