基于Bi-A*的ACO算法的最快路徑推薦

鄭永玲 白宇 楊楠 蔣順英

摘? 要：文章針對(duì)ACO算法收斂速度慢和容易陷入局部最優(yōu)等問(wèn)題，利用Bi-A*算法的代價(jià)估計(jì)函數(shù)優(yōu)化ACO算法的啟發(fā)式函數(shù)，增強(qiáng)算法全局搜索能力;再通過(guò)引入每次循環(huán)得出的最快路徑優(yōu)化ACO算法的信息素更新規(guī)則，加快算法收斂速度;基于Spark結(jié)合真實(shí)的大規(guī)模出租車(chē)軌跡數(shù)據(jù)，將Bi-A*-ACO算法應(yīng)用于最快路徑推薦，實(shí)驗(yàn)結(jié)果表明，Bi-A*-ACO算法比傳統(tǒng)ACO算法更具有有效性和準(zhǔn)確性。

關(guān)鍵詞：Bi-A*;ACO算法;載客路線;信息素;Spark

中圖分類(lèi)號(hào)：TP301.6;TP18? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）22-0074-08

The Fastest Path Recommendation of ACO Algorithm Based on Bi-A*

ZHENG Yongling，BAI Yu，YANG Nan，JIANG Shunying

（School of Data Science and Information Engineering，Guizhou Minzu University，Guiyang? 550025，China）

Abstract：Aiming at the problems of slow convergence of the ACO algorithm and easy to fall into local optimality，the article uses the cost estimation function of the Bi-A* algorithm to optimize the heuristic function of the ACO algorithm to enhance the algorithms global search ability;and then optimize the pheromone update rule of the ACO algorithm by introducing the fastest path obtained in each cycle to speed up the algorithm convergence speed;based on Spark combined with real large-scale taxi trajectory data，the Bi-A*-ACO algorithm is applied to the fastest route recommendation. The experimental results show that the Bi-A*-ACO algorithm is more effective and accurate than the traditional ACO algorithm.

Keywords：Bi-A*;ACO algorithm;passenger route;pheromone;Spark

0? 引? 言

隨著智慧城市和智慧交通不斷發(fā)展，出租車(chē)成為居民日常生活中不可或缺的重要出行工具，由于車(chē)輛需求不斷增加，導(dǎo)致城市交通擁堵、事故頻發(fā)等諸多情況[1]，熟悉城市路網(wǎng)的出租車(chē)司機(jī)可以快速通過(guò)最快路徑找到乘客，而缺乏經(jīng)驗(yàn)的出租車(chē)司機(jī)卻難以找到搭載乘客的最快路線，導(dǎo)致了空載出租車(chē)在盲目巡航過(guò)程中成本增加、交通擁堵和能源浪費(fèi)等問(wèn)題，因此，通過(guò)結(jié)合真實(shí)路網(wǎng)構(gòu)建算法幫助出租車(chē)推薦最快路徑變得十分迫切。就目前來(lái)看，全球定位系統(tǒng)（GPS）相關(guān)技術(shù)已經(jīng)趨于成熟并成為路徑規(guī)劃的重要支撐，通過(guò)出租車(chē)配備的GPS傳感器，可以向數(shù)據(jù)中心實(shí)時(shí)發(fā)送出租車(chē)的地理信息及運(yùn)營(yíng)狀況，保證了數(shù)據(jù)的真實(shí)性和可靠性。

在路徑推薦方面，經(jīng)驗(yàn)豐富的出租車(chē)駕駛員能快速準(zhǔn)確地找到抵達(dá)下一個(gè)目標(biāo)地點(diǎn)的最快路徑，甚至能在高峰時(shí)段有效避開(kāi)擁堵路段，因此其運(yùn)營(yíng)成本也相對(duì)較低。但是，對(duì)于缺乏經(jīng)驗(yàn)的駕駛員來(lái)說(shuō)不能及時(shí)找到快速到達(dá)目標(biāo)點(diǎn)的最快路徑，將導(dǎo)致其單位時(shí)間成本高和盈利低等問(wèn)題。針對(duì)上述問(wèn)題，本文通過(guò)結(jié)合歷史軌跡數(shù)據(jù)和真實(shí)路網(wǎng)進(jìn)行建模，準(zhǔn)確實(shí)現(xiàn)最快路徑推薦，有效幫助出租車(chē)快速抵達(dá)乘客位置，可以解決城市規(guī)劃和緩解交通擁堵等問(wèn)題。

近年來(lái)，現(xiàn)有的最快路徑推薦研究主要集中在：（1）貪心算法：如Dijkstra算法、Floyd算法和A*算法等;（2）啟發(fā)式算法：如ACO算法，遺傳算法等;（3）神經(jīng)網(wǎng)絡(luò)：如PCNN等。

