基于交通擁堵指數的蟻群改進算法研究

李梟　趙文君

摘要：隨著城市道路規模的不斷擴大，在車輛路線優化問題上，大部分學者只考慮距離或者費用等單目標，往往忽略了實際交通道路情況。提出了一種基于實際道路交通情況的路線優化改進蟻群算法，首先根據實際交通道路生成交通網絡圖，然后在信息素初始化時根據各路段的交通擁堵指數加入對應的交通擁堵權重；其次在信息揮發系數中加入車流量系數；最后在轉移概率中加入道路暢通強度加強螞蟻的選擇。Matlab模擬實驗證明，帶交通擁堵指數優化后的蟻群算法能更好地符合實際道路情況，解決車輛路線優化問題。

關鍵詞：車輛路線優化；交通擁堵指數；蟻群算法；Matlab

DOIDOI：10.11907/rjdk.172899

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）003007404

英文摘要Abstract：In view of the advancement of new urbanization in China and the continuous expansion of urban road scale， most scholars have only considered the single target of distance or cost， and often neglected the actual traffic road. Ant colony optimization algorithm for route optimization based on actual road traffic. First， according to the traffic congestion index， the traffic congestion weight is added when the pheromone is initialized. Secondly， the traffic flow coefficient is added to the information volatility coefficient. Finally， the road smoothing strength is added to the transformation probability. The simulation results show that the ant colony algorithm with traffic congestion index can be used to solve the problem of vehicle route optimization.

英文關鍵詞Key Words：optimization of vehicle routes； traffic jam index； ant colony algorithm； Matlab

0引言

我國新型城鎮化進程加快，城市交通道路變得越來越擁堵，城市居民出行、公交調度、物流轉運成為大問題，發展智慧交通已經成為解決交通擁擠的必要措施。本文在求解銷售員問題（Traveling Salesman Problem，TSP）、郵政員問題（Chinese Postman Problem，CPP）、車輛路線問題（Vehicle Routing Problem，VRP）等NP難題的背景下，研究一種基于現實交通道路的多目標優化車輛路線問題。車輛路線問題（VRP）最早由Dantzig和Ramser于1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗時最少等目的[1]。

目前常用的最優路徑求解方法有BellmanFord算法、Dijkstra算法、A*算法及蟻群算法（ACO）、遺傳算法（GA）、禁忌搜索算法（TS）、粒子群算法（PSO）、模擬退火算法（SA）、人工神經網絡（ANN）等啟發算法。

最近幾年來，蟻群算法的研究取得了很多成果。夏小云、周育人[2]回顧了蟻群優化算法的收斂性分析、時間復雜度分析與近似性能分析等理論研究進展，分析了其理論研究對象從簡單的擬布爾函數轉為組合優化問題以及實際應用問題。何小鋒、馬良[3]針對蟻群算法求解VRPTW問題時易于陷入局部最優和收斂速度滿的問題，提出了一種VRPTW的量子蟻群算法。文獻[4]中提出“最大最小蟻群系統”MMAS（MaxMin Ant System），將信息素濃度控制在一定范圍內變化，并對信息素濃度設置了上下限。文獻[5]提出了一種將蟻群算法選擇策略參數設置為迭代次數的分段函數蟻群算法。文獻[6]提出帶獎懲的蟻群算法，對較優解路徑信息素濃度進行獎勵，較差解路徑信息素濃度給予懲罰，然而這兩種算法的參數設置都根據經驗確定，難以準確引導信息素的更新。文獻[7]討論了參數設置對蟻群算法性能的影響，但未提出有效的參數選擇機制。文獻[8]提出增加初始信息素濃度方向性，并在全局更新中引入動態因子的新穎算法，但其對方向引導和動態因子的選用仍需進一步優化。在對傳統車輛路徑求解搜索時間過長、求解質量不高或得不到最優解等情況下，文獻[9]在一般物流配送路徑問題處理方法和數學模型的基礎上，提出了在限量車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）中用改進的蟻群算法優化求解物流的配送路徑。

在這些研究的基礎上，本文根據城市道路擁堵情況，把交通擁堵指數運用到蟻群算法中，提出了一種基于交通擁堵指數的蟻群改進算法，該算法對信息素的初始化設置、信息素揮發系數的設置和螞蟻轉移概率的計算進行了改進，在符合實際道路的情況下，提高了最優路徑的搜索效率。

