求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法

1、計(jì)算機(jī)研究與發(fā)展Journal of Computer Research and DevelopmentISSN 100021239ICN 1121777 UP46(3) : 5052512 , 2009求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法蔣興波呂肖慶劉成城李沫楠100871)200433)北京 100871 )1 （北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)研究所北京2 （第二軍醫(yī)大學(xué)衛(wèi)生勤務(wù)學(xué)教研室上海3（北京大學(xué)電子岀版新技術(shù)國(guó)家工程研究中心（lvxiaoqing cst. pku. edu. cn）A Dynamic 2Fit Heuristic Algorithm for the Rectangul

2、ar Strip Packing Problem1 21 311Jia ng Xin gbo , L u Xiao qing, Liu Chen gche ng , and Li Monan1 ( I nstitute of Computer Science and Technology , Peking Universit y , Beij ing 100871 )2 ( Department of Health Service , Second M ilitary Medical Universit y , Shanghai 200433)3 ( N ational Engineering

3、 Research Center of New Tech in Elect ronic Publishing , Peking Universit y , Beij ing 100871 )Abstract Given a set of small rectangular pieces of different sizes and a rectangular container of fixed widt h and infin ite len gt h , the recta ngular st rip pack ing problem (RSPP) con sist s of ort ho

4、go nally placing all the pieces wit hin the container , wit hout overlapping , such that the overall lengt h of the pack ing is mini mized. RSPP bel ongs to N P2hard problem in t heory and has many in dust rial applicatio ns such as the compositio n of n ews , the cutti ng of clot hi ng an d t he cu

5、tti ng of metal , etc. To solve the rectangular strip packing problem , a hybrid algorit hm , which combines a novel heuristic-r-l'includes 21 instances and thehm is morethe hybrid algorit(RSPP) ; hybridalgorit hm ;algorit hm dynamic2fit heuristic algorit hm (DF HA ) , wit h the genetic algorit

6、hm , is adopted. The DF HA algorit hm can dynamically select the better2fit rectangle for packing , according to the widt h2fit first (WFF) rule , the height2fit first ( HFF) rule , the placeable first ( PF) rule , and the biggest2 rectangle first (BRF) rule , and the evolutionary capability of gene

7、tic algorit hm is used to optimize the height of the packing which is calculated by DF HA. The hybrid algorit hm is tested on two sets of benchmark problems taken from the previous literat ure. The first set other one includes 13 instances. The computational result s show that effective than the exi

8、sting algorit hms from the previo us literat ure.Key words N P2hard problem ; rectangular strip packing problem dynamic2fit heuristic algorit hm (DF HA) ; genetic algorit hm (GA)，以期摘要矩形條帶裝箱問(wèn)題（RSPP）是指將一組矩形裝入在一個(gè)寬度固定高度不限的矩形容器中 獲得最小裝箱高度.RSPP理論上屬于NP難問(wèn)題，在新聞組版、布料下料以及金屬切割等工業(yè)領(lǐng)域中 有著廣泛的應(yīng)用.為解決該問(wèn)題，采用了一種混合算法，即將一種

9、新的啟發(fā)式算法一一態(tài)匹配算法一一遺傳算法結(jié)合起來(lái).混合算法中，動(dòng)態(tài)匹配算法能根據(jù) 4類啟發(fā)式規(guī)則動(dòng)態(tài)選擇與裝填區(qū)域相 匹配的下一個(gè)待裝矩形，同時(shí)將裝箱后所需容器高度用遺傳算法的進(jìn)化策略進(jìn)行優(yōu)化.對(duì)2組標(biāo)準(zhǔn)測(cè)試問(wèn)題的計(jì)算結(jié)果表明，相對(duì)于文獻(xiàn)中的已有算法，提出的算法更加有效.關(guān)鍵詞 NP難問(wèn)題；矩形條帶裝箱問(wèn)題；混合算法；動(dòng)態(tài)匹配啟發(fā)式算法；遺傳算法中圖法分類號(hào)TP301. 6收稿日期:2008 - 04 - 09 ;修回日期:2008-06-27通信作者:呂肖慶,010282531389 , lvxiaoqing cst. pku. edu. cn© 19弘酣妙 ChinaILlect

10、ionic PublishihgA lights reserved,http:/u-ctiki net蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#"© 1992009 Chilis Aeadeinrc JoumaS Llectr«nic Publishing llou Al rights reserved, http:/.V蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法507矩形條帶裝箱 (rectangular strip packing problem ,RSPP)是NP難問(wèn)題，其在工業(yè)領(lǐng)域中的應(yīng)用相當(dāng) 廣泛.目前,針對(duì)RSPP ,國(guó)內(nèi)外的相關(guān)學(xué)者

