迂回限制下城市交通網(wǎng)絡(luò)最短路徑算法優(yōu)化設(shè)計(jì)

劉 昊

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

0 引 言

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

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

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

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

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

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

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

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

(1)

設(shè)各起訖點(diǎn)對占總城市交通網(wǎng)絡(luò)分布量比例已知，城市交通網(wǎng)絡(luò)總?cè)萘恳罁?jù)增量加載方法求解步驟為：

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

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

(2)

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

(3)

使m=1。

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

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

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

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

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

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

依據(jù)迂回限制下城市交通網(wǎng)絡(luò)總?cè)萘浚瑯?gòu)建城市交通網(wǎng)絡(luò)模型Q=R(V,E)。R為迂回限制下城市交通網(wǎng)絡(luò)總?cè)萘俊表示將節(jié)點(diǎn)綜合后形成的新節(jié)點(diǎn)集合；E為非負(fù)實(shí)數(shù)，表示相鄰節(jié)點(diǎn)間距。

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

(4)

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

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

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

圖1 二叉樹方法搜索流程

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

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

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

(5)

其中，和節(jié)點(diǎn)s相關(guān)連的節(jié)點(diǎn)共有D1個(gè)；

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

(6)

其中，和節(jié)點(diǎn)j相關(guān)連的節(jié)點(diǎn)共有D2個(gè)。

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

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

2 實(shí)驗(yàn)分析

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

表1 三種算法計(jì)算最短路徑結(jié)果

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

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

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

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

三種算法在城市交通網(wǎng)絡(luò)最短路徑計(jì)算用時(shí)結(jié)果見圖3。

圖3 三種算法計(jì)算用時(shí)對比

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

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

表2 三種方法最短路徑仿真用時(shí)

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

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

圖4 三種算法100個(gè)節(jié)點(diǎn)準(zhǔn)確率對比

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

表3為隨機(jī)產(chǎn)生100個(gè)節(jié)點(diǎn)計(jì)算最短路徑時(shí)三種方法計(jì)算用時(shí)。

表3 三種算法計(jì)算100個(gè)節(jié)點(diǎn)用時(shí)對比

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

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

圖5 三種算法魯棒性對比

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

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

3 結(jié) 語

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