×

A two-phase approach for single container loading with weakly heterogeneous boxes. (English) Zbl 1461.90118

Summary: We propose in this paper a two-phase approach that decomposes the process of solving the three-dimensional single Container Loading Problem (CLP) into subsequent tasks: (i) the generation of blocks of boxes and (ii) the loading of blocks into the container. The first phase is deterministic, and it is performed by means of constructive algorithms from the literature. The second phase is non-deterministic, and it is performed with the use of Generate-and-Solve (GS), a problem-independent hybrid optimization framework based on problem instance reduction that combines a metaheuristic with an exact solver. Computational experiments performed on benchmark instances indicate that our approach presents competitive results compared to those found by state-of-the-art algorithms, particularly for problem instances consisting of a few types of boxes. In fact, we present new best solutions for classical instances from groups BR1 and BR2.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
68W40 Analysis of algorithms

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wäscher, G.; Haußner, H.; Schumann, H.; An improved typology of cutting and packing problems; Eur. J. Oper. Res.: 2007; Volume 183 ,1109-1130. · Zbl 1278.90347
[2] Bortfeldt, A.; Wäscher, G.; Constraints in container loading—A state-of-the-art review; Eur. J. Oper. Res.: 2013; Volume 229 ,1-20. · Zbl 1317.90172
[3] Scheithauer, G.; Algorithms for the container loading problem; Operations Research Proceedings 1991: Berlin, Germany 1992; ,445-452.
[4] Fanslau, T.; Bortfeldt, A.; A tree search algorithm for solving the container loading problem; INFORMS J. Comput.: 2010; Volume 22 ,222-235. · Zbl 1243.90090
[5] George, J.A.; Robinson, D.F.; A heuristic for packing boxes into a container; Comput. Oper. Res.: 1980; Volume 7 ,147-156.
[6] Bischoff, E.E.; Ratcliff, M.; Issues in the development of approaches to container loading; Omega: 1995; Volume 23 ,377-390.
[7] Zhu, W.; Lim, A.; A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem; Eur. J. Oper. Res.: 2012; Volume 222 ,408-417. · Zbl 1253.90015
[8] Araya, I.; Riff, M.C.; A beam search approach to the container loading problem; Comput. Oper. Res.: 2014; Volume 43 ,100-107. · Zbl 1348.90532
[9] Parreño, F.; Alvarez-Valdés, R.; Oliveira, J.; Tamarit, J.M.; Neighborhood structures for the container loading problem: A VNS implementation; J. Heuristics: 2010; Volume 16 ,1-22. · Zbl 1184.90174
[10] Gonçalves, J.F.; Resende, M.G.; A parallel multi-population biased random-key genetic algorithm for a container loading problem; Comput. Oper. Res.: 2012; Volume 39 ,179-190. · Zbl 1251.90238
[11] Gehring, H.; Bortfeldt, A.; A genetic algorithm for solving the container loading problem; Int. Trans. Oper. Res.: 1997; Volume 4 ,401-418. · Zbl 0906.90145
[12] Mack, D.; Bortfeldt, A.; Gehring, H.; A parallel hybrid local search algorithm for the container loading problem; Int. Trans. Oper. Res.: 2004; Volume 11 ,511-533. · Zbl 1131.90464
[13] Moura, A.; Oliveira, J.F.; A GRASP approach to the container-loading problem; IEEE Intell. Syst.: 2005; Volume 20 ,50-57.
[14] Liu, J.; Yue, Y.; Dong, Z.; Maple, C.; Keech, M.; A novel hybrid tabu search approach to container loading; Comput. Oper. Res.: 2011; Volume 38 ,797-807. · Zbl 1202.90033
[15] Dereli, T.; Das, G.S.; A hybrid ‘bee(s) algorithm’ for solving container loading problems; Appl. Soft Comput.: 2011; Volume 11 ,2854-2862.
[16] Morabito, R.; Arenales, M.; An AND/OR-graph approach to the container loading problem; Int. Trans. Oper. Res.: 1994; Volume 1 ,59-73. · Zbl 0854.90121
[17] Eley, M.; Solving container loading problems by block arrangement; Eur. J. Oper. Res.: 2002; Volume 141 ,393-409. · Zbl 1081.90610
[18] Pisinger, D.; Heuristics for the container loading problem; Eur. J. Oper. Res.: 2002; Volume 141 ,382-392. · Zbl 1081.90613
[19] He, K.; Huang, W.; An efficient placement heuristic for three-dimensional rectangular packing; Comput. Oper. Res.: 2011; Volume 38 ,227-233. · Zbl 1231.90322
[20] Raidl, G.R.; Decomposition based hybrid metaheuristics; Eur. J. Oper. Res.: 2015; Volume 244 ,66-76. · Zbl 1346.90827
[21] Blum, C.; Raidl, G.R.; ; Hybrid Metaheuristics: Powerful Tools for Optimization: Berlin, Germany 2016; .
[22] Boschetti, M.; Maniezzo, V.; Roffilli, M.; Bolufé Röhler, A.; Matheuristics: Optimization, Simulation and Control; Hybrid Metaheuristics: Berlin, Germany 2009; Volume Volume 5818 ,171-177.
[23] Haessler, R.W.; Brian Talbot, F.; Load planning for shipments of low density products; Eur. J. Oper. Res.: 1990; Volume 44 ,289-299. · Zbl 0684.90085
[24] Nepomuceno, N.; Pinheiro, P.; Coelho, A.L.; Tackling the Container Loading Problem: A Hybrid Approach Based on Integer Linear Programming and Genetic Algorithms; Evolutionary Computation in Combinatorial Optimization: Berlin, Germany 2007; Volume Voume 4446 ,154-165.
[25] Nepomuceno, N.; Pinheiro, P.; Coelho, A.L.; A Hybrid Optimization Framework for Cutting and Packing Problems; Recent Advances in Evolutionary Computation for Combinatorial Optimization: Berlin, Germany 2008; Volume Volume 153 ,87-99. · Zbl 1159.90477
[26] Saraiva, R.; Nepomuceno, N.; Pinheiro, P.; The Generate-and-Solve Framework Revisited: Generating by Simulated Annealing; Evolutionary Computation in Combinatorial Optimization: Berlin, Germany 2013; Volume Volume 7832 ,262-273.
[27] Wang, N.; Lim, A.; Zhu, W.; A multi-round partial beam search approach for the single container loading problem with shipment priority; Int. J. Prod. Econ.: 2013; Volume 145 ,531-540.
[28] Beasley, J.; An exact two-dimensional non-guillotine cutting tree search procedure; Oper. Res.: 1985; Volume 33 ,49-64. · Zbl 0569.90038
[29] Blum, C.; Raidl, G.R.; Hybridization Based on Problem Instance Reduction; Hybrid Metaheuristics: Powerful Tools for Optimization: Cham, Switzerland 2016; ,45-62.
[30] Pinheiro, P.R.; Coelho, A.L.V.; de Aguiar, A.B.; Bonates, T.O.; On the concept of density control and its application to a hybrid optimization framework: Investigation into cutting problems; Comput. Ind. Eng.: 2011; Volume 61 ,463-472.
[31] Blum, C.; Pinacho, P.; López-Ibáñez, M.; Lozano, J.A.; Construct, Merge, Solve & Adapt: A new general algorithm for combinatorial optimization; Comput. Oper. Res.: 2016; Volume 68 ,75-88. · Zbl 1349.90705
[32] Pacino, D.; Ropke, S.; Larsen, A.; Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results; Transp. Res. Part E Logist. Transp. Rev.: 2015; Volume 81 ,75-97.
[33] Bean, J.C.; Genetic algorithms and random keys for sequencing and optimization; ORSA J. Comput.: 1994; Volume 6 ,154-160. · Zbl 0807.90060
[34] Spears, W.M.; De Jong, K.A.; On the virtues of parameterized uniform crossover; Proceedings of the Fourth International Conference on Genetic Algorithms: ; ,230-236.
[35] Beasley, J.E.; OR-Library: Distributing test problems by electronic mail; J. Oper. Res. Soc.: 1990; ,1069-1072.
[36] Araya, I.; Guerrero, K.; Nuñez, E.; VCS: A new heuristic function for selecting boxes in the single container loading problem; Comput. Oper. Res.: 2017; Volume 82 ,27-35. · Zbl 1391.90040
[37] Liu, S.; Tan, W.; Xu, Z.; Liu, X.; A tree search algorithm for the container loading problem; Comput. Ind. Eng.: 2014; Volume 75 ,20-30.
[38] Tian, T.; Zhu, W.; Lim, A.; Wei, L.; The multiple container loading problem with preference; Eur. J. Oper. Res.: 2016; Volume 248 ,84-94. · Zbl 1346.90523
[39] Çağatay, I.; Christensen, J.; Pacino, D.; Ropke, S.; Flexible ship loading problem with transfer vehicle assignment and scheduling; Transp. Res. Part B Methodol.: 2018; Volume 111 ,113-134.
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.