用有记忆功能的退火遗传算法求解车辆路径问题

摘要

物流配送路径问题是个组合优化问题，很好的求解它可以帮助物流企业节省运输费用，对增加物流公司的经济效益有着至关重要的作用；近年来遗传算法对这1问题的求解得到广泛应用，但是遗传算法的交配算子操作可能遗失最优解，同时常用的停止准则无法保证得到最优解，从而严重影响了整个算法的性能；针对这1情况本文提出了将遗传算法和模拟退火算法结合，并加入了记忆装置，设计了1种有记忆功能的遗传模拟退火算法来求解物流配送路径优化问题，并进行了试验计算。结果表明：这种算法求解可以保证得到较高质量的解。

关键字:遗传算法；模拟退火算法；车辆路径问题；记忆装置

On The Result of Remembered Genetic Simulated Annealing Algorithm to Physical Distribution Routing Problem

Abstract

Physical distribution routing problem is a combination optimization problem, helping save transportation expenses and complete the distribution task accurately, which plays an essential role in increasing the financial profit for the distribution company. In recent years the result of Genetic Algorithm to optimization combination has been widely used but the Crossover operator of the Genetic Algorithm may be losing the best result. The common stop rule cannot ensure the result is the best of all the result. These weaknesses affect the performance of the algorithm. On the basis of the situation, this paper bring forward let the genetic algorithm and the simulated annealing algorithm comminuted, and let it has a remembering function. Thus we get a new hybrid algorithm, called remembered genetic simulated annealing algorithm. We make some experimental computation, the result demonstrate this algorithm can overcome the weakness above, and the high quality solutions obtained.

Keywords: the genetic algorithm, the simulated annealing algorithm, vehicle routing problem, remembering function