李斌成 何国强

摘 要：针对遗传算法求解带容量约束的车辆路径问题时，存在早熟收敛和易陷入局部最优的问题，提出了改进的遗传算法。该算法结合扫描算法思想将种群初始化进行改进，使种群从迭代之初就处于一种最优的状态，并改进了选择策略和交叉策略。通过标准测试算例验证可知，该算法求解结果同测试算例给出的当前最优值之间的偏差在-0.24%以内，且求解结果和稳定性均由于对比算法，为求解此类问题给出了更加有效的解决方案。

关 键 词：容量约束车辆路径问题;遗传算法;扫描算法;相似度;移民策略

一、引言

1959年，Dantzig et al.[1]和Ralphs et al. [2]提出了带容量约束的车辆路径问题（capacitated vehicle routing problem，CVRP），在物流配送和车辆调度问题中得到了广泛应用。目前，关于容量约束车辆路径的计算方法主要分三类：精确算法、启发式算法及智能优化算法。精确算法与启发式算法对于较大规模容量约束车辆路径问题求解比较困难，因此对容量约束车辆路径问题求解方法的研究主要集中在智能优化算法上，如遗传算法（GA）[3]、模拟退火算法（SA）[4]、蚁群算法（ACO）[5]。石兆[6]通过对智能优化算法求解容量约束车辆路径问题研究发现，禁忌搜索算法求解时间较短，但求解效果不稳定，禁忌规则也不易确定;模拟退火算法在牺牲时间的前提下可以计算得到相对满意的结果，但存在易陷入局部最优的缺陷;蚁群算法存在求解效率低，容易产生早熟收敛现象的问题。考虑到以上智能优化算法的缺点和不足，近年来许多学者采用改进的智能优化算法求解容量约束车辆路径问题。……