×

Simulation-based optimization for discharge/loading operations at a maritime container terminal. (English) Zbl 1200.90022

Summary: The discharge/loading process of a single container ship by multiple quay cranes and shuttle vehicles moving back and forth from the quay to the yard and vice versa is focused in this paper. The core problem of this major operational issue reduces to finding the optimal assignment and optimal sequencing (schedule) of bays (jobs) processed by a fixed number of available cranes (machines). Under the classical assumption that machines have no release time and that their processing occurs with continuity, at a constant rate, in literature it has been tackled as a deterministic machine scheduling problem and formulated by integer programming as the quay crane scheduling problem (QCSP). Here, instead, the QCSP is viewed as a decisional step within an uncertain and dynamic logistic process where the quay cranes are the resources to be managed at the best, i.e., by minimizing the time spent waiting for each other due to conflicts, as well as the time wasted for blocking and starvation phenomena due to congestion occurring along the path from the quay area and to the stacking yard and vice versa. We present a simulation-based optimization (SO) model for this wider modeling problem with the objective of finding the schedule which optimizes a classical objective function. The search process for the optimal schedule is accomplished by a simulated annealing (SA) algorithm, while performance estimation of the overall container discharge/loading process is provided by the simulation framework as a whole. Numerical experiments on a real instance are presented for tuning purposes of the SA procedure implemented within the simulator.

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI

References:

