张延 葛斌

摘 要：为了解决带软时间窗车辆路径这一类典型的NP-hard问题，减少总配送成本，本文提出一种混合蚁群算法，通过蚁群优化技术与遗传算法中的变异算子结合增加解的多样性，根据适应度函数评估解的质量获得精英解来对构建的模型求解，采用众所周知的基准所罗门数据集，设置25和100不同的客户规模仿真结果对比评估性能，得到全局平均解的优化率都达到10%以上的结果。仿真结果显示，高效地求解了VRPSTW问题，在收敛速度和寻优结果两方面均有明显优化。

关键词：VRPSTW;蚁群优化;变异算子;精英解

中图分类号：TP181  文献标识码：A  文章编号：1673-260X（2021）07-0009-04

1 引言

带软时间窗的车辆路径问题（VRPSTW），是基本VRP的延伸，时间窗约束被放宽为“软”，如果车辆未按客户提前预定的时间窗要求到达客户点，允许时间有所偏离，但必须付出一定惩罚成本。带软时间窗车辆路径问题在考虑带硬时间窗车辆路径问题会对车辆资源浪费和配送服务窗口要求过于强硬两方面存在优势。近年对VRPSTW的研究，Xu等人[1]采用了将贪婪策略和自适应策略结合的非支配排序遗传算法;Beheshti等人[2]提出了一种高效的混合列生成-元启发式方法;范厚明等人[3]将变领域下降搜索应用于粒子群算法的扰动，提高了算法的搜索性能;李国明等人[4]提出一种修正算法和禁忌搜索算法结合的两阶段改进算法;凌海峰等人[5]将蚁群算法与2-opt结合求解MDOVRPSTW。蚁群优化算法在求解VRP及其扩展问题上，因为其自身较强的自组织性和正反馈特点，拥有较好收敛效果同时容易陷入“早熟”，学者们于是通过引入精英保留方法、领域搜索或混合其他经典启发式算法优势[6]来改进蚁群算法。……