基于模擬退火的貫通約束不規(guī)則排樣

韓 偉 張子成

南京財(cái)經(jīng)大學(xué)，南京，210046

基于模擬退火的貫通約束不規(guī)則排樣

韓 偉 張子成

南京財(cái)經(jīng)大學(xué)，南京，210046

針對(duì)帶貫通性約束的不規(guī)則凸多邊形的排樣問題，提出了一種分階段構(gòu)造算法。為了控制每個(gè)階段新生成的組合圖形的形狀,構(gòu)造過程引入變動(dòng)的形狀權(quán)重，算法運(yùn)行早期采用較小權(quán)重使圖形組合具有較高出材率,而在后期采用較大的權(quán)重得到類似矩形的復(fù)合?；谀M退火思想引入溫度參數(shù)控制權(quán)重的變化率，在早期和后期形狀權(quán)重變化率較小而在中期變化率較大。采用ESICUP標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)分別對(duì)常數(shù)散列、線性散列和溫控散列進(jìn)行對(duì)比,結(jié)果表明溫控散列函數(shù)能有效提高排樣效率和排樣出材率。

不規(guī)則排樣;貫通約束;模擬退火;形狀權(quán)重

0 引言

二維排樣問題是一類典型的組合爆炸優(yōu)化問題，廣泛應(yīng)用于玻璃加工、金屬切割、服裝等行業(yè)。研究排樣優(yōu)化算法對(duì)提高原料利用率，建立節(jié)約型、環(huán)境友好型社會(huì)具有重要意義。Bennell等[1]分析了二維排樣問題的各種矩形優(yōu)化算法，對(duì)于不規(guī)則排樣問題，由于其組合的可能性增大，零件之間的重疊、相交及相鄰關(guān)系判斷也較為復(fù)雜，因此采用傳統(tǒng)的數(shù)學(xué)規(guī)劃和單一的啟發(fā)算法較難解決不規(guī)則排樣問題[2]。李敬花等[3]采用凸多邊形包絡(luò)法對(duì)不規(guī)則多邊形進(jìn)行處理，結(jié)合遺傳算法的快速全局搜索能力和模擬退火算法的局部搜索能力，以遺傳算法做外層循環(huán)，以模擬退火做內(nèi)層循環(huán)，從而改善遺傳算法的早熟缺陷。張德富等[4]提出了一種基于離散臨界多邊形模型，用于求解二維不規(guī)則排樣問題。梁利東等[5]將粒子群算法與剩余矩形匹配算法相融合，提高了排樣優(yōu)化問題的收斂速度并可以有效跳出局部最優(yōu)。上述文獻(xiàn)并未考慮排樣過程中的貫通性約束條件(guillotine constrain)[6-8]，即俗稱的“一刀切”。貫通性約束是一種重要而常見的加工過程約束，一般認(rèn)為，由于其計(jì)算代價(jià)太高，在一般非貫通約束排樣方法中加入貫通性約束條件幾乎是不可行的，因此，必須針對(duì)貫通約束研究專門的不規(guī)則排樣算法。

貫通約束早期的研究采用矩包法，用不規(guī)則零件的最小外接矩形(MER)替代不規(guī)則零件本身進(jìn)行排樣,將不規(guī)則排樣問題轉(zhuǎn)化為矩形排樣，然后用得到的排樣結(jié)果從MER中還原不規(guī)則零件，這種處理方式簡(jiǎn)單易行，但是對(duì)于三角形等零件存在大量浪費(fèi)。二步法[9-10]針對(duì)三角形、平行四邊形等零件，將零件進(jìn)行兩兩配對(duì)(pair),形成接近矩形的pair，然后再對(duì)配對(duì)組合的MER進(jìn)行排樣，在一定程度上解決了矩包法存在的浪費(fèi)問題，但是仍不能保證每個(gè)pair形成近似矩形的圖形。韓偉等[11-12]在二步法基礎(chǔ)上進(jìn)一步提出了一種將多個(gè)零件聚合成近似矩形的多階段構(gòu)造方法。在復(fù)合構(gòu)造過程中，引入形狀權(quán)重來控制復(fù)合圖形與矩形的近似程度，權(quán)重越大，兩個(gè)多邊形復(fù)合后形成的多邊形越接近矩形。該算法在前期采用較小的形狀權(quán)重，有利于提高早期復(fù)合的出材率，而在后期采用較大的形狀權(quán)重，有利于最終進(jìn)化出接近矩形原片的圖形復(fù)合。本文在文獻(xiàn)[11-12]的基礎(chǔ)上，進(jìn)一步對(duì)分階構(gòu)造過程的有效性進(jìn)行了理論分析，并提出了基于溫控散列函數(shù)的形狀權(quán)重調(diào)整方法。