1蟻群算法簡述

蟻群算法（Ant Colony Algorithm，ACA）最早由意大利學者Marco.Dorigo于1991年在博士論文中提出，該算法模擬了自然界中螞蟻的覓食行為[10]。螞蟻在尋找食物源時會在其經過的路徑上釋放一種叫信息素的外激素，并能感知其他伙伴釋放的信息素。因此信息素濃度的高低就可以近似表征為路徑的遠近，信息素濃度越高，表示對應的路徑距離越短。一般情況下螞蟻會以較大的概率優先選擇信息素濃度較高的路徑，并釋放一定量的信息素， 以增強該條路徑上的信息素濃度，這樣就形成一個正反饋。隨著時間的推進，較短路徑上的信息素逐漸積累增多，選擇該路徑的螞蟻個數也越來越多，最終螞蟻能夠找到一條從巢穴到食物源的最佳路徑，即距離最短。同時生物學家發現，路徑上的信息素濃度會隨著時間的推移而逐漸衰減。螞蟻覓食過程如圖1所示。

目前，蟻群算法廣泛應用于多種求組合最優化問題，例如車輛調度、通訊網絡中路由、容量平衡、圖著色、工件排序問題等。

1.1蟻群算法優缺點

蟻群算法作為一種仿生進化算法具有一些優點：①每只螞蟻在搜索過程中彼此獨立，相互通過信息素的釋放改變周圍的環境，并且個體間能通過環境中的信息素進行間接地通訊；②搜尋過程受正反饋的作用，不斷收斂，最終逼近于最優解；③具有分布并行計算的能力，多個個體同時進行并行計算，大大提高了算法的計算能力和運行效率；④啟發式的概率搜索方式，不容易陷入局部最優，易于尋找到全局最優解；⑤魯棒性較好，不會因為個別螞蟻搜索的路徑差影響整個搜索結果。

蟻群算法的缺點：①算法的搜索時間較長。當處理的問題規模較大時，要在短時間內從大量的解中尋找出最優解是比較難的。在搜索初期，各個路徑上的信息素濃度差不多一致，通過信息素的反饋，再到各個路徑上的信息素有明顯差別，這個過程需要較長時間；②易于陷入局部最優。在算法中影響螞蟻的轉移主要是由各個路徑上的信息素濃度和城市間距離兩個因素決定，致使螞蟻趨于信息素濃度強的路徑。

1.2蟻群算法基本步驟

步驟1：初始化參數

在計算之前為每只螞蟻建立禁忌列表，并對相關的參數進行初始化，如設螞蟻數量m、信息啟發因子α、期望啟發因子β、信息素揮發因子ρ、信息素釋放總量Q、最大迭代次數iter_max、當前迭代次數iter等參數。

步驟2：構建解空間

將每個螞蟻隨機分布在不同的起點，對每個螞蟻k（k=1，2，…，m）計算其下一個待訪問的城市，直到所有螞蟻訪問完所有城市。

步驟3：更新信息素

計算每個螞蟻經過的路徑長度：Lk（k=1，2，…，m）

并記錄當前迭代次數中的最優解。同時，對個城市連接路徑上的信息素濃度進行更新。其中信息素的更新M.Dorigo給出了3種不同的模型，分別為螞蟻循環系統（ant_cycle system）、螞蟻數量系統（ant_quantity system）、螞蟻密度系統（ant_density system）。它們的區別在于信息素變化的公式不同。

在螞蟻循環系統中：

Δτkij（t）=QLk若螞蟻k在該次循環中經過的邊（i，j）

0否則

在螞蟻數量系統中：

Δτkij（t）=Qdij若螞蟻k在時刻t和t+1之間經過的邊（i，j）0否則

在螞蟻密度系統中：

Δτkij（t）=Q若螞蟻k在時刻t和t+1之間經過的邊（i，j）

0否則

這3種模型中前種利用的是全局信息，而后兩種利用的是局部信息。

步驟4：判斷是否終止

若iter< iter_max，則令iter=iter+1，清空螞蟻經過路徑的記錄表，并返回步驟2；否則，終止計算，輸出最優解。

