面向大規模道路網的最短路徑近似算法

張志然，劉紀平，仇阿根，錢新林，張福浩

1. 武漢大學資源與環境科學學院，湖北 武漢 430079； 2. 中國測繪科學研究院，北京 100830； 3. 河南省科學院地理研究所，河南 鄭州 450052

隨著社會經濟和城市建設的發展，城市道路網規模逐漸擴大，并逐漸表現出復雜網絡的特性。對大規模路網來說，采用經典算法計算精確的最短路徑普遍存在時間復雜度過高、存儲消耗過大等問題[1-2]。在大部分實際應用中，可以使用良好的近似路徑來代替精確路徑，同時考慮計算時間和精度間的平衡[3]。多年來，研究學者提出多種預處理技術，包括啟發策略[4-5]、分層策略[2,6]、地標點策略[7-11]等，通過預處理保留網絡部分重要信息，達到提高計算效率的目的。

地標點策略被廣泛地應用于兩節點間的距離估計，通過選擇一定數量的中心節點，并預計算所有中心點間的最短路徑來提高計算效率，選擇的節點也稱為landmarks[7-8]、reference nodes[9]、beacons[10]、tracers[11]等。文獻[7]提出了滿足誤差限制條件的基于覆蓋和分割的地標選擇方法；文獻[8]對地標點選擇策略進行總結，對比分析了基本策略、限制策略和劃分策略在地標點選擇上的效率，并結合三角測量原理在社交網絡上進行最短路徑估計；文獻[10]在隨機選擇參考點的基礎上，通過可以進行一定比例調整的距離來保證性能。上述研究表明，最短路徑估計可以利用地標點提升計算效率。然而，這些方法不能同時實現地標點的規模控制和均衡分布，當地標點規模較大時，預計算所有地標點間的距離也具有較高的空間復雜度。

地標點可以充分利用節點的重要性提高選取質量。同時，在大規模道路網中，兩節點間的最短路徑較大可能地經過較為重要的節點，交通發達的地方，節點分布往往比較密集，大部分節點通常經過中心性較大的節點連接在一起。節點重要性對最短路徑的計算具有一定的啟發性。復雜網絡中的節點重要性評價的方法很多，多采用單一指標或多指標的形式[12-13]。度中心性[14]、中介中心性[15]、接近中心性[16]等方法均分別從不同的方面刻畫了節點在特定網絡中的重要性。但現實道路網結構類型多樣，很難用單一指標來說明節點在網絡中的重要程度[13]。

本文針對大規模道路網的結構特點，結合地標點策略和層次策略，提出一種顧及節點重要性的最短路徑估計方法。該方法應用復雜網絡理論和Critic賦權法分析節點的重要性，通過限制參數和節點重要性序列使中心節點均衡的分布于網絡中，同時，制定層次網絡構建方案將原網絡中的部分搜索問題轉移到高層網絡中，尋找一條實際存在的近似路徑作為可能的最短路徑，從而提高運算效率并保持較高的有效性。

1 節點重要性評價方法

1.1 評價指標

利用復雜網絡理論分析道路節點在網絡中的幾何或屬性特性，能夠準確地定位網絡的重要節點，對網絡中重要基礎設施和交通樞紐的協調管理，增強城市交通管理和服務質量，提高路徑分析和交通擁堵分析的效率具有重要的現實意義。度中心性、集聚系數[17]、接近中心性、中介中心性、特征向量中心性[18]等是當前節點重要性評價中主要的量化指標[19-22]。這些重要性度量指標最初應用在社會網絡中，隨后被推廣到其他類型網絡的研究中。在現實道路網中，節點常用來表示道路口、交叉路口、交通樞紐等，節點之間的連邊表示實際道路線，邊的權重表示該條道路的實際長度、歐氏距離、旅行時間距離等。

(1) 度中心性，是指網絡中與節點直接連接的邊數[14]

(1)

