劉 昊

(南寧學院信息工程學院，廣西 南寧 530299)

0 引 言

城市交通網(wǎng)絡是城市中所有郵電與運輸網(wǎng)組成的交通網(wǎng)，也叫城市運輸網(wǎng)絡。設施、組織、需求和徑路網(wǎng)絡是城市交通網(wǎng)絡的主要組成[1]。交通節(jié)點與交通線路組成了設施網(wǎng)絡與徑路網(wǎng)絡，二者相結合即為組織網(wǎng)絡。城市交通網(wǎng)絡具有開放性和復雜性[2]，城市交通網(wǎng)絡路徑分析是城市交通網(wǎng)絡的關鍵，而城市交通網(wǎng)絡路徑分析重點則是最短路徑計算[3]，求解最短路徑被廣泛應用在城市交通學、地理信息學等各種領域中[4]。而迂回限制是指限制車輛迂回次數(shù)，或者避免迂回線路，因此在求解城市交通網(wǎng)絡最短路徑前，考慮實際交通網(wǎng)絡中迂回限制下的分布規(guī)律、時間、交通網(wǎng)絡容量等問題[5]，可確保城市交通網(wǎng)絡最短路徑優(yōu)算法更適用于實際。許多專家學者都對城市交通網(wǎng)絡最短路徑算法進行了研究，并取得了一定的研究成果。

文獻[6]提出了一種基于快速收斂牛頓算法的城市最短路徑分析。主要將城市道路交通網(wǎng)絡作為研究基礎，通過快速收斂牛頓(RCN)算法對城市道路網(wǎng)絡最短路徑進行規(guī)劃，根據(jù)均衡接近原則以及更新速度獲取優(yōu)化步長以及迭代方向，以幾種類型不同的道路交通網(wǎng)絡為例，通過RCN算法以及GP(梯度投影)算法對收斂速度進行驗證。但是該方法存在耗時較長的問題，難以應用到實際生活中去。文獻[7]提出了一種基于雙端隊列的交通網(wǎng)絡最短路徑Dijkstra算法。采用標號對改進Dijkstra算法的思路進行分析，從運行以及存儲結構出發(fā)，對該算法進行改進優(yōu)化的同時對空間以及時間復雜度進行深入研究，最后在大規(guī)模城市交通網(wǎng)絡中進行效率測試。但是采用Pallottino算法優(yōu)化城市交通網(wǎng)絡最短路徑過程中，未考慮實際路況迂回限制下的交通網(wǎng)絡流量，導致優(yōu)化結果精度低。文獻[8]提出了一種基于改進Floyd算法的城市交通網(wǎng)絡最短路徑規(guī)劃方法。分析了Floyd算法解決車道的設置問題的有效性，但是由于在設置過程中計算量大且效率較低，所以需要對Floyd算法進行改進。改進的算法在計算最短路徑過程中，不相連的節(jié)點或通過中間節(jié)點相連的路徑將在判斷是否應當舍棄后在進行計算，降低了計算復雜度，但是改進之后的算法依舊存在迭代次數(shù)較高的問題。文獻[9]提出了一種基于MapInfo的Dijkstra最短路徑算法研究。由于MapInfo平臺數(shù)據(jù)結構簡單，但是不具備空間數(shù)據(jù)拓撲關系，存在無法直接分析最優(yōu)路徑的問題，因此建立了路網(wǎng)模型與道路數(shù)據(jù)的預處理，使用MapBasic語言編程擴MapInfo的功能。在MapInfo平臺上成功地建立了空間數(shù)據(jù)的拓撲關系，實現(xiàn)基于Dijkstra算法的城市交通網(wǎng)絡最優(yōu)路徑分析。但是該方法存在耗時較長與魯棒性較低的問題。

