“互聯網+”下城市路網的最優路徑選擇

虞博翔　萬仲禹　王豹　曹煜

摘要：在“互聯網+”的時代下，結合計算機數據采集以及系統仿真技術，對車輛在城市路網環境下，進行全局路徑最優規劃。將出發點與目的地連線所成對角線的矩形區域，作為路徑限制搜索區域。不同時間段的車流量和不變的道路距離對道路阻抗產生影響的主要原因。在此基礎上，建立城市路網的限制搜索區域時變權重有向圖模型，并采用蟻群算法求解全局規劃最優路徑。最后進行MATLAB軟件編程，仿真驗證了算法的可行性以及有效性。

關鍵詞：路網識別;道路阻抗;蟻群算法

中圖分類號：TP391.9 文獻標識碼：A

文章編號：1009-3044（2020）09-0200-03

1 路網模型及路阻函數確定

1.1城市路網模型

城市道路網絡[2]中包含雙向道路和單向道路，因此城市道路網絡可抽象為一個雙向有向圖模型：道路交叉口作為頂點，交叉口間的路段作為有向邊。同時，城市道路中不同的路段在不同的時間點道路的擁堵程度以及不同路段的長度等因素使得車輛通過城市道路所花費的時間是動態變化的，為此引入時變路阻函數作為有向圖中邊的權函數。

1.2時變路阻函數的確定

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

路阻主要是路段和節點所產生的阻礙。在一般的路徑規劃模型中，只是對不變的道路長度進行考慮，在大數據環境下，所需數據容易獲得，并沒有考慮其他因素。所以對于道路復雜，路況多變的道路阻抗，還需考慮不同時間段的車流量，以及信號燈造成的時間延誤，對此，在賈新春老師的研究基礎上，構造路阻函數[4]為

用表述時間的函數帶描述路阻情況，優化路阻函數目標，使其最小，本質上是車輛行程時間最短。

2 蟻群算法規劃最優路徑

2.1 蟻群算法原理

蟻群可以在不同的環境下，尋找最短到達食物源的路徑。螞蟻找到最短路徑要歸功于信息素和環境，假設有兩條路可從蟻窩通向食物，當螞蟻到達終點之后會立即返回，螞蟻會在其經過的路徑上留下信息素，距離短的路上的螞蟻往返一次時間短，重復頻率快，在單位時間里往返螞蟻的數目就多，留下的信息素也多，會吸引更多螞蟻過來，會留下更多信息素，即信息素的多少與路徑長短呈反比[5]，因此越來越多的螞蟻聚集到最短路徑[1]上來。

2.2 算法執行步驟

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

3 以徐州為例進行算法仿真分析

3.1 局部路網識別

運用Arcgis軟件，添加暗藍色徐州市局部地區底圖，將局部地區路網數據添加至底圖中，得到局部地區的路網可視化數據，如下圖所示：

即研究從節點l到節點2的最優路徑。

3.2 道路阻抗的確定

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

3.3 Matlab仿真分析

在得到各路徑的路權時，運用Matlab進行軟件編程，相關參數設置為：

軟件求解得出最終結果所示如下：

從收斂曲線變化趨勢可以得出在100此迭代次數下，最優路徑在31km左右，但這只是在極限狀態下，路程中的一些拐角點并沒有很好的體現，這也是該算法的缺陷之處。但從路徑仿真圖中可以得出大致的最優路徑。

4 結論

本文綜合考慮了城市路網中影響道路阻抗的動態變化因素與不變因素，結合限制搜索區域，引入搜索方向因素，運用Arcgis軟件對城市路網進行識別，建立針對限制搜索區域的時變權重有向圖模型，并提出了蟻群算法求解最優路徑規劃的想法。依靠蟻群算法自適應地選取最優路徑，保證了車輛在當時所處環境下所選路徑是最優的。Matlab仿真驗證了該模型算法的有效性以及可行性。

雖然考慮了城市路網中影響道路阻抗一些主要因素，但同樣還存在其他因素未能考慮，如天氣等。此外，對不同道路狀況，不同時間段內的車流量無法做到特別精準的預測，這使得算法存在一定局限性。

參考文獻：

[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]王潤澤，王亮，劉濤，等.考慮實時路況反饋的動態路徑規劃算法研究【Jl.測繪科學：2018（1）：1-9.

[3]莊焰，呂慎.城市道路交通流三參數關系研究[J].深圳大學學報，2005，22（4）：373-376.

[4]賈新春，彭登永，李雷，等.城市路網的一種最優路徑搜索算法[J].山西大學學報舊然科學版：2018（9）：1-12.

[5]趙娟平，高憲文，符秀輝.改進蟻群優化算法求解移動機器人路徑規劃問題[J].南京理工大學學報，2011，35（5）：637-641.

[6]史恩秀，陳敏敏，李俊，等，基于蟻群算法的移動機器人全局路徑規劃方法研究[J].農業機械學報，2014，45（6）：53-57.

【通聯編輯：梁書】