張鵬程，王春艷，茹江燕

（1.河北工程技術(shù)高等專科學(xué)校 電力工程系，河北 滄州 061001；2.滄州設(shè)備安裝技工學(xué)校，河北 滄州 061000）

矩形布局的啟發(fā)式優(yōu)化策略

張鵬程1，王春艷2，茹江燕2

（1.河北工程技術(shù)高等專科學(xué)校 電力工程系，河北 滄州 061001；2.滄州設(shè)備安裝技工學(xué)校，河北 滄州 061000）

利用可行域算法求解矩形布局問題，通過調(diào)整矩形布入形態(tài)，改變其單一的可行域形式增大其解空間。算例結(jié)果表明，矩形調(diào)整對布局結(jié)果影響有規(guī)律，利用可行域算法求解矩形布局問題，簡便、快捷、靈活、適應(yīng)性強，從而能夠靈活快速地獲得更優(yōu)異的矩形布局排布方案指導(dǎo)工程實踐。

矩形布局；可行域；啟發(fā)式算法；矩形形態(tài)；空間利用率

0 引 言

矩形布局問題作為一個具有NP-hard的組合最優(yōu)化問題，廣泛存在于板材切割、排樣、大規(guī)模集成電路設(shè)計、服裝裁剪和印刷排版等領(lǐng)域。由于在有限時間內(nèi)無法獲得全局最優(yōu)解，許多學(xué)者提出各種啟發(fā)式算法[1-3]用于解決不同領(lǐng)域的矩形布局問題，但很難找到一種對于各種不同特點的布局問題都有很好適應(yīng)性的求解方法。通過對不同算例計算結(jié)果進(jìn)行分析和比較得出，利用可行域算法求解矩形布局問題，簡便、快捷、靈活、適應(yīng)性強。

1 矩形布局問題的描述

矩形布局問題作為一類二維布局問題，將矩形作為排布對象，或利用矩形替代任意多邊形或不規(guī)則圖形進(jìn)行排布，其特點是既保留了布局問題的復(fù)雜性，又使得問題求解一定程度上得到簡化，工程實踐中，有相當(dāng)一部分多邊形布局問題的求解是利用包絡(luò)矩形將多邊形轉(zhuǎn)化為矩形來處理的。矩形布局問題是在給定的矩形板材上排放所需要的矩形零件，使排放區(qū)域或整張板材的廢料盡可能減少，節(jié)省板材，即：給定n個矩形零件Rl，R2，…，Rn，將零件全部排放板材P上，使得板材利用率高，且滿足下列約束條件：（1）對任意兩個零件Ri，Rj不發(fā)生重疊，即Ri∩Rj=Φ，1≤i，j≤n且i≠j；（2）Ri必須在板材邊界內(nèi)，即，1≤i≤n；（3）滿足一定的工藝條件。其求解目標(biāo)可表述為：求最優(yōu)排放序列I*，使，其中，Li為矩形的長，Wi為矩形的寬，為所有排入的矩形件的面積總和；M為所有矩形件排放完畢后所占用的板材面積。

2 利用可行域算法求解矩形布局問題

利用可行域算法求解矩形布局問題是一種很好的思路[4-6]。首先，求得每一個待布矩形在布局空間中的可行域；然后，根據(jù)定位策略,最終確定矩形最佳的擺放位置，如圖1所示。單純采用可行域算法求解矩形布局問題，根據(jù)約束條件設(shè)置定位函數(shù)參數(shù)，即可以獲得較好的布局方案和較優(yōu)的空間利用率。

圖1 矩形及其可行域

矩形可行域本質(zhì)上屬于矩形在其當(dāng)空布局空間中的不適合多邊形（NFP）。為求解過程的簡化和概念的一致性，規(guī)定矩形按其原始形態(tài)進(jìn)行計算，即布入時不發(fā)生旋轉(zhuǎn)，而最終矩形放入布局空間的形態(tài)，由其最初輸入時的狀態(tài)確定。一般情況下，矩形放置方式不同，其在布局空間中的可行域大小和形態(tài)也不同（當(dāng)其為正方形時例外），改變其中任一矩形的放置方式，都將會對最終布局結(jié)果產(chǎn)生影響。啟發(fā)式布局算法對于布局問題求解的效果是以最終的布局空間占有率來衡量的，即最大程度地提高材料利用率，減少材料浪費，從而增加企業(yè)經(jīng)濟效益。布局問題也屬于NPC問題，采用窮舉法列出并比較所有布局方案的優(yōu)劣是最簡單、直觀的策略，然而，這種方法只有當(dāng)矩形數(shù)量較少的時候有效；當(dāng)布局矩形達(dá)到一定規(guī)模時無疑會產(chǎn)生組合爆炸，而且這些計算在有限的時間內(nèi)是不可能完成的。基于啟發(fā)式的布局算法以人的認(rèn)知經(jīng)驗為導(dǎo)向，由于個人的思維方式及研究問題的思路和出發(fā)點不同而不可避免地加入更多人為因素，故使得現(xiàn)有求解方法都不同程度地帶有個人色彩。啟發(fā)式算法雖然可以從根本上降低問題求解的復(fù)雜度維數(shù)，將問題由不可求轉(zhuǎn)變?yōu)榭汕?，并且可以在較短時間內(nèi)獲得較為合理的求解方案，但這些是以犧牲部分解空間為代價的。利用啟發(fā)式算法只能以一定概率的方式獲得最優(yōu)解，或者是問題的近優(yōu)解或次優(yōu)解，對于工業(yè)生產(chǎn)中的實際問題其精確度已經(jīng)足夠。

