布局问题的分类及求解方法

摘 要：鉴于布局问题的多样性和复杂性，有必要对布局问题的分类以及常见的求解方法做一个研究总结。首先对布局问题分别按照空间维数，布局物的形状和约束条件分别进行分类，接着对各类布局问题常用的求解方法作了介绍，最后对布局问题的研究现状和发展趋势做了总结和展望。

关键词：布局问题；性能约束；启发式方法；智能算法

引言

布局问题是工业生产中经常出现的问题，如在玻璃切割、服装裁减以及金属加工等行业，需要在标准的材料上，切割出所需要的多个小型件，要求材料浪费最少；又如在货物运输、机械设计等领域，需要将一些小型的对象，如货品、零件、集成块等，装入一个大的容器，要求装载的对象数目最多（或者某种价值最大）。

布局问题的研究不仅具有重要的经济意义，也具有很强的理论意义。鉴于布局问题的多样性、复杂性，文章对布局问题的分类以及求解方法的做了一个研究综述。

1 布局问题的分类

工业生产中的布局问题各种各样，根据布局物维数、布局物和布局空间形状以及是否带性能约束，布局问题可分为如下几类[1]：

1.1 空间维数

布局问题按照空间维数可分为：一维布局问题、二维布局问题和三维布局问题。一般来说，问题维数越高，求解越困难。其中一维布局问题较为简单。二维布局问题由于其广泛的应用，是现阶段布局问题研究的一个主要分支。三维布局问题，由于图形和约束条件的复杂性，难于求解，因此研究相对较少，它将会成为今后布局问题研究的重点。

1.2 布局物的形状

布局问题按照布局物的形状，可分为规则图形的布局和不规则图形的布局。相对于规则图样的布局问题，不规则图样的布局问题的求解要困难很多，是由于不规则图样在不同的角度可以形成不同的布局方案，使得其解空间比规则图样的解空间大得多。因此，现实优化中，往往通过将不规则布局物简化处理为规则图形进行布局，但是这种近似处理会影响求解质量，从而很难得到较高质量的解。

1.3 约束条件

布局问题按照是否带性能约束分为：无性能约束问题和带性能约束问题。无性能约束的问题只需满足基本的不干涉要求，并尽量提高空间利用率。帶性能约束布局问题除了要满足以上基本要求外，还带有其它的性能约束。相比而言，带性能约束的布局问题由于存在多约束条件，使得解空间呈现出多峰态、非线性、不连续的特点，求解更加困难。

2 布局问题求解方法的分类

由于布局问题在工业产品中的广泛应用，引起了许多学者的关注，对布局问题进行了大量的研究，求解布局问题的方法很多，总的说来，可以分为以下几类。

2.1 精确的数学方法

早期的布局问题一般采用传统的数学规划方法求解（如线性规划、整数规划、非线性规划、动态规划、网络流和分枝定界法等）。精确的数学方法能得到问题的最优解，但对于较大规模布局问题，其耗时是难以承受的。

2.2 启发式方法

启发式算法在布局问题求解中占据了重要的地位，其通常根据问题的特点，设计启发式规则在布局空间中进行搜索，能较快的求得问题的解，是一种近似方法。但由于启发式方法缩小了搜索的空间，故得到的解一般不是问题的最优解，只是问题的较优解。

根据启发式策略的不同，启发式方法又分为定位定序的构造方法和全装填式的局部搜索方法。定位定序的构造方法根据一定的放置规则依次放置布局物，每一次放置均满足不干涉要求和某些其他要求，直至最后一个布局物，最后得到一个完整的解。如基于一维装箱的FFD算法、基于最左最下原则的BL算法等。这类启发式方法解的质量和布局顺序有关。与定位定序启发式方法不同，全装填式的局部搜索方法一次将全部的布局物放置到布局空间中，形成一个初始解，然后根据启发式策略对某个或某些布局物进行移动，逐步改进解的质量，最后得到满足要求的较优解。黄文奇等提出的求解圆形布局问题的“拟物法”，即是一种全装填式的局部搜索方法[2]。启发式算法的特点是针对某类或某些布局问题的结果较好，求解速度快，但其缺乏全局搜索能力，容易陷入局部最优，在对其他布局问题的普遍适用性上不强。

2.3 智能算法

20世纪70，80年代至今，随着智能优化算法如遗传算法（GA）、禁忌搜索（TS）、蚁群优化算法（ACO）、粒子群优化（PSO）算法、模拟退火算法（SA）、散射搜索（SS）算法和人工蜂群算法（ABC）等的不断出现，给解决布局问题提供了新的思路[1-4]。由于智能算法具有全局搜索能力，在求解NP-难的布局问题上显示出其优越性。但智能算法没有启发式方法针对性强，当布局问题的解空间呈现出多峰、不连续的特征时，单纯的智能算法会导致搜索空间大、搜索时间长、早熟等问题，并且不同的智能算法对于不同的布局问题，解的效果也有差异。

2.4 混合算法

将智能算法与启发式算法相结合形成混合算法，能有效弥补各自的不足，正日益成为解决布局问题的重要途径。Dagli等[4]采用人工神经网络方法、数学规划和遗传算法来求解定宽无限长板材的矩形布局问题，给出了SA、GA等与不同启发式算法结合对不同问题实例的综合性能评价的结果，有两点主要结论：（1）混合算法的结果优于单纯启发式算法的结果；（2）单纯启发式算法效果越好，则混合算法在同等条件下的效果也越好。

3 结束语

总的说来，从研究问题上看，一维布局问题相对简单，二维布局问题是当今布局问题研究的主流，而三维布局为今后研究发展的方向。基于复杂性的考虑，从布局物图形上看，主要集中在圆形（或球体）、矩形（或长方体）等规则图形布局上，现在逐渐开始对不规则的图形布局进行研究；从是否在性能约束上看，大多数研究主要为无性能约束的布局问题，对带性能约束的布局问题研究相对较少，但已引起研究者的关注。

在求解方法上，鉴于实际布局优化问题的复杂性，现阶段的主要求解方法还是启发式方法、智能算法或者两者相结合的混合算法。这类研究包括两个方面：（1）针对某一类具体问题，设计高效的启发式算法；（2）开发具有较强全局搜索能力的智能算法。而三维布局的有些启发式方法是通过扩展二维布局问题某些启发式方法的来的，规则图形的布局问题某些启发式方法进行适当地修改也可以应用到一些不规则图形布局问题上。

参考文献

[1]徐义春.卫星舱布局问题的智能求解方法研究[D].华中科技大学，2008.

[2]黄文奇，付樟华，许如初.不等圆 Packing 问题的拟物型邻域搜索算法[J].华中科技大学学报：自然科学版，2012，40（4）：1-4.

[3]徐荣武，封汉颍，郝飞龙，等.求解不等圆布局问题的一类遗传算法[J].信息与控制，2004，33（6）：656-659.

[4]Dagli CH， Poshyanond N. New approaches to nesting rectangular patterns， Journal of Intelligent manufacturing[J].1997，8：177-190.

作者简介：黄振东（1980-），男，汉族，湖北武汉人，博士，湖北经济学院讲师，主要研究方向：布局优化、计算智能，涌现计算。