1 基本概念

定義1 一個(gè)凸多邊形P可以表示為平面直角坐標(biāo)系中的點(diǎn)組成的一個(gè)序列〈p1,p2,…,pn〉,其中n為多邊形的邊數(shù),pi=〈xi,yi〉(i=1,2,…,n)是多邊形的端點(diǎn)。多邊形的第i條邊記為ei=〈pi,pi+1〉(i=1,2，…,n-1),en=〈pn,p1〉。多邊形內(nèi)部的點(diǎn)的集合記為I(P),邊界記為F(P),頂點(diǎn)集合記為V(P)。

定義2 一個(gè)客戶零件訂單是一個(gè)凸多邊形集合D={Pi|i=1，2，…，L},數(shù)據(jù)D中的多邊形稱作基元。

定義3 凸多邊形P(P∈D)的一個(gè)變換f可以表示為一個(gè)四元組 〈m,x,y,t〉。其中 m∈{0,1}表示鏡像變換,取值1表示X鏡像變換,0表示不進(jìn)行鏡像變換。Y鏡像變換可由X鏡像變換和旋轉(zhuǎn)來完成。x,y∈R分別表示多邊形沿x軸和y軸的平移量。t∈(-π,π]表示多邊形以參照點(diǎn)p1為中心的旋轉(zhuǎn)量。多邊形的變換空間記為ψ,它是各個(gè)子變換空間的直積。

定義4 設(shè)凸多邊形P1,P2∈D,f1∈ψ1,f2∈ψ2分別是P1、P2上的變換,函數(shù)Φ:D×D→{-1,0,1}為

定義5 設(shè)凸多邊形P1,P2∈D,f1∈ψ1,f2∈ψ2分別是P1、P2上的一個(gè)變換,f=f1·f2是P1、P2的一個(gè)復(fù)合變換,記作f(P1,P2)=f1(P1)∪f2(P2)。若Φf1(P1),f2(P2)≥0,則f稱作P1、P2的不相交變換。

設(shè)C(S)表示點(diǎn)集S的最小凸包,則變換f(P1,P2)的最小凸包為C(V(P1)∪V(P2)),記為O(f(P1,P2))。f(P1,P2)的最小外接矩形記為R(f(P1、P2))。

由圖1可以看出,若凸包浪費(fèi)率較小,則形成的匹配更為緊致,若矩包浪費(fèi)率較小,則形成的匹配更近似于矩形,便于后期進(jìn)行原片填充。據(jù)此,我們進(jìn)一步定義加權(quán)浪費(fèi)率。

定義7 給定形狀權(quán)重w,變換f(P1,P2)的加權(quán)浪費(fèi)率定義為

由圖2看出,若P1、P2是不相交的,則必存在直線e將多邊形O(f(P1、P2))切分為兩個(gè)多邊形P1、P2,稱e是O的一條貫通線,O相對(duì)于P1、P2是可貫通的。

圖1 凸包浪費(fèi)率和矩包浪費(fèi)率

圖2 兩個(gè)凸多邊形的外接凸包及其貫通線

2 復(fù)合

2.1 集合的變換

定義10 給定集合T={P1,P2,…,Pt}?D及其上的變換f。若?Pi∈T,Pj∈T,i≠j,有Φf(Pi)∪f(Pj)≥0,則f稱為不相交變換。

定義11 若C(S)表示點(diǎn)集S的最小凸包,則f(T)的最小凸包為

定義12 給定集合T={P1,P2,…,Pt}?D及其上的變換f,O是f(T)的凸包。若滿足以下兩個(gè)條件之一，則f(T)稱作可貫通的：①f(T)中含有且僅含有兩個(gè)多邊形Q1、Q2, 且O相對(duì)于Q1、Q2是可貫通的；②存在O的一條貫通線,將f(T)劃分為兩個(gè)子集T1、T2,且T1、T2是貫通的。