式中，δij表示與節點i是否與節點j相交，若相交，則δij=1，否則為0。度中心性是研究節點中心性最直接的度量指標，其值越大，表明節點越重要，連接的道路越多。

(2) 局部集聚系數，是指節點的相鄰節點之間的連接數與它們所有可能存在的連接數的比值[17]。無向圖中節點i的集聚系數為

Clc(i)=2ei/kiki-1

(2)

式中，ki為i的鄰接節點數，i與其鄰接節點之間最多可能存在2/kiki-1條連接，ei為鄰接節點間的邊的數量。集聚系數表示節點的聚集程度，其值越大，表明節點與鄰接節點間存在模塊結構的可能性越大。

(3) 接近中心性，是指節點到其他所有節點的最短路徑長度之和的倒數[16]

(3)

式中，dist(v,s)為節點i與j之間的最短路徑長度。接近中心性反映道路節點與其他節點之間的接近程度，用來度量節點在網絡中是否處于核心位置，其值越大，表明節點越重要，節點的影響及服務范圍越廣。

(4) 中介中心性，是指經過該節點的最短路徑數目與所有最短路徑數目的比值[15,22]

(4)

式中，σst為任意節點s到t的最短路徑數目，σst(i)為節點s到t的最短路徑中經過節點i的最短路徑數目。中介中心性反映了節點作為“橋梁”的重要程度，其值越大，表明最短路徑經過的次數越多，在整個網絡中的影響力和控制力越強。

(5) 特征向量中心性，通過鄰接節點的重要性來衡量本節點的重要性[18]

(5)

式中，A=ai,j為鄰接矩陣，如果節點i與j相連，則ai,j=1，否則為0；λ為常數，M(i)為節點i的鄰接節點。特征向量中心性反映了節點在網絡中的價值，相比于接近中心性，其考慮了鄰點的重要性。

1.2 基于Critic的多指標集成

單一指標僅能從單一層面反映節點的重要性，且節點重要性不僅取決于自身屬性，在一定程度上受其相鄰節點甚至更遠節點的影響[19]。為了綜合考慮節點在網絡中起到的局部及全局影響，以上述指標綜合評價網絡節點的重要性，更準確有效地發掘出復雜網絡中的重要節點，節點重要性評價模型定義如下

Ii=α1Cd(i)+α2Clc(i)+α3Ccc(i)+

α4Cb(i)+α5Ce(i)

(6)

式中，Ii為節點i的重要度；α1、α2、…、α5為系數；Cd(i)、Clc(i)、…、Ce(i)分別表示離差標準化后的度中心性、集聚系數、接近中心性、中介中心性和特征向量中心性。

由于指標系數的確定缺少專家經驗和可靠的網絡信息，本文對指標參數α1、α2、…、α5進行多重共線性分析，采用客觀賦權法Critic方法[23]實現模型信息量的最大化。指標Cj,0

(7)

式中，δj為第j個指標的標準差，rjk為指標j與k間的相關系數。可以看出，指標j的信息量包含兩部分：①單指標內部信息量，即指標標準差δj；②不同指標間的信息量，即指標與其他指標的沖突性rjk，rjk越大，沖突性越低。Ej越大，指標所包含的信息量越大，該指標的相對重要性越強。那么，指標Cj的系數αj表示為

(8)

2 顧及節點重要性的最短路徑估計方法

2.1 方法流程

本文的研究思路可概括為：首先，根據原始網絡計算單項評價指標，利用Critic方法實現節點重要性的多指標集成；其次，依據節點序列及限制條件，選擇中心節點并實現網絡劃分；然后，根據中心節點集合和中心節點間的連接關系構建層次結構網絡；最后，在層次結構網絡上實現最短路徑值的估計。方法流程如圖1所示，主要步驟描述如下：

(1) 節點重要性評價。從原始網絡中提取節點重要性的評價指標，采用客觀賦權法Critic方法探究節點重要程度，生成節點重要性序列。

