動態交通網絡中最優路徑查找算法

摘 要：在真實交通網絡中，可能出現某高速公路在某一時刻內通過的車輛過多，從而改變了該時刻道路的即時速度，這就需要對道路的交通流量進行監控。針對這一問題，通過建立交通網絡的速度模式庫，根據道路可達速度的變化更新速度模式。基于A算法與速度模式庫，提出針對動態交通網絡的最短路徑查詢算法。采用真實數據集對算法進行測試，結果表明，應用該方法能夠有效地解決在速度模式發生變化的情況下最優路徑的查找，使交通網絡中的最優路徑查詢更為準確有效。

關鍵詞：最優路徑；速度模式；道路網絡；A算法

中圖分類號：TP311.13文獻標志碼：A

文章編號：1001-3695(2009)06-2066-04

doi:10.3969/j.issn.1001-3695.2009.06.020

Shortest path algorithm under dynamic road network

SONG Xiao-yu，YU Lan-yang，SUN Huan-liang

(Faculty of Information Control Engineering， Shenyang Jianzhu University， Shenyang 110168， China)Abstract:Since the speed of road changes with the variation of traffic， it is necessary to monitor the flow of traffic.This paper established the speed model database to update the speed model of each road. Based on A algorithm and speed model database，proposed a shortest path algorithm under dynamic road network. The experiments on real datasets show that this method can be used to find the shortest path in dynamic road network， and it makes the shortest path queries more efficiently and more accurately.

Key words:shortest path; speed pattern; road network; A algorithm

人們出行時，從起點到出行者的目的地，往往會有多條不同的道路，一般情況下，人們更愿意選擇一條能夠快速到達的路徑。應用車輛導航系統可以解決這樣的問題。車輛導航系統中的路徑分析從本質上來說屬于圖論中的最短路徑問題。對于求解最短路徑問題的方法主要有Dijkstra算法^[1，2]，A算法^[3]等。

用以上這些方法盡管可以解決兩點間的路徑問題，但在真實的交通網絡上，同一條道路在不同的時間段內具有不同的速度。已有的路徑查詢方法大多只考慮了如何查找最短的路徑而沒有考慮速度因素的影響，或者沒有考慮到查詢過程中速度的變化^[4]。這樣道路的查詢處理不夠全面，也沒有反映道路交通的真實狀況。文獻[5]提出用速度模式的概念來解決這些問題，但由于路況信息的變化，如某一些道路在一段時間內過于擁擠，這樣初始的速度模式發生變化，若不進行處理，將使最優路徑查詢的準確性下降。

本文對查詢過程中道路的速度模式發生改變的情況進行處理。利用已有的速度模式建立一個速度模式庫，該庫將道路的速度模式按照時間與道路的等級進行存儲，具體表示為〈edge_class，t_start，t_end，SPD〉。其中：edge_class為道路等級；〈t_start，t_end〉表示時間間隔；SPD表示一系列的速度模式。在查詢過程中，通過判斷交通網絡中每條道路所被調用的次數是否超過給定的閾值來決定是否要對道路的速度模式進行更新處理，通過確定的速度模式來獲得當前時刻道路所具有的實時速度。路徑的搜索利用了A算法的思想，利用所確定的速度模式進行最優路徑的查找。該方法使路徑的查詢更加實時有效，滿足實際應用的需求。

1 問題描述及相關方法

1.1 問題描述

定義1 交通網絡。用G(V，E)來表示。V是一系列的頂點，代表道路上的交叉路口；E是一系列的邊，代表兩點間的一段道路^[6]。

定義2 最優路徑查找。給定一個交通網絡G(V，E)，速度模式S，一個查詢(包括起始點s和終點e)，計算一條從s點到達e點所用時間最少的路徑。

1.2 速度模式

為了更加充分地考慮到在道路查詢過程中一些因素對道路選擇的影響，一些文章提出了速度模式的概念。速度模式的定義為一個元組〈edge_id，t_start，t_end，D〉。其中:edge_id為該邊的ID號；〈t_start，t_end〉表示一段時間間隔；D表示在該時間間隔內影響通過這條道路速度的各種因素，如天氣、汽車的類型等。

