×

Minimizing delays in a shunting yard. (English) Zbl 1311.90011

Summary: We consider an operational process at shunting yards, where freight cars are disassembled and reassembled via a system of tracks and switches to form outbound trains with no restriction on the order of the freight cars. Given are due dates for each outbound train and priority values for its freight cars. Furthermore, the composition and the processing time of each inbound train is part of the input. An outbound train is defined by a set of freight cars taken from one or many inbound trains. In this context, we try to minimize the weighted tardiness of all outbound trains by determining the optimal humping sequence of inbound trains. We show that this problem is NP-hard and we present a simple mixed integer problem formulation. Besides two heuristic approaches and an implementation in CPLEX, the main focus of our single stage shunting problem to minimize weighted tardiness (SSSWT) is on developing an exact branch and bound procedure. Therefore, we present powerful precedence constraints and priority rules to reduce the solution space. Further, we compare the runtime and accuracy of the proposed algorithms with the results of CPLEX optimizer in a computational study.

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C11 Mixed integer programming

Software:

CPLEX
Full Text: DOI

References:

[1] Bektaş 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 · doi:10.1016/j.trc.2008.11.003
[2] Beygang K, Krumke SO, Dahms F (2010) Train marshalling problem—algorithms and bounds. Technical Report 132, University of Kaiserslautern, Fachbereich Mathematik
[3] Bohlin M, Dahms F, Flier H, Gestrelius S (2012) Optimal freight train classification using column generation. In: Delling D, Liberti L ( eds) 12th workshop on algorithmic approaches for transportation modelling, optimization, and systems, vol 25, Dagstuhl, Germany, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 10-22 · Zbl 1247.90027
[4] Bohlin M, Flier H, Maue J, Mihalák M (2011) Track allocation in freight-train classification with mixed tracks. In: Caprara A, Kontogiannis S (eds) 11th workshop on algorithmic approaches for transportation modelling, optimization, and systems, vol 20, Dagstuhl, Germany. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 38-51 · Zbl 1247.90028
[5] Bontekoning Y, Priemus H (2004) Breakthrough innovations in intermodal freight transport. Transp Plan Technol 27:335-345 · doi:10.1080/0308106042000273031
[6] Boysen N, Fliedner M, Jaehn F, Pesch E (2012) Shunting yard operations: theoretical aspects and applications. Eur J Oper Res 220(1):1-14 · doi:10.1016/j.ejor.2012.01.043
[7] Boysen N, Fliedner M, Kellner M (2010) Determining fixed crane areas in rail-rail transshipment yards. Transp Res Part B 46:1005-1016 · doi:10.1016/j.tre.2010.05.004
[8] Brueggeman, L.; Fellows, M.; Fleischer, R.; Lackner, M.; Komusiewicz, C.; Koutis, Y.; Pfandler, A.; Rosamond, F.; Kranakis, E. (ed.); Krizanc, D. (ed.); Luccio, F. (ed.), Train marshalling is fixed parameter tractable, No. 7288, 51-56 (2012), Berlin · doi:10.1007/978-3-642-30347-0_8
[9] Dahlhaus E, Horak P, Miller M, Ryan JF (2000) The train marshalling problem. Discret Appl Math 103:41-54 · Zbl 0962.90009 · doi:10.1016/S0166-218X(99)00219-X
[10] Dirnberger JR, Barkan CPL (2007) Lean railroading for improving railroad classification terminal performance: bottleneck management methods. Transp Res Rec 1995:52-61 · doi:10.3141/1995-07
[11] Du J, Leung JY (1990) Minimizing total tardiness on one machine is np-hard. Math Oper Res 15(3):483-495 · Zbl 0714.90052 · doi:10.1287/moor.15.3.483
[12] Emmons H (1969) One-machine sequencing to minimize certain functions of job tardiness. Oper Res 17:701-715 · Zbl 0176.50005 · doi:10.1287/opre.17.4.701
[13] Hansmann, RS; Zimmermann, UT; Krebs, H-J (ed.); Jäger, W. (ed.), Optimal sorting of rolling stock at hump yards, 189-203 (2008), Berlin · doi:10.1007/978-3-540-77203-3_14
[14] Jacob R, Marton P, Maue J, Nunkesser M (2011) Multistage methods for freight train classification. Networks 57:87-105 · Zbl 1205.90049 · doi:10.1002/net.20385
[15] Jaehn F, Rieder J, Wiehl A (2015) Single stage shunting minimizing weighted departure times. Omega 52:133-141 · doi:10.1016/j.omega.2014.11.001
[16] Kanet JJ (2007) New precedence theorems for one-machine weighted tardiness. Math Oper Res 32:579-588 · Zbl 1341.90047 · doi:10.1287/moor.1070.0255
[17] Kraft ER (2000) A hump sequencing algorithm for real time management of train connection reliability. J Transp Res Forum 39:95-115
[18] Kraft ER (2002a) Priority-based classification for improving connection reliability in railroad yards: Part I. Integration with car scheduling. J Transp Res Forum 56:93-105
[19] Kraft ER (2002b) Priority-based classification for improving connection reliability in railroad yards: Part II. Dynamic block to track assignment. J Transp Res Forum 56:107-119
[20] Lenstra J, Kan AR, Brucker P (1977) Complexity of machine scheduling problems. In: Hammer PL, Johnson BK, Nemhauser G (eds) Studies in integer programming, vol 1 of Annals of Discrete Mathematics. Elsevier, pp 343-362 · Zbl 0353.68067
[21] Statistisches Bundesamt (2013a) Güterverkehr 2013. Press release 41/14 · Zbl 0962.90009
[22] Statistisches Bundesamt (2013) Verkehr auf einen Blick 2013:42-46
[23] Yagar S, Saccomanno FF, Shi Q (1983) An efficient sequencing model for humping in a rail yard. Transp Res Part A 17A:251-262 · doi:10.1016/0191-2607(83)90089-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.