為了解決上述算法迭代次數(shù)高，耗時長，計算復雜且精度較低的問題，本文采用優(yōu)化Dijkstra算法，其主要原因在于為了保持Dijkstra算法保持通用性強、程序設計簡單的優(yōu)點，克服該算法在進行路徑尋優(yōu)時效率較低與占用空間大，嚴重浪費計算機的資源的缺點，且與其他算法相比，該算法的應用最為普遍，優(yōu)化價值較大且算法優(yōu)化后通用性較強，因此對Dijkstra算法進行改進。本文先計算了迂回限制下城市交通網(wǎng)絡容量，以此為基礎，利用二叉樹方法改進Dijkstra算法，并對最短路徑進行搜索，實現(xiàn)迂回限制下城市交通網(wǎng)絡最短路徑運算，提高最短路徑運算效率和精度。

1 城市交通網(wǎng)絡最短路徑算法優(yōu)化

1.1 迂回限制下城市交通網(wǎng)絡容量計算

城市交通網(wǎng)絡在規(guī)定時間內大概通過車輛及人流的最大流量即城市交通網(wǎng)絡容量[10]，城市交通網(wǎng)絡需要劃分各個城市交通小區(qū)，所有城市交通小區(qū)起訖點對之間客流分布相加就是城市交通需求總量。

計算城市交通網(wǎng)絡容量需要先調查現(xiàn)狀起訖點并劃分城市交通小區(qū)。城市交通網(wǎng)絡雙向路段依據(jù)圖論可簡單認為是不同方向的兩條弧與將路段相連的端點；城市交通網(wǎng)絡單行道依據(jù)圖論可簡單認為是與道路網(wǎng)相連部位的點與一條單向弧。因此，有容量約束的點與弧組成了城市交通網(wǎng)絡。為使問題簡單化，用弧容量來代表交通網(wǎng)絡中的點容量，以交叉口容量情況針對點容量折減各路段容量，這時的弧容量為將交叉口點容量加入與折減后的新容量，因此城市交通網(wǎng)絡可以用弧容量表示為D=(V,C)。此公式內，V表示為城市交通網(wǎng)絡中節(jié)點集合，C表示為城市交通網(wǎng)絡中弧的集合。

設劃分城市交通小區(qū)后，起訖點分布如下：

(1)

設各起訖點對占總城市交通網(wǎng)絡分布量比例已知，城市交通網(wǎng)絡總容量依據(jù)增量加載方法求解步驟為：

(1)求解城市交通網(wǎng)絡路段零流阻抗與通行情況。尋找該交通網(wǎng)絡中距離最短的起訖點對并將其行駛時間計算出來。交通網(wǎng)絡中最短距離城市交通小區(qū)j點與城市交通小區(qū)s點間行駛時間用T(r,s)表示。

(2)城市交通網(wǎng)絡中各起訖點對間交通情況矩陣為：

(2)

設總出行城市交通分布增量用ΔQ(m)表示，ΔQ(m)×p=Δq(m)，則有：

(3)

使m=1。

(3)在城市交通網(wǎng)絡中分配交通量，分配次數(shù)為m。在城市交通網(wǎng)絡中利用交通分配方法分配Δq(m)，城市交通網(wǎng)絡中行駛時間阻抗被更新[11]。依據(jù)阻抗函數(shù)獲取城市交通網(wǎng)絡中各路徑行駛時間。當達到或超過通行能力路徑時，設定路徑行駛時間無窮大。

(4)研究各起訖點段最短路徑，同時求解最短路徑行駛時間T′(j,s)。若計算中起訖點對間無最短路徑時，說明兩點之間無路徑存在，因此無需繼續(xù)計算；城市交通網(wǎng)絡中最大迂回系數(shù)為：T′(j,s)≥δT(j,s)(δ>1)，城市交通網(wǎng)絡受迂回限制，因此此種情況下停止計算該起訖點間交通分布量，記錄停止計算的各起訖點對交通情況。

(5)當T′(j,s)<δT(j,s)時，證明該起訖點路徑行駛時間有限，此時按照步驟6繼續(xù)進行；否則停止計算，城市交通網(wǎng)絡容量為此時所有起訖點對間交通分布量相加[12-13]。

