《04讲(路线规划)ppt课件》由会员分享，可在线阅读，更多相关《04讲(路线规划)ppt课件（161页珍藏版）》请在金锄头文库上搜索。
1、配送线路规划 第四章 4 27 2020 P2 两点间路径问题 T标号 TentativeLabel P标号 PermanentLabel 4 27 2020 P3 多点间路径问题 4 27 2020 P4 2020 4 27 4 Floyd算法 Floyd算法是寻找加权图 权值可为负 中任意两个结点间最短路径的算法 思路 两结点间的最短路径要么是相邻时最短 要么是以通过几个中间结点为跳板时距离最短 算法每次以其中一个结点为跳板 如果以该结点为跳板后两结点间路径缩短 则更新这两结点间的路径 算法执行V次结束 直到测试完每个充当跳板的结点 4 27 2020 P5 2020 4 27 5 Flo
2、yd算法 过程 Floyd算法采用邻接矩阵W作为图的存储结构 W i j 表示结点vi和vj之间的距离 权重 D k 记录经历k步后 两点间的路径长 k 0 n 初始时 W D 0 P记录每步更新时结点间经历的中间结点 通过对P矩阵的回溯操作 可得两点间的最短路径 初始时 P为0矩阵 4 27 2020 P6 2020 4 27 6 Floyd算法 算法第k步的更新规则 以结点k为跳板 测试通过该结点后 两点间距离是否缩短 若距离不缩短则保留k 1步的结果 D k i j D k 1 i j 若距离缩短则更新两点间的距离 D k i j D k 1 i k D k 1 k j 即 D k i
3、j min D k 1 i j D k 1 i k D k 1 k j 如果第k个结点对缩短vi和vj间的路径做出贡献 P i j k 4 27 2020 P7 2020 4 27 7 Floyd算法 Floyd算法实例 图G及算法初始状态 D 0 W P 0 如下所示 2020 4 27 8 Floyd算法 2020 4 27 9 Floyd算法 矩阵D 4 中 无穷大元素表明其坐标对应的结点间无路径可达 其它元素表示两点间最短路径的长度 最终P指示如何通过回溯得到两结点间的最短路径 例 2到4的最短路径经过3 则有2 3 4 2到3经过1 则有2 1 3 4 2到1再无结点 P中对应0 回
4、溯结束 2到4之间最短路径为2 1 3 4 D 2 4 9 运输问题 略 线路问题的引入 1 车辆运送作业是物流中心最终及最具体直接的服务表征 运送管理的困难在于其可变因素太多 而且因素与因素间往往又相互影响 最直接的影响反映在运送的费用上 车辆路线问题 VRP 是物流中心成本问题的重要主体 如考虑到顾客需求量不确定的限制 该问题研究的重点是如何处理车辆的安排 运送路径选择 运送顺序的问题 等等 以求得成本最小 线路问题综述 TSP的假设是 有n个城市C1 C2 Cn Dij表示Ci与Cj间的距离 有一个推销员从某一城市出发 访问各城市且仅一次 再回到原出发城市 要求找一条最短的巡回路线 问题
5、的提出 推销员旅行问题 TSP TravelingSalesmanProblem 假设车辆具有容量限制下 找出通过所有需求点总成本最小的数条路线 同时每条路线必须由场站 Depot 出发 服务过数个需求点后再回到场站 主要目标是在满足下列限制 并求得每部车辆拜访顾客的顺序 使得车辆行驶总距离最短 1 每个需求点只能由一辆车服务一次 2 须满足所有需求点的需求 3 每一辆车都由场站出发 最后须回到场站 4 每车辆所服务的总需求量不能超过该车辆的容量 传统车辆路线问题 VRP VehicleRoutingProblem TSP VRP问题的传统求解 穷举搜寻 ExhaustiveSearchMet
6、hods 动态规划 DynamicProgrammingMethods 整数规划法 IntegerProgrammingMethods 分枝界限法 BranchandBoundMethods 正确解 ExactSolution 穷举搜寻法是一种简单但是费时的方法 因为它要把所有可能的路径集合解都列举出来 然后从中选择一个最短的 从组合数学的理论可知 当城市数目为n时 穷举法的方案数为 如果考虑每条路径要计算n个距离之和 则计算的工作量将正比于n 2 以下是用每秒运算100亿次加法计算的计算机按穷举搜寻法计算TSP所需的时间 穷举搜寻 ExhaustiveSearchMethods 以穷举法求解
7、TSP所需的计算时间表 4 27 2020 P18 整数规划法 IntegerProgrammingMethods 4 27 2020 P19 设S表示从v1到vi中间所可能的集合 S中的点的个数要随阶段改变 阶段 S中的点的个数 状态变量 i S 从v1点出发 经过S集合中所有点一次最后到达vi 最优指标函数fk i S 从v1出发 经过S集合中所有点一次最后到达vi 决策变量Pk i S 从v1经k个中间城镇的S到vi城镇的最短路线上邻接vi的前一个城镇 状态转移方程 边界条件 动态规划 DynamicProgrammingMethods 动态规划法最主要的特色 是将一个问题切成好几段相互
8、联系的阶段 接着在每个阶段去进行决策上的最佳化 在此每一个阶段决策最佳化的过程中 无论一开始的状况和一开始的决策为何 以后的最佳化策略都只取决于一开始决策所形成的当时状态 由于动态规划法是经过各个阶段性的最佳化决策过程 将之与穷举法比较 将会减少组合过多的问题 下页列出了不同城市数的TSP动态规划法 空间及时间的复杂度 例如以n 60为例 用一台每秒运算100亿次加法运算的计算机求解TSP时 需时超过3230年 动态规划 DynamicProgrammingMethods 不同城市数的TSP动态规划法 空间 时间复杂度 分枝界定法 BranchandBoundMethods 分枝界限法的三个主
9、要步骤为 分枝 界限 剪枝 先将问题的可行解展开为分枝树 而在搜寻分枝的过程中 同时设定解值的上限或下限值 当某节点其下限值超过问题的上限时 表示解比目前已求得的解差 则停止再往下分枝 重复搜寻步骤 再由各个分枝中寻找最佳解 4 27 2020 P23 1 任取初始H圈 C0 v1 vi vj vm v1 2 对所有的i j 1 i 1 j m 若 w vi vj w vi 1 vj 1 w vi vi 1 w vj vj 1 则在C0中删去边 vi vi 1 和 vj vj 1 而加入边 vi vj 和 vi 1 vj 1 形成新的H圈C 即C v1 vi vj vj 1 vi 1 vj 1
10、 vi v1 3 重复步骤 2 直到条件不满足为止 最后得到的C即为所求 二次逐次修正法 4 27 2020 P24 4 27 2020 P25 最差情况下 Worst caseAnalysis 若总节点数目为n 则出发点有n种选择 第2个节点的选择为n 1 第3个节点为n 2 依次递减 所以总组合数目为n 计算量仍然很大 以分枝界限法求解TSP所需的计算时间表 以上问题属于 未定论多项式难度 问题 NondeterministicPolynomialHard NP Hard 即在求解最佳解的时候 随着目标节点的增加 其难度会呈指数增长的问题 我们需要另辟蹊径 首先界定问题 TSP VRP问题
11、传统解法的总结 途程问题 RP RoutingProblem 节线途程问题 LRP LinkRoutingProblem 旅行推销员问题 TSP 节线途程问题 NRP NodeRoutingProblem 多重推销员问题 MTSP 多场站途程问题 MDVRP 单场站途程问题 VRP 随机途程问题 SVRP 中国邮差问题 CPP 载量限制邮差问题 CCPP 基本途程问题族谱图 途程问题细分 启发式 heuristics 意为通过对过去经验的归纳推理以及实验分析来解决问题的方法 即借助于某种直观推断或试探的方法 启发式方法要求分析人员必须运用自己的感知和洞察力 从与研究问题有关而较基本的模型及算法
12、中寻求其间的联系 从中得到启发 去发现适于解决该问题的思路和途径 用启发式方法解决问题时强调 满意 而不去追求最优性和探求最优解 原因是 1 很多问题不存在严格最优解 例如目标之间矛盾的多目标问题 这时 对目标的满意性常比最优性更能准确地描述人们的选择行为 2 对有些问题 得到它的最优解所花的代价太大 3 从实际决策的需要出发 有时要求解具有过高的精度没有意义 启发式方法能够比较快地得到满意解 这对NP Hard来说有着不可估量的作用 启发式算法heuristics 4 27 2020 P32 线路优化的常见启发式算法 2 1 50年代Dantzig Ramser 1959 利用整数规划模式
13、IntegerProgramming 来处理规模较小的问题 大约10到20个客户点 2 60年代Clarke Wright 1964 提出节省法 SavingMethods 来建立车辆配送路线 以及Christofides Eilon 1969 应用2 Opt及3 Opt方法处理较大规模的问题 大约30到100个客户点 3 70年代很多学者提出两阶段启发式算法 Two PhaseHeuristics 来求解车辆途程问题 约有100到1000个客户点 如GillettandMiller 1977 提出先途程后分群 以及Christofidesetal 提出先分群后途程的方法 4 80年代Fish
14、er Jaikumar 1981 提出数学规划法来处理大约50个客户点的问题 5 90年代很多学者利用宏启发式解法 Meta heuristics 来解决车辆途程问题 如 Robusteetal 1990 Alfaetal 1991 利用模拟退火法 SimulatedAnnealing Sement Taillard 1993 Gendreauetal 1994 Rochat Taillard 1995 以及Kelly 1996 都利用禁制搜寻法 TabooSearch 来求解问题 4 27 2020 P35 节省法 SavingAlgorithm 2 1 节省法 SavingAlgorith
15、m SA 本书中的概念是指Clarke Wright 1964 提出的节省法 基础SA为其他衍生节省法的基础 4 27 2020 P37 节省法的运作过程 a 路线连结 join 4 27 2020 P38 节省法的运作过程 b 并入 attach 4 27 2020 P39 节省法的运作过程 c 合并 merge 4 27 2020 P40 节省法的连接节线原则 1 节线 i j 中的i j点 不能被包含在某一路线中 4 27 2020 P41 节省法的连接节线原则 2 若节线 i j 中的i或j已包含在某一路线时 只要此点不是路线中的中间点即可 4 27 2020 P42 节省法的连接节线
16、原则 2 若节线 i j 中的i或j已包含在某一路线时 只要此点不是路线中的中间点即可 4 27 2020 P43 节省法的连接节线原则 3 若节点i与j分属两条不同路线 只要此两点皆是路线的端点 路线就可以合并 i j 4 27 2020 P44 研究问题 节省量计算 节省量排序 连接原则 限制条件 连结 并入 合并 节省量大于0 输出结果 符合 不符合 Y N 节省法求解流程 4 27 2020 P45 无约束的单车辆配送问题 4 27 2020 P46 首先计算节省量 并从大到小排序 4 27 2020 P47 H C B A G F E D 绘制出参考图如下 4 27 2020 P48 H C B A G F E D Step1 4 27 2020 P49 H C B A G F E D Step2 4 27 2020 P50 H C B A G F E D Step3 4 27 2020 P51 H C B A G F E D Step4 4 27 2020 P52 H C B A G F E D Step5 4 27 2020 P53 H C B A G F E D Ste
