|
|
|
| HAPE3D—a new constructive algorithm for the 3D irregular packing problem |
| Xiao Liu, Jia-min Liu, An-xi Cao, Zhuang-le Yao |
| School of Civil and Transportation Engineering, South China University of Technology, Guangzhou 510640, China; School of Information Science and Engineering, Shenyang University of Technology, Shenyang 110870, China; College of Ocean Science and Engineer, Shanghai Maritime University, Shanghai 201306, China |
|
|
|
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.
|
|
Received: 08 December 2014
Published: 05 May 2015
|
|
|
一种新型三维不规则排样构造算法HAPE3D
目的：现实工程中存在大量排样问题，其中最具挑战的是三维不规则排样问题。研究该类问题的首要难题是将三维不规则排样问题转化为一个优化问题。本文提供一个构造算法HAPE3D,将不规则三维排样问题转化成一个组合优化问题。
创新点：提出的新型不规则排样构造算法HAPE3D无需计算临界多面体（NFP）,并允许零件灵活旋转。
方法：首先，用最小势能原理解释三维不规则排样问题中零件的运动机理（图5）。然后，提出HAPE3D三个重要技术环节：（1）三维体的分离判据（图6）;（2）点在三维体内的判据（图7）；（3）多面体靠接算法（图8、9）。接着，给出HAPE3D的算法流程。最后通过两个算例检验算法可行性。
结论：HAPE3D是一种非常可靠的三维不规则排样算法。它区别于其它同类算法的最大特点是无需计算NFP，并在保持零件原有面貌（不需要将零件分解为多个长方体）的基础上允许零件旋转。HAPE3D可方便地与其它启发式算法（比如SA）结合形成混合启发式算法，从而进一步提高排样效率，其计算速度还有很大改进空间。
关键词：
三维排样,
布置设计,
仿真,
优化,
构造算法,
现代启发式算法
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
