鐘慧玲，章 夢，石永強(qiáng)，蔡文學(xué)

（華南理工大學(xué)經(jīng)濟(jì)與貿(mào)易學(xué)院，廣東廣州510006）

智能交通系統(tǒng)（intelligent transportation system，ITS）是解決交通擁擠問題的有效工具，路徑規(guī)劃則是其中最重要的功能之一，即給定起點和終點后，求解出一條合理的路徑誘導(dǎo)車輛行駛.目前實現(xiàn)該功能的路徑規(guī)劃算法的基礎(chǔ)是最短路算法，已有許多學(xué)者提出［1－3］基于固定邊權(quán)的靜態(tài)最短路算法，該類型算法求解的結(jié)果為一條距離最短的路徑，而在現(xiàn)實應(yīng)用中，通常需要通行時間最短（最快）的路徑，求解該路徑需要考慮交通狀況對于通行時間的影響.受道路通行時間的不確定性和路網(wǎng)規(guī)模過大的雙重影響，該類算法求解路徑的過程效率還有待進(jìn)一步提升，因此極大地限制了其實際應(yīng)用（如在集中式路徑誘導(dǎo)系統(tǒng)中的應(yīng)用）.目前許多學(xué)者研究如何提高求解路徑的算法效率［4－6］，但還存在著算法搜索盲目性等局限，故本文以提高計算效率為目標(biāo)進(jìn)行該類最短路算法的研究.

根據(jù)刻畫道路通行時間的不同方式，考慮交通狀況的最短路算法研究可以分為兩類：一是將通行時間表達(dá)為時間依賴性函數(shù)的算法［4］，二是將通行時間表達(dá)為完全隨機(jī)數(shù)的算法［7］.由于后者的計算效率明顯低于前者，本文將基于前者進(jìn)行擴(kuò)展研究，即研究時間依賴性路網(wǎng)下的最短路算法.該類型的算法由Cooke［8］提出，后續(xù)研究主要從串行計算和并行計算兩個角度來提高計算效率.串行計算應(yīng)用不同加速策略提高其計算效率［9－10］：① 方向誘導(dǎo)策略［11］雖然能夠縮小搜索空間，但是其計算效率還不能滿足實際需求；② 雙向搜索策略［12］執(zhí)行雙向搜索過程，大部分情況下能夠提高計算效率，但是在最壞的情況下比單向搜索策略差，同時難以確定后向搜索的出發(fā)時刻；③ 壓縮圖策略［13］通過簡化路網(wǎng)有效提高了算法效率，但是其效率還有進(jìn)一步提升的空間；④ 路徑分解策略［14］能夠有效提升效率，但其求解的路徑可能不是最短路；⑤ 分區(qū)策略［15］能夠有效提高算法效率，但算法的預(yù)處理時間過長.并行計算依賴于具體的串行算法［16］，通過將串行計算并行化的方式提高計算效率，其計算效率與并行計算過程中使用的網(wǎng)絡(luò)分割方法、串行最短路算法以及終止檢測方法有較緊密的關(guān)系，是目前比較前沿的發(fā)展方向.

由于并行計算的基礎(chǔ)是串行最短路算法，因此本文將先進(jìn)行串行最短路算法的研究.針對串行計算單獨使用各項加速策略存在的缺陷，目前一些研究［4，17－18］將幾種不同的策略結(jié)合起來以進(jìn)一步提高算法效率，比較典型的是將方向誘導(dǎo)策略、雙向搜索策略和壓縮圖策略結(jié)合起來的TDCALT（time dependent core－based A＊landmarks triangle inequality）算法［4］，該算法分為兩個子算法：離線預(yù)處理子算法和在線搜索子算法.首先通過離線預(yù)處理子算法對時間依賴性路網(wǎng)進(jìn)行分層預(yù)處理以壓縮路網(wǎng)，同時根據(jù)文獻(xiàn)［19］進(jìn)行地標(biāo)點的選擇處理；其次通過在線搜索子算法在經(jīng)過預(yù)處理的路網(wǎng)上利用方向誘導(dǎo)策略和雙向搜索策略計算最短路.該算法的效率比其他算法的效率有很大的提高［4］，但其還存在著搜索盲目性等缺陷，仍有進(jìn)一步提升的空間.

