×

zbMATH — the first resource for mathematics

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing. (English) Zbl 1201.90176
Summary: The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beasley, J. E. (1985a). Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society, 36, 297–306. · Zbl 0589.90040
[2] Beasley, J. E. (1985b). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33, 49–64. · Zbl 0569.90038 · doi:10.1287/opre.33.1.49
[3] Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072.
[4] Bengtsson, B. E. (1982). Packing rectangular pieces–a heuristic approach. The Computer Journal, 25, 353–357.
[5] Berkey, J. O., & Wang, P. Y. (1987). Two dimensional finite bin packing algorithms. Journal of the Operational Research Society, 38, 423–429. · Zbl 0611.90079
[6] Bischoff, E. E., Janetz, F., & Ratcliff, M. S. W. (1995). Loading pallets with non-identical items. European Journal of Operational Research, 84, 681–692. · Zbl 0928.90075 · doi:10.1016/0377-2217(95)00031-K
[7] Boschetti, M. A. (2004). New lower bounds for the finite three-dimensional bin packing problem. Discrete Applied Mathematics, 140, 241–258. · Zbl 1069.90085 · doi:10.1016/j.dam.2003.08.004
[8] Boschetti, M. A., & Mingozzi, A. (2003a). Two-dimensional finite bin packing problems. Part I: New lower and upper bounds. 4OR, 1, 27–42. · Zbl 1062.90051
[9] Boschetti, M. A., & Mingozzi, A. (2003b). Two-dimensional finite bin packing problems. Part II: New lower and upper bounds. 4OR, 2, 135–147. · Zbl 1097.90033
[10] 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
[11] Crainic, T. G., Perboli, G., & Tadei, R. (2008). TS 2 PACK: A two-level tabu search for the three-dimensional bin packing problem. European Journal of Operational Research. doi: 10.1016/j.ejr.2007.06.063 . · Zbl 1161.90012
[12] den Boef, E., Korst, J., Martello, S., Pisinger, D., & Vigo, D. (2005). Erratum to ’The three-dimensional bin packing problem’: robot-packable and orthogonal variants of packing problems. Operations Research, 53, 735–736. · Zbl 1165.90603 · doi:10.1287/opre.1050.0210
[13] Faroe, O., Pisinger, D., & Zachariasen, M. (2003). Guided local search for the three-dimensional bin-packing problem. INFORMS Journal on Computing, 15(3), 267–283. · Zbl 1238.90112 · doi:10.1287/ijoc.15.3.267.16080
[14] Fekete, S. P., & Schepers, J. (2004a). A combinatorial characterization of higher-dimensional orthogonal packing. Mathematics of Operations Research, 29(2), 353–368. · Zbl 1082.90095 · doi:10.1287/moor.1030.0079
[15] Fekete, S. P., & Schepers, J. (2004b). A general framework for bounds for higher-dimensional orthogonal packing problems. Mathematical Methods of Operations Research, 60(2), 311–329. · Zbl 1076.90049 · doi:10.1007/s001860400376
[16] Fekete, S. P., & Van der Veen, J. C. (2007). PackLib2: An integrated library of multi-dimensional packing problems. European Journal of Operational Research 183, 1131–1135. · Zbl 1136.90452 · doi:10.1016/j.ejor.2006.04.023
[17] Fekete, S. P., Schepers, J., & Van der Veen, J. C. (2007). An exact algorithm for higher-dimensional packing. Operations Research, 55, 569–587. · Zbl 1167.90483 · doi:10.1287/opre.1060.0369
[18] Feo, T. A., & Resende, M. G. C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8, 67–71. · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[19] Gibbons, J. D., & Chakraborti, S. (2003). Non parametric statistical inference (4th ed.). New York: Marcel Dekker. · Zbl 1115.62004
[20] Hansen, P., & Mladenovic, N. (2005). Variable neighborhood search. In E. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimization and decision support techniques (pp. 211–238). Berlin: Springer.
[21] Lodi, A., Martello, S., & Vigo, D. (1999). Approximation algorithms for the oriented two-dimensional bin packing problem. European Journal of Operational Research, 112(1), 158–166. · Zbl 0937.90121 · doi:10.1016/S0377-2217(97)00388-3
[22] Lodi, A., Martello, S., & Vigo, D. (2002). Heuristic algorithms for the three-dimensional bin packing problem. European Journal of Operational Research, 141(2), 410–420. · Zbl 1081.90612 · doi:10.1016/S0377-2217(02)00134-0
[23] Lodi, A., Martello, S., & Vigo, D. (2004). TSpack: a unified tabu search code for multi-dimensional bin packing problems. Annals of Operations Research, 131, 203–213. · Zbl 1066.90142 · doi:10.1023/B:ANOR.0000039519.03572.08
[24] Martello, S., & Vigo, D. (1998). Exact solution of the two-dimensional finite bin packing problem. Management Science, 44(3), 388–399. · Zbl 0989.90114 · doi:10.1287/mnsc.44.3.388
[25] Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations Research, 40, 256–267. · Zbl 1106.90371 · doi:10.1287/opre.48.2.256.12386
[26] Martello, S., Pisinger, D., Vigo, D., den Boef, E., & Korst, J. (2007). Algorithm 864: Algorithms for general and robot-packable variants of the three-dimensional bin packing problem. ACM Transactions on Mathematical Software, 33, 1. · Zbl 05458437 · doi:10.1145/1206040.1206047
[27] Monaci, M., & Toth, P. (2006). A set-covering-based heuristic approach for bin-packing problems. INFORMS Journal on Computing, 18(1), 71–85. · Zbl 1241.90191 · doi:10.1287/ijoc.1040.0089
[28] Parreño, F., Alvarez-Valdes, R., Oliveira, J. F., & Tamarit, J. M. (2008a). A maximal-space algorithm for the container loading problem. INFORMS Journal on Computing, 20, 412–422. · Zbl 1243.90094 · doi:10.1287/ijoc.1070.0254
[29] Parreño, F., Alvarez-Valdes, R., Oliveira, J. F., & Tamarit, J. M. (2008b). Neighborhood structures for the container loading problem: a VNS implementation. Journal of Heuristics. doi: 10.1007/s10732-008-9081-3 . · Zbl 1184.90174
[30] Prais, M., & Ribeiro, C. C. (2000). Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS Journal on Computing, 12(3), 164–176. · Zbl 1040.90504 · doi:10.1287/ijoc.12.3.164.12639
[31] Resende, M. G. C., & Ribeiro, C. C. (2003). Greedy randomized adaptive search procedures. In F. Glover & G. Kochenberger (Eds.), Handbook of metaheuristics (pp. 219–249). Dordrecht: Kluwer Academic. · Zbl 1102.90384
[32] Wäscher, G., Haussner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research. 183, 1109–1130. · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.