配送运输管理最短路径算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三节 配送线路的优化,一、,配送线路的优化方法,两点间直送式配送运输规划,一对一配送的最短路线问题,供应商,客户,9/22/2024,1,设某物流公司要把一批货物从下图的公路网络中的V1城运送到V6城。网络中各边旁的数字表示相应两城之间的公路里程（公里）。试问:汽车应走从,V1,到,V6,的什么路线才能使所行驶的里程最少？,9/22/2024,2,算法1：指定两点间最短路的D,i,jkstra标号算法,Dijkstra,算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。,Dijkstra,算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。,Dijkstra,算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。,9/22/2024,3,Dijkstra,算法的基本过程是采用标号法。在操作过程中有两种标号：暂时性标号,T,（,Temporary Label),和永久性标号,P(Permanent Label),。,给顶点,Vi,一个,P,标号,P(Vi),时表示从指定点,Vs,到,Vi,的最短路的长度为,P(Vi),，且,Vi,的标号不再改变。,给顶点,Vi,一个,T,标号,T(Vi),时表示从指定点,Vs,到,Vi,的估计最短路长的上界为,T(Vi),，是一个临时标号。,9/22/2024,4,算法的每一步都把某一点或几个点的,T,标号改为,P,标号,;,当指定点,Vt,得到,P,标号时全部计算结束。,对于有,N,个顶点的网络，最多经过,N-1,步运算就可得到从指定点,Vs,到指定点,Vt,的最短路的长度。,9/22/2024,5,算法步骤,Step1:,给,Vs,以标号,P,标号,0,，即,P(Vs)=0,其他各顶点,Vi,均给,T,标号，即,T(Vi)=,。,Step2:,若,Vi,是刚得到,P,标号的顶点，则考虑与,Vi,相邻的有,T,标号的所有顶点,Vj,把这些顶点,Vj,的,T,标号修改为：,T(Vj)=minT(Vj),P(Vi)+W,ij,9/22/2024,6,Step3:,比较所有具有,T,标号的顶点的标号，把最小者 改为,P,标号，即,当存在两个或两个以上最小,T,标号时，可以同时把它们都改为,P,标号。当全部顶点均为,P,标号时，或当,Vt,得到,P,标号时，停止运算；否则用代替转回步骤,2,。,9/22/2024,7,首先求出从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,9/22/2024,8,练习,求,V1,到,V6,的最短距离。,9/22/2024,9,Dijkstra,标号算法还可应用于有向网络。,例,2,设有一个原油输送系统，油库为，码头为是三个中间阀门点。管道长度已知。原油由,Vs,经过中间阀门点流向码头。为了使原油尽快输送到码头，应该沿哪一条线路输送。,9/22/2024,10,一对多配送的最短路线问题分送式配送运输,第三节 配送线路的优化,一、,配送线路的优化方法,9/22/2024,11,分送式配送运输,分送式配送是指由,一个供应点,对,多个客户,的共同送货。,基本条件：同一条线路上所有客户的需求量总和,不大于,一辆车的额定载重量，送货时，由这一辆车装着所有客户的货物，沿着一条精心挑选的最佳路线依次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。,9/22/2024,12,节约里程法,Clarke,和,Wright,于,1964,年提出该算法。,节省里程法（,Savings Algorithm,）,VSP,网络法（,Vehicle Scheduling Program,）,节约里程法的目标：根据配送中心的运输能力及其到客户之间的距离和各客户之间的相对距离来制订使总的配送车辆吨千米数达到或接近最小的配送方案。,9/22/2024,13,节约里程法的基本思想,P,A,B,b,a,P,A,B,b,a,D1=2(a+b) D2=a+b+c,D1-D2=2(a+b)-(a+b+c)=a+b-c0,第二种方案比第一种方案要节约a+b-c的里程数,c,9/22/2024,14,节约里程法基本思想：,如果一个配送中心分别向,N,个客户配送货物，在汽车载重能力允许的前提下，每辆汽车在配送路线上经过的客户个数越多，里程节约量越大，配送线路越合理。,9/22/2024,15,节约法的基本规定,：,1.,配送的是同种或相似的货物；,2.,各客户的位置及需求量已知；,3.,配送中心有足够的运输能力。,且满足：,1.,满足所有用户的要货需求；,2.,每辆车不能超载；,3.,每车每天总运行时间或行驶里程不能超出规定上限；,4.,方案能满足所有用户的到货时间要求。,9/22/2024,16,步骤1：计算网络结点之间的最短距离。,步骤2：计算各客户之间的可节约的运行距离：,a+b-c,其中a 为P点至各点距,离；,b为P点至各点距,离；,c为两点间最小距,离。,步骤3：对节约里程,数,按大小顺序进行排列。,步骤4：组成配送路线图,9/22/2024,17,节约里程法算例,配送中心,P0,向,P1,P2,P3,P4,P5,共,5,个客户配送货物，该配送中心和,5,家客户之间的运输距离以及,5,家客户需要送货的数量已知（单位：运输距离：,km,；送货数量：吨）。已知该配送中心备有额定载重量为,2,吨的卡车,3,辆，额定载重量,4,吨的卡车,2,辆。,1.,试利用节约里程法制定最优配送方案。,2.,设卡车行驶速度平均为,40km/,小时,试比较优化后的方案比单独向各用户分送可节约多少时间？,9/22/2024,18,该算例配送路线网络图,10,P,1,P,0,P,2,P,4,（1.4）,P,3,P,5,（2.4）,（0.9）,（1.7）,（1.5）,12,7,5,12,4,13,6,8,12,16,8,9/22/2024,19,节约里程法基本步骤,Step1:,作运输里程表，列出配送中心到用户及用户间的最短距离；,Step2:,由运输里程表、按节约里程公式，求得相应的节约里程数，如上表（）内,；,Step3:,将节约里程进行分类，按从大到小顺序排列；,Step4:,按“节约里程”的大小和客户的收货数量或重量，在车辆载重允许的情况下组成配送巡回路线图。,9/22/2024,20,配送中心与用户及用户间最短距离,9/22/2024,21,节约里程数,9/22/2024,22,节约里程数排序,9/22/2024,23,初始方案,P,3,P,4,7,（1.4）,P,0,P,2,P,5,P,1,（2.4）,（0.9）,（1.7）,（1.5）,10,6,8,8,9/22/2024,24,二次解,8,（1.4）,P,0,P,2,P,3,P,4,P,5,P,1,（2.4）,（0.9）,（1.7）,（1.5）,10,7,5,4,8,16,9/22/2024,25,节约里程数为,20km,故节约时间为,20km/40km/,小时,=0.5,小时,9/22/2024,26,练习：,求节约里程的线路设计，假定该公司有,2T,和,4T,车，每次运行距离不超过,60KM,。,14,9/22/2024,27,9/22/2024,28,9/22/2024,29,c,a,b,9/22/2024,30,(a+b-c=5+8-4=9),(5+7-7=5)(8+7-3=12),9/22/2024,31,9/22/2024,32,(5+8+7+5+4+12+9+12+6)*2=136,9/22/2024,33,9/22/2024,34,9/22/2024,35,9/22/2024,36,9/22/2024,37,