本文以TDCALT算法為基礎(chǔ)，首先對TDCALT算法中的上限值進(jìn)行動態(tài)優(yōu)化，提高算法效率；其次針對其搜索盲目性的缺陷（即算法搜索了明顯不在最短路上的節(jié)點）通過引入應(yīng)用于靜態(tài)路網(wǎng)下最短路算法的剪枝策略［20］，將其改進(jìn)為適用于時間依賴性路網(wǎng)的剪枝策略來彌補(bǔ)該缺陷，進(jìn)一步提高算法效率；最后在廣州市路網(wǎng)上通過試驗對比分析本文提出的改進(jìn)TDCALT算法（improved TDCALT，ITDCALT），TDCALT算法和TDIJKSTRA（time－dependent DIJKSTRA）算法在各種算法評價指標(biāo)下的表現(xiàn).

1 問題定義

本文使用時間依賴性路網(wǎng)來表達(dá)路網(wǎng)信息和交通狀況信息，時間依賴性路網(wǎng)G的定義如下：式中：G表示時間依賴性路網(wǎng)；V表示道路節(jié)點集合；E表示路段集合，其元素為有序?qū)Α磝，y〉，x為路段的起點，y為路段的終點；L（x，y）是路段〈x，y〉的長度；TE是在時間區(qū)間［t0，t1］上定義的函數(shù)，Tx，y（t）是非負(fù)實數(shù)，表示t時刻在路段〈x，y〉上的通行時間.

對于給定的起點S∈V、終點D∈V、出發(fā)時刻T，如何在G上高效地求解出在T時刻出發(fā)，從S到D的通行時間最短的路徑即本文研究的主要問題.

2 ITDCALT算法

在求解時間依賴性路網(wǎng)的最短路算法中，TDCALT算法的效率比其他算法的效率有很大提高［4］，但是還存在著一定的缺陷，因此本文將以該算法為基礎(chǔ)進(jìn)行改進(jìn).

2.1 TDCALT算法描述

文獻(xiàn)［4］中提出的TDCALT算法分為兩個子算法：離線預(yù)處理子算法（該部分主要作用為初始化路網(wǎng)，只需執(zhí)行一次即可）和在線搜索子算法（該部分主要作用為計算最短路，需在每一次搜索請求中執(zhí)行一次）.其中離線預(yù)處理子算法應(yīng)用了壓縮圖策略和方向誘導(dǎo)策略，在線搜索子算法應(yīng)用了雙向搜索策略和方向誘導(dǎo)策略.以下簡要闡述兩個子算法的主要步驟，為方便描述，引入以下表述：

G（V，E）：原始的時間依賴性路網(wǎng)；

GC（VC，EC）：經(jīng)過壓縮圖策略處理之后的時間依賴性路網(wǎng)；

G（V，E）：下限值路網(wǎng)，即該路網(wǎng)中每一條路段E的通行時間都是G中該路段所有通行時間的最小值，記為len；

GC（VC，EC）：經(jīng)過壓縮圖策略處理之后的時間依賴性下限值路網(wǎng)，即該路網(wǎng)中每一條路段EC的通行時間都是GC中該路段所有通行時間的最小值；

GCA（VCA，ECA）：經(jīng)過壓縮圖策略和方向誘導(dǎo)策略處理之后的時間依賴性路網(wǎng)；

GCA（VCA，ECA）：經(jīng)過壓縮圖策略和方向誘導(dǎo)策略處理之后的時間依賴性下限值路網(wǎng)，即該路網(wǎng)中每一條路段ECA的通行時間都是GCA中該路段所有通行時間的最小值；

GF（VF，EF）：G和GCA合并之后的路網(wǎng)，其中VF＝V，EF＝E∪ECA.

2.1.1 離線預(yù)處理子算法

輸入：原始的時間依賴性路網(wǎng)G（V，E）.

輸出：經(jīng)過預(yù)處理的路網(wǎng)GCA（VCA，ECA）.

步驟：首先是基于壓縮圖策略的預(yù)處理子算法，其次是基于方向誘導(dǎo)策略的預(yù)處理子算法，分別如下：

（1）基于壓縮圖策略的預(yù)處理子算法

