模块八配送路线规划作业课件.ppt
模块八 配送路线的规划作业,知识目标,配送路线规划的意义及原则,配送路线规划的目标,影响配送路线规划的因素,配送路线优化的方法,第一节 配送路线规划的意义及原则,近年来,由于小批量,多批次的及时配送方式的发展,运输费用正在逐年提升,许多企业的运费已经超越了库存费用. 选择有效的配送路线,已成为控制物流成本的主要措施. 那么如何选择有效的配送路线呢?,有效的配送路线，实际上是在保证商品准时到达客户指定点的前提下，尽可能的减少运输的车次和运输的总路程. 在这种思想的指导下，节约法已成为选择配送路线的主要方法,并受到国内外物流界的青睐.,通常认为，配送是近距离，小批量，品种比较复杂，按用户需要搭配品种与数量的服务体系。从配送中心把货物送到所需要的各个用户，有很多不同的路线选择方案。合理的选择配送路线，对企业和社会具有很重要的意义： 优化配送路线，可以提高配送效率，对配送车辆做到 物尽其用尽 可能的降低配送成本。 可以准时、快速地把货物送到客户的手中，能极大地提高 客户满意度。 有利于企业提高效益。 对社会而言，它可以节省运输车辆，缓解交通紧张状况，减少噪音、尾气排放等运输污染，为保护生态平衡、创造美好家园做出贡献。,进行配送路线优化时，必须有明确的目，遵循基本的原则。配送路线方案目标的选择可以从以下几个方面来考虑： 配送效益最高或配送成本最低 配送里程最短 配送服务水准最优 配送劳动的消耗最小,考虑因素,配送路线规划的目标,以效益最高为目标,以成本最低为目标,以路程最短为目标,以吨千米最小为目标,以准确性最高为目标,以运力最合理为目标,以劳动消耗最小为目标,影响配送路线规划的因素,道路交通网,配送中心位置,客户分布状况,车辆运行限制,车辆额定载重量,道路状况；如最大承载力,车车流辆量通的行变高化潮； 如 上 下 班,配送路线优化的方法,标号法 节约里程法,优化的方法,需求网络中两点间最短线路的方法，叫做标号法,当由一个配送中心向多个客户进行共同送货，在同一条线路上的所有客户的需求量总和不大于一辆车的额定载重时有这一辆车配装着所有客户需求的货物按照预先设计好的最佳路线一次讲货物送给到客户中。,10,1、双标号法,最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。一、求解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,1,6,图上标号法:,0,0,1, ,1, ,1,1,1, ,1, ,1, ,1,3,1,6,图上标号法:,0,0,1, ,1, ,1,1,1, ,1, ,1, ,1,3,1,6,0,0,1, ,4,11,1,1,1, ,1, ,1, ,1,3,图上标号法:,1,5,0,0,1, ,4,11,1,1,1, ,1, ,1, ,1,3,1,6,图上标号法:,1,5,0,0,1, ,4,11,1,1,1, ,1, ,1, ,1,3,3,5,图上标号法:,3,5,0,0,1, ,4,11,1,1,1, ,1, ,1,3,1, ,图上标号法:,3,5,0,0,1, ,4,11,1,1,1, ,1, ,1,3,1, ,图上标号法:,3,5,0,0,4,11,1,1,1, ,2,6,1, ,1,3,1,图上标号法:,3,5,0,0,4,11,1,1,1, ,2,6,1, ,1,3,1,图上标号法:,3,5,0,0,5,10,1,1,1, ,2,6,5,12,1,3,5,9,图上标号法:,3,5,0,0,5,10,1,1,1, ,2,6,5,12,1,3,5,9,图上标号法:,22,例1 求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：,2、节约里程算法基本原理,基本原理是几何学中三角形一边之长必定小于另外两边之和。节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。,假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且（Qa+Qb）小于运输装载量Q，如图所示，如果配送中心分别送货，那么需要两个车次，总路程为：L1=2（La+Lb）。,A,B,DC,La,Lb,A,B,DC,La,Lb,Lab,如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为： L2=La+Lb+Lab 有三角形的性质我们知道： Lab（La+Lb） 所以第二次的配送方案明显优于第一种，且行走总路程节约： L=（La+Lb）Lab 如果配送中心的供货范围内还存在着：3,4,5，n个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车。,例题：由配送中心P向AI等9个用户配送货物。图中连线上的数字表示公路里程（km）。靠近各用户括号内的数字，表示各用户对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回走行里程不能超过35km，设送到时间均符合用户要求，求该配送中心的最优送货方案。,计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离表：,由最短距离表，利用节约法计算出各用户之间的节约里程，编制节约里程表：AB:LA+LBLAB=11+10-5=16AC:LA+LCLAC=11+9-10=10AD: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：4t车，走行32km，载重量3.7t；路径B：4t车，走行31km，载重量3.9t；路径C：2t车，走行30km，载重量1.8t。 总共走行里程93km，共节约里程（16+14+12）+（8+7）+6=63km。,优缺点分析,优点： 节约法是一种简便、易行的方法，一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单清晰、便于执行。,缺点： 第一，利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。例如城市间配送时对高速公路的选择，城市内部上下班时间的道路拥挤，一个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相连等，所以时间对配送路线的选择有时更重要。 第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量，多品种，多批次。而节约法更适合需求稳定或是需求的时间不紧迫，这显然不能满足现代多变得市场环境。,最后值得一提的是，节约法计算的配送路线并不是总路程最短。 原因是节约法一方面要缩短总路程,另一方面又要充分利用车辆的运输空间(载重 / 容积) ，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空间允许，就必须按着节约路程的大小顺序进行选择而不考虑其它的预设路线，在事实情况下选择的路线并不能“节约”路程和有效利用运输空间，而且运输的车次也不一定减少，对比上例中两种方案就会发现这一问题。,节约法的改进建议,由以上的分析可知,节约法简便易行,同时也有一些弊端.是否可以通过改进使其成为一种最优的方法呢 ?在配送路线选择决策时,通常考虑较优的原则,而不是最优化原则.深入了解客户,加强与客户的信息交流。通过对客户需求的时间变化对其进行分类,以增加配送的灵活性。路线决策过程中实施多路线同步决策。节约法的实施过程,要综合考虑路程长短和时间因素。配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。,题目,例：有一配送中心P，其配送网络如图所示，A-D为各收货点，括号内的数字为各收货点的需求量（吨），两点间连线上的数字是距离（公里）。运输货车有最大为2吨和4吨，试确定配送路线。,P,A,B,C,D,8,7,9,10,5,5,4,(0.6),(0.7),(1.7),(0.8),解：1 计算配送中心与各收货点及各收货点相互之间的最短距离,2 计算各收货点间的节约里程数，并将其进行排序,3 按节约里程大小组合顺序组合，安排配送路线由表可以看出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,
