蚁群算法PPT课件

20 04 2020 1 来源于生物界的蚁群算法在车辆路径问题 VRP 中的应用 学号 姓名 指导教师 20 04 2020 2 1 VRP的问题来源和研究现状 论文要点 2 蚁群算法及其在VRP中的具体应用 3 VRP程序设计和求解分析 来源于生物界的蚁群算法在车辆路径问题 VRP 中的应用 20 04 2020 3 1 VRP的问题来源和研究现状 物流 Logistics 20 04 2020 4 通常意义下的VRP的提法为 已知一批客户 每个客户点的位置和货物需求已知 车辆的负载能力一定 每辆车都从起点 depot 出发 完成若干客户点的运送任务后再回到起点 假设每个客户被而且只被访问一次 每辆车所访问的城市的需求总和不能超过车辆的负载能力 问题是使所有客户需求都得到满足 且总旅行成本最小 1 VRP的问题来源和研究现状 车辆路径问题 VehicleRoutingProblem 简记VRP 是物流配送优化中关键的一环 20 04 2020 5 VRP已经被证明是NP hard问题目前提出的求解算法很多 20 04 2020 6 1 VRP的问题来源和研究现状 求解方法 Solution 20 04 2020 7 2 蚁群算法及其在VRP中的具体应用 蚁群算法与VRP 20 04 2020 8 2 蚁群算法及其在VRP中的具体应用 蚂蚁选择最短路径的原理 信息素 信息素浓度越高蚂蚁越容易选择 经过时间越长信息素挥发越多蚂蚁选择较短路径 20 04 2020 9 2 蚁群算法及其在VRP中的具体应用 代表路径上的信息素浓度对选择概率的影响 信息素浓度越高 选择该路径的机率就越大 故实际上就是蚁群的正反馈机制 吃午饭了 去一食堂还是二食堂呢 大家都去一食堂吃饭 我也去一食堂吧 代表路径上的启发因子 为路径间的距离 即距离越小选择该路径的机率就越大 故启发因子实际代表蚂蚁的能见度 要吃午饭了 去一食堂还是二食堂呢 二食堂比较近 去二食堂吧 为随机因子 即在选择路径时给与蚂蚁适当扰动 要吃午饭了 今天到底是去一食堂还是二食堂呢 随便选一个吧 20 04 2020 10 2 蚁群算法及其在VRP中的具体应用 对于蚁群算法中的等相关参数 的选择 目前还没有成熟的理论可供参考 一般只能通过实验进行选择 信息素挥发 本文中 信息素更新策略采用最大 最小蚂蚁系统MMAS算法 因为经大量学者实验验证 这种更新机制有较好的效果 20 04 2020 11 3 VRP程序设计和求解分析 本文求解VRP主要采取蚁群优化2阶段构造算法 AntConstructiveAlgorithm 即 第1阶段 根据蚁群优化准则 每次将一个不在线路上的点增加进线路 直到所有的点都被安排进线路为止 第2阶段 将得到的可行解进行2 OPT变换优化 20 04 2020 12 3 VRP程序设计和求解分析 第1阶段 根据蚁群优化准则 每次将一个不在线路上的点增加进线路 直到所有的点都被安排进线路为止 20 04 2020 13 3 VRP程序设计和求解分析 从当前点出发 根据选择概率选择下一个点 20 04 2020 14 3 VRP程序设计和求解分析 第2阶段 将得到的可行解进行2 OPT变换优化 2 opt原理 20 04 2020 15 3 VRP程序设计和求解分析 以上为程序设计原理 具体程序流程如下 BEGINDO FOR i 0 i 最大蚂蚁组数 i FOR j 0 reach 1 reach 最大节点数 j j为蚂蚁数 初始化一只蚂蚁 即将一只蚂蚁放到起点 WHILE 蚂蚁没有达到最大载重量且仍然有节点未经访问 蚂蚁按照选择概率公式 1 选择下一节点 reach reach代表已经访问的节点数 reach ant n i j 将这组蚂蚁的蚂蚁数记录下来nextant 转到下一组蚂蚁 FOR i 0 i 最大蚂蚁组数 i FOR j 0 j 本组蚂蚁数 j 对每一只蚂蚁进行2 opt交换 比较得到的解选择本次循环得到的最好蚂蚁 将其与全局最好解进行比较 按照全局最优解根据公式 2 更新信息素nc WHILE nc NC 迭代结束 输出最优解 20 04 2020 16 3 VRP程序设计和求解分析 程序流程图 20 04 2020 17 3 VRP程序设计和求解分析 为了检验算法的结果 求解实例全部采用osiris tuwien ac at网络公布的CVRP测试问题 下载网址为 http osiris tuwien ac at wgarn VehicleRouting neo Problem 20Instances CVRPinstances html 各实例验证结果如下 20 04 2020 18 3 VRP程序设计和求解分析 实例 A n33 k5 实验时 取迭代次数为20次 选择概率权重为信息素挥发 20 04 2020 19 3 VRP程序设计和求解分析 将表格数据画图得 20 04 2020 20 3 VRP程序设计和求解分析 得到的A n33 k5具体运输路线 20 04 2020 21 谢谢观赏 结束 20 04 2020 22 20 04 2020 23 分支定界法 BranchandBoundApproach 6 分支定界法是一种应用范围很广的搜索算法 它的基本思想是把给定问题分解为若干个较小的子问题 每个子问题又可继续分解 直到子问题不能再分解或不能产生最优解 根据问题的特点和不同的策略 把问题分解为子问题的过程称之为分支 分支定界法求解VRP问题的基本思想是 以相应的不含整数约束的VRP问题 B 的最优解为出发点 若此解是整数解 那么这个解就是原VRP问题 A 的最优解 否则以B的非整数解的相邻整数作附加条件 形成2个分支 即2个子问题 进行求解 若对上面2个子问题求出最优解是整数解 则停止该子问题的分支 否则继续分支求解 这种方法只能适用于求解小型VRP问题 Kolenatal曾利用此方法求解含时间窗约束的车辆巡回问题 发现当节点数扩大至12时 计算机有内存不足的现象产生 20 04 2020 24 割平面法 CuttingPlanesApproach 6 割平面法求解VRP问题 A 的基本思想是 在求解相应的不含整数约束的VRP问题 B 上 增加线性约束条件 几何术语称为割平面 以将B的可行域切割掉一部分 使其切割掉的部分只包含非整数解 没有切割掉任何整数可行解 直到切割后得到的可行域有一个整数坐标的极点恰好是A的最优解为止 由于割平面法求解时间过长 故不适用于大规模问题 20 04 2020 25 网络流算法 NetworkFlowApproach 6 网络流算法求解VRP问题的基本思想是 首先构建VRP问题的网络模型 找到网络中需调量最大的弧 然后通过调节弧流量或弧两端节点上的位势 来减少弧上的需调量 直至所有弧的需调量都等于零 由于网络模型的顶点数目和边的数目会显著影响网络流算法时间效率 所以这种算法只适用于小规模的VRP问题 20 04 2020 26 动态规划方法 DynamicProgrammingApproach 6 动态规划法求解VRP问题的基本思路是 将VRP问题视为一个阶段的决策问题 进而将其转化为依次求解具有递推关系的单阶段的决策问题 从而简化计算过程 用这种方法可求得VRP的最优解 但仅适用于较小规模的寻优问题 此外 Fisher 1985 Jomstern 1986 Madsen 1990 Halse 1992 等人分别用