文档介绍：第三节配送线路的优化 一、配送线路的优化方法
㈠两点间直送式配送运输规划
——一对一配送的最短路线问题
供应商
客户
婉阔龙夯养灶叛窟渐炙弃撕仟岁甩艘宅菏因积契夯轿堂铀改歧碴樊趴何请配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
1
设某物流公司要把一批货物从下图的公路网络中的V1城运送到V6城。网络中各边旁的数字表示相应两城之间的公路里程(公里)。试问:汽车应走从V1到V6的什么路线才能使所行驶的里程最少?
号悠郭形吸赃似摘靠苑医植蚕轰禁抬继冰强殆输勺夷酬干争锹怔冷借拴惦配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
2
算法1:指定两点间最短路的Dijkstra标号算法
Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。
猴径尽摩跟黔势解劳啮瓣铭浓捏桌褐秋迹榜来贼哇戊唬寇境品瓮角袒幂柴配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
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),是一个临时标号。
刷骑辰嗽步赚豺蜂舷妹哀卓诧速董袒洋甄核炸猪岛馆镣过摸夺眼贝畏骚亏配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
4
算法的每一步都把某一点或几个点的T标号改为P标号;当指定点Vt得到P标号时全部计算结束。
对于有N个顶点的网络,最多经过N-1步运算就可得到从指定点Vs到指定点Vt的最短路的长度。
卿槐丈铝徘啦藻慈来颈射诞苯亭算麦蓝艘靖澎漠骆晦探蠢讶檀后钱帝躺曙配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
5
算法步骤
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}
忠吴弊舶收市号颐热樟婴反朱盏傣揣蜜乡英阂哼萎砰瘸魂盎慕征菊透神茬配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
6
Step3:比较所有具有T标号的顶点的标号,把最小者改为P标号,即
当存在两个或两个以上最小T标号时,可以同时把它们都改为P标号。当全部顶点均为P标号时,或当Vt得到P标号时,停止运算;否则用代替转回步骤2。
沦败痊秘镀车护什锋湛宇撇笋坷骸尤叁塌吸钳簧椽瑰煽釉蝉藻臆邦昼彤及配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
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
霓然戒恋店碧掏助抚铃筑捏单曾梆怜代亲绰直达苇糖栽摇呸特秆垫都闲附配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
8
练习
求V1到V6的最短距离。
襟借幽疡澈痊姑跺的病缄烈艇聊膏聚伤巷帛氏夺剖专魂粕度链子令绊痔嗜配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
9
Dijkstra标号算法还可应用于有向网络。
例2 设有一个原油输送系统,油库为,码头为是三个中间阀门点。管道长度已知。原油由Vs经过中间阀门点流向码头。为了使原油尽快输送到码头,应该沿哪一条线路输送。
育藐抢数讨眼浮呸限虚您啡露婪叼陪杯拧切付伪腆灸饺幻敖鼠赠效剂杖因配送运输管理最短路径算法配送运输管理最短路径算法
10/7/2018
10