基于蚁群算法的物流车辆路径优化问题的研究精编版

1、 车辆路径规划概述 蚁群算法简介 VRP问题的相关研究 改进的ACO及TSP求解 CVRP问题及求解 Contents 目 录 1 车辆路径问题概述 车辆路径规划概述 车辆路径调度问题是由 G Dantzig 首先提出的, N Christofides 在 后来总结深化。 车辆路径问题（VRP），主要解决的是派多少辆车走什么样的路线 进行运输的问题。具体来讲，就是给定了相互连通的若干有货物需求的 顾客点，若干车辆从配送中心出发，完成对所有顾客点的配送任务后回 到配送中心，要求所走的路线不能重复，目的是找到最小成本的配送方 案。 根据实际约束条件的差异，车辆路径问题种类千 变万化，并各具特色。

2、经典车辆路径问题，其实就是在车辆路径的调度中，仅仅考虑最基本 的货车载重量约束(或容量约束)的最一般化的运输问题，即有容量约束 的车辆路径问题(Capacitated Vehicle Routing Problem）。 经典VRP要求满足的条件及假设： 经典车辆路径问题CVRP 1 2 3 CVRP的数学模型 k k：第：第k k辆车辆车 ：运输车辆的数量：运输车辆的数量 ：车辆：车辆k k所走的路径的集合所走的路径的集合 带时间窗的车辆路径问题VRPTW 在很多时候，会要求在一定时间范围内到达顾客点(当然有时配送中心 也有时间范围限制)，否则将因停车等待或配送延迟而产生损失。比较而言， 时间

3、窗VRP除了必须实现经典 VRP 的要求，还要考虑访问时间的限制，这 样才能找到合理方案。 软时间窗软时间窗VRPVRP：要：要 求竟可能在时间窗求竟可能在时间窗 内到达访问内到达访问 硬时间窗硬时间窗VRPVRP：必：必 须在时间窗内到达须在时间窗内到达 访问访问 VRPTW 的数学模型 2 VRP问题的相关研究 对对VRPVRP问题的相关研究问题的相关研究 求解问题的精确算法求解问题的精确算法 分支定界法 Laporte等人利用VRP和其松弛形式T-VRP之间的关系,把T- VRP转化成了TSP的分枝定界算法求解了一般问题 动态规划算法 将VRP问题视为一个n阶段的决策问题,进而将其转化为

4、依次 求解n个具有递推关系的单阶段决策问题.Eilon通过递归的 形式利用动态规划法求解具有固定车辆数的VRP问题 三下标车辆流方程 由Fisher等人提出,用以求解带能力约束、时间窗口以及无 停留时间的VRP问题。在该方程中,两个下标表示弧或边,另 一个下标表示车辆的序号。 二下标车辆流方程 Laporte提出了用以求解对称的一般VRP问题,结合了爬山法 的思想,核心依然是线性规划。 求解问题的元启发式算法求解问题的元启发式算法 禁忌搜索算法 由Glover在1986年提出，是一种全局逐步寻优算法,此算法采用 禁忌搜索表纪录已达到过的局部最优点,在下一次搜索中对于禁 忌表中的节点有选择或是不

5、再选择，以此来避免陷入局部最优 解。Gendrean最先用此法解决VRP问题 模拟退火算法 解决VRP问题时，将物理退火中原子获得的能量相当于分配最优 节点，将原子震动模拟为线路寻优空间的随机搜索。（Laporte 和Teodorovic） 遗传算法 Berger和Barkaoui（2004）利用并行混合遗传算法求解带时间 窗的车辆路径问题。郎茂祥通过构建单亲遗传算法,有效改进了 传统遗传算法对复杂问题搜索效率低,易陷入过早收敛的缺陷。 蚁群算法蚁群算法 Bullnheimer B.等人首先将蚁群算法的思想用于VRP问题。Bell John.E等提出一种改进的蚁群算法用来求解VRP。Alber

6、bo V等 人改进蚁群算法求解TDVRP。刘志硕等人构造了求解的自适应蚁 群算法。 3 蚁群算法简介 蚁群算法简史 2001年至今 1996年-2001年 意大利学者 Dorigo1991年 启发 各种改进算法的提出，应用领域更广各种改进算法的提出，应用领域更广 引起学者关注，在应用领域得到拓宽 ACO首次被系统的提出首次被系统的提出 自然界中真实蚁群集体行为 蚁群算法简史蚁群算法简史 u蚁群算法（Ant Algorithm)是一种由自然界真实蚂蚁 觅食行为提炼而成的优化算法，于1991年，由意大利学 者Macro Dorigo在其博士论文中提出，并成功的解决了 旅行商（TSP）问题。 u19

