Abstract
Based on the concept of maximal rectangular space that can be filled at current time and the siege warfare tactics, we make several critical improvements on the quasi-human caving-degree approach to get a stronger algorithm ICDA for a classical NP hard problem: the three-dimensional rectangular packing problem. Within similar computing time, the new algorithm gained an average volume utilization of 90.92% on the natural and difficult 100 benchmarks, called BR15, where items to be packed are almost different in size. Compared with current best record just reported in the literature in 2010, our result makes an improvement by 0.54%.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cook S A. The complexity of theorem-proving procedures. In: Harrison M A, Banerji R B, Ullman J D, eds. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC). New York: ACM Press, 1971. 151–158
Cook S A. The P vs. NP Problem. CLAY Mathematics Foundation Millennium Problems, http://www.claymath.org/millennium
Wigderson A. P, NP and mathematics: a computational complexity perspective. In: International Congress of Mathematicians (ICM). Zurich: EMS Publishing House, 2007. 1: 665–712
Huang W Q, Zhan S H. A quasi-physical method for solving packing problems (in Chinese). J Appl Math, 1979, 2: 176–180
Huang W Q, Xu R C. Introduction to the Modern Theory of Computation D Background, Foreground and Solving Method for the NP-hard Problem (in Chinese). Beijing: Science Press, 2004. 47–70
Huang W Q, He K. A pure quasi-human algorithm for solving the cuboid packing problem. Sci China Ser F-Inf Sci, 2009, 52: 52–58
Huang W Q, He K. A caving degree approach for the single container loading problem. Eur J Oper Res, 2009, 196: 93–101
Bischoff E E. Three-dimensional packing of items with limited load bearing strength. Eur J Oper Res, 2006, 168: 952–966
Moura A, Oliveira J F. A GRASP approach to the container-loading problem. IEEE Intell Syst, 2005, 20: 50–57
Gehring H, Bortfeldt A. A parallel genetic algorithm for solving the container loading problem. Int Trans Oper Res, 2002, 9: 497–511
Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem. Eur J Oper Res, 2001, 131: 143–161
Bortfeldt A, Gehring H, Mack D. A parallel tabu search algorithm for solving the container loading problem. Parall Comput, 2003, 29: 641–662
Parreno F, Alvarez-Valdes R, Oliveira J F, et al. Neighborhood structures for the container loading problem: a VNS implementation. J Heurist, 2010, 16: 1–22
Bischoff E E, Ratcliff M S W. Issues in the development of approaches to container loading. OMEGA-Int J Manag S, 1995, 23: 377–390
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
He, K., Huang, W. A quasi-human algorithm for solving the three-dimensional rectangular packing problem. Sci. China Inf. Sci. 53, 2389–2398 (2010). https://doi.org/10.1007/s11432-010-4112-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-010-4112-8