HAPE3D—a new constructive algorithm for the 3D irregular packing problem

Abstract

We propose a new constructive algorithm, called HAPE3D, which is a heuristic algorithm based on the principle of minimum total potential energy for the 3D irregular packing problem, involving packing a set of irregularly shaped polyhedrons into a box-shaped container with fixed width and length but unconstrained height. The objective is to allocate all the polyhedrons in the container, and thus minimize the waste or maximize profit. HAPE3D can deal with arbitrarily shaped polyhedrons, which can be rotated around each coordinate axis at different angles. The most outstanding merit is that HAPE3D does not need to calculate no-fit polyhedron (NFP), which is a huge obstacle for the 3D packing problem. HAPE3D can also be hybridized with a meta-heuristic algorithm such as simulated annealing. Two groups of computational experiments demonstrate the good performance of HAPE3D and prove that it can be hybridized quite well with a meta-heuristic algorithm to further improve the packing quality.

Keywords

3D packing problem / Layout design / Simulation / Optimization / Constructive algorithm / Meta-heuristics

References

[1] Allen, S.D., Burke, E.K., Kendall, G., 2011. A hybrid placement strategy for the three-dimensional strip packing problem. Eur. J. Oper. Res., 209(3): 219-227. [

[2] Al-Raoush, R., Alsaleh, M., 2007. Simulation of random packing of polydisperse particles. Powder Technol., 176(1): 47-55. [

[3] Art, J.R.C., 1966. An Approach to the Two Dimensional Irregular Cutting Stock Problem. IBM Cambridge Scientific Center Report, Massachusetts.

[4] Bennell, J.A., Dowsland, K.A., Dowsland, W.B., 2001. The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon. Comput. Oper. Res., 28(3): 271-287. [

[5] Bortfeldt, A., Wäscher, G., 2013. Constraints in container loading—a state-of-the-art review. Eur. J. Oper. Res., 229(1): 1-20. [

[6] Burke, E.K., Hellier, R.S.R., Kendall, G., , 2007. Complete and robust no-fit polygon generation for the irregular stock cutting problem. Eur. J. Oper. Res., 179(1): 27-49. [

[7] Cagan, J., Degentesh, D., Yin, S., 1998. A simulated annealingbased algorithm using hierarchical models for general three-dimensional component layout. Comput.-Aid. Des., 30(10): 781-790. [

[8] Cui, S., Zhang, S., Chen, X., , 2011. Point-in-polyhedra test with direct handling of degeneracies. Geo-spatial Inform. Sci., 14(2): 91-97. [

[9] Ericson, C., 2004. Real-Time Collision Detection. The Morgan Kaufmann Series in Interactive 3-D Technology. CRC Press, USA.

[10] Huo, J., Li, G., Teng, H., 2006. Layout optimization of a satellite module using a parallel genetic-Powell-ant colony hybrid algorithm. J. Dalian Univ. Technol., 46(5): 679-684.

[11] Liu, H., He, Y., 2006. Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowestgravity- center principle. J. Zhejiang Univ.-Sci. A, 7(4): 570-576. [

[12] Liu, X., Ye, J., 2011. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems. J. Zhejiang Univ.-Sci. A (Appl. Phys. & Eng.), 12(11): 860-872. [

[13] Song, Y., Turton, R., Kayihan, F., 2006. Contact detection algorithms for DEM simulations of tablet-shaped particles. Powder Technol., 161(1): 32-40. [

[14] Stoyan, Y., Chugay, A., 2009. Packing cylinders and rectangular parallelepipeds with distances between them into a given region. Eur. J. Oper. Res., 197(2): 446-455. [

[15] Stoyan, Y.G., Gil, N.I., Pankratov, A., , 2004. Packing Non-convex Polytopes into a Parallelepiped. Technische Universität Dresden, Dresden.

[16] Szykman, S., Cagan, J., 1995. A simulated annealing-based approach to three-dimensional component packing. J. Mech. Des., 117(2A): 308-314. [

[17] Wu, Y., Li, W., Goh, M., , 2010. Three-dimensional bin packing problem with variable bin height. Eur. J. Oper. Res., 202(2): 347-355. [

[18] Zhang, W., Gao, Y., Fang, L., , 2008. Three-dimensional component layout modeling and optimization design. Acta Aeronaut. Astronaut. Sin., 29(6): 1554-1562(in Chinese).