摘要：智慧交通借助物聯(lián)網(wǎng)技術(shù)和大數(shù)據(jù)技術(shù)，給人們提供了更加智能的出行路徑規(guī)劃服務(wù)。在復(fù)雜多變的城市交通網(wǎng)絡(luò)中，計(jì)算起點(diǎn)到終點(diǎn)的最短通行時(shí)間路徑，需要根據(jù)采集的路況信息數(shù)據(jù)，動(dòng)態(tài)計(jì)算每條路徑的最短通行時(shí)間，從而給出最短時(shí)間到達(dá)的路徑規(guī)劃方案。文章使用蟻群算法對(duì)最短時(shí)間路徑規(guī)劃問題進(jìn)行研究，通過算法改進(jìn)，給出兩點(diǎn)之間時(shí)間最短的路徑規(guī)劃計(jì)算方法，利用MATLAB仿真軟件導(dǎo)入實(shí)例化數(shù)據(jù)，模擬智慧交通動(dòng)態(tài)采集路況信息并規(guī)劃路線的過程，從而驗(yàn)證該方法的有效。

關(guān)鍵詞：智慧交通；路徑計(jì)算；最短時(shí)間；MATLAB；蟻群算法

中圖分類號(hào)：TP399

文獻(xiàn)標(biāo)志碼：A

0 引言

隨著國(guó)家經(jīng)濟(jì)的迅速發(fā)展，人們的收入水平飛速增加，駕駛汽車出行已經(jīng)成為越來越多家庭首要選擇的出行方式。然而，日益增長(zhǎng)的汽車總量給城市交通帶來了巨大壓力，在有限的通行道路資源下，如何根據(jù)實(shí)時(shí)變化的道路通行信息，按需動(dòng)態(tài)規(guī)劃出行路徑，成為人們出行的首要需求。在這種情況下，智慧交通技術(shù)應(yīng)運(yùn)而生，在出行路徑規(guī)劃方面主要借助物聯(lián)網(wǎng)技術(shù)對(duì)道路通行情況進(jìn)行實(shí)時(shí)采集、上報(bào)，利用大數(shù)據(jù)技術(shù)中的特定方法，對(duì)采集上報(bào)的數(shù)據(jù)進(jìn)行分析和計(jì)算，最終給出具體的路徑規(guī)劃方案。

對(duì)于智慧交通的路徑規(guī)劃問題，通常采用蟻群算法對(duì)起止點(diǎn)之間的路徑進(jìn)行遍歷計(jì)算，而原生蟻群算法只能求解最短路徑問題。最短通行路徑和最短通行時(shí)間路徑顯然不是同一個(gè)研究問題，最短通行路徑在動(dòng)態(tài)交通的情況下未必是最短時(shí)間通行路徑。例如，救護(hù)車或其他執(zhí)行特殊任務(wù)的車輛，為了及時(shí)有效地達(dá)成最終任務(wù)，從起點(diǎn)到終點(diǎn)往往不是以最短通行路徑為目標(biāo)，而是以最短通行時(shí)間為目標(biāo)。因此，需要對(duì)蟻群算法模型進(jìn)行改進(jìn)，基于當(dāng)前規(guī)劃的路徑和道路通行速度進(jìn)行動(dòng)態(tài)迭代運(yùn)算，從而解決動(dòng)態(tài)規(guī)劃最短通行時(shí)間路徑的問題。

