A biased random-key genetic algorithm for the container pre-marshalling problem. (English) Zbl 1349.90563
Summary: The container pre-marshalling problem (CPMP) is performed at container terminals around the world to re-order containers so that they can be more efficiently transferred through the terminal. We introduce a novel decoder for a biased random-key genetic algorithm (BRKGA) that solves the CPMP. The decoder consists of a construction algorithm that learns how to best apply single and compound containers moves to quickly sort a bay of containers. Our approach finds better solutions than the state-of-the-art method on many instances of the standard pre-marshalling benchmarks in less computational time. Furthermore, we perform a computational analysis of different components of the BRKGA decoder to determine what types of heuristics work best for pre-marshalling problems, as well as conduct a feature space analysis of different pre-marshalling approaches.
MSC:
| 90B80 | Discrete location and assignment |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [2] | Bean, J., Genetic algorithms and random keys for sequencing and optimization, ORSA J Comput, 6, May (2), 154-160 (1994) · Zbl 0807.90060 |
| [3] | Bischl, B.; Kerschke, P.; Kotthoff, L.; Lindauer, M.; Malitsky, Y.; Fréchette, A., ASliba benchmark library for algorithm selection, Artif Intell, 237, 41-58 (2016) · Zbl 1357.68202 |
| [4] | Bortfeldt, A.; Forster, F., A tree search procedure for the container pre-marshalling problem, Eur J Oper Res, 217, 3, 531-540 (2012) · Zbl 1244.90122 |
| [6] | Caserta, M.; Voß, S., A corridor method-based algorithm for the pre-marshalling problem, Lect Notes Comput Sci, 5484, 788-797 (2009) |
| [7] | Cordeau, J.; Legato, P.; Mazza, R.; Trunfio, R., Simulation-based optimization for housekeeping in a container transshipment terminal, Comput Oper Res, 53, 81-95 (2015) · Zbl 1348.90077 |
| [9] | Duin, C.; Voß, S., The pilot methoda strategy for heuristic repetition with application to the Steiner problem in graphs, Networks, 34, 3, 181-191 (1999) · Zbl 0980.90094 |
| [10] | Expósito-Izquierdo, C.; Melián-Batista, B.; Moreno-Vega, J., A domain-specific knowledge-based heuristic for the blocks relocation problem, Adv Eng Inform, 28, 4, 327-343 (2014) |
| [11] | Expósito-Izquierdo, C.; Melián-Batista, B.; Moreno-Vega, M., Pre-marshalling problemheuristic solution method and instances generator, Expert Syst Appl, 39, 9, 8337-8349 (2012) |
| [12] | Felsner, S.; Pergel, M., The complexity of sorting with networks of stacks and queues, Lect Notes Comput Sci, 5193, 417-429 (2008) · Zbl 1158.68368 |
| [15] | Gonçalves, J.; Resende, M., Biased random-key genetic algorithms for combinatorial optimization, J Heuristics, 17, 5, 487-525 (2011) |
| [16] | Gonçalves, J.; Resende, M., A parallel multi-population biased random-key genetic algorithm for a container loading problem, Comput Oper Res, 39, 2, 179-190 (2012) · Zbl 1251.90238 |
| [17] | Grunow, M.; Günther, H.-O.; Lehmann, M., Strategies for dispatching agvs at automated seaport container terminals, OR Spectr, 28, 4, 587-610 (2006) · Zbl 1098.90507 |
| [18] | Gupta, N.; Nau, D., On the complexity of blocks-world planning, Artif Intell, 56, 2-3, 223-254 (1992) · Zbl 0785.68046 |
| [19] | Heaver, T.; Meersman, H.; Van De Voorde, E., Co-operation and competition in international container transportstrategies for ports, Marit Policy Manag, 28, 3, 293-305 (2001) |
| [20] | Huang, S.-H.; Lin, T.-H., Heuristic algorithms for container pre-marshalling problems, Comput Ind Eng, 62, 1, 13-20 (2012) |
| [21] | Jin, B.; Zhu, W.; Lim, A., Solving the container relocation problem by an improved greedy look-ahead heuristic, Eur J Oper Res, 240, 3, 837-847 (2015) · Zbl 1338.90052 |
| [23] | Kim, K.; Hong, G.-P., A heuristic rule for relocating blocks, Comput Oper Res, 33, 4, 940-954 (2006) · Zbl 1079.90079 |
| [24] | Lalla-Ruiz, E.; González-Velarde, J. L.; Melián-Batista, B.; Moreno-Vega, J., Biased random key genetic algorithm for the tactical berth allocation problem, Appl Soft Comput, 22, 60-76 (2014) |
| [25] | Lee, Y.; Chao, S.-L., A neighborhood search heuristic for pre-marshalling export containers, Eur J Oper Res, 196, 2, 468-475 (2009) |
| [26] | Lee, Y.; Hsu, N., An optimization model for the container pre-marshalling problem, Comput Oper Res, 34, 11, 3295-3313 (2007) · Zbl 1123.90010 |
| [27] | Lehnfeld, J.; Knust, S., Loading, unloading and premarshalling of stacks in storage areas: survey and classification, Eur J Oper Res, 239, 2, 297-312 (2014) · Zbl 1339.90006 |
| [29] | Mitchell, M., An introduction to genetic algorithms (1998), MIT Press: MIT Press Cambridge, Massachusetts · Zbl 0906.68113 |
| [30] | Notteboom, T., The time factor in liner shipping services, Marit Econ Logist, 8, March (1), 19-39 (2006) |
| [32] | Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O., Scikit-learnmachine learning in Python, J Mach Learn Res, 12, 2825-2830 (2011) · Zbl 1280.68189 |
| [33] | Psaraftis, H., Letter to the editor, Marit Econ Logist, 6, 195-196 (2004) |
| [35] | Rodrigue, J.; Comtois, C.; Slack, B., The Geography of Transport Systems (2009), Routledge: Routledge Milton Park |
| [36] | Ruiz, E.; Albareda-Sambola, M.; Fernández, E.; Resende, M., A biased random-key genetic algorithm for the capacitated minimum spanning tree problem, Comput Oper Res, 57, 95-108 (2015), URL 〈http://www.sciencedirect.com/science/article/pii/S0305054814003153〉 · Zbl 1348.90553 |
| [37] | Smith-Miles, K.; Baatar, D.; Wreford, B.; Lewis, R., Towards objective measures of algorithm performance across instance space, Comput Oper Res, 45, 12-24 (2014) · Zbl 1348.90646 |
| [39] | Stahlbock, R.; Voß, S., Operations research at container terminalsa literature update, OR Spectr, 30, 1, 1-52 (2008) · Zbl 1133.90313 |
| [40] | Steenken, D.; Voß, S.; Stahlbock, R., Container terminal operations and operations research - a classification and literature review, OR Spectr, 26, 1, 3-49 (2004) · Zbl 1160.90322 |
| [41] | Tang, L.; Zhao, R.; Liu, J., Models and algorithms for shuffling problems in steel plants, Nav Res Logist (NRL), 59, 7, 502-524 (2012) · Zbl 1407.90233 |
| [42] | Tierney, K., Optimizing liner shipping fleet repositioning plans (2015), Springer: Springer New York, NY · Zbl 1333.90005 |
| [44] | Tierney, K.; Pacino, D.; Jensen, R., On the complexity of container stowage planning problems, Discrete Appl Math, 169, 225-230 (2014) · Zbl 1297.90144 |
| [46] | Tierney, K.; Voß, S.; Stahlbock, R., A mathematical model of inter-terminal transportation, Eur J Oper Res, 235, 2, 448-460 (2014) · Zbl 1305.90076 |
| [50] | Vernimmen, B.; Dullaert, W.; Engelen, S., Schedule unreliability in liner shippingorigins and consequences for the hinterland supply chain, Marit Econ Logist, 9, 3, 193-213 (2007) |
| [51] | Wang, N.; Jin, B.; Lim, A., Target-guided algorithms for the container pre-marshalling problem, Omega, 53, 67-77 (2015) |
| [53] | Zhu, W.; Qin, H.; Lim, A.; Zhang, H., Iterative deepening \(A^⁎\) algorithms for the container relocation problem, IEEE Trans Autom Sci Eng, 9, 4, 710-722 (2012) |
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.