11、進(jìn)行了 大量的研究，并提出了各種各樣的算法，這些算法歸 納起來(lái)可以分為3類：精確算法、啟發(fā)式算法以及超 啟發(fā)式算法.相對(duì)而言，對(duì)精確算法的研究較早.Glmore與Gomory1 用線性規(guī)戈曜立了下料切割問(wèn)題的數(shù)學(xué) 模型,將線性規(guī)劃的求解轉(zhuǎn)化為一個(gè)背包子問(wèn)題，然后構(gòu)造出求解背包問(wèn)題的有效方法；對(duì)于一刀切下料切割問(wèn)題，Christofides等人2用樹(shù)搜索方法給出 了一個(gè)精確算法，而 Beasley則將該算法用于求解 二維非一刀切切割問(wèn)題；Hifi等人4給出了一種基于分枝定界方法，用于對(duì)中小規(guī)模二維裝箱問(wèn)題的 求解;Lesh等人針對(duì)二維完美裝箱問(wèn)題，提出了基于分枝定界的窮舉搜索算法，該算法已經(jīng)證明

12、對(duì)于規(guī)模小于30的裝箱問(wèn)題是有效的.由于精確算法為指數(shù)時(shí)間復(fù)雜度，因此解決小規(guī)模問(wèn)題較好.對(duì)于規(guī)模較大的裝箱問(wèn)題，常采用啟發(fā)式算法.目前比較經(jīng)典的啟發(fā)式算法是Baker等人6提出的BL (bottom 2left)算法、Chazelle提出 的BL F( bottom 2left fill )算法.與BL等算法不同 , Burke等人8提出了一種最佳匹配算法(best2fit ,B F)，該算法相對(duì)優(yōu)于 BL算法.除上面經(jīng)典啟發(fā)式 算法外，近年來(lái)出現(xiàn)了大量針對(duì)二維裝箱問(wèn)題的啟 發(fā)式算法，如Chen等人9給出A1算法;Cui等人10 提出 HRBB 算法；Beltr cn 等人11的 GRASP

13、 + VNS 算法；Alvarez2Valdes 等人12給出的 GRASP 算法；Hua ng等人13的HA算法以及張德富等 人14提出的PH算法等.啟發(fā)式算法只允許解的優(yōu)化結(jié)果朝著好的方向 單向遞增，因此較易陷入局部最優(yōu)解.而超啟發(fā)式算 法則允許部分較差解出現(xiàn)，并且能夠跳出局部最優(yōu)進(jìn)而在整個(gè)搜索空間進(jìn)行全局尋優(yōu).常見(jiàn)的超啟發(fā)式算法包括遺傳算法(genetic algorit hm ,GA)、模擬 退火(simulated annealing ,SA)算法、隨機(jī)搜索法 (random search , RS)、進(jìn)化算法 (na ve evalutio n , NE)、禁忌搜索(tabu se

14、arch ,TS)算法等.目前的研 究熱點(diǎn)是將超啟發(fā)式算法與啟發(fā)式算法相結(jié)合,形成一種較單純的啟發(fā)式算法更優(yōu)的混合算法. Bortfeldt 15提出了無(wú)任何編碼的GA ,并給出了求解RSPP的SPGAL算法;Zhang等人何針對(duì)矩形 裝箱問(wèn)題，給出了混合算法，該算法主要基于啟發(fā)式 遞歸策略和SA ;Dereli等人17則采用了 SA算法與 遞歸布局方法相混合來(lái)解決RSPP. Burke等人18將BF與超啟發(fā)式算法(GA ,SA ,TS) ,BL F算法結(jié)合起來(lái)，形成一種混合算法，該算法優(yōu)于單純的BF算法.在文獻(xiàn)19中，Hopper等人將 SA , GA , RS, N E等與BL ,BL F