(2) 中心節點選擇與網絡劃分。依據節點重要性序列，以優先重要性強的節點、排除被標記的節點為原則生成中心節點集，通過限制參數將原始網絡劃分為若干個子網絡(見2.2節)。

(3) 層次結構網絡構建。中心節點集構成層次結構網絡的節點，對具有連接關系的中心節點間進行輔助邊構建，構成層次結構網絡的邊。

(4) 最短路徑估計。依據所構建的層次結構網絡，實時計算得到任意兩個節點間的近似最短路徑(見2.3節)。

圖1 方法流程Fig.1 Analysis process

2.2 網絡劃分策略

影響最短路徑計算精度的一個核心因素是網絡劃分，而中心節點作為子網絡的核心，其選擇很大程度上影響了劃分的效率和劃分后網絡的拓撲結構?，F有研究中提出和使用的中心點選擇的基本策略，主要包括隨機法與基于度中心性、中介中心性、接近中心性等帶有啟發思想的度量方法?；静呗砸云渲心骋环N方法作為中心節點的選擇策略，指定選取數量控制節點規模。但是，基本策略可能會使中心節點分布較為集中，部分中心節點的覆蓋貢獻較小，因此，本文在此基礎上，引入多指標評價模型將網絡節點的相對重要性進行量化，通過限制性的網絡劃分策略，使中心節點較為均勻的分布于整個網絡。

不妨假設某一中心節點li的覆蓋范圍為β，被li所覆蓋的節點不納入選擇范圍，在能夠有效減小中心節點規模的同時，提高算法執行效率。為此，從空間角度引入規模參數m和深度參數h，分別用于調節中心節點的覆蓋范圍。對于無向圖GV,E,W，網絡劃分包括以下幾個步驟：

(1) 依據節點重要性由高到低排序得到序列T。

(2) 從序列T中依次選取節點s。

(3) 若s未被標記，將s加入到中心點集S，將以s為中心節點的子網絡記為Gs，并執行步驟(4)，否則執行步驟(2)。

(4) 從節點s開始執行寬度優先遍歷，若搜索到的節點t滿足覆蓋條件βm,h，則對t進行標記，并劃分到子網絡Gs中，記錄s到t的最短路徑。

(5) 循環執行步驟(2)—(4)，直到序列T為空。

以上步驟生成了一個包含d個中心節點的集合S，并將原始網絡G劃分為d個子網絡，記為G1、G2、…、Gd。本文以節點數量表示規模參數，以節點到中心節點的最短距離上限表示深度參數，即βm,h滿足dists,t≤h且numVs≤m，其中，Vs表示Gs的節點集，numVs表示Gs包含的節點數量。

如圖2所示，每兩個節點間的距離值為1，β1和β2表示節點li的覆蓋條件，其中，淺色陰影部分覆蓋的節點滿足β1:m=13,h=2，虛線范圍內的節點滿足的β2:m=25,h=3，被覆蓋的節點和邊組成以li為中心節點、以β1/β2為限制參數的子網絡Gli。

在對網絡進行劃分后，將中心節點集合抽象為層次結構網絡的節點，依據子網絡間的連接情況構建輔助邊，這些邊構成層次結構網絡的邊。給定無向圖G(V,E,W)，劃分后的子網絡為{G1,G2,…,Gd}，Gi(Vi,Ei,Wi),1≤i≤d對應中心節點li，構建思想主要包括兩步：節點收縮和輔助邊構建。節點收縮：將Gi中所有節點壓縮為一個超級節點li；輔助邊構建：在存在公共節點或連接邊的任意兩個子網絡Gi,Gj間的超級節點li與lj間添加輔助邊lj,k，并計算和保存li與lj的最短路徑。因此，層次結構網絡Gh為一個包含d個中心點的圖，實現了網絡規模的收縮。如圖3所示，黑色節點為中心節點，白色節點為普通節點。圖3(a)中灰色橢圓表示網絡劃分情況；圖3(b)表示具有連接關系的中心節點間的最短路徑；圖3(c)表示構建得到的層次結構網絡，基于層次結構網絡實現最短路徑的近似計算。

