New bounds and algorithms for the transshipment yard scheduling problem. (English) Zbl 1280.90033

Summary: In a modern rail-rail transshipment yard huge gantry cranes transship containers between different freight trains, so that hub-and-spoke railway systems are enabled. In this context, we consider the transshipment yard scheduling problem (TYSP) where trains have to be assigned to bundles, which jointly enter and leave the yard. The objective is to minimize split moves and revisits. Split moves appear whenever containers have to be exchanged between trains of different bundles, whereas revisits occur if a train has to enter the yard twice, because some container dedicated to this train was not available during its first visit. We extend the basic TYSP, so that additional real-world requirements of modern rail-rail yards, e.g., the one currently constructed in Hannover-Lehrte, are considered. We provide complexity proofs for different problem settings and present several heuristic procedures as well as one exact algorithm. The paper concludes with computational results showing the efficiency of the proposed algorithms.


90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] Alicke, K. (2002). Modeling and optimization of the intermodal terminal mega hub. OR Spectrum, 24, 1–17. · Zbl 0993.90012
[2] Alicke, K., & Arnold, D. (1998). Modellierung und Optimierung von mehrstufigen Umschlagsystemen. Fördern und Heben, 8, 769–772.
[3] Ballis, A., & Golias, J. (2002). Comparative evaluation of existing and innovative rail–road freight transport terminals. Transportation Research Part A: Policy and Practice, 36, 593–611. · doi:10.1016/S0965-8564(01)00024-6
[4] Blasum, U., Bussieck, M., Hochstättler, W., Moll, C., Scheel, H.-H., & Winter, T. (1999). Scheduling trams in the morning. Mathematical Methods of Operations Research, 49, 137–148. · Zbl 0947.90044
[5] Bontekoning, Y., Macharis, C., & Trip, J. (2004). Is a new applied transportation research field emerging? A review of intermodal rail-truck freight transport literature. Transportation Research Part A: Policy and Practice, 38, 1–24. · doi:10.1016/j.tra.2003.06.001
[6] Bostel, N., & Dejax, P. (1998). Models and algorithms for container allocation problems on trains in a rapid transshipment shunting yard. Transportation Science, 32, 370–379. · Zbl 0987.90505 · doi:10.1287/trsc.32.4.370
[7] Boysen, N., & Fliedner, M. (2010). Determining crane areas in intermodal transshipment yards: The yard partition problem. European Journal of Operational Research, 204, 336–342. · Zbl 1178.90142 · doi:10.1016/j.ejor.2009.10.031
[8] Boysen, N., Jaehn, F., & Pesch, E. (2010a). Scheduling freight trains in rail–rail transshipment yards, Transportation Science, to apppear
[9] Boysen, N., Fliedner, M., & Kellner, M. (2010b). Determining fixed crane areas in rail–rail transshipment yards. Transportation Research Part E, 46, 1005–1016. · doi:10.1016/j.tre.2010.05.004
[10] Cordeau, J.-F., Toth, P., & Vigo, D. (1998). A survey of optimization models for train routing and scheduling. Transportation Science, 32, 380–404. · Zbl 0987.90507 · doi:10.1287/trsc.32.4.380
[11] Corry, P., & Kozan, E. (2008). Optimised loading patterns for intermodal trains. OR Spectrum, 30, 721–750. · Zbl 1193.90038 · doi:10.1007/s00291-007-0112-5
[12] Crainic, T., & Kim, K. (2007). Intermodal transport. In C. Barnhart & G. Laporte (Eds.), Transportation: Vol. 14. Handbooks in operations research and management science (pp. 467–538). Amsterdam: North-Holland.
[13] Dahlhaus, E., Horak, P., Miller, M., & Ryan, J. (2000). Optimised loading patterns for intermodal trains. Discrete Applied Mathematics, 103, 41–54. · Zbl 0962.90009 · doi:10.1016/S0166-218X(99)00219-X
[14] EU (2007). Mitteilung der Kommission an den Rat und das europäische Parlament: Aufbau eines vorrangig für den Güterverkehr bestimmten Schienennetzes.
[15] Feo, T., Goldschmidt, O., & Khellaf, M. (1992). One-half approximation algorithms for the k-partition problem. Operations Research, 40, 170–173. · Zbl 0745.90072 · doi:10.1287/opre.40.1.S170
[16] Freling, R., Lentink, R., Kroon, L., & Huisman, D. (2005). Shunting of passenger train units in a railway station. Transportation Science, 39, 261–272. · doi:10.1287/trsc.1030.0076
[17] Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039
[18] He, S., Song, R., & Chaudhry, S. (2000). Fuzzy dispatching model and genetic algorithms for railyards operations. European Journal of Operational Research, 124, 307–331. · Zbl 1025.90520 · doi:10.1016/S0377-2217(99)00383-5
[19] Kellner, M., Boysen, N., & Fliedner, M. (2010). How to park freight trains on rail–rail transshipment yards: The train location problem, submitted. · Zbl 1244.90143
[20] Lim, A., Rodrigues, B., & Xu, Z. (2007). A m-parallel crane scheduling problem with a non-crossing constraint. Naval Research Logistics, 54, 115–127. · Zbl 1126.90025 · doi:10.1002/nav.20189
[21] Macharis, C., & Bontekoning, Y. (2004). Opportunities for or in intermodal freight transport research: A review. European Journal of Operational Research, 153, 400–416. · Zbl 1053.90008 · doi:10.1016/S0377-2217(03)00161-9
[22] Meyer, P. (1999). Entwicklung eines Simulationsprogramms für Umschlagterminals des Kombinierten Verkehrs. Aachen: Shaker Verlag.
[23] Moccia, L., Cordeau, J., Gaudioso, M., & Laporte, G. (2006). A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal. Naval Research Logistics, 53, 45–59. · Zbl 1112.90033 · doi:10.1002/nav.20121
[24] Papadimitriou, C., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and Complexity. Prentice-Hall: Englewood Cliffs. · Zbl 0503.90060
[25] Pesch, E., & Glover, F. (1997). TSP ejection chains. Discrete Applied Mathematics, 76, 165–181. · Zbl 0883.90120 · doi:10.1016/S0166-218X(96)00123-0
[26] Rotter, H. (2004). New operating concepts for intermodal transport: The mega hub in Hanover/Lehrte in Germany. Transportation Planning and Technology, 27, 347–365. · doi:10.1080/0308106042000273022
[27] Sammarra, M., Cordeau, J., Laporte, G., & Monaco, M. (2007). A tabu search heuristic for the quay crane scheduling problem. Journal of Scheduling, 10, 327–336. · Zbl 1168.90468 · doi:10.1007/s10951-007-0029-5
[28] Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1994). Scheduling theory. Single-stage systems. Kluwer: Dordrecht. · Zbl 0827.90079
[29] Wiegmans, B., Stekelenburg, D., Versteegt, C., & Bontekoning, Y. (2007). Modeling rail–rail exchange operations: An analysis of conventional and new-generation terminals. Transportation Journal, 46, 5–20.
[30] Winter, T., & Zimmermann, U. (2000). Real-time dispatch of trams in storage yards. Annals of Operations Research, 96, 287–315. · Zbl 0966.90006 · doi:10.1023/A:1018907720194
[31] Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraints. Journal of Operational Research Society, 57, 1464–1471. · Zbl 1123.90042 · doi:10.1057/palgrave.jors.2602110
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.