姚 怡, 賴朝安
(1. 華南理工大學(xué)工商管理學(xué)院,廣東 廣州 510640;2. 廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院,廣西 南寧 530004)
一種帶剪切約束的啟發(fā)式二維裝箱算法
姚怡1,2, 賴朝安1
(1. 華南理工大學(xué)工商管理學(xué)院,廣東 廣州 510640;2. 廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院,廣西 南寧 530004)
提出一種滿足剪切約束的啟發(fā)式二維裝箱算法,通過(guò)價(jià)值修正策略提高箱的空間利用率,進(jìn)而減少箱的使用數(shù)量。該啟發(fā)式算法將較難裝箱的物品賦予較高的價(jià)值及裝箱優(yōu)先權(quán);并通過(guò)延展或融合剩余零散空間,將未用的空間合并到剩余相鄰空間,以改進(jìn)空間利用率。基于標(biāo)桿測(cè)試數(shù)據(jù)集的仿真實(shí)驗(yàn)證明了該算法的有效性和相較于其他二維裝箱算法的優(yōu)越性。
二維裝箱;價(jià)值修正;剪切方式;啟發(fā)式
二維裝箱(two-dimensional bin packing,2DBP)問(wèn)題作為一個(gè)典型的組合優(yōu)化問(wèn)題吸引了大量集中于數(shù)學(xué)模型或算法的研究,近期的研究則更加關(guān)注大規(guī)模的裝箱問(wèn)題,對(duì)此通常不是采用系統(tǒng)的、精確的方法追求問(wèn)題的最優(yōu)解,而是采用確定性算法對(duì)解的生成方式加以一定的限制,在可接受的時(shí)間內(nèi)獲取較優(yōu)解[1-2];或者采用各種啟發(fā)式算法[3-10],通過(guò)不斷嘗試逐步趨優(yōu)的方法,達(dá)到有效合理的目標(biāo),取得足夠滿意的解。2DBP的研究主要關(guān)注輸出(價(jià)值)最大化與輸入(價(jià)值)最小化兩項(xiàng)指標(biāo),以達(dá)到裝箱效率的最大化。本文研究以輸入最小化為目標(biāo)的2DBP多箱問(wèn)題,該問(wèn)題可描述為:給定固定尺寸的多個(gè)二維矩形箱,其寬度為W,高度為H;存在大量在尺寸上差異較大的二維矩形物品,現(xiàn)需尋找能裝入所有物品的、且保證物品不重疊并呈現(xiàn)正交擺放形式的裝箱方案,達(dá)到所使用的箱數(shù)量最小化的目標(biāo)。
定向與剪切這兩種約束的組合產(chǎn)生4種2D裝箱方式:OF、RF、OG和RG[3]。O是指矩形物品只能定向裝箱(orientated,O),R則相反,允許物品旋轉(zhuǎn)(rotatable,R);G是指物品必須采用類似剪床的“一刀切”工藝的擺放布局,即剪切方式(guillotine-cut,G);而F則相反,允許物品自由擺放。本文研究2種情況:2DBP-OG和2DBP-RG。
2002年Lodi等[7]針對(duì)4種2DBP類型(OF、RF、OG和RG)提出了一種啟發(fā)式算法,同時(shí)設(shè)計(jì)了一個(gè)統(tǒng)一的禁忌搜索算法,在鄰域的探索中通過(guò)改變啟發(fā)性規(guī)則去適應(yīng)裝箱類型的變化。1999年Lodi等[3]提出了背包裝填算法(knapsack problem,KP),采用了基于所產(chǎn)生子問(wèn)題的另一個(gè)層裝填策略。在(兩值)背包問(wèn)題中,必須選擇n個(gè)元素的一個(gè)子集,每個(gè)元素有相應(yīng)的利潤(rùn)和重量,使總重量不超過(guò)給定的容重并且總利潤(rùn)達(dá)到最大。2009年P(guān)olyakovsky和M′Hallah[8]提出了基于代理的智能算法(agent-based,A-B),以剪切型左下原則(guillotine bottom-left,GBL)做物品的基礎(chǔ)裝填,并設(shè)置了物品的代理機(jī)制,每個(gè)代理?yè)碛凶约旱膮?shù)、適應(yīng)度和判定過(guò)程,通過(guò)代理間的相互影響,決定物品的最佳裝填位置。2011年Charalambous和Fleszar[9]針對(duì)帶剪切約束的2DBP提出了一個(gè)啟發(fā)式算法,采用平均面積的策略選擇物品并逐個(gè)箱子裝填,有效避免了因單純追求箱子的面積利用率而導(dǎo)致小物品的過(guò)度使用。2013年Fleszar[10]針對(duì)2BP-OG/RG問(wèn)題構(gòu)造了3個(gè)插入型啟發(fā)式算法,通過(guò)樹型結(jié)構(gòu)去描述物品布局以及物品的各種插入操作,并設(shè)計(jì)了新的判定規(guī)則用于改善算法效果。
針對(duì)裝箱過(guò)程中,由于某些物品過(guò)度使用而產(chǎn)生局部最優(yōu)而非全局最優(yōu)的現(xiàn)象,Belov提出順序價(jià)值修正策略(sequential value correction,SVC)。通過(guò)不斷修正物品價(jià)值來(lái)達(dá)到全局優(yōu)化的目的,并將該方法成功運(yùn)用于一維下料問(wèn)題[11]和帶排樣問(wèn)題[12],取得較好的效果。本文的二維裝箱算法借鑒了Belov提出的價(jià)值修正策略,具體如下:
(1) 對(duì)每個(gè)物品設(shè)定初始價(jià)值,形成價(jià)值不等的候選物品集合A;
(2) 從集合A中選擇要填充的若干物品形成集合B,并沿高度方向ih對(duì)物品非增序排列,采取左下角原則做基礎(chǔ)填充,形成階梯狀的物品填充布局P;
(3) 選擇位于階梯上方的某個(gè)矩形空間s,對(duì)其進(jìn)行裝箱;
(5) 每當(dāng)一個(gè)箱子裝滿了或剩余空間已經(jīng)無(wú)任何利用價(jià)值時(shí),就打開另一個(gè)新的空箱繼續(xù)裝填直至剩余物品為0,此時(shí)獲取一個(gè)裝箱方案C;
(6) 采用價(jià)值修正公式對(duì)每個(gè)物品價(jià)值進(jìn)行修正,形成附帶新價(jià)值的物品集合,重新裝箱,獲得新的裝箱方案,經(jīng)過(guò)若干次的迭代,選取最優(yōu)裝箱方案作為結(jié)果。
主算法偽代碼如下:
算法1. Main()
1.1物品初始價(jià)值設(shè)定
價(jià)值修正策略是為了在迭代過(guò)程中能更快更好地逼近最佳結(jié)果,在每一次迭代開始時(shí),將前一次迭代的結(jié)果傳遞過(guò)來(lái),作為參數(shù)調(diào)節(jié)本次迭代的初始值。本文方法在每輪裝箱方案生成后均對(duì)所有物品重設(shè)價(jià)值,采用價(jià)值修正的方式調(diào)整裝箱布局,使得難裝的物品(價(jià)值大)先行填充。衡量每個(gè)箱子的裝箱布局的好或壞,不再是單純的面積利用率,而是改成所裝物品總價(jià)值最大化。在首輪裝箱方案中,需要給每個(gè)物品一個(gè)初始價(jià)值。根據(jù)經(jīng)驗(yàn),一般面積越大的物品填充難度越大,因此直接設(shè)置物品面積為初始價(jià)值。設(shè)箱子尺寸為HW×,需對(duì)矩形物品集合A=進(jìn)行裝箱。裝箱之前,根據(jù)式(1)賦予每個(gè)物品 ai一個(gè)初始價(jià)值 vi:
1.2空間填充方法(pack(r,B))本文算法除了定義物品集合A,還定義了空間集合用來(lái)存放當(dāng)前箱子中可供填充的各種矩形空間信息。為方便描述,將已有或即將有物品填充的矩形空間稱為填充區(qū)域。對(duì)每個(gè)新打開的箱子,集合S默認(rèn)擁有一個(gè)面積為H×W的填充區(qū)域s00∈s0,隨著填充操作的持續(xù)進(jìn)行,會(huì)有分裂出來(lái)的剩余子空間集不斷加入集合S。當(dāng)或S集合元素?zé)o利用價(jià)值,即任意 sij都無(wú)法容納任意的 ai時(shí),一個(gè)箱子的填充操作結(jié)束,允許打開新箱繼續(xù)填充。每次的填充操作都選擇一個(gè)填充區(qū)域和若干物品,將物品沿空間寬度W方向按照 hi從高到低的原則依次排列填充,填充操作完畢后將生成子空間集(如圖1所示),對(duì)空間 s00進(jìn)行填充后,生成包含4個(gè)子空間的集合
圖1 填充操作后剩余子空間的生成
算法2. pack(r,B)
1.2.1空間的選擇(sele_area(S))
填充操作每次只針對(duì)一個(gè)矩形區(qū)域空間,對(duì)新打開的箱子,默認(rèn)只有一個(gè)面積為H×W的填充區(qū)域,無(wú)需進(jìn)行選擇。當(dāng)對(duì)某個(gè)填充區(qū)域進(jìn)行階梯狀填充操作之后,在每個(gè)物品上方均一對(duì)一生成小的矩形區(qū)域空間sij左下角坐標(biāo)與物品左上角坐標(biāo)重疊,右上角坐標(biāo)與當(dāng)前填充區(qū)域右上角坐標(biāo)重疊,因此下一輪的填充操作必須進(jìn)行空間選擇。在如圖 1所示的首輪填充操作后,物品1(2、3、4)對(duì)應(yīng)區(qū)域空間A(B、C、D),4個(gè)區(qū)域空間形成空間集合S中的一個(gè)子集,即各區(qū)域空間尺寸、面積各有差異。本文算法按照面積從大到小進(jìn)行空間選擇,每個(gè)空間子集 si只選擇一個(gè)空間成為填充區(qū)域。如圖1所示的空間子集 s1,優(yōu)先選擇面積最大的區(qū)域 A進(jìn)行下一輪的物品填充。如果區(qū)域 A由于形狀的緣故無(wú)法容納候選物品集合中的任何物品,則選擇面積次大的區(qū)域 B進(jìn)行下一輪的物品填充,以此類推,按面積大小進(jìn)行填充區(qū)域選擇。如果所有空間均無(wú)法容納物品,且無(wú)法與其他區(qū)域合并空間,則在集合S中刪除該子集 s1j。
算法3. sele_area(S)
1.2.2物品的選擇(selete(ai,r))
在進(jìn)行填充操作時(shí),首要步驟是從候選物品集合中挑選合適的物品形成B集合,用于填充當(dāng)前的面積為H×W的矩形區(qū)域,使得填充區(qū)域價(jià)值最大,然后再考慮剩余空間的利用。此時(shí),物品的挑選實(shí)際上是一個(gè)經(jīng)典的0-1背包問(wèn)題。0-1背包問(wèn)題描述如下:有n件物品和一個(gè)容量為V的背包,第i件物品的重量是 c[i],價(jià)值是w[i],求解將哪些物品裝入背包可使這些物品的重量總和不超過(guò)背包容量,且價(jià)值總和最大。0-1背包問(wèn)題可以用遞歸法、動(dòng)態(tài)規(guī)劃法、貪心法和分支界限法等多種方法解決,本文選用動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是先要有效地找出子問(wèn)題,并通過(guò)其子問(wèn)題推出原問(wèn)題的解,通常子問(wèn)題與原問(wèn)題是相同的,只是規(guī)模上的縮小,直到遇見問(wèn)題的界限。對(duì)于0-1背包問(wèn)題,也可以找出滿足動(dòng)態(tài)規(guī)劃的子問(wèn)題:如果不放第i件物品,那么問(wèn)題就轉(zhuǎn)化為“前i?1件物品放入容量為v的背包中”,價(jià)值為如果放第i件物品,那么問(wèn)題就轉(zhuǎn)化為“前i?1件物品放入剩下的容量為v?c[i]的背包中”。此時(shí)能獲得的最大價(jià)值就是再加上通過(guò)放入第i件物品獲得的價(jià)值因此狀態(tài)轉(zhuǎn)移方程為:
在進(jìn)行如圖 1所示的物品填充時(shí),由于只允許正交方式擺放,不允許重疊,且物品上下兩個(gè)方向均無(wú)其他物品,因此可看成一次沿著填充區(qū)域的寬度方向的一維填充操作。此時(shí)物品的選擇過(guò)程就與經(jīng)典0-1背包問(wèn)題存在一一對(duì)應(yīng)關(guān)系:
(1) 填充區(qū)域的寬度W——一個(gè)容量為 V的背包;
(2) 物品價(jià)值 vi——物品價(jià)值w[i];
(3) 物品寬度wi——物品的重量是 c[i](OG方式);
(4) 物品寬度wi或長(zhǎng)度hi——物品的重量是c[i](RG方式)。
在物品選擇過(guò)程中,對(duì)于OG方式,只能正放不能倒放,因此,凡是物品過(guò)大放不進(jìn)指定區(qū)域即滿足的物品自然淘汰,不在選擇范圍內(nèi);而對(duì)于RG方式,則需要從正放和倒放兩個(gè)方向進(jìn)行考慮,是選擇物品寬度wi(正放),還是選擇長(zhǎng)度 hi(倒放)作為沿填充區(qū)域?qū)挾萕填充的對(duì)象,主要依據(jù)以下判斷規(guī)則:
(1) 如果該物品寬度小于等于高度且正放倒放均能放進(jìn)區(qū)域內(nèi)即wi≤hi&&wi≤W&&wi≤H&&hi≤W&&hi≤H,則選擇物品寬度wi;
(3) 如果該物品寬度大于高度且正放倒放均能放進(jìn)區(qū)域內(nèi)即wi>hi&&wi≤W&&wi≤H&&hi≤W&&hi≤H,則選擇物品高度hi;
(5) 其他情況的物品屬于無(wú)論正放還是倒放都超出區(qū)域的情況,做淘汰處理,不參與物品選擇。
算法4. selete(ai,r)
1.2.3子空間的生成
圖2 3個(gè)子空間集s上 、s左 和s下的生成
當(dāng)子空間集均不為空時(shí),添加到空間集S的末尾成為候選空間。如此循環(huán),處理剩余空間。為防止無(wú)效空間集的循環(huán)生成,設(shè)置終止條件:當(dāng)某個(gè)子空間集中所有矩形區(qū)域均屬于無(wú)效空間時(shí),禁止生成下級(jí)空間集并刪除當(dāng)空間集S=φ時(shí),表示當(dāng)前箱子已完成填充操作,允許打開新的箱子繼續(xù)填充。
剩余空間離散化意味著可選擇的物品種類會(huì)變少,因此有必要進(jìn)行空間擴(kuò)張或空間融合,這有利于提高空間利用率。當(dāng)然,采取措施的前提是保證剪切方式的正確實(shí)施,因此在做騰挪操作時(shí),應(yīng)以對(duì)應(yīng)物品的填充寬度作為移動(dòng)步長(zhǎng)。當(dāng)某個(gè)子空間集被定義為無(wú)效空間集時(shí),允許其向剩余的相鄰空間集輸送空間。輸送的次序依照空間集S的次序,假設(shè)當(dāng)前空間集如圖3(a)所示。當(dāng)空間集因無(wú)合適物品而被定義為無(wú)效空間集時(shí),依照順序,需向右騰挪后被安排給空間集如圖3(b)所示;然后再向上騰挪后被安排給空間集,如圖3(c)所示;當(dāng)與空間集相鄰的空間集個(gè)數(shù)為0時(shí),刪除空間集的所有信息。
圖3 空間合并示例
1.3價(jià)值修正
物品的價(jià)值決定了物品在裝箱過(guò)程中的優(yōu)先級(jí)別,對(duì)于面積較大的,或形狀獨(dú)特的,或大部分剩余空間均難以將之容納的物品應(yīng)賦予更高的價(jià)值,提升其優(yōu)先級(jí)別。
本文算法通過(guò)多次迭代提高解的質(zhì)量,每次迭代均根據(jù)上一次的裝箱方案C對(duì)各物品價(jià)值 vi進(jìn)行修正,以達(dá)到讓難裝的物品先行填充的目的。設(shè):在當(dāng)次迭代產(chǎn)生的裝箱方案C中,物品 ai所在的那個(gè)箱子一共填充了m個(gè)物品,則面積利用率設(shè)置兩個(gè)常數(shù)g∈(0,1)和 ρ>1,g為修正價(jià)值的權(quán)值系數(shù);ρ為控制參數(shù),實(shí)驗(yàn)中可嘗試不同的值使得物品的價(jià)值更趨向于合理。本文設(shè)計(jì)價(jià)值修正公式為:
式(3)中,通過(guò)權(quán)值系數(shù)g來(lái)調(diào)節(jié)物品的原價(jià)值在新價(jià)值中所占的比例;存在的意義在于:箱子中物品個(gè)數(shù)越多,意味著小尺寸物品較多,且易于和其他物品形成互補(bǔ)關(guān)系提升填充率,應(yīng)該降低該類物品的價(jià)值。
通過(guò)上述價(jià)值公式的修正,使得算法在構(gòu)造一個(gè)解決方案時(shí)充分考慮了每個(gè)物品的使用頻率,每次迭代生成的裝箱方案都參考了上一次方案的參數(shù),根據(jù)參數(shù)重新修正物品價(jià)值。不再單純以面積利用率作為衡量裝箱效果的唯一標(biāo)準(zhǔn),而是以箱子物品的總價(jià)值作為裝箱優(yōu)劣的判斷準(zhǔn)則,這種修正機(jī)制賦予了難裝物品更高的優(yōu)先權(quán),有效避免了較差方案的生成。
本文算法(value correction heuristic,VCH)采用二維裝箱實(shí)驗(yàn)中常用的500個(gè)標(biāo)準(zhǔn)算例進(jìn)行驗(yàn)算,并與其他算法結(jié)果進(jìn)行比較。500個(gè)算例共分為10個(gè)classes,每個(gè)class包含50個(gè)小題。每個(gè)小題提供的箱子均為正方形,物品尺寸在小于箱子尺寸范圍內(nèi)隨機(jī)生成,算法采用C#編程,Microsoft visualstudio 2010進(jìn)行編譯。為了節(jié)約運(yùn)行時(shí)間,本文算法讀取了二維裝箱算法下界(lower bound,LB)數(shù)據(jù),其中,2BP|O|G 調(diào)用了 Fekete和Schepers[5]給出的下界,2BP|R|G調(diào)用了Clautiaux等[6]給出的下界。實(shí)驗(yàn)中設(shè)置g=0.45;ρ=1.2,經(jīng)200次迭代計(jì)算上述500個(gè)標(biāo)準(zhǔn)算例,SH算法取得數(shù)據(jù)為:2BP|O|G共需7 309個(gè)箱子,平均用時(shí)0.236 s;2BP|R|G共需 7 059個(gè)箱子,平均用時(shí)0.255 s。表1顯示本文算法(VCH)與其他啟發(fā)式算法進(jìn)行比較的結(jié)果,數(shù)據(jù)顯示VCH算法在箱子消耗總數(shù)上占有優(yōu)勢(shì)。
表2顯示了A-B,CHBP,CFIH+J4算法和本文算法(VCH)的細(xì)節(jié)數(shù)據(jù)的對(duì)比,同時(shí)列出下界(LB)數(shù)據(jù)作參考。數(shù)據(jù)表明VCH算法在第5組中表現(xiàn)特別優(yōu)秀,其他組也取得不錯(cuò)的結(jié)果,無(wú)論是O|G方式還是R|G方式,500題的箱子消耗總數(shù)比其他算法都要少。
表1 本文算法與其他算法的性能對(duì)比數(shù)據(jù)
表2 4種算法的分段數(shù)據(jù)對(duì)比(箱子個(gè)數(shù))
表3 取不同迭代次數(shù)的運(yùn)算結(jié)果(箱子個(gè)數(shù))
本文提出了一個(gè)應(yīng)用于剪切方式的啟發(fā)式二維裝箱算法,對(duì)當(dāng)前剩余空間設(shè)計(jì)了有效劃分和填充,相鄰小空間的合并有效提高了面積利用率。該算法通過(guò)修正物品價(jià)值調(diào)整物品的填充次序,多次迭代使解逐步趨優(yōu)。實(shí)驗(yàn)表明,相比其他啟發(fā)式算法,本文算法取得了較好的裝箱結(jié)果。由于其需要多次調(diào)用0-1背包子算法,因此耗費(fèi)時(shí)間較多,在時(shí)間性能上沒取得更好的結(jié)果。基于這個(gè)問(wèn)題,未來(lái)可采用并行編程技術(shù),或時(shí)間復(fù)雜度更低的背包算法,提高時(shí)間效率。
[1] 潘衛(wèi)平, 陳秋蓮, 崔耀東, 等. 基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法[J]. 圖學(xué)學(xué)報(bào), 2015, 36(1): 7-11.
[2] 易向陽(yáng), 潘衛(wèi)平, 張俊暉. 基于五塊模式的單一矩形件排樣算法[J]. 圖學(xué)學(xué)報(bào), 2015, 36(4): 521-525.
[3] Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems [J]. INFORMS Journal on Computing, 1999, 11(4): 345-357.
[4] W?scher G, Hau?ner H, Schumann H. An improved typology of cutting and packing problems [J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.
[5] Fekete S P, Schepers J. A general framework for bounds for higher dimensional orthogonal packing problems [J]. Mathematical Methods of Operations Research, 2004, 60(2): 311-329.
[6] Clautiaux F, Jouglet A, Hayek J E. A new lower bound for the non-oriented two-dimensional bin-packing problem [J]. Operations Research Letters, 2007, 35(3): 365-373.
[7] Lodi A, Martello S, Vigo D. Recent advances on two-dimensional bin packing problems [J]. Discrete Applied Mathematics, 2002, 123(1-3): 296-379.
[8] Polyakovsky S, M′Hallah R. An agent-based approach to the two-dimensional guillotine bin packing problem [J]. European Journal of Operational Research, 2009, 192(3): 767-781.
[9] Charalambous C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers & Operations Research, 2011, 38(10): 1443-1451.
[10] Fleszar K. Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts [J]. Computers & Operations Research, 2013, 40(1): 463-474.
[11] Belov G, Scheithauer G. Setup and open-stacks minimization in one-dimensional stock cutting [J]. INFORMS Journal on Computing, 2007, 19(1): 27-35.
[12] Belov G, Scheithauer G, Mukhacheva E A. One-dimensional heuristics adapted for two-dimensional rectangular strip packing [J]. Journal of the Operational Research Society, 2008, 59: 823-832.
A Heuristic Algorithm for Two-Dimensional Bin Packing with Guillotine Constraints
Yao Yi1,2,Lai Chaoan1
(1. School of Business Administration, South China University of Technology, Guangzhou Guangdong 510640, China; 2. College of Computer and Electronics Information, Guangxi University, Nanning Guangxi 530004, China)
A heuristic approach for two-dimensional bin packing problems with guillotine constraints is proposed to minimize bin usage by maximizing space efficiency through the strategy of value correction. This heuristic algorithm firstly assigns higher values and packing priorities to items considered more difficult to pack into residual spaces, then selects packing spaces in descending order of unused area, and finally expand or merge residual small spaces and add unusable space to the residual adjacent space set, so as to improve the utilization rate. Simulation experiments on benchmark test sets suggest that the approach can work effectively and rivals existing other 2DBP methods.
two-dimensional bin packing; value correction; guillotine cut; heuristic
TP 391
A
2095-302X(2015)06-0879-08
2015-06-25;定稿日期:2015-07-08
國(guó)家自然科學(xué)基金面上項(xiàng)目(71371058);國(guó)家自然科學(xué)基金地區(qū)科學(xué)基金項(xiàng)目(61363026)
姚怡(1975–),女,廣東陽(yáng)江人,副教授,碩士。主要研究方向?yàn)榻M合優(yōu)化算法。E-mail:yaoyi@gxu.edu.cn
賴朝安(1973–),男,廣西欽州人,副教授,博士。主要研究方向?yàn)橹圃煨畔⒒?、?chuàng)新方法。E-mail:chalai@scut.edu.cn