交通路網中最優路徑算法的道路權重選擇

［摘 要］在交通路網中，尋找任意兩點間最優路徑是出行導航的基本功能。除了最優路徑算法自身性能外，道路權重的選擇也直接決定了尋徑結果的優劣。現有最優路徑算法通常以通行能力為道路權重，其可能導致不合理的尋徑結果，同時也不具有全局負載均衡的能力。因此本文以Dijkstra算法為例，引入可達性概念作為道路權重，從而彌補以通行能力為道路權重的缺陷。

［關鍵詞］Dijkstra算法；道路權重；通行能力；可達性

doi:10.3969/j.issn.1673-0194.2009.15.017

［中圖分類號］C931；U412.37［文獻標識碼］A［文章編號］1673-0194（2009）15-0054-03

1 引 言

在交通路網中，兩點間最優路徑算法的優劣主要受到兩個因素的影響，即所使用的通用最短路徑算法和所選擇的道路權重。通用最短路徑算法是最優路徑選擇的搜索工具，決定了如何在龐大的路網數據庫中找到最優（或者最滿意）的可行路徑。道路權重則是最優路徑選擇的搜索指標，它的標定決定了通用最短路徑算法搜索的依據。所謂最優路徑選擇就是使用通用最短路徑算法搜索道路權重最高（或者局部最高）的可行路徑。因此，通用最短路徑的選擇直接影響到最優路徑選擇的效率和優化度，而道路權重直接影響到最優路徑選擇的合理性。

其中，研究人員普遍關注所選用的通用最短路徑算法。為解決這個問題，現在已有多種優秀的最優路徑算法，如Dijkstra算法、Floyd算法、A*算法等。但是，研究人員常常忽視了道路權重問題，提供給出行者的道路權重選擇沒有貼近出行者的實際出行習慣，并不能真正滿足出行者的需求。

在現有的靜態駕駛導航和出行者信息系統中，普遍選擇通行能力為道路權重。所謂通行能力是指兩點間行駛路徑的平均通行流量，如果出行者所行駛的道路平均通行流量最大，就意味著出行者能夠以最短的時間到達終點。這是一種以時耗為優先衡量標準的最優路徑算法，貼近于城市出行者的出行特點。但是以通行能力為道路權重所得出的最優路徑有以下缺陷：

（1）忽視出行者能耗（出行距離遠近）損失；

（2）缺乏城市路網全局負載均衡能力。

因此，本文以較為經典的Dijkstra算法為通用最短路徑算法，解析以通行能力為道路權重的最優路徑算法產生以上兩個缺陷的原因，并進一步提出道路權重的選擇應考慮城市路網的可達性，在算法中引入路網可達性的概念，從而使算法兼顧出行者的能耗和時耗，同時能夠對城市路網起到全局負載均衡的作用。

2 Dijkstra算法簡介

Dijkstra算法是由E.W. Dijkstra于1959年提出的一個最短路徑算法，也是目前公認的求解最短路徑問題的最經典的算法。其基本思想是用逐點增長的方法構造一棵路徑樹，從而得到從該樹的根節點（即起點）到其他所有節點的最優路徑。其基本原理是：［1］

（1）從起點出發，遍歷所有直接連通節點，將其中權重最大的節點作為中間節點；

（2）擴展出該中間節點的所有后續節點，并遍歷該中間節點的所有直接連通節點，并修改其他節點在加入該中間節點后距離起點的距離；

（3）選擇出權重最大的節點，將其加為中間節點，并修改其他的中間節點；

（4）循環執行第（2）、（3）步，直至找到終點。

由此可以得到按權重遞增次序排列的從起點出發經過各中間節點到達終點的最優路徑序列。

從以上描述可以看到，Dijkstra算法首先尋找道路權重最大的節點，以后中間節點的道路權重順次遞減。那么如果以通行能力為道路權重，該算法會首先找到起點周邊通行能力最高的道路，然后順次擴展。

3 選擇通行能力為道路權重

本節以Dijkstra算法為通用最短路徑算法，解釋在最優路徑算法中選擇通行能力為道路權重時的兩個缺陷。

3.1 忽視出行者能耗損失

本文利用某應用以通行能力為道路權重的Dijkstra算法的尋徑軟件，演示該算法在面對同一小區內距離較近的兩點時，所得出的最優路徑。

圖1 軟件對同一小區內近距離兩點之間所得出的最優路徑

