张鹏程，王春艳，茹江燕

（1.河北工程技术高等专科学校 电力工程系，河北 沧州 061001；2.沧州设备安装技工学校，河北 沧州 061000）

矩形布局的启发式优化策略

张鹏程1，王春艳2，茹江燕2

（1.河北工程技术高等专科学校 电力工程系，河北 沧州 061001；2.沧州设备安装技工学校，河北 沧州 061000）

利用可行域算法求解矩形布局问题，通过调整矩形布入形态，改变其单一的可行域形式增大其解空间。算例结果表明，矩形调整对布局结果影响有规律，利用可行域算法求解矩形布局问题，简便、快捷、灵活、适应性强，从而能够灵活快速地获得更优异的矩形布局排布方案指导工程实践。

矩形布局；可行域；启发式算法；矩形形态；空间利用率

0 引 言

矩形布局问题作为一个具有NP-hard的组合最优化问题，广泛存在于板材切割、排样、大规模集成电路设计、服装裁剪和印刷排版等领域。由于在有限时间内无法获得全局最优解，许多学者提出各种启发式算法[1-3]用于解决不同领域的矩形布局问题，但很难找到一种对于各种不同特点的布局问题都有很好适应性的求解方法。通过对不同算例计算结果进行分析和比较得出，利用可行域算法求解矩形布局问题，简便、快捷、灵活、适应性强。

1 矩形布局问题的描述

矩形布局问题作为一类二维布局问题，将矩形作为排布对象，或利用矩形替代任意多边形或不规则图形进行排布，其特点是既保留了布局问题的复杂性，又使得问题求解一定程度上得到简化，工程实践中，有相当一部分多边形布局问题的求解是利用包络矩形将多边形转化为矩形来处理的。……