2帶交通擁堵指數的改進蟻群算法

2.1信息素濃度初始化

在經典蟻群算法中，大部分學者把初始信息素濃度設置為一個固定相同的值，這樣容易使螞蟻在開始搜索時產生大量的無關搜索路徑，使得初始搜索時間偏長，這對信息素濃度的局部更新產生了誤導，阻礙最優路徑的搜索。本文基于實際交通道路情況的連通圖（見圖2、圖3），在信息素濃度初始時根據道路交通擁堵情況加入交通擁堵權重（見表1），將初始化信息素公式修改為式（1）：

τij=Qdij·ω（1）

ω=0.090>TCI>2

0.072>TCI>4

0.054>TCI>6

0.036>TCI>8

0.018>TCI>10

其中，dij為相鄰兩節點間的距離；Q為每次搜索分配的總信息素，是一個給定的常量；ω為交通擁堵指數權重。交通路線越擁堵，初始信息素的濃度越低，這對初始搜索產生了較為合理的方向引導，加快了搜索速度。

2.2轉移策略選擇

在一般蟻群算法中，螞蟻k在節點i尋找下一節點j的轉移概率為式（2）：

2.3信息素揮發系數

基本蟻群算法的信息揮發系數ρ是一個不變的常量，鑒于實際道路交通車流量情況，不同道路的車流量不同，不能滿足信息素及時更新的要求，故將信息素揮發系數改進為：ρ+ω，其中，ω為車流量系數：

ω=1車流量2

3結論與分析

實驗采用圖2中所示的道路進行算法的分析與仿真，搜索在符合實際道路情況下從某一節點出發，經過全部節點返回到起點的最短路徑。本文改進的算法與經典蟻群算法（ACS）、MMAS算法進行對比分析。主要實驗參數如表2所示。

通過用Matlab實驗分析，得出結果如圖4經典蟻群算法（ACS）、圖5 MMAS算法、圖6基于交通擁堵指數的蟻群改進算法的路徑軌跡圖。

以上結果與圖2實際交通道路圖進行對比分析，采用經典蟻群算法（ACS）的結果與實際道路有許多不符合的地方，如1011、39；MMAS算法同樣存在不符合實際道路的情況，如611、39；采用基于交通擁堵指數的蟻群改進算法能夠很好地按照實際道路進行路線規劃。

4結語

本文針對車輛路線優化問題上往往忽略實際交通道路的情況，利用Matlab模擬實驗證明帶交通擁堵指數優化后的蟻群算法能夠很好地按照實際道路進行路線規劃，其中加入了交通擁堵權重、車流量系數以及道路暢通強度。未來可以考慮人流量、城市布局以及交通紅綠燈等待時間等因素對路線優化的影響。

參考文獻參考文獻：

[1]PAOLO TOTH， DANIELE VIGO. He vehicle routing problem[M].Society for Industrial and Applied Mathematics Philadephia，2002.

[2]夏小云，周育人.蟻群優化算法的理論研究進展[J].智能系統學報，2016，11（1）：2736.

[3]何小鋒，馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統工程理論與實踐，2013，33（5）：12561261.

[4]STUTZLE，HOES.Maxmin ant system[J].Future Generation Computer System Journal，2000，16（8）：889914.

[5]畢軍，付夢印.一種改進的蟻群算法求解最短路徑問題[J].計算機工程與應用，2003，39（3）：107109.

[6]鄭衛國，田其沖，張磊.基于信息素強度的改進蟻群算法[J].計算機仿真，2010（7）：191193.

[7]ZAKZOUK A A A ，ZAHER H M ，ELDEEN R A Z.An ant colony optimization approach for solving shortest path problem with fuzzy constraints[C]. 2010 The 7th International Conference on Informatics and Systems， INFOS，2010：18.

[8]吳虎發，李學俊，章玉龍.改進的蟻群算法求解最短路徑問題[J].計算機仿真，2012，29（8）：215218.

[9]袁文濤，孫紅.CVRP物流配送路徑優化及應用研究[J].軟件導刊，2016，11（15）：140143.

[10]COLORNI A， DORIGO M， MNAIEZZO V. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems，Man and Cybernetics，1996，26（1）：2941.

責任編輯（責任編輯：何麗）