问题介绍

排样下料是诸多制造行业的首道工序，也是关键工序。下料利用率的提高能够帮助企业节约原材料成本，提高企业的利润，从而提升企业的核心竞争力，此外，原材料的充分利用符合绿色制造的理念。根据所需切割零件的形状，下料问题可以分为矩形排样和异形排样。异形排样的应用场景广泛，如制衣行业、制鞋行业、钣金行业、造船行业以及家具行业等。根据原材料的形状，异形排样又可分为卷型材异形排样和板材异形排样。

1. 卷型材异形排样

卷型材异形排样主要出现在皮革、纸张（图1）、布匹（图2）等行业，由于原材料本身的特性，该问题假定原材料宽度固定，长度可变，问题目标是从原材料中切割出所需的异形零件并最小化使用长度。

图1.皮革切割

图2. 2019广东工业智造创新大赛（赛场二：面料剪裁利用率优化）案例

2. 板材异形排样

板材异形排样主要出现在家具（图3）、钣金（图4）等行业，该问题中假定原材料长、宽固定，问题目标是使用最少数量的原材料切割出所需异形零件。为了进一步节约成本，在最小化板材数量的同时，一般要求最大化最后一块板的剩余面积以便后续使用。钣金行业，由于异形零件存在孔洞，导致零件可以嵌套摆放，从而增加了问题的复杂性。

图3. 板材排样

图4. 钣金排样

几何工具

二维异形排样问题的求解难点在于如何避免零件与零件之间发生重叠，即使用合适的几何工具检测重叠。

在解决二维异形排样问题的早期，受到计算机性能的限制，同时考虑到异形零件的复杂性，学者们通过将异形零件转化成对应的包络矩形，将二维异形排样问题简化成了二维矩形排样问题，降低了问题的复杂度，但随之而来的则是在零件的包络矩形本身利用率较低的时候，排样结果必定很差。

图5. 包络矩形

如今，在二维异形排样领域，常用的几何工具通常是临界多边形法和像素法。

像素法是指将异形零件转化成多个像素点或扫描线，将异形零件的重叠检测简化成不同零件的像素点或扫描线之间的重叠检测。

扫描线算法是计算机图形学中的一个经典算法，扫描线储存的数据结构较为单一，通常是零件内部线段的两个端点。

像素点法的数据结构更为多样，1986年Segenreich 和 Braga发表的论文[8]中，将零件内部的点设值为3，零件边上的点设值为1，空白则为0，而1993年Oliveira 和 Ferreira 在论文[7]中直接用1表示非空白的点。2001年Babu 发表的论文[5]则反其道而行之，将非空白的点设为0，边界之外或边界上的则为大于0的值，该值从右向左逐渐累加，当需要零件向右移动时可以动态地调整步长。

像素法初始化和重叠检测的思路很简单，但由于异形零件通常是由浮点数坐标组成，将其按照一定精度转化时通常会有精度损失，同时也较难利用一些常见的几何规则如切线法线等，在实现上，像素法的求解策略也较为单一。

图6. 像素点法

临界多边形的思想最早是在Art的论文[2]中提出来，但它使用了envelope这一术语，在1976年Albano[1]正式提出了not fit polygon即NFP这一概念。临界多边形法是指在异形零件B上选择一个参考点，将异形零件B在另一个异形零件A上环绕一周后，根据参考点的轨迹生成一个多边形，在判断B是否与A重叠时，仅需要判断零件B上的参考点是否位于生成的多边形内部即可。临界多边形的生成并不需要另外写程序，国外有专门的程序可以调用。由于临界多边形的有效性，临界多边形在近些年的在学术上的使用相当广泛。

图7. 临界多边形

