Mathematical models and solution methods for optimal container terminal yard layouts. (English) Zbl 1200.90025

Summary: In this paper, we introduce an integer linear program for planning the layout of container yards. We concentrate on a special layout class of container yards which we call yard layout with transfer lanes. For those layouts typically rubber tired gantry cranes are used for stacking operations and trucks for horizontal transports. We show that the optimization model can be formulated as a special type of a resource constrained shortest path problem for which the LP relaxation always has at least one integer optimal solution. This model is restricted to a rectangular storage yard which allows a linear formulation. For an arbitrary shaped container yard we adopt the model and develop a variable neighborhood descent (VND) heuristic for solving non-rectangular instances. Concerning the rectangular case, we show that the VND heuristic achieves optimal solutions for 38% of the realistic test instances.


90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C59 Approximation methods and heuristics in mathematical programming


Full Text: DOI


[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs
[2] Beasley JE, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19: 379–394 · Zbl 0673.90085 · doi:10.1002/net.3230190402
[3] Dekker R, Voogd P, van Asperen E (2006) Advanced methods for container stacking. OR Spectr 28(4): 563–586 · Zbl 1098.90505 · doi:10.1007/s00291-006-0038-3
[4] Drira A, Pierreval H, Hajri-Gabouj S (2007) Facility layout problems: A survey. Annu Rev Control 31(2): 255–267
[5] Duinkerken M, Dekker R, Kurstjens S, Ottjes J, Dellaert N (2006) Comparing transportation systems for inter-terminal transport at the maasvlakte container terminals. OR Spectr 28(4): 469–493 · Zbl 1098.90506 · doi:10.1007/s00291-006-0056-1
[6] Handler GY, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10(4): 293–309 · Zbl 0453.68033 · doi:10.1002/net.3230100403
[7] Hansen P, Mladenovic N (2001) Variable neighborhood search: Principles and applications. Eur J Oper Res 130(3): 449–467 · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[8] Imai A, Sasaki K, Nishimura E, Papadimitriou S (2006) Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks. Eur J Oper Res 171(2): 373–389 · Zbl 1090.90009 · doi:10.1016/j.ejor.2004.07.066
[9] Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Column generation. Springer, Berlin, pp 33–65 · Zbl 1130.90315
[10] Kim KH (1997) Evaluation of the number of rehandles in container yards. Comput Ind Eng 32(4): 701–711 · doi:10.1016/S0360-8352(97)00010-7
[11] Kim KH, Kim HB (1999) Segregating space allocation models for container inventories in port container terminals. Int J Prod Econ 59: 415–423 · doi:10.1016/S0925-5273(98)00028-0
[12] Kim KH, Park Y-M, Jin M-J (2008) An optimal layout of container yards. OR Spectr 30(4): 675–695 · Zbl 1193.90145 · doi:10.1007/s00291-007-0111-6
[13] Liu C, Jula H, Vukadinovic K, and Ioannou P (2000) Comparing different technologies for containers movement in marine container terminals. In: IEEE intelligent transportation systems conference proceedings
[14] Liu C-I, Jula H, Ioannou P (2002) Design, simulation, and evaluation of automated container terminals. IEEE Trans Intell Trans Syst 3: 12–26 · doi:10.1109/6979.994792
[15] Liu C-I, Jula H, Vukadinovic K, Ioannou P (2004) Automated guided vehicle system for two container yard layouts. Transpo Res C 12: 349–368 · doi:10.1016/j.trc.2004.07.014
[16] Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11): 1097–1100 · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[17] MOPS (2009) Mops–mathematical optimization system: About mops. MOPS Optimierungssysteme GmbH and Co. KG. http://www.mops-optimizer.com . Accessed 08 Mar 2009
[18] Petering MEH (2009) Effect of block width and storage yard layout on marine container terminal performance. Transp Res E Logist Transp Rev 45: 591–610 · doi:10.1016/j.tre.2008.11.004
[19] Petering MEH, Murty KG (2009) Effect of block length and yard crane deployment systems on overall performance at a seaport container transshipment terminal. Comput Oper Res 36(5): 1711–1725 · Zbl 1177.90274 · doi:10.1016/j.cor.2008.04.007
[20] Saanen YA, Valkengoed MV (2005) Comparison of three automated stacking alternatives by means of simulation. In: WSC ’05: Proceedings of the 37th conference on winter simulation, pp 1567–1576. Winter simulation conference
[21] Singh S, Sharma R (2006) A review of different approaches to the facility layout problems. Int J Adv Manuf Technol 30(5): 425–433 · doi:10.1007/s00170-005-0087-9
[22] Stahlbock R, Voß S (2008) Operations research at container terminals: a literature update. OR Spectr 30(1): 1–52 · Zbl 1133.90313 · doi:10.1007/s00291-007-0100-9
[23] Steenken D, Voß S, Stahlbock R (2004) Container terminal operation and operations research–a classification and literature review. OR Spectrum 26: 3–49 · Zbl 1160.90322 · doi:10.1007/s00291-003-0157-z
[24] Suhl UH (1994) Mops–mathematical optimization system. Eur J Oper Res 72(2): 312–322 · Zbl 0800.90690 · doi:10.1016/0377-2217(94)90312-3
[25] UNCTAD (2008) Review of Maritime Transport 2008. UNCTAD.
[26] Vis IFA (2006) A comparative analysis of storage and retrieval equipment at a container terminal. Int J Prod Econ 103(2): 680–693 · doi:10.1016/j.ijpe.2006.01.002
[27] Vis IFA, de Koster R (2003) Transshipment of containers at a container terminal: An overview. Eur J Oper Res 147(1): 1–16 · Zbl 1011.90005 · doi:10.1016/S0377-2217(02)00293-X
[28] Vis IFA, Harika I (2004) Comparison of vehicle types at an automated container terminal. OR Spectr 26(1): 117–143 · Zbl 1161.90315 · doi:10.1007/s00291-003-0146-2
[29] Wiese J, Kliewer N, Suhl L (2009) A survey of container terminal characteristics and equipment types. Technical Report 0901, DS&OR Lab, University of Paderborn. http://dsor.upb.de/uploads/tx_dsorpublications/DSOR_WP_0901.pdf
[30] Wiese J, Suhl L, Kliewer N (2010) Mathematical programming and simulation based layout planning of container terminals. Manuscript. Int J Simul Process Modell (to appear) · Zbl 1200.90025
[31] Yang C, Choi Y, Ha T (2004) Simulation-based performance evaluation of transport vehicles at automated container terminals. OR Spectr 26(2): 149–170 · Zbl 1069.90027 · doi:10.1007/s00291-003-0151-5
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.