求解矩形条带装箱问题的动态匹配启发式算法

1、计算机研究与发展Journal of Computer Research and DevelopmentISSN 100021239ICN 1121777 UP46(3) : 5052512 , 2009求解矩形条带装箱问题的动态匹配启发式算法蒋兴波吕肖庆刘成城李沫楠100871)200433)北京 100871 )1 （北京大学计算机科学技术研究所北京2 （第二军医大学卫生勤务学教研室上海3（北京大学电子岀版新技术国家工程研究中心（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)，以期摘要矩形条带装箱问题（RSPP）是指将一组矩形装入在一个宽度固定高度不限的矩形容器中 获得最小装箱高度.RSPP理论上属于NP难问题，在新闻组版、布料下料以及金属切割等工业领域中 有着广泛的应用.为解决该问题，采用了一种混合算法，即将一种

9、新的启发式算法一一态匹配算法一一遗传算法结合起来.混合算法中，动态匹配算法能根据 4类启发式规则动态选择与装填区域相 匹配的下一个待装矩形，同时将装箱后所需容器高度用遗传算法的进化策略进行优化.对2组标准测试问题的计算结果表明，相对于文献中的已有算法，提出的算法更加有效.关键词 NP难问题；矩形条带装箱问题；混合算法；动态匹配启发式算法；遗传算法中图法分类号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蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#"© 1992009 Chilis Aeadeinrc JoumaS Llectr«nic Publishing llou Al rights reserved, http:/.V蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法507矩形条带装箱 (rectangular strip packing problem ,RSPP)是NP难问题，其在工业领域中的应用相当 广泛.目前,针对RSPP ,国内外的相关学者

11、进行了 大量的研究，并提出了各种各样的算法，这些算法归 纳起来可以分为3类：精确算法、启发式算法以及超 启发式算法.相对而言，对精确算法的研究较早.Glmore与Gomory1 用线性规戈曜立了下料切割问题的数学 模型,将线性规划的求解转化为一个背包子问题，然后构造出求解背包问题的有效方法；对于一刀切下料切割问题，Christofides等人2用树搜索方法给出 了一个精确算法，而 Beasley则将该算法用于求解 二维非一刀切切割问题；Hifi等人4给出了一种基于分枝定界方法，用于对中小规模二维装箱问题的 求解;Lesh等人针对二维完美装箱问题，提出了基于分枝定界的穷举搜索算法，该算法已经证明

12、对于规模小于30的装箱问题是有效的.由于精确算法为指数时间复杂度，因此解决小规模问题较好.对于规模较大的装箱问题，常采用启发式算法.目前比较经典的启发式算法是Baker等人6提出的BL (bottom 2left)算法、Chazelle提出 的BL F( bottom 2left fill )算法.与BL等算法不同 , Burke等人8提出了一种最佳匹配算法(best2fit ,B F)，该算法相对优于 BL算法.除上面经典启发式 算法外，近年来出现了大量针对二维装箱问题的启 发式算法，如Chen等人9给出A1算法;Cui等人10 提出 HRBB 算法；Beltr cn 等人11的 GRASP

13、 + VNS 算法；Alvarez2Valdes 等人12给出的 GRASP 算法；Hua ng等人13的HA算法以及张德富等 人14提出的PH算法等.启发式算法只允许解的优化结果朝着好的方向 单向递增，因此较易陷入局部最优解.而超启发式算 法则允许部分较差解出现，并且能够跳出局部最优进而在整个搜索空间进行全局寻优.常见的超启发式算法包括遗传算法(genetic algorit hm ,GA)、模拟 退火(simulated annealing ,SA)算法、随机搜索法 (random search , RS)、进化算法 (na ve evalutio n , NE)、禁忌搜索(tabu se

14、arch ,TS)算法等.目前的研 究热点是将超启发式算法与启发式算法相结合,形成一种较单纯的启发式算法更优的混合算法. Bortfeldt 15提出了无任何编码的GA ,并给出了求解RSPP的SPGAL算法;Zhang等人何针对矩形 装箱问题，给出了混合算法，该算法主要基于启发式 递归策略和SA ;Dereli等人17则采用了 SA算法与 递归布局方法相混合来解决RSPP. Burke等人18将BF与超启发式算法(GA ,SA ,TS) ,BL F算法结合起来，形成一种混合算法，该算法优于单纯的BF算法.在文献19中，Hopper等人将 SA , GA , RS, N E等与BL ,BL F