15、啟發(fā)式算法相結(jié)合，并對(duì)不同問(wèn)題實(shí)例的綜合性能評(píng)價(jià)結(jié)果進(jìn)行了對(duì)比分析，得出:1) BL F的求解結(jié)果優(yōu)于 BL的求解結(jié)果，但BL F的 時(shí)間復(fù)雜度較高；2)混合算法的求解結(jié)果優(yōu)于單純 啟發(fā)式算法的求解結(jié)果；3)在啟發(fā)式算法相同的條 件下，混合算法求解結(jié)果從高到低(裝箱高度越低、 結(jié)果越好)依次為SA > GA ,N E > RS，但是SA的迭 代次數(shù)較多.迄今為止，雖然對(duì)RSPP進(jìn)行了大量的研究，取 得了一定的成績(jī)，但是從相關(guān)文獻(xiàn)給出的實(shí)驗(yàn)結(jié)果 上看，該問(wèn)題仍然有進(jìn)一步研究的必要.例如BL ,BL F等啟發(fā)式算法，它們?cè)趯?duì)矩形裝入過(guò)程中嚴(yán)格 按照矩形的某個(gè)裝入序列進(jìn)行，容易產(chǎn)生較大的

16、空洞，浪費(fèi)空間.BF算法由于按照大面積矩形優(yōu)先裝 入，容易產(chǎn)生階梯狀的排版結(jié)果，且在階梯邊緣處易 產(chǎn)生大量的較小空洞.本文提出了一種新的啟發(fā)式算法 ，即動(dòng)態(tài)匹配啟 發(fā)式算法(dynamic2fit heuristic algorithm ,DFHA )，并 與GA相結(jié)合形成混合算法來(lái)解決 RSPP.1 RSPP模型1. 1問(wèn)題描述RSPP是指將n個(gè)不同規(guī)格的矩形n,力，, rn裝入在寬度 W固定、長(zhǎng)度L不限的矩形容器 T 中，要求裝完所有矩形后占用高度H packing最小.在矩形的裝入過(guò)程中，要求滿足：1) 對(duì)于任意整數(shù)i, j 1 , n , i豐j, ri , rj互不 重疊;2)門必須

17、裝入在矩形容器 T內(nèi)，即不能超出容 器T的寬度 W;3) r的邊必須與矩形容器 T的邊平 行，即滿足正交性 r可以90°旋轉(zhuǎn).1.2相關(guān)定義坐標(biāo)系：采用直角坐標(biāo)系，矩形容器的左下角為 坐標(biāo)原點(diǎn)，容器寬度所在方向?yàn)闄M坐標(biāo)X ,長(zhǎng)度所在方向?yàn)榭v坐標(biāo)Y.裝入序列：n個(gè)矩形的一個(gè)裝入序列表示為n =(n(1) , n(2),n(n).其中 n (i) (i = 1 ,2 ,n) 表示矩形編號(hào),n(i) 1 , n，對(duì)任意i ,j 1 , n,當(dāng) i Mj時(shí),n (i) Mn (j).設(shè)imd表示編號(hào)為 n (i)的矩 形，它由五元組構(gòu)成，即厲= x , y , w , h , 0,其中 ED

18、 .x, rn(i) . y分別表示該矩形裝入后，其左下角的橫坐標(biāo)、縱坐標(biāo),r«( i). w , r«(i) . h, n(i).0分別表示該矩 形的寬度、高度、旋轉(zhuǎn)角度.裝入輪廓線：矩形裝入過(guò)程中產(chǎn)生的輪廓線集 合用隊(duì)列C = ei,e2,em表示，其中元素ek為水 平線線段，它由三元組構(gòu)成，即ek = x,y,w,其中， 8.x,ek.y表示第k個(gè)水平線線段的左端點(diǎn)坐標(biāo)(起點(diǎn)坐標(biāo));ek. w表示第k個(gè)水平線線段的寬度；并且 對(duì)任意 0<k< m,有 ek.x<ek+i.x,且 ek. y ek+1. y. 所有線段長(zhǎng)度之和等于容器的寬度.最低水平線

19、：最低水平線定義為隊(duì)列C中其y坐標(biāo)最小的水平線(如有多個(gè)，取x坐標(biāo)最小的水 平線).最優(yōu)解Hopt : Hopt表示窮舉所有可能情況得到 的最小裝箱高度，也稱最優(yōu)裝箱高度.裝箱咼度 Hpacking : Hpacking表示根據(jù)當(dāng)前裝入序 列,按照裝箱算法將所有矩形裝入矩形容器T內(nèi)所得到的最小咼度.空洞：空洞是指在裝箱過(guò)程中由矩形或者矩形 與容器邊界(如x=0,y=0,x=W 或者y = Hpacking ) 圍成的空白區(qū).空洞越多，面積越大，材料的浪費(fèi)就 越多.2 DFHA設(shè)計(jì)2. 1 基本思想對(duì)于NP難問(wèn)題，最直接的方式是通過(guò)搜索的 方法在整個(gè)解空間中尋找最優(yōu)解或者滿意解.當(dāng)問(wèn)題規(guī)模較大時(shí)

20、，這種盲目搜索就變得十分困難，甚至根本不可行.因此相關(guān)學(xué)者常利用問(wèn)題解本身的某 些結(jié)構(gòu)特征來(lái)構(gòu)造出一些啟發(fā)式規(guī)則，并按照該規(guī)則設(shè)計(jì)出啟發(fā)式算法，由該算法來(lái)求得問(wèn)題的一個(gè) 滿意解.對(duì)于矩形條帶裝箱問(wèn)題，它有以下幾個(gè)可以利 用的結(jié)構(gòu)特征:1)面積較大的矩形裝入后易產(chǎn)生較 大的空洞，面積較小的矩形裝入后只產(chǎn)生較小的空 洞;2)較大的空洞常常可以裝入面積較小的矩形；3)裝入過(guò)程中產(chǎn)生的輪廓線越平滑，即組成輪廓線的水平線數(shù)量越少，就越有利于后期矩形的裝入. 2.2啟發(fā)規(guī)則設(shè)計(jì)DF HA利用了矩形條帶裝箱問(wèn)題的3個(gè)結(jié)構(gòu)特征，設(shè)計(jì)出了 4個(gè)啟發(fā)式規(guī)則，即寬度匹配優(yōu)先、 高度匹配優(yōu)先、可裝入優(yōu)先以及大矩形優(yōu)先

