張宇

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

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

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

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

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

二、系統(tǒng)詳細結構

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

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

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

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

三、詳細設計

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

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

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

把V分成兩組：

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

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

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

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

（3）每個頂點對應一個距離

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

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

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

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

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

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

四、系統(tǒng)測試

測試用例的設計

（1）測試用例1

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

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

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

預期結果：在軟件的車輛當前位置文本框中輸出選擇的結果

（2）測試用例2

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

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

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

預期結果：在軟件的車輛當前位置文本框中輸出選擇的結果

（3）測試用例3

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

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

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

預期結果：在軟件的車輛當前位置文本框中輸出選擇的結果

（4）測試用例4

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

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

輸入：點擊目的地

預期結果：若設置成功，則彈出成功對話框

五、結論

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

【參考文獻】

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