上述研究大部分主要運(yùn)用在機(jī)器人路徑規(guī)劃、AGV路徑規(guī)劃和TSP問(wèn)題等方面，在出租車(chē)最快路徑推薦應(yīng)用相對(duì)較少。為此，作者基于貴州民族大學(xué)海量數(shù)據(jù)統(tǒng)計(jì)與分析方向的研究，針對(duì)傳統(tǒng)ACO算法的缺陷，提出利用Bi-A*算法改進(jìn)傳統(tǒng)的ACO算法，由于單機(jī)環(huán)境下處理大規(guī)模軌跡數(shù)據(jù)存在“內(nèi)存消耗高、I/O開(kāi)銷(xiāo)大、數(shù)據(jù)傳輸耗時(shí)、計(jì)算性能低”等諸多弊端，作者便結(jié)合Spark平臺(tái)進(jìn)行最快路徑推薦，通過(guò)并行算法有效彌補(bǔ)單機(jī)環(huán)境缺陷;數(shù)據(jù)來(lái)源于北京市GPS數(shù)據(jù)和真實(shí)路網(wǎng)節(jié)點(diǎn)數(shù)據(jù)（谷歌地圖）。

1? 相關(guān)工作

本小節(jié)簡(jiǎn)要介紹路徑推薦的相關(guān)工作，并分析所存在的問(wèn)題。車(chē)輛路徑推薦是城市規(guī)劃和資源配置的重要支撐，通過(guò)對(duì)車(chē)輛進(jìn)行最快路徑推薦可以解決城市路網(wǎng)規(guī)劃、交通路線確定等問(wèn)題。

貪心算法：湯紅杰等人利用鄰接表來(lái)存儲(chǔ)Dijkstra算法中的路網(wǎng)圖，并使用二叉堆存儲(chǔ)未到達(dá)節(jié)點(diǎn)得到一種優(yōu)化的Dijkstra算法[2]，鄒益民等人利用幾何方法得出了移動(dòng)機(jī)器人在彎道運(yùn)行過(guò)程中移動(dòng)時(shí)間與過(guò)渡圓弧圓心之間的數(shù)學(xué)關(guān)系，通過(guò)這個(gè)關(guān)系來(lái)改進(jìn)Dijkstra算法以解決機(jī)器人避障問(wèn)題的路徑規(guī)劃[3]，程林等人通過(guò)利用SuperMap GIS平臺(tái)的網(wǎng)絡(luò)編輯功能來(lái)改進(jìn)傳統(tǒng)的Dijkstra算法[4]。李大東等人通過(guò)可視化Dijkstra單向最快路徑規(guī)劃算法將飛行軌跡視為一系列直線和圓弧，利用轉(zhuǎn)彎終點(diǎn)與起點(diǎn)構(gòu)建三圓弧組合實(shí)現(xiàn)避障轉(zhuǎn)彎，在Dijkstra算法中成功引入最小轉(zhuǎn)彎的半徑約束[5]。朱永強(qiáng)等人通過(guò)利用雙向A*算法搜索一條最快路徑作為ACO算法的初始解，然后使用該路徑經(jīng)過(guò)的節(jié)點(diǎn)為中心，線性更新信息素以提高較優(yōu)解路徑ACO算法的信息素濃度，通過(guò)改進(jìn)傳統(tǒng)ACO算法以解決物流機(jī)器人的路徑規(guī)劃[6]。衣麟卓等人利用ACO算法優(yōu)化Dijkstra方法，求解多條件約束下海上搜救最快路徑的全局最優(yōu)解[7]。陳建宏等人考慮了應(yīng)急行動(dòng)過(guò)程中路徑規(guī)劃的目標(biāo)條件和約束條件，通過(guò)在Dijkstra算法和A*算法中設(shè)計(jì)不同目標(biāo)條件下的代價(jià)函數(shù)，并使用PostGIS數(shù)據(jù)庫(kù)構(gòu)建開(kāi)發(fā)了機(jī)動(dòng)路徑規(guī)劃計(jì)算軟件[8]。陳敏等人將滿(mǎn)足車(chē)輛運(yùn)動(dòng)學(xué)約束的最快路徑作為距離度量引入RRT算法，這樣便于求解最近鄰搜索中的最快路徑[9]。王磊等人通過(guò)尋找最快路徑必經(jīng)節(jié)點(diǎn)對(duì)A*算法的搜索方向進(jìn)行約束，然后再對(duì)最快路徑段進(jìn)行組合得到最終的最快路徑推薦[10]。張丹紅等人為了獲取兩節(jié)點(diǎn)間更快的可行路徑，使用多方位A*算法的搜索結(jié)果構(gòu)建出任意兩個(gè)巡邏點(diǎn)間的最快路徑網(wǎng)絡(luò)，其次，利用最快路徑網(wǎng)絡(luò)構(gòu)建多點(diǎn)巡邏路徑規(guī)劃的目標(biāo)函數(shù)，并使用ACO算法求解目標(biāo)函數(shù)的全局最優(yōu)解[11]。

