郑娟毅，付姣姣，程秀琦

(西安邮电大学通信与信息工程学院，陕西西安 710121)

1 引言

随着城市信息化的快速发展，物流发展的愈加迅速，企业间的竞争也愈加激烈，若能在物流末端配送环节加以改进，则能更好的满足需求[1]。车辆路径问题是物流车辆路径规划的关键环节，车辆路径问题(vehicle routing problem,VRP)是指由一个负责配送货物的车队选择较为合适的配送路线，完成具有一定数量的配送点要求并回到配送中心且满足所有约束条件后达到路径最优的问题[2]。在求解VRP中，启发式算法一直是研究路径优化问题的重点，启发式算法主要有节约法[3]，扫描法[4]，遗传算法[5]，粒子群算法[6]，蚁群算法[7](ant colony algorithm，ACA)和模拟退火算法[8](simulated annealing，SA)等，蚁群算法具有较好的并行性和鲁棒性，并且易于其它算法结合，模拟退火算法运算效率高，求解方向与算法的初始状态无关。文献[9]采用并行搜索方式进行信息素交互的双种群最大最小蚁群算法，改善了解的质量但是收敛速度下降了。文献[9]提出一种解决Job-Shop的模拟退火蚁群算法，算法的收敛速度提高了，但出现早熟现象。文献[10]提出求解旅行商问题的模拟退火蚁群算法，它在一定程度上避免了早熟现象，但是收敛速度降低了。

针对以上算法在求解车辆路径问题易陷入局部最优和收敛速度较慢等问题，本文提出一种自适应蚁群算法，将模拟退火算法得到的解作为蚁群算法的初始值；在蚁群算法的状态转移规则引入道路阻抗系数，以满足实际路径需求，并对信息素挥发因子进行自适应调整，结合2-opt邻域搜索算法对蚁群算法得到的解二次交换，改变解的质量并进行优选，前期避免陷入局部最优，后期加快算法收敛速度。……