圖2 中心節點覆蓋示意圖Fig.2 Coverage of the center nodes

圖3 層次結構網絡構建示意圖Fig.3 Network partition

2.3 最短路徑近似估計

為了有效估計兩節點間的最短路徑，本文以通過中心節點的一條實際存在的路徑近似代表節點間的最短路徑，分別計算起始點或目標點到與其最近的中心節點間的最短距離，然后在層次網絡中進行最短路徑計算。因此，對于任意節點對(s,t)，其最短路徑包含三部分，即s和t分別到所屬子網絡中距離其最近的中心節點間的最短路徑與中心節點間的最短路徑之和。最短路徑及最短路徑的近似值表示為

dist(s,t)=dist(s,ls)+dist(ls,lt)+dist(t,lt)

(9)

path(s,t)=path(s,ls)+path(ls,lt)+path(t,lt)

(10)

式中，ls、lt表示到s、t所屬子網絡中距離最近的中心節點，path(s,t)表示s到t的近似最短路徑，dist(s,t)表示s到t的近似最短路徑值。dist(ls,lt)、在Gh中計算得到，為近似值；dist(s,ls)、dist(t,lt)、path(s,ls)與path(t,lt)在網絡劃分時已經進行計算并存儲，為真實值，因此可以直接查詢獲得。若s為中心節點，則dist(s,ls)、path(s,ls)項為0；同理，若t為中心節點，則dist(t,lt)、path(t,lt)項為0。為了保證路徑的真實性，在計算path(ls,lt)的過程中動態讀取輔助邊計算的中間結果，即具有連接關系的中心節點間的最短路徑，最終生成一條實際存在的近似路徑。

與常見的隨機方法、度中心性等基本策略不同，在最短路徑計算時，考慮了大規模道路網中最短路徑較大可能經過重要性較大的節點，算法依據網絡中的節點重要性來構建中心節點集合、劃分區域，充分考慮了網絡的拓撲結構。同時，常見的基于地標點的最短路徑估計方法，通過預處理所有地標點間的最短路徑，以求在查詢時可以達到O1的時間復雜度，但對于大規模道路網數據，往往需要較高的空間復雜度。本文在充分簡化后的層次網絡上實時計算最短路徑，在滿足一定的精度要求情況下，降低了空間復雜度，有效提高了計算效率。

3 試 驗

3.1 數據集

本文使用大規模道路網數據——紐約城市道路網作為測試數據。紐約城市道路網為無向平面圖，有264 346個節點和730 100條邊，99%的節點度分布在[1,4]之間。道路交叉口和道路分別抽象為網絡的節點和邊，邊權重為相應的路段的長度。本文采用復雜網絡分析軟件計算生成節點的度中心性、集聚系數、接近中心性、中介中心性和特征向量中心性，指標的描述性統計信息見表1。

表1 評價指標的描述性統計

首先，對指標進行標準化，計算各指標的標準差和相關性，根據Critic方法計算各指標的綜合權重(見表1)。從表中可以看出，對于該道路網來說，接近中心性和度中心性在5項指標中具有較大的權值，占總比重的60%，而中介中心性的權值最小，為0.070 7。節點重要性的綜合統計結果顯示，節點重要值呈正態分布特征。其中，88%的節點的重要性值介于[0.1,0.4]之間，表明絕大部分節點具有相似的重要性；僅有9%的節點重要性值介于[0.5,1.0]之間，說明網絡中存在少量的占支配地位的節點。

3.2 層次網絡構建結果分析