3 矩形布局的啟發(fā)式算法的實現(xiàn)

在確定矩形布入次序時，可以其面積為依據(jù)按從大到小順序依次進(jìn)行布局操作，規(guī)定已經(jīng)布入布局空間的矩形位置不再發(fā)生變化，而矩形布入后布局空間會隨之發(fā)生相應(yīng)更新，以便為下一個矩形的放置做好準(zhǔn)備。而先排放面積大的矩形，最后用較小的矩形填充空隙，也使得大矩形獲得優(yōu)先排放機會，小矩形的放置又相對靈活多變，從而盡可能提高布局空間總體的利用率。

在布局過程中，矩形放置方式(橫放/縱放)不同，其可行域也不同，從而最終的布局結(jié)果也不一樣。如圖2所示，對于相同矩形布局空間，同一矩形橫放時,可行域為900（30×30）；而縱放時，可行域為500（50 ×10）。顯然，不同放置方式對后序布入的所有矩形及最終布局結(jié)果會產(chǎn)生很大影響，而這種影響必然從矩形布局的空間利用率表現(xiàn)出來。對于一個規(guī)模為N矩形布局問題（即矩形的數(shù)量為N）而言，當(dāng)改變矩形的布入形態(tài)，其可能選擇的布局方案比單一方式擺放方案多出2N-1種，這將大大增加布局解空間，從而使得更優(yōu)秀方案的出現(xiàn)成為可能。

圖2 矩形不同放置方式下的可行域

在矩形定位過程中，在所有有效放置位置（由矩形的可行域給出）中按照一定原則力求獲得最佳放置位置，從而有利于后續(xù)矩形的布入及最終獲得最優(yōu)空間利用率。在定位策略的選擇上，多數(shù)啟法式算法的實現(xiàn)基于BL策略或BLF策略，本文采用文獻(xiàn)[7]提出的定位函數(shù)法，定位函數(shù)的一般公式如下：

上式中，f（xi，yi）為總定位函數(shù)；ft（xi，yi）為關(guān)于各個吸引子定位函數(shù)；m為吸引子個數(shù)，吸引子原則上可以選取布局空間角上、邊上、中心或任意位置；n為矩形數(shù)量；（xi，yi）為布局矩形基點坐標(biāo)；（x0t，y0t）為布局吸引子坐標(biāo)；αt，βt為權(quán)重因子，表示矩形擺放時出現(xiàn)在x軸方向或y軸方向上的概率，當(dāng)αt>βt時,表示矩形優(yōu)先在x方向擺放；當(dāng)αt<βt時,表示矩形優(yōu)先在y方向擺放。如當(dāng)取吸引子的位置為布局空間左下角，矩形以相同概率擺放在x軸方向或y軸方向上時，定位函數(shù)的具體形式為：

為便于比較和計算，統(tǒng)一選取吸引子的位置為布局坐標(biāo)系的原點，即布局空間的左下角，矩形布局測試數(shù)據(jù)集見表1。

3.1 利用可行域算法求解矩形布局

利用可行域算法對表1中所有矩形布局測試數(shù)據(jù)進(jìn)行計算。求解過程中，采用矩形原始形態(tài)布入（即按strip3.xls文件中給出的長寬數(shù)據(jù)）?？尚杏蛩惴y試7類共35組矩形布局測試數(shù)據(jù)的布局結(jié)果見表2。

