×

MIP-based approaches for the container loading problem with multi-drop constraints. (English) Zbl 1251.90324

Summary: We present approaches based on a mixed integer linear programming model (MIP) for the problem of packing rectangular boxes into a container or truck, considering multi-drop constraints. We assume that the delivery route of the container is already known in advance and that the volume of the cargo is less than or equal to the container volume. Considering the sequence that the boxes should be unloaded, the aim is to avoid additional handling when each drop-off point of the route is reached, as well as ensuring that the boxes do not overlap each other and the cargo loading is stable. Computational tests with the proposed model and the approaches were performed with randomly generated instances and instances from the literature using an optimization solver embedded into a modeling language. The results validate the model and the approaches, but indicate that they are able to handle only problems of a moderate size. However, the model and the approaches can be useful to motivate future research to solve larger problems, as well as to solve more general problems considering integrated vehicle routing and container loading problems.

MSC:

90C27 Combinatorial optimization
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beasley, J. E. (1985). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33(1), 49–64. · Zbl 0569.90038 · doi:10.1287/opre.33.1.49
[2] Bischoff, E. E., & Marriott, M. D. (1990). A comparative evaluation of heuristics for container loading. European Journal of Operational Research, 44(2), 267–276. · Zbl 0684.90083 · doi:10.1016/0377-2217(90)90362-F
[3] Bischoff, E. E., & Ratcliff, M. S. W. (1995). Issues in the development of approaches to container loading. Omega, 23(4), 377–390. · doi:10.1016/0305-0483(95)00015-G
[4] Christensen, S. G., & Rousøe, D. M. (2009). Container loading with multi-drop constraints. International Transactions in Operational Research, 16(6), 727–743. · Zbl 1179.90278 · doi:10.1111/j.1475-3995.2009.00714.x
[5] Christofides, N., & Whitlock, C. (1977). An algorithm for two-dimensional cutting problems. Operations Research, 25(1), 30–44. · Zbl 0369.90059 · doi:10.1287/opre.25.1.30
[6] Dowsland, W. B. (1991). Three-dimensional packing–solution approaches and heuristic development. International Journal of Production Research, 29(8), 1673–1685. · doi:10.1080/00207549108948039
[7] Eley, M. (2002). Solving container loading problems by block arrangement. European Journal of Operational Research, 141(2), 393–409. · Zbl 1081.90610 · doi:10.1016/S0377-2217(02)00133-9
[8] Fuellerer, G., Doerner, K. F., Hartl, R. F., & Iori, M. (2010). Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201(3), 751–759. · Zbl 1173.90511 · doi:10.1016/j.ejor.2009.03.046
[9] Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A tabu search algorithm for a routing and container loading problem. Transportation Science, 40(3), 342–350. · doi:10.1287/trsc.1050.0145
[10] George, J. A., & Robinson, D. F. (1980). A heuristic for packing boxes into a container. Computers and Operations Research, 7(3), 147–156. · doi:10.1016/0305-0548(80)90001-5
[11] Haessler, R. W., & Talbot, F. B. (1990). Load planning for shipments of low density products. European Journal of Operational Research, 44(2), 289–299. · Zbl 0684.90085 · doi:10.1016/0377-2217(90)90364-H
[12] Han, C. P., Knott, K., & Egbelu, P. J. (1989). A heuristic approach to the three-dimensional cargo-loading problem. International Journal of Production Research, 27(5), 757–774. · Zbl 0667.90075 · doi:10.1080/00207548908942585
[13] Iori, M., Gonzalez, J. S., & Vigo, D. (2007). An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation Science, 41(2), 253–264. · doi:10.1287/trsc.1060.0165
[14] Jin, Z., Ohno, K., & Du, J. (2004). An efficient approach for the three-dimensional container packing problem with practical constraints. Asia-Pacific Journal of Operational Research, 21(3), 279–295. · Zbl 1056.90118 · doi:10.1142/S0217595904000254
[15] Junqueira, L., Morabito, R., & Yamashita, D. S. (2012). Three-dimensional container loading models with cargo stability and load bearing constraints. Computers and Operations Research, 31(1), 74–85. · Zbl 1251.90240 · doi:10.1016/j.cor.2010.07.017
[16] Lai, K. K., Xue, J., & Xu, B. (1998). Container packing in a multi-customer delivering operation. Computers & Industrial Engineering, 35(1–2), 323–326. · doi:10.1016/S0360-8352(98)00085-0
[17] Lin, J. L., Chang, C. H., & Yang, J. Y. (2006). A study of optimal system for multiple-constraint multiple-container packing problems. In Proceedings of the 19th international conference on industrial, engineering and other applications of applied intelligent systems, Annecy (Vol. 4031, pp. 1200–1210).
[18] Lins, L., Lins, S., & Morabito, R. (2002). An n-tet graph approach for non-guillotine packing of n-dimensional boxes into an n-container. European Journal of Operational Research, 141(2), 421–439. · Zbl 1081.90592 · doi:10.1016/S0377-2217(02)00135-2
[19] Miyazawa, F. K., & Wakabayashi, Y. (1999). Approximation algorithms for the orthogonal Z-oriented three-dimensional packing problem. SIAM Journal on Computing, 29(3), 1008–1029. · Zbl 0941.68053 · doi:10.1137/S009753979631391X
[20] Morabito, R., & Arenales, M. (1994). An and/or-graph approach to the container loading problem. International Transactions in Operational Research, 1(1), 59–73. · Zbl 0854.90121 · doi:10.1016/0969-6016(94)90046-9
[21] Moura, A., & Bortfeldt, A. (2009). A packing and routing application for a Portuguese trading company. In Book of abstracts of the 6th ESICUP meeting, Valencia.
[22] Moura, A., & Oliveira, J. F. (2005). A GRASP approach to the container-loading problem. IEEE Intelligent Systems, 4(20), 50–57.
[23] Moura, A., & Oliveira, J. F. (2009). An integrated approach to the vehicle routing and container loading problems. OR-Spektrum, 31(4), 775–800. · Zbl 1175.90045 · doi:10.1007/s00291-008-0129-4
[24] Parreño, F., Alvarez-Valdes, R., Oliveira, J. F., & Tamarit, J. M. (2010). A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing. Annals of Operation Research, 179(1), 203–220. · Zbl 1201.90176 · doi:10.1007/s10479-008-0449-4
[25] Scheithauer, G., Terno, J., Riehme, J., & Sommerweiss, U. (1996). A new heuristic approach for solving the multi-pallet packing problem. Technical report, MATH-NM-03-1996. Technische Universität Dresden, Dresden.
[26] Silva, J. L. C., Soma, N. Y., & Maculan, N. (2003). A greedy search for the three-dimensional bin packing problem: the packing static stability case. International Transactions in Operational Research, 10(2), 141–153. · Zbl 1134.90480 · doi:10.1111/1475-3995.00400
[27] Tarantilis, C. D., Zachariadis, E. E., & Kiranoudis, C. T. (2009). A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems, 10(2), 255–271. · doi:10.1109/TITS.2009.2020187
[28] Terno, J., Scheithauer, G., Sommerweiss, U., & Riehme, J. (2000). An efficient approach for the multi-pallet loading problem. European Journal of Operational Research, 123(2), 372–381. · Zbl 0967.90040 · doi:10.1016/S0377-2217(99)00263-5
[29] Tetris (2009). 25th anniversary. Available at: http://www.tetris.com . Accessed in: 14 out 2009.
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.