啟發(fā)式算法：張麗杰等人通過(guò)優(yōu)化自適應(yīng)果蠅算法，實(shí)現(xiàn)節(jié)點(diǎn)和路徑容量受限的動(dòng)態(tài)疏散路徑規(guī)劃[12]。王宇等人提出一種適用于復(fù)雜多邊形邊界與內(nèi)部障礙物的三維作業(yè)區(qū)域的ACO算法的植保無(wú)人機(jī)路徑規(guī)劃方法[13]。李嘉偉等人通過(guò)利用廣度優(yōu)先搜索枚舉SRIO網(wǎng)絡(luò)中的節(jié)點(diǎn)構(gòu)建網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑢⒙酚商鴶?shù)作為路由的成本，提出一種負(fù)載均衡最快路徑路由算法[14]。王杰等人結(jié)合考慮交通狀況、服務(wù)人口和現(xiàn)有公交線網(wǎng)布局等因素提出了一種公交線路規(guī)劃約束模型[15]，袁佳泉等人通過(guò)使用Dijkstra算法獲得巡檢點(diǎn)間的最快路徑，然后通過(guò)該算法得到的路徑構(gòu)建無(wú)向圖，最后利用模擬退火ACO雙層啟發(fā)式算法求解全局最優(yōu)解[16]。劉建仁通過(guò)分析城市物流配送過(guò)程中路徑規(guī)劃的影響因子，然后建立相關(guān)的約束條件，結(jié)合影響因子和約束條件構(gòu)建路徑規(guī)劃的目標(biāo)函數(shù)，最后利用ACO算法尋找目標(biāo)函數(shù)的最優(yōu)路徑[17]。張強(qiáng)等人通過(guò)利用障礙物檢測(cè)算法識(shí)別有效路徑中間點(diǎn)的障礙物，然后結(jié)合引力場(chǎng)和邊界條件推薦起點(diǎn)到中間點(diǎn)的局部路徑，通過(guò)將中間點(diǎn)作為新的起點(diǎn)，進(jìn)行反復(fù)迭代，直到起點(diǎn)與終點(diǎn)重合[18]。杜玉紅等人對(duì)粒子群算法的動(dòng)態(tài)慣性權(quán)重調(diào)整策略和改進(jìn)的ACO算法的信息素更新規(guī)則進(jìn)行了一個(gè)有機(jī)融合[19]。李憲強(qiáng)等人通過(guò)結(jié)合ACO算法與人工勢(shì)場(chǎng)算法，提出了一種新的航跡規(guī)劃尋優(yōu)算法[20]。胡春陽(yáng)等人引入頭尾搜索機(jī)制和獎(jiǎng)懲因子與信息素最大最小閾值信息素進(jìn)行獎(jiǎng)勵(lì)，然后在ACO算法中使用遺傳算法變異因子，有效解決了ACO算法的陷入局部最優(yōu)和收斂速度慢等問(wèn)題[21]。

最后簡(jiǎn)單闡述神經(jīng)網(wǎng)絡(luò)在路徑規(guī)劃上的相關(guān)應(yīng)用。徐煒等人根據(jù)三維地形，將地勢(shì)和障礙物進(jìn)行幾何化，并根據(jù)流場(chǎng)控制方程構(gòu)建地形函數(shù)算法;將地形函數(shù)算法與Hopfield神經(jīng)網(wǎng)絡(luò)進(jìn)行了有機(jī)結(jié)合[22]。孫藝彬等人基于脈沖耦合神經(jīng)網(wǎng)絡(luò)，將拓?fù)涞貓D與PCNN網(wǎng)絡(luò)進(jìn)行結(jié)合，并由此設(shè)計(jì)距離和角度約束得出一種基于定向約束的PCNN網(wǎng)絡(luò)的路徑規(guī)劃方法[23]。陳志軍等人通過(guò)結(jié)合模糊神經(jīng)網(wǎng)絡(luò)和遺傳算法建立了一種新的三維路徑規(guī)劃方法[24]。金飛虎等人提出利用ACO算法優(yōu)化Hopfield神經(jīng)網(wǎng)絡(luò)來(lái)解決空間機(jī)器人多空間站訪問(wèn)問(wèn)題[25]。衛(wèi)玉梁等人針對(duì)智能小車(chē)全局路徑規(guī)劃和路障規(guī)避問(wèn)題，采用RBF（Radial Basis Function）網(wǎng)絡(luò)對(duì)Q學(xué)習(xí)算法的動(dòng)作值函數(shù)進(jìn)行逼近[26]。

