改进三维不规则排样构造算法  

Improved constructive algorithm for irregular three-dimensional packing problems

作　　者：刘虓[1] 徐磊 陈超核[1] 刘嘉敏[2] LIU Xiao;XU Lei;CHEN Chaohe;LIU Jiamin(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)

机构地区：[1]华南理工大学土木与交通学院,广东广州510640 [2]沈阳工业大学信息科学与工程学院,辽宁沈阳110870

出　　处：《计算机集成制造系统》2021年第1期165-171,共7页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(11627802);上海交通大学海洋工程国家重点实验室研究基金资助项目(1518)。

摘　　要：针对三维不规则排样构造算法的瓶颈问题提出了两方面改进:首先,将不规则三维零件进行矢量图与像素图的混合表达,在算法的初始阶段,零件采用矢量方式表达;在寻找最优排样姿态阶段则使用立方体微粒表达;在算法末尾阶段为了消除零件之间的缝隙并输出精确的排样图,零件恢复为矢量表达。然后,引入航空航天领域的“全姿态”概念:借助经线和纬线在球体上均匀布置多个表面点;以球心为起点,以表面点为终点,从而确定多个旋转轴。通过这种方法,零件可以获得比传统方法更多的旋转轴,从而大大提升了排样姿态的优化搜索空间。通过算例证明,所提算法具有执行速度快和排样性能好的优点。To solve the bottleneck problems in the three-dimensional irregular packing problems,two improved methods were proposed.First,the vector graphics were hybridized with bitmaps to describe the 3D irregular parts.The parts were described in form of vector graphics during the primary procedure of packing,and then represented by the cube-shaped particles before seeking optimal packing attitude.To eliminate the gaps between the parts and to export the accurate packing layout,the parts were restored again with vector graphics.Second,the concept of all-attitude in aerospace field was introduced.Multiple surface points were evenly arranged on the sphere through the longitudinal and latitudinal lines.Thus,multiple axis of rotation could be determined by taking the center of sphere as the starting point and the surface point as the ending point.In this way,the part could get more rotating shafts than the traditional method,thus greatly improving the optimization search space of the packing attitude.Numerical examples proved that the proposed algorithm had the advantages of fast execution speed and good layout performance.

关 键 词：三维排样 不规则排样 混合表达 全姿态 构造算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]