HAPE3D&amp;mdash;a new constructive algorithm for the 3D irregular packing problem*

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

doi:10.1631/FITEE.1400421

Your Location：

Home >

Browse articles >

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

Computer & Automation | Updated：2022-06-06

- HAPE3D—a new constructive algorithm for the 3D irregular packing problem*
- 一种新型三维不规则排样构造算法HAPE3D
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 5, Pages: 380-390(2015)
- 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：
- DOI：10.1631/FITEE.1400421
  CLC：
- Received：08 December 2014，
  
  Revised：2015-04-10，
  
  Accepted：29 March 2015，
  
  Published：2015-03
- Accepted：
Scan QR Code
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：

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

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

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

Related Author

Xiao-qing ZHANG

Zheng-feng MING

Tian-qi WU

Min YAO

Jian-hua YANG

Salvador IBARRA-MARTNEZ

JosA. CASTN-ROCHA

Julio LARIA-MENCHACA

Related Institution

School of Mechano-Electronic Engineering, Xidian University

School of Physics and Electronic Engineering, Xianyang Normal University

School of Computer Science and Technology, Zhejiang University

Engineering School, Autonomous University of Tamaulipas

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰

HAPE3D&mdash;a new constructive algorithm for the 3D irregular packing problem*

DOI：10.1631/FITEE.1400421

摘要

Abstract

关键词

Keywords

references

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