利用可行域的矩形布局求解方法.pdf

现代制造工程2010年第3期
制造技术/工艺装备
利用可行域的矩形布局求解方法
张鵬程',郡艳梅,李国顺,茹江燕
(1河北工程技术高等专科学校电气工程系,沧州061001
2中国化学工程第十三建设有限公司,沧州061000)
摘要:针对矩形布局求解问题,研究和分析矩形在布局空间中的可行域,提出一种以矩形可行域为依据的布局求解方法,
其内容包括矩形可行域的确定、布局空间的分割和确定以及布局子空间的选择等算法。算例表明,该方法可以获得良好
的布局方案,是一种行之有效的布局求解方法,具有广泛的实用性。
关键词:矩形布局;可行域;布局空间;定位函数
中图分类号:TP391.72文献标识码:A文章编号:1671-3133(2010)03-009004
An rectangle packing algorithm based on feasible region
ZHANG Peng-cheng, XI Yan-mei, LI Guo-shun, RU Jiang-yan'
(1 Department of Electrical Engineering, Hebei Engineering and
Technology College, Cangzhou 061001, Hebei, China: 2 The 13 Construction Co
Ltd. of China National Chemical Engineering, Cangzhou 061000, Hebei, China)
Abstract: Aming at rectangle packing problem, studies rectangle,'s feasible region in packing space, presents a packing algorithm
based on rectangles feasible region, its main contents include: rectangles feasible region calculation, packing space division and
determination, packing sub paces selection. A large number of examples indicate that the algorithm is an effective method ap-
proach to solve rectangle packing problem, which can produce optimal packing results and have wide applicability in engineering
practice
Key words: rectangle packing; feasible region; packing region; positioning function
0引言
好的布局结果。
矩形可行域的确定
矩形布局问题)作为一个具有 Np-hard的组合
最优化问题,广泛存在于板材切割、排样、大规模集成
在布局求解过程中,一个最基本的要求就是放入
电路设计、服装裁剪和印刷排版等领域。由于在有限的每一个矩形既不能和布局空间边界发生干涉,也不
的时间内无法获得全局最优解,许多学者提出了各种能和已经布入的矩形互相干涉,否则为无效布局。判
启发式算法3?,用于解决不同领域的矩形布局问题,断一个矩形布入是否发生干涉是一个计算量很大的
但很难找到一种对于各种不同特点的布局问题都有过程,而且随布人矩形的增多,其复杂程度会越来越
很好适应性的求解方法
大。为了避免这样的干涉计算,本文引入了矩形可行
本文提出一种利用可行域求解矩形布局问题的域的概念。
方法。该方法以矩形在其布局空间中的可行域为基
可行域是布局物体在布局空间中所有可行位置的
础,将布局问题简化为定位和定序策略的选取,同时集合,具体可表示为布局物体上任意一点在物体沿布局
结合实时布局空间的分割和确定算法,最终获得矩形空间边界移动时的封闭轨迹包含的区域大小?,如图1
在布局空间中最合适的位置。大量算例证明:该方法所示。可行域的大小(面积)反映了该物体能够被布入
是求解矩形布局问题的一种行之有效的方法,且具有的难易程度。如果能够求出待布矩形的可行域,那么,
较为广泛的适用性,采用不同的算例测试皆可获得很定位矩形布入位置时只要考虑可行域范围内的点就可
河北工程技术高等专科学校科研基金资助项目(X0904)
万方数据
制造技术/工艺装备
现代制造工程2010年第3期
以了,因为在可行域中任意位置放置矩形,都不会和已点,则P。即为该矩形的可行域,转第六步结束,否则,
经布人的矩形及布局空间边界发生干涉。
继续。
第四步:求出偏移多边形的边界多边形P。,比较
多边形P。和P。中相邻顶点的连接次序。如果P。中
的顶点连接次序与相应的P,中的顶点连接次序相同,
ヤZー
说明该顶点属于可行域上的顶点;如果连接次序相
反,则说明该顶点不在可行域上。
第五步:遍历并处理P。上所有顶点,即可获得待
布矩形R的可行域。
第六步:程序结束。
图1待布矩形及其可行域(阴影部分,设矩形不旋转)
算法思想:由于矩形布局问题中,布局空间可以2布入矩形的定位
描述为一个直角多边形,且边界分别与布入矩形的宽
考虑到实际布局过程中条件约束,本文采用文献
和高平行,那么,矩形的可行域可由布局空间上的所[8]中提出来的定位函数来计算产生矩形的布入位
有顶点向布局空间内部,分別按矩形宽和高的一半进置。由于矩形可以放置在可行域中的任意位置,因此
行偏移得到。如果偏移多边形发生自交,则自交区域可以将可行域上的点分别代人定位函数,通过比较函
为矩形的不可行域。检测偏移多边形所有顶点,利用数值来选取最佳位置。实际布局过程中不同方向上
其边界多边形去掉所有的自交区域,剩下的部分即为的约束条件由定位函数中的参数值反映。
矩形在当前布局空间中的可行域,如图2和图3所示。
定位函数的具体形式为:
图2为矩形及其偏移多边形,图3为边界多边形和矩
形在布局空间中的可行域
(x,y)=∑o(x,y,)
f,(x2,y:)=c,1x-x+B,y
omit
式中:(x;,y1)为总的定位函数:(x,y)为关于各个
吸引子的定位函数;m为吸引子的个数;n为待布局矩
形的数量;(x,y1)为待布局矩形基点的坐标;(xo,yo
为布局吸引子的坐标;anB、o,分别为权重因子,且a
图2矩形及其偏移多边形(虚线部分)
+B1=1,01=1
定位评价函数可描述为:min(x;,y1)。
3布局空间的确定
对于二维矩形布局问题,随着待布矩形的布入
布局空间的形状开始发生变化,其形状随着布入矩形
的增多也越来越复杂。在布局过程结束时,布局空间
图3边界多边形及矩形的可行域(剖面线部分)
将被布入的矩形最大限度地填充。由于布局空间在
每一个矩形布入后都要发生相应的变化,而更新后的
矩形在布局空间中的可行域求解算法如下。
布局空间大小、形状又直接影响着下一个待布矩形的
第一步:设当前布局空间多边形为P,待布矩形为具体放置,所以,确定布局空间对于布局问题的整个
求解过程都有着重要的影响。
第二步:将