目前，對(duì)于最短通行時(shí)間路徑規(guī)劃問題的研究成果較多，例如，在生產(chǎn)車間中，通過增加轉(zhuǎn)彎次數(shù)的優(yōu)化路徑設(shè)計(jì)，減少機(jī)器人到達(dá)目的地所需的時(shí)間，從而提高機(jī)器人的工作效率^［1］；針對(duì)交通網(wǎng)絡(luò)系統(tǒng)中路網(wǎng)時(shí)間流問題，引進(jìn)堵塞系數(shù)，構(gòu)造動(dòng)態(tài)時(shí)間函數(shù)，建立在動(dòng)態(tài)堵塞情況下的最短時(shí)間流模型，從而給出最短時(shí)間路徑規(guī)劃方案^［2］；通過構(gòu)建最短時(shí)間—最大流量分析模型，找出配送線路的優(yōu)化途徑，提高物流企業(yè)盈利能力和客服服務(wù)水平等^［3］。本文主要利用改進(jìn)的蟻群算法，結(jié)合實(shí)時(shí)交通通行信息，動(dòng)態(tài)計(jì)算最短通行時(shí)間的路徑規(guī)劃問題。

1 問題分析

我國(guó)急救物資的運(yùn)輸主要根據(jù)貨物的運(yùn)輸距離選擇運(yùn)輸方式。一般來說，急需的貨物而路程較遠(yuǎn)的，多使用航空運(yùn)送，短程可由公路運(yùn)送。城市內(nèi)配送由專門的車輛進(jìn)行緊急運(yùn)輸，因?yàn)閷Ｓ密囕v具有一定的權(quán)限，在城市內(nèi)擁有優(yōu)先通行的權(quán)利。但是，人們普遍忽略了其途經(jīng)路段對(duì)交通的影響，每當(dāng)車輛需要緊急通行的時(shí)候，都會(huì)因?yàn)槠胀ㄜ囕v的堵塞或交通管制而對(duì)部分交通路口產(chǎn)生較大的交通壓力，甚至造成嚴(yán)重堵車。本文主要研究利用智慧交通技術(shù)和蟻群算法，動(dòng)態(tài)規(guī)劃最短通行時(shí)間的路徑問題。

2 算法改進(jìn)

使用蟻群算法，先要對(duì)算法中的參數(shù)設(shè)定初始值。

節(jié)點(diǎn)數(shù)量n=20。節(jié)點(diǎn)數(shù)量就是網(wǎng)絡(luò)模型中的起始點(diǎn)、目標(biāo)點(diǎn)與各路口的數(shù)量，本文以真實(shí)路網(wǎng)情況為基準(zhǔn)，建立了起始點(diǎn)與目標(biāo)點(diǎn)之間的路網(wǎng)模型，確定節(jié)點(diǎn)為20個(gè)。

螞蟻數(shù)量M=50。螞蟻的數(shù)量一般為節(jié)點(diǎn)數(shù)量的2～3倍。本文中的網(wǎng)絡(luò)圖節(jié)點(diǎn)數(shù)值為20，因此取節(jié)點(diǎn)數(shù)量的2.5倍，設(shè)定螞蟻數(shù)量為50個(gè)。

信息激素啟發(fā)因子α=1。

期望啟發(fā)因子β=2。通過大量的試驗(yàn)分析，得出了β通常為0～5，選擇β=2的效果最佳。所以，本文中的β數(shù)值是2。

初始各條道路上的信息素濃度C=0.1。

每只螞蟻所攜帶的信息量Q=100。

信息素?fù)]發(fā)系數(shù)ρ=0.3。

最大的迭代次數(shù)是指在執(zhí)行完指定周期后，蟻群算法會(huì)停止執(zhí)行，并且以目前群中最好的結(jié)果為該問題的最優(yōu)解，MAXNC=200。

下面，改進(jìn)蟻群算法，計(jì)算最短時(shí)間路徑。

在算法開始時(shí)，把 m個(gè)螞蟻隨機(jī)分配到 n個(gè)節(jié)點(diǎn)，每只螞蟻都有一個(gè)禁忌表，其第一個(gè)元素是它目前所處的節(jié)點(diǎn)。此時(shí)，所有路線中的信息素量都是初始值，所有螞蟻都會(huì)憑借剩余的信息素的多少和設(shè)置的啟發(fā)信息選取接下來要前往的節(jié)點(diǎn)。在時(shí)刻t，螞蟻m從節(jié)點(diǎn)i轉(zhuǎn)移到城市j的概率為：

