基于實時道路信息的個性化繞行指引方法研究*

□ 陸 杰，陶 菲，閆金偉，張帥倩,林 霜

(南通大學 地理科學學院,江蘇 南通 226007)

1 引言

近年來，隨著我國社會經濟的快速發展，城市化水平明顯加速，居民汽車保有量增加，隨之而來的城市交通擁堵問題逐漸加重，嚴重影響城市居民的出行效率，阻礙城市的經濟發展[1]。

在道路擁堵方面，Kamal等[2]提出了一種通過對單個車輛進行系統控制，緩解交通擁堵、節能減排的新方法。錢振等[3]采用基于出租軌跡數據的預測方法對交通擁堵狀態進行精確預測。在路徑優化方面，Liang Qi等[4]提出了針對交通事故的城市道路動態繞行方案。賈新春等[5]通過建立一種限制搜索區域的時變權重有向圖模型，獲取最優路徑。馮豪杰等[6]在Dijkstra算法基礎上，引入多限制因子的最優路徑計算方法，在實際中做出了有效地實踐。張東波等[7]提出了基于子圖分割的并行搜索方法。

隨著人工智能與大數據時代的來臨，每個領域都在改變[8-9]，智慧城市使城市一切的信息可以通過數字信息獲取[10-11]。因此，本文基于城市道路擁堵信息以及交通燈信息，引入司機的個性化參數作為優化閾值，對實時道路狀態變化進行檢測，為司機提供一種個性化的道路擁堵繞行指引服務，從路徑優化的角度緩解了城市交通擁堵程度。并以北京四環以內的部分道路作為實驗樣區，驗證了此方法在實際應用中的有效性，是一次新的嘗試，具有一定的創新性和可行性，為未來智慧城市的發展做出一定的貢獻。

2 數據獲取與處理

2.1 數據獲取

本文選取北京四環以內作為實驗樣區，數據來源于高德地圖，選取的道路為四環以內的部分主要城市道路，該區域面積約為63km2，主要路段數為196條。所需要的數據主要包括：道路路段長度、交通燈位置及時間數據、擁堵路段數據、擁堵等級信息數據。

道路的路段長度通過高德地圖提供的API在網絡上獲取，獲取的信息主要包括：請求狀態(status)，返回狀態信息(info)，請求狀態編碼(infocode)，道路信息(roads)其中包含路段信息(polylines)。通過polylines中經緯點信息，可以計算出道路長度。

以道路交叉點作為交通信號燈所在位置，由于車輛行駛速度各不相同，所遇的交通信號燈時間不盡相同，所以，在實驗中無法精確設置交通燈通行時間。針對此問題，本文將通過不斷改變交通燈通行時間的測試數值，從一定的數值范圍對算法進行實驗保證算法的科學性。

對于擁堵路段數據，結合實際路況與算法需求，對道路擁堵情況進行模擬，從而達到多方面分析檢驗算法的效果。

最后擁堵等級數據，本文根據文獻[3]中的道路擁堵等級與車速對應關系，并根據實際情況進行修正。

2.2 數據處理

從高德地圖中獲取的道路數據，主要是四環以內。首先對道路進行截取操作，剔除與運算無關的道路，這樣不僅降低算法運行時間，而且提高了算法的精確性。具體結果如圖1。

圖1 北京四環以內道路(左)及主要實驗道路(右)

在實際道路地圖中以顏色將道路擁堵等級劃分為四類，分別對應：暢通、輕度擁堵、中度擁堵、重度擁堵，這四種道路擁堵等級。對于四種道路擁堵等級所對應的車輛行駛速度，結合本文的實際數據情況，最終確定本文采用的交通擁堵等級取值范圍，如表1所示。

表1 交通擁堵等級取值范圍

其中，暢通、輕度擁堵、中度擁堵、重度擁堵四個等級的車速值在實際實驗之中不應取值為一個范圍，因此，本文通過實際道路的限速規定以及車輛實際行駛狀況，最終設定：①暢通路段平均車速為65km/h；②輕度擁堵路段平均車速為50km/h；③中度擁堵路段平均車速為30km/h；④重度擁堵路段平均車速為10km/h。

實驗還需要將交通燈位置數據匹配到道路之中，由于本文以道路岔口作為交通信號燈所在位置，所以，對交通岔口以自然數字進行編號，具體如圖2。

圖2 道路交通燈自然編號示意圖

3 算法分析與設計

3.1 算法分析

對于實際生活中的地圖導航功能，一般只提供最短距離路徑、最短時間路徑以及一些相關道路信息給用戶進行選擇，缺少了用戶個性化選擇，沒有考慮到一些人為的主觀因素。在實際情況中路況信息是不斷變化的，針對道路的狀態信息變化現有的功能并不能做出相應的改變，缺少靈活性。而本文針對這一問題，提出的“個性化的繞行指引方法”旨在加入人為主觀參數，對道路搜索進行優化，并在導航行駛過程中檢測道路信息的變化，做出相應的路徑優化，給用戶提供更加人性化的選擇。

算法運算前首先需要獲取用戶的個性化參數，如：可忍受道路附加長度(Lf)、可忍受道路附加時間(Tf)、道路優化標準(Rp)等。此部分參數需要用戶通過系統前端界面進行錄入。此外，還需要城市道路相關信息(MatGraph)作為基礎數據。