綜上所述，貪心算法的結(jié)構(gòu)較為簡(jiǎn)單，但在大數(shù)據(jù)集下算法效率較低;而啟發(fā)式算法能有效地提高彌補(bǔ)貪心算法的運(yùn)行效率，準(zhǔn)確實(shí)現(xiàn)最快路徑推薦，但存在容易受到參數(shù)影響而陷入局部最優(yōu)、收斂速度較慢等缺點(diǎn);神經(jīng)網(wǎng)絡(luò)受網(wǎng)絡(luò)的深度和復(fù)雜程度的影響，計(jì)算代價(jià)也比傳統(tǒng)算法高。貪心算法是最早運(yùn)用于路徑推薦的算法，但啟發(fā)式算法的發(fā)展逐漸取代了貪心算法，因此，就目前來(lái)看，在路徑推薦方面啟發(fā)式算法運(yùn)用較多，但都是運(yùn)用在機(jī)器人、AGV和TSP問(wèn)題，在出租車(chē)路徑推薦方面運(yùn)用較少。因此，通過(guò)利用Bi-A*算法和最快路徑更新規(guī)則有效彌補(bǔ)ACO算法的缺陷。最快路徑推薦主要是通過(guò)歷史數(shù)據(jù)獲取空車(chē)位置和乘客位置，然后將空車(chē)位置和乘客位置加入路網(wǎng)節(jié)點(diǎn)，然后對(duì)節(jié)點(diǎn)進(jìn)行路徑推薦。針對(duì)ACO算法容收斂速度慢和容易陷入局部最優(yōu)等問(wèn)題，使用Bi-A*算法的代價(jià)估計(jì)函數(shù)優(yōu)傳統(tǒng)化ACO算法的啟發(fā)式函數(shù)，增強(qiáng)ACO算法的全局搜索能力，最后利用本次循環(huán)得到的最快路徑改進(jìn)信息素的更新規(guī)則，加快了ACO算法收斂速度，由實(shí)驗(yàn)結(jié)果可得，Bi-A*-ACO算法比傳統(tǒng)ACO算法在最快路徑推薦具有更好的準(zhǔn)確性。

2? Bi-A*-ACO算法

本節(jié)中，提出Bi-A*算法改進(jìn)ACO算法尋找最快路徑，以提高出租車(chē)在最短距離內(nèi)快速尋找乘客路徑推薦的準(zhǔn)確性和有效性;并結(jié)合真實(shí)路網(wǎng)進(jìn)行最快路徑推薦。

2.1? 算法概述

如圖1所示，基于Bi-A*算法改進(jìn)ACO算法的最快路徑推薦方法主要包含數(shù)據(jù)預(yù)處理、數(shù)據(jù)建模和算法實(shí)現(xiàn)三個(gè)步驟，在數(shù)據(jù)預(yù)處理中，通過(guò)現(xiàn)有的移動(dòng)軌跡大數(shù)據(jù)提取出乘客位置和空車(chē)位置;在數(shù)據(jù)建模中，Bi-A*算法優(yōu)化ACO算法的啟發(fā)式函數(shù);在模型實(shí)現(xiàn)中，通過(guò)結(jié)合真實(shí)北京路網(wǎng)進(jìn)行最快路徑推薦，以驗(yàn)證最快路徑推薦的有效性和準(zhǔn)確性。

2.2? 數(shù)據(jù)處理

在進(jìn)行最快路徑推薦前，需要構(gòu)建路網(wǎng)，并對(duì)出租車(chē)軌跡數(shù)據(jù)進(jìn)行過(guò)濾無(wú)關(guān)數(shù)據(jù)。路網(wǎng)主要是由節(jié)點(diǎn)（交叉路口）和路徑組成，本文利用圖論中的帶權(quán)無(wú)向圖表示路網(wǎng)，本小節(jié)先介紹帶權(quán)的無(wú)向圖，再進(jìn)行數(shù)據(jù)處理和路網(wǎng)介紹。

2.2.1? 帶權(quán)的無(wú)向圖

圖是由頂點(diǎn)集V和頂點(diǎn)間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，用二元組G=（V，E）表示。無(wú)向圖G如圖2所示。

頂點(diǎn)集V=（v1，v2，v3，v4），邊集E=（e12，e13，e14，e21，e23，e24，e31，e32，e34，e41，e42，e43）。