若f(T)是可貫通的,則f稱作T上的可貫通變換。進(jìn)一步,若f是不相交變換,則稱f為T上的可行變換。所有可行變換的集合組成可行空間,記為Γ(T)。 玻璃排樣問題可歸結(jié)為在可行空間中尋找使得原材料用料最省的零件排樣方案。

2.2 復(fù)合及其性質(zhì)

定義15 設(shè)集合T1,T2?D,f1、f2分別是T1、T2上的變換,T1、T2的一個(gè)復(fù)合變換是一個(gè)多邊形集合,記為f(T1,T2)=f1(T1)∪f2(T2)。

定義17 設(shè)T?D,B=f(T) 是T的一個(gè)變換。若滿足下面兩個(gè)條件之一，則稱B是T的一個(gè)θ-復(fù)合：①B只含有一個(gè)元素；②T可以劃分為T1、T2,若B1、B2分別是T1、T2的θ-復(fù)合，則B是B1、B2的θ-可接受匹配。

如圖3所示，一個(gè)θ-復(fù)合B對(duì)應(yīng)一棵二叉復(fù)合樹,記為T(B)。該二叉樹以原像T中元素作為葉子節(jié)點(diǎn),以復(fù)合B為根節(jié)點(diǎn)。根據(jù)定義17，T(B)構(gòu)造如下：若符合條件①則T(B)含有且只含有一個(gè)節(jié)點(diǎn)B；若符合條件②,則分別以B1、B2構(gòu)造二叉樹T(B1)、T(B2),并進(jìn)一步以T(B1)和T(B2)作為左右子樹構(gòu)造二叉樹T(B)?？梢宰C明，θ-復(fù)合是原像T的一個(gè)可行變換。證明過程如下。

(1)首先用數(shù)學(xué)歸納法證明?H∈T(B)是其原像的非相交變換。①若H是兩個(gè)多邊形P1、P2的匹配,則H必是P1、P2最優(yōu)匹配,得證；②若H的左右子樹T(H1)、T(H2)均是原像T1、T2的不相交變換,由H是H1、H2的加權(quán)匹配,可得H是原像T的不相交變換。 (2)證明?H∈T(B)是其原像的貫通變換。①若H是兩個(gè)多邊形P1、P2的匹配,則H必是P1、P2的貫通變換；②若H的左右子樹T(H1)、

(a)0.95-復(fù)合

(b)二叉復(fù)合樹

T(H2)均是原像T1、T2的貫通變換,又H是H1、H2的加權(quán)匹配,若記O、O1、O2分別是H、H1、H2的凸包,則O相對(duì)于O1、O2是可貫通的。

綜合(1)、(2),T(B)的任意一個(gè)節(jié)點(diǎn)是其原像的可行變換，證畢。

3 基于模擬退火的分階構(gòu)造算法

3.1 基本例程:兩個(gè)多邊形的匹配

文獻(xiàn)[8]給出了兩個(gè)多邊形零件的slide/attach啟發(fā)式匹配方法，首先對(duì)P1的頂點(diǎn)和邊進(jìn)行順時(shí)針編號(hào),對(duì)P2的頂點(diǎn)和邊進(jìn)行逆時(shí)針編號(hào)，定義基本操作函數(shù)如下。

(1)鏡像M(P,m)：對(duì)多邊形P進(jìn)行鏡像操作，m∈{0,1}, 取值1表示X鏡像變換,0表示不進(jìn)行鏡像變換。

(2)靠接A(P1,P2,i,j)：保持P1不變,將P2平移,使其第j個(gè)頂點(diǎn)與P1的第i個(gè)頂點(diǎn)重合,并旋轉(zhuǎn)P2,使其第j條邊與P1的第i條邊重合。

(3)滑動(dòng)S(P1,P2,i,j,d)：平移P2,使其第j個(gè)頂點(diǎn)沿著P1的第i條邊滑動(dòng),滑動(dòng)距離為d，d≤max(0,D(ei)-D(ej))。

圖4所示為靠接操作與滑動(dòng)操作示例。

(a)靠接操作 (b)滑動(dòng)操作

算法1 兩個(gè)凸多邊形啟發(fā)式匹配算法如下：

