改進矩陣法尋優(yōu)法在交通仿真系統(tǒng)中的應(yīng)用

摘要：文章在矩陣尋優(yōu)法的基礎(chǔ)上加入了啟發(fā)信息要素，提出了一種改進的動態(tài)尋優(yōu)算法。文中給出了算法的基本過程與實現(xiàn)方法，并對啟發(fā)信息的合理性予以論述。最后以城市交通仿真系統(tǒng)為平臺，通過實驗給出了此算法與全動態(tài)Dijkstra算法的性能比較，分析結(jié)果證實了改進矩陣算法方法具有較高的速度，驗證了該方法的正確性和有效性。

關(guān)鍵詞：矩陣尋優(yōu)算法；城市交通仿真系統(tǒng)（CTS）；動態(tài)Dijkstra算法

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)29-0257-03

The Application of Modified Matrix Shortest-Path Algorithm in Traffic Simulation System

QIAN Wei-feng， WANG Jian

(CIMS Research Center，Tongji University，Shanghai 201804，China)

Abstract: Based on the matrix shortest-path algorithm and the instructive information， the author presented an improved dynamic shortest-path algorithm. In this article the fundamentals and realization of the algorithm were given and its rationality was discussed. Finally， the performance of Dijkstra algorithm and the algorithm that the author put forward were compared on the city traffic simulation system platform，the better speed are achieved using the improved dynamic shortest-path algorithm which valid the validity and effectiveness of the method in this paper.

Key words: Matrix Shortest-Path Algorithm; City Traffic Simulation System (CTS); Dynamic Dijkstra Algorithm

1 引言

路徑尋優(yōu)作為地理信息系統(tǒng)(GIS)網(wǎng)絡(luò)分析的重要組成部分，在交通、通信、網(wǎng)絡(luò)等各領(lǐng)域中起著重要的作用。國內(nèi)外眾多學(xué)者對各種路徑尋優(yōu)算法進行大量深入的研究和廣泛的應(yīng)用。其中1996年Cherkassky[1]在分析數(shù)據(jù)模型的基礎(chǔ)上對眾多歷史算法進行了性能評價，Zhuang Xiaodong[2]等將增強式學(xué)習(xí)方法運用于機器人路徑搜索，楊素瓊[3]將A*算法運用于地圖尋優(yōu)中。此類算法在理論分析中均歸結(jié)為單源路徑尋優(yōu)，雖然算法本身推廣至多源問題，但是在實際交通仿真系統(tǒng)中采用往往會受到運算時間，硬件性能等多因素的限制。如靜態(tài)Dijkstra算法對于單源問題的算法復(fù)雜度為O(n2+m)，其中n為結(jié)點數(shù)，m為邊數(shù)。在多結(jié)點多目標的動態(tài)尋優(yōu)問題中，此類尋優(yōu)算法均存在需要反復(fù)調(diào)用算法模塊，求解效率低等問題。

基于2007年上海市博項目-城市交通仿真系統(tǒng)(CTS)的車輛仿真模塊，本文提出了一種新型的路徑尋優(yōu)算法，在矩陣路徑尋優(yōu)算法[4]的基礎(chǔ)上，利用啟發(fā)信息進行優(yōu)化[5]限制更新結(jié)點的規(guī)模；提供了VS2005平臺下c#對算法的實現(xiàn)；與動態(tài)Dijkstra全結(jié)點更新法進行了實際運行效率的比較。

2 矩陣路徑尋優(yōu)

對于單源單目標尋找兩節(jié)點間最短路徑，可以簡化為一個給定權(quán)值的無向圖G。

我們將G的頂點集記為

定義Dij(m)為G中從頂點vi到vj的內(nèi)部頂點，只能取自Vm且Vm-1最多只取一次的最短路徑。遞推公式如下：

Dij(0)=lij，dij(m)=min{dij(m-1)，dim(m-1)+dmj(m-1) }，i≠j （4）

