智能交通車流自動導(dǎo)引系統(tǒng)

張宇

【摘 要】 隨著中國經(jīng)濟的發(fā)展和人民生水平的提高，交通活動已經(jīng)成為人們生活的重要組成部分，本文首先介紹了道路數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)和存儲方式，然后依據(jù)實際情況，考慮車輛在動態(tài)環(huán)境下尋找最優(yōu)路徑，提出了使用強化學(xué)習(xí)方法作為主要研究算法，對車輛智能體進行道路選擇的結(jié)果給予一定的獎勵，從而使車輛最終選取理論上最優(yōu)的一條道路。

【關(guān)鍵詞】 強化學(xué)習(xí) 車輛路徑規(guī)劃 動態(tài)環(huán)境

一、系統(tǒng)功能分析

本課題是研究動態(tài)環(huán)境中車輛路徑規(guī)劃的問題，并設(shè)計出可視化的仿真軟件以達到模擬現(xiàn)實情況下駕駛者在道路上的行車路線。此仿真軟件要滿足以下功能：設(shè)置車輛的起始地點和目的地點，并可設(shè)置車輛行駛過程中道路環(huán)境，例如某一道路上會發(fā)生交通堵塞等問題的情況。對于在現(xiàn)實世界中，道路完全具有實時性和動態(tài)性，因此在程序中可將路障設(shè)置為隨機路障，即完全由程序隨即決定當前時刻是哪條道路有障礙。該系統(tǒng)在設(shè)置完車輛行車環(huán)境后，通過算法和程序的計算，找到一條在當前環(huán)境下最適合的行車路線，以達到滿足本課題的要求，模擬出現(xiàn)實世界中動態(tài)環(huán)境下的車輛路徑規(guī)劃問題。

系統(tǒng)功能主要可以劃分為三個部分：一是給出車輛在不同行車方案下的運行成本，二是設(shè)計算法尋找車輛行駛的最優(yōu)路徑，還有一個是顯示車輛的行車路線。最后給出系統(tǒng)的功能概圖，為軟件的總體設(shè)計和詳細設(shè)計提供依據(jù)。

二、系統(tǒng)詳細結(jié)構(gòu)

在仿真系統(tǒng)軟件的設(shè)計上，系統(tǒng)的大體思想是輸入->處理->輸出。模擬選擇輸入車輛的起始地點和目的地點，并選擇產(chǎn)生路障的類型，這些都是輸入問題。之后在后臺運行，根據(jù)選擇的條件進行路徑規(guī)劃，此為處理部分，最后將處理的結(jié)果以文字和在系統(tǒng)界面上顯示的形式進行表示，這位輸出部分。

輸入模塊又可分為三個子輸入模塊部分：起始地點選擇模塊，目的地點選擇模塊和道路障礙選擇模塊。其中，在起始地點和目的地點兩個選擇模塊中，可模擬選擇車輛的起始位置和目的位置。在這兩個模塊中，都可以使用選擇已確定的地點，或可以通過輸入其地理坐標，作為用戶選擇的起始地點或目的地點。對于道路障礙子模塊來說，可以對其選擇產(chǎn)生隨機路障，或者自己選擇有路障的路段，但是對系統(tǒng)進行設(shè)置隨機路障更符合現(xiàn)實情況。

處理模塊就是對車輛的路徑選擇進行算法設(shè)計和編寫程序。在這一部分，使用強化學(xué)習(xí)算法進行動態(tài)環(huán)境中的車輛路徑規(guī)劃問題，同時在預(yù)測車輛可能的行駛路線的情況，據(jù)此對車輛下一步行駛的路段進行預(yù)測。

輸出模塊由兩個子模塊構(gòu)成。一個是車輛進行路徑選擇后，在界面上的顯示，即使用劃線的方式對車輛行駛的路線進行標注，此為畫圖模塊，在線程中進行處理。另一個是車輛在行駛的過程中，輸出其選擇的路線，行駛的狀態(tài)，和當前環(huán)境下的交通堵塞等狀況。

三、詳細設(shè)計

