王金敏， 朱丽苹

（1. 天津市高速切削与精密加工重点实验室，天津 300222；2. 天津职业技术师范大学机械工程学院，天津 300222）

基于序列模型的三维矩形布局算法

王金敏1,2， 朱丽苹2

（1. 天津市高速切削与精密加工重点实验室，天津 300222；2. 天津职业技术师范大学机械工程学院，天津 300222）

针对三维矩形布局问题进行了研究。在三元序列的基础上，结合布局物体的几何可行域，提出了三元序列结合几何可行域的布局算法。并且利用遗传算法对布局算法进行优化，得到了三元序列结合可行域布局遗传算法。分析和实例证明，三元序列结合几何可行域的改进算法有效地提高了布局效率。

布局问题；三元序列；可行域；遗传算法

布局问题(packing problem)[1-2]是指给定一个布局空间和若干待布物体，将待布物体合理地摆放在空间中满足必要的约束，并达到某种最优指标。布局问题的求解非常困难，唐晓君等[3]详细阐述了布局问题的复杂性。即使是最简单的一维布局问题也被证明是 NP完全问题(non-deterministic polynomial, NP)。因此，布局问题吸引了大批的学者对其进行研究。Hashimshony和 Roth[4]介绍了ALG模型，该模型在给定的约束条件下，利用图论来产生可行的布局方案。袁苗龙等[5]利用图法则分析了三维布局模型生成方法对车身内进行了布置，但文章并没有过多地对布局结果进行分析。晏敏等[6]给出了用于表达矩形物体平面布局空间关系的方图模型，并提出了方图矩阵及其运算规则。该模型侧重平面布局问题的求解，对空间布局问题的求解有一定的困难。……