An exact approach to the flat shunting problem with a focus on car movement cost optimization

Abstract

Flat shunting is a classical railway yard operation that aims to rearrange a given sequence of railcars into a desired sequence by using a shunting engine and a set of shunting tracks. The operation considered in this study is a one-end push–pull process, which is particularly relevant when an initial classification or drop-off process cannot directly form the target outbound order. Compared to train timetabling or routing problems, this microscopic operational task is difficult to handle both practically and theoretically, as the shunting tracks have a strict first-in-last-out (FILO) requirement (i.e., cars can be coupled or decoupled only from one end of a track). Focusing on the multi-stage flat shunting problem, we develop a mixed-integer linear programming (MILP) model to optimize the number of engine actions, as the mesoscopic cost, and the number of car movements, as the microscopic cost, during pull-back and assignment operations. The proposed model is solved using a standard optimization solver and a customized branch-and-bound algorithm. A sequencing state measure is proposed to quantitatively evaluate the deviation of a car distribution in a yard from the desired final car sequence, leading to an effective heuristic rule that significantly improves branching efficiency. The proposed approach saves more than 99% of the computation time compared with the basic branch-and-bound algorithm. Through numerical experiments with several benchmarks, we found that optimizing generalized car movement costs can further improve the quality of shunting schedules even when the number of pull-back engine actions is already optimal.

Keywords

Flat shunting problem / Multi-stage sorting / Mixed-integer linear programming / Car movement cost / Branch-and-bound algorithm / Sequencing state measure

References

[1] Dahlhaus E, Horak P, Miller M, et al. The train marshalling problem. Discrete Appl Math, 2000, 1031–34154.

[2] Hansmann RS, Zimmermann UT. Optimal sorting of rolling stock at hump yards. Mathematics – key technology for the future, 2008Springer189203.

[3] Ministry of Railways of the People’s Republic of China (2006) Regulations on Railway Technical Management: Order No. 29 of the Ministry of Railways. Beijing (in Chinese)

[4] Daganzo CF, Dowling RG, Hall RW. Railroad classification yard throughput: the case of multistage triangular sorting. Transp Res Part A Gen, 1983, 17295106.

[5] National Bureau of Statistics of ChinaChina statistical yearbook 2019, 2019, Beijing: China Statistics Press

[6] Boysen N, Fliedner M, Jaehn F, et al. Shunting yard operations: theoretical aspects and applications. Eur J Oper Res, 2012, 2201114.

[7] Deleplanque S, Hosteins P, Pellegrini P, et al. Train management in freight shunting yards: formalisation and literature review. IET Intell Transp Syst, 2022, 161012861305.

[8] Gatto M, Maue J, Mihalák M, et al. Shunting for dummies: an introductory algorithmic survey. Robust and online large-scale optimization, 2009Springer310337.

[9] He S, Song R, Chaudhry SS. An integrated dispatching model for rail yards operations. Comput Oper Res, 2003, 307939966.

[10] Bohlin M, Hansmann R, Zimmermann UT. Optimization of railway freight shunting. Handbook of optimization in the railway industry, 2018Springer International Publishing181212.

[11] Beygang K, Krumke SO, Dahms FHW (2010) Train marshalling problem: algorithms and bounds. Technical Report 132, Technische Universität Kaiserslautern, Kaiserslautern

[12] Brueggeman L, Fellows M, Fleischer R et al (2012) Train marshalling is fixed parameter tractable. In: Kranakis E, Krizanc D, Luccio F (eds) Fun with Algorithms. Lecture Notes in Computer Science, vol. 7288. Springer, Berlin, Heidelberg, pp 51–56

[13] Rinaldi F, Rizzi R. Solving the train marshalling problem by inclusion–exclusion. Discrete Appl Math, 2017, 217: 685-690.

[14] Dörpinghaus J, Rainer S (2018) A graph-theoretic approach to the train marshalling problem. In: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems (FedCSIS), Poznan, Poland, 9–12 September 2018. IEEE, pp 227–231.

[15] Falsafain H, Tamannaei M. A novel dynamic programming approach to the train marshalling problem. IEEE Trans Intell Transport Syst, 2020, 212701710.

