李 卓 李文霞 巨玉祥 陈晓明 何晓平

(兰州交通大学交通运输学院 兰州 730070)

0 引 言

车辆路径问题(vehicle routing problem,VRP)是物流供应链研究领域的经典核心问题[1]，带软时间窗的车辆路径问题(vehicle routing problem with soft time window,VRPSTW)是组合优化中在物资送达各客户点设置了带有惩罚性质的软时间窗约束，是经典VRP中的一种变体，现实中快递配送[2]、应急物资调度[3]、人员救护[4]等路径规划问题均可被归纳为VRPSTW问题.

考虑到VRPSTW问题的NP-hard性质，精确算法在求解具有一定规模的问题时已不适用，而启发式算法在求解大规模VRP问题的适用性凸显，已被学术界广泛认可，且不少学者在传统算法的基础上进行了改进.范厚明等[5]将变领域下降搜索应用于粒子群算法的扰动，提高了算法的搜索性能，并将其应用于求解同时集配车辆路径问题.郭咏梅等[6]针对应急物流背景下的车辆路径问题，将人工鱼群算法中拥挤度因子引入蚁群算法来指导蚁群的聚集，提高了算法性能.值得注意的是，蚁群优化算法在计算复杂性和收敛速度方面比较适用于求解VRP及其变体问题，且解的质量不依赖于解的初始化，具有较好的鲁棒性[7]；然而，由于蚁群算法较强的自组织性和正反馈性，表现出良好收敛性的同时易陷入局部最优，因此，部分学者通过引入领域搜索[8-9]、精英保留策略或混合其他经典启发式算法优势[10-11]来改进蚁群算法.近些年来，随着新兴群智能优化算法的兴起，不少学者考虑将其应用于各自的研究领域[12]，其中萤火虫算……