計量地理學-10.2-最短路徑與選址問題

1、最短路徑與選址問題,P＝{vi1，ei1，vi2，ei2，…，eik-1，vik},路徑是頂點與邊的交替序列集合,在地理網絡中，給定一個起始點，指定一個終止點，在從起點至終點的所有路徑中，找到一條最短的路徑，是為最短路徑分析。,含義？,距離最短？時間最少？經濟成本最節(jié)?。?指定障礙點？指定中途點？……,最優(yōu)路徑分析,“純距離”意義上的最短路徑,最短路徑的含義,“經濟距離”意義上的最短路徑,需要運送一批物資從一個城市到另一個城市，選擇什

2、么樣的運輸路線距離最短？,某公司在10大港口C1，C2，…，C10設有貨棧，從Ci到Cj之間的直接航運價格，是由市場動態(tài)決定的。如果兩個港口之間無直接通航路線，則通過第三個港口轉運。那么，各個港口之間最廉價的貨運線路是什么？,“時間”意義上的最短路徑,某家經營公司有一批貨物急需從一個城市運往另一個城市，那么，在由公路、鐵路、河流航運、航空運輸等4種運輸方式和各個運輸線路所構成的交通網絡中，究竟選擇怎樣的運輸路線最節(jié)省時間？,賦權圖上的最

3、短路徑問題,,空間距離,經濟成本,時間成本,權重值,連接邊,地理網絡賦權圖,最短路徑分析,找出網絡中不經過障礙點且權值總和最小的路徑,找出網絡中權值總和最小的路徑,指定障礙點,找出網絡中經過中途點且權值總和最小的路徑,指定中途點,最短路徑分析算法,1959年E.W.Dijkstar 提出的標號法是最短路徑問題最基礎也是應用最廣泛的分析求解方法 。,標號法優(yōu)點 ①不僅可以求出起點到終點的最短路徑及其長度； ②而且可以求

4、出起點到其他任何一個頂點的最短路徑及其長度； ③同時適用于求解有向圖或無向圖上的最短路徑問題。,標號法的基本思想 設G是一個賦權有向圖，即對于圖中的每一條邊，都賦予了一個權值。在圖G中指定兩個頂點，確定為起點和終點，不妨設v1為起點，vk為終點。,找到從v1至vk的權值最小路徑,最短路徑分析算法,每次有一個頂點的標號由T至P，那么最多經過k-1步，就可以求得到從起點v1到每一個頂點的最短路徑及其長度。,首先從起點

5、v1開始，給每個頂點標一個符號與數字，稱為標號。這些標號又進一步區(qū)分為T標號和P標號兩種類型。 其中，每一個頂點的T標號為臨時標號，其數字表示從起點v1到該點的最短路徑長度的上界(最大值)；每一個頂點的P標號為固定標號 (當前頂點已找到最短路徑)，其數字表示從v1到該點的最短路長度。,標號法的基本思想,在最短路徑計算過程中，對于已經得到P標號的頂點，不再改變其標號；對于凡是沒有標上P標號的頂點，先給它一個T標號；算法的每一

6、步就是把頂點的T標號逐步修改，將其變?yōu)镻標號。（即依次修改頂點由臨時標號T轉換為固定標號P）,如何確定頂點由T至P？,最短路徑分析算法,標號法具體計算步驟：,初始化，先給v1標上P標號P(v1)＝ 0，其余各點標上T標號T(vj)＝+∞ (j≠1)。,① 如果剛剛得到P標號的點是vi，那么，找出下列集合包括的所有這樣的頂點：,至v1的最短路徑已找到,② 若圖G中沒有T標號，則停止。否則，把擁有最小T值的頂點 的T標號修改為P標號

7、，然后再轉入①。 其中， 滿足,從vi出發(fā)可達的其它臨時T標號的頂點,并且將其T標號修改為： min[T(vj), P(vi)+wij],,,vj原最短路徑長度與通過vi再至vj的路徑長度進行比較取較小值,從剛修改完標號數值的所有頂點vj中，將其數值最小的vj0的T標號修改為P標號,初始化：P(v1)＝ 0, T(vj)＝+∞,對于最近得到P標號的點vi ：找出它直達的所有其它T標

