蚁群算法在车辆路径问题中的应用

. .

蚁群算法在车辆路径问题中的应用

摘要

蚁群算法〔Ant Colony Optimization, ACO〕是意大利学者M.Dorigo等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。通过介绍蚁群觅食过程中基于信息素〔pheromone〕的最短路径的搜索策略，给出了基于MATLAB的蚁群算法在车辆路径问题〔Vehicle Routing Problem, VRP〕中的应用。蚁群算法采用分布式并行计算机制，易于其他方法结合，而且具有较强的鲁棒性，但搜索时间长，容易陷入局部最优解。针对蚁群算法存在的过早收敛问题，参加2—opt方法对问题求解进展了局部优化，计算机仿真结果说明，这种混合型蚁群算法对求解车辆路径问题有较好的改良效果。

关键词：蚁群算法、 组合优化、车辆路径问题、2-opt方法

1. 车辆路径问题

车辆路径问题〔VRP〕来源于交通运输，1959年由Dantzig提出，它是组合优化问题中一个典型的NP-hard问题。最初用于研究亚特兰大炼油厂向各个加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点。 车路优化问题如下：

. -可修编.

. .

有一批客户，各客户点的位置坐标和货物需求，供给商具有假设干可供派送的车辆，运载能力给定，每辆车都是从起点出发，完成假设干客户点的运送任务后再回到起点。现要求以最少的车辆数和最少的车辆总行程来完成货物的派送任务。

2、蚁群系统根本原理

在蚂蚁群找到食物时，它们总能找到一条从食物到蚁穴之间的最短路径。因为蚂蚁在寻找食物时会在路途上释放一种特殊的信息素。当它们碰到一个还没有走过的路口时，会随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后面的蚂蚁再次碰到这个路口时，会选择激素浓度较高的路径走。这样形成了一个正反应，最优路径上的激素浓度越来越高，而其他的路径上激素浓度却会随时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻找过程中，整个蚁群通过相互留下的信息素作用交换着路径信息，最终找到最优路径。

3、根本蚁群算法求解车辆路径问题

求解VRP问题的蚂蚁算法中，每只蚂蚁是一个独立的用 于构造路线的过程，假设干蚂蚁过程之间通过信息素值来交换信 息，合作求解，并不断优化。这里的信息素值分布式存储在图

. -可修编.

. .

中，与各弧相关联。蚂蚁算法求解VRP问题的过程如下: (1) 参数初始化。

令t=0和循环次数也NC=0，设置最大循环次数NCmax。，将m只蚂蚁随机地放到n个城市，将每条边(i,j)上的信息素设为一个常数，且??ij=0〔??ij表示循环中路径(i,j)上的信息素增量〕，将出发点城市设置到禁忌表中； (2) 选择城市。

每个蚂蚁按照状态变化规那么逐步地构造一个解，即生成一条路。蚂蚁任务是在约束条件下，访问客户后回到仓库，生成一条回路。设蚂蚁k当前所在的顶点为i ，那么蚂蚁k由点i 向点j 移动要遵循一下公式〔1〕的状态变化规那么而不断迁徙，按不同概率来选择下一个。

??? (q?q,k?allowed) Exploitation v?argmax???????ijijk0????v?V

(q?q0) Exploration 〔1〕

〔其中allowedk??0,1,,n?1??tabuk 表示蚂蚁k当前选择的城市集合，tabuk为禁忌表，它记录蚂蚁k已经路过的城市，用来说明人工蚂蚁的记忆性。?ij用于评价蚂蚁由点i 向点j 移动的启发函数，其值通常用距离的倒数求得，即?ij?d?ci,cj?。?,?表达了信息素

?1和启发信息对蚂蚁决策的影响。?取值为1；参数??0描述启发函数的重要性;参数q0〔0?q0?1〕决定利用和开发的相对重要性，利用〔Exploitation〕指走最好的路，开发〔Exploration〕指按信息素浓度高概率高的原那么选择V, q是在[0,1]上任取的随机数〕

. -可修编.