從圖1中可以看到，某小區是一正方形區域，四角分別為A、B、C、D四個點。小區四邊有4條道路：其中AD和DC是主要道路，通行能力較強，但繞行距離較遠；AB和BC路段則是連接路網不同小區的次要道路，通行能力較弱，但很明顯起點和終點都是在一條AB線路附近。從圖中起點到終點，該軟件給出了走AD→DC→CB的最優路徑，很明顯該最優路線并不合理。

Dijkstra算法首先將起點綁定到最近的AB道路上，同時在綁定點的直接連接點中搜索與起點間通行能力最高的節點，自然會把AD線路上的節點作為中間節點，并沿著AD線路擴展搜索，因此最終會沿著DC→CB線路找到終點。圖2展示了該算法的遍歷點范圍。在圖2中可以看到，該算法雖然在起點周圍遍歷了AB線上的點，但是最終還是選擇了通行能力更高的AD線上的點。

通過這個Dijkstra算法實例可以看到，以通行能力為道路權重的最優路徑算法在對近距離的兩點尋徑時會“舍近求遠”。即選擇通行能力為道路權重時，算法單純以時耗作為出行者選擇的要求，忽視了出行者能耗的需求，給出行者規劃出一條行駛速度快但是繞遠的路途。

圖2 以通行能力為道路權重的搜索范圍

3.2 缺乏城市路網全局負載均衡能力

一個城市的道路網絡由不同等級的道路組成，不同等級的道路的通行能力和功能要求均不相同。只有整個城市的交通負載根據出行者目的的不同，均衡分布在不同等級的道路，這個城市的路網才能得到最有效的利用，道路交通才能達到均衡的狀態。很多城市交通擁堵問題都是由于城市路網負載不均衡引起的。而導航系統和出行者信息系統作為城市交通誘導系統的一部分，應當起到均衡城市路網負載的作用。

我國現行的道路功能等級分類方法采用國標《城市道路交通規劃設計規范》提出的道路分類法，將城市道路分為城市快速路、主干道、次干道和支路。城市交通網絡中，機動車總要通過選擇不同層次的道路來完成一次出行。理想狀況下，城市網絡中各等級道路的使用情況如圖3所示。短距離出行應優先采用次干路和支路，長距離出行應選擇主干路和快速路。即次干路和支路的主要功能是為短距離出行和中長距離出行集散服務;主干路和次干路的主要功能是快速輸送中長距離客貨流。［2］

而以通行能力為道路權重的最優路徑算法忽視了城市路網層次機構，偏重于出行者需求的局部最優化，沒有考慮到城市路網的全局負載均衡。選擇通行能力為道路權重沒有考慮到起始點和目的地之間的距離，無論出行者行駛距離或遠或近，均盡量在通行能力大的道路上行駛，從而加重了原本已經擁堵的城市快速路和主干線的負擔，而次干道和支路則是利用率不足。這樣的導航系統和出行者信息系統也失去了其平衡城市交通路網負載的意義。［3］

4 城市路網可達性

綜合上述缺陷，可看到其主要原因是以通行能力為道路權重忽略了能耗和時耗的綜合指標，從而出現了“舍近求遠”和“局部優化、全局失衡”的現象。為了彌補這些缺陷，在此引入一個新的綜合指標——可達性。

Hansen于1959年首次提出可達性的概念［4］，將其定義為交通網絡中各節點間相互作用機會的大小，并利用重力方法研究了可達性與城市土地利用之間的關系。之后，城市規劃、交通地理等領域的專家相繼對此進行了研究，并給出了不同的定義。可達性這一概念所要表述的是路網中任意點之間通達的可能性及難易程度，是基于能耗和時耗的綜合評價指標，這兩點又與路網的機動性和繞行指數相關。

4.1 機動性

機動性反映的是交通的快捷程度，它要求城市道路體系要保障一定的速度服務水平，用行程速度來量度。路網所提供的服務車速越高，表明它的機動性越好，在一定的時間內所行駛的距離越長，可達范圍愈大。

Vj=S / t（1）

式中，Vj為行程速度（km/h），是機動性的度量，S為行駛道路長度（km），t為行程時間（h）。

4.2 繞行指數

繞行指數是指兩點之間的運行線路長度與其間的直線距離之比，它反映的是兩點之間運行線路的繞行程度。通達點之間的到達是采用某種交通方式以一定的行程速度在可行線路上完成的，該線路是否合理，是否為最短路徑，只有用兩點間的直線距離來比較衡量，繞行指數越小，兩點之間越接近于直線連接，損耗越小。

=S /D（2）

式中，為繞行指數，反映路網的直達性；S為兩點間的運行線路長度（km）；D為兩點之間的直線距離（km）。