為了比較單指標與綜合指標計算得到的節點重要性，以及限制條件等因素對層次網絡和最短路徑計算結果的影響，本文分別采用隨機法、度中心性和多指標集成法，基于約束條件進行網絡劃分與層次結構網絡構建，分別記為RANDOM/β、DEGREE/β和SYNTHESIS/β。同時，將上述方法同兩種現有選取思想進行比較：①文獻[24]中區域中心點的選擇策略，考慮復雜網絡的無標度特性，依據節點度中心性序列，選取的中心節點集合滿足度數之和不大于全部節點度數之和的50%，或數量不超過節點總數的10%，記為DEGREE/CDZ；②文獻[7]中帶有限制條件的地標點選擇策略，通過深度參數h降低覆蓋的重疊度，本文以綜合節點重要性定義節點序列，記為SYNTHESIS/h。

為了進一步探討限制參數β對層次網絡規模的影響，分別設置參數β1(5,200)、β2(10,400)、β3(15,600)、β4(25,800)、β5(40,1000)、β6(55,1200)、β7(75,1400)、β8(95,1600)、β9(120,1800)、β10(150,2000)、β11(185,2200)、β12(220,2400)，前者規模參數m以節點數量表示；后者深度參數h表示節點到中心節點的最短距離上限，單位為米。從中心節點的數量占節點總數的比例(見圖4)、輔助邊數量與原始網絡邊總數的比值(見圖5)兩個方面來衡量層次網絡的規模。

圖4 不同選取方法下中心節點數量占比Fig.4 The percentage of center nodes in different methods

圖5 不同選取方法下輔助邊數量占比Fig.5 The percentage of auxiliary edges in different methods

圖4和圖5所示：①5種方法均有效降低了原始網絡的規模，除DEGREE/CDZ方法指定了中心節點數量外，其他方法得到的中心節點數量和輔助邊數量均隨參數變化呈指數型降低；②SYNTHESIS/β、DEGREE/β和RANDOM/β方法在數量上沒有明顯的差異，β1(5,0.2)時，SYNTHESIS/β方法得到的層次網絡規模最大，但其中心節點數量和輔助邊數量也僅占原始網絡節點數量和邊的36%和64%，β12(220,2.4)時，3種方法的中心節點數量和輔助邊數量均僅占原始網絡節點和邊的1.3%和4.8%；③SYNTHESIS/h方法只采用深度參數h作為限制條件，因此增大了中心節點的覆蓋范圍，在數量上明顯小于上述3種方法。

3.3 最短路徑近似結果分析

在構建的5種層次結構網絡上，本文采用點對點Dijkstra算法[25]近似計算任意兩點間的最短路徑，使用二叉堆實現優先隊列，算法復雜度為O(mlogn)[26]。在大規模網絡上估計所有節點的最短路徑是非常昂貴的，因此，從原始網絡中隨機選取500個節點對，根據不同層次網絡上最短路徑值的平均路徑比，測評計算的準確性。路徑比是指若干節點對的最短路徑近似值與精確值比值，比值越接近1，表示方法的準確率越高。

為了比較不同方法構建的層次網絡對計算精度的影響，圖6顯示了最短路徑比與限制參數的變化趨勢。結果顯示，DEGREE/CDZ方法的平均路徑比為1.128，其他方法均隨參數的增大而增大；在一定參數范圍內，SYNTHESIS/β方法最為精確，β1時路徑比達到1.026，DEGREE/β略高于SYNTHESIS/β方法；RANDOM/β方法隨機選擇中心節點，通用性較好，但是沒有考慮網絡的拓撲結構特性，準確性最低。SYNTHESIS/β與DEGREE/β方法考慮了網絡的中心性特征，優先考慮具有較大重要性的節點，說明重要性越大的節點在最短路徑計算中起越重要的作用。

圖6 不同方法下的平均路徑比Fig.6 Average path ration in different methods

圖7表示中心節點規模同平均路徑比的關系，從4種方法的趨勢線可以看出，平均路徑比隨著中心節點數量的降低而增加。對于相同數量的中心節點，SYNTHESIS/β和SYNTHESIS/h方法表現出較高的準確性，且變化趨勢基本吻合，而RANDOM/β方法的準確性最低。由本文算法的原理可知，節點重要性評價模型和限制參數的取值直接影響了中心節點的選取結果，并最終影響了最短路徑的計算精度。隨著限制參數的增大，中心節點的數量也增大，子網絡規模越來越大。本文的中心節點選擇方法與網絡劃分方法SYNTHESIS/β與SYNTHESIS/h的試驗結果表明，相對于單一指標，對多指標集成方法能夠更好地保留重要節點，有效降低了中心節點的數目，且估算結果較為精確，同時滿足了距離的性能與準確性的要求。

