上海交通大学学报

上海交通大学学报（自然版） ›› 2013, Vol. 47 ›› Issue (07): 1060-1064.

• 自动化技术、计算机技术 • 上一篇    下一篇

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

刘虓1,操安喜2,叶家玮1   

  1. (1.华南理工大学 土木与交通学院， 广州 510640; 2.上海海事大学 海洋环境与工程学院， 上海 201306)
     
  • 收稿日期:2012-08-21 出版日期:2013-07-30 发布日期:2013-07-30
  • 基金资助:

    国家高技术研究发展计划（863）项目（2009AA093303）

A Novel Constructive Algorithm for Irregular Three-dimensional Packing Problems

LIU Xiao1,CAO Anxi2,YE Jiawei1
  

  1. (1.School of Civil and Transportation Engineering, South China University of Technology, Guangzhou 510640, China; 2.College of Ocean Environment and Engineer, Shanghai Maritime University, Shanghai 201306, China)
  • Received:2012-08-21 Online:2013-07-30 Published:2013-07-30

摘要：

基于最小势能原理，提出了一种新型不规则三维排样构造算法(HAPE3D)：容器内部均匀分布多个离散排样点，零件依次平移至每个排样点，然后绕x、y、z轴旋转，最终找到使零件重心最低的最优排样姿态.文中还提出了一个多面体重叠检测算法，令HAPE3D摆脱了临界多面体束缚.算例表明,HAPE3D能够处理任意形状的多面体零件，并可以考虑零件旋转，同时具备孔洞填充功能.HAPE3D的速度也较快，使其与现代启发式算法混合成为可能.
 
 

关键词: 三维排样, 不规则排样, 构造算法, 多面体重叠检测, 优化

Abstract:

This paper presented a novel constructive algorithm(HAPE3D) for irregular three-dimensional packing problems based on the principle of minimum total potential energy. Many equally spaced points were set in the container. Each spare part was moved to the points one by one and was rotated by an angle around the x, y and z axis. An optimal attitude was found at which the spare part had the lowest center of gravity. In addition, a novel technique for polygon overlap testing was proposed which enabled the HAPE3D to get out of the dependence on no-fit polyhedron. Numerical experiment shows that the HAPE3D is capable of hole-filling and packing the arbitrarily shaped spare part which is permitted to rotate. Moreover, the HAPE3D is fast,  making it possible to hybridize  with one of meta-heuristics.

Key words:  three-dimensional packing, irregular packing, constructive algorithm, polyhedron intersection detecting test, optimization

中图分类号: