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

摘 要：降低成本、提高材料利用率是生產(chǎn)商提高收益的重要方式，所以如何將板材切割出更多有效目標板件是一個值得探討的問題。為了得到更高效的二維矩形排樣算法，通過以貼邊度為放置動作判斷核心，并以集束搜索的方式進行搜索求解。實驗使用packing問題常用的C21算例組進行演算，并與基本算法、GRASP算法和TABU算法進行對比。這3種基本算法平均利用率為97.39%、98.50%、99.53%，而使用集束搜索策略后平均利用率上升到了99.80%。整體利用率比基本算法平均利用率上漲2.41%，比GRASP算法平均利用率上漲1.3%，比TABU算法平均利用率上漲0.27%?；舅惴ㄔ谑褂眉阉鞑呗院螅闯珿RASP算法和TABU算法，使平均利用率進一步提升。

關(guān)鍵詞：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問題指在二維空間中，有一已知長寬的矩形框和有限個已知長寬的目標矩形，現(xiàn)需將這些目標矩形盡可能多地填放入已知長寬的矩形框中，但目標矩形在框內(nèi)不可有重疊，且目標矩形之間沒有先后順序[1]。

二維矩形排樣問題也可看為矩形件切割問題，但前者將目標矩形填充到固定長寬的方框中，后者則反過來，將固定長寬的板材切割出多個目標矩形。兩者本質(zhì)相同，都是為了找出最優(yōu)解，減少浪費，且互為對方的逆過程。排樣問題最早由俄國經(jīng)濟學家家 Kantorovich[2]提出，隨后由Gilmore & Gormory[3-4]兩位學者在20世紀70年代提出以線性規(guī)劃法解決在一維和二維上的排樣問題。但當時由于計算機水平有限，并沒有產(chǎn)生較大影響。直到80年代，計算機技術(shù)開始蓬勃發(fā)展，數(shù)學規(guī)劃法才得到重視。在此期間Farley等[5]提出動態(tài)規(guī)劃方法、Beasley[6]提出整數(shù)規(guī)劃方法、Manevich 等[7]提出整數(shù)線性規(guī)劃方法。

二維矩形Packing問題自1971年被提出，成為計算機科學領(lǐng)域中未被解決的典型NP難度問題之一。近年來國內(nèi)外學者提出多種高效算法，大致可分為非隨機型和隨機型近似算法。非隨機型近似算法側(cè)重于先選擇放置動作的優(yōu)先級，然后在其基礎(chǔ)上進行部分枚舉，包括底部左齊擇優(yōu)匹配算法[8]、分支限界[9]、擬人算法[10]；隨機型近似算法混雜使用各種放置策略，并伴隨一定隨機化處理，其中包括遺傳算法[11]、粒子群算法[12]，隨機進行局部搜索[13]。

眾多學者嘗試使用混合算法突破該問題。Alvarez-Valdes等[14]在隨機搜索的基礎(chǔ)上進行算法改進，設(shè)計出GRASP算法，算法提出了分階段的思想，含有構(gòu)建和改進兩個階段，在改進階段的實驗結(jié)果有相應(yīng)提高；Silva[15]提出一種由基本算法和智能優(yōu)化算法結(jié)合的三維重疊混合分組遺傳算法；Andrade[16]基于對剩余空間的利用理念，提出非精確兩階段剩余排樣的雙層整數(shù)規(guī)劃模型；Juan Carlos Gomez[17]提出一種使用特定遺傳算子組成可變長度的規(guī)則集解決二維裝箱問題的超啟發(fā)式算法。

本文先設(shè)計以貼邊度為重要選擇指標的基本算法，然后在基本算法的基礎(chǔ)上，進行局部回溯處理，讓算法可以預(yù)見更多分支選項，從而得到更好的近似最優(yōu)解。

1 基本算法

基本算法是一種非隨機型近似算法，通過制定的指標每次選擇當前格局下最好的目標矩形并放入矩形框內(nèi)，期間沒有隨機參數(shù)干預(yù)算法結(jié)果，直到所有目標方塊全部放入矩形框內(nèi)，或矩形框內(nèi)沒有剩余空間繼續(xù)放入目標方塊才停止算法。

1.1 算法定義

算法進行相關(guān)定義如下：

定義1：格局，矩形框內(nèi)已放置的目標矩形和框外還未放置的目標矩形統(tǒng)稱為一個格局。所以，初始格局是一個矩形框，框內(nèi)沒有放置任何目標矩形，所有目標矩形均在框外。終止格局是所有目標矩形都已放置在矩形框內(nèi)或矩形框內(nèi)沒有剩余空間繼續(xù)放置任何目標矩形。