輸入：多邊形P1、P2,權(quán)重w, 滑動(dòng)增量ε

輸出：P1、P2的加權(quán)最優(yōu)匹配

初始化best_m,best_i,best_j,best_d,min_u

對(duì)P1的每一個(gè)頂點(diǎn)i

對(duì)P2的每一個(gè)頂點(diǎn)j

form∈{0,1}

for d=0…max(0,D(ei)-D(ej)), step ε

執(zhí)行滑動(dòng)操作S(P1,P2,i,j,d)

best_i←i;best_j←j;best_d←d

執(zhí)行M(P2,best_m),A(P1,P2,best_i,best_j);

S(best_d)

返回P1∪f(P2)

3.2 森林

考慮到每個(gè)復(fù)合可以看作一棵樹,我們將所有m階θ-復(fù)合組成的集合稱為m階θ-森林。事實(shí)上,利用θ-復(fù)合之間定義清晰的組合關(guān)系,第m階森林可以由前m-1階森林構(gòu)造出來，如圖5所示。

圖5 森林構(gòu)造過程示例

定義18 給定權(quán)重w及閾值θ,定義第m階θ-森林為

通過結(jié)構(gòu)化存儲(chǔ)已有森林,我們可以利用類似求解Fibonacci序列的構(gòu)造方法來快速構(gòu)造高階森林。實(shí)際上,森林構(gòu)造過程是一個(gè)多步?jīng)Q策過程,每階森林代表一步?jīng)Q策。在森林構(gòu)造過程中,將來自相同或不同森林的兩個(gè)復(fù)合的外接凸包看作多邊形,利用4.1節(jié)的多邊形匹配基本例程求其匹配。將匹配度作為啟發(fā)信息,并與閾值θ相比較,以決定是否選入更高階的森林。之所以不從森林中截取固定數(shù)目的復(fù)合,是因?yàn)橥ㄟ^匹配度來截取更具有靈活性,有利于保持復(fù)合的多樣性。

3.3 沖突檢查及原片約束

森林構(gòu)造過程中,為保證新構(gòu)造的每個(gè)復(fù)合尺寸不超過原片尺寸,需要進(jìn)行約束檢查。設(shè)原片的長(zhǎng)和寬分別為L(zhǎng)和W,對(duì)于新構(gòu)造的復(fù)合B, 若l(R(B))和w(R(B))分別為B的外接最小矩形的長(zhǎng)和寬,則要求l(R(B))≤L,w(R(B))≤W。

3.4 溫控散列函數(shù)

模擬退火通過溫控參數(shù)解決了優(yōu)化算法在探索(explore)和利用(exploit)上的兩難問題，從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即若陷入局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。在早期通過較高的溫度使得算法在全局范圍搜索，而在后期算法能較快地收斂到當(dāng)前找尋到的最優(yōu)區(qū)域內(nèi)。在森林構(gòu)造算法的早期,采用較小的權(quán)重可以使生成的復(fù)合具有較小的浪費(fèi)率。而在后期采用較大的權(quán)重可以得到類似矩形的復(fù)合,用于填充原片。經(jīng)驗(yàn)數(shù)據(jù)顯示，森林構(gòu)造過程中各階森林中復(fù)合的數(shù)目大致符合二項(xiàng)式分布，這是因?yàn)樵缙诨緢D形的組合可能性較大，而后期受到?jīng)_突檢測(cè)和原片尺寸約束，雖然復(fù)合的數(shù)目增加，但是復(fù)合進(jìn)行繼續(xù)組合的可能性降低。因此考慮在早期和后期使形狀權(quán)重的變化率較小，而在中間階段使形狀權(quán)重發(fā)生明顯變化，為此構(gòu)造了溫控參數(shù)來適應(yīng)這一要求。若最大進(jìn)化代數(shù)為mg,權(quán)重w的變化區(qū)間設(shè)定為[0,1]，則第i階森林中,形狀權(quán)重設(shè)定為

式中，T為溫度參數(shù);mid=mg/2。

圖6 不同溫度參數(shù)下形狀權(quán)重的變化情況(mg=30)

3.5 森林構(gòu)造算法

算法2 森林構(gòu)造算法 (forest construction algorithm, FCA)如下：

輸入：max_g, DataSetD,T,selection_thread,stock_type