(6)將所有停止計算的起訖點對刪除，所有起訖點對間交通分布量相對比例在存在的最短路徑滿足T′(j,s)<δT(j,s)時保持不變，但交通分布比例矩陣p(m)內的元素值和維數(shù)會存在變化，因此使m=m+1，回到步驟2繼續(xù)運算。

以上計算城市交通容量過程中，考慮了最大迂回系數(shù)δ。

1.2 城市交通網(wǎng)絡最短路徑算法優(yōu)化

依據(jù)迂回限制下城市交通網(wǎng)絡總容量，構建城市交通網(wǎng)絡模型Q=R(V,E)。R為迂回限制下城市交通網(wǎng)絡總容量。V表示將節(jié)點綜合后形成的新節(jié)點集合；E為非負實數(shù)，表示相鄰節(jié)點間距。

E={δdab|dab=F(Y1,Y2,Y3,…)}

(4)

式中，Y1為道路間幾何距離即簡單距離因子；Y2為路面等級因子；Y3為擁擠程度因子。

利用阻抗值形容通行能力受人、車流量與路面等級作用而引起的變化，城市交通小區(qū)內擁擠程度與路段等級利用阻抗值大小來區(qū)分[14]。用阻抗值雖然不能表示出受影響的具體大小，但是可以互相進行比較，作為計算依據(jù)。

采用優(yōu)化Dijkstra最短路徑算法從城市交通網(wǎng)絡模型中道路起點到道路終點，利用二叉樹方法按其方向性進行搜索，直至搜索到最短路徑為止。其搜索流程如圖1所示。

圖1 二叉樹方法搜索流程

假設r(dj,pj)為城市交通網(wǎng)絡中各節(jié)點的標號，r表示起點和節(jié)點j間迂回限制容量，起點s與節(jié)點j最短路徑距離為dj，若兩點間無相連路徑，則其距離為無限大，pj為起點s與節(jié)點j最短路徑距離的前一節(jié)點。用Dijkstra算法獲取最短距離是基于頂點進行二叉樹循環(huán)，循環(huán)次數(shù)與節(jié)點數(shù)n相同，隨著循環(huán)的繼續(xù)形成了節(jié)點s為中心的樹，此樹隨著循環(huán)的繼續(xù)一步步向四周擴大，直到尋找到最短路徑計算結束。因該算法計算過于復雜，大部分分支對求最短路徑并無幫助，因此需要對此算法進行優(yōu)化[15]。

求城市交通網(wǎng)絡中隨機節(jié)點s與節(jié)點j的最短路徑dj，由各節(jié)點與各邊形成此路徑。若dj間各道路與節(jié)點s和節(jié)點j為同方向，則計算較容易，但是大部分情況，最短路徑的節(jié)點與邊通常不在一條線，因為起點為s，因此將dj簡化為從s至j與從j至s兩條最短路徑，計算過程如下：

(2)從節(jié)點s出發(fā)，找到節(jié)點s與節(jié)點j間直線距離夾角最小的邊，設A1為此邊端點，則有：

(5)

其中，和節(jié)點s相關連的節(jié)點共有D1個；

從節(jié)點j出發(fā)，找到節(jié)點j與節(jié)點s間直線距離夾角最小的邊，設B1為此邊端點，則有：

(6)

其中，和節(jié)點j相關連的節(jié)點共有D2個。

起始點為s時選擇點為A1，那么前點為A1。重復以上操作直至獲取起點是A1同時從A1至j距離最短的邊夾角最小。此時獲取的路徑鏈為該交通網(wǎng)絡中路徑最短解。若最終結果為兩條或多條，將其經過站點及阻抗值記錄，并選擇最為合適的路徑。