定義2：放置動作，將一個目標矩形放入矩形框內(nèi)，該過程稱為一個動作，所以相對試放動作是選擇一個目標矩形進行試放，但最終該目標矩形沒有放入矩形框內(nèi)，僅為試放。放置時用目標矩形的一個頂角填充格局中矩形框內(nèi)的一個角區(qū)，以避免目標矩形放入后沒有與其它任意邊貼靠。放置動作時應(yīng)保證放置的目標矩形不超出矩形框邊界，且不與已放置在框內(nèi)的目標矩形重疊。

定義3 ：角區(qū)，在矩形框內(nèi)由90°角延伸的空白區(qū)域。角區(qū)一共有3種類型：矩形框邊界構(gòu)成的90°區(qū)域，即矩形框的4個90°角；矩形框邊界和框內(nèi)目標矩形邊構(gòu)成的90°角區(qū)域；兩個框內(nèi)目標矩形的邊構(gòu)成的90°角。具體例子如圖1角區(qū)示例所示，圖中角區(qū)1是第1種類型，角區(qū)2是第2種類型，角區(qū)3是第3種類型。

定義4：動作空間，是一個自定義的虛擬矩形塊，該矩形塊在矩形框空白區(qū)域內(nèi)，只要滿足其上、下、左、右都與其它已放入的目標矩形或矩形框重合，則稱該虛擬矩形塊為一個動作空間。所有放置動作的目的是將目標矩形填充于動作空間中的某個角落，且動作空間某個頂角必然與當前格局下某個角區(qū)重合。

定義5：貼邊度，當前格局下將待放入的目標矩形的邊與已放入矩形框的目標矩形的邊或矩形框四邊重合的邊數(shù)。如圖2貼邊度示例所示，左圖中目標矩形1的貼邊度為2，右圖中目標矩形2的貼邊度為3。貼邊度取值范圍是{0、1、2、3、4}。

貼邊度是基本算法的重要判斷指標，貼邊數(shù)越大越優(yōu)先。貼邊數(shù)最大時即意味著該目標矩形可完美填充矩形框內(nèi)的某個空白。其它輔助判斷指標有矩形塊面積越大越優(yōu)先，當前格局下角區(qū)數(shù)越少越優(yōu)先，其比較先后順序是貼邊度>角區(qū)數(shù)>目標矩形面積。最優(yōu)先比較貼邊度，越大越優(yōu)先；當貼邊度相同時比較當前格局下放入目標矩形后的角區(qū)數(shù)；若角區(qū)數(shù)也相同時則比較放置的目標矩形面積大小。

1.2 算法步驟

基本算法步驟包括通過判斷指標進行放置動作的選擇，選擇后直接放置，沒有回溯、試放環(huán)節(jié)。其具體步驟為：①導入數(shù)據(jù)，進行相關(guān)數(shù)據(jù)初始化，并構(gòu)建初始格局；②根據(jù)選擇指標先后順序和判斷標準選擇并完成放置動作；③更新相關(guān)數(shù)據(jù)，更新動作空間進入新格局；④重復(fù)前3項步驟，直到所有目標矩形全部放入矩形框內(nèi)或矩形框內(nèi)沒有剩余空間可放置矩形框外任何目標矩形，結(jié)束算法。

該算法由于步驟簡單且沒有分支，可迅速得到排版結(jié)果，但計算出的排版結(jié)果受目標矩形樣式影響。若所有目標矩形之間差距越小，最終排版利用率越大、結(jié)果越好；若目標矩形之間差距越大，最終排版利用率越小、結(jié)果越差。受目標矩形樣式影響是無回溯算法的弊端，其算法流程如圖3所示。

算法每次選取當前格局下制定指標最好的放置動作進行試放，直至放置結(jié)束。基本算法運行路線是一條直線，每個格局下均從所有放置動作中選取一個進行放置，期間沒有任何回退步驟。動作空間更新則是按照胡文蓓等[18]學者提出的的方法進行相關(guān)操作。

1.3 基本算法結(jié)果

選擇C21算例作為算法計算用例，這是packing問題常用的一組基本用例。C21相對于packing問題的其它組用例來說較為簡單，用例中小矩形的個數(shù)不多，最少為10個，最多為196個。

