基于集束搜索的二维矩形排样问题求解算法

摘 要：降低成本、提高材料利用率是生产商提高收益的重要方式，所以如何将板材切割出更多有效目标板件是一个值得探讨的问题。为了得到更高效的二维矩形排样算法，通过以贴边度为放置动作判断核心，并以集束搜索的方式进行搜索求解。实验使用packing问题常用的C21算例组进行演算，并与基本算法、GRASP算法和TABU算法进行对比。这3种基本算法平均利用率为97.39%、98.50%、99.53%，而使用集束搜索策略后平均利用率上升到了99.80%。整体利用率比基本算法平均利用率上涨2.41%，比GRASP算法平均利用率上涨1.3%，比TABU算法平均利用率上涨0.27%。基本算法在使用集束搜索策略后，反超GRASP算法和TABU算法，使平均利用率進一步提升。

关键词：NP难度；Packing问题；集束搜索

DOI：10. 11907/rjdk. 191280

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2019）005-0084-05

Abstract：It is an important way for producers to reduce cost and improve material utilization rate to increase profit. Therefore， how to cut out more effective target plates is a question worth discussion. In order to obtain a more efficient two-dimensional rectangular layout algorithm， the paper designs a method to search and solve the problem by taking the welt as the core of placement action judgment and using the method of cluster search. In the experiment， C21 example set commonly used in packing problem was used for calculation， and it was compared with the basic algorithm， GRASP algorithm and TABU algorithm. The average utilization rate of the 3 algorithm are 97.39%， 98.50% and 99.53%. Overall utilization rate is 2.41% higher compared with the average utilization rate of basic algorithm， 1.3% compared with the average utilization rate of GRASP algorithm， and 0.27% compared with the average utilization rate of TABU algorithm. After using the cluster search strategy， the average utilization ratio of the basic algorithm has been improved， and the GRASP algorithm and TABU algorithm have been surpassed.

Key Words： Np-hardness； Packing problem； cluster search

0 引言

二维矩形Packing问题指在二维空间中，有一已知长宽的矩形框和有限个已知长宽的目标矩形，现需将这些目标矩形尽可能多地填放入已知长宽的矩形框中，但目标矩形在框内不可有重叠，且目标矩形之间没有先后顺序[1]。

二维矩形排样问题也可看为矩形件切割问题，但前者将目标矩形填充到固定长宽的方框中，后者则反过来，将固定长宽的板材切割出多个目标矩形。两者本质相同，都是为了找出最优解，减少浪费，且互为对方的逆过程。排样问题最早由俄国经济学家家 Kantorovich[2]提出，随后由Gilmore & Gormory[3-4]两位学者在20世纪70年代提出以线性规划法解决在一维和二维上的排样问题。但当时由于计算机水平有限，并没有产生较大影响。直到80年代，计算机技术开始蓬勃发展，数学规划法才得到重视。在此期间Farley等[5]提出动态规划方法、Beasley[6]提出整数规划方法、Manevich 等[7]提出整数线性规划方法。

二维矩形Packing问题自1971年被提出，成为计算机科学领域中未被解决的典型NP难度问题之一。近年来国内外学者提出多种高效算法，大致可分为非随机型和随机型近似算法。非随机型近似算法侧重于先选择放置动作的优先级，然后在其基础上进行部分枚举，包括底部左齐择优匹配算法[8]、分支限界[9]、拟人算法[10]；随机型近似算法混杂使用各种放置策略，并伴随一定随机化处理，其中包括遗传算法[11]、粒子群算法[12]，随机进行局部搜索[13]。

众多学者尝试使用混合算法突破该问题。Alvarez-Valdes等[14]在随机搜索的基础上进行算法改进，设计出GRASP算法，算法提出了分阶段的思想，含有构建和改进两个阶段，在改进阶段的实验结果有相应提高；Silva[15]提出一种由基本算法和智能优化算法结合的三维重叠混合分组遗传算法；Andrade[16]基于对剩余空间的利用理念，提出非精确两阶段剩余排样的双层整数规划模型；Juan Carlos Gomez[17]提出一种使用特定遗传算子组成可变长度的规则集解决二维装箱问题的超启发式算法。

