Full Text:   <2397>

Summary:  <1994>

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: 6532

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Xiao Liu

http://orcid.org/0000-0003-2975-4749

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2015 Vol.16 No.5 P.380-390

http://doi.org/10.1631/FITEE.1400421


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


Author(s):  Xiao Liu, Jia-min Liu, An-xi Cao, Zhuang-le Yao

Affiliation(s):  School of Civil and Transportation Engineering, South China University of Technology, Guangzhou 510640, China; more

Corresponding email(s):   liuxiao@scut.edu.cn

Key Words:  3D packing problem, Layout design, Simulation, Optimization, Constructive algorithm, Meta-heuristics


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.

一种新型三维不规则排样构造算法HAPE3D

目的:现实工程中存在大量排样问题,其中最具挑战的是三维不规则排样问题。研究该类问题的首要难题是将三维不规则排样问题转化为一个优化问题。本文提供一个构造算法HAPE3D,将不规则三维排样问题转化成一个组合优化问题。
创新点:提出的新型不规则排样构造算法HAPE3D无需计算临界多面体(NFP),并允许零件灵活旋转。
方法:首先,用最小势能原理解释三维不规则排样问题中零件的运动机理(图5)。然后,提出HAPE3D三个重要技术环节:(1)三维体的分离判据(图6);(2)点在三维体内的判据(图7);(3)多面体靠接算法(图8、9)。接着,给出HAPE3D的算法流程。最后通过两个算例检验算法可行性。
结论:HAPE3D是一种非常可靠的三维不规则排样算法。它区别于其它同类算法的最大特点是无需计算NFP,并在保持零件原有面貌(不需要将零件分解为多个长方体)的基础上允许零件旋转。HAPE3D可方便地与其它启发式算法(比如SA)结合形成混合启发式算法,从而进一步提高排样效率,其计算速度还有很大改进空间。

关键词:三维排样;布置设计;仿真;优化;构造算法;现代启发式算法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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).

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE