工厂规划布局问题求解方法分类

由于布局问题在工业产品中的广泛应用，引起了许多学者的关注，对布局问题进行了大量的研究，求解布局问题的方法很多。因此天行健通过总结把方法划分为以下几类。

1、精确的数学方法

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

2、启发式方法

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

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

3、智能算法

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

4、混合算法

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