虞博翔　萬(wàn)仲禹　王豹　曹煜

摘要：在“互聯(lián)網(wǎng)+”的時(shí)代下，結(jié)合計(jì)算機(jī)數(shù)據(jù)采集以及系統(tǒng)仿真技術(shù)，對(duì)車輛在城市路網(wǎng)環(huán)境下，進(jìn)行全局路徑最優(yōu)規(guī)劃。將出發(fā)點(diǎn)與目的地連線所成對(duì)角線的矩形區(qū)域，作為路徑限制搜索區(qū)域。不同時(shí)間段的車流量和不變的道路距離對(duì)道路阻抗產(chǎn)生影響的主要原因。在此基礎(chǔ)上，建立城市路網(wǎng)的限制搜索區(qū)域時(shí)變權(quán)重有向圖模型，并采用蟻群算法求解全局規(guī)劃最優(yōu)路徑。最后進(jìn)行MATLAB軟件編程，仿真驗(yàn)證了算法的可行性以及有效性。

關(guān)鍵詞：路網(wǎng)識(shí)別;道路阻抗;蟻群算法

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）09-0200-03

1 路網(wǎng)模型及路阻函數(shù)確定

1.1城市路網(wǎng)模型

城市道路網(wǎng)絡(luò)[2]中包含雙向道路和單向道路，因此城市道路網(wǎng)絡(luò)可抽象為一個(gè)雙向有向圖模型：道路交叉口作為頂點(diǎn)，交叉口間的路段作為有向邊。同時(shí)，城市道路中不同的路段在不同的時(shí)間點(diǎn)道路的擁堵程度以及不同路段的長(zhǎng)度等因素使得車輛通過(guò)城市道路所花費(fèi)的時(shí)間是動(dòng)態(tài)變化的，為此引入時(shí)變路阻函數(shù)作為有向圖中邊的權(quán)函數(shù)。

1.2時(shí)變路阻函數(shù)的確定

市場(chǎng)路網(wǎng)模型中的路阻函數(shù)與表征交通流特性的基本參數(shù)：交通流量qij（t）、行車速度vij（t）、車流密度Pij（t）密切相關(guān)，且交通流的三個(gè)基本參數(shù)[3]之間符合q= pv。

路阻主要是路段和節(jié)點(diǎn)所產(chǎn)生的阻礙。在一般的路徑規(guī)劃模型中，只是對(duì)不變的道路長(zhǎng)度進(jìn)行考慮，在大數(shù)據(jù)環(huán)境下，所需數(shù)據(jù)容易獲得，并沒(méi)有考慮其他因素。所以對(duì)于道路復(fù)雜，路況多變的道路阻抗，還需考慮不同時(shí)間段的車流量，以及信號(hào)燈造成的時(shí)間延誤，對(duì)此，在賈新春老師的研究基礎(chǔ)上，構(gòu)造路阻函數(shù)[4]為

用表述時(shí)間的函數(shù)帶描述路阻情況，優(yōu)化路阻函數(shù)目標(biāo)，使其最小，本質(zhì)上是車輛行程時(shí)間最短。

2 蟻群算法規(guī)劃最優(yōu)路徑

2.1 蟻群算法原理

蟻群可以在不同的環(huán)境下，尋找最短到達(dá)食物源的路徑。螞蟻找到最短路徑要?dú)w功于信息素和環(huán)境，假設(shè)有兩條路可從蟻窩通向食物，當(dāng)螞蟻到達(dá)終點(diǎn)之后會(huì)立即返回，螞蟻會(huì)在其經(jīng)過(guò)的路徑上留下信息素，距離短的路上的螞蟻往返一次時(shí)間短，重復(fù)頻率快，在單位時(shí)間里往返螞蟻的數(shù)目就多，留下的信息素也多，會(huì)吸引更多螞蟻過(guò)來(lái)，會(huì)留下更多信息素，即信息素的多少與路徑長(zhǎng)短呈反比[5]，因此越來(lái)越多的螞蟻聚集到最短路徑[1]上來(lái)。

