配送路线优化(里程节约法)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,配送线路优化方法,（一）直送式配送运输,适用方法,最短路径法,适用条件：,1,、由配送中心向每一位客户开展专门送货；,2,、该客户的送货量一般必须满足配送车辆满载。,配送效果：,1.,配送车辆满载运输；,2.,配送运输路线距离最短。,标点法设计最短线路,一对一配送的最短路线问题,【,例,】,求,1-6,的,最短距,离。,供应商,客户,首先求出从,1,出发的一条最短路径（,1-2,：,4,），求次短路径（,2-5,：,2,），依次类推：（,5-6,：,8,），（,5-4-6,：,7,），（,5-4-3-6,：,6,），最短距离求得的最短路径是：,1-2-5-4-3-6,距离是：,4+2+6=12,（二）分送式配送运输,适用方法,节约里程法,适用条件：,1,、由配送中心向多位客户开展拼装送货；,2,、每位客户的送货量都不能满足配送车辆满载。,配送效果：,1.,配送车辆满载运输；,2.,配送运输路线距离最短。,一对多配送的最短路线问题,供应商,客户,节约里程法的意义,送货时，由一辆车装载所有客户的货物，沿着一条精心设计的最佳路线依次将货物送到各位客户手中，这样既保证按时按量将用户需要的货物及时送达，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。,1.,满足客户配送需要,2.,减少配送车辆使用,3.,缓解交通紧张压力,节约里程法,(Saving Algorithm),车辆调度程序法,(Vehicle Scheduling Program:VSP),又称节约算法，是指用来解决运输车辆数目不确定的问题的最有名的启发式算法。,核心思想,:,节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。,节约里程法,利用节约法制定出的配送方案除了使配送总吨公里数最小外，还应满足以下条件：,满足所有用户的需求,不使任何一辆车超载,每辆车每天的总运行时间或行驶里程不超过规定的上限；,用户到货时间要求。不得超过规定时间。,节约里程法,P,A,（客户）,B,（客户）,a,b,(,配送中心,),P,A,（客户）,B,（客户）,(,配送中心,),b,a,c,运行距离为：,2a+2b,运行距离为：,a+b+c,节约行程：,a+b,c,节约里程法,例题：已知配送中心,P,0,向,5,个用户,P,j,配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有,3,台,2t,卡车和,2,台,4t,两种车辆可供使用。利用节约里程法制定最优的配送方案。,(1.4),P,0,P,2,P,3,P,4,P,5,P,1,(2.4),(0.9),(1.7,）,(1.5),10,12,7,5,9,4,13,6,8,12,16,8,节约里程法,第,1,步：作运输里程表，列出配送中心到用户及用户间的最短距离。,需求量,P,0,P,1,1.5,8,P,1,P,2,1.7,8,12,P,2,P,3,0.9,6,13,4,P,3,P,4,1.4,7,15,9,5,P,4,P,5,2.4,10,16,18,16,12,P,5,节约里程法,第,2,步：按节约里程公式求得相应的节约里程数,需求量,P,0,1.5,8,P,1,1.7,8,12,P,2,4,0.9,6,13,4,P,3,1,10,1.4,7,15,9,5,P,4,0,6,8,2.4,10,16,18,16,12,P,5,2,0,0,5,节约里程法,第,3,步：将节约里程按从大到小顺序排列,序号,路线,节约里程,1,P,2,P,3,10,2,P,3,P,4,8,3,P,2,P,4,6,4,P,4,P,5,5,5,P,1,P,2,4,6,P,1,P,5,2,7,P,1,P,3,1,8,P,2,P,5,0,9,P,3,P,5,0,10,P,1,P,4,0,节约里程法,第,4,步：根据载重量约束与节约里程大小，顺序连接各客户结点,形成二个配送路线,.,P2P3,P3P4,P2P4,P4P5,P1P2,P1P5,P1P3,P2P5,P3P5,P1P4,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,6,8,8,4,5,节约里程法,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,8,8,4,5,配送线路,1,节约里程法,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,8,8,4,5,配送线路,1,配送线路,1,：,运量,=1.7+0.9+1.4=4t,运行距离,8,4,5,7,24km,用一辆,4t,车运送,节约距离,=18km,配送线路,2:,运量,=2.4+1.5=3.9t4t,运行距离,8,10,16,34km,用一辆,4t,车运送,节约距离,=2km,节约里程法,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,6,8,8,初始方案：配送线路,5,条，需要车,5,辆,配送距离,=392=78KM,节约里程法,初始方案：,配送线路,5,条，需要车,5,辆,配送距离：,392=78KM,优化后的方案：,2,条配送线路，,2,辆,4t,车,配送距离：,24,34,58km,练习,位于牡丹江市内的百家姓配送中心（,P,0,）向它旗下的,10,家连锁商店,p,i,(i=1,2,10),配送商品，其配送网络如下图所示。,图中括号内的数字表示每一家连锁店的需求量（,t,），线路上的数字表示两节点之间的距离（,km,）。配送中心现有,2t,和,4t,车辆可供使用，并且每辆车配送距离不得超过,30km,。,请为百家姓配送中心制定最优的配送方案。,第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心与客户及客户之间的最短距离，结果见表,11-11,。,第二步：计算节约里程,sij,结果见表,11-12,。,第三步：将节约,sij,进行分类，按从大到小的顺序排列，得表,11-13,第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图,（,1,）初始方案：对每一客户分别单独派车送货，结果如图,11-10,。,修正方案,4,