基于剪枝策略的改進(jìn)TDCALT算法

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

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

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

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

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

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

1 問題定義

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

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

2 ITDCALT算法

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

2.1 TDCALT算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.2 在線搜索子算法

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

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

步驟如下：

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

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

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

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

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

2.2 TDCALT算法改進(jìn)

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

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

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

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

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

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

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

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

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

文獻(xiàn)［20］中對(duì)Reach的定義為：對(duì)于一條給定的最短路徑P1（S…v…D），v相對(duì)于P1的Reach值P1（Reach）＝Min（d（S…v），d（v…D））.設(shè)P1，…，Pn為路網(wǎng)中經(jīng)過v的所有的最短路，則v相對(duì)于整個(gè)路網(wǎng)的Reach值v.Reach＝Max（P1（Reach），P2（Reach），…，Pn（Reach））.如圖2所示，P1與P2為路網(wǎng)中經(jīng)過v的所有的最短路，P1＿Prefix為路徑P1上起點(diǎn)到v的前半段路徑，P1＿Suffix為路徑P1上v到終點(diǎn)的后半段路徑，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ù)處理階段計(jì)算每一個(gè)點(diǎn)相對(duì)整個(gè)路網(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é)點(diǎn).

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

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

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

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

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

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

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

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

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

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

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

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

據(jù)Reach定義，有

∵對(duì)于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àn)對(duì)比分析

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

3.1 算法評(píng)價(jià)指標(biāo)

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

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

3.2 算法測(cè)試與對(duì)比分析

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

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

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

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

表2 算法運(yùn)行時(shí)間表Tab.2 Running time of algorithms ms

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

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

（1）ITDCALT算法的性能最高，且最為穩(wěn)定.①由表2可知，ITDCALT算法的平均運(yùn)行時(shí)間最少，平均僅需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值相似，主要原因?yàn)镮TDCALT算法的搜索節(jié)點(diǎn)數(shù)較TDCALT算法少，導(dǎo)致其在指標(biāo)B上優(yōu)勢(shì)性不明顯.③ 表2，3中四分位數(shù)的分布表明ITDCALT算法的運(yùn)行時(shí)間與搜索空間比TDCALT和TDIJKSTRA算法更為穩(wěn)定.

4 結(jié)語(yǔ)

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