圖的邊給出相關(guān)的數(shù)據(jù)統(tǒng)稱(chēng)為權(quán)重;權(quán)重可以用一個(gè)節(jié)點(diǎn)和節(jié)點(diǎn)間的距離表示，帶有權(quán)重的圖稱(chēng)為網(wǎng)。帶有權(quán)重的無(wú)向圖如圖3所示，圖中數(shù)字表示兩節(jié)點(diǎn)之間的權(quán)重。

2.2.2? 路網(wǎng)

當(dāng)GPS設(shè)備故障、出租車(chē)司機(jī)出現(xiàn)錯(cuò)誤操作或信號(hào)延遲等情況時(shí)，可能造成出租車(chē)GPS信息錯(cuò)誤，例如：當(dāng)出租車(chē)途經(jīng)隧道時(shí)信號(hào)較弱，導(dǎo)致了出租車(chē)發(fā)送消息延遲，出租車(chē)經(jīng)緯度出現(xiàn)偏差等情況，一些駕駛員為了在休息時(shí)免受打擾，故意將GPS運(yùn)營(yíng)狀態(tài)設(shè)為載客狀態(tài)，但出租車(chē)實(shí)際為空載狀態(tài)。因此，為了提高模型的準(zhǔn)確性和可靠性，需要實(shí)施數(shù)據(jù)預(yù)處理剔除無(wú)效和錯(cuò)誤數(shù)據(jù)。具體流程如圖4（a）、圖4（b）所示。

數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)過(guò)濾、數(shù)據(jù)提取和路網(wǎng)無(wú)向圖。數(shù)據(jù)過(guò)濾是為了過(guò)濾GPS數(shù)據(jù)中的無(wú)效數(shù)據(jù);數(shù)據(jù)提取是為了提取空車(chē)位置和乘客位置;路網(wǎng)無(wú)向圖主要標(biāo)注出道路交叉點(diǎn)作為無(wú)向圖的節(jié)點(diǎn)。數(shù)據(jù)預(yù)處理步驟為：

Step1：數(shù)據(jù)過(guò)濾。通過(guò)讀取HDFS文件中的數(shù)據(jù)，將數(shù)據(jù)轉(zhuǎn)換為Spark中的彈性分布數(shù)據(jù)集（RDD），再對(duì)RDD進(jìn)行分片，過(guò)濾掉無(wú)效數(shù)據(jù)，然后提取出所需要的字段（出租車(chē)ID、運(yùn)營(yíng)狀態(tài)、時(shí)間、經(jīng)度、緯度），按照出租車(chē)ID排序。

Step2：數(shù)據(jù)提取。根據(jù)Step1得出的結(jié)果尋找出相同出租車(chē)ID，分別提取運(yùn)營(yíng)狀態(tài)連續(xù)為0（空車(chē)）、1（載客）、1（載客）的數(shù)據(jù)序列（運(yùn)營(yíng)狀態(tài)連續(xù)為011表示一個(gè)載客事件發(fā)生）和運(yùn)營(yíng)狀態(tài)連續(xù)為1（載客）、1（載客）、0（空車(chē)）的數(shù)據(jù)序列（運(yùn)營(yíng)狀態(tài)連續(xù)為110表示一個(gè)下客事件發(fā)生），本文保留第二個(gè)運(yùn)營(yíng)狀態(tài)為1（乘客位置）和第二個(gè)運(yùn)營(yíng)狀態(tài)為0（空車(chē)位置）的出租車(chē)ID、運(yùn)營(yíng)狀態(tài)、時(shí)間、經(jīng)度、緯度，得出乘客坐標(biāo)和空車(chē)坐標(biāo)。

通過(guò)數(shù)據(jù)預(yù)處理得出乘客位置和空車(chē)位置，我們?cè)诼肪W(wǎng)中將乘客位置和空車(chē)位置作為一個(gè)道路節(jié)點(diǎn)。如圖5所示。

圖5中圓點(diǎn)為交叉路口，將乘客位置和空車(chē)位置添加在帶權(quán)的有向圖的節(jié)點(diǎn)集中并將其看為一個(gè)節(jié)點(diǎn)，權(quán)重主要是利用兩個(gè)相連節(jié)點(diǎn)間的球面坐標(biāo)距離作為帶權(quán)有向圖的權(quán)重。

Step3：路網(wǎng)無(wú)向圖。通過(guò)Step2得到乘客位置和空車(chē)位置結(jié)合真實(shí)路網(wǎng)構(gòu)建帶權(quán)的無(wú)向圖G=（V，E），如圖5所示。

2.3? 算法設(shè)計(jì)

ACO算法由Dorigo等人于1991年在第一屆歐洲人工生命會(huì)議上提出，是一種用來(lái)尋找優(yōu)化路徑的概率型算法[27]。ACO算法本質(zhì)上是一種啟發(fā)式全局優(yōu)化，該算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征。

