×

A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem. (English) Zbl 1394.90500

Summary: Efficient container loading has the potential to considerably reduce logistics and transportation costs. The container loading problem is computationally complex and, despite extensive academic effort, there remains room for algorithm improvement. Real-world problems are not always addressed satisfactorily primarily due to the large number of complex constraints and objectives. The problem addressed by this work is an unsolved multiple container loading problem introduced by Renault on the occasion of the 2014/2015 ESICUP challenge, organized by the EURO Special Interest Group on Cutting and Packing (ESICUP). Renault’s problem requires a large number of different items to be packed into containers of different types and sizes. Items must be grouped into stacks and respect the ‘this side up’ constraint. The primary objective is to minimize the volume of shipped containers. The smallest volume container may be left behind for the next shipment and is excluded from the main objective. Nevertheless, only a limited percentage of each product may be packed into this container. Additionally, a set of secondary objectives is considered. This work presents a decomposition approach embedded in a multi-phase heuristic for the problem. Feasible solutions are generated quickly, and subsequently improved by local search and post-processing procedures. Experiments revealed that the approach generates optimal solutions for two instances, in addition to good quality solutions for those remaining from the Renault set. The algorithmic contribution is, however, not restricted to the Renault instances. Experiments on less constrained container loading instances from the literature demonstrate the approach’s general applicability and competitiveness.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90B80 Discrete location and assignment
90B90 Case-oriented studies in operations research

Software:

Ts2pack; SCIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476
[2] Araya, I.; Riff, M. C., A beam search approach to the container loading problem, Computers and Operations Research, 43, 1, 100-107 (2014) · Zbl 1348.90532
[3] Bischoff, E.; Janetz, F.; Ratcliff, M., Loading pallets with non-identical items, European Journal of Operational Research, 84, 3, 681-692 (1995) · Zbl 0928.90075
[4] Bischoff, E.; Ratcliff, M., Issues in the development of approaches to container loading, Omega, 23, 4, 377-390 (1995)
[5] Bortfeldt, A.; Gehring, H., Ein tabu search-verfahren für containerbeladeprobleme mit schwach heterogenem kistenvorrat, Operations-Research-Spektrum, 20, 4, 237-250 (1998) · Zbl 0917.90116
[6] Bortfeldt, A.; Gehring, H., A hybrid genetic algorithm for the container loading problem, European Journal of Operational Research, 131, 1, 143-161 (2001) · Zbl 0979.90101
[7] Bortfeldt, A.; Gehring, H.; Mack, D., A parallel tabu search algorithm for solving the container loading problem, Parallel Computing, 29, 5, 641-662 (2003)
[8] Bortfeldt, A.; Wäscher, G., Constraints in container loading: a state-of-the-art review, European Journal of Operational Research, 229, 1, 1-20 (2013) · Zbl 1317.90172
[10] Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 4, 655-671 (2004) · Zbl 1165.90690
[11] Chazelle, B., The bottomn-left bin-packing heuristic: an efficient implementation, IEEE Transactions on Computers, 32, 8, 697-707 (1983) · Zbl 0526.68065
[12] Che, C. H.; Huang, W.; Lim, A.; Zhu, W., The multiple container loading cost minimization problem, European Journal of Operational Research, 214, 3, 501-511 (2011) · Zbl 1226.90085
[14] Crainic, T. G.; Perboli, G.; Tadei, R., Extreme point-based heuristics for three-dimensional bin packing, INFORMS Journal on Computing, 20, 3, 368-384 (2008) · Zbl 1243.90088
[15] Crainic, T. G.; Perboli, G.; Tadei, R., TS2PACK: a two-level tabu search for the three-dimensional bin packing problem, European Journal of Operational Research, 195, 3, 744-760 (2009) · Zbl 1161.90012
[16] Dereli, T.; Das, G. S., A hybrid bee(s) algorithm for solving container loading problems, Applied Soft Computing, 11, 1, 2854-2862 (2011)
[17] Eley, M., Solving container loading problems by block arrangement, European Journal of Operational Research, 141, 393-409 (2002) · Zbl 1081.90610
[18] Faroe, O.; Pisinger, D.; Zachariasen, M., Guided local search for the three-dimensional bin-packing problem, INFORMS Journal on Computing, 15, 3, 267-283 (2003) · Zbl 1238.90112
[19] Gehring, H.; Bortfeldt, A., A genetic algorithm for solving the container loading problem, International Transactions in Operational Research, 4, 5-6, 401-418 (1997) · Zbl 0906.90145
[20] He, K.; Huang, W., A caving degree based flake arrangement approach for the container loading problem, Computers & Industrial Engineering, 59, 2, 344-351 (2010)
[21] Imahori, S.; Yagiura, M., The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio, Computers and Operations Research, 37, 2, 325-333 (2010) · Zbl 1175.90429
[23] Lim, A.; Ma, H.; Xu, J.; Zhang, X., An iterated construction approach with dynamic prioritization for solving the container loading problems.(report), Expert Systems With Applications, 39, 4, 4292 (2012)
[24] Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: a survey, European Journal of Operational Research, 141, 241-252 (2002) · Zbl 1081.90576
[25] Lodi, A.; Martello, S.; Vigo, D., Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research, 141, 410-420 (2002) · Zbl 1081.90612
[26] Loh, T. H.; Nee, A. Y.C., A packing algorithm for hexahedral boxes, Proceedings of the conference of industrial automation, 115-126 (1992)
[27] Martello, S.; Pisinger, D.; Vigo, D., The three-dimensional bin packing problem, Operations Research, 48, 256-267 (2000) · Zbl 1106.90371
[28] Moura, A.; Oliveira, J. F., A grasp approach to the container-loading problem, IEEE Intelligent Systems, 20, 4, 50-57 (2005)
[29] Ngoi, B. K.A.; Tay, M. L.; Chua, E. S., Applying spatial representation techniques to the container packing problem, International Journal of Production Research, 32, 1, 111-123 (1994) · Zbl 0905.90145
[30] Parreño, F.; Alvarez-Valdes, R.; Tamarit, J. M.; Oliveira, J. F., A maximal-space algorithm for the container loading problem, INFORMS Journal on Computing, 20, 3, 412-422 (2008) · Zbl 1243.90094
[31] Ren, J.; Tian, Y.; Sawaragi, T., A priority-considering approach for the multiple container loading problem, International Journal of Metaheuristics, 1, 4, 298-316 (2011)
[32] Ren, J.; Tian, Y.; Sawaragi, T., A tree search method for the container loading problem with shipment priority, European Journal of Operational Research, 214, 3, 526-535 (2011) · Zbl 1219.90024
[33] Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347
[34] Zhao, X.; Bennell, J. A.; Bektaş, T.; Dowsland, K., A comparative review of 3d container loading algorithms, International Transactions in Operational Research, 23, 1-2, 287-320 (2016) · Zbl 1338.90360
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.