Abstract
In shunting yards, railcars of incoming trains are uncoupled and reassembled to outbound trains. This time-critical process that employs a complex system of switches, hump hills, and classification tracks requires plenty interdependent decision problems to be solved. An elementary decision task among these is the train makeup problem, which assigns railcars of inbound freight trains to outbound trains, such that the priority values of the selected cuts of railcars are maximized and given train capacities are observed. This assignment decision is further complicated by the fact that railcars cannot facultatively be selected, but the buildup sequences of incoming trains need to be considered. This work introduces and discusses the basic train makeup problem, analyses its complexity status and develops suited exact and heuristic solution procedures that are tested in a comprehensive computational study.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ballis A, Golias J (2002) Comparative evaluation of existing and innovative rail-road freight transport terminals. Transp Res Part A Policy Pract 36:593–611
Bektas T, Crainic TG, Morency V (2009) Improving the performance of rail yards through dynamic reassignments of empty cars. Transp Res Part C 17C:259–273
Bontekoning Y, Priemus H (2004) Breakthrough innovations in intermodal freight transport. Transp Plan Technol 27:335–345
Boysen N, Fliedner M, Jaehn F, Pesch E (2012) Shunting yard operations: theoretical aspects and applications. Eur J Oper Res 220:1–14
Boysen N, Fliedner M, Jaehn F, Pesch E (2013) A survey on container processing in railway yards. Transp Sci 47:312–329
Daganzo CF, Dowling RG, Hall RW (1983) Railroad classification yard throughput: the case of multistage triangular sorting. Transp Res Part A 17A:95–106
Dahlhaus E, Horak P, Miller M, Ryan JF (2000) The train marshalling problem. Discrete Appl Math 103:41–54
Di Stefano G, Koci ML (2004) A graph theoretical approach to the shunting problem. Electron Notes Theor Comput Sci 92:16–33
European Commission (2001) White paper, European transport policy for 2010: time to decide. COM 370
Freville A (2004) The multidimensional 0–1 knapsack problem: an overview. Eur J Oper Res 155:1–21
Gatto M, Maue J, Mihalák M, Widmayer P (2009) Shunting for dummies: an introductory algorithmic survey. In: Ahuja R, Möhring R, Zaroliagis C (eds) Robust and online large-scale optimization, lecture notes in computer science, vol 5868. Springer, Berlin, pp 310–337
Goldberg A, Tarjan R (1988) A new approach to the maximum flow problem. J ACM 35:921–940
Hansmann RS, Zimmermann UT (2008) Optimal sorting of rolling stock at hump yards. In: Krebs H-J, Jäger W (eds) Mathematics—key technology for the future. Springer, Berlin Heidelberg, pp 189–203
He S, Song R, Chaudhry SS (2000) Fuzzy dispatching model and genetic algorithms for railyards operations. Eur J Oper Res 124:307–331
He S, Song R, Chaudhry SS (2003) An integrated dispatching model for rail yards operations. Comput Oper Res 30:939–966
Jacob R, Marton P, Maue J, Nunkesser M (2011) Multistage methods for freight train classification. Networks 57:87–105
Kraft ER (2000) A hump sequence algorithm for real time management of train connection reliability. J Transp Res Forum 39:95–115
Kroon LG, Lentink RM, Schrijver A (2008) Shunting of passenger train units: an integrated approach. Transp Sci 42:436–449
Li H, Song R, Jin M, He S (2014) Optimization of railcar connection plan in a classification yard. In: Transportation research board 93rd annual meeting, No. 14-3091
Lowerre B (1976) The Harpy speech recognition system. PhD thesis, Carnegie Mellon University
Lübbecke ME, Zimmermann UT (2005) Shunting minimal rail car allocation. Comput Optim Appl 31:295–308
Menakerman N, Rom R (2001) Bin packing with item fragmentation. In: Dehne F, Sack J-R, Tamassia R (eds) Algorithms and data structures. Springer, Berlin, pp 313–324
Petersen ER (1977) Railyard modeling: part I. Transp Sci 11:37–49
Puchinger J, Raidl GR, Pferschy U (2010) The multidimensional knapsack problem: structure and algorithms. INFORMS J Comput 22:250–265
RPM (2014) Railroad performance measures. http://www.railroadpm.org/.Accessed March 2014
Shachnai H, Tamir T, Yehezkely O (2006) Approximation schemes for packing with item fragmentation. In: Erlebach T, Persinao G (eds) Approximation and online algorithms. Springer, Berlin Heidelberg, pp 334–347
Shachnai H, Tamir T, Yehezkely O (2008) Approximation schemes for packing with item fragmentation. Theory Comput Syst 43:81–98
Shachnai H, Yehezkely O (2007) Fast asymptotic FPTAS for packing fragmentable items with costs. In: Csuhaj-Varjú E, Ésik Z (eds) Fundamentals of computation theory. Springer, Berlin, pp 482–493
Tsamboulas D, Vrenken H, Lekka AM (2007) Assessment of a transport policy potential for intermodal mode shift on a European scale. Transp Res Part A Policy Pract 41:715–733
US DOT (1998) Transportation equity act for the 21st century, moving Americans into the 21st century. Department of Transportation
Verband der Automobilindustrie e.V. (VDA) (2006) Jahresbericht 2006, Frankfurt am Main 2006 (in German)
Weingartner HM, Ness DN (1967) Methods for the solution of the multidimensional 0/1 knapsack problem. Oper Res 15:83–103
Yagar S, Saccomanno FF, Shi Q (1983) An efficient sequencing model for humping in a rail yard. Transp Res Part A Gen 17:251–262
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boysen, N., Emde, S. & Fliedner, M. The basic train makeup problem in shunting yards. OR Spectrum 38, 207–233 (2016). https://doi.org/10.1007/s00291-015-0412-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-015-0412-0