本文先设计以贴边度为重要选择指标的基本算法，然后在基本算法的基础上，进行局部回溯处理，让算法可以预见更多分支选项，从而得到更好的近似最优解。

1 基本算法

基本算法是一种非随机型近似算法，通过制定的指标每次选择当前格局下最好的目标矩形并放入矩形框内，期间没有随机参数干预算法结果，直到所有目标方块全部放入矩形框内，或矩形框内没有剩余空间继续放入目标方块才停止算法。

1.1 算法定义

算法进行相关定义如下：

定义1：格局，矩形框内已放置的目标矩形和框外还未放置的目标矩形统称为一个格局。所以，初始格局是一个矩形框，框内没有放置任何目标矩形，所有目标矩形均在框外。终止格局是所有目标矩形都已放置在矩形框内或矩形框内没有剩余空间继续放置任何目标矩形。

定义2：放置动作，将一个目标矩形放入矩形框内，该过程称为一个动作，所以相对试放动作是选择一个目标矩形进行试放，但最终该目标矩形没有放入矩形框内，仅为试放。放置时用目标矩形的一个顶角填充格局中矩形框内的一个角区，以避免目标矩形放入后没有与其它任意边贴靠。放置动作时应保证放置的目标矩形不超出矩形框边界，且不与已放置在框内的目标矩形重叠。

定义3 ：角区，在矩形框内由90°角延伸的空白区域。角区一共有3种类型：矩形框边界构成的90°区域，即矩形框的4个90°角；矩形框边界和框内目标矩形边构成的90°角区域；两个框内目标矩形的边构成的90°角。具体例子如图1角区示例所示，图中角区1是第1种类型，角区2是第2种类型，角区3是第3种类型。

定义4：动作空间，是一个自定义的虚拟矩形块，该矩形块在矩形框空白区域内，只要满足其上、下、左、右都与其它已放入的目标矩形或矩形框重合，则称该虚拟矩形块为一个动作空间。所有放置动作的目的是将目标矩形填充于动作空间中的某个角落，且动作空间某个顶角必然与当前格局下某个角区重合。

定义5：贴边度，当前格局下将待放入的目标矩形的边与已放入矩形框的目标矩形的边或矩形框四边重合的边数。如图2贴边度示例所示，左图中目标矩形1的贴边度为2，右图中目标矩形2的贴边度为3。贴边度取值范围是{0、1、2、3、4}。

贴边度是基本算法的重要判断指标，贴边数越大越优先。贴边数最大时即意味着该目标矩形可完美填充矩形框内的某个空白。其它辅助判断指标有矩形块面积越大越优先，当前格局下角区数越少越优先，其比较先后顺序是贴边度>角区数>目标矩形面积。最优先比较贴边度，越大越优先；当贴边度相同时比较当前格局下放入目标矩形后的角区数；若角区数也相同时则比较放置的目标矩形面积大小。

1.2 算法步骤

基本算法步骤包括通过判断指标进行放置动作的选择，选择后直接放置，没有回溯、试放环节。其具体步骤为：①导入数据，进行相關数据初始化，并构建初始格局；②根据选择指标先后顺序和判断标准选择并完成放置动作；③更新相关数据，更新动作空间进入新格局；④重复前3项步骤，直到所有目标矩形全部放入矩形框内或矩形框内没有剩余空间可放置矩形框外任何目标矩形，结束算法。

该算法由于步骤简单且没有分支，可迅速得到排版结果，但计算出的排版结果受目标矩形样式影响。若所有目标矩形之间差距越小，最终排版利用率越大、结果越好；若目标矩形之间差距越大，最终排版利用率越小、结果越差。受目标矩形样式影响是无回溯算法的弊端，其算法流程如图3所示。

