基于蟻群算法動態計算最短時間路徑方法的研究
2023-04-29 00:00:00王佳卓
無線互聯科技 2023年10期
摘要：智慧交通借助物聯網技術和大數據技術，給人們提供了更加智能的出行路徑規劃服務。在復雜多變的城市交通網絡中，計算起點到終點的最短通行時間路徑，需要根據采集的路況信息數據，動態計算每條路徑的最短通行時間，從而給出最短時間到達的路徑規劃方案。文章使用蟻群算法對最短時間路徑規劃問題進行研究，通過算法改進，給出兩點之間時間最短的路徑規劃計算方法，利用MATLAB仿真軟件導入實例化數據，模擬智慧交通動態采集路況信息并規劃路線的過程，從而驗證該方法的有效。
關鍵詞：智慧交通；路徑計算；最短時間；MATLAB；蟻群算法
中圖分類號：TP399
文獻標志碼：A
0 引言
隨著國家經濟的迅速發展，人們的收入水平飛速增加，駕駛汽車出行已經成為越來越多家庭首要選擇的出行方式。然而，日益增長的汽車總量給城市交通帶來了巨大壓力，在有限的通行道路資源下，如何根據實時變化的道路通行信息，按需動態規劃出行路徑，成為人們出行的首要需求。在這種情況下，智慧交通技術應運而生，在出行路徑規劃方面主要借助物聯網技術對道路通行情況進行實時采集、上報，利用大數據技術中的特定方法，對采集上報的數據進行分析和計算，最終給出具體的路徑規劃方案。
對于智慧交通的路徑規劃問題，通常采用蟻群算法對起止點之間的路徑進行遍歷計算，而原生蟻群算法只能求解最短路徑問題。最短通行路徑和最短通行時間路徑顯然不是同一個研究問題，最短通行路徑在動態交通的情況下未必是最短時間通行路徑。例如，救護車或其他執行特殊任務的車輛，為了及時有效地達成最終任務，從起點到終點往往不是以最短通行路徑為目標，而是以最短通行時間為目標。因此，需要對蟻群算法模型進行改進，基于當前規劃的路徑和道路通行速度進行動態迭代運算，從而解決動態規劃最短通行時間路徑的問題。
目前，對于最短通行時間路徑規劃問題的研究成果較多，例如，在生產車間中，通過增加轉彎次數的優化路徑設計，減少機器人到達目的地所需的時間，從而提高機器人的工作效率［1］；針對交通網絡系統中路網時間流問題，引進堵塞系數，構造動態時間函數，建立在動態堵塞情況下的最短時間流模型，從而給出最短時間路徑規劃方案［2］；通過構建最短時間—最大流量分析模型，找出配送線路的優化途徑，提高物流企業盈利能力和客服服務水平等［3］。本文主要利用改進的蟻群算法，結合實時交通通行信息，動態計算最短通行時間的路徑規劃問題。
1 問題分析
我國急救物資的運輸主要根據貨物的運輸距離選擇運輸方式。一般來說，急需的貨物而路程較遠的，多使用航空運送，短程可由公路運送。城市內配送由專門的車輛進行緊急運輸，因為專用車輛具有一定的權限，在城市內擁有優先通行的權利。但是，人們普遍忽略了其途經路段對交通的影響，每當車輛需要緊急通行的時候，都會因為普通車輛的堵塞或交通管制而對部分交通路口產生較大的交通壓力，甚至造成嚴重堵車。本文主要研究利用智慧交通技術和蟻群算法，動態規劃最短通行時間的路徑問題。
2 算法改進
使用蟻群算法，先要對算法中的參數設定初始值。
節點數量n=20。節點數量就是網絡模型中的起始點、目標點與各路口的數量，本文以真實路網情況為基準，建立了起始點與目標點之間的路網模型，確定節點為20個。
螞蟻數量M=50。螞蟻的數量一般為節點數量的2～3倍。本文中的網絡圖節點數值為20，因此取節點數量的2.5倍，設定螞蟻數量為50個。
信息激素啟發因子α=1。
期望啟發因子β=2。通過大量的試驗分析，得出了β通常為0～5，選擇β=2的效果最佳。所以，本文中的β數值是2。
初始各條道路上的信息素濃度C=0.1。
每只螞蟻所攜帶的信息量Q=100。
信息素揮發系數ρ=0.3。
最大的迭代次數是指在執行完指定周期后，蟻群算法會停止執行，并且以目前群中最好的結果為該問題的最優解，MAXNC=200。
下面，改進蟻群算法，計算最短時間路徑。
在算法開始時，把 m個螞蟻隨機分配到 n個節點，每只螞蟻都有一個禁忌表，其第一個元素是它目前所處的節點。此時，所有路線中的信息素量都是初始值，所有螞蟻都會憑借剩余的信息素的多少和設置的啟發信息選取接下來要前往的節點。在時刻t，螞蟻m從節點i轉移到城市j的概率為：
式中，i，j分別為起點與終點；m為螞蟻編號；t表示時刻；Pmij（t）為t時刻第m只從 i節點到 j的螞蟻傳遞的概率［4］，其數值越大，螞蟻就越有可能選擇路徑i-j；Cij（t）為t時刻該路徑的信息素濃度，初始為0.01［4］；ηij（t）為啟發函數；Cis（t）為從節點i到目標節點s的信息素總量；ηis（t）為從節點i到目標節點s的期望啟發函數值；α為信息素啟發因子；β為期望啟發因子；A為第k只螞蟻下一步允許選擇的節點集合。即當節點j屬于集合A時（說明該節點尚未被訪問），被選擇的概率為（節點i到j路徑上的信息素×節點i到j路徑上啟發式信息值）/（節點i到s路徑上的信息素×節點i到s路徑上的啟發式信息值的總量，s遍歷集合A中所有的節點）；而當節點j不屬于集合A時，說明該節點已經被訪問過，被選擇的概率為0。
常規的以距離最短為目標的路徑規劃，啟發函數可以描述為：
式中，dij為節點i和節點j的路徑i-j的距離。因為本文中啟發因子是時間，所以啟發函數應改為：
式中Vt為在t時刻的路況下該路段車輛的速度，啟發式函數為螞蟻經過i到j路徑所用的時間的倒數。
基于正反饋的蟻群算法，可以在最短的時間內選擇最小的路徑。在最短的時間路徑上，信息素的濃度越高，所選的可能性就越大。但是，如果信息素濃度太高，就會喪失啟發信息的功能，導致蟻群喪失搜索解空間的能力，陷入局部最優。該方法通過模擬自然界中信息素的揮發現象來進行信息素的更新。
在（t+n）時刻，路徑i-j信息素濃度的計算方法如下：
Cij（t+n）=（1-ρ）Cij（t）+ΔCij（t）（5）
式中，ρ為揮發因子；（1-ρ）為信息素保留系數；Cij（t）為t時刻i到j路徑的信息素濃度；ΔCij（t）為完成一輪迭代路徑i-j信息素濃度的增加量。其計算方法如下：
式中，ΔCmij（t）為第m只螞蟻完成一輪迭代路徑i-j信息素濃度的增加量；M為蟻群規模。
ΔCmij（t）的計算方法如下：
式中，Q為完成一輪迭代螞蟻留下的信息素濃度總量；Tm為第m只螞蟻經過一輪迭代所通過的路徑的時間。
3 數據驗證
從起點開始選擇須經過的18個重要路口，在不同時間根據不同的路況來實時選擇最優路徑。以起點為坐標原點，測量出各個路口以及終點的X坐標和Y坐標，利用MATLAB軟件，將起始端和終點段及每個十字路口的位置坐標輸入數字矩陣，再使用scatter函數，生成的二維位置如圖1所示。
在MATLAB中，基于當前路況，節點1后選擇的路徑應為節點2（即為甲至節點A）。節點甲至節點A距離為381 m，速度為30 km/h，可以得出節點甲至節點A用時約0.8 min，該時間未超過1 min，所以從節點A開始下一次計算時應仍使用第一分鐘速度矩陣。
經過第六次運算后，節點6后選擇的路徑應為節點8（即為節點O至節點Q）。節點O至節點Q距離為300 m，速度為50 km/h，可以得出節點O至節點Q約用時0.4 min，該時間與前5次運算時間相加為0.8+1.3+0.6+1.8+1.1+0.4=6 min。所以，從節點Q開始計算時應使用第七分鐘速度矩陣。運算至節點Q后，下一節點即為終點乙，距離為700 m，速度30 km/h，用時1.4 min。MATLAB程序第六次運算結果如圖2所示。
4 結語
優化前路徑：甲→A→C→F→J→N→Q→乙，總距離381+335+300+500+900+1 100+700=4 216 m，總用時8.4 min。根據6次運算結果得出，最終優化路徑為甲→A→D→G→K→O→Q→乙，總距離700+300+1 100+900+300+650+381=4 331 m，用時7.4 min。雖然優化后路程較優化前長，但優化后用時更短，更符合本設計目的。運用基于智慧交通的實時數據傳輸與計算，可以在多變的交通環境中找出最快到達目的地的路徑，在應對突發的交通狀況時，可以盡量避免進入交通擁堵路段。由此可見，將智慧交通與多段式選擇的蟻群算法結合運用到路徑選擇問題是行之有效的，能夠給出最短時間路徑規劃方案。
參考文獻
［1］王敬齋.同城配送最短時間最大流量研究［J］.吉林工商學院學報，2015（4）：43-46.
［2］黃宇達，李學威，趙紅專，等.考慮路段擁堵的最短時間流優化問題［J］.計算機與數字工程，2016（9）：1641-1644，1663.
［3］金躍強.靜態場中機器人避障最短時間路徑規劃模型［J］.機床與液壓，2018（15）：88-93.
［4］王玙.基于蟻群算法的航空物流配送路徑優化方法研究［J］.信息技術，2021（11）：76-80.
（編輯 沈 強）
Research on the method of dynamically calculating the shortest time path based on the ant colony algorithm
Wang Jiazhuo
（High-tech College，Liaoning Rail Transit Vocational College， Shenyang 110023， China）
Abstract： With the help of Internet of Things and big data technology， smart transportation could provide people with more intelligent travel path planning services. In the sophisticated and changing urban transportation network， calculating the path with shortest passage time from the starting point to the end point requires the dynamic calculation of the shortest passage time of each path based on the collected road condition information， so as to provide the path planning scheme with shortest time. In this paper， the ant colony algorithm is adopted to study the shortest time path planning problem， and by improving the algorithm， the shortest time path planning calculation method between two points is given. By using Matlab simulation software， the instantiated data is used and the process of dynamically collecting the road condition information and planning the route is simulated. And it is verified that this method is effective.
Key words： intelligent traffic; path calculation; shortest time; Matlab; ant colony algorithm
