The Three-Dimensional Bin Packing Problem
作者： Silvano Martello , David Pisinger , Daniele Vigo
DOI: 10.1287/OPRE.48.2.256.12386
关键词: Mathematics 、 Square packing in a square 、 Bin packing problem 、 Cutting stock problem 、 Exact algorithm 、 Approximation algorithm 、 Set packing 、 Bin 、 Discrete mathematics 、 Upper and lower bounds 、 Applied mathematics
摘要: The problem addressed in this paper is that of orthogonally packing a given set rectangular-shaped items into the minimum number three-dimensional rectangular bins. strongly NP-hard and extremely difficult to solve practice. Lower bounds are discussed, it proved asymptotic worst-case performance ratio continuous lower bound ?. An exact algorithm for filling single bin developed, leading definition an branch-and-bound problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up 90 items, presented: It shown many can be solved optimality within reasonable time limit.
acm.org
core.ac.uk
jstor.org 
sci-hub.se 参考文章(18)
Guntram Scheithauer, A Three-dimensional Bin Packing Algorithm Journal of Automata, Languages and Combinatorics. ,vol. 27, pp. 263- 271 ,(1991)
Harald Dyckhoff, Ute Finke, Cutting and Packing in Production and Distribution Contributions to Management Science. ,(1992) , 10.1007/978-3-642-58165-6
M. R. Garey, E. G. Coffman, D. S. Johnson, Approximation algorithms for bin packing: a survey Approximation algorithms for NP-hard problems. pp. 46- 93 ,(1996)
Harald Dyckhoff, A typology of cutting and packing problems European Journal of Operational Research. ,vol. 44, pp. 145- 159 ,(1990) , 10.1016/0377-2217(90)90350-K
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
Eleni Hadjiconstantinou, Nicos Christofides, An exact algorithm for general, orthogonal, two-dimensional knapsack problems European Journal of Operational Research. ,vol. 83, pp. 39- 56 ,(1995) , 10.1016/0377-2217(93)E0278-6
C.S. Chen, S.M. Lee, Q.S. Shen, An analytical model for the container loading problem European Journal of Operational Research. ,vol. 80, pp. 68- 76 ,(1995) , 10.1016/0377-2217(94)00002-T
Eberhard E. Bischoff, Michael D. Marriott, A comparative evaluation of heuristics for container loading European Journal of Operational Research. ,vol. 44, pp. 267- 276 ,(1990) , 10.1016/0377-2217(90)90362-F
Keqin Li, Kam-Hoi Cheng, On three-dimensional packing SIAM Journal on Computing. ,vol. 19, pp. 847- 867 ,(1990) , 10.1137/0219059
J.A. George, D.F. Robinson, A heuristic for packing boxes into a container Computers & Operations Research. ,vol. 7, pp. 147- 156 ,(1980) , 10.1016/0305-0548(80)90001-5