[1] Ahmed MA, Alkhamis TM (2002) Simulation-based optimization using simulated annealing with ranking and selection. Comput Oper Res 29: 387–402 · Zbl 0994.90102 · doi:10.1016/S0305-0548(00)00073-3
[2] Ahmed MA, Alkhamis TM (2004) Simulation-based optimization using simulated annealing with confidence interval. In: Ingalls RG, Rossetti MD, Smith JS, Peters BA (eds) Proceedings of the 2004 winter simulation conference, pp 514–519
[3] Alrefaei MH, Andradóttir S (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Manag Sci 45(5): 748–764 · Zbl 1231.90315 · doi:10.1287/mnsc.45.5.748
[4] Banks J, Carson JS, Nelson BL, Nicol DM (2001) Discrete-event system simulation, 3rd edn. Prentice-Hall, Upper Saddle River
[5] Canonaco P, Legato P, Mazza RM (2007) An integrated simulation model for channel contention and berth management at a maritime container terminal. In: Zelinka I, Oplatková Z, Orsoni A (eds) Proceedings 21st European conference on modelling and simulation, pp 353–362
[6] Canonaco P, Legato P, Mazza RM, Musmanno R (2008) A queuing network model for the management of berth crane operations. Comput Oper Res 35: 2432–2446 · Zbl 1179.90074
[7] Chan WK, Schruben LW (2004) Generating scheduling constraints for discrete event dynamics systems. In: Ingalls RG, Rossetti MD, Smith JS, Peters BA (eds) Proceedings of the 2004 winter simulation conference, pp 568–576
[8] Chen HC, Chen CH, Dai L, Yücesan E (1997) New development of optimal computing budget allocation for discrete event simulation. In: Andradóttir S, Healy KJ, Withers DH, Nelson BL (eds) Proceedings of the 1997 winter simulation conference, pp 334–341
[9] Fu M, Nelson B (2003) Guest editorial. ACM Trans Model Comput Simul 13(2): 105–107 · doi:10.1145/858481.858482
[10] Goldsman DM, Kim S-H, Marshall WS, Nelson BL (2002) Ranking and selection for steady-state simulation: procedures and perspectives. INFORMS J Comput 14(1): 2–19 · Zbl 1238.65139 · doi:10.1287/ijoc.14.1.2.7710
[11] Hong LJ, Nelson BL (2007) Selecting the best system when systems are revealed sequentially. IIE Trans 39: 723–734 · doi:10.1080/07408170600838415
[12] Ingber L (1993) Simulated annealing: practice versus theory. Math Comput Model 18(11): 29–57 · Zbl 0819.90080 · doi:10.1016/0895-7177(93)90204-C
[13] Kim KH, Günther H-O (2007) Container terminal and terminal operations. In: Container terminals and cargo systems. Springer, Berlin, pp 3–12
[14] Kim KH, Moon KC (2003) Berth scheduling by simulated annealing. Transp Res B 37: 541–560 · doi:10.1016/S0191-2615(02)00027-9
[15] Kim KH, Park Y-M (2004) A crane scheduling method for port container terminals. Eur J Oper Res 156: 752–768 · Zbl 1062.90027 · doi:10.1016/S0377-2217(03)00133-4
[16] Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 221: 671–680 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[17] Lee LH, Chew EP, Manikam P (2006) A general framework on the simulation-based optimization under fixed computing budget. Eur J Oper Res 174(3): 1828–1841 · Zbl 1102.90366 · doi:10.1016/j.ejor.2005.02.052
[18] Lee D-H, Wang HQ, Miao L (2008) Quay crane scheduling with non-interference constraints in port container terminals. Transp Res E 44(1): 124–135 · doi:10.1016/j.tre.2006.08.001
[19] Legato P, Mazza RM, Trunfio R (2008a) Simulation-based optimization for the quay crane scheduling problem. In: Mason SJ, Hill R, Moench L, Rose O (eds) Proceedings of the 2008 winter simulation conference, pp 2717–2725
[20] Legato P, Gullì D, Trunfio R (2008b) Modeling, simulation and optimization of logistics processes. In: Bruzzone AG, Longo F, Piera MA, Aguilar RM, Frydman C (eds) Proceedings of 20th European modeling and simulation symposium (Simulation in Industry), pp 569–578
[21] Liang C, Mi W (2007) A quay crane scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Comput Ind Eng 56(3): 1021–1028 · doi:10.1016/j.cie.2008.09.024
[22] Lim A, Rodrigues B, Xiao F, Zhu Y (2004) Crane scheduling with spatial constraints. Naval Res Logist 51: 386–406 · Zbl 1054.90036 · doi:10.1002/nav.10123
[23] Liu CL (1968) Introduction to combinatorial mathematics. McGraw-Hill, New York · Zbl 0188.03801
[24] Liu J, Wan Y-W, Wang L (2006) Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures. Naval Res Logist 53: 60–74 · Zbl 1112.90031 · doi:10.1002/nav.20108
[25] Mazza RM (2008) Simulation-based optimization in port logistics. Ph.D. Dissertation, Università della Calabria
[26] Ng WC, Mak KL (2006) Quay crane scheduling in container terminals. Eng Optim 38: 723–737 · doi:10.1080/03052150600691038
[27] Pidd M, Castro RB (1998) Hierarchical modular modelling in discrete simulation. In: Medeiros DJ, Watson EF, Carson JS, Manivannan MS (eds) Proceedings of the 30th conference on winter simulation, pp 383–389
[28] Rinott Y (1978) On two-stage selection procedures and related probability-inequalities. Commun Stat Theory Methods A 7(8): 799–811 · Zbl 0392.62020 · doi:10.1080/03610927808827671
[29] Roenko N (1990) Simulated annealing under uncertainty. Technical report, Institute for Operations Research, University of Zurich
[30] Sammarra M, Cordeau J-F, Laporte H, Monaco MF (2007) A tabu search heuristic for the quay crane scheduling problem. J Sched 10: 327–336 · Zbl 1168.90468 · doi:10.1007/s10951-007-0029-5
[31] Schruben LW (1983) Simulation modelling with event graphs. Commun ACM 26(11): 957–963 · doi:10.1145/182.358460
[32] Stahlbock R, Voß S (2008) Operations research at container terminals: a literature update. OR Spectrum 30(1): 1–52 · Zbl 1133.90313 · doi:10.1007/s00291-007-0100-9
[33] 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
[34] Trunfio R (2008) Modeling, simulation and optimization in logistics. Ph.D. dissertation, Università della Calabria
[35] Zhu Y, Lim A (2006) Crane scheduling with non-crossing constraint. J Oper Res Soc 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.