速度模式描述了在不同條件下道路的速度。表1表示在交通網絡中某一條道路的速度模式。實際中有很多影響道路速度的因素，在本例中，列出了影響道路速度的三個因素，即時間、天氣、車輛類型。

1.3 交通網絡劃分

為了更好地定義邊的速度模式以及加快路徑的查詢速度，Gonzalez等人^[7]提出了一種有效的交通網絡劃分方法。該方法將整個交通網絡G(V，E)按照邊的等級不同，對整個區域進行分層。利用區域劃分，可以用區域樹對交通網絡中的點進行索引^[8]。首先根據所給定的邊的等級為交通網絡中的點劃分等級，點劃分等級的原則是取與該點連接的所有邊中等級最大的邊的等級作為該點的等級。根據點與邊的等級對區域進行劃分。具體劃分過程如下：

首先取出一點指定一區域號，并按照一定規則將所有與其相關聯的點加入，分配相同區域號；再取出其他點，按照相同方法進行分配。當每一個點都有區域號時分配結束，把具有相同區域號的點存放在一起，通過點所屬的區域號就可以建立區域層次樹。

區域層次樹如圖1所示。通過區域樹的建立，可以減少查詢過程中點的遍歷。例如要在1:7:2的區域中選取一點作為起點，在1:3:2中找一點為終點。通過三級道路在1：7：2的區域中不斷擴展查找，直到找到二級道路，通過二級道路進入1:7區域，再通過一級道路進入1區域，而后用降序通過一級道路進入1:3區域，再通過二級道路進入1:3:2區域。

1.4 A算法

傳統的Dijkstra最短路徑算法由于計算量十分龐大，必須尋求高效的路徑規劃算法。啟發式搜索由于在路徑的規劃中引入了啟發信息，使得在搜索過程中能夠優先考慮更有希望的頂點。這無疑有助于減小算法的搜索空間，從而提高搜索效率。A算法是目前廣為流行的啟發式搜索算法。所謂啟發式搜索，就是利用一個估價函數來評估每一次的決策價值，決定先嘗試哪一種方案，這樣可以極大地優化搜索的速度。A算法核心的部分就在于其估值函數的設計上。f(n)=h(n)+g(n)。其中f(n)是每個可能探測點的估值。它由兩部分組成：一部分為g(n)，它表示為從起始搜索點到當前點的代價；另一部分為h(n)，表示當前點到目標點的估值。

A算法搜索路徑的做法如圖2所示（起始位置為a，目標位置為p，字母后面的數表示節點的估計值）。

搜索過程中設置兩個表，即OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。算法中有一步是根據估價函數重排OPEN表。這樣循環中的每一步只考慮OPEN表中狀態最好的節點。具體搜索過程如下：

a）初始狀態

b）估算a5，取得搜索到的子節點，并放入OPEN表中

c）估算b4，取得搜索到的子節點，并放入OPEN表中

OPEN=[c4，e5，f6，d6];

CLOSED=[b4，a5];

d）估算c4；取得搜索到的子節點，并放入OPEN表中

OPEN=[h3，g4，e5，f6，d6];

CLOSED=[c4，b4，a5];

e）估算h3，取得搜索到的子節點，并放入OPEN表中

OPEN=[o2，p3，g4，e5，f6，d6];

CLOSED=[h3，c4，b4，a5];

f）估算o2，取得搜索到的子節點，并放入OPEN表中

OPEN=[p3， g4， e5， f6， d6];

CLOSED=[o2， h3， c4， b4， a5];

g）估算p3，已得到解。

2 動態速度模式下路徑查詢算法

本文在A算法的基礎上進行改進，加入了速度模式的概念，并且為交通網絡中邊的元組添加了一個新的限定參數X，用于控制速度模式的變化。邊的元組具體表示為〈edge_id，start_x，start_y，end_x，end_y，X〉， edge_id為邊的ID號；start_x，start_y為起始點的坐標，end_x，end_y為終止點的坐標；X表示該邊被調用的次數。當X超出某一給定的數值Cn時，邊的速度模式要重新選取。選取方法表示如下： 

V(t)=SP1 X≤Cn

SP2 X＞Cn（1）

