×

A heuristic algorithm for container loading of pallets with infill boxes. (English) Zbl 1346.90862

Summary: We consider the container loading problem that occurs at many furniture factories where product boxes are arranged on product pallets and the product pallets are arranged in a container for shipments. The volume of products in the container should be maximized, and the bottom of each pallet must be fully supported by the container floor or by the top of a single pallet to simplify the unloading process. To improve the filling rate of the container, the narrow spaces at the tops and sides of the pallets in the container should be filled with product boxes. However, it must be ensured that all of the infill product boxes can be entirely palletized into complete pallets after being shipped to the destination. To solve this problem, we propose a heuristic algorithm consisting of a tree search sub-algorithm and a greedy sub-algorithm. The tree search sub-algorithm is employed to arrange the pallets in the container. Then, the greedy sub-algorithm is applied to fill the narrow spaces with product boxes. The computational results on BR1-BR15 show that our algorithm is competitive.

MSC:

90C90 Applications of mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Araya, I.; Riff, M. C., A beam search approach to the container loading problem, Computers & Operations Research, 43, 4, 100-107 (2014) · Zbl 1348.90532
[2] Bischoff, E. E.; Ratcliff, M. S.W., Issues in the development of approaches to container loading, Omega, 23, 4, 377-390 (1995)
[3] Bischoff, E. E.; Janetz, F.; Ratcliff, M. S.W., Loading pallets with non-identical items, European Journal of Operational Research, 84, 3, 681-692 (1995) · Zbl 0928.90075
[4] Bischoff, E. E.; Marriott, M., Comparative evaluation of heuristics for container loading, European Journal of Operational Research, 44, 2, 267-276 (1990) · Zbl 0684.90083
[5] Bortfeldt, A.; Gehring, H., A tabu search algorithm for weakly heterogeneous container loading problems, OR Spectrum, 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.; Mack, D., A heuristic for the three dimensional strip packing problem, European Journal of Operational Research, 183, 3, 1267-1279 (2007) · Zbl 1136.90413
[9] 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] Dyckhoff, H.; Finke, U., Cutting and packing in production and distribution (1992), Physica-Verlag: Physica-Verlag Heidelberg
[11] Egeblad, J.; Garavelli, C.; Lisi, S.; Pisinger, D., Heuristics for container loading of furniture, European Journal of Operational Research, 200, 3, 881-892 (2010) · Zbl 1177.90339
[12] Eley, M., Solving container loading problems by block arrangement, European Journal of Operational Research, 141, 2, 393-409 (2002) · Zbl 1081.90610
[13] Fanslau, T.; Bortfeldt, A., A tree search algorithm for solving the container loading problem, INFORMS Journal on Computing, 22, 2, 222-235 (2010) · Zbl 1243.90090
[14] Faroe, O.; Pisinger, D.; Zachariasen, M., Guided local search for three-dimensional bin-packing problem, INFORMS Journal on Computing, 15, 3, 267-283 (2003) · Zbl 1238.90112
[15] 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
[16] Gehring, H.; Bortfeldt, A., A parallel genetic algorithm for solving the container loading problem, International Transactions in Operational Research, 9, 4, 497-511 (2002) · Zbl 1008.90001
[17] George, J. A., A method for solving container packing for a single size of box, Journal of the Operational Research Society, 43, 4, 307-312 (1992) · Zbl 0825.90719
[18] George, J. A.; Robinson, D. F., A heuristic for packing boxes into a container, Computers and Operations Research, 7, 3, 147-156 (1980)
[19] He, K.; Huang, W., An efficient placement heuristic for three-dimensional rectangular packing, Computers & Operations Research, 38, 1, 227-233 (2011) · Zbl 1231.90322
[20] Hemminki, J., Container loading with variable strategies in each layer, (Presented at ESI-X, July 2-15 (1994), EURO Summer Institute: EURO Summer Institute Jouy-En-Josas, France)
[21] Hifi, M., Approximate algorithms for the container loading problem, International Transactions in Operational Research, 9, 6, 747-774 (2002) · Zbl 1044.90060
[22] Huang, W.; He, K., A caving degree approach for the single container loading problem, European Journal of Operational Research, 196, 1, 93-101 (2009) · Zbl 1161.90013
[23] Junqueira, L.; Morabito, R.; Sato Yamashita, D., Three-dimensional container loading models with cargo stability and load bearing constraints, Computers & Operations Research, 39, 1, 74-85 (2012) · Zbl 1251.90240
[24] Lim, A.; Ma, H.; Qiu, C.; Zhu, W., The single container loading problem with axle weight constraints, International Journal of Production Economics, 144, 1, 358-369 (2013)
[25] Lim, A.; Rodrigues, B.; Wang, Y., A multi-faced buildup algorithm for three-dimensional packing problems, Omega, 31, 6, 471-481 (2003)
[26] Liu, S.; Tan, W.; Xu, Z.; Liu, X., A tree search algorithm for the container loading problem, Computers & Industrial Engineering, 11, 5, 20-30 (2014)
[27] Lu, Y.; Cha, J., A fast algorithm for identifying minimum size instances of the equivalence classes of the pallet loading problem, European Journal of Operational Research, 237, 3, 794-801 (2014) · Zbl 1338.90220
[28] Mack, D.; Bortfeldt, A.; Gehring, H., A parallel hybrid local search algorithm for the container loading problem, International Transactions in Operational Research, 11, 5, 511-533 (2004) · Zbl 1131.90464
[29] Morabito, R.; Arenales, M., Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach, European Journal of Operational Research, 94, 3,8, 548-560 (1996) · Zbl 0947.90537
[30] Morabito, R.; Arenales, M., An AND/OR-graph approach to the container loading problem, International Transactions in Operational Research, 1, 1, 59-73 (1994) · Zbl 0854.90121
[31] Moura, A.; Oliveira, J. F., A GRASP approach to the container-loading problem, IEEE Intelligent Systems, 20, 4, 50-57 (2005)
[32] Parreno, F.; Alvarez-Valdes, R.; Oliveira, J. F.; Tamarit, J. M., A maximal space algorithm for the container loading problem, INFORMS Journal on Computing, 20, 3, 412-422 (2007) · Zbl 1243.90094
[33] Parreno, F.; Alvarez-Valdes, R.; Oliveira, J. F.; Tamarit, J. M., Neighborhood structures for the container loading problem: AVNS implementation, Journal of Heuristics, 16, 1, 1-22 (2010) · Zbl 1184.90174
[34] Pisinger, D., Heuristics for the container loading problem, European Journal of Operational Research, 141, 2, 143-153 (2002) · Zbl 1081.90613
[35] 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
[36] Sixt, M., Dreidimensionale Packprobleme. Losungsverfahren basierend auf den Meta-Heuristiken Simulated Annealing und Tabu-Suche (1996), Europaischer Verlag der Wissenschaften: Europaischer Verlag der Wissenschaften Frankfurt am Main
[37] Terno, J.; Scheithauer, G.; Sommerweiß, U.; Rieme, J., An efficient approach for the multi-pallet loading problem, European Journal of Operational Research, 123, 2, 372-381 (2000) · Zbl 0967.90040
[38] Tian, T.; Zhu, W.; Lim, A.; Wei, L., The multiple container loading problem with preference, European Journal of Operational Research, 248, 1, 84-94 (2016) · Zbl 1346.90523
[39] Wang, N.; Lim, A.; Zhu, W., A multi-round partial beam search approach for the single container loading problem with shipment priority, International Journal of Production Economics, 145, 2, 531-540 (2013)
[40] 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
[41] Wei, L.; Zhu, W.; Lim, A., A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem, European Journal of Operational Research, 241, 1, 39-49 (2015) · Zbl 1338.90270
[42] Zhang, D.; Peng, Y.; Leung, S., A heuristic block-loading algorithm based on multi-layer search for the container loading problem, Computers & Operations Research, 39, 2267-2276 (2012)
[43] Zhu, W.; Lim, A., A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem, European Journal of Operational Research, 222, 3, 408-417 (2012) · Zbl 1253.90015
[44] Zhu, W.; Huang, W.; Lim, A., A prototype column generation strategy for the multiple container loading problem, European Journal of Operational Research, 223, 1, 27-39 (2012) · Zbl 1253.90014
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.