按照溫度T初始化權(quán)重?cái)?shù)組w

對(duì)第m代森林(m=2，3,…，max_g)

for i=1，2，…，m-1

求出Bx、By的原像 Tx、Ty

根據(jù)4.3進(jìn)行沖突檢查和原片約束檢查

由定義17,構(gòu)造f*(Bx,By)

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

歐洲切割與排樣研究會(huì)(ESICUP)網(wǎng)站上載了文獻(xiàn)[9]中采用的測(cè)試數(shù)據(jù)作為不規(guī)則貫通排樣研究公開數(shù)據(jù),8個(gè)數(shù)據(jù)集中4個(gè)取自Jotika軟件公司實(shí)際訂單數(shù)據(jù)，另外4個(gè)則是抽樣數(shù)據(jù)。表1給出了數(shù)據(jù)集的統(tǒng)計(jì)參數(shù)，其中零件的不規(guī)則度是其外接最小矩形內(nèi)的平均浪費(fèi)率,面積取量綱一單位。實(shí)驗(yàn)中,原片量綱一尺寸為3210×2250。

表1 實(shí)驗(yàn)數(shù)據(jù)說明

數(shù)據(jù)集規(guī)模平均邊數(shù)邊數(shù)標(biāo)準(zhǔn)差平均面積面積標(biāo)準(zhǔn)差不規(guī)則度Jotika40403.560.74110708898644600.2741Jotika50503.700.64711046538253710.3416Jotika60603.730.60710417757916340.2986Jotika70703.770.56910182797826750.2578Han80803.670.5087278136220350.2457Han1001003.830.4939685817395220.2520Han1201203.610.5628197777320180.3142Han1501503.820.6959321108134010.2667

4.2 實(shí)驗(yàn)對(duì)比

定義20 排樣平均出材率為

式中，N為排樣原片數(shù)量;A為原片面積。

我們選擇常數(shù)散列和線性散列與溫控散列進(jìn)行對(duì)比。常數(shù)散列方法是指在構(gòu)造過程中,形狀權(quán)重w是一個(gè)常數(shù),一般取值為0或者1。線性散列方法是指在構(gòu)造過程中,權(quán)重變化率是常數(shù)。第i(i=1，2,…，mg)階森林中,權(quán)重設(shè)定為wi=i/mg。表2列出了各個(gè)數(shù)據(jù)集合在不同參數(shù)下的平均出材率,測(cè)試表明，選取合適的溫度參數(shù)T，溫控散列函數(shù)能使排樣利用率取得較好的結(jié)果。

表2 不同選擇閾值θ及溫控參數(shù)T下,各數(shù)據(jù)集的出材率(括號(hào)內(nèi)為原片數(shù))

數(shù)據(jù)集θ=0.92θ=0.96w=0w=1線性散列T=4T=5w=0w=1線性散列T=4T=5Jotika400.675(9)0.759(8)0.759(8)0.759(8)0.759(8)0.759(8)0.675(9)0.759(8)0.759(8)0.675(9)Jotika500.764(10)0.764(10)0.848(9)0.848(9)0.848(9)0.764(10)0.764(10)0.848(9)0.848(9)0.764(10)Jotika600.720(12)0.720(11)0.786(11)0.786(11)0.786(11)0.720(11)0.720(12)0.720(12)0.720(11)0.720(11)Jotika700.715(14)0.715(14)0.715(14)0.770(13)0.770(13)0.770(13)0.715(14)0.715(14)0.770(13)0.715(14)Han800.741(11)0.815(10)0.815(10)0.815(10)0.815(10)0.815(10)0.741(11)0.741(11)0.815(10)0.741(11)Han1000.744(18)0.744(18)0.788(17)0.788(17)0.788(17)0.788(17)0.788(17)0.788(17)0.788(17)0.744(18)Han1200.762(18)0.807(17)0.807(17)0.807(17)0.807(17)0.762(18)0.722(19)0.762(18)0.807(17)0.762(18)Han1500.800(24)0.800(24)0.835(23)0.835(23)0.835(23)0.835(23)0.835(23)0.835(23)0.835(23)0.835(23)