步驟1.1：對于路網(wǎng)G中的每一個節(jié)點v，如滿足被去除的標(biāo)準(zhǔn)（如果v節(jié)點的入邊數(shù)量為N，出邊數(shù)量為M，對于給定的參數(shù)C，若NM＞C（N＋M），即可去除v節(jié)點［4］，其中參數(shù)C∈（0，＋∞）.不同的參數(shù)C產(chǎn)生不同的預(yù)處理結(jié)果，進(jìn)而影響算法效率），則去除該點，同時生成虛擬邊連接該點相應(yīng)的前驅(qū)和后繼節(jié)點，轉(zhuǎn)入步驟1.2.

步驟1.2：對于每一條虛擬邊，如果其連接的兩個節(jié)點之間存在另一條比虛擬邊更短的路徑，則將虛擬邊去除.如此即形成路網(wǎng)GC.

（2）基于方向誘導(dǎo)策略的預(yù)處理子算法

步驟2.1：在GC中選取N個節(jié)點作為地標(biāo)點，轉(zhuǎn)入步驟2.2.

步驟2.2：計算GC中每一個地標(biāo)點到其他節(jié)點的通行時間和其他點到該地標(biāo)點的通行時間，將這些通行時間信息存放入GC中.如此即形成路網(wǎng)GCA.

2.1.2 在線搜索子算法

輸入：起點S，終點D，出發(fā)時刻T，路網(wǎng)GF，路網(wǎng)GCA.

輸出：T時刻出發(fā)，S和D之間的最短路徑P（S，D，T）及其通行時間d（S，D，T）.

步驟如下：

步驟3.1：在GF上使用TDIJKSTRA算法開始前向／后向搜索，搜索過的節(jié)點分別存入集合F／B.當(dāng)搜索到v∈VCA，不再從v節(jié)點擴(kuò)展搜索.當(dāng)B∩F≠?（情況一）或者前／后向的優(yōu)先級隊列都為空（情況二）時，轉(zhuǎn)入步驟3.2.

步驟3.2：若為情況一，在GF上以S為起點，使用TDIJKSTRA算法搜索，直到搜索到D即結(jié)束，輸出P（S，D，T）以及d（S，D，T）.若為情況二，則

步驟3.2.1：以F／B中的葉節(jié)點為前向／后向搜索的優(yōu)先級隊列初始集合，在GCA／GCA上開始使用方向誘導(dǎo)策略進(jìn)行搜索，且后向搜索的節(jié)點存入集合B.設(shè)雙向搜索在v1點相遇，記S…v1…D的通行時間為r，轉(zhuǎn)入步驟3.2.2.

步驟3.2.2：繼續(xù)雙向搜索，直到后向搜索中所有點的鍵值都超過Kr（K為給定的參數(shù)，其中參數(shù)K∈（0，1］，不同的參數(shù)K直接影響在線搜索子算法的效率以及結(jié)果路徑的通行時間），則轉(zhuǎn)入步驟3.2.3.

步驟3.2.3：繼續(xù)前向搜索，但只搜索B中的節(jié)點，直到搜索到D即終止.輸出P（S，D，T）以及d（S，D，T）.

2.2 TDCALT算法改進(jìn)

TDCALT算法雖然很好地結(jié)合了多種加速策略，但還存在一定的缺陷，本文分別對其改進(jìn).

2.2.1 r值的動態(tài)更新改進(jìn)

在線搜索子算法中，后向搜索的終止條件是其優(yōu)先級隊列中所有節(jié)點的鍵值全部超過Kr（步驟3.2.2），因此在保證r大于最短通行時間的前提下，r越小則后向搜索越快終止，算法的搜索空間越小，如圖1所示.當(dāng)r1減小為ri時，搜索空間減少的部分如深色部分所示.TDCALT算法中r被設(shè)置為雙向搜索第一次相遇時所找到路徑的通行時間值，如圖1的r1所示.在后續(xù)的最短路搜索過程中，可能會找到更小的r值，如圖1中的ri所示，但該縮小的r值信息在TDCALT算法中沒有被很好利用，導(dǎo)致算法搜索空間大，算法效率降低.

圖1 不同r值的搜索空間Fig.1 Search space of different values of r

對此，本文改進(jìn)為動態(tài)更新該r值.當(dāng)雙向搜索第一次相遇時，將r值設(shè)置為此時找到的可行路徑的通行時間，如圖1中的r1所示.在后續(xù)的雙向搜索過程中，若找到其他可行路徑的通行時間小于當(dāng)前的r值，則將該r值更新為當(dāng)前可行路徑的通行時間值，如圖1中的ri所示.如此處理既可保證r＞d（S，D，T），又可使r值不斷減小，由此能夠縮小搜索空間，提高算法效率.

