Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic
作者： Lukas Baumgartner , Verena Schmid , Christian Blum
DOI: 10.1007/978-3-642-25566-3_6
关键词: Upper and lower bounds 、 Probabilistic logic 、 Cutting stock problem 、 Heuristic 、 Integer programming 、 Set packing 、 Heuristics 、 Algorithm 、 Computer science 、 Mathematical optimization 、 Bin packing problem
摘要: The two-dimensional bin packing problem (2BP) consists in a set of rectangular items into rectangular, equally-sized bins. is NP-hard and has multitude real world applications. We consider the case where are oriented guillotine cutting free. In this paper we first present review well-know heuristics for 2BP then propose new ILP model problem. Moreover, develop multi-start algorithm based on probabilistic version LGFi heuristic from literature. Results compared to other well-known heuristics, using data sets provided obtained experimental results show that proposed returns excellent solutions. With an average percentage deviation 1.8% best know lower bounds it outperformes algorithms by 1.1%−5.7%. Also 3 500 instances tested upper bound was found.
springer.com
core.ac.uk
sci-hub.st 参考文章(19)
F. R. K. Chung, M. R. Garey, D. S. Johnson, On Packing Two-Dimensional Bins Siam Journal on Algebraic and Discrete Methods. ,vol. 3, pp. 66- 76 ,(1982) , 10.1137/0603007
Edward G Coffman, Jr, Michael R Garey, David S Johnson, Robert Endre Tarjan, Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms SIAM Journal on Computing. ,vol. 9, pp. 808- 826 ,(1980) , 10.1137/0209062
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
William B. Dowsland, On a Research Bibliography for Cutting and Packing Problems Journal of the Operational Research Society. ,vol. 43, pp. 1020- 1020 ,(1992) , 10.1057/JORS.1992.157
Brenda S Baker, Edward G Coffman, Jr, Ronald L Rivest, Orthogonal Packings in Two Dimensions SIAM Journal on Computing. ,vol. 9, pp. 846- 855 ,(1980) , 10.1137/0209064
Andrea Lodi, Silvano Martello, Michele Monaci, Two-dimensional packing problems: A survey European Journal of Operational Research. ,vol. 141, pp. 241- 252 ,(2002) , 10.1016/S0377-2217(02)00123-6
Andrea Lodi, Silvano Martello, Daniele Vigo, Recent advances on two-dimensional bin packing problems Discrete Applied Mathematics. ,vol. 123, pp. 379- 396 ,(2002) , 10.1016/S0166-218X(01)00347-X
Andrea Lodi, Silvano Martello, Daniele Vigo, Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems Informs Journal on Computing. ,vol. 11, pp. 345- 357 ,(1999) , 10.1287/IJOC.11.4.345
E. Hopper, B. Turton, A genetic algorithm for a 2D industrial packing problem annual conference on computers. ,vol. 37, pp. 375- 378 ,(1999) , 10.1016/S0360-8352(99)00097-2
J. O. Berkey, P. Y. Wang, Two-Dimensional Finite Bin-Packing Algorithms Journal of the Operational Research Society. ,vol. 38, pp. 423- 429 ,(1987) , 10.1057/JORS.1987.70