IDEAS home Printed from https://ideas.repec.org/p/ems/eureri/78820.html

A Comparison of Optimization Methods for Solving the Depot Matching and Parking Problem

Author

Listed:
  • Haahr, J.T.
  • Lusby, R.M.
  • Wagenaar, J.C.

Abstract

We consider the Train Unit Shunting Problem, an important plan- ning problem for passenger railway operators. This problem entails assigning physical train units to scheduled train services in such a way that the resulting shunting yard operations are feasible. As such, it arises at every shunting yard in the railway network and involves matching train units to arriving and departing train services as well as assigning the selected matchings to appropriate shunting yard tracks. We present a comparison benchmark of multiple solution approaches for this problem. In particular, we have developed a Constraint Pro- gramming formulation, a Column Generation approach, and a random- ized greedy heuristic. We compare and benchmark these approaches against slightly adjusted existing methods based on a a Mixed Inte- ger Linear Program, and a Two-Stage heuristic. The benchmark con- tains multiple real-life instances provided by the Danish State Rail- ways (DSB) and Netherlands Railways (NS). The results highlight the strengths and weaknesses of the considered approaches.

Suggested Citation

  • Haahr, J.T. & Lusby, R.M. & Wagenaar, J.C., 2015. "A Comparison of Optimization Methods for Solving the Depot Matching and Parking Problem," ERIM Report Series Research in Management ERS-2015-013-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.
    • Handle: RePEc:ems:eureri:78820
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/78820/ERS-2015-013-LIS.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Freling, R. & Lentink, R.M. & Kroon, L.G. & Huisman, D., 2002. "Shunting of Passenger Train Units in a Railway Station," ERIM Report Series Research in Management ERS-2002-74-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.
    2. Pisinger, David, 1995. "A minimal algorithm for the multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 394-410, June.
    3. Leo G. Kroon & Ramon M. Lentink & Alexander Schrijver, 2008. "Shunting of Passenger Train Units: An Integrated Approach," Transportation Science, INFORMS, vol. 42(4), pages 436-449, November.
    4. Fioole, Pieter-Jan & Kroon, Leo & Maroti, Gabor & Schrijver, Alexander, 2006. "A rolling stock circulation model for combining and splitting of passenger trains," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1281-1297, October.
    5. Richard Freling & Ramon M. Lentink & Leo G. Kroon & Dennis Huisman, 2005. "Shunting of Passenger Train Units in a Railway Station," Transportation Science, INFORMS, vol. 39(2), pages 261-272, May.
    6. Pisinger, David, 1995. "An expanding-core algorithm for the exact 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 87(1), pages 175-187, November.
    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. Wang, Dian & Yao, Ling & D’Ariano, Andrea & Zhan, Shuguang & Wang, Lisha, 2025. "Rolling stock shunt operation planning in urban rail transit depots with maintenance consideration," Transportation Research Part B: Methodological, Elsevier, vol. 199(C).

    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. Haahr, Jørgen & Lusby, Richard M., 2017. "Integrating rolling stock scheduling with train unit shunting," European Journal of Operational Research, Elsevier, vol. 259(2), pages 452-468.
    2. Christian Artigues & Eric Bourreau & Vincent Jost & Safia Kedad-Sidhoum & François Ramond, 2018. "Trains do not vanish: the ROADEF/EURO challenge 2014," Annals of Operations Research, Springer, vol. 271(2), pages 1091-1105, December.
    3. Liu, Xiaowei & Peng, Qiyuan & Du, Bo & Zhang, Yongxiang & Zhong, Qingwei & Yan, Xu, 2024. "An influence path analytic study for the operational performance of large passenger railway stations: The China case," Transportation Research Part A: Policy and Practice, Elsevier, vol. 188(C).
    4. Zhu, Jia Hui & Dollevoet, Twan & Huisman, Dennis, 2025. "An exact and heuristic framework for rolling stock rescheduling with railway infrastructure availability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 195(C).
    5. Budai-Balke, G. & Maróti, G. & Dekker, R. & Huisman, D. & Kroon, L.G., 2007. "Re-scheduling in railways: the rolling stock balancing problem," Econometric Institute Research Papers EI 2007-21, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    6. Haahr, Jørgen Thorlund & Lusby, Richard M. & Wagenaar, Joris Camiel, 2017. "Optimization methods for the Train Unit Shunting Problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 981-995.
    7. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    8. Boysen, Nils & Fliedner, Malte & Jaehn, Florian & Pesch, Erwin, 2012. "Shunting yard operations: Theoretical aspects and applications," European Journal of Operational Research, Elsevier, vol. 220(1), pages 1-14.
    9. Yanasse, Horacio Hideki & Pinto Lamosa, Maria Jose, 2007. "An integrated cutting stock and sequencing problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1353-1370, December.
    10. Martin Josef Geiger & Sandra Huber & Sebastian Langton & Marius Leschik & Christian Lindorf & Ulrich Tüshaus, 2018. "Multi-attribute assignment of trains to departures in rolling stock management," Annals of Operations Research, Springer, vol. 271(2), pages 1131-1163, December.
    11. Wang, Dian & Yao, Ling & D’Ariano, Andrea & Zhan, Shuguang & Wang, Lisha, 2025. "Rolling stock shunt operation planning in urban rail transit depots with maintenance consideration," Transportation Research Part B: Methodological, Elsevier, vol. 199(C).
    12. Kroon, L.G. & Lentink, R.M. & Schrijver, A., 2006. "Shunting of Passenger Train Units: an Integrated Approach," ERIM Report Series Research in Management ERS-2006-068-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.
    13. repec:ers:journl:v:xxiv:y:2021:i:3:p:316-334 is not listed on IDEAS
    14. Li Lei & Raymond S K Kwan & Zhiyuan Lin & Pedro J Copado-Mendez, 2022. "Resolution of coupling order and station level constraints in train unit scheduling," Public Transport, Springer, vol. 14(1), pages 27-61, March.
    15. Kateryna Czerniachowska, 2022. "A genetic algorithm for the retail shelf space allocation problem with virtual segments," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 364-412, March.
    16. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    17. Boysen, Nils & Emde, Simon, 2016. "The parallel stack loading problem to minimize blockages," European Journal of Operational Research, Elsevier, vol. 249(2), pages 618-627.
    18. Kyungmin Kim & Minseok Song, 2022. "Energy-Saving SSD Cache Management for Video Servers with Heterogeneous HDDs," Energies, MDPI, vol. 15(10), pages 1-16, May.
    19. Hoto, Robinson & Arenales, Marcos & Maculan, Nelson, 2007. "The one dimensional Compartmentalised Knapsack Problem: A case study," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1183-1195, December.
    20. Mavrotas, George & Figueira, José Rui & Florios, Kostas, 2009. "Solving the bi-objective multidimensional knapsack problem exploiting the concept of core," MPRA Paper 105087, University Library of Munich, Germany.
    21. Subhash C. Sarin & Hanif D. Sherali & Seon Ki Kim, 2014. "A branch‐and‐price approach for the stochastic generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(2), pages 131-143, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:ems:eureri:78820. 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: RePub The email address of this maintainer does not seem to be valid anymore. Please ask RePub to update the entry or send us the correct address (email available below). General contact details of provider: https://edirc.repec.org/data/erimanl.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.