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

張鵬程，王春艷，茹江燕

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

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

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

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

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

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

0 引 言

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

1 矩形布局問(wèn)題的描述

矩形布局問(wèn)題作為一類二維布局問(wèn)題，將矩形作為排布對(duì)象，或利用矩形替代任意多邊形或不規(guī)則圖形進(jìn)行排布，其特點(diǎn)是既保留了布局問(wèn)題的復(fù)雜性，又使得問(wèn)題求解一定程度上得到簡(jiǎn)化，工程實(shí)踐中，有相當(dāng)一部分多邊形布局問(wèn)題的求解是利用包絡(luò)矩形將多邊形轉(zhuǎn)化為矩形來(lái)處理的。矩形布局問(wèn)題是在給定的矩形板材上排放所需要的矩形零件，使排放區(qū)域或整張板材的廢料盡可能減少，節(jié)省板材，即：給定n個(gè)矩形零件Rl，R2，…，Rn，將零件全部排放板材P上，使得板材利用率高，且滿足下列約束條件：（1）對(duì)任意兩個(gè)零件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為矩形的長(zhǎng)，Wi為矩形的寬，為所有排入的矩形件的面積總和；M為所有矩形件排放完畢后所占用的板材面積。

2 利用可行域算法求解矩形布局問(wèn)題

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

圖1 矩形及其可行域

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

[1]王小港，姚林聲，甘駿人.一種有效的VLSI布圖規(guī)劃算法[J].微處理機(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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008(2):246-252.

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

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

[7]王金敏，楊維嘉.動(dòng)態(tài)吸引子在布局求解中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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é)校電力工程系，實(shí)驗(yàn)師，碩士；王春艷（1977—），女，河北黃驊人，滄州設(shè)備安裝技工學(xué)校講師；茹江燕（1979—），女，河北宣化人，滄州設(shè)備安裝技工學(xué)校講師.