节约里程法-应用.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,节约运输里程法,节约里程的定义,A,B,P,A,B,P,运输方式由（一）变成（二），可节省的运输距离为（,2a+2b,）,-,（,a+b+c,）,=a+b-c 0,，,这一节省的运输距离称为“节约里程”,（一）,（二）,a,b,a,b,c,1,节约里程法,基本假定,配送的是同一种货物,各客户的坐标及需求量均为已知,配送中心有足够的运输能力,2,节约运输里程法,举例,实例：有一工厂,P,，,AJ,表示,P,附近的客户，（）内数字表示运输量（吨），路线上的数字表示道路的距离（公里）。假设工厂只拥有,2,吨车和,4,吨车两种，并且限制车辆一次运输的最远距离为,30,公里，请问怎样安排运输路线，使运输距离最小？,P,A,B,C,D,E,F,G,H,I,J,7,6,6,5,5,4,11,4,8,10,4,6,8,5,6,2,4,3,2,7,9,10,7,4,3,5,9,（,0.7),（,1.5),（,0.8),（,0.4),（,1.4),（,1.5),（,0.6),（,0.8),（,0.5),（,0.6),3,第一步：作出最短距离矩阵,P,A,B,C,D,E,F,G,H,I,J,P,10,9,7,8,8,8,3,4,10,7,A,4,9,14,18,18,13,14,11,4,B,5,10,14,17,12,13,15,8,C,5,9,15,10,11,17,13,D,6,13,11,12,18,15,E,7,10,12,18,15,F,6,8,17,15,G,2,11,10,H,9,11,I,8,J,4,第二步：作出节约里程项目,A,B,C,D,E,F,G,H,I,J,A,15,8,4,0,0,0,0,9,13,B,11,7,3,0,0,0,4,8,C,10,6,0,0,0,0,1,D,10,3,0,0,0,0,E,9,1,0,0,0,F,5,4,1,0,G,5,2,0,H,5,0,I,9,J,5,第三步：节约里程项目的分类,顺位,连接线,节约里程,顺位,连接线,节约里程,1,AB,15,13,FG,5,2,AJ,13,13,GH,5,3,BC,11,13,HI,5,4,CD,10,16,AD,4,4,DE,10,16,BI,4,6,AI,9,16,FH,4,6,EF,9,19,BE,3,6,IJ,9,19,DF,3,9,AC,8,21,GI,2,9,BJ,8,22,CJ,1,11,BD,7,22,EG,1,12,CE,6,22,FL,1,6,节约运输里程法应用,P,A,B,C,D,E,F,G,H,I,J,10,4,8,8,3,7,9,10,7,8,初解：,线路数：,10,条,总运输距离：,148KM,车辆台数：,2,吨车,10,台,(0.7),(1.5),(0.8),(0.4),(1.4),(1.5),(0.6),(0.8),(0.5),(0.6),7,节约运输里程法应用,二次解：,按节约里程的大小，连接,AB,，,AJ,，,BC,线路数：,7,条,总运输距离：,109KM,车辆台数：,2,吨车,6,台，,4,吨车,1,台,(0.5),线路,A,：,装载量,3.6,运输距离,27KM,P,A,B,C,D,E,F,G,H,I,J,10,4,8,8,3,7,5,4,7,8,(0.7),(1.5),(0.8),(0.4),(1.4),(1.5),(0.6),(0.8),(0.6),4,8,节约运输里程法应用,(1.4),P,A,B,C,D,E,F,G,H,I,J,10,4,8,8,3,7,5,4,7,8,3,次解：,按节约里程的大小，连接,CD,和,DE,，,但因为限制，不能连接,CD,，,所以只能连接,D-E,线路数：,6,条,总运输距离：,99KM,车辆台数：,2,吨车,5,台，,4,吨车,1,台,(0.7),(1.5),(0.8),(0.4),(1.5),(0.6),(0.8),(0.5),(0.6),4,线路,A,：,装载量,3.6,运输距离,27KM,9,节约运输里程法应用,P,A,B,C,D,E,F,G,H,I,J,10,4,8,3,7,5,4,7,8,4,次解,：按节约里程的大小，连接,AI,和,EF,，,但因为,A,已组合在完成的线路,A,中，不能连接,AI,，,所以只能连接,EF,线路数：,5,条,总运输距离：,90KM,车辆台数：,2,吨车,3,台，,4,吨车,2,台,(0.7),(1.5),(0.8),(0.4),(1.4),(1.5),(0.6),(0.8),(0.5),(0.6),4,线路,A,：,装载量,3.6,运输距离,27KM,10,节约运输里程法应用,5,次解：,按节约里程的大小，连接,IJ,、,AC,、,BJ,、,BD,、,CE,。,但由于同一组中总有一头或两头包含在已完成线路,A,中，不能再作出新的线路。,所以考虑下一组,FG,组合到线路,B,组,线路数：,4,条,总运输距离：,85KM,车辆台数：,2,吨车,2,台，,4,吨车,2,台,P,A,B,C,D,E,F,G,H,I,J,10,4,8,3,7,5,4,7,(0.7),(1.5),(0.8),(0.4),(1.4),(1.5),(0.6),(0.8),(0.5),(0.6),4,6,7,6,线路,A,：,装载量,3.6,运输距离,27KM,线路,B,：,装载量,3.9,运输距离,30KM,11,节约运输里程法应用,最终解：,按节约里程的大小，下面考虑,GH,，,HI,，由,GH,于受运输距离和载重量的限制，所以不能组合进线路,B,。,只能连接,HI,，,作出线路,C,线路数：,3,条,总运输距离：,80KM,车辆台数：,2,吨车,1,台，,4,吨车,2,台,P,A,B,C,D,E,F,G,H,I,J,10,4,8,3,7,5,4,7,(0.7),(1.5),(0.8),(0.4),(1.4),(1.5),(0.6),(0.8),(0.5),(0.6),4,6,7,6,线路,A,：,装载量,3.6,运输距离,27KM,线路,B,：,装载量,3.9,运输距离,30KM,9,线路,C,：,装载量,1.3,运输距离,23KM,12,节约里程法,-,步骤,第一步：计算最短距离,第二步：计算节约里程,第三步：按照节约里程排序,第四步：安排配送,13,