21、.寬度匹 配優(yōu)先規(guī)則可以減少空洞的產(chǎn)生，特別在裝入初期, 由于用來(lái)與可裝區(qū)域進(jìn)行比較的矩形較多，因此能匹配上的概率就越大，從而產(chǎn)生空洞的概率就越小；高度匹配優(yōu)先規(guī)則使得裝箱輪廓相對(duì)規(guī)整；可裝入優(yōu)先規(guī)則在一定程度上可以避免產(chǎn)生階梯狀裝箱結(jié) 果,從而降低在階梯邊緣處產(chǎn)生較小空洞的可能性；高度匹配優(yōu)先、可裝入優(yōu)先以及大矩形優(yōu)先規(guī)則可 以將較小矩形延后裝入.4種啟發(fā)式規(guī)則結(jié)合起來(lái)不但可使矩形裝入后產(chǎn)生的空洞數(shù)量較少，而且所有空洞總面積也相對(duì)較小.1) 寬度匹配優(yōu)先(width2fit first ,WFF)WFF是指在所有待裝矩形中，優(yōu)先裝入寬度或 高度與最低水平線 Q等寬的矩形.如存在多個(gè)匹配 矩形

22、，優(yōu)先裝入面積最大的.WFF不會(huì)增加裝入輪 廓線數(shù)量，不會(huì)在最低水平線 ek上產(chǎn)生新的更小的 可裝入?yún)^(qū)域，從而降低了產(chǎn)生空洞的可能性 .2) 高度匹配優(yōu)先(heights first ,HFF )HFF是指在所有待裝矩形中，優(yōu)先裝入寬度或 高度不大于最低水平線 ek寬度、且裝入后能實(shí)現(xiàn)左 填平的矩形.如存在多個(gè)匹配矩形，則裝入面積最 大的.3) 可裝入優(yōu)先(placeable first ,PF)PF是指在一定范圍內(nèi)從待裝矩形中按照裝入序列依次查找寬度或高度不大于最低水平線ek寬度的矩形，如存在，則裝入.如存在多個(gè)匹配矩形，則裝 入面積最大的.4) 大矩形優(yōu)先(biggest2rectangl

23、e first ,BRF)BRF是指在待裝矩形中，優(yōu)先裝入寬度或高度 不大于最低水平線8寬度的矩形.如存在多個(gè)可裝矩形，則裝入面積最大的.與PF不同是的,BRF查 詢的是所有待裝矩形.2. 3 DFHA 實(shí)現(xiàn)DF HA的算法流程如下.procedure D F H A (inp ut : n , outp ut: H packing )I n it Coordi nate (r«);I n it Con tours (C);H packing = 0 ; n3初始化裝箱高度3 nfor (i = 1 ; i < n + 1 ; i + + )1) if (rm . x >

24、 - 1) continue ; n3 矩形已被裝 入3 n在C中取最低水平線ek;j = - 1 ;n3用于裝入的矩形所在序列號(hào)3 nWFF(i, n, ek , j) ; if (j > - 1) goto 3);H F F( i, n , 8 , j) ; if (j > - 1) goto 3);P F (i, n , ek, n 16, j) ; if (j > - 1) goto 3);BRF(i, n, e<, j) ; if (j > - 1) goto 3);2) 合并C中的邊；轉(zhuǎn)1);3) 將n(j)號(hào)對(duì)應(yīng)的矩形"裝入在C中的最 低水