對于速度模式，按照邊的等級進行存儲，形成速度模式，如表2所示。在查詢路徑的過程中對速度模式發生變化的情況進行處理。其核心思想是：通過對已知的速度模式進行歸類存儲，建立速度模式庫。從查詢的起點開始判斷出發時刻的速度模式，在查詢過程中，通過X的值來判斷當前所查詢的邊的速度模式是否需要更新，并每間隔一段時間對X進行監控。

2.1 算法執行過程

以圖3為例，假設汽車從A點出發，終點為M，出發的時刻記為t，每隔一段時間要對速度模式是否需要更新進行判斷，這里時間間隔設為tx，并且已對幾種不同的速度模式進行了存儲。

查找從A到M的最優路徑需完成以下幾個步驟：

a)首先建立速度模式庫，將已知的速度模式存入動態數組中，按照時間先后順序進行排序。取得汽車在A點的出發時間，根據出發時間從速度模式SP1中取得對應的初始速度。

b)從A點開始查找，首先找到所有與A點相連的點，這里為B、C兩點。將AB邊與AC邊的X值分別加1。以B點為例，假設在速度模式為SP1的情況下，從A到達B所用的具體時間為t1，計算當前時間tc。根據當前時間選取該時刻道路的速度。當前時間為出發時間與行程所用時間之和。利用式（1）來判斷在通過AB邊的過程中是否發生速度模式的改變。如果當前的速度模式沒有發生改變，保留從A到B所用時間t1，否則利用新的速度模式重新計算從A到B所用時間，用同樣的方法取得A點到C點所用時間。分別估算從B、C兩點到達路徑的終點所有的最短時間，這里通過兩點間的直線距離除以行駛最大速度來計算。將兩點到A點所用的具體時間與兩點到終點所用的時間相加，選擇值較小的一個，并將該點作為下一次擴展的起始點。同時，將所選的邊加入到結果集中。查詢過程中，每間隔一段時間td就要對當前道路的X進行監控，以確定新的實時速度。

c)假設把B點作為新的擴展點，與B點相連的點有C、D、N，由于C點再次被加入，這樣從A到達C有兩條路徑，即ABC與AC，需要重新計算A點到C點所用時間并選取所用時間最小的值。之前沒有加入過的點通過步驟b)來進行處理。這樣，每次獲得一個新的擴展節點來不斷地查找，直到查找到路徑的終點為止。按照一定的次序從結果集中提取最優路徑。同時更新在結果集中沒有被選取的邊的X值。

2.2 算法描述

為了便于理解，表3中給出了算法中的符號及意義的對應關系。

動態速度模式下，路徑查詢算法如下所示。

輸入：交通網絡G(V，E)，路徑的起始點s和終點e，出發的時間t

輸出：a series of edges//最優路徑

執行SpeedPat(t);

EnClose_List(tmfpoint);

while (getpoint !=1)

FindNeighbour(tmfpoint);

while (heap.Las_Pos !=NULL)

tmpoint=heap.Container.GetAt(0);

if(tmpoint->inopenlist !=true);

CalculateValue(tmfpoint，tmpoint，epoint);

if邊的調用次數超過閾值

SpeedPat(t1);

CalculateValue(tmfpoint，tmpoint，epoint);

else

更新temp_point信息;

if到達制定時間間隔

updataSP();//更新當前時刻邊的調用次數

Sort_List();

De_Heap();

tmfpoint=mlist.containeropen.GetAt(0);//取出最小值

EnClose_List(tmfpoint);

GetResult(temp_fatherpoint);//return result

UpDate();//更新未被選中的路徑

當進行最優路徑查詢時，首先根據出發時間取出初始速度模式下該時刻所對應的實時速度(步驟1)。將初始點加入到CLOSE鏈表中，從初始點開始找到所有與該點相連的點，計算出在初始速度模式下到達這些點的實際時間并判斷速度模式是否需要更改進行判斷。如果速度模式發生改變，用新的速度模式重新計算到達這些點的實際時間。取出所用時間最小的邊，將該邊的終點作為下一次循環的起始點，并將該點加入結果集CLOSE鏈表中(步驟2~18)。從結果集中提取最優路徑并對結果集中其他邊的調用次數進行更新。

3 算法性能測試

3.1 測試環境

本文實現了在變化的速度模式下的最優路徑查詢算法。使用Visual C++ 6.0編程語言。測試在處理器為P4 2.66 GHz、內存1 GB，操作系統為Windows XP的PC機上進行。測試所采用的數據集^[7]來自城市交通網模擬平臺。

