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

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

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

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

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

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

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

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

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

9、上P標(biāo)號P(v1)=0，表示從v1到v1的最短路徑為零；其他點(diǎn)(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)號的點(diǎn)。因?yàn)?v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T標(biāo)號，所以修改這3個(gè)點(diǎn)的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)號的點(diǎn)。因?yàn)?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)號的點(diǎn)。因?yàn)?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)號的點(diǎn)。因?yàn)?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)號的點(diǎn)。因?yàn)?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)號的點(diǎn)。

15、因?yàn)?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)形式：,(注：黃色表示頂點(diǎn)標(biāo)號順序；綠色

16、表示頂點(diǎn)權(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ò)圖時(shí)，問題的核心就變成了網(wǎng)絡(luò)圖上的優(yōu)化計(jì)算問題。其中，最為常見的是關(guān)于路徑和頂點(diǎn)的優(yōu)選計(jì)算問題。 在路徑的優(yōu)選計(jì)算問題中，最常見的是最短路徑分析；而在頂點(diǎn)的優(yōu)選計(jì)算問題中，最為常見的是中心點(diǎn)和中位點(diǎn)選址問題。,選址問題的數(shù)學(xué)模型取決于兩個(gè)

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

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

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

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

21、理網(wǎng)絡(luò)圖中找到最佳選址位置使得所在頂點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑距離的總和達(dá)到最小（或者以各個(gè)頂點(diǎn)的載荷加權(quán)求和）。,中位點(diǎn)選址問題的數(shù)學(xué)描述 設(shè)G＝(V, E)是一個(gè)無向簡單連通賦權(quán)圖，連接兩個(gè)頂點(diǎn)的邊的權(quán)值代表它們之間的距離，對于某個(gè)頂點(diǎn)vi，有一個(gè)正的負(fù)荷a(vi)，它與其它各頂點(diǎn)之間的最短路徑長度為di1，di2，…，din。 那么，中位點(diǎn)選址問題，就是求圖G的中位點(diǎn)vi0 ，使得：,例3：某縣下屬7個(gè)鄉(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è)立一個(gè)中心郵局，為全縣所轄的7個(gè)鄉(xiāng)鎮(zhèn)共同服務(wù)。問該中心郵局應(yīng)該設(shè)在哪一個(gè)鄉(xiāng)鎮(zhèn)（頂點(diǎn)）？,為何郵局的選址要傾向于中位點(diǎn)，即最短路徑長度加權(quán)總和最小？,解：第1步：用標(biāo)號法求出每一個(gè)頂點(diǎn)vi至其他各個(gè)頂點(diǎn)vj的最短路徑長度dij(i, j ＝1,2,…,7)，并將其寫成如下最短路徑長度距離矩陣：,