算法運行過程中，先搜索得出最短距離路徑和最短時間路徑相關信息，接著以最短距離路徑的距離(Rll)和消耗的時間(Rlt)以及最短時間路徑的距離(Ttl)和消耗的時間(Rtt)作為判斷標準搜索出可選路徑。并以用戶個性化參數和路徑本身的狀態信息作為篩選條件，剔除不滿足條件的路徑，獲取最終路徑。

算法運算結束后，將最終信息推送給用戶，同時針對用戶所選擇的路徑進行檢測，若新出現新增擁堵路段且擁堵等級大于Rp，則做出優化。具體流程圖如圖3。

3.2 算法設計

根據上文的算法分析過程，算法的主體數據結構設計主要包括三個部分：交通信號燈信息數據結構、道路信息存儲數據結構以及順序棧數據結構。

首先是交通信號燈信息數據結構(VertexType)，其中包含類型為整型的交通燈自然數編號和類型為浮點型的交通燈信號平均通過時間。

其次是道路信息存儲數據結構，其中包括存儲路段信息的整型鄰接矩陣、擁堵路段距離的整型鄰接矩陣、擁堵路段等級的浮點型鄰接矩陣、記錄路段總數和頂點數以及頂點信息的VertexType類型數組。

圖3 算法流程圖

最后是順序棧(stack)數據結構，主要作為算法運算過程的核心載體，包括存儲路徑信息的VertexType型數組和整型的棧頂。

以上完成了算法的數據結構設計，接下來是算法的邏輯運算過程，表2給出了算法中相關函數的含義。

表2 函數具體含義

算法流程：

Begin

Init(MatGraph);

w=起點;

s=終點；

Best Distance_Road=Dijkstra(MatGraph， w， s)；

Best_Time_Road=DijkstraMatGraph， w， s);

Push(stack， w );

while(stack≠φ)

e=GetTop (stack)；

if(e==s)

Save (p， path[]);

Pop(stack，e);

e=GetTop(stack);

while(find(e，eN))

if(Path(w,eN,Rlt,Rtl))

Push(stack,eN);

break

while end

if(!find(e,eN))

Pop(stack,e);

e=GetTop(stack);

while end

for p in path[]

if(conform(p,Lf,Tf))

Recommend(p);

for end

End

4 算法檢驗

4.1 數據導入處理

通過前文的數據準備，將獲取的數據轉化成為對應的數據結構并錄入。錄入的數據共包含57個頂點元素，196條邊數據，交通燈通過時間取40s作為平均通過時間。對于其中交通擁堵的路段長度，通過地圖測量得出。道路擁堵等級根據前文設置的參數轉化成為固定的數值進行運算。最后，以自然序號為0的節點為源點，以自然序號為57的節點為終點，個人主觀參數(只作為測試使用)：擁堵耗時不大于3min,附加距離不超過1000米，道路優化標準為中度擁堵，進行道路搜索。

4.2 運行結果檢驗

通過輸入的參數進行路徑搜索，輸出參數包含5個字段：“總長”，“擁堵耗時”，“節點耗時”，“總耗時”，“路徑”，以路徑長度為準，從小到大排序。搜索結果具體如表3所示。

表3 最終推薦路徑信息

可見除去最短時間路徑和最短距離路徑，還存在兩條較為合適的路徑，搜索結果如圖4所示。其中“路徑1”對應路徑長度為15780m，“路徑2”對應路徑長度為15800m，“路徑3”對應路徑長度為15830m，“路徑4”對應路徑長度為16020m。

當用戶選擇路徑4行作為最終的行駛路徑時，系統則將路徑4納入檢測系統，并開始檢測路徑4所包含的路段中是否有新增擁堵路段，若存在則同時判斷擁堵等級是否大于用戶的主觀參數。現假設路徑4中存在新增擁堵路段(從54節點到55節點，其他擁堵路段信息不變)且擁堵等級為重度擁堵，此時用戶處于40到50節點之間。系統則會開始優化從50到57的路徑，優化結果如表4。

圖4 推薦路徑地圖

表4 優化路徑信息

搜索結果如圖5所示，其中“路徑1”對應路徑長度為4920m，“路徑2”對應路徑長度為4990m，“路徑3”對應路徑長度為5000m。可見在道路新增擁堵路段時，算法可根據出現的情況及時計算出優化的路徑，達到了動態優化路徑的目的，在實際中有著廣泛應用。

圖5 優化路徑地圖

通過多次實驗與驗證，算法可以搜索出從源點到終點所有的可選路徑，推薦路徑符合實際需求，算法運行正確，搜索結果合理，給予了用戶更多選擇，防止距離最短但耗時過長以及時間最短但距離過長的一些極端交通路徑的出現，從而提高用戶體驗，為用戶提供更好的服務。

5 結語

本文提出了一種基于實時道路信息的個性化繞行指引方法，該方法基于城市道路擁堵信息以及交通燈信息，以駕駛員從前端界面輸入的個性化參數作為優化閾值，為司機提供一種個性化的道路擁堵繞行指引的服務，可滿足不同司機對于行駛時間、里程的不同需求。在實驗過程中，以實際路段狀況為測試數據，通過科學設置其中靈活的參數，考慮多種實際情況，并進行大量實驗與驗證。實驗結果表明此方法在實時道路擁堵繞行指引中具有很高的應用價值。下一步擬針對自動化參數設定方法進行研究，借助人工智能建立學習庫模擬人們的出行習慣，以提供更加合適的主觀參數，方便人們的生活出行。