張宇

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

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

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

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

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

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

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

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

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

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

三、詳細(xì)設(shè)計(jì)

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

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

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

把V分成兩組：

（1）s：已求出最短路徑的頂點(diǎn)的集合

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

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

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

（3）每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離

S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長(zhǎng)度

T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度

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

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

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

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

四、系統(tǒng)測(cè)試

測(cè)試用例的設(shè)計(jì)

（1）測(cè)試用例1

用例描述：測(cè)試起始地點(diǎn)輸入模塊是否能夠正確使用

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

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

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

（2）測(cè)試用例2

用例描述：測(cè)試終點(diǎn)輸入模塊是否能夠正確使用

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

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

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

（3）測(cè)試用例3

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

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

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

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

（4）測(cè)試用例4

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

前置條件：起始點(diǎn)目的地正確編寫并編譯成功

輸入：點(diǎn)擊目的地

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

五、結(jié)論

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

【參考文獻(xiàn)】

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