×

A reference length approach for the 3D strip packing problem. (English) Zbl 1253.90142

Summary: In the three-dimensional strip packing problem (3DSP), we are given a container with an open dimension and a set of rectangular cuboids (boxes) and the task is to orthogonally pack all the boxes into the container such that the magnitude of the open dimension is minimized. We propose a block building heuristic based on extreme points for this problem that uses a reference length to guide its solution. Our 3DSP approach employs this heuristic in a one-step lookahead tree search algorithm using an iterative construction strategy. We tested our approach on standard 3DSP benchmark test data; the results show that our approach produces better solutions on average than all other approaches in literature for the majority of these data sets using comparable computation time.

MSC:

90B80 Discrete location and assignment
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, S. D.; Burke, E. K.; Kendall, G., A hybrid placement strategy for the three-dimensional strip packing problem, European Journal of Operational Research, 209, 219-227 (2011) · Zbl 1205.90238
[2] Alvarez-Valdes, R.; Parreño, F.; Tamarit, J. M., Reactive GRASP for the strip-packing problem, Computers and Operations Research, 35, 1065-1083 (2008) · Zbl 1179.90269
[3] Aşık, O.; Özcan, E., Bidirectional best-fit heuristic for orthogonal rectangular strip packing, Annals of Operations Research, 172, 405-427 (2009) · Zbl 1184.90131
[4] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packings in two dimensions, SIAM Journal on Computing, 9, 846-855 (1980) · Zbl 0447.68080
[5] Bansal, N., Han, X., Iwama, K., Sviridenko, M., Zhang, G., 2007. Harmonic algorithm for 3-dimensional strip packing problem. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms SODA ’07, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 1197-1206.; Bansal, N., Han, X., Iwama, K., Sviridenko, M., Zhang, G., 2007. Harmonic algorithm for 3-dimensional strip packing problem. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms SODA ’07, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 1197-1206. · Zbl 1302.90165
[6] Bischoff, E. E.; Ratcliff, M. S.W., Issues in the development of approaches to container loading, Omega, 23, 377-390 (1995) · Zbl 0858.90106
[7] Bortfeldt, A., A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, European Journal of Operational Research, 172, 814-837 (2006) · Zbl 1111.90094
[8] Bortfeldt, A., Gehring, H., 1999. Two metaheuristics for strip packing problems. In: Proceedings band der 5th International Conference of the Decision Sciences Institute, Athen, Vol. 2, pp. 1153-1156.; Bortfeldt, A., Gehring, H., 1999. Two metaheuristics for strip packing problems. In: Proceedings band der 5th International Conference of the Decision Sciences Institute, Athen, Vol. 2, pp. 1153-1156.
[9] Bortfeldt, A.; Gehring, H., A hybrid genetic algorithm for the container loading problem, European Journal of Operational Research, 131, 143-161 (2001) · Zbl 0979.90101
[10] Bortfeldt, A.; Mack, D., A heuristic for the three-dimensional strip packing problem, European Journal of Operational Research, 183, 1267-1279 (2007) · Zbl 1136.90413
[11] Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 655-671 (2004) · Zbl 1165.90690
[12] Burke, E. K.; Kendall, G.; Whitwell, G., A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem, INFORMS Journal on Computing, 21, 505-516 (2009) · Zbl 1243.90254
[13] Chazelle, B., The bottom-left bin-packing heuristic: An efficient implementation, IEEE Transactions on Computers, C-32, 697-707 (1983) · Zbl 0526.68065
[14] Crainic, T. G.; Perboli, G.; Tadei, R., Extreme point-based heuristics for three-dimensional bin packing, INFORMS Journal on Computing, 20, 368-384 (2008) · Zbl 1243.90088
[15] Davies, A. P.; Bischoff, E. E., Weight distribution considerations in container loading, European Journal of Operational Research, 114, 509-527 (1999) · Zbl 0938.90056
[16] Fanslau, T.; Bortfeldt, A., A tree search algorithm for solving the container loading problem, INFORMS Journal on Computing, 22, 222-235 (2010) · Zbl 1243.90090
[17] He, Y.; Wu, Y.; de Souza, R., A global search framework for practical three-dimensional packing with variable carton orientations, Computers and Operations Research (2011)
[18] Hifi, M., Exact algorithms for the guillotine strip cutting/packing problem, Computers and Operations Research, 25, 925-940 (1998) · Zbl 1040.90568
[19] Huang, W.; Li, Y.; Akeb, H.; Li, C., Greedy algorithms for packing unequal circles into a rectangular container, Journal of The Operational Research Society, 56, 539-548 (2005) · Zbl 1095.90095
[20] Huang, W. Q.; Li, Y.; Li, C. M.; Xu, R. C., New heuristics for packing unequal circles into a circular container, Computers and Operations Research, 33, 2125-2142 (2006) · Zbl 1086.90063
[21] Jansen, K.; Solis-Oba, R., An asymptotic approximation algorithm for 3d-strip packing, (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete algorithm SODA ’06, New York, NY, USA (2006), ACM), 143-152 · Zbl 1192.90176
[22] Karabulut, K.; İnceoğlu, M. M., A hybrid genetic algorithm for packing in 3d with deepest bottom left with fill method, (Yakhno, T., Advances in information systems. Advances in information systems, Lecture Notes in Computer Science, Vol. 3261 (2005), Springer: Springer Berlin/ Heidelberg), 441-450
[23] Kenmochi, M.; Imamichi, T.; Nonobe, K.; Yagiura, M.; Nagamochi, H., Exact algorithms for the two-dimensional strip packing problem with and without rotations, European Journal of Operational Research, 198, 73-83 (2009) · Zbl 1163.90803
[24] Leung, S. C.H.; Zhang, D., A new heuristic approach for the stock-cutting problems, (Engineering and Technology K: Business and Economic Sciences, vol. 2 (2010), World Academy of Science), 121-126, 2
[25] Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, INFORMS Journal on Computing, 15, 310-319 (2003) · Zbl 1238.90116
[26] 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, 412-422 (2008) · Zbl 1243.90094
[27] Parreño, F.; Alvarez-Valdes, R.; Oliveira, J.; Tamarit, J., Neighborhood structures for the container loading problem: A vns implementation, Journal of Heuristics, 16, 1-22 (2010) · Zbl 1184.90174
[28] Pisinger, D., Heuristics for the container loading problem, European Journal of Operational Research, 141, 382-392 (2002) · Zbl 1081.90613
[29] Terno, J.; Scheithauer, G.; Sommerweiß, U.; Riehme, J., An efficient approach for the multi-pallet loading problem, European Journal of Operational Research, 123, 372-381 (2000) · Zbl 0967.90040
[30] Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 1109-1130 (2007) · Zbl 1278.90347
[31] Weng, Y., Guo, S., Zhu, W., Lim, A., Oon, W.-C., 2010. The 6 key elements to SCLP block building approaches. In: International Conference on Educational and Information Technology (ICEIT), Vol. 1, 2010, pp. 402-407.; Weng, Y., Guo, S., Zhu, W., Lim, A., Oon, W.-C., 2010. The 6 key elements to SCLP block building approaches. In: International Conference on Educational and Information Technology (ICEIT), Vol. 1, 2010, pp. 402-407.
[32] Wu, Y.-L.; Huang, W.; Lau, S.-C.; Wong, C. K.; Young, G. H., An effective quasi-human based heuristic for solving the rectangle packing problem, European Journal of Operational Research, 141, 341-358 (2002) · Zbl 1081.90615
[33] Zhang, D.; Liu, Y.; Chen, S.; Xie, X., A meta-heuristic algorithm for the strip rectangular packing problem, (Wang, L.; Chen, K.; Ong, Advances in Natural Computation chapter 157. Advances in Natural Computation chapter 157, Lecture Notes in Computer Science, 3612 (2005), Springer Berlin/ Heidelberg: Springer Berlin/ Heidelberg Berlin, Heidelberg), 1235-1241
[34] Zhang, D.; Kang, Y.; Deng, A., A new heuristic recursive algorithm for the strip rectangular packing problem, Computers and Operations Research, 33, 2209-2217 (2006) · Zbl 1086.90068
[35] Zhang, D. F.; Wei, L. J.; Chen, Q. S.; Chen, H. W., A combinatorial heuristic algorithm for the three-dimensional packing problem(in chinese with english abstract), Journal of Software, 18, 2083-2089 (2007) · Zbl 1174.90768
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.