改进的遗传算法及在物流配送路径优化中的应用

Improved genetic algorithm and its application to the optimization of physical distribution routing

物流配送中带有时间窗车辆路径问题(vehicle routing problem with time window,VRPTW)是复杂的NP-Hard难题,本文针对这个问题提出一种改进的遗传算法.针对简单遗传算法容易出现"早熟收敛"的问题,算法设计了一种基于个体浓度的群体多样性保持策略,将其作为选择算子,依据个体期望繁殖率来选择子代,引入新颖的CX交叉算子.通过对实际的物流配送实例进行实验和计算,实验结果表明,该遗传算法可以更加有效地求得有时间窗车辆路径问题的优化解,是解决物流配送车辆路径安排较好的方案.

Vehicle Routing Problem with Time Windows （VRPTW） is a complicated NP-Hard problem in physical distribution This paper presents an improved genetic algorithm. To avoid the problem of ＂premature convergence＂ in simple genetic algorithm, a kind of group diversity maintaining strategy, which is based on the density of individual is applied in this algorithm as a selection operator, and adopting the reproductive rate of individual expectation to choose offspring. Besides. a novel CX crossover is also involved in this algorithm. This algorithm can find the optimal or nearly optimal solution to VRPTW effectively, and it is a preferable schema for VRPTW, which is proved by a physical distribution instance.