2.2.2 剪枝策略的改進(jìn)與應(yīng)用

在線搜索子算法中，其搜索過程未考慮放棄搜索明顯不在最短路上的節(jié)點，從而導(dǎo)致了搜索的盲目性，搜索空間擴(kuò)大，算法效率降低.在靜態(tài)最短路算法中，可以使用剪枝策略來解決該問題.該策略在靜態(tài)最短路算法中能夠取得很好的效果，但是不能直接應(yīng)用到時間依賴性路網(wǎng)下的最短路算法中.本節(jié)將考慮改進(jìn)剪枝策略，將其引入到時間依賴性路網(wǎng)下的最短路算法中，彌補(bǔ)TDCALT算法的缺陷.

2.2.2.1 基于Reach的靜態(tài)剪枝策略

靜態(tài)最短路算法中使用剪枝策略需要兩個過程：離線預(yù)處理過程和在線搜索過程.在離線預(yù)處理過程中對每一節(jié)點生成一個標(biāo)識信息，以標(biāo)識該點是否在最短路上；在在線搜索過程中利用該標(biāo)識信息判斷節(jié)點是否在最短路上，以進(jìn)行剪枝，避免搜索不在最短路上的節(jié)點，以此減少搜索空間，提高算法效率.文獻(xiàn)［20］中所提出的應(yīng)用于靜態(tài)路網(wǎng)的基于Reach的剪枝策略為該類策略的典型代表.

文獻(xiàn)［20］中對Reach的定義為：對于一條給定的最短路徑P1（S…v…D），v相對于P1的Reach值P1（Reach）＝Min（d（S…v），d（v…D））.設(shè)P1，…，Pn為路網(wǎng)中經(jīng)過v的所有的最短路，則v相對于整個路網(wǎng)的Reach值v.Reach＝Max（P1（Reach），P2（Reach），…，Pn（Reach））.如圖2所示，P1與P2為路網(wǎng)中經(jīng)過v的所有的最短路，P1＿Prefix為路徑P1上起點到v的前半段路徑，P1＿Suffix為路徑P1上v到終點的后半段路徑，P2＿Prefix與P2＿Suffix與前述定義類似，則P1（Reach）＝Min（d（P1＿Prefix），d（P1＿Suffix））＝7，P2（Reach）＝Min（d（P2＿Prefix），d（P2＿Suffix））＝4，v.Reach＝Max（P1（Reach），P2（Reach））＝7.文獻(xiàn)［20］首先在離線預(yù)處理階段計算每一個點相對整個路網(wǎng)的Reach值.在求解S和D之間最短路的在線搜索過程中若式（1）成立

d（S…v）＞v.Reach且d（v…D）＞v.Reach（1）則可確定v不在S和D之間的最短路上，故放棄搜索v（即剪枝操作），以減少搜索空間，提高算法效率.如圖2所示，d（S…v）＝11＞v.Reach＝7且d（v…D）＝10＞v.Reach＝7，故放棄搜索v節(jié)點.

2.2.2.2 時間依賴性剪枝策略的改進(jìn)

基于Reach的剪枝策略的成功應(yīng)用必須滿足以下兩個關(guān)鍵條件：

條件一：離線預(yù)處理過程中，節(jié)點的Reach值必須是按照定義計算得到的值.

對于時間依賴性路網(wǎng)，由于其道路通行時間隨時間變化，按照定義計算Reach的過程中需要確定經(jīng)過v點的所有最短路，但是時間依賴性路網(wǎng)中不能確定上述最短路（如：P1在t1時刻是連接S和D的最短路，因為道路通行時間隨時間變化，所以P1在t2時刻可能不是連接S和D的最短路），因此將不能按照定義求解Reach值，即條件一不能滿足.

圖2 基于Reach的剪枝策略示意圖Fig.2 Example of Reach－based pruning strategy

條件二：在線搜索過程中，由于式（1）需要，必須能夠?qū)崟r獲得d（S…v）和d（v…D）.

在獲取d（v…D）的過程中，由于達(dá)到目的點D的時刻未知，因此d（v…D）也未知，故不能實時獲取d（v…D），即條件二不能滿足.