[16] Di Stefano G, Love Koči M. A graph theoretical approach to the shunting problem. Electron Notes Theor Comput Sci, 2004, 92: 16-33.

[17] Jaehn F, Rieder J, Wiehl A. Minimizing delays in a shunting yard. OA Spectrum, 2015, 372407429

[18] Haahr JT, Lusby RM. A matheuristic approach to integrate humping and pullout sequencing operations at railroad hump yards. Networks, 2016, 672126138.

[19] Daganzo CF. Static blocking at railyards: sorting implications and track requirements. Transp Sci, 1986, 203189199.

[20] Yagar S, Saccomanno FF, Shi Q. An efficient sequencing model for humping in a rail yard. Transp Res Part A Gen, 1983, 174251262.

[21] Dahlhaus E, Manne F, Miller M et al. Algorithms for combinatorial problems related to train marshalling. In: Proceedings of the Eleventh Australasian Workshop on Combinatorial Algorithms (AWOCA 2000), Hunter Valley, Australia, 29 July–1 August 2000. University of Newcastle, Newcastle, pp 7–16

[22] Lübbecke ME, Zimmermann UT. Shunting minimal rail car allocation. Comput Optim Appl, 2005, 313295308.

[23] Hansmann R (2011) Optimal sorting of rolling stock. Dissertation, Technische Universität Braunschweig

[24] Bohlin M, Gestrelius S, Dahms F et al (2013) Optimized shunting with mixed-usage tracks.Technical Report T201306, Swedish Institute of Computer Science (SICS)

[25] Jacob R, Márton P, Maue J, et al. Multistage methods for freight train classification. Networks, 2011, 57187105.

[26] Zien M, Kirschstein T, Bierwirth C. A study on sorting strategies in marshaling yards with a limited number of tracks and track capacity. J Rail Transp Plan Manag, 2025, 33100498

[27] Márton P, Maue J, Nunkesser M. An improved train classification procedure for the hump yard lausanne triage[C]//9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)(2009). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2009: 1–15.

[28] Adlbrecht J-A, Hüttler B, Zazgornik J, et al. The train marshalling by a single shunting engine problem. Transp Res Part C Emerg Technol, 2015, 58: 56-72.

[29] Jaehn F, Otto A, Seifried K. Shunting operations at flat yards: retrieving freight railcars from storage tracks. OR Spectr, 2018, 402367393

[30] Lee Y, Hsu N-Y. An optimization model for the container pre-marshalling problem. Comput Oper Res, 2007, 341132953313.

[31] Caserta M, Voß S, et al. GiacobiniBrabazon A, Cagnoni S, et al. A corridor method-based algorithm for the pre-marshalling problem M. Applications of evolutionary computing, 2009, Berlin, Heidelberg: Springer, 788-797. vol 5484

[32] Tierney K, Pacino D, Voß S. Solving the pre-marshalling problem to optimality with A* and IDA. Flex Serv Manuf J, 2017, 292223259.

[33] Hottung A, Tanaka S, Tierney K. Deep learning assisted heuristic tree search for the container pre-marshalling problem. Comput Oper Res, 2020, 113. 104781

[34] Petersen ER. Railyard modeling: part I. Prediction of put-through time. Transp Sci, 1977, 1113749.

[35] Peng QY, Wang CG. Railway traffic organization, 20152nd ednBeijingChina Railway Publishing House

[36] Laporte G. Generalized subtour elimination constraints and connectivity constraints. J Oper Res Soc, 1986, 375509514.

[37] Gao SW, Zhang DY. Elimination of inverse-order— a new model of shunting operation. J China Railway Soc, 2003, 25517(in Chinese)

[38] Büsing C, Maue J. de Berg M, Meyer U. Robust algorithms for sorting railway cars. Algorithms – ESA 2010, 2010, Berlin, Heidelberg: Springer, 350-361. vol 6346

Funding

National Science Foundation of China(52272324)

National Key Research and Development Program of China(2022YFB4300504)

Rights & permissions

The Author(s)