2.2 算法執(zhí)行步驟

蟻群算法[6]的執(zhí)行流程圖如圖1所示：

3 以徐州為例進(jìn)行算法仿真分析

3.1 局部路網(wǎng)識(shí)別

運(yùn)用Arcgis軟件，添加暗藍(lán)色徐州市局部地區(qū)底圖，將局部地區(qū)路網(wǎng)數(shù)據(jù)添加至底圖中，得到局部地區(qū)的路網(wǎng)可視化數(shù)據(jù)，如下圖所示：

即研究從節(jié)點(diǎn)l到節(jié)點(diǎn)2的最優(yōu)路徑。

3.2 道路阻抗的確定

對(duì)各條道路按照從上到下，從左到右的先后順序進(jìn)行數(shù)字編號(hào)，總共有20條主要道路。根據(jù)上節(jié)描述的路阻函數(shù)計(jì)算方式，根據(jù)實(shí)地考察以及Matlab仿真實(shí)驗(yàn)，得出各條道路的路阻如下表所示：

3.3 Matlab仿真分析

在得到各路徑的路權(quán)時(shí)，運(yùn)用Matlab進(jìn)行軟件編程，相關(guān)參數(shù)設(shè)置為：

軟件求解得出最終結(jié)果所示如下：

從收斂曲線變化趨勢(shì)可以得出在100此迭代次數(shù)下，最優(yōu)路徑在31km左右，但這只是在極限狀態(tài)下，路程中的一些拐角點(diǎn)并沒(méi)有很好的體現(xiàn)，這也是該算法的缺陷之處。但從路徑仿真圖中可以得出大致的最優(yōu)路徑。

4 結(jié)論

本文綜合考慮了城市路網(wǎng)中影響道路阻抗的動(dòng)態(tài)變化因素與不變因素，結(jié)合限制搜索區(qū)域，引入搜索方向因素，運(yùn)用Arcgis軟件對(duì)城市路網(wǎng)進(jìn)行識(shí)別，建立針對(duì)限制搜索區(qū)域的時(shí)變權(quán)重有向圖模型，并提出了蟻群算法求解最優(yōu)路徑規(guī)劃的想法。依靠蟻群算法自適應(yīng)地選取最優(yōu)路徑，保證了車輛在當(dāng)時(shí)所處環(huán)境下所選路徑是最優(yōu)的。Matlab仿真驗(yàn)證了該模型算法的有效性以及可行性。

雖然考慮了城市路網(wǎng)中影響道路阻抗一些主要因素，但同樣還存在其他因素未能考慮，如天氣等。此外，對(duì)不同道路狀況，不同時(shí)間段內(nèi)的車流量無(wú)法做到特別精準(zhǔn)的預(yù)測(cè)，這使得算法存在一定局限性。

參考文獻(xiàn)：

[1] Erin B，AbiVev R，lbrahim D.Teaching robot navigation in thepresence of obstacles uslng a computer simulation program[J].Procedia - Social and Behavioral Sciences， 2010， 2（2）： 565-571.

[2]王潤(rùn)澤，王亮，劉濤，等.考慮實(shí)時(shí)路況反饋的動(dòng)態(tài)路徑規(guī)劃算法研究【Jl.測(cè)繪科學(xué)：2018（1）：1-9.

[3]莊焰，呂慎.城市道路交通流三參數(shù)關(guān)系研究[J].深圳大學(xué)學(xué)報(bào)，2005，22（4）：373-376.

[4]賈新春，彭登永，李雷，等.城市路網(wǎng)的一種最優(yōu)路徑搜索算法[J].山西大學(xué)學(xué)報(bào)舊然科學(xué)版：2018（9）：1-12.

[5]趙娟平，高憲文，符秀輝.改進(jìn)蟻群優(yōu)化算法求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題[J].南京理工大學(xué)學(xué)報(bào)，2011，35（5）：637-641.

[6]史恩秀，陳敏敏，李俊，等，基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45（6）：53-57.

【通聯(lián)編輯：梁書】