文档介绍：2016-11-61第三节配送线路的优化一、配送线路的优化方法㈠两点间直送式配送运输规划——一对一配送的最短路线问题供应商客户2016-11-62设某物流公司要把一批货物从下图的公路网络中的V1城运送到V6城。网络中各边旁的数字表示相应两城之间的公路里程(公里)。试问:汽车应走从V1到V6的什么路线才能使所行驶的里程最少?2016-11-63算法1:指定两点间最短路的Dijkstra标号算法?Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。?Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。2016-11-64?Dijkstra算法的基本过程是采用标号法。在操作过程中有两种标号:暂时性标号T(Temporary Label) 和永久性标号P(Permanent Label)。?给顶点Vi一个P标号P(Vi)时表示从指定点Vs到Vi的最短路的长度为P(Vi),且Vi的标号不再改变。?给顶点Vi一个T标号T(Vi)时表示从指定点Vs到Vi的估计最短路长的上界为T(Vi),是一个临时标号。2016-11-65?算法的每一步都把某一点或几个点的T标号改为P标号;当指定点Vt得到P标号时全部计算结束。?对于有N个顶点的网络,最多经过N-1步运算就可得到从指定点Vs到指定点Vt的最短路的长度。2016-11-66算法步骤?Step1:给Vs以标号P标号0,即P(Vs)=0,其他各顶点Vi均给T标号,即T(Vi)=∞。?Step2: 若Vi是刚得到P标号的顶点,则考虑与Vi相邻的有T标号的所有顶点Vj,把这些顶点Vj的T标号修改为:T(Vj)=min{T(Vj),P(Vi)+Wij}2016-11-67?Step3:比较所有具有T标号的顶点的标号,把最小者改为P标号,即?当存在两个或两个以上最小T标号时,可以同时把它们都改为P标号。当全部顶点均为P标号时,或当Vt得到P标号时,停止运算;否则用代替转回步骤2。)}V(T{min)V(Pjji?)V(Ti2016-11-68首先求出从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 2016-11-69?练习?求V1到V6的最短距离。2016-11-610?Dijkstra标号算法还可应用于有向网络。?例2 设有一个原油输送系统,油库为,码头为是三个中间阀门点。管道长度已知。原油由Vs经过中间阀门点流向码头。为了使原油尽快输送到码头,应该沿哪一条线路输送。