15、启发式算法相结合，并对不同问题实例的综合性能评价结果进行了对比分析，得出:1) BL F的求解结果优于 BL的求解结果，但BL F的 时间复杂度较高；2)混合算法的求解结果优于单纯 启发式算法的求解结果；3)在启发式算法相同的条 件下，混合算法求解结果从高到低(装箱高度越低、 结果越好)依次为SA > GA ,N E > RS，但是SA的迭 代次数较多.迄今为止，虽然对RSPP进行了大量的研究，取 得了一定的成绩，但是从相关文献给出的实验结果 上看，该问题仍然有进一步研究的必要.例如BL ,BL F等启发式算法，它们在对矩形装入过程中严格 按照矩形的某个装入序列进行，容易产生较大的

16、空洞，浪费空间.BF算法由于按照大面积矩形优先装 入，容易产生阶梯状的排版结果，且在阶梯边缘处易 产生大量的较小空洞.本文提出了一种新的启发式算法 ，即动态匹配启 发式算法(dynamic2fit heuristic algorithm ,DFHA )，并 与GA相结合形成混合算法来解决 RSPP.1 RSPP模型1. 1问题描述RSPP是指将n个不同规格的矩形n,力，, rn装入在宽度 W固定、长度L不限的矩形容器 T 中，要求装完所有矩形后占用高度H packing最小.在矩形的装入过程中，要求满足：1) 对于任意整数i, j 1 , n , i丰j, ri , rj互不 重叠;2)门必须

17、装入在矩形容器 T内，即不能超出容 器T的宽度 W;3) r的边必须与矩形容器 T的边平 行，即满足正交性 r可以90°旋转.1.2相关定义坐标系：采用直角坐标系，矩形容器的左下角为 坐标原点，容器宽度所在方向为横坐标X ,长度所在方向为纵坐标Y.装入序列：n个矩形的一个装入序列表示为n =(n(1) , n(2),n(n).其中 n (i) (i = 1 ,2 ,n) 表示矩形编号,n(i) 1 , n，对任意i ,j 1 , n,当 i Mj时,n (i) Mn (j).设imd表示编号为 n (i)的矩 形，它由五元组构成，即厲= x , y , w , h , 0,其中 ED

18、 .x, rn(i) . y分别表示该矩形装入后，其左下角的横坐标、纵坐标,r«( i). w , r«(i) . h, n(i).0分别表示该矩 形的宽度、高度、旋转角度.装入轮廓线：矩形装入过程中产生的轮廓线集 合用队列C = ei,e2,em表示，其中元素ek为水 平线线段，它由三元组构成，即ek = x,y,w,其中， 8.x,ek.y表示第k个水平线线段的左端点坐标(起点坐标);ek. w表示第k个水平线线段的宽度；并且 对任意 0<k< m,有 ek.x<ek+i.x,且 ek. y ek+1. y. 所有线段长度之和等于容器的宽度.最低水平线

19、：最低水平线定义为队列C中其y坐标最小的水平线(如有多个，取x坐标最小的水 平线).最优解Hopt : Hopt表示穷举所有可能情况得到 的最小装箱高度，也称最优装箱高度.装箱咼度 Hpacking : Hpacking表示根据当前装入序 列,按照装箱算法将所有矩形装入矩形容器T内所得到的最小咼度.空洞：空洞是指在装箱过程中由矩形或者矩形 与容器边界(如x=0,y=0,x=W 或者y = Hpacking ) 围成的空白区.空洞越多，面积越大，材料的浪费就 越多.2 DFHA设计2. 1 基本思想对于NP难问题，最直接的方式是通过搜索的 方法在整个解空间中寻找最优解或者满意解.当问题规模较大时

20、，这种盲目搜索就变得十分困难，甚至根本不可行.因此相关学者常利用问题解本身的某 些结构特征来构造出一些启发式规则，并按照该规则设计出启发式算法，由该算法来求得问题的一个 满意解.对于矩形条带装箱问题，它有以下几个可以利 用的结构特征:1)面积较大的矩形装入后易产生较 大的空洞，面积较小的矩形装入后只产生较小的空 洞;2)较大的空洞常常可以装入面积较小的矩形；3)装入过程中产生的轮廓线越平滑，即组成轮廓线的水平线数量越少，就越有利于后期矩形的装入. 2.2启发规则设计DF HA利用了矩形条带装箱问题的3个结构特征，设计出了 4个启发式规则，即宽度匹配优先、 高度匹配优先、可装入优先以及大矩形优先