由此算法依次構(gòu)造D(1)， D(2)…D(n)，在D(n)中元素dij(n)即從vi到vj的最短路長。

在計算中同時構(gòu)造路徑矩陣R，設(shè)R(m)=(rij(m))，這里rij(m)是當(dāng)前vi到vj最短鏈的第一個中間點，算法開始于R(0)=(rij(0))，rij(0)=j，迭代到第m步，

算法原理簡述： 求vi和vj間最短路，從D(0)開始逐一檢查vi和vj經(jīng)過各中間點的情況，即時更新dij值，通過n次檢查后即取道所有結(jié)點，獲得的即為vi至vj的最短路徑。

3 動態(tài)矩陣路徑尋優(yōu)及優(yōu)化

在實際仿真系統(tǒng)中，我們采用道路的擁塞度作為道路的權(quán)值lij，其中l(wèi)ij=F(linkroad-length，avalible-ratio)，其中l(wèi)inkroad_length表示道路的實際長度，avalible_ratio與路網(wǎng)擁塞情況與跟駛特征參數(shù)相關(guān)。以n倍重繪時間為間隔輪詢各lij參數(shù)，當(dāng) 超過預(yù)定的閥值范圍時則更新L矩陣(實際系統(tǒng)中v取[0.7，1.3])。為了避免更新過程中系統(tǒng)涉及過多方向結(jié)點，我們在此利用啟發(fā)信息，僅對以當(dāng)前車輛位置點與目標點為焦點，與矩形道路區(qū)域的內(nèi)切橢圓的相似橢圓作為更新區(qū)域，如圖1所示，由于橢圓圓周上的點到兩焦點均等長，而路網(wǎng)圖基于真實道路長度，這與實際行駛過程的判斷是基本符合的，所以可以認為一種合理化的模型簡化。

4 算法步驟與實現(xiàn)

1) 計算t0時刻下所有道路權(quán)值lij (t0=0時認為lij僅與linkroad_length有關(guān))， 將所有在v區(qū)間外的結(jié)點置于集合 Collection temp_nodes中.

2) 構(gòu)造啟發(fā)信息通過ellipseFilter函數(shù)對temp_nodes中的點過濾，將結(jié)果存于Collection ud_note中

foreach(PointF node in temp_nodes){

float x = node.X; float y = node.Y;

//whether the node's in standard ellipse

bool in_ell = Math.Pow((Math.Pow(x， 2f) + Math.Pow(y， 2f))， 0.5f) > 2 * ecllipse_a;

}

3) 更新長度矩陣L，利用公式1-2構(gòu)造算法類matrix_fp，在此類中構(gòu)造dij(m) 的遞推方法，構(gòu)造D(0)~D(n)的n次迭代方法。以下片段為dij(m)的實現(xiàn)。

public class matrix_fp//construction method

{ ............

InitAllNotes(); //Initialize linkroads' info

transDate(point， al_linkroad_ratio， status); //class parm trans

parm_d[i，j，m] = Math.Min(parm_d[i，j，m-1]， parm_d[i，m，m-1] + parm_d[m，j，m-1]);

}

4) 由公式（5）求得路徑矩陣R， 對于不同的車輛分別從R從獲得i行j列的值。

此算法的關(guān)鍵在于構(gòu)造算法類matrix_fp的運用，實際系統(tǒng)的路徑搜索中，約70%的時間用于matrix_fp的構(gòu)造，我們對系統(tǒng)優(yōu)化核心問題也就是對matrix_fp的簡化。雖然不考慮啟發(fā)信息下矩陣算法的復(fù)雜度仍為O(n2+m)，但是由于使用了利用橢圓規(guī)則限制了更新點的數(shù)量，并根據(jù)硬件性能對更新閥值合理設(shè)置，對于大多數(shù)車輛在僅在3-5個輪詢間隔內(nèi)更新matrix_fp。在程序中我們通過在運算后及時將此類改為弱引用，避免過多更新類同時存在引起的大量內(nèi)存占用。