傳統(tǒng)ACO算法主要是通過(guò)移動(dòng)概率來(lái)發(fā)現(xiàn)下一個(gè)移動(dòng)對(duì)象，該算法的移動(dòng)概率主要由當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的啟發(fā)式函數(shù)和信息素表示，如式（1）所示：

其中，ηie（t）為當(dāng)前節(jié)點(diǎn)i與終點(diǎn)e之間的啟發(fā)函數(shù)，是利用A*算法的代價(jià)估計(jì)函數(shù)代替原始的啟發(fā)式函數(shù);dij為當(dāng)前節(jié)點(diǎn)i和下一節(jié)點(diǎn)j之間的球面距離，且dij=Rθ= Rarccos[cos（xi1-xj1）cos（xi2）cos（xj2）+sin（xi2）sin（xj2）];allowk（k=1，2，…，n）為螞蟻k待訪問(wèn)路網(wǎng)節(jié)點(diǎn)的集合;τij（t）為從路網(wǎng)節(jié)點(diǎn)i轉(zhuǎn)移到路網(wǎng)節(jié)點(diǎn)j的信息素濃度;α為信息素的重要程度，其值越大，信息素的濃度在概率轉(zhuǎn)移中起的占比越大;β為啟發(fā)函數(shù)的重要程度，其值越大，啟發(fā)函數(shù)在概率轉(zhuǎn)移中的占比越大，即螞蟻會(huì)以最近的路網(wǎng)節(jié)點(diǎn)為最佳轉(zhuǎn)移節(jié)點(diǎn)。

釋放信息素的同時(shí)，路網(wǎng)節(jié)點(diǎn)間的信息素濃度也在逐漸散發(fā)，因此，當(dāng)螞蟻完成一次循環(huán)后，需要實(shí)時(shí)更新路徑上的信息素濃度，如式（3）所示：

其中，參數(shù)ρ（0<ρ<1）為信息素?fù)]發(fā)因子;n為螞蟻數(shù)量。 為第k只螞蟻在本次循環(huán)中的最快距離，作為信息素的更新規(guī)則;Δτij為所有螞蟻在當(dāng)前節(jié)點(diǎn)i轉(zhuǎn)到下一節(jié)點(diǎn)j連接路徑上釋放信息素濃度之和，如式（4）所示：

其中，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量;dbest為第k只螞蟻本次循環(huán)得出的最佳距離長(zhǎng)度。

Bi-A*-ACO算法流程圖如圖5所示，本流程中利用雙向的A*算法主要是為了增強(qiáng)算法運(yùn)行效率。

如圖5所示，Bi-A*-ACO算法的實(shí)現(xiàn)過(guò)程主要由以下三個(gè)步驟組成：

Step1：通過(guò)Bi-A*算法獲取最小代價(jià)函數(shù)作為ACO算法的啟發(fā)式函數(shù)。

Step2：通過(guò)使用本次循環(huán)的最快路徑改進(jìn)ACO算法的信息素更新規(guī)則。

Step3：通過(guò)Step1和Step2得到的Bi-A*-ACO算法計(jì)算下一個(gè)節(jié)點(diǎn)的選擇概率，詳細(xì)的算法偽代碼為：

Algorithm1? 最快路徑推薦

Input：路網(wǎng)無(wú)向圖

1： Bi-A*→f（i）=dij+dje

2：→ACO算法

3：→ACO算法

4： Bi-A*-ACO算法

5：保存模型

Output：最快路徑推薦

3? 案例研究

通過(guò)與傳統(tǒng)ACO算法比較，結(jié)合真實(shí)出租車(chē)軌跡數(shù)據(jù)驗(yàn)證所提出的Bi-A*優(yōu)化的ACO算法對(duì)出租車(chē)進(jìn)行最快載客路徑推薦，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。

3.1? 數(shù)據(jù)描述

本案例使用的數(shù)據(jù)來(lái)源于2012年11月12 000輛出租車(chē)（北京市）所產(chǎn)生的GPS軌跡數(shù)據(jù)。該數(shù)據(jù)集由9億多條GPS記錄組成，如圖6所示。

本實(shí)驗(yàn)使用14、36個(gè)路網(wǎng)節(jié)點(diǎn)為實(shí)驗(yàn)數(shù)據(jù)集，交叉路口（節(jié)點(diǎn)）坐標(biāo)如表2、表3所示。

3.2? 實(shí)驗(yàn)結(jié)果

通過(guò)大量的實(shí)驗(yàn)將ACO算法的參數(shù)初始化，如表4所示。

