基于自适应动态搜索蚁群算法的车辆路径规划

贺智明，郑 丽，梁 文

(江西理工大学 信息工程学院，江西 赣州 341000)

0 引 言

车辆路径问题(vehicle routing problem，VRP)是指一组车辆从指定点出发，且遍历到一系列特定点的路线[1]。由于该问题的传统求解方法效果不佳，如精确算法[2]和启发式算法[3,4]。因此，学者们将AI技术与启发式算法结合，如：模拟退火算法[5]、禁忌搜索算法[6]、遗传算法[7]和蚁群算法[8]等。相对而言，蚁群算法(ant colony，ACO)在寻径方面占据独特优势。然而，当问题规模较大时，算法易陷入局部困境，无法对搜索空间进行深层次挖掘。为此，学者们做出不同的改进，例如：文献[9]将人工免疫和ACO算法相结合，有效解决紧急粮食分配问题；徐坤等[10]将信息素挥发因子采用莱维飞行模式更新，提高了算法的全局寻优能力；王飞鹏等[11]在求解TSP问题的最优解集中按比例选取部分解集构造近似骨架，并基于近似骨架对问题分段求解，有效解决算法精度不高等问题。

上述改进方法主要通过改变部分更新规则或同其它算法互补。然而ACO算法中关键参数的设置以及群体的合作行为都直接影响着算法性能。为此，本文提出自适应动态搜索蚁群算法(ADACO)，通过实验性配置关键组合参数和自适应伪随机策略协助群体选择合理的转移方向。此外，信息素强度的分段化设定有效预防了群体长时间滞留于困境中而无法跳脱的现象，减少了时间开销。

1 模型建立

本小节针对车辆路径问题建立数学模型，其中包括模型假设、符号说明和目标优化函数的设定。

1.1 模型假设

依据实际问题对该模型做出如下假设：