论文部分内容阅读
定位—运输路线安排问题(LRP)是分销网络设计和物流管理决策中的难题。由于LRP是NP-complete问题,对它的求解方法大多局限于将其分解为定位—分配问题和车辆运输路线安排问题,或者是基于这种分解思想。文章通过对遗传算法(GA)中树编码、免疫遗传算法以及GA阶段进化策略深入地分析和研究,构建了定位—运输路线安排问题的遗传算法,它与以往算法最大的不同点就是并没有基于两阶段求解的思路,而是将LRP的解看作一个整体,从而减小了在进化过程中停滞于局部最优解的概率,提高了GA的计算效率和计算速度。文中详细叙述了针对LRP问题的树编码、交叉、变异、爬山、免疫、合并小路线等各种算子设计过程,并利用一实例来验证算法的可行性。该算法为LRP问题以及相关大规模组合优化问题的求解开辟了一个新的思路,同时也为GA中树编码在实际中应用做了有益的尝试。
Positioning - Routing Problem (LRP) is a challenge in distribution network design and logistics management decisions. Because LRP is an NP-complete problem, its solution is mostly limited to its decomposition into positioning-distribution problems and vehicle routing problems, or based on this idea of decomposition. By analyzing and studying the genetic algorithm (GA) tree coding, immune genetic algorithm and GA evolution strategy, the article builds a genetic algorithm for the location-routing problem. The biggest difference between this algorithm and the previous one is that it is not based on the genetic algorithm Instead, the idea of LRP is considered as a whole, so as to reduce the probability of stagnation in the local optimal solution in the evolutionary process and improve the computational efficiency and computational speed of GA. In this paper, we describe in detail the design process of various operators such as tree coding, crossover, mutation, hill climbing, immunity, merging small routes and so on, and verify the feasibility of the algorithm by using an example. The algorithm opens up a new idea for solving LRP problems and related large-scale combinatorial optimization problems, and also makes a useful attempt for practical application of tree coding in GA.