基于集束搜索的二維矩形排樣問題求解算法

摘 要：降低成本、提高材料利用率是生產商提高收益的重要方式，所以如何將板材切割出更多有效目標板件是一個值得探討的問題。為了得到更高效的二維矩形排樣算法，通過以貼邊度為放置動作判斷核心，并以集束搜索的方式進行搜索求解。實驗使用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.

（責任編輯：江 艷）