25、 平線ek上;如果未旋轉(zhuǎn)，貝U Hpacking = max (Hpacking , rnj) . X + "(j) . h ),否貝U Hpacking = maX (Hpacking ,加.X + "(j) . w)；更新 "(j)的坐標(biāo)和集合C;如果j > i,轉(zhuǎn)1);"© 1992009 Chilis Aeadeinrc JoumaS Llectr«nic Publishing llou Al rights reserved, http:/.V蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#a"©

26、 1992009 Chilis Aeadeinrc JoumaS Llectr«nic Publishing llou Al rights reserved, http:/.V蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#end for3.3交叉© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法511end procedure其中I nit Coordi nate ( rn)是對(duì)所有矩形塊的坐 標(biāo)

27、x , y進(jìn)行初始化，即對(duì)任意j 1, n(j).x = rn(j) .y = - 1.I nit Contours ( C)對(duì)裝箱輪廓線進(jìn)行初始化.在初始階段，由于容器T未被裝入，因此其輪廓線僅 由一個(gè)水平線線段構(gòu)成 ，即C = e,其中e = 0, 0 ,W ,W為容器T的寬度.WFF () , H FF() , PF() ,BRF()分另U表示按照 WFF ,HFF ,PF以及BRF啟發(fā)式規(guī)則在隊(duì)列n中第i位開(kāi)始依次查找與最低水平線ek相匹配矩形的查詢過(guò)程，其返回值為 j.其中PF()的查詢范圍為 nn.3 GA + DFHA 設(shè)計(jì)3. 1 GA + DFHA算法流程本文中采用了遺傳算法

28、GA與DF HA相結(jié)合的方式來(lái)解決RSPP，其算法流程如下.金那駕1|_監(jiān)食=procedure GA_D F H A ()編碼；k = 0;隨機(jī)產(chǎn)生m個(gè)個(gè)體組成初始群體pop(k) = n ,n2 , ,nm;對(duì)單個(gè)個(gè)體 n執(zhí)行D F H A (n , Hpacking );記 錄個(gè)體適應(yīng)度 f (ni) (f (ni) = 1 n Hpacking (n);判斷是否滿足停止條件.若是，則停止計(jì)算，輸 出最佳結(jié)果；否則：利用排序選擇操作產(chǎn)生新的群體sel pop ( k +1);根據(jù)交叉概率Pc進(jìn)行交叉操作，產(chǎn)生群體 cross pop ( k + 1);根據(jù)變異概率Pm進(jìn)行變異操作，產(chǎn)生群

29、體 mutpop (k + 1);pop( k + 1) = mutpop ( k+ 1) ; k = k + 1;返回 end procedure3.2編碼與選擇矩形裝箱采用整數(shù)編碼，即n個(gè)矩形分別用整 數(shù)1 ,2,n編號(hào),矩形的一個(gè)裝入序列對(duì)應(yīng)一個(gè)染 色體編碼.例如：個(gè)體n的染色體編碼為(-6158- 3 2 - 74 - 9),表示裝入序列為 6 1 5 8 3 2 74 9, 在裝入過(guò)程中，編號(hào)為6,3,7 ,9的矩形進(jìn)行90°旋轉(zhuǎn).本文在采用排序選擇方法來(lái)生成下一代個(gè)體的 同時(shí),還混合使用了最優(yōu)保存策略.交叉是產(chǎn)生新個(gè)體的主要方法，本文主要采用雙點(diǎn)交叉.首先隨機(jī)生成起止交叉

30、點(diǎn)Pcr1 , Pcr2 1 ,n;其次將配對(duì)個(gè)體Rr1到Pcr2之間的基因進(jìn)行互換;最后依次將未出現(xiàn)的父代基因填入子代對(duì)應(yīng)的 空白基因位上.例如：n = ( - 6 1 5 8 - 3 2 - 7 4 - 9) , n = (3 5 - 9 8 - 2 4 1 7 6),起止交叉點(diǎn) Pc“ , Pcr2分別為2 , 6,則交叉后產(chǎn)生的個(gè)體編碼為n； = ( - 6 5 - 9 8-241 - 3 - 7) , n； = ( - 9 1 5 8 - 3 2 4 7 6). 3.4變異本文變異包括2部分：一是旋轉(zhuǎn)變異；二是裝入 序列變異.1) 旋轉(zhuǎn)變異旋轉(zhuǎn)變異采用了單點(diǎn)取反和部分取反2種方式.單