4.3 可達性

可達性反映的是路網的交通可達能力，它應當定義為單位時間內可實現通達的直線距離，在數值上等于行程速度與繞行指數之比。

Ck=D / t=Vj/（3）

式中，Ck為可達能力(km/h)，是可達性的量度。

上述可達性定義把道路交通的固定設施和移動工具有機地結合起來，在反映可達能力的同時也道出了路網的機動運行效率和結構的合理性。例如從60 (km/h)/1.2 = 50 (km/h)中，可以得到的結論是50 km的距離需要1h的路程，車速利用率中等但會有10 km的繞行，而50 (km/h) /1.0=50 (km/h)中的速度雖然較低，但卻具有相同的可達能力，且又為直線最短路徑，能耗要小于前者。這個定義是把時耗和能耗統一起來的可達性表達方式，是已有可達性概念的本質反映，是較為理想的路網可達性定義。［5］

5 選擇可達性為道路權重

可達性概念也可以作為道路權重的選擇之一。如果將道路權重換為可達性定義，則一個節點距離起點的道路權重取決于該點與起點之間的直線距離與時間之比，也是平均速度與繞行指數之比。

如圖4所示，其中藍色E點和紅色F點為兩個中間點。很明顯，AF的繞行指數接近為1，而ADCE的繞行指數接近為3，那么只要ADCE的平均速度不大AF的3倍，那么AF的可達性比ADCE的可達性要大，所以算法最終會選擇F點作為中間節點，而不是ADCE節點。

圖4 兩個中間節點的可達性道路權重比較

6 總 結

從以上描述中可以看到，以可達性為道路權重的Dijkstra算法通過引用時耗和能耗的綜合指標——可達性，規避了通行能力為道路權重的最優道路不合理缺陷。

以可達性為道路權重也考慮到了出行者的行駛距離。如果出行者的出行距離較遠（如城間出行），起訖點之間直線距離長且可選擇路徑少，繞行指數會比較低，從而算法會更多地考慮出行者時耗需求，將出行者誘導在通行能力更高的道路上；如果出行者的出行距離較短，起訖點之間的直線距離短且可選擇路徑多，繞行指數會比較高，從而算法會均衡出行者時耗和能耗的需求，將出行者誘導在通行能力較低的道路上。因此以可達性為道路權重也起到了一定的均衡城市路網全局負荷的作用。

道路權重是最優路徑算法的搜索指標，它決定了最短路徑搜索的趨勢方向，與所選用通用最短路徑算法并沒有直接的聯系。可達性對于其他通用最短路徑算法也具有一定的適用性。但是筆者尚沒有驗證在其他算法中也能實現相當的效果。

雖然以可達性為道路權重具有以上優點，但是在實驗中發現，其沒有完全規避掉高通行能力的問題，它仍然會搜索大量的高通行能力中間點，因此其效率仍較低，因此可以考慮設計一個簡單比例系數，以減小通行能力在道路權重中的比例，從而減小算法的搜索范圍，提高算法的搜索效率。

主要參考文獻

［1］ 楊兆升. 城市交通流誘導系統［M］. 北京：中國鐵道出版社，2004.

［2］ 中華人民共和國建設部. 中華人民共和國行業標準——城市道路設計規范CJJ37-90 ［S］.1990.

［3］ 郭繼孚. 從行車路徑看城市路網功能結構問題——以北京市為例［J］. 城市問題，2007（6）.

［4］ WG Hansen. How Accessibility Shapes Land Use［J］. Journal of the American Planning Association， 1959， 25(2): 73-76.

［5］ 曾松，楊佩昆，方棣波. 城市道路網結構的可達性評價［J］. 同濟大學學報: 自然科學版， 2001(6).

The Selection of the Route Weight for Optimum Path Algorithm

in the Transportation Network

BAI Chen

(School of Economics and Management， University of Science and Technology Beijing，

Beijing 100083， P.R.China)

Abstract: Searching for the optimum path between any two points in the traffic net is the basic foundation of travel navigation. In addition to its own performance of the optimal path algorithm， the selection of the route weight directly determines the result of the merits of routing. Currently， the traffic capacity is usually used as the route weight in the optimal path algorithms， which may lead to unreasonable results and can’t achieve the overall load balancing. Therefore， in this paper， Dijkstra algorithm being as an example， the Accessibility is introduced as the road weight to make up those deficiencies caused by traffic capacity as the route weight.

Key words: Optimum Access Algorithm; Weight of Route; Traffic Capability; Accessibility