模块八---配送路线的规划作业

1、模块八模块八 配送路线的规划作业配送路线的规划作业 知识目标知识目标 配送路线规划的意义及原则 配送路线规划的目标 影响配送路线规划的因素影响配送路线规划的因素 配送路线优化的方法 第一节第一节 配送路线规划的意义及原则配送路线规划的意义及原则 近近年来年来,由于小批量由于小批量,多批次的及时配送方式的发展多批次的及时配送方式的发展,运输费用正运输费用正 在逐年提升在逐年提升,许多企业的运费已经超越了库存费用许多企业的运费已经超越了库存费用. 选择有效的配选择有效的配 送路线送路线,已成为控制物流成本的主要措施已成为控制物流成本的主要措施. 那么如何选择有效的配那么如何选择有效的配 送路线呢送

2、路线呢? 有有效的配送路线，实际上是在保证商品准时到达客户指定点的前效的配送路线，实际上是在保证商品准时到达客户指定点的前 提下，尽可能的减少运输的车次和运输的总路程提下，尽可能的减少运输的车次和运输的总路程. 在这种思想的指在这种思想的指 导下，节约法已成为选择配送路线的主要方法导下，节约法已成为选择配送路线的主要方法,并受到国内外物流并受到国内外物流 界的青睐界的青睐. 通通常认为，配送是近距离，小批量，品种比较复杂，按用户需要搭配品常认为，配送是近距离，小批量，品种比较复杂，按用户需要搭配品 种与数量的服务体系。从配送中心把货物送到所需要的各个用户，有很种与数量的服务体系。从配送中心把货

3、物送到所需要的各个用户，有很 多不同的路线选择方案。合理的选择配送路线，对企业和社会具有很重多不同的路线选择方案。合理的选择配送路线，对企业和社会具有很重 要的意义：要的意义： 优化配送路线，可以提高配送效率，对配送车辆做到优化配送路线，可以提高配送效率，对配送车辆做到 物尽其用尽物尽其用尽 可能的降低配送成本可能的降低配送成本。 可以准时、快速地把货物送到客户的手中，能极大地可以准时、快速地把货物送到客户的手中，能极大地 提高提高 客户满意度。客户满意度。 有利于企业提高效益。有利于企业提高效益。 对社会而言对社会而言，它可以节省运输车辆，缓解交通紧张状况，减少噪音、尾，它可以节省运输车辆，

4、缓解交通紧张状况，减少噪音、尾 气排放等运输污染，为保护生态平衡、创造美好家园做出贡献。气排放等运输污染，为保护生态平衡、创造美好家园做出贡献。 进行配送路线优化时，必须有明确的目，遵循基本的原则。配送 路线方案目标的选择可以从以下几个方面来考虑： 配送效益最高或配送成本最低配送效益最高或配送成本最低 配送里程最短配送里程最短 配送服务水准最优配送服务水准最优 配送劳动的消耗最小配送劳动的消耗最小 考考 虑虑 因因 素素 配送路线规划的目标 以效益最高为目标以效益最高为目标 以成本最低为目标以成本最低为目标 以路程最短为目标以路程最短为目标 以吨千米最小为目标以吨千米最小为目标 以准确性最高为

5、目标以准确性最高为目标 以运力最合理为目标以运力最合理为目标 以劳动消耗最小为目标以劳动消耗最小为目标 影响配送路线规划的因素影响配送路线规划的因素 道道 路路 交交 通通 网网 配配 送送 中中 心心 位位 置置 客客 户户 分分 布布 状状 况况 车车 辆辆 运运 行行 限限 制制 车车 辆辆 额额 定定 载载 重重 量量 道道 路路 状状 况况 ； 如如 最最 大大 承承 载载 力力 车车车车 流辆流辆 量通量通 的行的行 变高变高 化潮化潮 ； 如如 上上 下下 班班 配送路线优化的方法配送路线优化的方法 标号法标号法 节约里程法节约里程法 优 化 的 方 法 需求网络中两点需求网络中

6、两点 间最短线路的方法，间最短线路的方法， 叫做标号法叫做标号法 当由一个配送中心向多个客户进行共当由一个配送中心向多个客户进行共 同送货，在同一条线路上的所有客户同送货，在同一条线路上的所有客户 的需求量总和不大于一辆车的额定载的需求量总和不大于一辆车的额定载 重时有这一辆车配装着所有客户需求重时有这一辆车配装着所有客户需求 的货物按照预先设计好的最佳路线一的货物按照预先设计好的最佳路线一 次讲货物送给到客户中。次讲货物送给到客户中。 10 1 1、双标号法、双标号法 o最短路问题：对一个赋权的有向图最短路问题：对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找到一找到一 条