5 實驗結(jié)果對比

圖2為實際系統(tǒng)中上海南浦大橋區(qū)域的主干道路網(wǎng)圖。在圖2基礎(chǔ)上取結(jié)點與路徑信息并簡化為29結(jié)點，46條路徑的圖3。

取v=[0.7，1.3] (區(qū)間半寬度為0.3) 至[0.4，1.6]（區(qū)間半寬度為0.6）間的若干數(shù)據(jù)，分別運用在仿真軟件中較為普遍的Dijkstra算法與我們所提出的改進矩陣算法，在結(jié)構(gòu)封裝后于同一環(huán)境下進行性能對比。測試環(huán)境：CPU:奔騰4 2.4Ghz內(nèi)存：1G，顯卡：GeForce4 5600，系統(tǒng)剩余空間:10G以上，DirectX: 9.0c。

如圖4，5所示，在我們的實驗中，閥值v=[0.6，1.4]時，采用Dijkstra算法與改進矩陣算法對道路總體車流輛的影響較小，這種影響隨著區(qū)間的擴大而增加。即在硬件條件允許的情況下，我們可以適當(dāng)放棄FPS（每秒楨數(shù)），通過設(shè)計較窄的閥值區(qū)間來使仿真過程中的路徑選擇更接近Dijkstra的全動態(tài)更新，這可以讓車輛的路徑尋優(yōu)更接近于最佳；在實際交通仿真的運用過程中，我們更多情況下對采集率（或者數(shù)據(jù)輸入速率）有較高的要求，我們采用采用的v可以接近[0.7，1.3]，這時改進矩陣算法相比Dijkstra算法平均更新點數(shù)與平均更新路徑都大大減少，這也將直接提高仿真系統(tǒng)的運行效率。

6 結(jié)論

本文在現(xiàn)有路徑尋優(yōu)算法的基礎(chǔ)上，提出了基于矩陣尋優(yōu)與啟發(fā)信息的改進算法，并將其運用于城市交通仿真系統(tǒng)，結(jié)果表明算法在一定程度上解決了靜態(tài)算法缺乏準確性與全動態(tài)算法對硬件要求過高的矛盾。本算法以矩陣計算為基礎(chǔ)，更利于計算機運算，又通過啟發(fā)性信息進行更新結(jié)點數(shù)量的控制，在盡可能減少精確度損失的情況下提高了計算機運行的效率，這類方法在大規(guī)模道路網(wǎng)絡(luò)的仿真中將有著更廣闊的應(yīng)用前景。

參考文獻：

[1] Karypis G，Han E，Kumar V，et al.Hierarchical clustering using dynamic modeling[J].Computer，1999，23(8):68-75.

[2] Zhuang Xiaodong.Robot path planning in dynamic environment based on reinforcement learning[J].

[3] 楊素瓊，林碧.基于A*算法的地圖路徑搜索的實現(xiàn)[J].鐵路計算機應(yīng)用，2000(9):8-11.

[4] 劉纘武.應(yīng)用圖論[M].長沙:國防科技大學(xué)出版社，2006:70-74.

[5] 劉名龍.城市道路網(wǎng)最短路徑啟發(fā)算法研究[J].公路交通科技，2006，23(8):136-138.

[6] Resnick P.lacovou N，et al.GroupLens:An Open Architecture for Collaborative Filtering of Netnews[C].Proceeding of CSCW’94 Chapel Hill，NC，1994:175-186.

[7] Herlocker J L，Konstan J A，Borcher A，et al.An Algorithmic Framework for Performing Collaborative Filtering[C].Proceedings of ACM SIGIR’99，ACM press，1999:230-237.

[8] 蘇永云，晏克非.車輛導(dǎo)航系統(tǒng)的動態(tài)最優(yōu)路徑搜索方法研究[J].系統(tǒng)工程，2000，18(4);14-17.