算法每次选取当前格局下制定指标最好的放置动作进行试放，直至放置结束。基本算法运行路线是一条直线，每个格局下均从所有放置动作中选取一个进行放置，期间没有任何回退步骤。动作空间更新则是按照胡文蓓等[18]学者提出的的方法进行相关操作。

1.3 基本算法结果

选择C21算例作为算法计算用例，这是packing问题常用的一组基本用例。C21相对于packing问题的其它组用例来说较为简单，用例中小矩形的个数不多，最少为10个，最多为196个。

该组用例包含21个实例，每一个实例由一个大矩形长宽参数、多个小矩形长宽参数和小矩形个数3部分组成。C21算例的每个实例均存在最优解，即每个实例所有小矩形均可将大矩形刚好填充完，使利用率达到100%。基本算法对C21算例实验结果如表1所示。

由表1可看出，基本算法运行时间很短，但21个例子中没有一个达到100%的利用率，由此可看出基本算法还是存在一些弊端。不过，21个例子的平均利用率达到96%以上，所以放置动作的选择指标效率较高，在实验中的结果也比较理想。

2 集束搜索算法

在基本算法的基础上，添加集束搜索策略。在一定程度上必然会增加算法运算时间，但运行过程中会带给算法更多选择空间，因此需综合评估算法最终表现。

算法中的定义与基本算法相同。放置动作的选择指标大致遵循“贴边度>角区数>目标矩形面积”的准则，但有一些差别，算法不再是一条直线走到底，而是在当前格局下将所有可放置动作进行试放，试放后根据选择指标进行排序，选择前10个试放动作，继续进行试放，此时采取基本算法试放到最终格局。计算此时10个最终格局的利用率，选取最大利用率对应的最初试放动作，对该试放动作进行放置，进入新格局。

由以上步骤可选出当前格局下，执行哪个放置动作会有更好的未来趋势，其算法示例如图4所示。

如图4所示，每一次放置动作是试放时利用率最优的候选动作。一直重复该操作，直到所有目标矩形放完为止。若有某个试放的终止格局利用率也达到100%，则可直接结束算法，将该试放路径的过程全部作为试放动作进行处理。

使用C21算例组进行集束搜索算法试验。实验结果如表2所示。

从表2的实验结果可知，使用集束搜索算法进行分支计算后，计算结果全面超过基本算法，其中还有半数取得最优解，但也出现了NP难度问题的常见现象，在取得最优解的同时，随着目标方块数量的增加，算法运算时间也显著增加。

将实验结果与Alvarez-Valdes [19]提出的GRASP算法、TABU算法[20]进行对比。对比结果如表3、表4所示。

从上述两表的实验对比可知，使用基本算法通过集束搜索策略的改进后，反超GRASP算法和TABU算法的实验结果。基本算法平均利用率为97.39%，GRASP算法平均利用率为98.50%，TABU算法平均利用率为99.53%，使用集束搜索策略后平均利用率上升到99.80%。整体利用率比基本算法平均利用率上升2.41%，比GRASP算法平均利用率上升了1.3%，比TABU算法平均利用率上升了0.27%。

3 结语

本文在基本算法的基础上对集束搜索策略进行改进。基础算法根据放置动作的选择指标可以达到一个较理想的排版结果，一方面由于制定的指标策略很高效，另一方面由于C21算例组在Packing问题中并不是难度较大的算例组，目标矩形个数均在200以内，相比于其它目标矩形差异较大，与数量更多的算例组相比，该组算例较普通。在使用集束搜索策略后，可明显看到相较于基本算法，排版结果利用率明显更高，但其运行时间也越来越长。本文采用非随机型近似算法，算法中没有随机数对运算结果造成影响，但根据结果来看，可以再增加一些随机选项，可能可得到更好的排版结果。例如本文集束搜索宽度为10，但随着目标矩形之间差异增大，数量增多，该宽度设定可能不再合适，搜索宽度参数取值或与目标矩形长宽和个数存在着某种数量关系，能够得到更好的排版结果，所以下一步实验方向是寻找该数量关系是否存在。