其中，n為螞蟻數(shù)量，α為信息素的重要程度，β為啟發(fā)函數(shù)的重要程度，參數(shù)ρ（0<ρ<1）為信息素?fù)]發(fā)因子，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量。

下面實(shí)驗(yàn)均是利用上述參數(shù)作為實(shí)驗(yàn)參數(shù)。

當(dāng)數(shù)據(jù)集為14個(gè)路網(wǎng)節(jié)點(diǎn)時(shí)，Bi-A*-ACO算法和傳統(tǒng)ACO算法實(shí)驗(yàn)結(jié)果如表5所示。

通過(guò)表5得出在相同參數(shù)下，利用Bi-A*算法優(yōu)化的ACO算法在效率方面明顯高于傳統(tǒng)的ACO算法，由于數(shù)據(jù)集較少，在相同起始點(diǎn)時(shí)，Bi-A*-ACO算法雖然和傳統(tǒng)ACO算法推薦的最快路徑一致，但提出的算法在效率方面比傳統(tǒng)ACO算法分別提高了54.573 7%、47.050 8%和61.568 8%。

為了進(jìn)一步驗(yàn)證算法在路徑推薦方面的有效性，通過(guò)增加數(shù)據(jù)集對(duì)優(yōu)化的ACO算法進(jìn)行有效性驗(yàn)證。

如表6所示當(dāng)數(shù)據(jù)集增加至36個(gè)節(jié)點(diǎn)后，當(dāng)起始點(diǎn)分別為1、36;20、7;10，27時(shí)，本文提出的Bi-A*-ACO算法比傳統(tǒng)ACO算法在效率方面分別提高了74.4713%、78.5876%、74.1656%;在最快路徑推薦方面，Bi-A*-ACO算法比傳統(tǒng)ACO算法推薦的最快距離分別減少了54.874 1 m、56.478 5 m、21.857 8 m，實(shí)驗(yàn)結(jié)果表明，在效率和最快路徑推薦方面Bi-A*-ACO算法明顯優(yōu)于傳統(tǒng)ACO算法。

4? 結(jié)? 論

實(shí)驗(yàn)研究發(fā)現(xiàn)，本文提出的Bi-A*-ACO算法在14個(gè)路網(wǎng)節(jié)點(diǎn)數(shù)據(jù)集下，固定相同起始點(diǎn)時(shí)，優(yōu)化算法和傳統(tǒng)算法最快路徑推薦的準(zhǔn)確性一致，但是運(yùn)行時(shí)間上優(yōu)化算法比傳統(tǒng)算法明顯減少了一半，當(dāng)數(shù)據(jù)集增加至36個(gè)路網(wǎng)節(jié)點(diǎn)時(shí)，Bi-A*-ACO算法不管是在運(yùn)行效率方面還是最快路徑推薦方面明顯都比傳統(tǒng)ACO算法效率、準(zhǔn)確性更高。在未來(lái)工作中我們將加入道路好壞、交通狀況對(duì)最快路徑推薦的影響。

參考文獻(xiàn)：

[1] 王迎，趙建軍，李興菊，等.基于交通大數(shù)據(jù)的車(chē)輛行駛路徑規(guī)劃綜述 [J].軟件導(dǎo)刊，2020，19（10）：50-54.

[2] 湯紅杰，王鼎，皇攀凌，等.優(yōu)化Dijkstra算法在工廠內(nèi)物流AGV路徑規(guī)劃的研究 [J].機(jī)械設(shè)計(jì)與制造，2018（S1）：117-120.

