基于最小势能原理的不规则零件排样算法*

刘虓 叶家玮 胡金鹏

(华南理工大学土木与交通学院，广东广州510640)

排样在造船、布匹和皮革加工业中有着广泛应用.排样效率的微小提升可带来巨大的经济效益，而排样算法属于组合优化问题，具有极高的计算复杂度，国内外对此进行了几十年持续不断的研究.大多数零件具有不规则的几何外形，因此其排样问题具有重大的现实意义.

目前不规则零件排样的求解策略主要基于两点:“靠左向下”原则(BL)和临界多边形(NFP).BL最初由Baker等［1］提出，由于其简便性和良好表现被广泛采用，同时一些改进算法也相继出现［2］.由于BL会在母板上形成孔洞，造成浪费，于是有学者提出“靠左向下并填充孔洞”求解策略(BLF)，其计算复杂度为 O(N3)(N 为零件数).Chazelle［3］则提出了一种改进的 BLF算法，其算法复杂度为O(N2).

由Art［4］首次提出的NFP是一种功能强大的几何工具，它与BL结合产生了各种排样算法［5］.不少学者对NFP进行了专门研究［6-7］.NFP的求解非常耗时，求解时间与零件数量N及零件的旋转角个数(RN)成平方关系.以欧洲排样研究组织(ESICUP)提供的标准问题SWIM(N=10，RN=2)为例，Burke等［7］声称每个NFP耗时1/66s，所有NFP计算时间为1/66×(10×2)2=6.08 s.但如果 RN=32，则计算时间将高达1/66×(10×32)2=1551.52s.

Burke等［8］在母材上布置一排垂线，零件沿线移动寻找最优旋转角使零件“包围盒”宽度最小.Dowsland等［9］指出:如将零件看作砂砾，母材看作玻璃瓶，不断摇晃“玻璃瓶”可使“砂砾”排列更紧密.这说明重力在排样中起到了重要作用.Lee等［10］在母材上布置多个排样点，在各点对零件进行旋转以找到最优排样姿态使零……