計量地理學(xué)：最短路徑及選址問題

1、 對于許多地理問題，當(dāng)它們被抽象為圖論意義下的網(wǎng)絡(luò)圖時，問題的核心就變成了網(wǎng)絡(luò)圖上的優(yōu)化計算問題。其中，最為常見的是關(guān)于路徑和頂點(diǎn)的優(yōu)選計算問題。 在路徑的優(yōu)選計算問題中，最常見的是最短路徑問題；而在頂點(diǎn)的優(yōu)選計算問題中，最為常見的是中心點(diǎn)和中位點(diǎn)選址問題。 “純距離純距離”意義上的最短路徑意義上的最短路徑 例如，需要運(yùn)送一批物資從一個城市到另一個城市，選擇什么樣的運(yùn)輸路線距離最短？ “經(jīng)濟(jì)距離經(jīng)濟(jì)距離”意義上的最短路徑意義上的最短路徑 例如，某公司在10大港口C1，C2，C10設(shè)有貨棧，從Ci到Cj之間的直接航運(yùn)價格，是由市場動態(tài)決定的。如果兩個港口之間無直接通航路線，則通過第三個港口轉(zhuǎn)運(yùn)。

2、那么，各個港口之間最廉價的貨運(yùn)線路是什么？一、最短路徑問題一、最短路徑問題（一）最短路徑的含義（一）最短路徑的含義 “時間時間”意義上的最短路徑意義上的最短路徑 例如，某家經(jīng)營公司有一批貨物急需從一個城市運(yùn)往另一個城市，那么，在由公路、鐵路、河流航運(yùn)、航空運(yùn)輸?shù)?種運(yùn)輸方式和各個運(yùn)輸線路所構(gòu)成的交通網(wǎng)絡(luò)中，究竟選擇怎樣的運(yùn)輸路線最節(jié)省時間？ 以上3類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。 不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。 權(quán)這種權(quán)值既可以代表“純距離 ”，又可以代表“經(jīng)濟(jì)距離 ”，也可以代表“時間距離 ”。 （二）（二）最短路徑的算法最短路徑的算法 標(biāo)號法標(biāo)號

3、法 1959年E.W.Dijkstar 提出的標(biāo)號法是最短路徑問題最好的求解方法 。 標(biāo)號法優(yōu)點(diǎn)標(biāo)號法優(yōu)點(diǎn) 不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長度，而且可以求出起點(diǎn)到其他任何一個頂點(diǎn)的最短路徑及其長度；同時適用于求解有向圖或無向圖上的最短路徑問題。.n標(biāo)號法的基本思想標(biāo)號法的基本思想 設(shè)G是一個賦權(quán)有向圖，即對于圖中的每一條邊，都賦予了一個權(quán)值。在圖G中指定兩個頂點(diǎn)，確定為起點(diǎn)和終點(diǎn)，不妨設(shè)v1為起點(diǎn)，vk為終點(diǎn)。 首先從v1開始，給每一個頂點(diǎn)標(biāo)一個數(shù)，稱為標(biāo) 號。這些標(biāo)號，又進(jìn)一步區(qū)分為T標(biāo)號和P標(biāo)號兩種類型。其中，每一個頂點(diǎn)的T標(biāo)號表示從起點(diǎn)v1到該點(diǎn)的最短路徑長度的上界，這種標(biāo)號為臨時

4、標(biāo)號；P標(biāo)號表示從v1到該點(diǎn)的最短路長度，這種標(biāo)號為固定標(biāo)號。 在最短路徑計算過程中，對于已經(jīng)得到P標(biāo)號的頂點(diǎn)，不再改變其標(biāo)號；對于凡是沒有標(biāo)上P標(biāo)號的頂點(diǎn)，先給它一個T標(biāo)號；算法的每一步就是把頂點(diǎn)的T標(biāo)號逐步修改，將其變?yōu)镻標(biāo)號。 那么，最多經(jīng)過k-1步，就可以求得到從起點(diǎn)v1到每一個頂點(diǎn)的最短路徑及其長度。n標(biāo)號法具體計算步驟標(biāo)號法具體計算步驟 如果剛剛得到P標(biāo)號的點(diǎn)是vi，那么，對于所有這樣的點(diǎn) 將其T標(biāo)號修改為：minT(vj)，P(vi)+wij。 若G中沒有T標(biāo)號，則停止。否則，把點(diǎn) 的T標(biāo)號修改為P標(biāo)號，然后再轉(zhuǎn)入。 其中， 滿足 開始，先給v1標(biāo)上P標(biāo)號P(v1) 0，其余各點(diǎn)

