背景

下料问题（CuttingStockProblem）是把固定形状的一种或多种（少量）材料切分加工为若干（多种）不同大小规格的零件的问题。下料问题广泛存在于制造业中，尤其是其中的生产加工工艺流程，大到机加工的零件切分、航空复合材料的切分、造船业的板类剪裁，小到家装家具木料剪裁、服装布料剪裁、铝制门窗的材料切割、金属管道的切割等等。

制造业中，压缩成本，提高利润率一直是一个永恒课题，而在下料场景中，如何最大化利用原材料，提高材料利用率，减少废品率在该课题下显得尤为重要。研究下料问题，设计一套完备的下料引擎，不仅可以提高生产中材料利用率，还可以极大程度降低材料管理的人力成本，提高管理效率。

下料问题按原材料和零件的维度，可以分为一维、二维和三维下料问题。其中一维下料问题指原材料是柱形或棒形材料的下料，二维下料问题主要指板型材料的下料，三维下料问题指材料在长宽高均有要求的下料。雪浪云下料引擎对3种下料场景均有完整的解决方案，未来也会针对每种算法进行专门的讲述。

下料问题中，二维下料问题最为常见。这里根据切分后物体的形状，又可分为矩形二维下料和异形二维下料，本文则重点介绍在矩形二维下料的算法和实际应用。

算法介绍和对比

二维矩形材料的下料剪裁问题指的是如何在标准板上规划并且剪裁一定数量的不同长宽的零件，并同时最小化标准板的使用数量来节约生产成本的切割问题。这个问题在很多材料加工的行业中都是很关键的一个步骤。在零件数量和种类相对较少的情况下，人工排版基本上能在较短的时间内排出合理的剪裁方案。但是当订单数量增多，合单后的零件数量较多的情况下，人工排版就会显得相对低效。而二维下料剪裁算法，则可以根据用户需求，在极短的时间内完成对大订单的零件排版，同时将材料的损耗降到最低。

而在二维下料剪裁算法中，又分断头台算法（Guillotine）和非断头台算法（Maximal-Rectangle）。两者的区别从结果上看，前者的排版在每次被切割的时候，都能找到横向或者纵向一刀切的位置，这在很多行业（航空、建筑等）的材料加工中都是非常常见的；后者的排版则不具备这个属性，这种方法相对而言会比前者增加板材的利用率，但是同时对加工设备的要求也更高（需要能随时转向的切割工具）。

图1a）

图1b）

图1a）和1b）为断头台算法在10x6的标准板上的排版

图2非断头台算法在同样的标准板上对同一批零件进行的排版

可以看到的是，非断头算法将所有零件都排在了一块标准板上而断头台算法因为要满足横纵一刀的切割模式，无法将零件统一排在一块标准板上。下文将讲述两种算法所使用的一些启发函数，以及两者在排版过程中最大的不同。

步骤1：整理输入的零件参数（长、宽），并将其按排序规则排序（面积降序、最长边降序、最短边降序等）并确定板材规格（长、宽）

步骤2.1：将零件依据排好的顺序从从可用板材中选出最适合该零件放入的板材，并将该零件从该板材的最左下角置入

步骤2.2-a（断头台算法）：每当一个板材中被置入一个零件，剩下的空间则会根据一定分裂规则分裂成两个小材料。如图3所示原来的R1在置入了P1以后，剩余的空间在R1的较短边方向截成了R2与R3，所生成的新R2与R3则成了新的可用板材。

步骤2.2-b（非断头台算法）：相较于2.2-a，在非断头台算法中，这个步骤在进行对剩余面积的分裂的过程中，不会将R1拆分成独立的R2与R3，而是生成两个拥有交叉面积的R2与R3（如下图）并放入可用板材列表中，这部分的区别就是造成断头台和非断头台之间的主要差异的原因（下面会有一个案例分析简介）。

步骤3：当某零件无法放入剩余的所有可用板材时（包括之前分裂出来的类似R2与R3板材），将零件放入一个全新的板材；并重复步骤2-3直到所有零件都已经被排入板材中。

下图概括了整个算法的流程：

断头台与非断头台算法的案例解析：

由上图可见，在断头台算法的限制下，P5无法放入原来所有的任何材料内（标红），而非断头算法则正好有一个足够的空间可以容下P5。

总结

二维矩形下料，在实际生产中非常常见，且下料方案的优劣直接影响对原材料的利用率，因此大部分企业会增派专门人手甚至部门，设计最优的下料方案。当订单量和订单复杂度非常高时，人工排料的质量和速度则无法保证，该情况下，人力很难在短时间内快速生成非常优秀的下料方案。设计一套完整高可用的下料算法引擎，有三方面的意义：

提高原材料利用率，最大程度降低废料率减少人力成本，无需花费大量人力和精力用于计算最优排料方案方便生产管理，采用该系统辅助优化，能够与生产或业务系统对接，及时了解和管理生产进度，跟踪原料的使用情况目前，雪浪云下料系统已经成功应用在家具行业木料剪裁，服装行业布料剪裁，和一些大型制造业的材料切割系统中。在各种规模的场景下，均能够快速得到可执行程度高的下料切割方案，大大提高了原材料利用率。

同时，在一些特殊复杂加工场景（如立体物体的热处理、喷漆等），雪浪云运筹学团队将下料算法、复杂排产算法、产销量预估等多种技术结合，辅助企业完成全链路生产优化。

目前，雪浪云的下料引擎基础版已发布，旨在帮助用户在下料场景中，能够以极低的成本快速完成精准下料方案。雪浪云将秉承普惠机器智能理念，为企业输出越来越多廉价、可用的智能解决方案，帮助企业完成工业智能化升级。