由于上述兩個關(guān)鍵條件不能直接得到滿足，因此基于Reach的剪枝策略將不能直接應(yīng)用于時間依賴性路網(wǎng)下的最短路算法中，本文將分別針對上述兩個缺陷進(jìn)行改進(jìn)，使其能夠應(yīng)用于時間依賴性路網(wǎng)下的最短路算法中，進(jìn)一步提高算法效率.

（1）滿足條件一的算法改進(jìn)

GCA為經(jīng)過2.1.1節(jié)離線預(yù)處理后的路網(wǎng)，其通行時間為len；

Pitj為路網(wǎng)GCA上時刻點tj經(jīng)過v節(jié)點的所有最短路（i＝1，…，n；j＝1，…，m）；

Pi為路網(wǎng)上經(jīng)過v點的所有最短路（i＝1，…，n）.

據(jù)Reach定義，有

∵對于j＝1，…，m都有上述等式成立

步驟如下：

（2）滿足條件二的算法改進(jìn)

TDCALT算法在線搜索過程中，雖然不能直接提供d（v…D）用于式（1）進(jìn)行剪枝操作，但其后向搜索過程能夠提供d（v…D）的下限值（d（v…D）），該值同樣可以應(yīng)用于式（1）進(jìn)行剪枝操作，結(jié)合滿足條件一的算法改進(jìn)，將式（1）擴(kuò)展為

3 試驗對比分析

本文從算法的效果和性能兩方面選取相應(yīng)的算法評價指標(biāo).為更好地展示ITDCALT算法的性能，本文以TDIJKSTRA算法作為基準(zhǔn)算法，并在廣州市路網(wǎng)上測試和對比分析了ITDCALT算法、TDCALT算法、TDIJKSTRA算法在不同指標(biāo)下的表現(xiàn).

3.1 算法評價指標(biāo)

本文考慮從算法效果和算法性能兩方面來評價算法.針對算法效果，本文以結(jié)果路徑的通行時間作為評價指標(biāo)，該指標(biāo)值越小表示越接近于最短通行時間，效果越好.針對算法性能，目前多以算法的運行時間作為評價指標(biāo)［4］，該指標(biāo)值越小表示計算速度越快，性能越好，但該指標(biāo)與計算機(jī)的性能相關(guān)程度較大.為更好地評價算法性能，本文以真實反映算法邏輯處理過程為原則，增加算法搜索空間作為評價指標(biāo).該指標(biāo)完全獨立于計算機(jī)性能，主要通過兩個子指標(biāo)來體現(xiàn)：① 搜索總節(jié)點數(shù)占路網(wǎng)總節(jié)點數(shù)比例，該指標(biāo)值越小表示搜索空間越小，性能越好，下文簡稱指標(biāo)A；② 結(jié)果路徑上節(jié)點總數(shù)占搜索總點數(shù)比例，該指標(biāo)值越大表示搜索空間越小，性能越好，下文簡稱指標(biāo)B.算法評價指標(biāo)體系如圖3所示.

圖3 算法評價指標(biāo)體系Fig.3 Evaluation index of algorithm

3.2 算法測試與對比分析

本文在廣州市路網(wǎng)上測試了ITDCALT算法、TDCALT算法、TDIJKSTRA算法的性能.該路網(wǎng)包含114 935條邊與55 357個節(jié)點，節(jié)點的平均出入邊數(shù)量為2.1，其中邊信息中包含其起點、終點以及邊的通行時間信息（該值為時間依賴性函數(shù)，不同時刻點道路的通行速度采用隨機(jī)生成，變化范圍為0～120km·h－1），點信息中包含了與之相連的出邊、入邊的信息.所有的算法均采用C＃（.NET 2.0）實現(xiàn)，算法的運行平臺為Windows Server 2008，2.26GHz處理器，4G內(nèi)存.

在廣州市路網(wǎng)上隨機(jī)選取了1 000對點對，每對點對分別模擬一個起點與終點，出發(fā)時刻統(tǒng)一為6點.分別使用ITDCALT算法、TDCALT算法、TDIJKSTRA算法，計算從6點出發(fā)，上述1 000個點對之間的最短路，并輸出算法運行時間，結(jié)果路徑的通行時間，搜索節(jié)點總數(shù)，結(jié)果路徑上的節(jié)點總數(shù)等信息.

