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

被引：0

作者：

Xiao LIU ^{[1
]}

Jia-min LIU ^{[2
]}

An-xi CAO ^{[3
]}

Zhuang-le YAO ^{[1
]}

机构：

[1] School of Civil and Transportation Engineering, South China University of Technology

[2] School of Information Science and Engineering, Shenyang University of Technology

[3] College of Ocean Science and Engineer, Shanghai Maritime University

来源：

Frontiers of Information Technology & Electronic Engineering | 2015年 / 16卷 / 05期

基金：

中央高校基本科研业务费专项资金资助;

关键词：

3D packing problem; Layout design; Simulation; Optimization; Constructive algorithm; Meta-heuristics;

D O I：

暂无

中图分类号：

TB482 [包装设计];

学科分类号：

1403 ;

摘要：

We propose a new constructive algorithm, called HAPE3 D, 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. HAPE3 D can deal with arbitrarily shaped polyhedrons, which can be rotated around each coordinate axis at different angles. The most outstanding merit is that HAPE3 D does not need to calculate no-fit polyhedron(NFP), which is a huge obstacle for the 3D packing problem. HAPE3 D can also be hybridized with a meta-heuristic algorithm such as simulated annealing. Two groups of computational experiments demonstrate the good performance of HAPE3 D and prove that it can be hybridized quite well with a meta-heuristic algorithm to further improve the packing quality.

引用

页码：380 / 390

页数：11

共 18 条

[1] Complete and robust no-fit polygon generation for the irregular stock cutting problem[J] . E.K. Burke,R.S.R. Hellier,G. Kendall,G. Whitwell. &nbspEuropean Journal of Operational Research . 2006 (1)
[2] Contact detection algorithms for DEM simulations of tablet-shaped particles[J] . Yongxin Song,Richard Turton,Ferhan Kayihan. &nbspPowder Technology . 2005 (1)
[3] The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon
Bennell, JA
Dowsland, KA
Dowsland, WB
[J]. COMPUTERS & OPERATIONS RESEARCH, 2001, 28 (03) : 271 - 287
[4] Packingnon-convex polytopes into a parallelepiped. Stoyan Y G,Gil M,Pankratov A V,et al. MATH-NM-06-2004 Technische Universitt ofDresden . 2004
[5] Real-Time Collision Detection. C Ericson. The MorganKaufmann Series in Interactive 3D Technology . 2004
[6] An approach to the dimensional irregular cutting-stock problem. Art R C. IBM Cambridge Scientific Center report 36-Y08 . 1966
[7] Heuristic algorithm based on the principle of minimum total potential energy(HAPE):a new algorithm for nesting problems
Xiao LIU
[J]. Journal of Zhejiang University-Science A(Applied Physics & Engineering), 2011, 12 (11) : 860 - 872
[8] Point-In-Polyhedra Test with Direct Handling of Degeneracies[J]. CUI Shulin 1,ZHANG Shuqing 2,CHEN Xuanxi 1,PANG Zhenping 1,FU Xiaoyang 1,ZHANG Xu 3 1.Department of Computer Science and Technology,Zhuhai College of Jilin University,Zhuhai 519041,China 2.Northeast Institute of Geography and Agricultural Ecology,Chinese Academy of Sciences,Changchun 130012,China 3.Department of Arts,Zhuhai College of Jilin University,Zhuhai 519041,China. Geo-Spatial Information Science. 2011(02)
[9] A simulated annealing-based approach to three-dimensional component packing. Szykman S,Cagan J. Journal of Mechanical Design . 1995
[10] 三维组件布局建模与优化设计
张卫红
高瑜
方亮
陈裕泽
[J]. 航空学报, 2008, (06) : 1554 - 1562

← 1 2 →