最小時間路徑算法的改進及在路徑優化中的應用
2008-01-01 00:00:00李星毅翟曉峰施化吉
計算機應用研究 2008年6期
摘要：由于城市交通網絡中路徑行程時間是隨著時間的變化而變化的，求解最小時間路徑比較困難，為此提出把交通網絡抽象為時間依賴的網絡模型的解決方法。對時間依賴網絡模型和理論基礎進行分析，指出文獻［1］描述的最小時間路徑算法存在的不足，即不能正確記錄路徑；通過引入一個記錄路徑的數組來對此算法進行改進，改進后的算法不僅解決了原算法存在的問題，而且可以滿足n∶1的最短路徑搜索，擴展了原算法的應用范圍。最后用實驗驗證了改進算法的正確性和有效性。
關鍵詞：時間依賴網絡； 最短路徑算法； 路徑優化
中圖分類號：TP301文獻標志碼：A
文章編號：1001－3695(2008)06－1645－03
0引 言
最短路徑一直是交通規劃、計算機科學、GIS等領域研究的一個熱點問題。許多學者和專家就此問題提出了很多優秀的算法。文獻［2］對17種最短路徑算法進行了分析和評價。交通網絡中路徑優化多采用Dijkstra、Bellman－Ford－Moore算法、Floyd算法、啟發式搜索算法A*等一些經典算法的改進算法［3~5］。這些算法都假設交通網絡為權值固定的靜態網絡，是以路徑的空間距離最短作為優化目標的。在實際中，出行車輛從一個地方出發到達另一個地方主要考慮的是花費時間最少，而不是空間距離。為此，本文提出把交通網絡抽象為時間依賴的網絡模型，在該模型上求解的最小時間路徑即為花費時間最少的路徑。
網絡中弧段的權值是隨著時間的改變而改變的，弧段的權值與時間存在一定的映射關系，這樣的網絡稱之為時間依賴的網絡。在交通網絡中，根據路段行程時間的實測數據可以預測隨后若干時間段內該路段的行程時間，因此可以建立路段行程時間與時間的一個函數關系，即路段的行程時間是時間的一個函數。在此基礎上，交通網絡就抽象成了一個時間依賴的網絡模型。
本文討論了基于時間依賴的網絡模型及優化條件，指出文獻［1］存在的不能得到正確路徑的不足，給出了改進的最小時間路徑算法，并用一個實例網絡來驗證改進算法的正確性和有效性。
1時間依賴網絡模型
時間依賴網絡記做（V，E，T）。其中：V＝｛v1，v2，…，vn｝為有限節點集；E是有限弧集，E=V×V；T=（gij(t))是對于每一個弧（vi，vj）∈E在時間閉區間上定義的時間代價函數。其中：t∈［t0，tm］R；gij(t)是非負實數，表示從節點vi在t時刻出發到達節點vj的行走時間；［t0，tm］是時間閉區間；t0是網絡節點中的最早出發時間；tm是到達的最晚時刻，即在該時刻以后到達是沒有意義的。有時也可以假設gij(t)=∞，t＞tm。
如果時間是離散的，時間依賴網絡模型記做(V×S，E，T)。其中：S是將時間離散化后的時間間隔，S＝｛t0，t0+Δ，t0+2Δ，…，t0+(M-1)Δ｝；t0是所有網絡節點中出發最早的時間；Δ表示一個有效的采樣間隔（交通網絡中行程時間預測中通常取5 min，高峰時間計算中有時也取15 min）；M是t0到t0+(M-1)Δ有效時間段的數目。t∈S，gij(t)是非負實數，t+gij(t)總是有定義。對于t＞t0+(M-1)Δ時，定義為gij(t)=∞。V×S={（vi，tj)｜vi∈V，tj∈S}表示節點的狀態空間；有序對(vi，tj)表示節點的一個狀態，即節點vi在時刻tj的狀態情況。
2時間依賴網絡的理論基礎
傳統網絡中最短路徑求解的理論基礎與在時間依賴網絡中是不同的。本文中假設網絡中的弧為非負的，在傳統的網絡中，定理1是成立的。
定理1網絡中最短路徑的子路徑也是最短路徑。
定理1是著名的Dijkstra和一些標號設置算法的理論基礎。時間依賴網絡中存在不遵循上面定理的情況，下面給出一個上面定理不成立的例子，如圖1所示。
圖1的網絡中，節點a在到節點d的最小時間路徑為（a，b，c，d），用時為20。節點a到c的最小時間路徑為（a，c），用時為5，顯然該最短路徑的子路徑（a，b，c）不是一條最短路徑。可見圖1的網絡不遵循上述定理1。
時間依賴的網絡可分為FIFO（first in first out）網絡和非FIFO網絡兩種。下面給出定義。
定義若gij(t)連續，處處可微并且t，gij(t)＜Δt+gij(t+Δt），則稱弧（vi，vj）為FIFO弧。對于時間離散的網絡，若對于任何(vi，vj)∈E，s+gij(s)＜t+gij(t)，s，s＜t且t∈S，則稱弧（vi，vj）為FIFO弧；不具這種性質的弧稱為非FIFO弧。如果網絡中所有的弧都是FIFO弧，那么該網絡就是FIFO網絡；包含一條或一條以上的非FIFO弧的網絡稱為非FIFO網絡。
既適合于FIFO網絡，又適合非FIFO網絡的優化條件如下：
定理2［1］vi∈V，t∈S，設fi(t)表示從節點vi在時間t出發到達目的節點vN的時間，則fi(t)表示從節點vi在時間t出發到達目的節點vN的最小時間的充分必要條件是：對于所有的弧(vi，vj)∈E， fi(t)≤gij(t)+fi(t+gij(t))。
3時間依賴網絡最小時間路徑算法
3．1文獻［1］算法存在的問題
將文獻［1］給出的既適合于FIFO網絡又適合非FIFO網絡的SPTDN算法應用于實例網絡，發現有些情況下SPTDN算法得不到正確的結果，如圖2所示。
圖2為一時間依賴網絡，網絡中時間間隔Δ=10，S＝｛0，10，20，30，40｝。guv=10，20，30，40，40表示guv(0)=10，guv(10)=20，guv(20)=30，guv(30)=40，guv(40)=40。
對圖2的網絡用文獻［1］給出的SPTDN算法進行計算。節點a為起點，0時刻為出發時刻，節點d為終點，得到最小行程時間為fa(0)=30，最小時間路徑為（a，b，c，d）。顯然結果中的最小時間路徑是不正確的，正確路徑應該為（a，c，d）。為了找出錯誤的原因，對SPTDN算法的計算過程進行分析。
算法中用于記錄路徑的語句為succ(i):= j（節點i的后續節點為j）。設List中節點的計算過程為（d，c，a，b，a）。算法開始執行，當計算到節點c時，a的后續節點記錄為c，即succ(a):=c；繼續執行，當計算到List中節點b時有，t＝0時succ(a):=c，當t＝10時succ(a):=b發生錯誤。這里產生錯誤的原因是節點a在t＝0和t＝10到達終點d的路徑不一樣。為了解決這一問題，在記錄路徑時引入一個時間t，用i→next[t]=j來記錄路徑。下面給出改進后的算法實現及實驗驗證。
3．2時間依賴網絡的存儲結構
首先給出時間依賴網絡的存儲結構。時間依賴的網絡比傳統網絡需要更多的存儲空間。對于龐大的網絡，存儲結構的設計顯得更加重要，好的存儲結構的設計不僅可以降低算法的空間復雜度，也可以降低算法的時間復雜度。在交通領域內，采用鄰接表數據結構存儲網絡拓撲數據，關聯節點間查詢，時間復雜度僅為O（e/n)［7］。本文基于逆鄰接類型給出一種適用于時間依賴網絡的存儲結構，其C語言結構定義如下：
typedef struct SEdge{//弧的存儲結構
int sqen; //弧段序號
int nodeStartid; //弧尾序號
int nodeEndid; //弧頭序號
int weight[M]; //權值
}sedge[ENUM];
typedef struct SAdj{//鄰接點結構
int adjEsqen; //弧段序號
struct SAdj *psadj; //索引
}sadj;
typedef struct SVNode{//節點存儲結構
int sqen; //節點序號
char nodeid[11]; //節點ID
int adjnum; //鄰接點數目
SAdj *pFirstsdj; //鄰接點索引
}svnode[VNUM];
typedef struct SResult{//存放結果
float fv[M]; //最小時間
int nextNodesqen[M]; //后續節點，用來記錄路徑
}sresult[VNUM];
該網絡的逆鄰接表如圖3所示。
3．3最小時間路徑改進算法的實現
從源點vs到終點vN的最小時間路徑求解過程如下：
a）初始化。對于所有t∈S，fN(t)=0；其他所有節點fi(t)=∞。如果t+gij(t)＞t0+(M-1)Δ，則gij(t)=∞。建一個列表List將vN插入列表。
b）取出List中的首個節點為當前節點vj，并把該節點從List中刪除。對于每一個節點vi∈(E-1(j)-{vN})，在每一個時間t，條件fi(t)＞gij(t)+fj(t+gij(t))是否成立，不成立則跳到d）。
c）fi(t)=gij(t)+fj(t+gij(t))；i→next[t]=j；若vi不在List中，則把vj插入List。
d）判斷List是否為空，若為空算法結束。若不空跳到b）繼續執行。
以下為算法的C語言代碼：
for(int i=0; i for(int t=0; t sresult[i]．fv[t] = MAX; //最大值 }for(int t=0; t sresult[VNUM-1]．fv[t]=0; sresult[VNUM-1]．nextNodesqen[t]=4; } SList *slist=new SList[LISTNUM]; for(int j=0; j slist[j]．pnext=slist[j+1]; slist[j]．nodesqen=NODESQEN; } //算法的主題代碼部分 while(first－>nodesqen!=NODESQEN) { crusqen=first－>nodesqen-1; adjnum=svnode[crusqen]．adjnum ; padj=svnode[crusqen]．pFirstsdj; while(adjnum>0) { flag=1; h=padj－>adjEsqen-1; g=sedge[h]．nodeStartid-1; for(int i=0; i<10*M; i+=10){ k=i/10; f=k + sedge[h]．weight[k]/10; if(f<=M-1){ if(sedge[h]．weight[k]+sresult[crusqen]．fv[k] < sresult[g]．fv[k]){ sresult[g]．fv[k]=sedge[h]．weight[k]+sresult[crusqen]．fv[k]; sresult[g]．nextNodesqen[k] = crusqen + 1; plist_one=first－>pnext; while(plist_one－>nodesqen!=NODESQE){ if(plist_one－>nodesqen==g+1) flag=true; plist_one=plist_one－>pnext; } if(flag==1) plist_one－>nodesqen=g+1; } } } adjnum--; padj=padj－>psadj; } first=first－>pnext; } 設網絡中節點數為n，弧段數為m，時間段數目為M，C是所有弧中的最大權值。由于一條路徑中最多包含n-1條弧段，每個節點的fi(t)更新次數最大為nC，算法至多nC次減少每個節點的fi(t)（因為每次減少的數量至少為一個單位）。在等價的時間依賴網絡中，節點數為n×M，弧段數為m×N，因此每個節點最多更新nMC次。對網絡中所有節點掃描的最大次數為∑i∈V（nMC)｜E-1（i)｜，所以算法的最壞時間復雜度為O(nmM2C)。在交通網絡中，M和C都是常數，節點的逆鄰接點數目一般也比較小（道路網中一般不超過４），因此總的時間復雜度為O(n2)。 4實驗及應用 表1列出了對圖2網絡用上述算法進行計算得到的結果。算法結束后得到的最小時間為fa(0)，值為30；最小用時路徑為（a，c，d），結果正確。 算法不僅可以得到源點到終點1∶1的最小時間路徑，同時可以得到網絡中所有節點在不同時刻出發到達終點ｎ∶1的最小時間路徑。改進后的最小時間路徑算法有了更加廣泛的適用范圍。例如，當城市實時導航系統給出的最小行程時間路徑中某路段出現突發事件而被迫改變行進路線時，只要對當前位置進行相鄰次數的計算即可確定新的最小時間路徑，極大地減少了路徑搜索的次數。這樣可以減少服務器的壓力，這在城市實時導航系統中非常有用。改進后的最小時間路徑算法更具實際應用價值。 改進后的最小時間路徑算法已經成功地應用于某市交警局中心系統中最短路徑的搜索。該系統中以車牌自動識別系統的識別數據為源數據，通過相鄰監測點間的識別數據比對來得到實測路段行程時間；用指數平滑法預測路段在未來若干個時間段內的行程時間。把行程時間作為時間段的一個函數，城市交通網絡就抽象成了一個時間依賴的網絡。 5結束語 時間依賴網絡模型比傳統的網絡模型有更加廣泛的應用背景，以路段的行程時間為權值的城市道路交通網絡是一種典型的時間依賴的網絡。最小時間路徑算法在智能交通系統（ITS）的核心部分——路徑誘導系統中有很好的應用前景。本文給出的最小時間路徑算法的改進算法不僅可以有效地求解1∶1的單源點最短路徑問題，而且可以求解n ∶1的多源點最短路徑問題，擴展了最小時間路徑算法的應用范圍。 參考文獻： ［1］譚國真，高文．時間依賴的網絡中最小時間路徑算法[J]．計算機學報，2002，25（2）：165－172. ［2］CHERKASSKY B V，GOLDBERG A V，RADZIK T．Shortest paths algorithms：theory and experimental evaluation[J].Mathematical Programming，1996，73（2）：129－174. ［3］王峰，游志勝，曼麗春，等. Dijkstra及基于Dijkstra的前N條最短路徑算法在智能交通系統中的應用［J］．計算機應用研究，2006，23（9）：203－205. ［4］謝仕義，徐兵．基于ITS的加速最短路徑搜索算法研究［J］．計算機工程與應用，2006，42（16）：212－215. ［5］吳必軍，李利新，雷小平，等. 基于城市道路數據庫的最短路徑搜索[J].西南交通大學學報，2003，38（1）：80－83. ［6］陸峰．最短路徑算法：分類體系與研究進展[J]．測繪學報，2001，30（3）：269－275. 注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