(3)將s、j作為根節(jié)點的直線段兩端夾角最小的邊加入二叉樹，利用二叉樹方法對其所有節(jié)點標記起來，直至與s或j點重合為止。為使計算簡便精準，利用廣度優(yōu)先方法遍歷該二叉樹，可大大減少節(jié)點遍歷數(shù)；對需要加入路徑隊列的節(jié)點實施判斷，若該點為終點，那么無需對該點進行計算，更新受該點影響的節(jié)點長度。利用以上優(yōu)化算法計算后，若最終結果大于1，通過對比最終計算出的最優(yōu)路徑阻抗值，選擇最合適的路徑作為最終結果。

2 實驗分析

為驗證本文算法的實用性，實驗以某城市交通路網(wǎng)為例，在MapInfo環(huán)境下對該城市地圖實施矢量化，將MapX在VB環(huán)境下進行二次開發(fā)，便于快速搜索該城市交通網(wǎng)絡最短路徑。實驗平臺的計算機配置為Core i3-7100，內存大小256 G，硬盤大小500 G。該交通網(wǎng)絡中含有節(jié)點數(shù)386個，路段共769條。在該交通網(wǎng)絡中隨機選取10個點，對比分析本文算法、文獻[7]算法、文獻[8]算法的最短路徑優(yōu)化結果，見表1。

表1 三種算法計算最短路徑結果

表1在十個節(jié)點間最短路徑計算結果，可以看出本文算法比文獻[7]算法和文獻[8]算法在每兩個節(jié)點間距離都明顯小于其它兩種方法，并且本文算法計算路徑時選擇的節(jié)點與路段均為最少，很大程度的縮短了交通路徑，說明了本文算法在城市交通網(wǎng)絡中計算最短路徑的有效性。原因是本文方法利用二叉樹方法按其方向性進行搜索，此樹隨著循環(huán)的繼續(xù)一步步向四周擴大，遍歷了所有有可能性的路徑，避免了路徑對比不全的問題。

三種方法在計算十個節(jié)點間最短路徑過程中迭代次數(shù)見圖2。

圖2 三種算法迭代次數(shù)對比

從圖2可以看出，本文算法在計算城市交通網(wǎng)絡最短路徑時迭代次數(shù)明顯低于其它兩種方法，在9次計算中，迭代次數(shù)均在20次左右，遠遠低于其他兩種方法。迭代次數(shù)的減少不僅使計算用時降低，而且避免了由于迭代次數(shù)過多造成的計算不準確，進一步驗證了本文算法的計算效率。

三種算法在城市交通網(wǎng)絡最短路徑計算用時結果見圖3。

圖3 三種算法計算用時對比

通過圖3三種方法計算城市交通網(wǎng)絡最短路徑計算用時可以看出，本文算法計算十個節(jié)點間最短距離用時在0.1s左右，明顯低于文獻[7]算法和文獻[8]算法。尤其是文獻[8]算法在計算1-2節(jié)點時，用時高達0.75 s，高于本文算法0.65 s，可以看出本文算法具有較高的計算效率。原因是在使用二叉樹搜索最短路徑時，利用廣度優(yōu)先方法遍歷該二叉樹，大大減少了節(jié)點遍歷數(shù)，減少了路徑計算時間。

在該實驗平臺中，依據(jù)實驗選用三種算法模擬實際出行，選擇參數(shù)相同的汽車依據(jù)三種算法按照時速50km/h進行仿真模擬，實驗考慮車輛與行人擁堵，交通紅綠燈等狀況。統(tǒng)計三種算法仿真用時，具體數(shù)據(jù)見表2。

表2 三種方法最短路徑仿真用時

從表2可以看出，本文算法在考慮了交通狀況下的十個節(jié)點間最短路徑仿真用時最短，本文算法中考慮了城市交通網(wǎng)絡迂回路徑的限制，使得交通路徑運行時間明顯縮短，增加了本文算法的實用性，驗證了本文算法在實際應用中的有效性。