31、點(diǎn)取反變異是指隨機(jī)選擇單個(gè)基因進(jìn)行取反變異.例如，對(duì)于個(gè)體 n = (n (1) , n (2),n ( i),n( n),取隨機(jī)變異點(diǎn)i,則變異后產(chǎn)生的新個(gè)體 為 n； = (n (1) ,n(2),，-n(i),n(n).部分取反變異指隨機(jī)生成起止變異點(diǎn)Pmu1 ,Pmu2 1, n;然后將Pmu1到Pmu2之間的基因取反.2) 裝入序列變異裝入序列變異采用了兩點(diǎn)位置互換、部分逆轉(zhuǎn)與首部逆轉(zhuǎn)3種方式.兩點(diǎn)位置互換變異首先隨機(jī)生成 2個(gè)變異點(diǎn)i, j 1, n;然后將2個(gè)基因互換.例如：n = (n(1) , n (2),n (i1),，n (i2) , :n (n) , N , i2 1

32、, n, 則變異后產(chǎn)生的新個(gè)體為n； = (n (1) , n (2),n(i2),，n(h),，n( n).部分逆轉(zhuǎn)變異首先隨機(jī)生成起止變異點(diǎn)Pmu1 ,Pmu2 1 , n;然后將Pmu1到Pmu2之間的基因逆轉(zhuǎn).首部逆轉(zhuǎn)變異首先隨機(jī)生成變異點(diǎn)Pmu 1 ,n;然后將1至U Pmu之間的基因逆轉(zhuǎn).在所有變異個(gè)體中，單點(diǎn)取反、部分取反、兩點(diǎn) 位置互換、部分逆轉(zhuǎn)、首部逆轉(zhuǎn)所占比例分別為10 % ,20 % ,50 % ,10%,10 %.4實(shí)驗(yàn)對(duì)比為了驗(yàn)證 GA + DF HA的有效性，本文給出了 2組實(shí)驗(yàn)結(jié)果對(duì)比，其所用實(shí)例分別來(lái)自于文獻(xiàn)19 和文獻(xiàn)8 . GA + DF HA用C+ +編程

33、實(shí)現(xiàn).實(shí)驗(yàn)平臺(tái):Pentium 4 3.0 GHz ,512MB memory.運(yùn)行參數(shù)：交叉概率Pc =0.9 ,變異概率Pm = 實(shí)驗(yàn)1在文獻(xiàn)19 中,Hopper等人給出了 21組不同 尺寸的實(shí)驗(yàn)實(shí)例，這些實(shí)例分成7個(gè)大類，每個(gè)大類 由3組實(shí)例組成，其矩形個(gè)數(shù)從16197個(gè)不等.每 個(gè)實(shí)例的最優(yōu)解 Hopt已經(jīng)給出，其相關(guān)數(shù)據(jù)見(jiàn)文獻(xiàn)19.在本文算法中，群體大小設(shè)為 50 ,終止條件為最大進(jìn)化代數(shù)等于3000，或者裝箱咼度Hpacking等于最優(yōu)解Hopt .對(duì)每組實(shí)驗(yàn)實(shí)例重復(fù)運(yùn)行20次，記錄每個(gè)大類60次（每個(gè)大類3個(gè)實(shí)例，每個(gè)實(shí)例進(jìn)行 20次實(shí)驗(yàn)）實(shí)驗(yàn)的平均裝箱高度到最優(yōu)

34、裝箱高度的 相對(duì)距離 Hrd = （60 次平均 Hpacking - Hopt ） nHopt X 100 %.實(shí)驗(yàn)結(jié)果對(duì)比如表1所示：© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟

35、發(fā)式算法#Table 1 Computational Results of Nine Algorithms ( Hrd)表1 9種算法的實(shí)驗(yàn)結(jié)果Hrd%Algorit hmC1C2C3C4C5C6C7MeanGRASP + VNS 11 14. 4017. 3312. 936. 804. 513. 552. 898. 92SA + HR16 5. 004. 472. 232. 221. 862. 53. 243. 07SPGAL 15 1. 700. 902. 201. 400. 000. 700. 501. 00Hybrid SA171. 664. 884. 003. 943. 183. 3

36、03. 383. 48A190. 000. 001. 111. 671. 110. 830. 420. 73ph145. 004. 444. 443. 331. 111. 111. 252. 95HRBB 101. 700. 001. 102. 201. 901. 401. 301. 40GRASP 12 0. 000. 001. 081. 641. 101. 561. 361. 33GA + DFHA0. 000. 000. 670. 220. 000. 560. 420. 27© 1994-20China Academic Jcunial Elect!onic Publishin

37、g House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#從表1中可以看出，本文給出的 GA + DF HA 算法獲得的Hrd最小為0、最大為0.67,平均相對(duì)距 離（Mean）為0. 27 ,比其他10種算法中獲得的最小 平均相對(duì)距離（A1 :0.73）減少了 0. 46個(gè)百分點(diǎn).在 7大類實(shí)例中

38、，有3大類實(shí)例的 Hrd為0，即對(duì)應(yīng)的 所有實(shí)例20次實(shí)驗(yàn)結(jié)果皆取得了最優(yōu)解；而其他算 法中，至多有 2大類（A1 , GRASP）的 Hrd為0.因 此,實(shí)驗(yàn)結(jié)果表明，針對(duì)RSPP,本文提出的 GA +DFHA算法相對(duì)更優(yōu).表2給出了上述所有算法的計(jì)算時(shí)間.由于本文算法采用了裝箱高度等于最優(yōu)解作為終止運(yùn)行條 件之一，因此，雖然C5的規(guī)模（即被裝入矩形的個(gè) 數(shù)）大于C4,但由于其獲得最優(yōu)解的進(jìn)化代數(shù)相對(duì) 較小，所以其運(yùn)行時(shí)間略小于 C4.本文給出的GA + DF HA的算法復(fù)雜度為 O（n2）.© 1994-20China Academic Jcunial Elect!onic Pu

39、blishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#Table 2 Run Times of Nine Algorithms表2 9種算法的運(yùn)行時(shí)間sAlgorit hmC1C2C3C4C5C6C7MeanGRASP + VNS 11 0. 000. 000. 000. 000.

40、 020. 071. 370. 21SA + HR16 23. 0053. 5074. 00212. 50429. 50556. 121661. 00430. 75SPGAL 15 -139. 00Hybrid SA173. 646. 3618. 78101. 20287. 27757. 201650. 6403. 57A1 9 0. 370. 611. 710. 150. 403. 9845. 027. 46PH 140. 000. 000. 001. 515. 6923. 74707. 12105. 45HRBB 100. 270. 330. 882. 192. 832. 244. 261

41、. 86GRASP 12 -60. 00GA + DFHA0. 010. 044.2311.315. 0574.85290.5855. 15 Pentium 166 M Hz and 96 MB RAM Dell GX270 wit ha3.0 GHz CPU Pentium PC wit h 2 GHz2. 4 GHz PC wit h 512 MB memory Pentium 4 2. 8 GHz , 512 MB memory Pentium 川 797 M Hz Pentium 4 1.6 GHz , 256 MB memory Pentium 4 mobile 2. 0 GHz ,

42、 512 MB memory© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#© 1994-20China Academic Jcunial Elect!onic Pu

43、blishing House. All rights reser-ed. http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#表 3 給出了 GRASP + VNS , GRASP , HRBB 以及本文的 GA + DF HA對(duì)21組實(shí)例求得的實(shí)際 實(shí)驗(yàn)結(jié)果 Hpacking .在對(duì)21組實(shí)例的實(shí)驗(yàn)中，每次實(shí) 驗(yàn)皆能獲得最優(yōu)解Hopt的實(shí)例GA + DF HA有12組，而 GRASP為8組，HRBB為7組；至少獲得 1 次最優(yōu)解（即最小裝箱高度 Hmin =最優(yōu)解Hopt ）的實(shí) 例 GA + DFHA 有 18 組,而 GRASP 為 8 組,HRBB 為9組；GA + DF H

44、A獲得的最大裝箱咼度 Hmax與 最優(yōu)解Hopt之間的距離最多為1個(gè)基本單位.因此, 無(wú)論是最優(yōu)解所占比例 ，還是最小裝箱高度 Hmin、 平均裝箱高度 Havg以及最大裝箱高度 Hmax ,相對(duì)于GRASP + VNS , GRASP 與 HRBB 3 種算法,GA + DF HA算法的求解結(jié)果更優(yōu).C 1994-2009 China Academic Jcuma Llectronic Pug Mouse. A rights reserved, http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#C 1994-2009 China Academic Jcuma Llectronic

45、 Pug Mouse. A rights reserved, http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#Table 3 Computational Results of Twenty2One Instances表321組實(shí)例計(jì)算結(jié)果比較Belt r cn11 Alvarez 2Valdes 12 Cui10 GA + DF HAGRASP + VNSGRASPHRBBInstanceHoptn(20 runs)(10 runs)(6 runs)(20 runs)H minH avgH maxH minH avgH minH avgH maxH minH avgH maxC1

46、120162122. 30232020. 002020. 00202020. 0020C1220172123. 20252020. 002121. 00212020. 0020C1320162223. 15242020. 002020. 00202020. 0020C2115251617. 20191515. 001515. 00151515. 0015C2215251618. 00201515. 001515. 00151515. 0015C2315251617. 60201515. 001515. 00151515. 0015C3130283232. 55343030. 003030. 0

47、0303030. 0030C3230293234. 25373131. 003131. 00313030. 6031C3330283334. 85373030. 003030. 00303030. 0030C4160496363. 55666161. 006060. 50616060. 3061C4260496164. 60686161. 006161. 33626060. 0060C4360496264. 10666161. 006161. 00616060. 1061C5190739293. 45959191. 009090. 67919090. 0090C5290739394. 7597

48、9191. 009292. 00929090. 0090C5390739294. 00989191. 009191. 17929090. 0090C6112097123124. 40130121121. 90121121. 00121120120. 60121C6212097123124. 65128121121. 90121121. 83122120120. 50121C6312097122123. 75126121121. 90121121. 33122120120. 90121C71240196244246. 45248244244. 00242242. 002

49、41C72240197244247. 05255242242. 90245245. 00245241241. 00241C73240196245247. 30258243243. 00241241. 33242241241. 00241C 1994-2009 China Academic Jcuma Llectronic Pug Mouse. A rights reserved, http:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法#C 1994-2009 China Academic Jcuma Llectronic Pug Mouse. A rights reserved, htt

50、p:蔣興波等：求解矩形條帶裝箱問(wèn)題的動(dòng)態(tài)匹配啟發(fā)式算法5154.2 實(shí)驗(yàn)2文獻(xiàn)8給出了 13組標(biāo)準(zhǔn)實(shí)驗(yàn)實(shí)例，其待排矩 形數(shù)量n從103152不等，容器寬度 W和最優(yōu)解 H opt已經(jīng)給出.在本文的算法中 ，群體大小仍設(shè)為 50,終止條件為最大進(jìn)化代數(shù)等于3000（其中N12為100 ,N13為5），或者裝箱咼度Hpackin等于最優(yōu)解Hopt ;對(duì)每組實(shí)驗(yàn)實(shí)例重復(fù)運(yùn)行20次.實(shí)驗(yàn)結(jié)果見(jiàn)表4.從表4可以看出，GA + DF HA算法在對(duì)該組 實(shí)例的實(shí)驗(yàn)中,20次均獲得最優(yōu)解（即Havg = Hopt） 的有6組，而其他算法中至多只有3組（HA ） . 20次實(shí)驗(yàn)中，GA+DFHA算法對(duì)10組實(shí)例

51、皆獲得了至 少1次最優(yōu)解，遠(yuǎn)遠(yuǎn)高于其他算法，而算法獲得的最 大裝箱高度（Hmax）與最優(yōu)解之間除 N5相差2個(gè)基 本單位 外，其余至多相差1個(gè)基本單位 GA + DF HA求解N1至N13的平均運(yùn)行時(shí)間分別為0 ,0. 02,0. 33,25. 75,35. 45,2. 25,53. 00, 71. 95 , 29. 50 ,66. 35 ,6. 00 ,65. 00 ,108. 75，單位為 s.而 HA 算法所用時(shí)間（見(jiàn)文獻(xiàn)13）遠(yuǎn)遠(yuǎn)大于GA + DF HA.因此，相對(duì)而言，GA + DF HA 對(duì)求解 RSPP 具有較明顯的優(yōu)勢(shì).Table 4Computational Results

52、of Five Algorithms for Thirteen Instances表413組實(shí)例計(jì)算結(jié)果InstanceWH optnBFBF + TS BF + SA BF + GAGRASPHAH minHminH minH minH minH avgH minHminH avgH maxN1404010454040404040404040. 0040N2305020535050505050505050. 0050N3305030525151525151505050. 0050N4808040868382838181818080. 9081N510010050105103103104102102102100101. 55102N65010060102102102102101101101100100. 00100N78010070108105104104101101101100100. 95101N8