在学术上，一部分学者利用临界多边形搜索可行解，即对一个异形零件序列进行解码，零件的放置规则和放置顺序对解的质量有决定性作用。另外一部分学者的做法是，基于重叠移除，通过不断地压缩面板，移动异形零件在面板上的摆放搜索更好的解。相较于按照序列搜索可行解的方法，重叠移除更好地利用了临界多边形这一几何工具的性质，扩大了解空间，使得算法更有机会获得更优秀的解。

临界多边形的缺点也很明显，不仅很难适应于非凸或带空洞的零件，还由于临界多边形的生成是一对对地生成，当异形零件的种类和允许旋转次数上涨时，为了获得更优解，临界多边形生成的调用呈指数级增长，同时异形零件的顶点数量过多也会增加临界多边形的初始化时间。

常用算法

排样算法通常使用启发式或元启发式算法进行求解，精确算法仅能为一些小例子或者带有特殊特征的例子找到最优解，Toledo, Carravilla, Ribeiro, Oliveira, 和 Gomes在2013年发表的论文[5]虽然对较大的实例进行了优化，但依然存在一些限制，同时大部分精确算法不考虑旋转，结果将会受到很大约束。

启发式算法的运用通常可以分为序列搜索算法和重叠移除算法。

序列搜索算法常见的有左底法，即按照从左往右，从下往上的顺序搜索零件的放置点。序列搜索算法的关键在于确定放置顺序，常见的做法是采用遗传算法等元启发式策略搜索一个能使利用率最高的放置顺序，同时如Burke, Hellier, Kendall 和 Whitwell在2006年发表的论文[4]中通过离散化水平搜索修改了左底法，并应用了爬山禁忌搜索。

图8. 序列搜索算法

重叠移除算法通常采用了重叠移除和压缩的方法，如在卷型材异形排样，通过序列搜索算法得到一个可行解后，迭代减少面板的长度，实现压缩；压缩的同时将导致零件超出面板或发生重叠，此时采用重叠移除的方法，移动零件得到新的可行解。由于进行布局搜索时几何约束即重叠约束过强，通常定义一个重叠函数松弛几何约束，如Imamichi, Yagiura, 和 Nagamochi 在2009年发表的论文[6]中提出采用一个非线性规划模型，该模型可以同时对所有零件产生作用。

图9. 重叠移除算法

由于重叠移除算法的有效性，如今常见的算法结构都是采用一个简单的序列搜索算法生成一个初始解，通过迭代依次执行分离和压缩算法，并采用各种元启发式策略跳出局部最优。

「参考文献」

[1] Adamowicz M, Albano A. Nesting two dimensional shapes in rectangular modules. Computer Aided Design 1976;8(1):27-33.

[2] Art, Richard Carl, Jr. An approach to the two dimensional irregular cutting stock problem [J]. 1966.

[3] Babu, A.R., Babu, N.R., 2001. A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Computer-Aided Design 33, 879–891.

[4] Edmund Burke, Robert Hellier, Graham Kendall, Glenn Whitwell. A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem[J]. Operations Research, 2006, 54(3).

[5] Franklina M.B. Toledo,Maria Antónia Carravilla,Cristina Ribeiro,José F. Oliveira,A. Miguel Gomes. The Dotted-Board Model: A new MIP model for nesting irregular shapes[J]. International Journal of Production Economics, 2013, 145(2).

[6] Imamichi T, Vagiura M, Nagamochi H. An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem[D]. Technical Report 2007-009, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, 2007.

[7] Oliveira, J. F., Ferreira, J.S., 1993. Algorithms for nesting problems, Applied Simulated Annealing. In: Vidal, R. V. V. (Ed.), Lecture Notes in Econ. and Maths Systems, Vol. 396. Springer Verlag, pp. 255–274.

[8] Segenreich, S.A., Braga, L. M., 1986. Optimal nesting of general plane figures: a Monte Carlo heuristical approach. Computers & Graphics 10, 229–237.

[9] 崔耀东.不规则冲裁件单一下料计算机优化排样[J].航天工艺,1995(06):46-48