布局結(jié)果表明，利用可行域算法可以快速有效地求解矩形布局問題，在極短的時間內(nèi)獲得較為理想的布局方案。隨著矩形數(shù)量的增加，布局材料的空間利用率呈現(xiàn)上升趨勢。這是因為對于相同大小的板材，當(dāng)矩形數(shù)量較少時，則每一個矩形所占空間的權(quán)重就相對較大，而當(dāng)每一個矩形的面積相對布局空間的比例較大時，其可行域就會相應(yīng)變小，任意一個矩形不能布入，都會對最終空間占有率產(chǎn)生較大影響；當(dāng)矩形數(shù)量較多時，矩形相對面積較小，一個矩形的布入與否不會對最終空間占有率產(chǎn)生較大影響，而且小矩形布局時容易“見縫插針”，布局過程更加靈活，所以最終空間利用率較高。利用可行域算法求解矩形布局問題，隨著矩形數(shù)量的增加，布局效果越好，且不同矩形數(shù)據(jù)的空間利用率值越穩(wěn)定，如圖3所示。

表1 矩形布局測試數(shù)據(jù)集

表2 可行域算法測試7類共35組矩形布局測試數(shù)據(jù)的布局結(jié)果

當(dāng)無法獲得布局最優(yōu)解時（矩形全部布入，空間占有率100%），一定會產(chǎn)生有的矩形無法布入的情況。矩形無法布入的原因可能是由于布局空間本身太小，無法容納該矩形，或者由于啟發(fā)式布局策略自身的局限性所引起的，如矩形的放置位置和放置方式，不同的放置位置和放置方式一定會對后續(xù)所有矩形的放置產(chǎn)生影響。

圖3 T1,T2,T3三類數(shù)據(jù)布局結(jié)果比較

3.2 單一矩形旋轉(zhuǎn)

矩形布局的啟發(fā)式算法一般是將每一個矩形逐次放入布局空間。首先，按照布局規(guī)則和布局策略要求正確放入一個矩形，矩形放入后其位置不再發(fā)生變動，相關(guān)算法會計算布局空間所發(fā)生的變化，從而對布局空間進(jìn)行更新，為下一個矩形的布入做好準(zhǔn)備。在選定待布矩形后，確定矩形的放置方式：矩形放置方式不同，對后續(xù)矩形排布造成的影響也不一樣，最終導(dǎo)致不同的布局結(jié)果。對于不同矩形進(jìn)行旋轉(zhuǎn)，取旋轉(zhuǎn)后的布局結(jié)果與未旋轉(zhuǎn)之前的布局結(jié)果進(jìn)行比較，選取其中空間利用率較高的布局方案記錄下來，將空間利用率較低的布局方案舍去。依次計算和比較每個矩形的情況，最后將空間利用率最高的結(jié)果作為最終布局方案。

以圖3中直接布局結(jié)果最差的T1e組矩形布局測試數(shù)據(jù)為例，矩形數(shù)量為17個，布局空間為200×200，對T1e組矩形布局測試數(shù)據(jù)進(jìn)行布局，布局結(jié)果見表3。先對所有矩形按面積降序排列，然后在布局過程中從大到小依次調(diào)整單個矩形的放置方式，獲得單一矩形旋轉(zhuǎn)后的布局結(jié)果見表4。單一矩形調(diào)整后的空間利用率與原空間利用率比較如圖4所示。

表3 T1e組矩形布局測試數(shù)據(jù)的布局結(jié)果

從以上數(shù)據(jù)分析可以得出，通過對單一矩形布入形態(tài)進(jìn)行調(diào)整，獲得了更好的布局結(jié)果，空間利用率從79.46%增長為85.8125%，直接提高近7個百分點。另外，就布局矩形而言，面積較大的矩形形態(tài)的改變對最終布局結(jié)果的影響更明顯，所以在設(shè)計矩形布局優(yōu)化算法時，應(yīng)以改變大面積的矩形放置方式為主。

3.3 多個矩形旋轉(zhuǎn)

對照矩形輸入時的寬度值和高度值定義的初始狀態(tài)，隨機調(diào)換部分矩形的寬度和高度值即改變其放置方式，從而影響最終的布局結(jié)果，增大解空間范圍，通過比較從中優(yōu)選出最佳布局方案。以系統(tǒng)時間作為種子，利用函數(shù)srand[(unsigned)time(NULL)]初始化隨機數(shù)發(fā)生器，利用函數(shù)rand()產(chǎn)生隨機數(shù)，并用算式rand()%n生成布局過程中隨機發(fā)生旋轉(zhuǎn)的矩形序號，n是參與布局的矩形數(shù)。從矩形旋轉(zhuǎn)后產(chǎn)生的樣本空間中隨機選取1000個樣本點，找到其中最優(yōu)解，T1e組矩形布局測試數(shù)據(jù)多個矩形旋轉(zhuǎn)后的布局結(jié)果見表5。

