Abstract
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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Beasley, J. E. (1985a). Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society, 36, 297–306.
Beasley, J. E. (1985b). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33, 49–64.
Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072.
Bengtsson, B. E. (1982). Packing rectangular pieces—a heuristic approach. The Computer Journal, 25, 353–357.
Berkey, J. O., & Wang, P. Y. (1987). Two dimensional finite bin packing algorithms. Journal of the Operational Research Society, 38, 423–429.
Bischoff, E. E., Janetz, F., & Ratcliff, M. S. W. (1995). Loading pallets with non-identical items. European Journal of Operational Research, 84, 681–692.
Boschetti, M. A. (2004). New lower bounds for the finite three-dimensional bin packing problem. Discrete Applied Mathematics, 140, 241–258.
Boschetti, M. A., & Mingozzi, A. (2003a). Two-dimensional finite bin packing problems. Part I: New lower and upper bounds. 4OR, 1, 27–42.
Boschetti, M. A., & Mingozzi, A. (2003b). Two-dimensional finite bin packing problems. Part II: New lower and upper bounds. 4OR, 2, 135–147.
Christofides, N., & Whitlock, C. (1977). An algorithm for two-dimensional cutting problems. Operations Research, 25(1), 30–44.
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.
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.
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.
Fekete, S. P., & Schepers, J. (2004a). A combinatorial characterization of higher-dimensional orthogonal packing. Mathematics of Operations Research, 29(2), 353–368.
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.
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.
Fekete, S. P., Schepers, J., & Van der Veen, J. C. (2007). An exact algorithm for higher-dimensional packing. Operations Research, 55, 569–587.
Feo, T. A., & Resende, M. G. C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8, 67–71.
Gibbons, J. D., & Chakraborti, S. (2003). Non parametric statistical inference (4th ed.). New York: Marcel Dekker.
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.
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.
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.
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.
Martello, S., & Vigo, D. (1998). Exact solution of the two-dimensional finite bin packing problem. Management Science, 44(3), 388–399.
Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations Research, 40, 256–267.
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.
Monaci, M., & Toth, P. (2006). A set-covering-based heuristic approach for bin-packing problems. INFORMS Journal on Computing, 18(1), 71–85.
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.
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.
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.
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.
Wäscher, G., Haussner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research. 183, 1109–1130.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Parreño, F., Alvarez-Valdes, R., Oliveira, J.F. et al. A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing. Ann Oper Res 179, 203–220 (2010). https://doi.org/10.1007/s10479-008-0449-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0449-4