3.2 測試結果

圖4表示在三種不同的情況下，路徑查詢的對比情況。以下三種情況具有相同的起始點和終點，并且都同時對兩點間的路徑進行查詢。按照線型的粗細將公路劃分為三級，圖中，虛線邊為算法所查找到的路徑。其中，（a）為在不考慮速度模式的情況下利用A算法進行最短路徑查詢；（b）為在A算法的基礎上加入速度模式進行最優路徑查詢，但在行程中速度模式不發生改變；（c）表示在A算法的基礎上加入了速度模式，并且在行程中速度模式發生改變的情況下最優路徑的查詢。

由圖4可知，盡管無速度模式的最短路徑查找算法所找到的路徑總長最短，但在加入了速度模式后，由于最短路徑挑選的道路多為三級公路，速度較慢，不是最優路徑。對于圖4中的(b)和(c)，當某一時刻速度模式發生改變如交通高峰期，這時若仍沿用原速度模式查找，由于道路的速度模式發生了變化，一級公路的速度反而不如二級和三級公路；若沒有考慮速度模式的變化，所選道路仍多為一級公路，如(b)；而正常的情況下應該選擇低級的道路才能保證到達終點所用時間最短。

圖5表示查找相同的路徑，在相同的動態速度模式下，三種算法所查找的路徑行駛全程所用時間的對比。圖中橫坐標表示所要查找的路徑長度(m)，分別取10 000、20 000、40 000、60 000；縱坐標表示通過利用查詢得到的路徑，汽車行駛全程所用的時間；DY-SP表示加入動態速度模式的最優路徑查找算法；ST-SP表示固定速度模式下最優路徑查找算法；SP表示無速度模式的A最短路徑查找算法。

由圖5可以看出，在動態的速度模式下，利用A算法所查找的最短路徑汽車行駛所用的時間比加入了速度模式所查找的路徑汽車行駛所用的時間長；而用固定的速度模式所查找的路徑汽車行駛所用時間與動態速度模式下所查找的路徑汽車行駛所用時間相比，前者所用時間較長。

4 結束語

本文在基于A道路查詢算法基礎上，加入了速度模式的概念，并且對在道路擁擠致使初始速度模式發生改變的情況下，提出了一種最優路徑的查找算法。該算法通過建立速度模式庫，對速度模式發生變化的情況進行處理，給出在此情況下的最優路徑。這樣使對路徑查詢問題的處理更為全面，更加真實地模擬了道路交通的實際狀況。另外，該方法在實際應用中還有若干問題有待解決，如速度模式的有效性以及交通突發時間的影響問題等，都有待于進一步解決。

參考文獻：

［1］DIJKSTRA E.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1（1）:269-271.

［2］ZHAN F B， NOON C E. Shortest path algorithms: an evaluation using real road networks[J].Transportation Science，1998，31(1):65-73.

［3］BRINKHO T.A framework for generating network-based moving objects[J].GeoInformatica，2002，6(2):153-180.

［4］SHEKHAR S，YOO J S.Processing in-route nearest neighbor queries:a comparison of alternative approaches[C]// Proc of ACMGIS Conference on Management of Data. New York: ACM Press，2003:9-16.

［5］GONZALEZ H，HAN Jia-wei，LI Xiao-lei.Adaptive fastest path computation on a road network:a traffic mining approach[C]//Proc of the 33rd International Conference on Very Large Data Bases.Austria:VLDB Press，2007:23-28.

［6］KANOULAS E，DU Y，XIA T，et al.Finding fastest paths on a road network with speed patterns[C]//Proc of the 22nd International Conference on Data Engineering. Washington DC:IEEE Computer Society Press， 2006:10.

［7］GONZALEZ H，HAN Jia-wei，LI Xiao-lei，et al.Warehousing and analyzing of massive RFID data sets[C]// Proc of the 22nd International Conference on Data Engineering.Washington DC:IEEE Computer Society，2006:83.

［8］SALTENIS S，JENSEN C S，LEUTENEGGER S T，et al.Indexing the positions of continuously moving objects[C]//Proc of ACM SIGMOD International Conference on Management of Data. Dallas: ACM Press，2000:331-342.