Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2015, Vol. 16 Issue (5): 380-390    DOI: 10.1631/FITEE.1400421
    
一种新型三维不规则排样构造算法HAPE3D
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
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
 全文: PDF 
摘要： 目的：现实工程中存在大量排样问题，其中最具挑战的是三维不规则排样问题。研究该类问题的首要难题是将三维不规则排样问题转化为一个优化问题。本文提供一个构造算法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.
Key words: 3D packing problem    Layout design    Simulation    Optimization    Constructive algorithm    Meta-heuristics
收稿日期: 2014-12-08 出版日期: 2015-05-05
CLC:  TP391.7  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Xiao Liu
Jia-min Liu
An-xi Cao
Zhuang-le Yao

引用本文:

Xiao Liu, Jia-min Liu, An-xi Cao, Zhuang-le Yao. HAPE3D—a new constructive algorithm for the 3D irregular packing problem. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 380-390.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1400421    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2015/V16/I5/380

[1] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . 使用猫群算法优化线性天线阵列的最佳阵因子辐射方向图：电磁仿真验证[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 570-577.
[2] Hamid Reza Boveiri. 基于渐进式蚁群优化的多处理器任务分配[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 498-510.
[3] Ali Darvish Falehi, Ali Mosallanejad. 使用基于多目标粒子群算法多层自适应模糊推理系统晶闸管控制串联电容器补偿技术的互联多源电力系统动态稳定性增强器[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 394-409.
[4] Jun-hong Zhang, Yu Liu. 应用完备集合固有时间尺度分解和混合差分进化和粒子群算法优化的最小二乘支持向量机对柴油机进行故障诊断[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 272-286.
[5] He Hao, Wei-zhong Fei, Dong-min Miao, Meng-jia Jin, Jian-xin Shen. 有定子径向通风孔的大型永磁同步发电机的转矩特性[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(8): 814-824.
[6] Tian-qi Wu, Min Yao, Jian-hua Yang. 海豚群算法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(8): 717-729.
[7] Xiao-xin Fu, Yong-heng Jiang, De-xian Huang, Jing-chun Wang, Kai-sheng Huang. 基于候选曲线的公路轨迹规划中的智能计算量分配[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(6): 553-565.
[8] Izabela Nielsen, Robert Wójcik, Grzegorz Bocewicz, Zbigniew Banaszak. 模糊操作时间约束下的多模过程优化：声明式建模方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(4): 338-347.
[9] Friederike Wall. 自适应分布式搜索过程中的组织变化及问题复杂度对性能的影响[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(4): 283-295.
[10] Rui Zhao, Gui-he Qin, Jia-qiao Liu. 一种解决FlexRay总线静态段信号调度问题的矩形装箱优化方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(4): 375-388.
[11] Gao-qi He, Yi Jin, Qi Chen, Zhen Liu, Wen-hui Yue, Xing-jian Lu. 基于影子障碍物模型的真实感人群转弯行为模拟[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(3): 200-211.
[12] Xin Li, Jin Sun, Fu Xiao, Jiang-shan Tian. 一种基于参数扰动的芯片成品率双目标优化框架[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(2): 160-172.
[13] Jing-fa Liu, Juan Huang, Gang Li, Wen-jie Liu, Ting-zhao Guan, Liang Hao. 一种基于新的势能曲面变平的卫星舱布局问题的启发式方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(10): 1031-1043.
[14] Zi-wu Ren, Zhen-hua Wang, Li-ning Sun. 基于混合生物地理学优化的8自由度冗余臂逆运动学求解[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(7): 607-616.
[15] Ahmet Sayar, Süleyman Eken, Okan ?ztürk. 不确定空间二维范围查询的Kd-树和四叉树分解[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 98-108.