參數(shù)C與參數(shù)K均對算法結(jié)果有影響，但確定參數(shù)C和K的理論最優(yōu)值是NP－HARD問題［2］，因此本文通過試驗確定參數(shù)C和K的經(jīng)驗最優(yōu)值.由參數(shù)C的性質(zhì)可知，其不宜過大或過小，參數(shù)C過大會導(dǎo)致路網(wǎng)壓縮率過小，參數(shù)C過小會導(dǎo)致路網(wǎng)壓縮率過大，路網(wǎng)壓縮率過大或過小都會降低算法效率.參數(shù)C的經(jīng)驗最優(yōu)值受路網(wǎng)中節(jié)點平均出入邊數(shù)量的影響，參照文獻(xiàn)［18］中測試參數(shù)C的做法，結(jié)合測試路網(wǎng)中節(jié)點的平均出入邊數(shù)量，本文測試了參數(shù)C從0.5到3.0，步長為0.5情況下的算法運行情況，獲得經(jīng)驗最優(yōu)的參數(shù)C為1.0.在經(jīng)驗最優(yōu)參數(shù)C為1.0的情況下，測試了參數(shù)K從0.1到1.0，步長為0.1的情況下的算法運行情況.如表1所示，ITDCALT算法和TDCALT算法的結(jié)果路徑平均通行時間與算法平均運行時間之間存在“背反”關(guān)系.隨著K不斷縮小，ITDCALT算法和TDCALT算法的結(jié)果路徑通行時間有所延長，但延長較少，ITDCALT算法平均延長0.07%，TDCALT算法平均延長0.28%，當(dāng)K＝1.0時，三種算法均輸出通行時間最短的路徑，同時算法運行時間也在不斷縮小.設(shè)置C＝1.0，K＝1.0，三種算法在算法運行時間和搜索空間上的性能表現(xiàn)如表2，3所示.

表1 不同參數(shù)K的算法運行時間與通行時間Tab.1 Running time and travel time of algorithm when Kis different

表2 算法運行時間表Tab.2 Running time of algorithms ms

表3 算法搜索空間Tab.3 Search space of algorithms %

通過上述試驗結(jié)果的分析，可以得到以下結(jié)論：

（1）ITDCALT算法的性能最高，且最為穩(wěn)定.①由表2可知，ITDCALT算法的平均運行時間最少，平均僅需19.28ms，僅為TDCALT算法的61.97%及TDIJKSTRA算法的8.39%.②由表3可知，ITDCALT算法的搜索空間最小.從指標(biāo)A的平均值上看，ITDCALT算法的平均值是最低的，僅為1.20%，而TDCALT算法的該指標(biāo)值為3.06%，約為ITDCALT算法的2.55倍，TDIJKSTRA算法的該指標(biāo)為49.72%，約為ITDCALT算法的41.43倍.從指標(biāo)B的平均值上看，ITDCALT算法的指標(biāo)值為28.35%，而TDCALT算法的該指標(biāo)的平均值為21.05%，TDIJKSTRA算法的該指標(biāo)平均值為0.82%.ITDCALT算法的指標(biāo)B值與TDCALT算法的指標(biāo)B值相似，主要原因為ITDCALT算法的搜索節(jié)點數(shù)較TDCALT算法少，導(dǎo)致其在指標(biāo)B上優(yōu)勢性不明顯.③ 表2，3中四分位數(shù)的分布表明ITDCALT算法的運行時間與搜索空間比TDCALT和TDIJKSTRA算法更為穩(wěn)定.

4 結(jié)語

本文針對大規(guī)模交通網(wǎng)絡(luò)中求解最短路的低效性與非實時性問題，構(gòu)造了一種融合交通狀況信息的高效最短路算法.該算法通過時間依賴性路網(wǎng)刻畫路網(wǎng)信息和交通狀況信息，通過改進(jìn)目前效率較高的TDCALT算法，結(jié)合改進(jìn)的剪枝策略來提高最短路算法的效率.試驗表明，本文所提出的算法在算法運行時間和搜索空間兩個指標(biāo)上都明顯優(yōu)于原算法.在智能交通系統(tǒng)的集中式路徑誘導(dǎo)系統(tǒng)中，該優(yōu)勢不僅能夠提高系統(tǒng)的響應(yīng)速度，同時能降低算法占用的計算機(jī)資源.該研究成果目前已得到了初步試用，取得了較好的效果.未來可以考慮：① 采用不同的時間依賴性函數(shù)來刻畫交通狀況信息，更好地擬合真實交通狀況；② 考慮本算法的并行計算研究，進(jìn)一步提高效率.