8、號的頂點,更新各頂點vj的權值：min[T(vj), P(vi)+wij],更新最小權值的T標號頂點為P標號,當前網絡圖中已沒有T標號頂點,停止，最短路徑已找到,YES,NO,Dijkstar標號法算法流程：,例1：在下凸所示的賦權有向圖中，每一個頂點vi（i=1，2，…，n）代表一個城鎮(zhèn)；每一條邊代表相應兩個城鎮(zhèn)之間的交通線，其長度用邊旁的數字表示。試求城鎮(zhèn)v1到v7之間的最短路徑。,賦權有向交通阿網絡圖,解：初始化：首先給v1標

9、上P標號P(v1)=0，表示從v1到v1的最短路徑為零；其他點(v2，v3，…，v7)標上T標號T(vj)＝+∞（j＝2，3，…，7）。,P 0,T +∞,T +∞,T +∞,T +∞,T +∞,T +∞,第1步：① v1是剛得到P標號的點。因為(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T標號，所以修改這3個點的T標號數值為： T(v2)＝min[

10、T(v2)，P(v1)+w12]＝min[ +∞，0+2]＝2 T(v3)＝min[T(v3)，P(v1)+w13 ]＝ min[ +∞，0+5]＝5 T(v4)＝min[T(v4)，P(v1)+w14 ]＝ min[ +∞，0+3]＝3,P 0,T +∞,T +∞,T +∞,② 在所有T標號中，T(v2)＝2最小，于是令P(v2)＝2。,T 2,T 5,T 3,P 2,第2步：① v2是剛得到

11、P標號的點。因為(v2，v3)，(v2，v6)∈E，而且v3, v6是T標號，故修改v3和v6的T標號為： T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4 T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9,② 在所有的T標號中，T(v4)＝3最小，于是令P(v4)＝3。,P 0,T +∞,T +∞,T +∞,T 5,T 3,P 2,T 9,T

12、4,P 3,第3步：① v4是剛得到P標號的點。因為(v4，v5)∈E，而且v5是T標號，故修改v5的T標號為 T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8,② 在所有的T標號中，T(v3)＝4最小，故令P(v3)＝4。,P 0,T +∞,T +∞,P 2,T 9,T 4,P 3,T 8,P 4,第4步：① v3是剛得到P標號的點。因為(v3，v5)，(v3，v6)∈E，而且v5和v

13、6為T標號，故修改v5和v6的T標號為： T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7 T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9,P 0,T +∞,P 2,T 9,P 3,T 8,P 4,② 在所有的T標號中，T(v5)＝7最小，故令P(v5)＝7。,T 7,T 9,P 7,第5步：① v5是剛得到P標號的點。因為(v5，v6)，(v5 ，v7

14、)∈E，而且v6和v7都是T標號，故修改它們的T標號為： T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]= 8 T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14,② 在所有T標號中，T(v6)＝8最小，于是令：P(v6)＝8。,P 0,T +∞,P 2,P 3,P 4,T 9,P 7,T 8,T 14,P 8,第6步：① v6是剛得到P標號的點。

15、因為(v6，v7)∈E，而且v7為T標號，故修改它的T標號為 T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13② 目前只有v7是T標號，故令：P(v7)＝13。,P 0,P 2,P 3,P 4,P 7,T 14,P 8,T 13,P 13,從v1到v7之間的最短路徑為(v1，v2，v3，v5，v6，v7)，最短路徑長度為13。,？,標號法另一種解答表現形式：,(注：黃色表示頂點標號順序；綠色

16、表示頂點權值更新內容),標號順序：,V1,V2,V4,V3,V5,V6,V7,優(yōu)先連接順序：,V2,V3,V5,V5,V6,V7,選址問題,對于許多地理問題，當它們被抽象為圖論意義下的網絡圖時，問題的核心就變成了網絡圖上的優(yōu)化計算問題。其中，最為常見的是關于路徑和頂點的優(yōu)選計算問題。 在路徑的優(yōu)選計算問題中，最常見的是最短路徑分析；而在頂點的優(yōu)選計算問題中，最為常見的是中心點和中位點選址問題。,選址問題的數學模型取決于兩個