21、.宽度匹 配优先规则可以减少空洞的产生，特别在装入初期, 由于用来与可装区域进行比较的矩形较多，因此能匹配上的概率就越大，从而产生空洞的概率就越小；高度匹配优先规则使得装箱轮廓相对规整；可装入优先规则在一定程度上可以避免产生阶梯状装箱结 果,从而降低在阶梯边缘处产生较小空洞的可能性；高度匹配优先、可装入优先以及大矩形优先规则可 以将较小矩形延后装入.4种启发式规则结合起来不但可使矩形装入后产生的空洞数量较少，而且所有空洞总面积也相对较小.1) 宽度匹配优先(width2fit first ,WFF)WFF是指在所有待装矩形中，优先装入宽度或 高度与最低水平线 Q等宽的矩形.如存在多个匹配 矩形

22、，优先装入面积最大的.WFF不会增加装入轮 廓线数量，不会在最低水平线 ek上产生新的更小的 可装入区域，从而降低了产生空洞的可能性 .2) 高度匹配优先(heights first ,HFF )HFF是指在所有待装矩形中，优先装入宽度或 高度不大于最低水平线 ek宽度、且装入后能实现左 填平的矩形.如存在多个匹配矩形，则装入面积最 大的.3) 可装入优先(placeable first ,PF)PF是指在一定范围内从待装矩形中按照装入序列依次查找宽度或高度不大于最低水平线ek宽度的矩形，如存在，则装入.如存在多个匹配矩形，则装 入面积最大的.4) 大矩形优先(biggest2rectangl

23、e first ,BRF)BRF是指在待装矩形中，优先装入宽度或高度 不大于最低水平线8宽度的矩形.如存在多个可装矩形，则装入面积最大的.与PF不同是的,BRF查 询的是所有待装矩形.2. 3 DFHA 实现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用于装入的矩形所在序列号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中的边；转1);3) 将n(j)号对应的矩形"装入在C中的最 低水

25、 平线ek上;如果未旋转，贝U Hpacking = max (Hpacking , rnj) . X + "(j) . h ),否贝U Hpacking = maX (Hpacking ,加.X + "(j) . w)；更新 "(j)的坐标和集合C;如果j > i,转1);"© 1992009 Chilis Aeadeinrc JoumaS Llectr«nic Publishing llou Al rights reserved, http:/.V蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#a"©

26、 1992009 Chilis Aeadeinrc JoumaS Llectr«nic Publishing llou Al rights reserved, http:/.V蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#end for3.3交叉© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法511end procedure其中I nit Coordi nate ( rn)是对所有矩形块的坐 标

27、x , y进行初始化，即对任意j 1, n(j).x = rn(j) .y = - 1.I nit Contours ( C)对装箱轮廓线进行初始化.在初始阶段，由于容器T未被装入，因此其轮廓线仅 由一个水平线线段构成 ，即C = e,其中e = 0, 0 ,W ,W为容器T的宽度.WFF () , H FF() , PF() ,BRF()分另U表示按照 WFF ,HFF ,PF以及BRF启发式规则在队列n中第i位开始依次查找与最低水平线ek相匹配矩形的查询过程，其返回值为 j.其中PF()的查询范围为 nn.3 GA + DFHA 设计3. 1 GA + DFHA算法流程本文中采用了遗传算法