為驗證本文算法對迂回限制下不同城市交通網(wǎng)絡中最短路徑求解的適用性，在本文實驗平臺中隨機產生具有10—100個節(jié)點的網(wǎng)絡拓撲，交通網(wǎng)絡中的節(jié)點與邊隨機選取[0,200]范圍內的整數(shù)。將本文算法與文獻[7]算法和文獻[8]算法循環(huán)200次對比仿真結果的準確率，仿真結果見圖4。

圖4 三種算法100個節(jié)點準確率對比

由圖4可以看出，文獻[7]算法在隨機產生100個節(jié)點計算最短路徑時準確率平均達到70%，而文獻[8]算法準確率平均達到了75%，本文算法在隨機產生100個節(jié)點計算最短路徑時準確率平均高達99%，本文算法準確率遠遠高于其他算法，說明了本文算法在節(jié)點數(shù)目大時，城市交通網(wǎng)絡情況復雜時，運算結果同樣準確。

表3為隨機產生100個節(jié)點計算最短路徑時三種方法計算用時。

表3 三種算法計算100個節(jié)點用時對比

表3可以看出，節(jié)點個數(shù)與計算用時成正比增長，本文算法計算大量節(jié)點時用時明顯少于文獻[7]算法和文獻[8]算法，本文算法在計算100個節(jié)點時，用時僅為0.37 s，而文獻[7]算法與文獻[8]算法用時達到了1.34 s與2.01 s，本文算法比其它兩種算法減少了0.97 s與1.64 s，驗證了本文算法具有較高的計算效率。

三種算法的魯棒性對比結果如圖5所示。

圖5 三種算法魯棒性對比

分析圖5可以看出，本文算法在計算100個節(jié)點最短路徑時魯棒性最好，平均在95%左右，并且本文算法魯棒性不受節(jié)點數(shù)量增大的影響，且變化較為穩(wěn)定，而文獻[7]算法和文獻[8]算法魯棒性隨著隨著節(jié)點數(shù)的增加而降低，且變化幅度較大，說明這兩種算法不穩(wěn)定，從魯棒性變化幅度方面驗證了本文算法在面對大量數(shù)據(jù)時穩(wěn)定性。原因是計算城市交通容量過程中，考慮了最大迂回系，以此為基礎構建的城市交通網(wǎng)絡模型使得在網(wǎng)絡過載或者受到攻擊的情況下，計算也可以較好的進行。

以上大量實驗可以看出，本文算法在計算某城市交通網(wǎng)絡最短路徑時，求解過程中搜索的節(jié)點與邊為三種方法中最少的，并且計算過程中迭代次數(shù)最少，計算用時少于另兩種方法，計算結果最為準確，可以精準的計算出迂回限制下該城市交通網(wǎng)絡最短路徑。為驗證本文算法操作大量節(jié)點時穩(wěn)定性，在實驗平臺隨機選取了100個節(jié)點通過三種方法進行運算，結果可知本文算法在計算100個道路節(jié)點時準確率高達99%，計算用時低至0.37 s，本文算法魯棒性最好，再次驗證了本文算法的精準性與實用性。

3 結 語

最短路徑計算是城市交通網(wǎng)絡中最基本以及最重要的應用。以往搜索交通網(wǎng)絡中最短路徑計算的是兩個節(jié)點之間的幾何距離最短路徑，該最短路徑應用在公路交通網(wǎng)絡中具有重要的意義，但是對于城市交通網(wǎng)絡，存在城市道路路面等級問題與車輛或行人擁擠程度問題，因此幾何距離最短路徑并不代表為最優(yōu)路徑，本文算法在計算最短路徑的前提下，考慮了道路迂回限制，增大了算法的實用性。經過大量實驗證明，本文算法計算路徑時選擇的節(jié)點與路段均為最少，很大程度的縮短了交通路徑，本文算法在計算時間、計算迭代次數(shù)、計算精準度以及魯棒性方面都優(yōu)于對比方法，實際應用價值高。在未來隨著信息技術的不斷提高，需要將最短路徑計算與導航技術有機結合，以提高最短路徑計算的綜合實用性，實現(xiàn)城市交通流的有序流動。