從表2中可以看出溫控參數(shù)T應(yīng)該隨閾值θ取值變化，一般增大θ應(yīng)該適當(dāng)降低T。這是因?yàn)殚撝郸仍酱?則進(jìn)化的選擇壓力越大,算法越可能出現(xiàn)早熟,因此排樣結(jié)果相對(duì)較差。一般θ的設(shè)定應(yīng)該接近原片的平均出材率,但在算法運(yùn)行之前,我們無法獲知平均出材率,因此在實(shí)際應(yīng)用中通常根據(jù)原片尺寸和零件的平均尺寸來設(shè)定。在確定閾值θ的情況下,較大的溫控參數(shù)T代表較大的選擇壓力，這是因?yàn)檩^大的T會(huì)使得算法早期較小的形狀權(quán)重產(chǎn)生較久的作用，因此進(jìn)化得到的低階森林中復(fù)合數(shù)目也較少。

4.3 時(shí)間復(fù)雜度

實(shí)驗(yàn)所用計(jì)算機(jī)的處理器為Intel i5 M520,主頻2.4GHz,內(nèi)存2GB。測(cè)試結(jié)果見表3。不難看出,算法的運(yùn)行時(shí)間隨問題規(guī)模大致呈線性增長(zhǎng),這是因?yàn)樗惴ǔ浞掷昧藦?fù)合之間的組合關(guān)系,采用存儲(chǔ)記憶快速構(gòu)造各階森林。隨著閾值θ和溫度T的增大,選擇壓力也會(huì)較大,算法時(shí)間也會(huì)變短。

表3 不同選擇閾值θ及溫控參數(shù)T下,各數(shù)據(jù)集上的運(yùn)行時(shí)間

數(shù)據(jù)集θ=0.92θ=0.96w=0w=1線性散列T=4T=5w=0w=1線性散列T=4T=5Jotika40224140171210127188175114170147Jotika50271180195230151219178132176174Jotika60289182214270170225189148187160Jotika70314219248300203276211171245198Han80687483541605352633385387427387Han100918660746900494685475581549401Han120945740793914618741658624668447Han15013207209141147847776684783723489

5 結(jié)論

(1)本文針對(duì)不規(guī)則凸多邊形零件的排樣問題,對(duì)已有文獻(xiàn)提出的分階段構(gòu)造算法進(jìn)行了理論證明和實(shí)驗(yàn)分析，發(fā)現(xiàn)森林構(gòu)造過程中各階森林中復(fù)合的數(shù)目大致符合二項(xiàng)式分布，這是因?yàn)樵缙诨緢D形的組合可能性較大，而后期受到?jīng)_突檢測(cè)和原片尺寸約束，雖然復(fù)合的數(shù)目增加，但是復(fù)合進(jìn)行繼續(xù)組合的可能性降低。

(2)基于模擬退火思想提出溫控散列函數(shù)控制形狀權(quán)重的變化率，使得早期和后期形狀權(quán)重的變化率小，而在中間階段使形狀權(quán)重發(fā)生明顯變化。

(3)基于ESICUP公開的標(biāo)準(zhǔn)數(shù)據(jù)，分別對(duì)常數(shù)散列、線性散列和溫控散列進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明溫控散列能夠有效提高排樣出材率。

[1] Bennell J A, Oliveira J F. A Tutorial in Irregular Shape Packing Problems[J]. Journal of the Operational Research Society, 2009, 60(1):93-105.

[2] Bennell J, Scheithauer G, Stoyan Y, et al. Tools of Mathematical Modeling of Arbitrary Object Packing Problems[J]. Annals of Operations Research, 2010, 179(1):343-368.

