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

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

1 引言

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

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

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

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

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

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

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

以道路交叉點(diǎn)作為交通信號(hào)燈所在位置，由于車輛行駛速度各不相同，所遇的交通信號(hào)燈時(shí)間不盡相同，所以，在實(shí)驗(yàn)中無(wú)法精確設(shè)置交通燈通行時(shí)間。針對(duì)此問(wèn)題，本文將通過(guò)不斷改變交通燈通行時(shí)間的測(cè)試數(shù)值，從一定的數(shù)值范圍對(duì)算法進(jìn)行實(shí)驗(yàn)保證算法的科學(xué)性。

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

最后擁堵等級(jí)數(shù)據(jù)，本文根據(jù)文獻(xiàn)[3]中的道路擁堵等級(jí)與車速對(duì)應(yīng)關(guān)系，并根據(jù)實(shí)際情況進(jìn)行修正。

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

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

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

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

表1 交通擁堵等級(jí)取值范圍

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

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

圖2 道路交通燈自然編號(hào)示意圖

3 算法分析與設(shè)計(jì)

3.1 算法分析

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

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

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

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

3.2 算法設(shè)計(jì)

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

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

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

圖3 算法流程圖

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

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

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

算法流程：

Begin

Init(MatGraph);

w=起點(diǎn);

s=終點(diǎn)；

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 算法檢驗(yàn)

4.1 數(shù)據(jù)導(dǎo)入處理

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

4.2 運(yùn)行結(jié)果檢驗(yàn)

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

表3 最終推薦路徑信息

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

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

圖4 推薦路徑地圖

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

搜索結(jié)果如圖5所示，其中“路徑1”對(duì)應(yīng)路徑長(zhǎng)度為4920m，“路徑2”對(duì)應(yīng)路徑長(zhǎng)度為4990m，“路徑3”對(duì)應(yīng)路徑長(zhǎng)度為5000m?？梢?jiàn)在道路新增擁堵路段時(shí)，算法可根據(jù)出現(xiàn)的情況及時(shí)計(jì)算出優(yōu)化的路徑，達(dá)到了動(dòng)態(tài)優(yōu)化路徑的目的，在實(shí)際中有著廣泛應(yīng)用。

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

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

5 結(jié)語(yǔ)

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