参考文献：

[1] 王磊，尹爱华. 求解二维矩形Packing问题的一种优美度枚举算法[J]. 中国科学；信息科学，2015，45（9）：1127-1140.

[2] KANTOROVICH L V. Mathematical method of organizing and planning production [J]. Management Science， 1960， 6（4）： 366-422.

[3] GILMORE P C， GOMORY R E. A linear programming approach to the cutting stock problem[J]. Opeartions Research， 1961， 9（5）： 849-859.

[4] GILMORE P C， GOMORY R. E. A linear programming approach to the cutting stock problem-part Ⅱ[J]. Opeartions Research， 1963， 11（5）： 863-888.

[5] FARLEY A A. Mathematical programming models for cutting-stock problems in the clothing industry[J]. Journal of the Operational Research Society， 1988， 39（1）： 41-53.

[6] BEASLEY J E. Algorithms for unconstrained two-dimensional guillotine cutting[J]. Journal of the Operational Research Society， 1985，36（4）： 297-306.

[7] SHPITALNI M， MANEVICH V. Optimal orthogonal subdivision of rectangular sheets[J]. Journal of Manufacturing Science and Engineering，1996， 118（3）： 281-288.

[8] 蔣兴波，吕肖庆，刘成城. 二维矩形条带装箱问题的底部左齐择优匹配算法[J]. 软件学报，2009，20：1528-1538.

[9] CUI Y D，YANG Y L，CHENG X，et al. A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J]. Computer and Operations Research，2008，35： 1281-1291.

[10] HUANG W Q， CHEN D B， XU R C. A new heuristic algorithm for rectangle packing[J]. Computer and Operations Research， 2007， 34： 3270-3280.

[11] BORTFELDT A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces[J]. European Journal of Operational Research， 2006， 172： 814-837.

[12] JIANG J Q， LIANG Y C， SHI X H， et al. A hybrid algorithm based on PSO and SA and its application for two-dimensional non-guillotine cutting stock problem[J]. Lecture Notes of Computer Science， 2004， 3007： 666-669.

[13] ZHANG D F， WEI L J， LEUNG S C H， et al. A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem[J]. Informs Journal on Computing， 2013， 25： 332-345.

[14] ALVAREZ-VALDES R， PARRENO F， TAMARIT J M. Reactive GRASP for the strip-packing problem[J]. Computers & Operations Research， 2008， 35（4）： 1065-1083.

[15] SILVA E， ALVELOS F， CARVALHO J M V. Integrating two-dimensional cutting stock and lot-sizing problems[J]. Journal of the Operational Research Society， 2013， 65（1）： 108-123.

[16] ANDRADE R， BIRGIN E G， MORABITO R. Two-stage two-dimensional guillotine cutting stock problems with usable leftover[J]. International Transactions in Operational Research，2016，23： 121-145.

[17] GOMEZ J C，TERASHIMA-MARIN H. Evolutionary hyper-heuristics for tackling bi-objective 2D bin packing problems [J]. Genet Program Evolvable Mach，2018，19：151-181.

[18] 胡文蓓，饶昊. 二维Packing问題拟人型算法中的放置空间更新过程求解[J]. 软件导刊，2017，16（8）： 19-20.

[19] ALVAREZ-VALDES R， PARRE？O F， TAMARIT J M. A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems[J]. Journal of Operational Research Society， 2005， 56（4）： 414-425.

[20] ALVAREZ-VALDES R，PARRE？O F，TAMARIT J M. A TABU search algorithm for two-dimensional non-guillotine cutting problems[J]. European Journal of Operational Research，2007，183（3）： 1167-1182.

（责任编辑：江 艳）