圖7 平均路徑比與中心節點數量關系Fig.7 The relationship between average path ration and number of center nodes

由算法復雜性可知，最短路徑的計算時間隨網絡規模的減小而減小，所以在相同的限制參數下，SYNTHESIS/h計算時間最優，但其計算精度低于SYNTHESIS/β、DEGREE/β。原始網絡中最短路徑的平均計算時間為3.76 s，圖8可以看出，SYNTHESIS/β、DEGREE/β和RANDOM/β方法在計算時間上基本吻合，對計算精度最為精確的SYNTHESIS/β方法來說，在參數β1到β12，計算時間呈指數型降低，從1.412 s到0.039 s，計算效率提高了2.7到94倍。通過以上分析，SYNTHESIS/β方法不僅能保證較高的計算精度，也能夠有效提高最短路徑的計算效率。

為了更好地顯示近似最短路徑的估計效果，在不同參數下選取任意節點對進行近似最短路徑計算。圖9給出了參數為β1、β3、β5、β7、β9、β11等6種取值下的計算結果，灰色粗線表示節點間的精確路徑，黑色粗線表示相應參數下的近似最短路徑?？梢钥闯?，在不同參數下，β1、β3和β5得到的近似最短路徑均能較好地分布于精確路徑的周邊，隨著參數的增大，差距越大。因此，在實際的最短路徑計算中，本文方法顧及了節點的重要性和限制范圍，降低了網絡規模，通過調整選取參數，可以根據誤差要求選取一定的參數進行最短路徑的近似估計，滿足了道路網下最短路徑近似計算的基本要求。

圖8 最短路徑平均計算時間Fig.8 Mean time of shortest paths

圖9 不同參數下最短路徑近似結果Fig.9 Approximation results of shortest path in different parameters

4 結 論

本文在分析節點重要性評價指標的基礎上，基于Critic方法與復雜網絡理論實現節點重要性的綜合評價?；诖?，提出了顧及節點重要性的最短路徑估計方法，引入規模參數和深度參數實現網絡劃分，制定層次結構網絡的構建方案，實現大規模道路網數據的有效化簡和最短路徑的快速有效估計。本文以大規模道路網數據進行測試，試驗結果說明，顧及節點重要性的最短路徑估計方法能夠更好地均衡劃分后子網絡的規模，提高最短路徑的計算效率的同時保持了較高的計算精度，適用于大規模的道路網的最短路徑快速計算。

以復雜網絡理論為基礎，本文方法能夠為面向較大規模的交通運輸網絡、社會關系網絡、通訊網絡等現實網絡的節點重要性分析、網絡簡化和最短路徑分析等提供思路。本文方法僅從網絡本身的拓撲與空間特征出發進行處理，未對道路網的屬性特征和城市結構特征等因素進行考慮。后續需要擴展研究的內容有以下3點：①目前試驗表明該方法對于單中心特征明顯的紐約市數據具有較好的適用性，今后將在不同類型城市道路網(如多中心、放射狀、環狀道路等)上考察該方法的適用性與應用特點，進行更全面的評估和改進；②節點重要性分析、限制參數的界定與道路網節點的實際輻射范圍存在關聯，結合現實道路網中節點或邊的屬性信息，實現不同類型道路網的最短路徑特征研究與動態分析；③實際道路網絡多為有向圖且具有轉向限制，基于有向圖計算得到評價指標，在計算過程中考慮邊的方向性，將該方法拓展到有向交通網絡中；結合混合邊-節點算法[27]進一步研究具有轉向限制的大規模道路網絡的最短路徑近似計算。