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

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

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

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

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

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

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

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

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

9、上P標(biāo)號P(v1)=0，表示從v1到v1的最短路徑為零；其他點(v2，v3，…，v7)標(biāo)上T標(biāo)號T(vj)＝+∞（j＝2，3，…，7）。,P 0,T +∞,T +∞,T +∞,T +∞,T +∞,T +∞,第1步：① v1是剛得到P標(biāo)號的點。因為(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T標(biāo)號，所以修改這3個點的T標(biāo)號數(shù)值為： 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標(biāo)號中，T(v2)＝2最小，于是令P(v2)＝2。,T 2,T 5,T 3,P 2,第2步：① v2是剛得到

11、P標(biāo)號的點。因為(v2，v3)，(v2，v6)∈E，而且v3, v6是T標(biāo)號，故修改v3和v6的T標(biāo)號為： 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標(biāo)號中，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標(biāo)號的點。因為(v4，v5)∈E，而且v5是T標(biāo)號，故修改v5的T標(biāo)號為 T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8,② 在所有的T標(biāo)號中，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標(biāo)號的點。因為(v3，v5)，(v3，v6)∈E，而且v5和v

13、6為T標(biāo)號，故修改v5和v6的T標(biāo)號為： 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標(biāo)號中，T(v5)＝7最小，故令P(v5)＝7。,T 7,T 9,P 7,第5步：① v5是剛得到P標(biāo)號的點。因為(v5，v6)，(v5 ，v7

14、)∈E，而且v6和v7都是T標(biāo)號，故修改它們的T標(biāo)號為： 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標(biāo)號中，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標(biāo)號的點。

15、因為(v6，v7)∈E，而且v7為T標(biāo)號，故修改它的T標(biāo)號為 T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13② 目前只有v7是T標(biāo)號，故令：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。,？,標(biāo)號法另一種解答表現(xiàn)形式：,(注：黃色表示頂點標(biāo)號順序；綠色

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

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

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

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

20、服務(wù)距離。顯然，它們分別是矩陣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都是中心點。也就是說，消防站設(shè)在v1, v3, v5中任何一個頂點上都是可行的。,中位點選址問題,中位點選址問題的質(zhì)量判據(jù)： 所謂中位點選址，即從地

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

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