式中，i，j分別為起點(diǎn)與終點(diǎn)；m為螞蟻編號(hào)；t表示時(shí)刻；P^m_ij（t）為t時(shí)刻第m只從 i節(jié)點(diǎn)到 j的螞蟻傳遞的概率^［4］，其數(shù)值越大，螞蟻就越有可能選擇路徑i-j；C_ij（t）為t時(shí)刻該路徑的信息素濃度，初始為0.01^［4］；η_ij（t）為啟發(fā)函數(shù)；C_is（t）為從節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)s的信息素總量；η_is（t）為從節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)s的期望啟發(fā)函數(shù)值；α為信息素啟發(fā)因子；β為期望啟發(fā)因子；A為第k只螞蟻下一步允許選擇的節(jié)點(diǎn)集合。即當(dāng)節(jié)點(diǎn)j屬于集合A時(shí)（說明該節(jié)點(diǎn)尚未被訪問），被選擇的概率為（節(jié)點(diǎn)i到j(luò)路徑上的信息素×節(jié)點(diǎn)i到j(luò)路徑上啟發(fā)式信息值）/（節(jié)點(diǎn)i到s路徑上的信息素×節(jié)點(diǎn)i到s路徑上的啟發(fā)式信息值的總量，s遍歷集合A中所有的節(jié)點(diǎn)）；而當(dāng)節(jié)點(diǎn)j不屬于集合A時(shí)，說明該節(jié)點(diǎn)已經(jīng)被訪問過，被選擇的概率為0。

常規(guī)的以距離最短為目標(biāo)的路徑規(guī)劃，啟發(fā)函數(shù)可以描述為：

式中，d_ij為節(jié)點(diǎn)i和節(jié)點(diǎn)j的路徑i-j的距離。因?yàn)楸疚闹袉l(fā)因子是時(shí)間，所以啟發(fā)函數(shù)應(yīng)改為：

式中V_t為在t時(shí)刻的路況下該路段車輛的速度，啟發(fā)式函數(shù)為螞蟻經(jīng)過i到j(luò)路徑所用的時(shí)間的倒數(shù)。

基于正反饋的蟻群算法，可以在最短的時(shí)間內(nèi)選擇最小的路徑。在最短的時(shí)間路徑上，信息素的濃度越高，所選的可能性就越大。但是，如果信息素濃度太高，就會(huì)喪失啟發(fā)信息的功能，導(dǎo)致蟻群?jiǎn)适阉鹘饪臻g的能力，陷入局部最優(yōu)。該方法通過模擬自然界中信息素的揮發(fā)現(xiàn)象來進(jìn)行信息素的更新。

在（t+n）時(shí)刻，路徑i-j信息素濃度的計(jì)算方法如下：

C_ij（t+n）=（1-ρ）C_ij（t）+ΔC_ij（t）（5）

式中，ρ為揮發(fā)因子；（1-ρ）為信息素保留系數(shù)；C_ij（t）為t時(shí)刻i到j(luò)路徑的信息素濃度；ΔC_ij（t）為完成一輪迭代路徑i-j信息素濃度的增加量。其計(jì)算方法如下：

式中，ΔC^m_ij（t）為第m只螞蟻完成一輪迭代路徑i-j信息素濃度的增加量；M為蟻群規(guī)模。

ΔC^m_ij（t）的計(jì)算方法如下：

式中，Q為完成一輪迭代螞蟻留下的信息素濃度總量；T_m為第m只螞蟻經(jīng)過一輪迭代所通過的路徑的時(shí)間。

3 數(shù)據(jù)驗(yàn)證

