鄭永玲 白宇 楊楠 蔣順英

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

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

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

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

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

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

1? 相關(guān)工作

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

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

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

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

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

2? Bi-A*-ACO算法

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

2.1? 算法概述

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

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

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

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

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

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

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

2.2.2? 路網(wǎng)

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

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

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

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

通過數(shù)據(jù)預(yù)處理得出乘客位置和空車位置，我們在路網(wǎng)中將乘客位置和空車位置作為一個道路節(jié)點。如圖5所示。

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

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

2.3? 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

Algorithm1? 最快路徑推薦

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

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

2：→ACO算法

3：→ACO算法

4： Bi-A*-ACO算法

5：保存模型

Output：最快路徑推薦

3? 案例研究

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

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

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

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

3.2? 實驗結(jié)果

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

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

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

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

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

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

如表6所示當(dāng)數(shù)據(jù)集增加至36個節(jié)點后，當(dāng)起始點分別為1、36;20、7;10，27時，本文提出的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，實驗結(jié)果表明，在效率和最快路徑推薦方面Bi-A*-ACO算法明顯優(yōu)于傳統(tǒng)ACO算法。

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

[4] 程林，王美玲，張毅.一種基于SuperMap GIS的改進(jìn)Dijkstra算法 [J].地球信息科學(xué)學(xué)報，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].艦船科學(xué)技術(shù)，2020，42（16）：34-36.

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

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

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

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

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

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

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

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

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

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

[18] 張強(qiáng)，陳兵奎，劉小雍，等.基于改進(jìn)勢場蟻群算法的移動機(jī)器人最優(yōu)路徑規(guī)劃 [J].農(nóng)業(yè)機(jī)械學(xué)報，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è)計及在航跡規(guī)劃中的應(yīng)用 [J].航空學(xué)報，2020，41（S2）：213-219.

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

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

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

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

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

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

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

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