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

鄭永玲 白宇 楊楠 蔣順英

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

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

中圖分類號：TP301.6;TP18? ? ? 文獻標識碼：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? 引? 言

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

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

近年來，現有的最快路徑推薦研究主要集中在：（1）貪心算法：如Dijkstra算法、Floyd算法和A*算法等;（2）啟發式算法：如ACO算法，遺傳算法等;（3）神經網絡：如PCNN等。

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

1? 相關工作

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

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

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

最后簡單闡述神經網絡在路徑規劃上的相關應用。徐煒等人根據三維地形，將地勢和障礙物進行幾何化，并根據流場控制方程構建地形函數算法;將地形函數算法與Hopfield神經網絡進行了有機結合[22]。孫藝彬等人基于脈沖耦合神經網絡，將拓撲地圖與PCNN網絡進行結合，并由此設計距離和角度約束得出一種基于定向約束的PCNN網絡的路徑規劃方法[23]。陳志軍等人通過結合模糊神經網絡和遺傳算法建立了一種新的三維路徑規劃方法[24]。金飛虎等人提出利用ACO算法優化Hopfield神經網絡來解決空間機器人多空間站訪問問題[25]。衛玉梁等人針對智能小車全局路徑規劃和路障規避問題，采用RBF（Radial Basis Function）網絡對Q學習算法的動作值函數進行逼近[26]。

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

2? Bi-A*-ACO算法

本節中，提出Bi-A*算法改進ACO算法尋找最快路徑，以提高出租車在最短距離內快速尋找乘客路徑推薦的準確性和有效性;并結合真實路網進行最快路徑推薦。

2.1? 算法概述

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

2.2? 數據處理

在進行最快路徑推薦前，需要構建路網，并對出租車軌跡數據進行過濾無關數據。路網主要是由節點（交叉路口）和路徑組成，本文利用圖論中的帶權無向圖表示路網，本小節先介紹帶權的無向圖，再進行數據處理和路網介紹。

2.2.1? 帶權的無向圖

圖是由頂點集V和頂點間的關系集合E（邊的集合）組成的一種數據結構，用二元組G=（V，E）表示。無向圖G如圖2所示。

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

圖的邊給出相關的數據統稱為權重;權重可以用一個節點和節點間的距離表示，帶有權重的圖稱為網。帶有權重的無向圖如圖3所示，圖中數字表示兩節點之間的權重。

2.2.2? 路網

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

數據預處理主要包括數據過濾、數據提取和路網無向圖。數據過濾是為了過濾GPS數據中的無效數據;數據提取是為了提取空車位置和乘客位置;路網無向圖主要標注出道路交叉點作為無向圖的節點。數據預處理步驟為：

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

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

通過數據預處理得出乘客位置和空車位置，我們在路網中將乘客位置和空車位置作為一個道路節點。如圖5所示。

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

Step3：路網無向圖。通過Step2得到乘客位置和空車位置結合真實路網構建帶權的無向圖G=（V，E），如圖5所示。

2.3? 算法設計

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

傳統ACO算法主要是通過移動概率來發現下一個移動對象，該算法的移動概率主要由當前節點到下一節點的啟發式函數和信息素表示，如式（1）所示：

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

釋放信息素的同時，路網節點間的信息素濃度也在逐漸散發，因此，當螞蟻完成一次循環后，需要實時更新路徑上的信息素濃度，如式（3）所示：

其中，參數ρ（0<ρ<1）為信息素揮發因子;n為螞蟻數量。 為第k只螞蟻在本次循環中的最快距離，作為信息素的更新規則;Δτij為所有螞蟻在當前節點i轉到下一節點j連接路徑上釋放信息素濃度之和，如式（4）所示：

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

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

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

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

Step2：通過使用本次循環的最快路徑改進ACO算法的信息素更新規則。

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

Algorithm1? 最快路徑推薦

Input：路網無向圖

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

2：→ACO算法

3：→ACO算法

4： Bi-A*-ACO算法

5：保存模型

Output：最快路徑推薦

3? 案例研究

通過與傳統ACO算法比較，結合真實出租車軌跡數據驗證所提出的Bi-A*優化的ACO算法對出租車進行最快載客路徑推薦，并對實驗結果進行詳細分析。

3.1? 數據描述

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

本實驗使用14、36個路網節點為實驗數據集，交叉路口（節點）坐標如表2、表3所示。

3.2? 實驗結果

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

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

下面實驗均是利用上述參數作為實驗參數。

當數據集為14個路網節點時，Bi-A*-ACO算法和傳統ACO算法實驗結果如表5所示。

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

為了進一步驗證算法在路徑推薦方面的有效性，通過增加數據集對優化的ACO算法進行有效性驗證。

如表6所示當數據集增加至36個節點后，當起始點分別為1、36;20、7;10，27時，本文提出的Bi-A*-ACO算法比傳統ACO算法在效率方面分別提高了74.4713%、78.5876%、74.1656%;在最快路徑推薦方面，Bi-A*-ACO算法比傳統ACO算法推薦的最快距離分別減少了54.874 1 m、56.478 5 m、21.857 8 m，實驗結果表明，在效率和最快路徑推薦方面Bi-A*-ACO算法明顯優于傳統ACO算法。

4? 結? 論

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

參考文獻：

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

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

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

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

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

[6] 朱永強，孫宗濤.改進蟻群算法在物流機器人路徑規劃中的應用 [J].科學技術與工程，2020，20（30）：12467-12471.

[7] 衣麟卓.海上搜救最優路線規劃模型設計與仿真 [J].艦船科學技術，2020，42（16）：34-36.

[8] 陳建宏，黃曉明.復雜環境下特種車輛應急機動路徑規劃研究 [J].計算機仿真，2020，37（7）：159-162.

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

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

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

[12] 張麗杰，劉建昌，譚樹彬.復雜建筑火災中的人員疏散路徑多目標規劃 [J].東北大學學報（自然科學版），2020，41（6）：761-766.

[13] 王宇，王文浩，徐凡，等.基于改進蟻群算法的植保無人機路徑規劃方法 [J].農業機械學報，2020，51（11）：103-112+92.

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

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

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

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

[18] 張強，陳兵奎，劉小雍，等.基于改進勢場蟻群算法的移動機器人最優路徑規劃 [J].農業機械學報，2019，50（5）：23-32+42.

[19] 杜玉紅，張巖，趙煥峰.基于參數優化蟻群算法的機器人路徑規劃研究 [J].現代制造工程，2020（9）：7-14.

[20] 李憲強，馬戎，張伸，等.蟻群算法的改進設計及在航跡規劃中的應用 [J].航空學報，2020，41（S2）：213-219.

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

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

[23] 孫藝彬，楊慧珍.基于定向約束的脈沖耦合神經網絡路徑規劃 [J].計算機科學，2019，46（S2）：28-32.

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

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

[26] 衛玉梁，靳伍銀.基于神經網絡Q-learning算法的智能車路徑規劃 [J] 火力與指揮控制，2019，44（2）：46-49.

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

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