基于改進蟻群算法的交通網絡最優路徑規劃方法

李生彪，彭建奎

(蘭州文理學院 教育學院,甘肅 蘭州 730000)

在交通網絡中，最優路徑規劃是指尋找從起始地到目標地之間總代價最小的目標路徑的過程，交通網絡最優路徑規劃方法是智能交通領域研究的重點問題，解決該問題的傳統算法主要有廣度優先搜索法、Dijkstra算法等。 近些年，隨著智能技術的出現，一些學者采用群體仿生理論來解決最優路徑規劃問題，主要有蟻群算法、遺傳算法、神經網絡算法以及各算法之間的組合優化算法等。

蟻群算法模擬螞蟻合作覓食行為的性質，具有較強的全局搜索能力和并行性等優點。但傳統蟻群算法有易陷入局部最優解、搜索時間長、有時無法跳出死鎖狀態等局限性[1]。國內外學者對蟻群算法提出了一些改進思路，如高尚等[2-3]加入混沌理論，趙寶江[4]提出基于自適應路徑選擇和動態信息素更新的蟻群算法，黃貴玲等[5]加入直線優化啟發信息， FUELLERER等[6]加入幾種其他啟發式算法以提高算法效率，DONATI等[7]則完成了對多個目標的優化等。本研究針對傳統經典蟻群算法的局限性，改進信息素濃度更新方式，通過優化信息素總量增強全局搜索能力，以使算法更好地滿足于求解交通系統的最優路徑問題。

1 環境建模

把交通網絡中的道路起始點、目標點和交叉路口等抽象為節點，節點之間的道路抽象為弧，實際道路的長度、車輛通行的時間和道路擁堵程度等信息視為弧的權，那么實際的交通網就可以被抽象為一個帶權的有向圖。

對于給定的帶權有向圖G(V,{E})，其中，V是頂點集，E是弧的集合，c(v,w)是弧(v,w) 的權。Pst=(v0=vs,v1=,…,vn=vt)為V中由vs到vt的一條路徑。則最優路徑問題可表示為如下的數學模型：

minT(Pst)

(1)

在實際中，交通路段的信息實時變化，最優路徑的規劃也有不同的標準，如最少通行時間、最短距離、最低費用等。因此，針對不同的交通網絡信息，需要選擇恰當的算法才能找到最優路徑。

2 傳統蟻群算法及模型

螞蟻在巢穴和食物之間的路徑上會釋放信息素，最開始時不論路徑的長短都是等概率地選擇下一步可行路徑。后來，隨著迭代次數的增加，螞蟻在移動時會選擇信息素濃度高的路線，這樣就使得較短路線上的螞蟻數量不斷增加，較長路線上螞蟻數量不斷減少。因此，通過這些信息素，螞蟻可以找到一條巢穴到食物的最短路徑。

設m是螞蟻的數量,τij(t)是t時刻路徑(i,j)上的信息素濃度。在最開始的時刻，各條路徑上的信息素濃度相等，即τij(0)=C，C是常數。假設所有螞蟻均由路徑規劃的起點出發，然后，每只螞蟻在選擇其行進路徑時依據所在結點i鄰接各路徑上的信息素濃度計算轉移概率。在t時刻螞蟻k(k=1,2,…,n)由結點i轉移到節點j的轉移概率

(2)

式中：Ak={N-tk}表示螞蟻k禁忌表外可以走的節點，N為所在路徑網絡，tk為禁忌表；α是信息啟發式因子，β是期望啟發因子；ηij表示由節點i轉移到節點j的期望程度，通常ηij=1/dij，其中，dij表示節點i到節點j的距離。

當螞蟻完成一次對所有節點的搜索之后，則需要對信息素濃度進行更新處理。在此選用Ant-Cycle 模型[8]，則t+Δt時刻路徑(i,j)上的信息素濃度為

τij(t+Δt)=(1-ρ)·τij(t)+Δτij(t)

(3)

(4)

(5)

3 基于信息素更新方式改進的蟻群算法

3.1 信息素濃度限定原則