7、从条从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条的路，使得这条路上所有弧的权数的总和最小，这条 路被称之为从路被称之为从Vs到到Vt的最短路。这条路上所有弧的权数的总和被称为的最短路。这条路上所有弧的权数的总和被称为 从从Vs到到Vt的距离。的距离。 一、求解最短路的一、求解最短路的Dijkstra算法算法(双标号法）双标号法） 步骤：步骤： 1.给出点给出点V1以标号以标号(0,s) 2.找出已标号的点的集合找出已标号的点的集合I，没标号的点的集合，没标号的点的集合J以及弧的集合以及弧的集合 3. 如果上述弧的集合是空集，则计算结束。如果如果上述弧的集合是空集，则计算

8、结束。如果vt已标号（已标号（lt,kt），则），则 vs到到vt的距离为的距离为lt，而从，而从 vs到到vt的最短路径，则可以从的最短路径，则可以从kt 反向追踪反向追踪 到起点到起点vs 而得到。如果而得到。如果vt 未标号，则可以断言不存在从未标号，则可以断言不存在从 vs到到vt的有的有 向路。如果上述的弧的集合不是空集，则转下一步。向路。如果上述的弧的集合不是空集，则转下一步。 4. 对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的。在所有的 sij中，找中，找 到其值为最小的弧。不妨设此弧为（到其值为最小的弧。不妨设此弧为（Vc,

9、Vd），则给此弧的终点以双），则给此弧的终点以双 标号（标号（scd,c）,返回步骤返回步骤2。 ( ,)|, ijij v vvI vJ 1,6 图上标号法图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 1, 1,1 1, 1, 1, 1,3 1,6 图上标号法图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 1, 1,1 1, 1, 1, 1,3 1,6v5 v2 2 3 4 6 4 v3 v1 v

10、4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 图上标号法图上标号法: 1,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 1,6 图上标号法图上标号法: 1,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 3,5 图上标号法图上标号法: 3,5v5 v2

11、2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1,3 1, 图上标号法图上标号法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1,3 1, 图上标号法图上标号法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 1, 2,6 1, 1,3 1, 图上标号法图上标号法:

12、 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 1, 2,6 1, 1,3 1, 图上标号法图上标号法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 5,10 1,1 1, 2,6 5,12 1,3 5,9 图上标号法图上标号法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 5,10 1,1 1, 2,6 5,12 1

13、,3 5,9 图上标号法图上标号法: 22 例例1 求下图中求下图中v1到到v6的最短路的最短路 解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：各点的标号图如下： v2 3 5 2 7 5 3 1 5 12 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 12 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 2、节约里程算法基本原理、节约里程算法基本原理 o 基本原理是几何学中三角形一边之长必定小 于另外两边之和。 o 节约里程法核心思想是依次将运输问题中的

14、两个回路合并为一个回路，每次使合并后的 总运输距离减小的幅度最大，直到达到一辆 车的装载限制时，再进行下一辆车的优化。 优化过程分为并行方式和串行方式两种。 o 假如一家配送中心（DC）向两个用户A、B运 货，配送中心到两用户的最短距离分别是La 和Lb，A和B间的最短距离为Lab，A、B的货 物需求量分别是Qa和Qb，且（Qa+Qb）小于 运输装载量Q，如图所示，如果配送中心分别 送货，那么需要两个车次，总路程为：L1=2 （La+Lb）。 AB DC La Lb AB DC La Lb Lab 如果改用一辆车对两客户进行巡回送货，则只需一个车 次,行走的总路程为： L2=La+Lb+Lab

15、 有三角形的性质我们知道： Lab（La+Lb） 所以第二次的配送方案明显优于第一种，且行走总路程 节约： L=（La+Lb）Lab 如果配送中心的供货范围内还存在着：3,4,5，n个 用户，在运载车辆载重和体积都允许的情况下，可将它 们按着节约路程的大小依次连入巡回线路，直至满载为 止，余下的用户可用同样方法确定巡回路线，另外派车。 例题：例题：由配送中心由配送中心P P向向AIAI等等9 9个用户配送货物。个用户配送货物。 图中连线上的数字表示公路里程（图中连线上的数字表示公路里程（kmkm）。靠）。靠 近各用户括号内的数字，表示各用户对货物近各用户括号内的数字，表示各用户对货物 的需求量

16、（的需求量（t t）。配送中心备有）。配送中心备有2t2t和和4t4t载重量载重量 的汽车，且汽车一次巡回走行里程不能超过的汽车，且汽车一次巡回走行里程不能超过 35km35km，设送到时间均符合用户要求，求该配，设送到时间均符合用户要求，求该配 送中心的最优送货方案。送中心的最优送货方案。 A B C D E F G H I P (0.9) (1.2) (1.6) (1.1) (0.9) (0.9) (0.6) (1.7) (0.5) 4 4 4 5 5 5 5 5 6 6 6 3 7 7 7 8 9 10 10 11 12 14 o计算配送中心至各用户以及各用户之 间的最短距离，列表得最短

17、距离表： P A B C D E F G H I P A B C D E F G H I 11 10 9 6 7 10 10 8 7 5 10 14 18 21 21 13 6 5 9 15 20 20 18 11 4 10 19 19 17 16 6 15 16 14 13 9 17 15 14 14 18 17 12 17 7 由最短距离表，利用节约法计算出各用由最短距离表，利用节约法计算出各用 户之间的节约里程，编制节约里程表：户之间的节约里程，编制节约里程表： AB:LA+LBLAB=11+10-5=16 AC:LA+LCLAC=11+9-10=10 AD:LA+LDLAD=11+6-

18、14=3 AE:LA+LELAE=11+7-18=0 AF:LA+LFLAF=11+10-21=0 AG:LA+LGLAG=11+10-21=0 A B C D E F G H I A B C D E F G H I 16 10 3 0 0 0 6 12 14 7 2 0 0 0 6 11 6 0 0 0 0 7 1 0 0 0 8 0 0 0 6 0 0 6 0 8 节约里程表 根据节约里程表中节约里程多少的顺根据节约里程表中节约里程多少的顺 序，由大到小排列，编制节约里程顺序，由大到小排列，编制节约里程顺 序表，以便尽量使节约里程最多的点序表，以便尽量使节约里程最多的点 组合装车配送。组合

19、装车配送。 顺位 号 里程节约里 程 顺位 号 里程节约里 程 顺位 号 里程节约里 程 1A-B166H-I810F-G6 2B-C148B-D710G-H6 3A-I128D-E715A-D3 4C-D1110A-H616B-E2 5A-C1010B-I617D-F1 6E-F810C-E6 根据节约里程排序表和配车（车辆的载重和容积因素）、根据节约里程排序表和配车（车辆的载重和容积因素）、 车辆行驶里程等约束条件，渐进绘出配送路径：车辆行驶里程等约束条件，渐进绘出配送路径： A A B B C C D D E E F F G G H H I I P P (0.9)(0.9) (1.2)(

20、1.2) (1.6)(1.6) (1.1)(1.1) (0.9)(0.9) (0.9)(0.9) (0.6)(0.6) (1.7)(1.7) (0.5)(0.5) 4 4 7 5 5 5 5 8 8 6 6 6 6 6 6 9 9 1010 1010 1212 路径路径A 路径路径B 路径路径C o路径A：4t车，走行32km，载重量 3.7t； o路径B：4t车，走行31km，载重量 3.9t； o路径C：2t车，走行30km，载重量 1.8t。 总共走行里程93km，共节约里程 （16+14+12）+（8+7） +6=63km。 优缺点分析 优点： 节约法是一种简便、易行的方法，一方面体现

21、出优化节约法是一种简便、易行的方法，一方面体现出优化 运输过程，与一般方法相比缩短了运输路程；另一方面，运输过程，与一般方法相比缩短了运输路程；另一方面， 它也体现了物流配送网络的优势，实现了企业物流活动它也体现了物流配送网络的优势，实现了企业物流活动 的整合，而且思路简单清晰、便于执行。的整合，而且思路简单清晰、便于执行。 缺点： 第一，利用节约法选择配送路线过于强调节约路程，第一，利用节约法选择配送路线过于强调节约路程， 而没考虑行程中的时间因素，在许多情况下，时间更能而没考虑行程中的时间因素，在许多情况下，时间更能 决定物流配送的成本与服务质量。例如城市间配送时对决定物流配送的成本与服务

22、质量。例如城市间配送时对 高速公路的选择，城市内部上下班时间的道路拥挤，一高速公路的选择，城市内部上下班时间的道路拥挤，一 个巡回配送过程中的时间长短，直接影响配送人员的精个巡回配送过程中的时间长短，直接影响配送人员的精 神状态，而人员的精神状态又与交通事故和配送错误相神状态，而人员的精神状态又与交通事故和配送错误相 连等，所以时间对配送路线的选择有时更重要。连等，所以时间对配送路线的选择有时更重要。 第二，利用节约法选择配送路线不能对客户的需求进行第二，利用节约法选择配送路线不能对客户的需求进行 灵活多变的处理。由于现代的消费者的需求倾向于个性灵活多变的处理。由于现代的消费者的需求倾向于个性

23、 化，引起企业的生产、销售和配送也愈来愈倾向于小批化，引起企业的生产、销售和配送也愈来愈倾向于小批 量，多品种，多批次。而节约法更适合需求稳定或是需量，多品种，多批次。而节约法更适合需求稳定或是需 求的时间不紧迫，这显然不能满足现代多变得市场环境。求的时间不紧迫，这显然不能满足现代多变得市场环境。 最后值得一提的是，节约法计算的配送路线 并不是总路程最短。 原因是节约法一方面要 缩短总路程,另一方面又要充分利用车辆的运 输空间(载重 / 容积) ，减少配送车次，而 且只要在前一条预设路线上运行的配送车辆 的运输空间允许，就必须按着节约路程的大 小顺序进行选择而不考虑其它的预设路线， 在事实情况下选择的路线并不能“节约”路 程和有效利用运输空间，而且运输的车次也 不一