模块八配送路线规划作业课件.ppt

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

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

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

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

5、动消耗最小为目标以劳动消耗最小为目标 影响配送路线规划的因素影响配送路线规划的因素 道道路路交交通通网网配配送送中中心心位位置置客客户户分分布布状状况况车车辆辆运运行行限限制制车车辆辆额额定定载载重重量量道道路路状状况况；如如最最大大承承载载力力车车车车流辆流辆量通量通的行的行变高变高化潮化潮；如如 上上 下下 班班 配送路线优化的方法配送路线优化的方法 标号法标号法 节约里程法节约里程法优化的方法 需求网络中两点需求网络中两点间最短线路的方法，间最短线路的方法，叫做标号法叫做标号法当由一个配送中心向多个客户进行共当由一个配送中心向多个客户进行共同送货，在同一条线路上的所有客户同送货，在同一条

6、线路上的所有客户的需求量总和不大于一辆车的额定载的需求量总和不大于一辆车的额定载重时有这一辆车配装着所有客户需求重时有这一辆车配装着所有客户需求的货物按照预先设计好的最佳路线一的货物按照预先设计好的最佳路线一次讲货物送给到客户中。次讲货物送给到客户中。101 1、双标号法、双标号法o最短路问题：对一个赋权的有向图最短路问题：对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找到一找到一条从条从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从路被称之为从Vs到到Vt的最短路。这条路上所有弧的权数的总和被称为

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

8、如果vt 未标号，则可以断言不存在从未标号，则可以断言不存在从 vs到到vt的有的有向路。如果上述的弧的集合不是空集，则转下一步。向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 sij=li+cij。在所有的。在所有的 sij中，找中，找到其值为最小的弧。不妨设此弧为（到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双），则给此弧的终点以双标号（标号（scd,c）,返回步骤返回步骤2。(,)|,ijijv vvI vJ1,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v723

9、63v60,01,1,1,11,1,1,1,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1,1,11,1,1,1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,3图上标号法图上标号法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,31,6图上标号法图上标号法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,

10、1,1,33,5图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,2,61,1,31,图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,2,61,1,3

11、1,图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,9图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,9图上标号法图上标号法:22例例1 求下图中求下图中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v235275315

12、12 V1（0,s)v5 (8,4)v6(2,1)v3(3,3)v42、节约里程算法基本原理、节约里程算法基本原理o 基本原理是几何学中三角形一边之长必定小于另外两边之和。o 节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。o 假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且（Qa+Qb）小于运输装载量Q，如图所示，如果配送中心分别送货，那么需要两个

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

14、数字表示公路里程（图中连线上的数字表示公路里程（kmkm）。靠）。靠近各用户括号内的数字，表示各用户对货物近各用户括号内的数字，表示各用户对货物的需求量（的需求量（t t）。配送中心备有）。配送中心备有2t2t和和4t4t载重量载重量的汽车，且汽车一次巡回走行里程不能超过的汽车，且汽车一次巡回走行里程不能超过35km35km，设送到时间均符合用户要求，求该配，设送到时间均符合用户要求，求该配送中心的最优送货方案。送中心的最优送货方案。ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0.9)(0.9)(0.6)(1.7)(0.5)44455555666377789101011121

15、4o计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离表：P A B C D E F G H I PABCDEF GHI 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=16AC:LA+LCLAC=11+9-10=10

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

17、送。组合装车配送。顺位号里程节约里程顺位号里程节约里程顺位号里程节约里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E25A-C1010B-I617D-F16E-F810C-E6 根据节约里程排序表和配车（车辆的载重和容积因素）、根据节约里程排序表和配车（车辆的载重和容积因素）、车辆行驶里程等约束条件，渐进绘出配送路径：车辆行驶里程等约束条件，渐进绘出配送路径：A AB BC CD DE EF FG GH HI IP P(0.9)(0.9)(1.2)(1.2)(1.6)(1.6)(1.1)(1.1)(0.

18、9)(0.9)(0.9)(0.9)(0.6)(0.6)(1.7)(1.7)(0.5)(0.5)4 475 55 58 86 66 66 69 9101010101212路径路径A路径路径B路径路径Co路径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。优缺点分析优点：节约法是一种简便、易行的方法，一方面体现出优化节约法是一种简便、易行的方法，一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，运输过程，与一般方法

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

20、的时间长短，直接影响配送人员的精个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相神状态，而人员的精神状态又与交通事故和配送错误相连等，所以时间对配送路线的选择有时更重要。连等，所以时间对配送路线的选择有时更重要。第二，利用节约法选择配送路线不能对客户的需求进行第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代的消费者的需求倾向于个性灵活多变的处理。由于现代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批化，引起企业的生产、销售和配送也愈来愈倾向于小批量，多品种，多批次。而节约法更适合需求稳定或是需量，

21、多品种，多批次。而节约法更适合需求稳定或是需求的时间不紧迫，这显然不能满足现代多变得市场环境。求的时间不紧迫，这显然不能满足现代多变得市场环境。最后值得一提的是，节约法计算的配送路线并不是总路程最短。原因是节约法一方面要缩短总路程,另一方面又要充分利用车辆的运输空间(载重/容积)，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空间允许，就必须按着节约路程的大小顺序进行选择而不考虑其它的预设路线，在事实情况下选择的路线并不能“节约”路程和有效利用运输空间，而且运输的车次也不一定减少，对比上例中两种方案就会发现这一问题。节约法的改进建议节约法的改进建议 由以上的分析可知,节约法简便易

22、行,同时也有一些弊端.是否可以通过改进使其成为一种最优的方法呢?在配送路线选择决策时,通常考虑较优的原则,而不是最优化原则.o 深入了解客户,加强与客户的信息交流。o 通过对客户需求的时间变化对其进行分类,以增加配送的灵活性。o 路线决策过程中实施多路线同步决策。o 节约法的实施过程,要综合考虑路程长短和时间因素。o 配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。题目题目o 例：有一配送中心P，其配送网络如图所示，A-D为各收货点，括号内的数字为各收货点的需求量（吨），两点间连线上的数字是距离（公里）。运输货车有最大为2吨和4吨，试确定配送路线。PABCD879105

23、54(0.6)(0.7)(1.7)(0.8)o 解：1 计算配送中心与各收货点及各收货点相互之间的最短距离PABCDP10978A4914B510C5Do 2 计算各收货点间的节约里程数，并将其进行排序序号123456组合ABBCCDACBDAD节约里程151110874o 3 按节约里程大小组合顺序组合，安排配送路线按节约里程大小组合顺序组合，安排配送路线o 由表可以看出AB节约里程最大，已知A、B的配送货物量是：0.7+1.7=2.4吨，在货车载重限制内，可以入选，BC节约里程次之，C的配送货物数量是0.8吨，2.4+0.8=3.2吨，未超出货车载重量。CD再次之，D的配送量是0.6吨，3.2+0.6=3.8吨，可以拼装一辆4吨货车，因此配送线路一条，即PABCDP,全程为：10+4+5+5+8=32