在此設置每條路徑上信息素濃度的最小值τmin和最大值τmax，這樣就把每條路徑上的信息素濃度限定在[τmin,τmax]上。 改進的蟻群算法中設置信息素濃度下限τmin，雖然選擇這些路徑的概率很小，但不會為零，這樣就避免了螞蟻出現停滯的現象，從而使螞蟻能進行更高程度的搜索；由于在經典蟻群算法中，尋找最優路徑時并不會考慮路網的承受能力，因此有可能會出現擁堵的情況，改進的蟻群算法考慮到實際交通網絡中每條路徑都有最大承載量，故設置了信息素強度的上限τmax。

3.2 信息素局部更新算法的改進

由于在實際的交通網絡中有這樣的現象：在某條道路上的通過時間會隨著交通流量的增加而增加，而采用信息素局部更新的方法可使信息素濃度較高的邊對后面的螞蟻具有較小的吸引力，從而使螞蟻對沒有被選中的邊有更強的探索能力，且實驗表明，局部更新規則可以有效避免螞蟻收斂到同一路徑[9]，故文中將螞蟻行走過程中的信息素更新方式設置為局部更新原則。采用平滑機制的思路，當螞蟻通過路徑(i,j)后，路徑(i,j)上的信息素濃度作如下更新：

(6)

3.3 信息素全局更新模型的改進

雖然在局部信息素的改進中考慮了交通網絡容量的特性，但當交通流量越大，依據Ant-Cycle 模型(3)計算出的螞蟻在路網上留下的信息素濃度仍然是最高的，即后來的螞蟻根據式(2)仍會選擇這條路徑，最終造成該路徑崩潰[10]?，F有的信息素更新方法多是對式(4)做出調整，引進路徑上的阻抗函數。由于本文討論的是動態的交通網絡最優路徑搜索問題，故在此引進能反映實時路況的廣義路阻[11]來控制邊上的信息素。路徑(i,j)上的廣義路阻T(i,j)為

T(i,j)=t(i,j)+r(i,j)

(7)

t(i,j)=t0(i,j)[1+k1(V/C)k2]

(8)

r(i,j)=r1(i,j)+r2(i,j)[1+k1(V/C)k2]

(9)

(10)

(11)

式中:t(i,j)、r(i,j)分別為路徑(i,j)上的行駛時間和平均延誤時間，t0(i,j)表示交通流為零時路徑(i,j)的行駛時間；V為路徑(i,j)上的交通量當量值；C為路徑(i,j)的實用通行能力；k1、k2為回歸參數，可根據交通網絡的調查數據用最小二乘法確定；r1(i,j)、r2(i,j)分別為均勻延誤和過飽和延誤；k3、k4為常數；λ是進口路徑處綠信比；T是周期；X=V/λC為交叉路口飽和度；C為進口飽和通行能力；S是修正系數。

這樣，信息素濃度更新為

(12)

3.4 改進蟻群算法的實現步驟

將改進后的蟻群算法方法應用到實際的交通網絡路徑問題中，給出路徑選擇的改進蟻群算法步驟如下：

Step 1 信息素及參數初始化。螞蟻逐個位于起始點；初始化α、β、tmin、tmax、τij(0)、m、ξ、Q等參數。由于蟻群算法中的參數設定目前尚無理論上的依據，在此用經驗確定其最優組合[12]: 1≤α≤5,1≤β≤5,0.5≤ρ≤0.99,1≤Q≤10 000。

Step 2 選擇原則。每只螞蟻依據轉移概率在不在禁忌表中的匯點中選擇下一個節點，且將所選節點放入禁忌表中。當每只螞蟻走完一圈后，計算出螞蟻所走路徑的綜合系數值。

Step 3 局部更新原則。當螞蟻選中路徑(i,j)后，就按式(7)更新路徑(i,j)上的信息素濃度，以增加螞蟻選擇其他路徑的概率。

Step 4 局部最優路徑搜索。當m只螞蟻從起始點到終點搜索完成后，則求得m個解，分別在這m個解的鄰域中，采用局部搜索算法，求出局部最優解。

Step 5 全局更新原則。當得到m個局部最優解后(否則跳入 Step 2)，按照式(4)、(5)、(11)全局更新路徑信息素量，更新路徑阻抗，比較所有環游得出的綜合系數值，找出最優的環游路徑。