5、標(biāo)上T標(biāo)號T(vj)+（j1）。 )(min)(0jjvTvT0jv0jv標(biāo)號的標(biāo)號是而且TvEvvvjjij,例例1：在圖10.2.1所示的賦權(quán)有向圖中，每一個頂點(diǎn)vi（i=1，2，n）代表一個城鎮(zhèn)；每一條邊代表相應(yīng)兩個城鎮(zhèn)之間的交通線，其長度用邊旁的數(shù)字表示。試求城鎮(zhèn)v1到v7之間的最短路徑。 圖10.2.1 賦權(quán)有向交通網(wǎng)絡(luò)圖解解：首先給v1標(biāo)上P標(biāo)號P(v1)=0，表示從v1到v1的最短路徑為零。其他點(diǎn)(v2，v3，v7)標(biāo)上T標(biāo)號T(vj)+（j2，3，7）。 第第1步步： v1是剛得到P標(biāo)號的點(diǎn)。因為(v1，v2)，(v1，v3)，(v1，v4)E，而且v2，v3，v4是T標(biāo)號，所

6、以修改這3個點(diǎn)的T標(biāo)號為 T(v2)minT(v2)，P(v1)+w12min +，0+22 T(v3)minT(v3)，P(v1)+w13 min +，0+55 T(v4)minT(v4)，P(v1)+w14 min +，0+33 在所有T標(biāo)號中，T(V2)2最小，于是令P(V2)2。 第第2步步： v2是剛得到P標(biāo)號的點(diǎn)。因為(v2，v3)，(v2，v6)E，而且v3, v6是T標(biāo)號，故修改v3和v6的T標(biāo)號為 T(v3)minT(v3)，P(v2)+w23min5，2+24 T(v6)minT(v6)，P(v2)+w26min+，2+79 在所有的T標(biāo)號中，T(v4)3最小，于是令P(v

7、4)3。 第第3步步： v4是剛得到P標(biāo)號的點(diǎn)。因為(v4，v5)E，而且v5是T標(biāo)號，故修改v5的T標(biāo)號為 T(v5)minT(v5)，P(v4)+w45min+，3+58 在所有的T標(biāo)號中，T(v3)4最小，故令P(v3)4。 第第4步：步： v3是剛得到P標(biāo)號的點(diǎn)。因為(v3，v5)，(v3，v6)E，而且v5和v6為T標(biāo)號，故修改v5和v6的T標(biāo)號為 T(v5)minT(v5)，P(v3)+w35min8，4+37 T(v6)minT(v6)，P(v3)+w36min9，4+59 在所有的T標(biāo)號中，T(v5)7最小，故令P(v5)7。 第第5步：步： v5是剛得到P標(biāo)號的點(diǎn)。因為(v5

8、，v6)，(v5 ，v7)E，而且v6和v7都是T標(biāo)號，故修改它們的T標(biāo)號為 T(v6)minT(v6)，P(v5)+w56min9，7+1= 8 T(v7)minT(v7)，P(v5)+w57min+，7+7=14 在所有T標(biāo)號中，T(v6)8最小，于是令：P(v6)8。 第第6步：步： v6是剛得到P標(biāo)號的點(diǎn)。因為(v6，v7)E，而且v7為T標(biāo)號，故修改它的T標(biāo)號為 T(v7)minT(v7)，P(v6)+w67min14，8+5=13 目前只有v7是T標(biāo)號，故令：P(v7)13。 從城鎮(zhèn)v1到v7之間的最短路徑為(v1，v2，v3，v5，v6，v7)，最短路徑長度為13。 二、選址問題

9、二、選址問題 選址問題，是現(xiàn)代地理學(xué)研究的主要問題之一。選址問題涉及人類生產(chǎn)、生活、文化、娛樂等各個方面。 選址問題的數(shù)學(xué)模型取決于兩個方面的條件 ：可供選址的范圍、條件；怎樣判定選址的質(zhì)量。 本節(jié)的討論僅限于選址的范圍是一個地理網(wǎng)絡(luò)，而且選址位置位于網(wǎng)絡(luò)圖的某一個或幾個頂點(diǎn)上。 對這樣的選址問題，根據(jù)其選址的質(zhì)量判據(jù)，可以將其歸納為求網(wǎng)絡(luò)圖的中心點(diǎn)與中位點(diǎn)兩類問題。 （一）（一）中心點(diǎn)選址問題中心點(diǎn)選址問題 例例：某縣要在其所轄的6個鄉(xiāng)鎮(zhèn)之一修建一個消防站，為6個鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。 n中心點(diǎn)選址問題的質(zhì)量判據(jù)中心點(diǎn)選址問題的質(zhì)量判據(jù) 使最佳選址位置所在的頂點(diǎn)的最大

10、服務(wù)距離為最小。 中心點(diǎn)選址問題適宜于醫(yī)院、消防站點(diǎn)等一類服務(wù)設(shè)施的布局問題。 設(shè)G（V，E）是一個無向簡單連通賦權(quán)圖，連接兩個頂點(diǎn)的邊的權(quán)值代表它們之間的距離，對于每一個頂點(diǎn)vi，它與各個頂點(diǎn)之間的最短路徑長度為di1，di2，din。這些距離中的最大數(shù)稱為頂點(diǎn)vi的最大服務(wù)距離，記為e(vi)。 那么，中心點(diǎn)選址問題，就是求網(wǎng)絡(luò)圖G的中心點(diǎn) ，使得 )(min)(0iiiveve0ivn中心點(diǎn)選址問題的數(shù)學(xué)描述中心點(diǎn)選址問題的數(shù)學(xué)描述 例例2：假設(shè)某縣下屬的6個鄉(xiāng)鎮(zhèn)及其之間公路聯(lián)系如圖所示。每一頂點(diǎn)代表一個鄉(xiāng)鎮(zhèn)；每一條邊代表連接兩個鄉(xiāng)鎮(zhèn)之間的公路，每一條邊旁的數(shù)字代表該條公路的長度。現(xiàn)在要

11、設(shè)立一個消防站，為全縣的6個鄉(xiāng)鎮(zhèn)服務(wù)。試問該消防站應(yīng)該設(shè)在哪一個鄉(xiāng)鎮(zhèn)（頂點(diǎn)）？ 圖10.2.2解解：第第1步：步：用標(biāo)號法求出每一個頂點(diǎn)vi至其他各個頂點(diǎn)vj的最短路徑長度dij（i，j 1，2，6），并將它們寫成如下的距離矩陣027474205256750343423036754303463630666564636261565554535251464544434241363534333231262524232221161514131211ddddddddddddddddddddddddddddddddddddD 第第2步：步：求每一個頂點(diǎn)的最大服務(wù)距離。顯然，它們分別是矩陣D中各行的最大值，

12、即： e(v1)6，e(v2)7，e(v3)6，e(v4)7，e(v5)6，e(v6)7。 第第3步：步：判定。因為e(v1)e(v3)e(v5)mine(vi)6，所以v1，v3，v5都是中心點(diǎn)。也就是說，消防站設(shè)在v1，v3，v5中任何一個頂點(diǎn)上都是可行的。 中位點(diǎn)選址問題的質(zhì)量判據(jù)中位點(diǎn)選址問題的質(zhì)量判據(jù) 使最佳選址位置所在的頂點(diǎn)到網(wǎng)絡(luò)圖中其他各個頂點(diǎn)的最短路徑距離的總和（或者以各個頂點(diǎn)的載荷加權(quán)求和）達(dá)到最小。（二）中位點(diǎn)選址問題（二）中位點(diǎn)選址問題 中位點(diǎn)選址問題的數(shù)學(xué)描述中位點(diǎn)選址問題的數(shù)學(xué)描述 設(shè)G（V，E）是一個簡單連通賦權(quán)無向圖，連接兩個頂點(diǎn)的邊的權(quán)值為該兩頂點(diǎn)之間的距離；對

13、于每一個頂點(diǎn)vi（i1，2，n），有一個正的負(fù)荷a(vi)，而且它與其他各頂點(diǎn)之間的最短路徑長度為di1，di2，din。那么，中位點(diǎn)選址問題，就是求圖G的中位點(diǎn) ，使得 0ivnjijjiiiidvavSvS10)(min)(min)(例例3：某縣下屬7個鄉(xiāng)鎮(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)（頂點(diǎn)）？ 圖10.2.3解：解：第第1步：步：用標(biāo)號法求出每一個頂點(diǎn)vi至其他各個頂點(diǎn)vj的最短路徑長度dij（i，j 1，2，7），并將其

14、寫成如下距離矩陣 77767574737271676665646362615756555453525147464544434241373635343332312726252423222117161514131211dddddddddddddddddddddddddddddddddddddddddddddddddD05 . 13 . 63 . 35365 . 108 . 48 . 15 . 35 . 15 . 43 . 68 . 40353 . 63 . 93 . 38 . 13023 . 33 . 655 . 35202535 . 13 . 63 . 320365 . 43 . 93 . 6530 第第2 2步：步：以各頂點(diǎn)的載荷（人口數(shù)）加權(quán)，求每一個頂點(diǎn)至其他各個頂點(diǎn)的最短路徑長度的加權(quán)和 3 .1