矩形布局问题动态定序评价函数研究

Research of the evaluated function based on the dynamic ordering ruleZHANG Jing，WANG Jin-min(School of Mechanical Engineering，Tianjin University ofTechnology and Education，Tianjin 300222，China)Abstract：In the packing process，as the packing block increasing in the container，the container environment isbecoming more and more complex.In order to get better packing results，this paper puts forward three kinds ofevaluation function based on size match rule by considering the packing point，and then studies it further.Theexperimental results show that the evaluation function can improve the packing results， and it does have animportant role to packing problems。

Key words：packing problem；size match；evaluation function矩形布局问题是现实生产和生活实践中经常遇到的问题 ，涉及的领域很广，如货物的装运、板材的切割、服装的剪裁下料、大规模集成电路的布置设计等等。由于布局问题是NP难问题，其在有限的时间内很难找到最优解。针对这-问题，人们大多采用启发式算法加以解决。布局启发式算法中的构造式算法是人们常用的-类算法。该算法通常由定位规则和定序规则两部分组成。定序规则通过矩形块的某-项或某几项属性决定矩形块的布人顺序，常见的静态定序规则有Dowsland等lJ提出的按布局块面积递减的定序规则和Gehring等闭提出的按最长边递减的定序规则等。由于布局过程是动态变化的，采用静态规则往往达不到很好的效果 ，因此国内外-些学者对动态定序规则进行了研究 ，Hifl[31提出的容器装载的近似算法，是根据已步入矩形块的各尺寸来约束下-个布局块的尺寸 ，从而确定下-个布人的布局块；Wei等 提出最少浪费优先的启发式算法((LWF)，是采用BL算法来布置第1个矩形块，根据已步人的矩形块的位置特点划分第2个矩形块可布人的空间及位置，如有不能再进行布局的空间则将其划分出去 ，视为被浪费的空问，并重新划分可布局空间，依次类推，保证每次放入的矩形块所划分出去的被浪费的空间面积最少 ，从而实现矩形块的定序。本文在基于尺寸配合的动态定序规则嘲的基础上，提出了3种评价函数对待布局矩形块进行动态定序 ；利用这3种评价函数对-些算例进行计算，并对布局结果进行了比较和分析。

1 评价函数矩形布局问题就是将-些矩形物体按-定要求合理地放置在-个空间内，放人的矩形物体相互之间没有重叠，且使所占空间尽量地校其中，物体称为布收稿 日期 ：2012-12-17基金项目：国家自然科学基金资助项目(60975046)。

作者简介：张 晶(1987- )，女，硕士研究生；王金敏(1962- )，男，教授，硕士生导师，研究方向为智能布局· 26· 天 津 职 业 技 术 师 范 大 学 学 报 第 23卷局块，空间称为布局容器。在矩形布局过程中，随着布人布局块的增多，布局容器中剩余空间将变成有多个点组成的正交多边形，可选择的布置点也随之增多，也就是说布局越往后，布置点和布局坏境也越来越复杂。根据这-情况，文献[6]提出涵盖矩形布局问题的3类布置点的各种情况，如图1～6所示。

图1 第1类布置点 图2 第2类布置点之-DF：E.---A- 图3 第2类布置点之二 图4 第3类布置点之-卺图5 第3类布置点之二 图6 第3类布置点之三图1为无约束型布置环境，对布置到该点的矩形块的长高没有要求，当然长为L高为日的矩形块最为理想。图2为单约束型布置环境，布人到该布置点的矩形块的长不能大于L，而对矩形块的高并无约束。对于该布置点，长为 ，高为日1或H2的矩形块都很理想。图3为单约束型布置环境，布人到该布置点的矩形块的高不能大于日，而对矩形块的长并无约束。对于该布置点，长为日，高为 或 的矩形块都很理想。图4～6都为双约束型环境 ，布入到该布置点的矩形块长度不能大于 ([JAB)，高度不能大于t(即AC)。对于该类布置点，长为 高为H的矩形块比较理想。其中，布人布局块的实际长和高分别为 和Y。

针对上述3类6种情况的布置点，文献[6]提出了其对应的评价函数 ，但由于其评价函数前后比重相等 ，对某些算例，忽略了较好的解而没有得到满意的结果。本文在此基础上加以改进，添加了参变系数Ot、JB，且满足 1(0< ≤1)，提出评价函数的目的就是评价待布局矩形块的尺寸与布置点环境中相应尺寸的配合程度 ，以便选择最适合的布局块进行布局。评价函数如下：IoLl(x-，J)( -日)I-/3(xY) (a)，Y)al(x-)(y-H )(y-H )l-/3(xy)(b)(1)lal(x-日)(y-L1)(y-L )l-13(xY)(c)上述 (a)式针对第1类和第3类布置点 (见图1，4，5，6)；(b)式针对第2类布置点的第1种情况(见图2)；(e)式针对第2类布置点的第2种情况(见图3)。以下评价函数也依次对应。

al(x-L)lm(r-H)l-13(x )，Y) I( - )II(y-日。)II(y-H2)I-卢( )(2)Ial(x-H)mI(y- )l(y- 2)I-13(xy)I l( -L)(y-H)l- 砂/( ，Y)al(x-L)( -H )(y-H )l- (3)Ial(x-H)(Y-，J1)(y-L2)l-2 布局算法定序规则以布置点为导向，通过计算各待布局矩形块的评价函数的值来确定布局块的顺序，但要构成布局算法，还需要与吸引子法161的定位规则相结合(对于吸引子法所涉及的吸引子参数的确定，是采用粒子群算法进行优化的，详细过程请参见文献[6])。所提布局算法流程如图7所示。

I 嘉 需鍪 布 二二[筛选待布局矩形块 / I有匝亟圃 - - - - - [ 1选择函数值最小l的矩形块布入 二二[二更新待布局矩形块和剩余布局空间0断是否有剩余空间和未布矩形块布局结束，输出布局结果图7 算法流程图第 1期 张 晶，等：矩形布局问题动态定序评价函数研究 ·27·3 算例分析为了更好地实现上述算法，本文采用编程语言VC6.0，在2.00 GHz CPU，512 MB RAM的计算机上分别采用上述3种评价函数对相关算例进行了计算与分析。

算例1 利用文献[10]所提出的c1l-C73算例进行计算。其中评价函数(1)、(2)、(3)”的结果是利用本文所提出的评价函数，每个算例计算l0次，且在每个算例中 0.1×n(1≤1，≤10)，最后选取最优结果作为该算例的实验结果。实验结果如表1所示。

表1 文献6-9中C类算例计算结果与本文评价函数计算结果比较从上面实验数据可以看出，在这21个算例中，本文提出的评价函数(1)除了C1 1、C32算例外，其他算例都达到了99.33%以上。而文献[7]低于99.33%的结果有9个 ，文献[8低于99.33%的结果有7个 ，文献[9]低于99.33%的结果有17个 ，文献[6]低于99.33%的结果有7个。从最优解的个数和平均利用率看，评价函数(1)的结果与文献[6-91中的结果相比也都是最高的，平均利用率比最低结果高了1.06%。文献6-9]所能达到100%利用率的算例，本文除了C1 1算例外也相应达到了100%的利用率，而且本文提出的评价函数对于较大算例C43和C62也获得了100%的利用率。

通过比较本文提出的3种评价函数可以看出，评价函数(1)的布局结果最好，评价函数(3)次之。虽然评价函数(2)的结果总体上不如两者，但在算例C61，c71，C52，C13，C73中，评价函数(2)所得结果要高于评价函数(3)；在算例C22，C23中，其所得结果高于评价函数(1)。尤其是在算例C62中，评价函数(2)获得了当前最好的结果。

算例2 本文利用文献[1 1中的算例NlaN7e和T1a- e进行计算。NT类算例各有35个算例 ，分为N1-N7，Tl-T7共7个算例，其中每个算例有对应a、b、c、d、e 5个小类，而且都是在200x200的容器中进行布局的。计算结果如表2和表3所示。

表2 文献[6冲 N类算例计算结果与本文评价函数计算结果比较从表2数据中可以看出，N类的35个算例中，评价函数(1)所得算例结果有16个比文献[6好，3个与其持平 ，评价函数(2)所得结果有8个高于文献[6]，评价函数(3)所得结果有18个高于文献[6]，1个与其持平。由此可见，针对于N类算例，评价函数(3)所取得的效果较好，评价函数(1)(2)起补充作用。总体看来，使用本· 28· 天 津 职 业 技 术 师 范 大 学 学 报 第 23卷表3 文献6冲 T类算例计算结果与本文评价函数计算结果比较 %文提出的评价函数后，有22个算例的结果与文献[6]相比有了提高，平均利用率提高了0.71%。

从上述数据可以看出，T类的35个算例中，运用评价函数(1)和评价函数(3)所得结果中各有19个算例比文献[6]所得结果要高，其中评价函数(1)、评价函数(3)分别还有3个和1个算例结果与文献[6]中的结果持平。评价函数(2)所得结果有12个高于文献[6]，1个与之持平。其中，T7e算例获得了100%的利用率。整体看来 ，使用本文提出的评价函数后 ，有24个算例的结果比文献[6]所得结果高，平均利用率高出0.90%。

针对N类和T类算例进行进-步研究。通过对NT算例的每个算例进行待布局矩形块的个数的统计 ，我们发现对于同-类算例，它所包含的矩形块的个数是相等的。例如N7，它所对应的a、b、c、d、e 5//-算例中待布局矩形块的个数都是197，所以本文将它们作为-类进行统计。由于同-类算例的待布局矩形块的个数相同，本文又计算了N1～N7，T1～T7所对应的a、b、C、d、e 5个算例所得布局结果的平均利用率，如表4所示。

结合表4和图8、图9可以看出，随着待布局矩形块表4 NT类算例待布局矩形块的个数及其平均利用率算例图8 N类算例平均利用率算例图9 T类算例平均利用率的个数的增多，其对应的平均利用率呈上升趋势。整体看来，本文提出的3种评价函数所得布局结果的平均利用率，除了N1、N2和T7算例外，其他算例结果都比文献[6]所得结果高。由算例的平均利用率可以发现，N算例中评价函数(3)所获得的平均利用率比文献6]高0.03%；T算例中评价函数(3)所获得的平均利用率 比文献[6]高0.40%，评价函数(1)所得结果比文献[6]高0.11% 。

从上述实验数据比较中可以看出，本文提出的评价函数通过改变其参变系数 ，能够增加解的搜索范围，从而在-定程度上提高了布局结果。

∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞∞ 鳃 %∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞∞ 鲫 % 舛 虬第 1期 张 晶，等：矩形布局问题动态定序评价函数研究 ·29·4 结束语本文提出了3种评价函数 ，可通过改变其参变系数，从而得到较好的布局结果。通过算例分析，发现运用本文提出的评价函数 ，能够提高算例的空间利用率。对NT类算例，本文还计算了具有相同待布局矩形块的a，b，C，d，e 5个算例的平均利用率，通过比较发现，本文提出的评价函数，随着待布局块的增多，其获得的空间利用率也越高。由此可见，评价函数在动态定序规则中，对布局结果有着重要 的影响，选择合适的评价函数能够得到较好的结果。对于评价函数的系数如何选柔得到更好结果的问题，还有待进-步研究。