定位—运输路线安排问题的遗传算法研究

A Novel Genetic Algorithm for Location-Routing Problem

定位—运输路线安排问题(LRP)是分销网络设计和物流管理决策中的难题。由于LRP是NP-complete问题,对它的求解方法大多局限于将其分解为定位—分配问题和车辆运输路线安排问题,或者是基于这种分解思想。文章通过对遗传算法(GA)中树编码、免疫遗传算法以及GA阶段进化策略深入地分析和研究,构建了定位—运输路线安排问题的遗传算法,它与以往算法最大的不同点就是并没有基于两阶段求解的思路,而是将LRP的解看作一个整体,从而减小了在进化过程中停滞于局部最优解的概率,提高了GA的计算效率和计算速度。文中详细叙述了针对LRP问题的树编码、交叉、变异、爬山、免疫、合并小路线等各种算子设计过程,并利用一实例来验证算法的可行性。该算法为LRP问题以及相关大规模组合优化问题的求解开辟了一个新的思路,同时也为GA中树编码在实际中应用做了有益的尝试。

Location-routing problem is one of the problems in distribution network designing and logistic management.As a NP-complete problem,most of the algorithms for LRP are two-phase algorithms or based on it.One phase is for location-allocation problem;the other is for vehicle-routing problem.Through studying genetic algorithm,tree encoding,immune GA and phase-evolve-strategy of GA,a novel genetic algorithm for LRP is proposed in this paper.Distinguish between this GA and other algorithms for LRP is that the solution of LRP in this paper is looked as an integer.So the chance of the solution falling in local optimization cuts down,and the compute velocity and efficiency are improved at the same time.The tree encoding,crossover,mutation,immunity,climbing method and unite little rout method are depicted at length in this paper.A computational study shows that this novel GA is a feasible algorithm,which achieves improve-ment over LRP and other large-scale combinatorial optimization,and does some instructive attempts on applying tree en-coding in practice simultaneity.