基于改进双种群混合遗传算法的车辆路径问题研究

何国强 李斌成 王东先

摘 要：针对传统遗传算法求解带容量约束的车辆路径问题，存在早熟收敛、易陷入局部最优等问题，设计了双种群混合遗传算法。种群I在传统遗传算法中引入模拟退火思想及变邻域搜索策略，增强算法局部搜索性能。种群II在迭代过程中，通过设定阈值判断当种群达到早熟收敛状态时，利用“移民策略”植入外部个体，达到增加种群多样性、增强算法全局搜索和开发的能力。每次迭代完成后采用“移民算子”进行种群间的信息交流。最近邻插入方法在算法迭代结束之后对求解所得最好解的各子路径进行再优化。算例验证分析可知，所提算法计算结果同算例给出的最好解之间的偏差均在-1.00%以内，求解质量优于所有对比的算法，表明所提算法能有效解决容量约束的车辆路径问题，具有可靠的全局稳定性。

关 键 词：容量车辆路径问题;双种群;混合遗传算法; 移民策略;局部搜索/全局搜索

中图分类号：TP301.6  文献标志码： A 文章编号：2096-7934（2020）07-0108-11

一、 引言

车辆路径问题（vehicle routing problem， VRP）是典型的组合优化问题，经过不断发展，在VRP问题的基础上衍生出了很多其他问题，如：带时间窗的VRP（vehicle routing problem with times windows， VRPTW）、多配送中心VRP（multiple depot vehicle routing problem， m-VRP）、容量限制的VRP（capacitated vehicle routing problem， CVRP）等。其中，容量限制的VRP（capacitated vehicle routing problem， CVRP）实用性较为广泛，因而吸引了众多学者进行研究。目前，关于CVRP的计算方法主要分三类：精确算法、启发式算法及智能优化算法。精确算法与启发式算法对于较大规模CVRP问题求解比较困难，因而，目前对CVRP问题求解方法的研究主要集中在智能优化算法上，如遗传算法（GA）[1]、模拟退火算法（SA）[2]、蟻群算法（ACO）[3]。……