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

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

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

1 引言

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

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

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

2 數(shù)據(jù)獲取與處理

2.1 數(shù)據(jù)獲取

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

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

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

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

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

2.2 數(shù)據(jù)處理

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

圖1 北京四環(huán)以內(nèi)道路(左)及主要實驗道路(右)

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

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

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

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

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

3 算法分析與設計

3.1 算法分析

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

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

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

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

3.2 算法設計

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

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

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

圖3 算法流程圖

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

以上完成了算法的數(shù)據(jù)結(jié)構(gòu)設計，接下來是算法的邏輯運算過程，表2給出了算法中相關函數(shù)的含義。

表2 函數(shù)具體含義

算法流程：

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 數(shù)據(jù)導入處理

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

4.2 運行結(jié)果檢驗

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

表3 最終推薦路徑信息

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

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

圖4 推薦路徑地圖

表4 優(yōu)化路徑信息

搜索結(jié)果如圖5所示，其中“路徑1”對應路徑長度為4920m，“路徑2”對應路徑長度為4990m，“路徑3”對應路徑長度為5000m?？梢娫诘缆沸略鰮矶侣范螘r，算法可根據(jù)出現(xiàn)的情況及時計算出優(yōu)化的路徑，達到了動態(tài)優(yōu)化路徑的目的，在實際中有著廣泛應用。

圖5 優(yōu)化路徑地圖

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

5 結(jié)語

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