VRP算法介绍98410.ppt

VRP启发式算法 VRP算法分类 扫描算法 1974 k opt算法 interchange算法 蚁群算法 1991 2003 两阶段算法 1979 粒子群算法 1995 Constructiveheuristicsgraduallybuildsafeasiblesolutionwhilekeepinganeyeonsolutioncost butdonotcontainanimprovementphaseperse LaporteandSemet 2002 TrendsinHeuristics MorecomplexandrichVRPsFasterheuristics disregardingincreasingcomputerspeeds thatstillproduceshighqualitysolutionsAbilitytohandlelargerinstancesMorepreciseheutistics bettersolutionqualitywithoutworryingoverlyaboutthetimeneededforthecomputation SimplerheuristicsHeuristicsusingmathematicalprogramming combiningideasfromexactoptimizationwithheuristics ParallelimplementationsMorerealistictestinstances 一 构造启发式算法 最邻近法算法步骤 任取一点作为线路的起点 寻找与上一次加进线路中的点距离最近的点 把此点加到线路中去 重复2 直到所有的点都已考虑 这就得到了一条线路 14235678 例 练习现有一食品公司 位置在v1处 每天用一辆车给固定区域内的5家超市送货 要求货车到每个超市只能去一次 送完货后返回公司 各点之间的距离如下表所示 其中 距离具有对称性 设计一条派送货物的行驶距离最短的路径 一 构造启发式算法 最近插入法最近插入法 NearestInsertion 是Mole和Jameson于1976年提出的用于求解VRP的一种启发式算法 算法步骤 从一个节点出发 找到一个最近的节点 形成一个往返式子回路 在剩下的节点中 寻找一个离子回路中某一节点最近的节点 再在子回路中找到一个弧 使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小 实际上就是把新找到的节点加入子回路以后使得增加的路程最短 就把这个节点增加到子回路中 删去这条弧 重复以上过程 直到所有的节点都加入到子回路中 最近插入法关键是依序选择最合适的未分配的节点在路线中进行最佳位置的插入 以构建配送路线 直至不存在可行插入节点时新增一条初始路线 例各点之间距离如图所示 运用最近插入法求解最优路径 A B C D 36 42 46 20 52 40 E 65 50 70 解 从A点出发 找到一个最近的节点B 形成一个往返式子回路 在剩下的节点中 寻找一个离子回路中A B最近的节点 得到D 加入子回路中 A B C D 36 42 46 20 52 40 E 65 50 70 对于C点 再在子回路中找到一个弧 使弧的两端节点到C点的距离之和减去弧长的值最小 即d C A d C B d A B 52 46 20mind C D d C B d D B 42 46 40 48d C D d C A d A D 70 50 36则去除线路BD 加入线路BC和CD 其余点重复以上过程 直到所有的节点都加入到子回路中 练习现有一食品公司 位置在v1处 每天用一辆车给固定区域内的5家超市送货 要求货车到每个超市只能去一次 送完货后返回公司 各点之间的距离如下表所示 其中 距离具有对称性 设计一条派送货物的行驶距离最短的路径 一 构造启发式算法 算法思想 设有n个城市 点 取其中的一点 例如点1 作为配送中心 先将每个点与起点相连 构成线路1 j 1 j 2 3 n 即n 1条仅含一个访问点的线路 总费用为 其中 假设c1j cj1 然后 计算将i和j i j 1 连接在一条线路上所引起的路程节约值S i j S i j 2c1i 2c1j c1i cij c1j c1i c1j cijS i j 越大 说明把i和j连接在一起使总费用减少越多 根据S i j 的大小来构造线路 就有可能得到总费用较小的解 C W节约算法 算法步骤 选取起点 将起点与其它各点连接 得到n 1条线路1 j 1 j 2 3 n 对不违背限制条件的所有可连接点对 i j 计算节约值S i j c1i c1j cij 将算出的S i j 0 按从大到小的顺序排列 按照Sij的上述顺序 逐个进行检查 若存在两条这样的线路 一条包含弧或边 i 1 另一条包含弧或边 1 j 且合并后能保持解可行 则引入弧或边 i j 将两条线路合并 并删去 i 1 和 1 j 重复该步骤 直到没有可合并的线路为止 返回步骤4 直至考察完所有可插入弧 i j 为止 例用C W节约算法求下述的旅行商问题 其中点1为起 终 点 各点对间的距离由下表给出 1 将各点分别与点1相连 组成7条线路 2 计算节约值S i j c1i c1j cij 如S 2 3 c12 c13 c23 8 5 8 5 3 将算出的S i j 按从大到小的顺序排列于下表中 4 按照S i j 的大小顺序 考虑连接点i和点j 练习 现有一个仓库v0 需要对8个客户提供货物 它们的如下表所示 它们的距离矩阵如下表所示 假设每个车辆的运输能力是14个单位的货物 现有足够多的车辆 试用扫描算法对该运输问题进行求解 例某配送中心P向10个客户A J配送货物 其道路网如图1所示 图中连线上的数字表示两结点间的距离 km 各客户点旁括号内的数字表示该客户的需求量 t 配送中心有载重量为2t和4t的两种车辆可供使用 但车辆一次巡回的行驶距离不能超过30km 试制定其最优的配送线路 D 0 4 5C 0 8 5B 1 5 6247E 1 4 5691048A 0 7 765P7J 0 6 4343410811F 1 5 6G 0 6 29H 0 8 I 0 5 解下面用C W节约法求解 第一步 根据给出的相邻节点间的距离 求出配送中心至各客户点 各客户点间的最短距离 见下表 表最短距离 第二步 根据最短距离表 计算节约值sij 结果见下表 计算结果有正有负 节约值sij为负数时 无实际意义 故取值为零 表节约值 第三步 将所有的节约值sij按从大到小的顺序排列 见下表 表节约值排序 第四步 按照节约值sij的大小顺序 以及车辆载重量和行驶距离的限制 逐步构造配送线路 初始线路 对每一个客户分别单独派车送货 如下图所示 形成了10条初始配送线路 D 0 4 C 0 8 2B 1 5 796E 1 4 8P10A 0 7 57J 0 6 3410F 1 5 3G 0 6 H 0 8 I 0 5 线路合并 按照节约值sij的大小顺序 连接A B A J D 0 4 C 0 8 2B 1 5 7964E 1 4 8PA 0 7 5743410J 0 6 F 1 5 3G 0 6 H 0 8 I 0 5 连接B C 形成配送线路I 此时该线路的总需求量为3 6t 线路长度为27km 按照sij的大小顺序 现在应考虑是否将C D连接到配送线路I 但若将C D连接到该线路 线路长度将超过30km 不可行 D 0 4 C 0 8 25B 1 5 764E 1 4 8P线路IA 0 7 57J 0 6 43410F 1 5 3G 0 6 H 0 8 I 0 5 接下来 连接D E 开始构造配送线路II 重复该步骤 直到没有可合并的线路为止 得到的最终解如下图所示 共构造出3条配送线路 总的行驶里程为80km D 0 4 C 0 8 25B 1 5 676E 1 4 线路IIP线路I 27km 3 6t430km 3 9tA 0 7 77J 0 6 43410F 1 5 线路III23km 1 3t6G 0 6 H 0 8 9I 0 5 一 构造启发式算法 扫描算法扫描算法 SweepAlgorithm 最早是由Gillett和Miller 1974 提出的 是用于求解车辆数目不限制的VRP的一种启发式算法 扫描算法本质上是将距离近的客户归并到一个子路径中 扫描算法步骤 Step1建立极坐标系 Step2分组 Step3重复2的过程 Step4线路优化 Step1建立极坐标系 以起始点 配送中心 作为极坐标的原点 并以图中的任意一客户点和极点 配送中心 的连线定义为角度零 建立极坐标系 然后对所有的客户所在的位置进行极坐标系的变换 把所有客户点全部都转换为极坐标系下的点 STEP2分组 从最小角度的两个客户开始 建立一个组 按逆时针或者顺时针方向 将客户逐个加入到组中 直到客户需求总量超过了车辆负载限制时 结束该条线路 STEP3重复STEP2的过程 建立一个新的组 继续按照逆时针或者顺时针方向 将客户继续逐个加入到组中 生成新的线路 直到所有的客户点都被分到某个组为止 STEP4线路优化 对各个分组内的客户群就是一个个单独的TSP 其中 各组的起点都是极点 求解TSP 得到优化线路 例某配送中心P向客户点配送货物 图中各客户点旁括号内的数字表示该客户的需求量 t 配送中心有载重量为2t的车辆可供使用 试制定其最优的配送线路 P A 0 2t B 0 8t C 0 7t D 0 2t F 0 2t G 0 1t H 1 2t I 0 5t 显然 根据扫描算法 可以把客户点分为不同的两组 分别为 A B C D F G H I 分组完成后 即可对组内的客户点进行路径优化 P A 0 2t B 0 8t C 0 7t D 0 2t F 0 2t G 0 2t H 1 2t I 0 6t 一 构造启发式算法 两阶段算法先排程后分组这种方法首先构造一条或几条很长的线路 通常不可行 它包括了所有需求对象 然后再把这些很长的线路划分成一些短而可行的线路 具体进行时 一般是先解一个经过所有点的旅行商问题 形成一条线路 然后根据一定的约束 如车辆容量等 对它进行分划 先分组后排程这种方法先把节点和 或 弧的需求进行分组或划群 然后对每一组设计一条经济的线路 如扫描算法 其目的在于形成需求点的径向区域 从车场发出的射线 扫过 这个区域 使不超过车辆容量的需求点组成一个区域 一个区域就是一个组 当形成一系列这样的组后 再对每一组中的各点安排线路 二 改进启发式算法 局部搜索 黑夜的登山者 这里是山顶 局部最优解 近邻 neighborhood 近邻 对于某一个实行可行解x F 将x进行一些适当的变形所得到的可行解集合 近邻N x x 近邻操作 neighborhoodoperation 近邻操作 从某一可行解x出发 为了在其近邻N x 中生成一个可行解而使x适当变形的操作 局部最优解 locallyoptimalsolution N x 当中不再存在改善解的x 则称x为关于N x 的局部最优解 全局最优解 globallyoptimalsolution 应用局部搜索的概念 通过对边 成弧 进行交换 在初始可行解的邻域中对初始解进行调整 每次调整使可行解得到改进 直至解在邻城内不能改进为止 二 改进启发式算法 k opt算法基本原理是应用局部搜索的概念 通过对k条边 弧 行交换 在初始解的邻域中对初始解进行调整 每次调整接受得到改进的可行解 直至解在其邻域内不能改进为止 最终解就叫做k 最优解 k opt k是一开始就设定的常数 从巡回路径中找出k条边 共有Cnk中选择方法 必须全部考虑到 如果无论选出哪k条边替换都不能进一步优化 则称这条巡回路径是k 最优 显然 k越大优化后的效果越好 可是随着k增大 计算量也快速增大 考虑到计算时间的限制 一般都选较小的k 最常用的是2 opt和3 opt 2 opt算法 3 opt算法 3 opt算法是局部搜索算法中效率最高的k opt邻域算法 其基本过程是 设T是一条初始路径 产生3个随机位置x0 y0 z0 它们的下一个节点分别记为x1 y1 z1 对应的3条边的集合记为 a b c 三条边互不相邻 该算法试图找到另一个边集合 a1 a2 a3 使得新的费用变小 这里是3条边则称为3 opt 3 opt算法 图3 opt算法示意 0 1 2 3 4 5 6 7 8 9 在可行解中随机抽取三条互不相邻的边23 56和89 找出另一边的集合26 58和39使之形成回路 计算 如果d23 d56 d89 d26 d58 d39则交换两条回路 则交换后的解优于原来的解 如果d23 d56 d89 d26 d58 d39则保持原来的解不变 在改进的可行解中重复以上工作 直到不能改进为止 3 交换 3 opt 算法 3 opt算法中 打断抽取的三条边后 共有四种回路可选 见下图 0 1 3 4 5 6 7 8 9 2 1 26 58 39 0 1 3 4 5 6 7 8 2 2 26 59 38 9 3 交换 3 opt 算法 5 0 1 3 4 6 7 8 2 9 3 25 69 38 5 0 1 3 4 6 7 8 2 9 25 68 39 5 不合理的回路 0 1 3 4 6 7 8 2 9 28 35 69 5 0 1 3 4 5 6 7 8 2 0 1 3 4 5 6 7 8 2 4 29 35 68 9 3 29 58 36 3 交换 3 opt 算法 分别找出四条可能的回路 26 85 3