28、GA与DF HA相结合的方式来解决RSPP，其算法流程如下.金那駕1|_監食=procedure GA_D F H A ()编码；k = 0;随机产生m个个体组成初始群体pop(k) = n ,n2 , ,nm;对单个个体 n执行D F H A (n , Hpacking );记 录个体适应度 f (ni) (f (ni) = 1 n Hpacking (n);判断是否满足停止条件.若是，则停止计算，输 出最佳结果；否则：利用排序选择操作产生新的群体sel pop ( k +1);根据交叉概率Pc进行交叉操作，产生群体 cross pop ( k + 1);根据变异概率Pm进行变异操作，产生群

29、体 mutpop (k + 1);pop( k + 1) = mutpop ( k+ 1) ; k = k + 1;返回 end procedure3.2编码与选择矩形装箱采用整数编码，即n个矩形分别用整 数1 ,2,n编号,矩形的一个装入序列对应一个染 色体编码.例如：个体n的染色体编码为(-6158- 3 2 - 74 - 9),表示装入序列为 6 1 5 8 3 2 74 9, 在装入过程中，编号为6,3,7 ,9的矩形进行90°旋转.本文在采用排序选择方法来生成下一代个体的 同时,还混合使用了最优保存策略.交叉是产生新个体的主要方法，本文主要采用双点交叉.首先随机生成起止交叉

30、点Pcr1 , Pcr2 1 ,n;其次将配对个体Rr1到Pcr2之间的基因进行互换;最后依次将未出现的父代基因填入子代对应的 空白基因位上.例如：n = ( - 6 1 5 8 - 3 2 - 7 4 - 9) , n = (3 5 - 9 8 - 2 4 1 7 6),起止交叉点 Pc“ , Pcr2分别为2 , 6,则交叉后产生的个体编码为n； = ( - 6 5 - 9 8-241 - 3 - 7) , n； = ( - 9 1 5 8 - 3 2 4 7 6). 3.4变异本文变异包括2部分：一是旋转变异；二是装入 序列变异.1) 旋转变异旋转变异采用了单点取反和部分取反2种方式.单