［1］ Sommer C.Approximate shortest path and distance queries in networks［D］.Tokyo：The University of Tokyo，2010.

［2］ Bauer R，Columbus T，Katz B，et al.Preprocessing speed－up techniques is hard［C］／／Algorithms and Complexity.Rome：Springer Verlag，2010：359－370.

［3］ Sanders P，Schultes D.Highway hierarchies hasten exact shortest path queries［C］／／13th European Symposium on Algorithms.Palma de Mallorca：Springer Verlag，2005：568－579.

［4］ Delling D，Nannicini G.Bidirectional core－based routing in dynamic time－dependent road networks［C］／／Proceedings of 19th International Symposium on Algorithms and Computation.Gold Coast：Springer Verlag，2008：813－824.

［5］ Sherali H D，Hobeika A G，Kangwalklai S，et al.Timedependent，label－constrained shortest path problems with applications［J］.Transportation Science，2003，37（3）：278.

［6］ Sherali H D，Jeenanunta C，Hobeika A G.The approachdependent，time－dependent，label－constrained shortest path problem［J］.Networks，2006，48（2）：56.

［7］ Demetrescu C，Italiano G F.Algorithmic techniques for maintaining shortest routes in dynamic networks［J］.Electronic Notes in Theoretical Computer Science，2007，171（1）：3.

［8］ Cooke K L.The shortest route through a network with timedependent internodal transit times［J］.Journal of Mathematical Analysis and Application，1966，14（3）：493.

［9］ Buriol L S，Resende M G C，Thorup M.Speeding up dynamic shortest－path algorithms［J］.Journal on Computing，2008，20（2）：191.

［10］ Hamacher H W，Ruzika S，Tjandra S A.Algorithms for timedependent bicriteria shortest path problems［J］.Discrete Optimization，2006，3（3）：238.

［11］ Nannicini G.Bidirectional A＊search for time dependent fast path［C］／／Proceedings of the 7th Workshop on Experimental Algorithms.New York：Springer Verlag，2008：334－346.

［12］ Wan－Yen L，Zwicker M.Bidirectional search for interactive motion synthesis［J］.Computer Graphics Forum，2010，29（2）：563.

［13］ Delling D，Nannicini G.Core routing on dynamic timedependent road network［J］.Journal on Computing，2012，24（2）：187.

［14］ Fua L，Sunb D，Rilett L R.Heuristic shortest path algorithms for transportation applications：state of the art［J］.Computers＆Operations Research，2006，33：3324.

［15］ Nannicini G，Baptiste P，Krob D，et al.Fast computation of point－point paths on time－dependent road networks［C］／／Proceedings of the 2nd International Conference on Combinatorial Optimization and Applications.Newfoundland：Springer Verlag，2008：225－234.

［16］ 倪安寧，雋志才，高林杰.交通網(wǎng)絡(luò)最短路徑并行算法研究綜述［J］.公路交通科技，2006，23（12）：128.

NI Anning，JUAN Zhicai，GAO Linjie.An overview of research on parallel shortest path algorithm in transportation network［J］.Journal of Highway and Transportation Research and Development，2006，23（12）：128.

［17］ Muhring R，Schilling H，Schutz B，et al.Partitioning graph to speed up DIJKSTRA’s algorithm［J］.Journal of Experimental Algorithmics，2007，11（28）：1.

［18］ Delling D.Time－dependent SHARC－routing［J］.Algorithmica，2011，60（1）：60.

［19］ Goldberg A V，Harrelson C.Computing the shortest path：A＊search meets graph theory［C］／／Proceedings of the Sixteenth Annual ACM－SIAM Symposium on Discrete Algorithms.Vancouver BC：Society for Industrial and Applied Mathematics，2005：156－165.

［20］ Gutman R.Reach－based routing：a new approach to shortest path algorithms optimized for road networks［C］／／Proceedings of 6th Workshop on Algorithm Engineering and Experiments.Berlin：Springer Verlag，2004：332－343.