[3] 李敬花，樊付見，王昊，等.遺傳模擬退火融合算法求解工程二維排樣問題[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17(9)：1962-1967. Li Jinghua，F(xiàn)an Fujian，Wang Hao, et al. Combination Genetic Simulated Annealing Algorithms for Solving Two-dimensional Packing Problem[J]. Computer Integrated Manufacturing Systems ，2011，17(9)：1962-1967.

[4] 張德富，陳競(jìng)馳，劉永凱,等.用于二維不規(guī)則排樣的離散臨界多邊形模型[J].軟件學(xué)報(bào)，2009，20(6)：1511-1520. Zhang Defu，Chen Jingchi，Liu Yongkai,et al. Discrete No-fit Polygon, a Simple Structure for the 2-D Irregular Packing Problem[J]. Journal of Software，2009，20(6)：1511-1520.

[5] 梁利東，鐘相強(qiáng).粒子群算法在不規(guī)則件排樣優(yōu)化中的應(yīng)用[J].中國機(jī)械工程，2010，21(17)：2050-2052. Liang Lidong，Zhong Xiangqiang. Applications of Particle Swarm Optimization for Solving Irregular Part Nesting Problems[J]. China Mechanical Engineering，2010，21(17)：2050-2052.

[6] Christofides N, Hadjiconstantinou E. An Exact Algorithm for Orthogonal 2-D Cutting Problems Using Guillotine Cuts[J]. European Journal of Operational Research, 1995, 83(1):21-38.

[7] 戈鵬，邱厭慶，劉柱勝,等. 一刀切問題的優(yōu)化二叉樹排樣[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17(2)：329-337. Ge Peng，Qiu Yanqing，Liu Zhusheng, et al. Optimized Binary Tree Packing of Guillotine Problem[J]. Computer Integrated Manufacturing Systems, 2011,17(2)：329-337.

[8] 王桂蘭，成亞云，朱龍彪,等.滿足“一刀切”要求的木工板排樣優(yōu)化研究[J].工程設(shè)計(jì)學(xué)報(bào)，2014，21(3)：212-216. Wang Guilan，Cheng Yayun，Zhu Longbiao, et al. Research on Optimum "Guillotine Cutting" Lay Out of Carpentry Board[J]. Chinese Journal of Engineering Design，2014，21(3)：212-216.

[9] Hifi M, M’Hallah R, Saadi T. Algorithms for the Constrained Two-staged Two-dimensional Cutting Problem[J]. Informs Journal on Computing, 2008, 20(2):212-221.

[10] 曹大勇，楊梅，科托夫·弗拉基米爾·米哈伊拉維奇,等.二維一刀切裝箱問題的兩階段啟發(fā)式算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18(9)：1954-1963. Cao Dayong，Yang Mei，Kotov V M, et al. Two-stage Heuristic Algorithm for Two-dimensional Guillotine Bin Packing Problem[J]. Computer Integrated Manufacturing Systems，2012，18(9)：1954-1963.

[11] 韓偉,馬福民.帶貫通約束的不規(guī)則排樣分階構(gòu)造算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2012(11)：2421-2424. Han Wei，Ma Fumin. Layered Constructive Algorithm for Irregular Guillotine Packing Problem[J]. Journal of Chinese Computer Systems，2012(11)：2421-2424.

[12] Han W,Bennell J A, Zhao X, et al. Construction Heuristics for Two-dimensional Irregular Shape Bin Packing with Guillotine Constraints[J]. European Journal of Operational Research, 2013, 230(3):495-504.

(編輯 王旻玥)

A Simulated Annealing Algorithm for Irregular Guillotine Packing Problems

Han Wei Zhang Zicheng

Nanjing University of Finance and Economics,Nanjing,210046

A layered constructive algorithm was proposed for 2D irregular guillotine bin packing problems. Variant shape weighs were introduced to control the shapes of each evolved block, which indicated the similarity of the resulted shape to rectangle in each iteration. To get better utilization, smaller shape weights were used in early periods to get shapes with higher ratio of utilization, while larger weights were introduced in the last periods to let the shape be similar to rectangle. Based on simulated annealing, a parameter named temperature was introduced to control the change rate weights. The change of shape weights was smaller in early and later periods and larger in middle periods. Based on ESICUP standard test data, several weight adjustment strategies were examined, including fixed weight, linear change and temperature-controlled change, the results show that temperature-controlled change effectively improves the layout effiency and the material rate of layout.

irregular bin packing; guillotine constraint; simulated annealing; shape weight

2016-01-25

國家級(jí)電子商務(wù)信息處理國際聯(lián)合研究中心項(xiàng)目(2013B01035)

TP391

10.3969/j.issn.1004-132X.2016.24.011

韓 偉，男，1975年生。南京財(cái)經(jīng)大學(xué)信息工程學(xué)院副教授。主要研究方向?yàn)槿斯ぶ悄?。發(fā)表論文20余篇。張子成，男，1991年生。南京財(cái)經(jīng)大學(xué)信息工程學(xué)院碩士研究生。