数学建模中的节约里程法.ppt

1、第三节 物流配送组织,第三节 物流配送组织,配送路线合理与否对配送速度、车辆的合理利用和配送费用都有直接影响,因此配送路线的优化问题是配送工作的主要问题之一。采用科学的合理的方法制定配送路线,是配送活动中非常重要的一项工作。,第三节 物流配送组织,直送式配送运输，是指个供地点别一个客户的专门送货。从物流优化的角度看，直送式客户的基本条件是其需求量接近于或大于可用车辆的额定载质量，需专门派一辆或多辆车一次或多次送货。因此直送情况下，货物的配送要求是多装快跑，选择最短配送线路，以节约时间、费用，提高配送效率。即直送问题的物流优化，主要是寻找物流网络中的最短线路问题。 位势法,a,b,c,d,e,4

2、,3,6,7,4,2,第三节 物流配送组织,分送式配送是指由一个供应点对多个客户的共同送货。其基本条件是所有客户的需求量总和不大于一辆车的额定载质量。送货时，由这一辆车装着所有客户的货物，沿着一条精心选择的最佳线路依次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了文辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。 节约里程法,基本原理,基本原理是几何学中三角形一边之长必定小于另外两边之和。 节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化

3、过程分为并行方式和串行方式两种。,假如一家配送中心（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 如果配

4、送中心的供货范围内还存在着：3,4,5，n个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车。,实例分析,设一配送中心向13个客户配送商品，配送中心及客户间的最短距离如表1所示，如果配送的车辆载重为200吨，那么利用节约法求解的配送路线的步骤如下： 第一步，计算配送中心到库户间的最短距离，画出距离表。因为本例已给出，所以可以直接进行第二步。,表1 配送中心到客户间的最短距离表,第二步，根据最短距离表，利用节约法计算出用户间的节约里程，并由大到小排列，编制节约里程顺序表，如表2所示。 L=（La+Lb

5、）Lab 12：L1+L2-L12=12+8-9=11 13：L1+L3-L13=12+17-8=21 14：L1+L4-L14=12+15-9=18 15：L1+L5-L15=12+15-17=10 16：L1+L6-L16=12+20-23=9 17：L1+L7-L17=12+17-22=7 18：L1+L8-L18=12+8-17=3 19：L1+L9-L19=12+6-18=0 110：L1+L10-L1、10=12+16-23=7 111：L1+L11-L1、12=12+21-28=5 112：L1+L12-L1、12=12+11-22=1 113：L1+L13-L1、13=12+1

6、5-27=0,23：L2+L3-L23=8+17-10=15 24：L2+L4-L24=8+15-8=15 25：L2+L5-L25=8+15-9=14 26：L2+L6-L26=8+20-15=13 27：L2+L7-L27=8+17-13=12 28：L2+L8-L28=8+8-9=7 29：L2+L9-L29=8+6-12=2 210：L2+L10-L2、10=8+16-14=10 211：L2+L11-L2、11=8+21-18=11 212：L2+L12-L2、12=8+11-14=5 213：L2+L13-L2、13=8+15-20=3 34：L3+L4-L34=17+15-4=2

7、8 35：L3+L5-L35=17+15-14=18 36：L3+L6-L36=17+20-20=17 ,表2 节约里程表,第三步，根据节约里程顺序表和配送中心的约束条件，绘制配送路线。其具体步骤如下：首先选择最节约里程的路段（611），然后是（67），由于配送路线必须包含DC，且每条循环路线上的客户需求量之和要小于200吨，在接下的选择中满足条件的只有路段（118），此时载重总量为193吨，因为在余下选择中没有满足条件的客户，所以，第一回合的配送路线为（DC76118DC）。按此方法类推，其余的配送路线分别是（DC134DC）、（DC5101213DC）、（DC29DC）。 总路程为：（17

8、+4+7+13+8）+（12+8+4+15）+(15+9+9+8+15)+(8+12+6)=170 原路程为：2（12+8+17+15+15+20+17+8+6+16+21+11+15） =362 总共节约里程为：362170=192 或（33+34+16）+（28+21）+（22+18+18）+2=192,例：由配送中心P向AI等9个用户配送货物。图中连线上的数字表示公路里程（km）。靠近各用户括号内的数字，表示各用户对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回走行里程不能超过35km，设送到时间均符合用户要求，求该配送中心的最优送货方案。,计算配送中心至各用户以

9、及各用户之间的最短距离，列表得最短距离表：,由最短距离表，利用节约法计算出各用户之间的节约里程，编制节约里程表： AB:LA+LBLAB=11+10-5=16 AC:LA+LCLAC=11+9-10=10 AD:LA+LDLAD=11+6-14=3 AE:LA+LELAE=11+7-18=0 AF:LA+LFLAF=11+10-21=0 AG:LA+LGLAG=11+10-21=0 ,节约里程表,根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约里程顺序表，以便尽量使节约里程最多的点组合装车配送。,根据节约里程排序表和配车（车辆的载重和容积因素）、车辆行驶里程等约束条件，渐进绘出配送路

10、径：,路径A：4t车，走行32km，载重量3.7t； 路径B：4t车，走行31km，载重量3.9t； 路径C：2t车，走行30km，载重量1.8t。 总共走行里程93km，共节约里程（16+14+12）+（8+7）+6=63km。,优缺点分析,优点： 节约法是一种简便、易行的方法，一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单清晰、便于执行。,缺点： 第一，利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。例如城市间配送时对高速公路的选择，

11、城市内部上下班时间的道路拥挤，一个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相连等，所以时间对配送路线的选择有时更重要。 第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量，多品种，多批次。而节约法更适合需求稳定或是需求的时间不紧迫，这显然不能满足现代多变得市场环境。,最后值得一提的是，节约法计算的配送路线并不是总路程最短。由上面的案例可知,如若采用配送路线(DC - 1 - 3 - 4 - DC) ， (DC - 2 - 5 - 6 - DC)，

12、(DC - 10 - 7 - 11 - DC) 和(DC - 8 - 12 - 13 - 9 -DC) ,总路程为165 km ,比采用节约法的计算结果少11 km. 原因是节约法一方面要缩短总路程,另一方面又要充分利用车辆的运输空间(载重 / 容积) ，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空间允许，就必须按着节约路程的大小顺序进行选择而不考虑其它的预设路线，在事实情况下选择的路线并不能“节约”路程和有效利用运输空间，而且运输的车次也不一定减少，对比上例中两种方案就会发现这一问题。,节约法的改进建议,由以上的分析可知,节约法简便易行,同时也有一些弊端.是否可以通过改进使

13、其成为一种最优的方法呢 ?在配送路线选择决策时,通常考虑较优的原则,而不是最优化原则. 深入了解客户,加强与客户的信息交流。 通过对客户需求的时间变化对其进行分类,以增加配送的灵活性。 路线决策过程中实施多路线同步决策。 节约法的实施过程,要综合考虑路程长短和时间因素。 配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。,题目,例：有一配送中心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 按节约里程大小组合