從起點(diǎn)開始選擇須經(jīng)過的18個(gè)重要路口，在不同時(shí)間根據(jù)不同的路況來實(shí)時(shí)選擇最優(yōu)路徑。以起點(diǎn)為坐標(biāo)原點(diǎn)，測(cè)量出各個(gè)路口以及終點(diǎn)的X坐標(biāo)和Y坐標(biāo)，利用MATLAB軟件，將起始端和終點(diǎn)段及每個(gè)十字路口的位置坐標(biāo)輸入數(shù)字矩陣，再使用scatter函數(shù)，生成的二維位置如圖1所示。

在MATLAB中，基于當(dāng)前路況，節(jié)點(diǎn)1后選擇的路徑應(yīng)為節(jié)點(diǎn)2（即為甲至節(jié)點(diǎn)A）。節(jié)點(diǎn)甲至節(jié)點(diǎn)A距離為381 m，速度為30 km/h，可以得出節(jié)點(diǎn)甲至節(jié)點(diǎn)A用時(shí)約0.8 min，該時(shí)間未超過1 min，所以從節(jié)點(diǎn)A開始下一次計(jì)算時(shí)應(yīng)仍使用第一分鐘速度矩陣。

經(jīng)過第六次運(yùn)算后，節(jié)點(diǎn)6后選擇的路徑應(yīng)為節(jié)點(diǎn)8（即為節(jié)點(diǎn)O至節(jié)點(diǎn)Q）。節(jié)點(diǎn)O至節(jié)點(diǎn)Q距離為300 m，速度為50 km/h，可以得出節(jié)點(diǎn)O至節(jié)點(diǎn)Q約用時(shí)0.4 min，該時(shí)間與前5次運(yùn)算時(shí)間相加為0.8+1.3+0.6+1.8+1.1+0.4=6 min。所以，從節(jié)點(diǎn)Q開始計(jì)算時(shí)應(yīng)使用第七分鐘速度矩陣。運(yùn)算至節(jié)點(diǎn)Q后，下一節(jié)點(diǎn)即為終點(diǎn)乙，距離為700 m，速度30 km/h，用時(shí)1.4 min。MATLAB程序第六次運(yùn)算結(jié)果如圖2所示。

4 結(jié)語(yǔ)

優(yōu)化前路徑：甲→A→C→F→J→N→Q→乙，總距離381+335+300+500+900+1 100+700=4 216 m，總用時(shí)8.4 min。根據(jù)6次運(yùn)算結(jié)果得出，最終優(yōu)化路徑為甲→A→D→G→K→O→Q→乙，總距離700+300+1 100+900+300+650+381=4 331 m，用時(shí)7.4 min。雖然優(yōu)化后路程較優(yōu)化前長(zhǎng)，但優(yōu)化后用時(shí)更短，更符合本設(shè)計(jì)目的。運(yùn)用基于智慧交通的實(shí)時(shí)數(shù)據(jù)傳輸與計(jì)算，可以在多變的交通環(huán)境中找出最快到達(dá)目的地的路徑，在應(yīng)對(duì)突發(fā)的交通狀況時(shí)，可以盡量避免進(jìn)入交通擁堵路段。由此可見，將智慧交通與多段式選擇的蟻群算法結(jié)合運(yùn)用到路徑選擇問題是行之有效的，能夠給出最短時(shí)間路徑規(guī)劃方案。

參考文獻(xiàn)

［1］王敬齋.同城配送最短時(shí)間最大流量研究［J］.吉林工商學(xué)院學(xué)報(bào)，2015（4）：43-46.

［2］黃宇達(dá)，李學(xué)威，趙紅專，等.考慮路段擁堵的最短時(shí)間流優(yōu)化問題［J］.計(jì)算機(jī)與數(shù)字工程，2016（9）：1641-1644，1663.

［3］金躍強(qiáng).靜態(tài)場(chǎng)中機(jī)器人避障最短時(shí)間路徑規(guī)劃模型［J］.機(jī)床與液壓，2018（15）：88-93.

［4］王玙.基于蟻群算法的航空物流配送路徑優(yōu)化方法研究［J］.信息技術(shù)，2021（11）：76-80.

（編輯 沈 強(qiáng)）

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