Full Text:
<3234>
Summary: 
<2273>
CLC number: TP391.7
On-line Access: 2015-05-05
Received: 2014-12-08
Revision Accepted: 2015-03-29
Crosschecked: 2015-04-10
Cited: 0
Clicked: 8121
HAPE3D—a new constructive algorithm for the 3D irregular packing problem
| ||||||||||||||
Xiao Liu, Jia-min Liu, An-xi Cao, Zhuang-le Yao. HAPE3D—a new constructive algorithm for the 3D irregular packing problem[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(5): 380-390.
@article{title="HAPE3D—a new constructive algorithm for the 3D irregular packing problem",
author="Xiao Liu, Jia-min Liu, An-xi Cao, Zhuang-le Yao",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="16",
number="5",
pages="380-390",
year="2015",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1400421"
}
%0 Journal Article
%T HAPE3D—a new constructive algorithm for the 3D irregular packing problem
%A Xiao Liu
%A Jia-min Liu
%A An-xi Cao
%A Zhuang-le Yao
%J Frontiers of Information Technology & Electronic Engineering
%V 16
%N 5
%P 380-390
%@ 2095-9184
%D 2015
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1400421
TY - JOUR
T1 - HAPE3D—a new constructive algorithm for the 3D irregular packing problem
A1 - Xiao Liu
A1 - Jia-min Liu
A1 - An-xi Cao
A1 - Zhuang-le Yao
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 16
IS - 5
SP - 380
EP - 390
%@ 2095-9184
Y1 - 2015
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1400421
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.
The paper is very well written. The problem which the authors tackle (3D Irregular Packing) is a very difficult problem to address, where little research has progressed beyond the use of simple objects (such as rectangles/cubes and cylinders/spheres). Expanding the current knowledge regarding 3D packing with irregular pieces is a very important step considering industrial requirements, and possible efficiency gains (including waste reduction). Those approaches are a good and interesting contribution to the 3D irregular packing problem research area.
[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., et al., 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 annealing-based algorithm using hierarchical models for general three-dimensional component layout. Comput.-Aid. Des., 30(10):781-790.
[8]Cui, S., Zhang, S., Chen, X., et al., 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 lowest-gravity-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., et al., 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., et al., 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., et al., 2008. Three-dimensional component layout modeling and optimization design. Acta Aeronaut. Astronaut. Sin., 29(6):1554-1562 (in Chinese).
ORCID: 
Open peer comments: Debate/Discuss/Question/Opinion
<1>