Step 6 找出全局最優解。截止到當前迭代次數，在求得的所有局部最優解中，值最小的解作為全局最優解。

Step 7 不斷迭代直至迭代次數達到最大值，程序結束。

4 實驗仿真及結果

4.1 問題描述

設有一家連鎖店企業，有20家連鎖分店，編號為1～20，其貨物儲存倉庫(編號為0，坐標為(10，40))每天都向各個連鎖分店進行商品補給，該企業每天可調度的車輛數是4輛。 為了方便測試，將儲存倉庫及20個連鎖分店的位置坐標映射至XOY平面上，如圖1所示。各連鎖分店的位置坐標及每天所需補給量如表1所示。

圖1 連鎖分店及倉庫坐標圖Fig.1 Coordinate diagram of chain stores and warehouses

表1 連鎖分店坐標及日需補給量Tab.1 Location coordinates of chain stores and daily supply demand

4.2 參數設置

蟻群算法中不同參數的設置對算法的實驗結果有很大的影響，在此參照前面的參數最佳設置范圍，結合本測試案例，相關實驗參數設置見表2。

表2 相關實驗參數值Tab.2 Relevant experimental parameter values

4.3 仿真結果及分析

對本案例分別運用傳統蟻群算法(ant colony optimization，AC)、自適應轉移蟻群算法(adaptive ant colony optimization， AAC)和本文改進蟻群算法進行仿真計算。表 3給出了3種蟻群算法基于本案例運行 10 次所對應的配送成本、收斂代數以及運行時長結果。

表3 3種蟻群算法的運行結果Tab.3 Running results of three ant colony algorithms

從表3可看出，AC算法的配送成本集中在475的附近，沒有較大的突破，收斂代數最小31.31，最大54.54，變化較大，不具穩定性；AAC算法的配送成本主要集中在474附近，沒有較大變化，收斂代數也沒有明顯的規律性，對比前兩種蟻群算法，本文改進蟻群算法在配送成本方面有了一個實質性的進展和突破，突破了470的約束，以50%的概率歸攏于467.4，最佳收斂代數也是最低的26.26。此外，對比3種算法的運行時長，本文算法在最佳值、最差值和平均值方面都優于前兩種蟻群算法。

下面給出3種算法的配送成本、最佳配送方案以及收斂代數，見圖2、圖3、圖4和表4。

(a)AC算法的配送成本 (b)AC算法最佳派送方案圖2 AC算法規劃的配送方案及配送成本Fig.2 Distribution scheme and cost of AC

(a)AAC算法配送成本 (b)AAC算法最佳派送方案圖3 AAC算法規劃的配送方案及配送成本Fig.3 Distribution scheme and cost of AAC

(a) 本文算法配送成本 (b) 本文算法最佳派送方案圖4 本文算法規劃的配送方案及配送成本Fig.4 Distribution scheme and cost in this paper

表4 具體配送方案及配送成本Tab.4 Specific distribution scheme and distribution cost

對照圖2～4及表4，可以看出AC算法在第32代找到了最優路徑，其1號車路線為0-20-16-14-13-12-0，在走完20號、16號分店后再到14號分店，顯然違背了 “兩點之間線段最短”的公理，故該路線肯定不是最優的。AC算法經過長期動蕩搜索，最終收攏于475。AAC算法在第29代繪出最優路徑，最終收攏于472，其1號車路線作了優化，但還有交叉路線，說明還有提升的空間。本文改進蟻群算法的最優路徑在第27代完成，最終收攏于467，同比AC算法、AAC算法，在收斂代數上分別縮短了16.13%、7.14%，在配送成本上分別降低了1.77%、1.04%。本文改進蟻群算法1 號車的路線既不存在繞路現象，也沒有交叉路徑，顯然為最優路徑。此外，3種算法中4號車路線完全一樣，都為可取路徑。

綜上所述，本文算法較傳統蟻群算法在時間效率和配送成本方面均有明顯程度的提升，在交通網絡最優路徑規劃問題上更具高效性。