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

Liu Xiao; Liu Jia-min; Cao An-xi; Yao Zhuang-le

doi:10.1631/FITEE.1400421

Your Location：

Home >

Browse articles >

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

计算机与自动化 | Updated：2022-06-06

- 一种新型三维不规则排样构造算法HAPE3D
- HAPE3D—a new constructive algorithm for the 3D irregular packing problem*
- 信息与电子工程前沿（英文） 2015年16卷第5期页码：380-390
- Affiliations：
  
  1.School of Civil and Transportation Engineering, South China University of Technology, Guangzhou 510640, China
  2.School of Information Science and Engineering, Shenyang University of Technology, Shenyang 110870, China
  3.College of Ocean Science and Engineer, Shanghai Maritime University, Shanghai 201306, China
- Author bio：
  
  ‡Corresponding Author
- Funds：
  
  *Project supported by the Natural Science Foundation of Guangdong Province, China (No. S2013040016594), the Natural Science Foundation of Liaoning Province, China (No. 201102164), and the Fundamental Research Funds for the Central Universities, China (No. 2013ZM0124)
- DOI：10.1631/FITEE.1400421
  中图分类号：
- 收稿：2014-12-08，
  
  修回：2015-04-10，
  
  录用：2015-03-29，
  
  纸质出版：2015-03
- Accepted：
Scan QR Code
一种新型三维不规则排样构造算法HAPE3D[J]. 信息与电子工程前沿（英文）, 2015,16(5):380-390.

Liu Xiao, Liu Jia-min, Cao An-xi, et al. HAPE3D—a new constructive algorithm for the 3D irregular packing problem*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(5): 380-390.
一种新型三维不规则排样构造算法HAPE3D[J]. 信息与电子工程前沿（英文）, 2015,16(5):380-390. DOI： 10.1631/FITEE.1400421.

Liu Xiao, Liu Jia-min, Cao An-xi, et al. HAPE3D—a new constructive algorithm for the 3D irregular packing problem*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(5): 380-390. DOI： 10.1631/FITEE.1400421.

摘要

目的

现实工程中存在大量排样问题，其中最具挑战的是三维不规则排样问题。研究该类问题的首要难题是将三维不规则排样问题转化为一个优化问题。本文提供一个构造算法HAPE3D

将不规则三维排样问题转化成一个组合优化问题。

创新点

提出的新型不规则排样构造算法HAPE3D无需计算临界多面体（NFP）

并允许零件灵活旋转。

方法

首先，用最小势能原理解释三维不规则排样问题中零件的运动机理（图5）。然后，提出HAPE3D三个重要技术环节：（1）三维体的分离判据（图6）;（2）点在三维体内的判据（图7）；（3）多面体靠接算法（图8、9）。接着，给出HAPE3D的算法流程。最后通过两个算例检验算法可行性。

结论

HAPE3D是一种非常可靠的三维不规则排样算法。它区别于其它同类算法的最大特点是无需计算NFP，并在保持零件原有面貌（不需要将零件分解为多个长方体）的基础上允许零件旋转。HAPE3D可方便地与其它启发式算法（比如SA）结合形成混合启发式算法，从而进一步提高排样效率，其计算速度还有很大改进空间。

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

references

SD Allen , EK Burke , G Kendall . A hybrid placement strategy for the three-dimensional strip packing problem . Eur J Oper Res , 2011 . 209 ( 3 ): 219 - 227 . DOI: 10.1016/j.ejor.2010.09.023 http://doi.org/10.1016/j.ejor.2010.09.023 .

R Al-Raoush , M Alsaleh . Simulation of random packing of polydisperse particles . Powder Technol , 2007 . 176 ( 1 ): 47 - 55 . DOI: 10.1016/j.powtec.2007.02.007 http://doi.org/10.1016/j.powtec.2007.02.007 .

JRC Art . An Approach to the Two Dimensional Irregular Cutting Stock Problem . 1966 . IBM Cambridge Scientific Center Report, Massachusetts . .

JA Bennell , KA Dowsland , WB Dowsland . The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon . Comput Oper Res , 2001 . 28 ( 3 ): 271 - 287 . DOI: 10.1016/S0305-0548(00)00021-6 http://doi.org/10.1016/S0305-0548(00)00021-6 .

A Bortfeldt , G Wäscher . Constraints in container loading—a state-of-the-art review . Eur J Oper Res , 2013 . 229 ( 1 ): 1 - 20 . DOI: 10.1016/j.ejor.2012.12.006 http://doi.org/10.1016/j.ejor.2012.12.006 .

EK Burke , RSR Hellier , G Kendall , 等 . Complete and robust no-fit polygon generation for the irregular stock cutting problem . Eur J Oper Res , 2007 . 179 ( 1 ): 27 - 49 . DOI: 10.1016/j.ejor.2006.03.011 http://doi.org/10.1016/j.ejor.2006.03.011 .

J Cagan , D Degentesh , S Yin . A simulated annealing based algorithm using hierarchical models for general three-dimensional component layout . Comput-Aid Des , 1998 . 30 ( 10 ): 781 - 790 . DOI: 10.1016/S0010-4485(98)00036-0 http://doi.org/10.1016/S0010-4485(98)00036-0 .

S Cui , S Zhang , X Chen , 等 . Point-in-polyhedra test with direct handling of degeneracies . Geo-spatial Inform Sci , 2011 . 14 ( 2 ): 91 - 97 . DOI: 10.1007/s11806-011-0453-8 http://doi.org/10.1007/s11806-011-0453-8 .

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

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

H Liu , Y He . Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle . J Zhejiang Univ-Sci A , 2006 . 7 ( 4 ): 570 - 576 . DOI: 10.1631/jzus.2006.A0570 http://doi.org/10.1631/jzus.2006.A0570 .

X Liu , J Ye . 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) , 2011 . 12 ( 11 ): 860 - 872 . DOI: 10.1631/jzus.A1100038 http://doi.org/10.1631/jzus.A1100038 .

Y Song , R Turton , F Kayihan . Contact detection algorithms for DEM simulations of tablet-shaped particles . Powder Technol , 2006 . 161 ( 1 ): 32 - 40 . DOI: 10.1016/j.powtec.2005.07.004 http://doi.org/10.1016/j.powtec.2005.07.004 .

Y Stoyan , A Chugay . Packing cylinders and rectangular parallelepipeds with distances between them into a given region . Eur J Oper Res , 2009 . 197 ( 2 ): 446 - 455 . DOI: 10.1016/j.ejor.2008.07.003 http://doi.org/10.1016/j.ejor.2008.07.003 .

YG Stoyan , NI Gil , A Pankratov , 等 . Packing Non-convex Polytopes into a Parallelepiped . 2004 . Technische Universität Dresden, Dresden . .

S Szykman , J Cagan . A simulated annealing-based approach to three-dimensional component packing . J Mech Des , 1995 . 117 ( 2A ): 308 - 314 . DOI: 10.1115/1.2826140 http://doi.org/10.1115/1.2826140 .

Y Wu , W Li , M Goh , 等 . Three-dimensional bin packing problem with variable bin height . Eur J Oper Res , 2010 . 202 ( 2 ): 347 - 355 . DOI: 10.1016/j.ejor.2009.05.040 http://doi.org/10.1016/j.ejor.2009.05.040 .

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

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

An optimized grey wolf optimizer based on a mutation operator and eliminating-reconstructing mechanism and its application^#

Dolphin swarm algorithm

Optimizing urban traffic control using a rational agent