A multi-heuristic approach for solving the pre-marshalling problem. (English) Zbl 1364.90372
Summary: Minimizing the number of reshuffling operations at maritime container terminals incorporates the pre-marshalling problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method. The improvement is twofold, both in the quality of found solutions, and in the computational effort.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C27 | Combinatorial optimization |
| 90B06 | Transportation, logistics and supply chain management |
References:
| [1] | Bortfeldt A, Forster F (2012) A tree search procedure for the container pre-marshalling problem. Eur J Oper Res 217(3):531-540 · Zbl 1244.90122 · doi:10.1016/j.ejor.2011.10.005 |
| [2] | Caserta M, Voß S (2009) A corridor method-based algorithm for the pre-marshalling problem. Lect Notes Comput Sci 5484:788-797 · doi:10.1007/978-3-642-01129-0_89 |
| [3] | Caserta, M.; Schwarze, S.; Voß, S.; Böse, J. (ed.), Container rehandling at maritime container terminals, No. 49, 247-269 (2011), New York |
| [4] | Caserta M, Voß S, Sniedovich M (2011b) Applying the corridor method to a blocks relocation problem. OR Spectrum 33:915-929 · Zbl 1229.90019 · doi:10.1007/s00291-009-0176-5 |
| [5] | Expósito-Izquierdo C, Melián-Batista B, Moreno-Vega M (2012) Pre-marshalling problem: heuristic solution method and instances generator. Expert Syst Appl 39(9):8337-8349 · doi:10.1016/j.eswa.2012.01.187 |
| [6] | Gupta N, Nau D (1992) On the complexity of blocks-world planning. Artif Intell 56(23):223-254 · Zbl 0785.68046 · doi:10.1016/0004-3702(92)90028-V |
| [7] | Huang SH, Lin TH (2012) Heuristic algorithms for container pre-marshalling problems. Comput Ind Eng 62(1):13-20 · doi:10.1016/j.cie.2011.08.010 |
| [8] | Jovanovic R, Voß S (2014) A chain heuristic for the blocks relocation problem. Comput Ind Eng 75(1):79-86 · doi:10.1016/j.cie.2014.06.010 |
| [9] | Kim K, Hong GP (2006) A heuristic rule for relocating blocks. Comput Oper Res 33(4):940-954 · Zbl 1079.90079 · doi:10.1016/j.cor.2004.08.005 |
| [10] | Kim KH (1997) Evaluation of the number of rehandles in container yards. Comput Ind Eng 32:701-711 · doi:10.1016/S0360-8352(97)00010-7 |
| [11] | Lee Y, Chao SL (2009) A neighborhood search heuristic for pre-marshalling export containers. Eur J Oper Res 196(2):468-475 · doi:10.1016/j.ejor.2008.03.011 |
| [12] | Lee Y, Lee YJ (2010) A heuristic for retrieving containers from a yard. Comput Oper Res 37(6):1139-1147 · Zbl 1178.90234 · doi:10.1016/j.cor.2009.10.005 |
| [13] | Lehnfeld J, Knust S (2014) Loading, unloading and premarshalling of stacks in storage areas: survey and classification. Eur J Oper Res 239(2):297-312 · Zbl 1339.90006 · doi:10.1016/j.ejor.2014.03.011 |
| [14] | Murty K, Wan YW, Liu J, Tseng M, Leung E, Lai KK, Chiu H (2005) Hongkong international terminals gains elastic capacity using a data-intensive decision support system. Interfaces 35(1):61-75 · doi:10.1287/inte.1040.0120 |
| [15] | Rendl A, Prandtstetter M (2013) Constraint models for the container pre-marshaling problem. In: Katsirelos G, Quimper CG (eds) ModRef 2013: 12th international workshop on constraint modelling and reformulation, pp 44-56 |
| [16] | Scholl A, Voß S (1996) Simple assembly line balancing—heuristic approaches. J Heuristics 2:217-244 · doi:10.1007/BF00127358 |
| [17] | Steenken D, Voß S, Stahlbock R (2004) Container terminal operations and operations research—a classification and literature review. OR Spectrum 26(1):3-49 · Zbl 1160.90322 · doi:10.1007/s00291-003-0157-z |
| [18] | Tierney K, Pacino D, Voß S (2013) Solving the pre-marshalling problem to optimality with A* and IDA*. Tech. Rep. Technical University of Denmark |
| [19] | Tran NK, Haasis H-D (2014) Empirical analysis of the container liner shipping network on the East-West corridor (1995-2011). Netnomics 15(3):121-153 · doi:10.1007/s11066-014-9088-x |
| [20] | Ünlüyurt T, Aydin C (2012) Improved rehandling strategies for the container retrieval process. J Adv Transp 46(4):378-393 · doi:10.1002/atr.1193 |
| [21] | Voß S (2012) Extended mis-overlay calculation for pre-marshalling containers. Lect Notes Comput Sci 7555:86-91 · doi:10.1007/978-3-642-33587-7_6 |
| [22] | Wu KC, Ting CJ (2010) A beam search algorithm for minimizing reshuffle operations at container yards. In: Proceedings of the 2010 international conference on logistics and maritime systems. Busan, Korea |
| [23] | Zhang C (2000) Resource planning in container storage yard. PhD thesis, Department of Industrial Engineering, The Hong Kong University of Science and Technology |
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.
