基于集束搜索的二維矩形排樣問(wèn)題求解算法

摘 要：降低成本、提高材料利用率是生產(chǎn)商提高收益的重要方式，所以如何將板材切割出更多有效目標(biāo)板件是一個(gè)值得探討的問(wèn)題。為了得到更高效的二維矩形排樣算法，通過(guò)以貼邊度為放置動(dòng)作判斷核心，并以集束搜索的方式進(jìn)行搜索求解。實(shí)驗(yàn)使用packing問(wèn)題常用的C21算例組進(jìn)行演算，并與基本算法、GRASP算法和TABU算法進(jìn)行對(duì)比。這3種基本算法平均利用率為97.39%、98.50%、99.53%，而使用集束搜索策略后平均利用率上升到了99.80%。整體利用率比基本算法平均利用率上漲2.41%，比GRASP算法平均利用率上漲1.3%，比TABU算法平均利用率上漲0.27%。基本算法在使用集束搜索策略后，反超GRASP算法和TABU算法，使平均利用率進(jìn)一步提升。

關(guān)鍵詞：NP難度；Packing問(wèn)題；集束搜索

DOI：10. 11907/rjdk. 191280

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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問(wèn)題指在二維空間中，有一已知長(zhǎng)寬的矩形框和有限個(gè)已知長(zhǎng)寬的目標(biāo)矩形，現(xiàn)需將這些目標(biāo)矩形盡可能多地填放入已知長(zhǎng)寬的矩形框中，但目標(biāo)矩形在框內(nèi)不可有重疊，且目標(biāo)矩形之間沒(méi)有先后順序[1]。

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

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

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

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

1 基本算法

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

1.1 算法定義

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

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

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

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

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

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

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

1.2 算法步驟

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

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

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

1.3 基本算法結(jié)果

選擇C21算例作為算法計(jì)算用例，這是packing問(wèn)題常用的一組基本用例。C21相對(duì)于packing問(wèn)題的其它組用例來(lái)說(shuō)較為簡(jiǎn)單，用例中小矩形的個(gè)數(shù)不多，最少為10個(gè)，最多為196個(gè)。

該組用例包含21個(gè)實(shí)例，每一個(gè)實(shí)例由一個(gè)大矩形長(zhǎng)寬參數(shù)、多個(gè)小矩形長(zhǎng)寬參數(shù)和小矩形個(gè)數(shù)3部分組成。C21算例的每個(gè)實(shí)例均存在最優(yōu)解，即每個(gè)實(shí)例所有小矩形均可將大矩形剛好填充完，使利用率達(dá)到100%。基本算法對(duì)C21算例實(shí)驗(yàn)結(jié)果如表1所示。

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

2 集束搜索算法

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

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

由以上步驟可選出當(dāng)前格局下，執(zhí)行哪個(gè)放置動(dòng)作會(huì)有更好的未來(lái)趨勢(shì)，其算法示例如圖4所示。

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

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

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

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

從上述兩表的實(shí)驗(yàn)對(duì)比可知，使用基本算法通過(guò)集束搜索策略的改進(jìn)后，反超GRASP算法和TABU算法的實(shí)驗(yàn)結(jié)果。基本算法平均利用率為97.39%，GRASP算法平均利用率為98.50%，TABU算法平均利用率為99.53%，使用集束搜索策略后平均利用率上升到99.80%。整體利用率比基本算法平均利用率上升2.41%，比GRASP算法平均利用率上升了1.3%，比TABU算法平均利用率上升了0.27%。

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 王磊，尹愛(ài)華. 求解二維矩形Packing問(wèn)題的一種優(yōu)美度枚舉算法[J]. 中國(guó)科學(xué)；信息科學(xué)，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] 蔣興波，呂肖慶，劉成城. 二維矩形條帶裝箱問(wèn)題的底部左齊擇優(yōu)匹配算法[J]. 軟件學(xué)報(bào)，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問(wèn)題擬人型算法中的放置空間更新過(guò)程求解[J]. 軟件導(dǎo)刊，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.

（責(zé)任編輯：江 艷）