該組用例包含21個實例，每一個實例由一個大矩形長寬參數(shù)、多個小矩形長寬參數(shù)和小矩形個數(shù)3部分組成。C21算例的每個實例均存在最優(yōu)解，即每個實例所有小矩形均可將大矩形剛好填充完，使利用率達到100%?；舅惴▽21算例實驗結(jié)果如表1所示。

由表1可看出，基本算法運行時間很短，但21個例子中沒有一個達到100%的利用率，由此可看出基本算法還是存在一些弊端。不過，21個例子的平均利用率達到96%以上，所以放置動作的選擇指標效率較高，在實驗中的結(jié)果也比較理想。

2 集束搜索算法

在基本算法的基礎(chǔ)上，添加集束搜索策略。在一定程度上必然會增加算法運算時間，但運行過程中會帶給算法更多選擇空間，因此需綜合評估算法最終表現(xiàn)。

算法中的定義與基本算法相同。放置動作的選擇指標大致遵循“貼邊度>角區(qū)數(shù)>目標矩形面積”的準則，但有一些差別，算法不再是一條直線走到底，而是在當前格局下將所有可放置動作進行試放，試放后根據(jù)選擇指標進行排序，選擇前10個試放動作，繼續(xù)進行試放，此時采取基本算法試放到最終格局。計算此時10個最終格局的利用率，選取最大利用率對應(yīng)的最初試放動作，對該試放動作進行放置，進入新格局。

由以上步驟可選出當前格局下，執(zhí)行哪個放置動作會有更好的未來趨勢，其算法示例如圖4所示。

如圖4所示，每一次放置動作是試放時利用率最優(yōu)的候選動作。一直重復(fù)該操作，直到所有目標矩形放完為止。若有某個試放的終止格局利用率也達到100%，則可直接結(jié)束算法，將該試放路徑的過程全部作為試放動作進行處理。

使用C21算例組進行集束搜索算法試驗。實驗結(jié)果如表2所示。

從表2的實驗結(jié)果可知，使用集束搜索算法進行分支計算后，計算結(jié)果全面超過基本算法，其中還有半數(shù)取得最優(yōu)解，但也出現(xiàn)了NP難度問題的常見現(xiàn)象，在取得最優(yōu)解的同時，隨著目標方塊數(shù)量的增加，算法運算時間也顯著增加。

將實驗結(jié)果與Alvarez-Valdes [19]提出的GRASP算法、TABU算法[20]進行對比。對比結(jié)果如表3、表4所示。

從上述兩表的實驗對比可知，使用基本算法通過集束搜索策略的改進后，反超GRASP算法和TABU算法的實驗結(jié)果?；舅惴ㄆ骄寐蕿?7.39%，GRASP算法平均利用率為98.50%，TABU算法平均利用率為99.53%，使用集束搜索策略后平均利用率上升到99.80%。整體利用率比基本算法平均利用率上升2.41%，比GRASP算法平均利用率上升了1.3%，比TABU算法平均利用率上升了0.27%。

3 結(jié)語

本文在基本算法的基礎(chǔ)上對集束搜索策略進行改進。基礎(chǔ)算法根據(jù)放置動作的選擇指標可以達到一個較理想的排版結(jié)果，一方面由于制定的指標策略很高效，另一方面由于C21算例組在Packing問題中并不是難度較大的算例組，目標矩形個數(shù)均在200以內(nèi)，相比于其它目標矩形差異較大，與數(shù)量更多的算例組相比，該組算例較普通。在使用集束搜索策略后，可明顯看到相較于基本算法，排版結(jié)果利用率明顯更高，但其運行時間也越來越長。本文采用非隨機型近似算法，算法中沒有隨機數(shù)對運算結(jié)果造成影響，但根據(jù)結(jié)果來看，可以再增加一些隨機選項，可能可得到更好的排版結(jié)果。例如本文集束搜索寬度為10，但隨著目標矩形之間差異增大，數(shù)量增多，該寬度設(shè)定可能不再合適，搜索寬度參數(shù)取值或與目標矩形長寬和個數(shù)存在著某種數(shù)量關(guān)系，能夠得到更好的排版結(jié)果，所以下一步實驗方向是尋找該數(shù)量關(guān)系是否存在。

參考文獻：

[1] 王磊，尹愛華. 求解二維矩形Packing問題的一種優(yōu)美度枚舉算法[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] 蔣興波，呂肖慶，劉成城. 二維矩形條帶裝箱問題的底部左齊擇優(yōu)匹配算法[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.

（責任編輯：江 艷）