[3] 鄒益民，高陽(yáng)，高碧悅.一種基于Dijkstra算法的機(jī)器人避障問(wèn)題路徑規(guī)劃 [J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013，43（10）：111-118.

[4] 程林，王美玲，張毅.一種基于SuperMap GIS的改進(jìn)Dijkstra算法 [J].地球信息科學(xué)學(xué)報(bào)，2010，12（5）：649-654.

[5] 李大東，孫秀霞，彭建亮，等.基于可視圖法的改進(jìn)Dijkstra算法 [J].電光與控制，2010，17（3）：40-43.

[6] 朱永強(qiáng)，孫宗濤.改進(jìn)蟻群算法在物流機(jī)器人路徑規(guī)劃中的應(yīng)用 [J].科學(xué)技術(shù)與工程，2020，20（30）：12467-12471.

[7] 衣麟卓.海上搜救最優(yōu)路線規(guī)劃模型設(shè)計(jì)與仿真 [J].艦船科學(xué)技術(shù)，2020，42（16）：34-36.

[8] 陳建宏，黃曉明.復(fù)雜環(huán)境下特種車(chē)輛應(yīng)急機(jī)動(dòng)路徑規(guī)劃研究 [J].計(jì)算機(jī)仿真，2020，37（7）：159-162.

[9] 陳敏，李笑，武交峰，等.基于距離度量學(xué)習(xí)的智能車(chē)輛路徑規(guī)劃 [J].計(jì)算機(jī)仿真，2020，37（7）：163-167.

[10] 王磊，孫力帆.引入必經(jīng)點(diǎn)約束的路徑規(guī)劃算法研究 [J].計(jì)算機(jī)工程與應(yīng)用，2020，56（21）：25-29.

[11] 張丹紅，陳文文，張華軍，等.A*算法與蟻群算法相結(jié)合的無(wú)人艇巡邏路徑規(guī)劃 [J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，48（6）：13-18.

[12] 張麗杰，劉建昌，譚樹(shù)彬.復(fù)雜建筑火災(zāi)中的人員疏散路徑多目標(biāo)規(guī)劃 [J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，41（6）：761-766.

[13] 王宇，王文浩，徐凡，等.基于改進(jìn)蟻群算法的植保無(wú)人機(jī)路徑規(guī)劃方法 [J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2020，51（11）：103-112+92.

[14] 李嘉偉，張激，趙俊才，等.一種SRIO網(wǎng)絡(luò)負(fù)載均衡最短路徑路由算法 [J].計(jì)算機(jī)工程，2020，46（3）：214-221+228.

[15] 王杰，楊坤，孫峰，等.一種基于GIS的公交線路規(guī)劃方法 [J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，44（5）：1269-1275.

[16] 袁佳泉，李勝，吳益飛，等.基于模擬退火蟻群算法的機(jī)器人路徑規(guī)劃方法 [J].計(jì)算機(jī)仿真，2019，36（10）：329-333.

[17] 劉建仁.考慮交通擁堵的城市物流配送路徑規(guī)劃研究 [J].現(xiàn)代電子技術(shù)，2020，43（23）：116-119+123.

[18] 張強(qiáng)，陳兵奎，劉小雍，等.基于改進(jìn)勢(shì)場(chǎng)蟻群算法的移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃 [J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2019，50（5）：23-32+42.

[19] 杜玉紅，張巖，趙煥峰.基于參數(shù)優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃研究 [J].現(xiàn)代制造工程，2020（9）：7-14.

[20] 李憲強(qiáng)，馬戎，張伸，等.蟻群算法的改進(jìn)設(shè)計(jì)及在航跡規(guī)劃中的應(yīng)用 [J].航空學(xué)報(bào)，2020，41（S2）：213-219.

[21] 胡春陽(yáng)，姜平，周根榮.改進(jìn)蟻群算法在AGV路徑規(guī)劃中的應(yīng)用 [J].計(jì)算機(jī)工程與應(yīng)用，2020，56（8）：270-278.

[22] 徐煒，周蘭鳳，章民融.三維地形下基于Hopfield神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法 [J].計(jì)算機(jī)應(yīng)用與軟件，2019，36（10）：113-116+144.

[23] 孫藝彬，楊慧珍.基于定向約束的脈沖耦合神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃 [J].計(jì)算機(jī)科學(xué)，2019，46（S2）：28-32.

[24] 陳志軍，曾蒸.基于模糊神經(jīng)網(wǎng)絡(luò)和遺傳算法的機(jī)器人三維路徑規(guī)劃 [J].重慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，35（1）：93-99.

[25] 金飛虎，郭琦.基于蟻群算法的Hopfield神經(jīng)網(wǎng)絡(luò)在多空間站路徑規(guī)劃的應(yīng)用研究 [J].計(jì)算機(jī)應(yīng)用研究，2010，27（1）：51-53.

[26] 衛(wèi)玉梁，靳伍銀.基于神經(jīng)網(wǎng)絡(luò)Q-learning算法的智能車(chē)路徑規(guī)劃 [J] 火力與指揮控制，2019，44（2）：46-49.

[27] 張軍，詹志輝.計(jì)算智能 [M].北京：清華大學(xué)出版社，2009.

作者簡(jiǎn)介：鄭永玲（1995—），女，漢族，貴州畢節(jié)人，碩士研究生，研究方向：海量數(shù)據(jù)統(tǒng)計(jì)與分析;白宇（1994—），女，漢族，貴州仁懷人，碩士研究生，研究方向：海量數(shù)據(jù)統(tǒng)計(jì)與分析;楊楠（1997—），女，漢族，貴州盤(pán)縣人，碩士研究生，研究方向：海量數(shù)據(jù)統(tǒng)計(jì)與分析;蔣順英（1996—），女，漢族，貴州興義人，碩士研究生，研究方向：海量數(shù)據(jù)統(tǒng)計(jì)與分析。