路徑規(guī)劃各要素間不是互相孤立的，而是存在著復(fù)雜的關(guān)系。具體來說就是兩個基本要素結(jié)點和路段之間有著復(fù)雜的關(guān)系，在現(xiàn)實世界中，結(jié)點即為道路上的一條路段的兩端的路口。路段就可看作是不間斷的沒有路口的一條馬路，或者也可以看做是幾條路段和結(jié)點組成對的復(fù)合路段。

在本課題中Dijkstra算法的思想是：按照路徑長度遞增次序產(chǎn)生最短路徑算法。

即假設(shè)無向圖G=（V，E）中，每條邊E[i]的長度為w[i]，找到由頂點V0到其余各點的最短路徑。

把V分成兩組：

（1）s：已求出最短路徑的頂點的集合

（2）V-S=T：尚未確定最短路徑的頂點集合

將T中頂點按最短路徑遞增的次序加入到S中，

保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度

（3）每個頂點對應(yīng)一個距離

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度

可以證明：V0到T中頂點Vk的最短路徑，是從V0到Vk的直接路徑的權(quán)值

本課題的車輛路徑規(guī)劃算法的實現(xiàn)過程大體如下：

初始時，設(shè)置車輛的起始地點和目的地點，判斷車輛當前地點和目的地點是否相同，若相同，則表明當前位置與終點重合，認為到達終點，規(guī)劃結(jié)束；若不相同，則開始尋找車輛要走的下一條路徑。

在當前位置尋找下一步要走的路段，在當前結(jié)點處，判斷可走向的與之在同一路段上的另一端的結(jié)點，即選擇出將要走向的那個結(jié)點，在局部情況下可使付出的代價最小。在此處要計算，從與當前結(jié)點位置在同一路段上的其他結(jié)點分別到目的結(jié)點的最短路徑值，比較它們之間的大小，找到權(quán)值最小的那個結(jié)點，下一步，車輛就向著那個結(jié)點行駛，一直到到達目的地結(jié)點。

四、系統(tǒng)測試

測試用例的設(shè)計

（1）測試用例1

用例描述：測試起始地點輸入模塊是否能夠正確使用

前置條件：起始地點輸入模塊正確編寫并編譯成功

輸入：選取下拉列表中的某一個元素

預(yù)期結(jié)果：在軟件的車輛當前位置文本框中輸出選擇的結(jié)果

（2）測試用例2

用例描述：測試終點輸入模塊是否能夠正確使用

前置條件：輸入模塊正確編寫并編譯成功

輸入：向文本框中輸入數(shù)據(jù)

預(yù)期結(jié)果：在軟件的車輛當前位置文本框中輸出選擇的結(jié)果

（3）測試用例3

用例描述：測試目的結(jié)點輸入模塊是否能夠正確使用

前置條件：目的結(jié)點輸入模塊正確編寫并編譯失敗

輸入：選取下拉列表中選擇新地址

預(yù)期結(jié)果：在軟件的車輛當前位置文本框中輸出選擇的結(jié)果

（4）測試用例4

用例描述：測試設(shè)置路線查詢是否能夠正確使用

前置條件：起始點目的地正確編寫并編譯成功

輸入：點擊目的地

預(yù)期結(jié)果：若設(shè)置成功，則彈出成功對話框

五、結(jié)論

本軟件系統(tǒng)的設(shè)計是基于百度地圖API進行的動態(tài)環(huán)境下的車輛路徑規(guī)劃。在設(shè)計過程中，重點解決了在模擬現(xiàn)實世界中交通路況具有動態(tài)性和不確定性的情況下，車輛進行最優(yōu)路徑的選擇。在解決這個問題時使用到了很多方法和技巧，雖然在實現(xiàn)的過程中，遇到了很多難題和麻煩，也遭遇到很多瓶頸，但最后還是轉(zhuǎn)換了思維，使用了其他的方法解決了問題。

【參考文獻】

[1] 陸琳.不確定信息車輛路徑問題及其智能算法研究[M].第一版.北京：科學(xué)出版社，2010.