由于布局问题在工业产品中的广泛应用,引起了众多学者的关注。人们对布局问题进行了大量的研究,解决布局问题的方法也很多。所以天行健精益布局咨询通过总结把方法分为以下几类。
1.精确的数学方法
早期的布局问题一般用传统的数学规划方法(如线性规划、整数规划、非线性规划、动态规划、网络流和分枝定界法等)来解决。).精确的数学方法可以得到问题的最优解,但是对于大规模的布局问题,其耗时是难以承受的。
2、启发式方法
启发算法在解决布局问题中起着重要的作用,它通常是基于问题的特点。设计启发规则在布局空间中搜索是一种近似方法,可以快速得到问题的解。但由于启发公式法缩小了搜索空间,得到的解一般不是问题的最优解,而只是问题的较优解。
根据启发策略的不同,启发方法可分为定位排序构造法和满负荷局部搜索法。定位排序的构造方法按照一定的放置规则依次放置布局对象,每次放置都满足互不干涉等一些要求,直到最后一个布局对象,最终得到一个完整的解。如基于一维装箱的FFD算法、基于最左最低原则的BL算法等。这种启发方法的解的好坏与布局顺序有关。与定位排序启发法不同,全装载局部搜索法将所有布局对象一次性放入布局空间形成初始解,然后按照启发策略移动一个或部分布局对象,逐步提高解的质量,最终得到满足要求的较优解。我们提出的解决圆形布局问题的“伪对象法”是一种满负荷的局部搜索方法。启发算法的特点是能得到较好的结果,快速解决一些布局问题,但缺乏全局搜索能力,容易陷入局部最优,对其他布局问题的普遍适用性不强。
3、智能算法
20世纪七八十年代以来,随着遗传算法(GA)、禁忌搜索(1S)、蚁群优化算法(ACO)、粒子群优化(PSO)、模拟退火算法(S-person)、散射搜索算法(SS)、人工蜂群算法(ABC)等智能优化算法的出现,布局问题得到了解决。由于智能算法具有全局搜索能力,在解决复杂布局问题时显示了其优越性。但是智能算法没有启发式方法那么有针对性。当布局问题的解空间呈现多峰、不连续的特点时,简单的智能算法会导致搜索空间大、搜索时间长、早熟等问题。而且不同的智能算法对不同的布局问题有不同的理解效果。
4、混合算法
将智能算法与启发算法相结合,形成混合算法,可以有效弥补各自的不足,正日益成为解决布局问题的重要途径。采用人工神经网络方法、数学规划和遗传算法求解定宽无限长板材的矩形布局问题。给出了SA、GA和不同启发算法对不同问题实例的综合性能评估结果。主要结论有两个:①混合算法的结果优于纯启发算法;②纯启发算法效果越好,同等条件下混合算法效果越好。