布局結(jié)果表明，多個矩形同時發(fā)生旋轉(zhuǎn)可以進(jìn)一步增大解空間，同時會有更優(yōu)解出現(xiàn)。與表4相比，多個矩形調(diào)整放置方式比單一矩形旋轉(zhuǎn)更容易獲得優(yōu)化布局結(jié)果，當(dāng)發(fā)生旋轉(zhuǎn)的矩形數(shù)量接近總數(shù)一半時，出現(xiàn)局部最優(yōu)解的可能性較大。T1e組無矩形調(diào)整和多矩形調(diào)整方式產(chǎn)生的不同布局結(jié)果的比較如圖5所示。

表4 T1e組矩形布局測試數(shù)據(jù)單一矩形旋轉(zhuǎn)后的布局結(jié)果

圖4 單一矩形調(diào)整前后的空間利用率比較

表5 T1e組矩形布局測試數(shù)據(jù)多個矩形旋轉(zhuǎn)后的布局結(jié)果

4 結(jié) 論

利用可行域算法求解矩形布局問題是一種行之有效的方法，其簡便、快捷、靈活、適應(yīng)性強，求解結(jié)果不過度依賴矩形形式和問題規(guī)模，可以用于各種二維布局問題的求解實踐中。本文在基于矩形可行域算法的基礎(chǔ)上，引入啟發(fā)式布局策略，以調(diào)整矩形布入形態(tài)特征增大解空間范圍，最終通過對矩形布局過程和布局結(jié)果進(jìn)行優(yōu)化和優(yōu)選，獲得最佳矩形布局排布方案。對大量算例計算結(jié)果進(jìn)行分析和比較，得出調(diào)整矩形布入形態(tài)對布局結(jié)果的影響規(guī)律，即一般情況下，多矩形調(diào)整效果優(yōu)于單一矩形調(diào)整效果；而為獲得更優(yōu)異的布局結(jié)果，調(diào)整矩形的數(shù)量以接近矩形總數(shù)一半時為宜。

圖5 T1e組矩形布局結(jié)果的比較

[1]王小港，姚林聲，甘駿人.一種有效的VLSI布圖規(guī)劃算法[J].微處理機，2002(1):4-7.

[2] Chan H H，Markov I L.Practical slicing and non-slicing block-packing without simulated annealing[G]//ACM Special Interest Group on Design Automation.GLSVLSI’04.Boston:ACM Press，2004:282-287.

[3]Wu Y L，Huang Wenqi，LAU S，et al.An effective quasi-human based heuristic for solving the rectangle packing problem[J]. European Journal of Operational Research，2002(141):341-358.

[4]王金敏，張鵬程，朱艷華.矩形布局可行域的確定[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2008(2):246-252.

[5]張鵬程，郗艷梅，李國順，等.利用可行域的矩形布局求解方法[J].現(xiàn)代制造工程，2010(3):90-93.

[6]張鵬程，郗艷梅，任紅霞.矩形布局空間的處理及優(yōu)化研究[J].溫州職業(yè)技術(shù)學(xué)院學(xué)報，2011(1):54-58.

[7]王金敏，楊維嘉.動態(tài)吸引子在布局求解中的應(yīng)用[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005(8):1725-1730.

[責(zé)任編輯：王瑋明]

Optimization for Rectangle Packing Problem Based on Heuristic Strategy

ZHANG Pengcheng1, WANG Chunyan2, RU Jiangyan2
(1. Department of Electrical Engineering , Hebei Engineering and Technical College, Cangzhou, 061001, China; 2. Cangzhou Technical School of Equipment Installation, Cangzhou, 061000, China)

In order to solve the rectangle packing problem on the basis of feasible region algorithm, the rectangle pose can be adjusted to change its single feasible region form and expand its space. The result of the numerical example shows that the impact of rectangle pose adjustment to packing problem is regular. Applying the feasible region algorithm to solve rectangle packing problem is simple, fast, flexible and adaptable, and thus a better rectangle packing problem can be obtained to guide the practice.

Rectangle packing problem; Feasible region; Heuristic strategy; Rectangle pose; Space utilization ratio

TP301.6

A

1671-4326(2012)03-0045-04

2012-03-26

張鵬程（1976—），男，河北泊頭人，河北工程技術(shù)高等?？茖W(xué)校電力工程系，實驗師，碩士；王春艷（1977—），女，河北黃驊人，滄州設(shè)備安裝技工學(xué)校講師；茹江燕（1979—），女，河北宣化人，滄州設(shè)備安裝技工學(xué)校講師.