31、点取反变异是指随机选择单个基因进行取反变异.例如，对于个体 n = (n (1) , n (2),n ( i),n( n),取随机变异点i,则变异后产生的新个体 为 n； = (n (1) ,n(2),，-n(i),n(n).部分取反变异指随机生成起止变异点Pmu1 ,Pmu2 1, n;然后将Pmu1到Pmu2之间的基因取反.2) 装入序列变异装入序列变异采用了两点位置互换、部分逆转与首部逆转3种方式.两点位置互换变异首先随机生成 2个变异点i, j 1, n;然后将2个基因互换.例如：n = (n(1) , n (2),n (i1),，n (i2) , :n (n) , N , i2 1

32、, n, 则变异后产生的新个体为n； = (n (1) , n (2),n(i2),，n(h),，n( n).部分逆转变异首先随机生成起止变异点Pmu1 ,Pmu2 1 , n;然后将Pmu1到Pmu2之间的基因逆转.首部逆转变异首先随机生成变异点Pmu 1 ,n;然后将1至U Pmu之间的基因逆转.在所有变异个体中，单点取反、部分取反、两点 位置互换、部分逆转、首部逆转所占比例分别为10 % ,20 % ,50 % ,10%,10 %.4实验对比为了验证 GA + DF HA的有效性，本文给出了 2组实验结果对比，其所用实例分别来自于文献19 和文献8 . GA + DF HA用C+ +编程

33、实现.实验平台:Pentium 4 3.0 GHz ,512MB memory.运行参数：交叉概率Pc =0.9 ,变异概率Pm = 实验1在文献19 中,Hopper等人给出了 21组不同 尺寸的实验实例，这些实例分成7个大类，每个大类 由3组实例组成，其矩形个数从16197个不等.每 个实例的最优解 Hopt已经给出，其相关数据见文献19.在本文算法中，群体大小设为 50 ,终止条件为最大进化代数等于3000，或者装箱咼度Hpacking等于最优解Hopt .对每组实验实例重复运行20次，记录每个大类60次（每个大类3个实例，每个实例进行 20次实验）实验的平均装箱高度到最优

34、装箱高度的 相对距离 Hrd = （60 次平均 Hpacking - Hopt ） nHopt X 100 %.实验结果对比如表1所示：© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启

35、发式算法#Table 1 Computational Results of Nine Algorithms ( Hrd)表1 9种算法的实验结果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:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#从表1中可以看出，本文给出的 GA + DF HA 算法获得的Hrd最小为0、最大为0.67,平均相对距 离（Mean）为0. 27 ,比其他10种算法中获得的最小 平均相对距离（A1 :0.73）减少了 0. 46个百分点.在 7大类实例中

38、，有3大类实例的 Hrd为0，即对应的 所有实例20次实验结果皆取得了最优解；而其他算 法中，至多有 2大类（A1 , GRASP）的 Hrd为0.因 此,实验结果表明，针对RSPP,本文提出的 GA +DFHA算法相对更优.表2给出了上述所有算法的计算时间.由于本文算法采用了装箱高度等于最优解作为终止运行条 件之一，因此，虽然C5的规模（即被装入矩形的个 数）大于C4,但由于其获得最优解的进化代数相对 较小，所以其运行时间略小于 C4.本文给出的GA + DF HA的算法复杂度为 O（n2）.© 1994-20China Academic Jcunial Elect!onic Pu

39、blishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#Table 2 Run Times of Nine Algorithms表2 9种算法的运行时间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:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#© 1994-20China Academic Jcunial Elect!onic Publishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#© 1994-20China Academic Jcunial Elect!onic Pu

43、blishing House. All rights reser-ed. http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#表 3 给出了 GRASP + VNS , GRASP , HRBB 以及本文的 GA + DF HA对21组实例求得的实际 实验结果 Hpacking .在对21组实例的实验中，每次实 验皆能获得最优解Hopt的实例GA + DF HA有12组，而 GRASP为8组，HRBB为7组；至少获得 1 次最优解（即最小装箱高度 Hmin =最优解Hopt ）的实 例 GA + DFHA 有 18 组,而 GRASP 为 8 组,HRBB 为9组；GA + DF H

44、A获得的最大装箱咼度 Hmax与 最优解Hopt之间的距离最多为1个基本单位.因此, 无论是最优解所占比例 ，还是最小装箱高度 Hmin、 平均装箱高度 Havg以及最大装箱高度 Hmax ,相对于GRASP + VNS , GRASP 与 HRBB 3 种算法,GA + DF HA算法的求解结果更优.C 1994-2009 China Academic Jcuma Llectronic Pug Mouse. A rights reserved, http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#C 1994-2009 China Academic Jcuma Llectronic

45、 Pug Mouse. A rights reserved, http:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#Table 3 Computational Results of Twenty2One Instances表321组实例计算结果比较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:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法#C 1994-2009 China Academic Jcuma Llectronic Pug Mouse. A rights reserved, htt

50、p:蒋兴波等：求解矩形条带装箱问题的动态匹配启发式算法5154.2 实验2文献8给出了 13组标准实验实例，其待排矩 形数量n从103152不等，容器宽度 W和最优解 H opt已经给出.在本文的算法中 ，群体大小仍设为 50,终止条件为最大进化代数等于3000（其中N12为100 ,N13为5），或者装箱咼度Hpackin等于最优解Hopt ;对每组实验实例重复运行20次.实验结果见表4.从表4可以看出，GA + DF HA算法在对该组 实例的实验中,20次均获得最优解（即Havg = Hopt） 的有6组，而其他算法中至多只有3组（HA ） . 20次实验中，GA+DFHA算法对10组实例

51、皆获得了至 少1次最优解，远远高于其他算法，而算法获得的最 大装箱高度（Hmax）与最优解之间除 N5相差2个基 本单位 外，其余至多相差1个基本单位 GA + DF HA求解N1至N13的平均运行时间分别为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 算法所用时间（见文献13）远远大于GA + DF HA.因此，相对而言，GA + DF HA 对求解 RSPP 具有较明显的优势.Table 4Computational Results

52、of Five Algorithms for Thirteen Instances表413组实例计算结果InstanceWH optnBFBF + TS BF + SA BF + GAGRASPHAH minHminH minH minH minH avgH minHminH avgH maxN1404010454040404040404040. 0040N2305020535050505050505050. 0050N3305030525151525151505050. 0050N4808040868382838181818080. 9081N510010050105103103104102102102100101. 55102N65010060102102102102101101101100100. 00100N78010070108105104104101101101100100. 95101N8