7、96年,Macro Dorigo等人在IEEE系统、人、控制论 汇刊上发表了”Ant system:optimization by a colony of cooperating agents”一文，系统地阐述了 蚁群算法的基本原理和数学模型，蚁群算法逐渐引起了 世界许多国家研究者的关注，其应用领域也得到了迅速 拓宽。 u1998年10月在比利时布鲁塞尔召开了第一届蚁群算法 国际研讨会（ANTS），标志着蚁群算法的正式国际化。 u2000年，Marco Dorigo和Bonabeau E等人在国际顶级 学术刊物Nature上发表了蚁群算法的研究综述，从 而把这一领域的研究推向了国际数学的最前沿

8、。 u在我国，最早关于蚁群算法的研究见于1997年10月张 纪会与徐心和发表的论文“一种新的进化算法蚁群 算法”中。 蚁群算法简史 蚁群算法的研究现状蚁群算法的研究现状 目前，人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决 一维静态优化问题发展到解决多维动态优化组合问题，由离散域范围内研究逐渐拓展到 了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也 取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。 有学者通过对比实验发现 ，在组合优化问题中，蚁 群算法的优化性能要好于 遗传算法等算法。 蚁群算法是一种基于种 群的启发

9、式搜索算法 。 蚁群算法广泛应用于求 解TSP问题，Job-Shop 调度问题，二次指派问 题，背包问题等。 蚁群算法蚁群算法 是一种很有发展 前景的优化算法 蚁群算法原理蚁群算法原理 蚁群算法原理 蚂蚁能快速找到最佳觅食路径是因为在蚂蚁个体之 间是通过一种称为信息素的物质进行信息传递的。蚂蚁 在运动过程中，不但能够在它所经过的路径上留下该物 质，而且能够感知这种物质的存在及其强度，并朝着该 物质强度高的方向移动，以此指导自己的运动方向。 因此，由大量蚂蚁组成的蚁群集体行为表现出一种 信息正反馈现象。在一定时间内较短路径通过的蚂蚁要 多于较长路径，而某一路径上走过的蚂蚁越多，则后来 的蚂蚁选择

10、该路径的概率就越大。 下图是一个形象化的图示，用以说明蚁群的路径搜索过程 蚂蚁觅食协作本质可概括成如下三点： 路径概率选择机制：信息素踪迹越浓的路径，被选中的概率越大； 信息素更新机制：路径越短，路径上的信息素踪迹增长得越快； 协同工作机制：蚂蚁个体通过信息素进行信息交流。 蚂蚁算法采用人工蚂蚁模拟自然界蚂蚁的寻径方式，每个 人工蚂蚁的行为符合下列规律 人工蚂蚁的寻径规律人工蚂蚁的寻径规律 根据路径上的信息素浓度，以相应的概率来选取下 一步路径； 0101 不再选取自己本次循环已经走过的路径为下一步路 径，用一个数据结构( tabu list )来控制这一点； 0202 当完成了一次循环后，根