17、方面的條件 ：可供選址的范圍、條件；怎樣判定選址的質量。 本節(jié)討論僅限于選址的范圍是一個地理網絡，而且選址位置位于網絡圖的某一個或幾個頂點上。 對這樣的選址問題，根據其選址的質量判據，可以將其歸納為求網絡圖的中心點與中位點兩類問題。,中心點選址問題,中心點選址問題的質量判據： 中心點選址問題適宜于醫(yī)院、消防站點等一類服務設施的布局，所謂中心點選址，即從地理網絡圖中找到最佳選址位置使得所在頂點的最

18、大服務距離為最小。,中心點選址問題的數學描述 設G＝(V, E)是一個無向簡單連通賦權圖，連接兩個頂點的邊的權值代表它們之間的距離，對于某個頂點vi，它與其它各頂點之間的最短路徑長度為di1，di2，…，din。這些最短路徑長度距離中的最大數稱為頂點vi的最大服務距離，記為e(vi)。,那么，中心點選址問題，就是求網絡圖G的中心點vi0，使得其滿足：,例：假設某縣下屬的6個鄉(xiāng)鎮(zhèn)及其之間公路聯(lián)系如下圖所示。每一頂點代表一個鄉(xiāng)

19、鎮(zhèn)；每一條邊代表連接兩個鄉(xiāng)鎮(zhèn)之間的公路，每一條邊旁的數字代表該條公路的長度?，F在要設立一個消防站，為全縣的6個鄉(xiāng)鎮(zhèn)服務。試問該消防站應該設在哪一個鄉(xiāng)鎮(zhèn)（頂點）？,為何消防站的選址要傾向于中心點，即最大服務距離最??？,解：第1步：用標號法求出每一個頂點vi至其他各個頂點vj的最短路徑長度dij (I, j ＝ 1,2,…,6)，并將它們寫成如下的最短路徑長度距離矩陣:,最短路徑長度距離矩陣是上下三角對稱矩陣？,第2步：求每一個頂點的最大

20、服務距離。顯然，它們分別是矩陣D中各行或各列的最大值，即：,e(v1)＝6，e(v2)＝7，e(v3)＝6，e(v4)＝7，e(v5)＝6，e(v6)＝7,,,,,,,Max,第3步：判定。因為e(v1)＝e(v3)＝e(v5)＝min{e(vi)}＝6，所以v1, v3, v5都是中心點。也就是說，消防站設在v1, v3, v5中任何一個頂點上都是可行的。,中位點選址問題,中位點選址問題的質量判據： 所謂中位點選址，即從地

21、理網絡圖中找到最佳選址位置使得所在頂點到其他各個頂點的最短路徑距離的總和達到最小（或者以各個頂點的載荷加權求和）。,中位點選址問題的數學描述 設G＝(V, E)是一個無向簡單連通賦權圖，連接兩個頂點的邊的權值代表它們之間的距離，對于某個頂點vi，有一個正的負荷a(vi)，它與其它各頂點之間的最短路徑長度為di1，di2，…，din。 那么，中位點選址問題，就是求圖G的中位點vi0 ，使得：,例3：某縣下屬7個鄉(xiāng)

22、鎮(zhèn)，各鄉(xiāng)鎮(zhèn)所擁有的人口數a(vi) (i=1, 2, …, 7)，以及各鄉(xiāng)鎮(zhèn)之間的距離wij (i, j=1,2,…,7)。如圖所示。現在需要設立一個中心郵局，為全縣所轄的7個鄉(xiāng)鎮(zhèn)共同服務。問該中心郵局應該設在哪一個鄉(xiāng)鎮(zhèn)（頂點）？,為何郵局的選址要傾向于中位點，即最短路徑長度加權總和最?。?解：第1步：用標號法求出每一個頂點vi至其他各個頂點vj的最短路徑長度dij(i, j ＝1,2,…,7)，并將其寫成如下最短路徑長度距離矩陣：,