11、据整个路径长度来释放相应 浓度的信息素，并更新走过的路径上的信息素浓度 0303 基于TSP的基本蚁群算法的数学模型 以TSP为例说明 Dorigo等人提出的蚂蚁系统(Ant System)模型,其目标函数是： 模型中会用到的变量: 目m为蚁群中蚂蚁的总数 n为TSP规模 const(0)上的信息素浓度, j) (i, 时刻路径 (t)为t 的蚂蚁数目 时刻位于城市i (t)表示tb ijij i 在在 t t 时刻蚂蚁时刻蚂蚁 k k 由城市由城市 i i 转移到城市转移到城市 j j的状态转移概率的状态转移概率 为了避免残留信息素过多引起残留信息淹没启发信息，在每 只蚂蚁走完一步或者完成对

12、所有n个城市的遍历（也即一个循环结 束）后，要对残留信息进行更新处理。t+n时刻在路径(i, j)上的 信息量可按照如下规则进行调整。 表示信息素挥发系数，则表示信息素挥发系数，则1 1- -表示信息素残留因子，为了防止信息的无表示信息素残留因子，为了防止信息的无 限积累，限积累， 的取值范围为：的取值范围为： 含于含于0,1)0,1) 根据信息素更新策略的不同，Dorigo M 提出了三种不同的基本 蚁群算法模型，分别称之为Ant-Cycle 模型、Ant-Quantity 模型及 Ant-Density模型 的不同求法：)(其主要区别在于 k ij t Ant-Cycle 模型 Ant-Q

13、uantity模型 Ant-Density模型 蚂蚁算法中蚂蚁算法中 Q Q 、 、 、 等参数对算法性能有很大影响等参数对算法性能有很大影响 基本蚁群算法的程序结构流程基本蚁群算法的程序结构流程 4 改进ACO及TSP求解 蚁群算法的基本步骤：蚁群算法的基本步骤： 基本蚁群算法的改进基本蚁群算法的改进 一系列研究结果发现，用基本蚂蚁算法求解时容易如 下出现两个问题： 搜索进行到一定程度后，搜索进行到一定程度后， 所有的个体发现的解基所有的个体发现的解基 木完全一致，出现停滞木完全一致，出现停滞 现象，不能再对解空间现象，不能再对解空间 进一步搜索，导致可能进一步搜索，导致可能 无法找到全局最

14、优解无法找到全局最优解 收敛到全局最优解的收敛到全局最优解的 时间长，求解结果反时间长，求解结果反 复在局部最优解和全复在局部最优解和全 局最优解之间震荡。局最优解之间震荡。 改进算法中位于第i个结点的蚂蚁k，按以下选择策略移动到 结点 j： 内随机取值)()(argmax-allowed依照以下概率在h其中 uki ttU iuiuallowedk 改进算法的转移规则 改进的蚁群算法采用确定性选择和随机选择相结合的选择策 略，并且在搜索过程中动态调整确定性选择的概率。 改进算法的信息素局部更新规则改进算法的信息素局部更新规则 其中， 称为学习率， 称为挥发因子。通过引入蒸发因 子，可以做到对

15、过去信息的慢慢遗忘，因而能够强化后来学习得 到的知识，这样可以使较少的路径得到更多的访问机会，搜索的 范围会更加广，增加蚂蚁选择其它边的概率，防止算法收敛到局 部最优解，有利于发现更好解，不致过早出现停滞现象。 局部更新是为了避免所有蚂蚁都选择同一条路径。 改进算法的信息素全局更新规则改进算法的信息素全局更新规则 在改进的蚁群算法的迭代过程中，全局更新原则只对获得最短 路径的蚂蚁实施。当所有蚂蚁均完成一次循环时，信息素更新采用 如下规则： 蚁群算法应用实例蚁群算法应用实例 以30个城市TSP问题为例，说明蚁群算法的应用。城市的位置 信息如表所示： 计算结果计算结果 22- 2123- 25-

16、- 30- 29- 9- 24- 27 26- 1- 28- 6 - 2 - 3-5- 7 - 8 - 4- 10- 12- 11- 14- 18- 19- 20- 16- 17- 15- 13- 22 每次迭代的最短距离与平均距离对比图 结果对比结果对比 原原 文文 算算 法法 实实 现现 5 CVRP问题及求解 CVRP CVRP 问题的蚁群算法实现问题的蚁群算法实现 VRP 与 TSP 蚁 群 算 法 的 区 别 子路径构造过 程的区别 在 TSP 中，每只 蚂蚁均要经过 所有结点，而 在VRP 中，每 只蚂蚁并不需 要遍历所有结 点。 2 allowedk 的区别在TSP中， 蚂蚁转移

17、时只需考虑路径 的距离和信息浓度即可， 但在VRP中，蚂蚁转移时不 但要考虑上述因素，还需 要考虑车辆容量的限制。 这一差异在算法中的具体 体现就是allowedk 的确定 问题。 1 可行解结构的区别 在求解TSP问题中， 每只蚂蚁所构造出 来的路径均是一个 可行解，但在VRP 问题中，每只蚂蚁 所构造的回路仅是 可行解的“零部件” 3 在VRP 问题中，每只蚂蚁所构造的回路仅是可行解的一个组成部分， 各蚂蚁所构造的回路可能能够组成一些可行解，但也可能一个可行解都 得不到。避免无可行解 可采取以下策略： 大蚂蚁数策略：增加算法的蚂蚁数量M ，扩大组合范围， 从而增加可行解产生的可能性。 蚂蚁初始分布均匀策略：在每次迭代前，将蚂蚁随机均匀分 布于各个结点，从而增加发现可行解的机会。 近似解可行化策略：前两种策略的目的都是为了提高各蚂蚁 所构造的子回路组合成可行解的可能性，是一些针对无可行 解的“事前”预防性措施。 避免无可行解的策略避免无可行解的策略 CVRPCVRP实例仿真实例仿真 下面通过一个实例，进行仿真试验，检验上述算法的有效性及具体 性能。 结点数据如下：假设共有19个客户随机分布，