基于蟻群算法的出行者路徑選擇行為

張福龍

(天津公路工程設計研究院, 天津 300000)

當前交通環境復雜多變，出行者在考慮出行路徑的過程中除主觀因素外容易受外部環境影響，在短時間內快速預測出行者的選擇行為可為動態交通分配提供理論支撐，國內外學者對此進行了大量研究。文獻[1]從出行者心理學的角度出發，考慮交通系統的不確定性、出行者感知誤差及建模者觀測誤差分析出行者選擇路徑的過程。文獻[2]采用路徑均值設計更新蟻群算法，采用新的信息素更新方式用于指導出行者的選擇路徑。文獻[3]設計包含臭味信息素的蟻群算法，可以同時考慮系統和出行者之間的效益。文獻[4]運用蟻群算法分析交通擁擠條件下的出行者路徑選擇問題。文獻[5]提出混沌蟻群算法，該算法更加適用于出行者連續性的選擇路徑。文獻[6]提出一種歐式距離作為啟發因子，運用模糊蟻群算法尋找最小能量的路徑規劃。如何短時間快速的預測出行者的路徑選擇行為是解決城市交通問題的一大瓶頸，本文利用蟻群算法具有分布式計算的特點和概率選擇公式模擬出行者選擇路徑的行為，以期減少交通擁堵現象。

1 蟻群算法

蟻群算法的最大特點在于螞蟻選擇路徑的過程中采用概率選擇方式，根據路徑信息素濃度和路徑長短來選擇。文獻[7-8]首次提出蟻群算法并給出螞蟻選擇路徑的公式:

1.1 信息素更新策略

通過設計路徑上的信息素更新方式可以設計不同性能的蟻群算法。文獻[9]提出最大最小蟻群算法，將每條路徑信息素的大小限制在[τmin，τmax]以防止搜索過程的停滯。這種設置可以防止路徑的信息濃度過大或過小，比較符合出行者實際出行過程的實際路網情形，當出行路徑不存在交通量時，設置出行路徑的信息素濃度為最大值τmax；當路徑發生交通擁堵時設置路徑的信息素濃度為最小值τmin。

為了縮小流量在空間分布的差異性，加快算法的收斂速度，對傳統蟻群算法進行改進，引入信息素平滑和信息素蒸發機制。改進后的蟻群算法只對最優路徑上的信息素實行信息素蒸發機制，非最優路徑上的信息素實行信息素平滑機制，因此有：

τij(t+1)=τij(t)+(1-ρ)(τmax(t)-τij(t))

，

圖1 算法流程

1.2 算法的適用性分析

蟻群算法在交通規劃領域主要用于尋找最優路徑[10-24]，算法流程如圖1所示。利用蟻群算法的概率選擇公式并結合用戶均衡第一原理[25]，假設出行者具有相同的路徑決策規則，傳統模型大多以路徑的出行阻抗最小或者路徑的廣義費用最少作為決策規則。出行者在選擇路徑的過程中考慮出行路徑的廣義費用，將路徑的廣義費用相反數定義為路徑的信息素濃度，能夠較好的模擬出行者選擇路徑的過程，則有

Tij=Tij(0)[1+a(v/c)b]Ft+pij，

τij=1/Tij，

式中：Tij為路段ij上的廣義阻抗；Tij(0)為路段ij上的自由流行駛時間；v為通過路段的車流量，c為道路通行能力,v/c為路段ij上的交通量飽和度；pij為車輛通過路段ij的通行費(元)；Ft為車輛的時間價值(元/(h·車))；a、b為阻滯系數，a=0.15，b=4。

當出行者的決策過程受到外部極端條件影響時，如天氣原因導致道路實際通行能力下降，出行路徑廣義費用陡然增大。在此情況下采用臭味信息素更新機制，臭味信息素可以不同程度的減弱正常的信息素濃度，有

τij(t+1)=γτij(t),γ∈[0,1]，

式中：γ為臭味信息素作用強度系數。

2 案例應用分析

圖2 路徑選擇

構造如圖2所示的交通路網，根據出行者的個體特征通過調節參數α、β的大小摸擬不同出行者的個體特征，對路徑選擇結果的差異。先后分4次讓出行者選擇路徑，針對不同的出行者，參數α、β采用不同的取值，最后分析模擬出行者選擇路徑的過程。

當α=1，β=1，ρ=0.95時，t1、t2、t3、t4時刻的出行量分別為17 811、23 747、29 683、34 286 pcu(當量交通量)。根據已知數據，利用EXCEL軟件進行編程進行計算，計算步驟如下：

1)確定從起點1到終點5有12條有效路徑，分別為G1G2(1，2，5)、G1S2(1，2，5)、S1S2(1，2，5)、S1G2(1，2，5)、G3G4(1，3，5)、G3S4(1，3，5)、S3S4(1，3，5)、S3G4(1，3，5)、G5G6(1，4，5)、G5S6(1，4，5)、S5S6(1，4，5)、S5G6(1，4，5)。計算各條路徑的廣義費用，進而計算出各條路徑的初始信息素濃度。

2)判斷路網中各個路徑的信息素濃度，計算t1時刻出行者選擇路徑的概率。計算結果如表1所示。

表1 t1時刻出行者選擇結果

3)重新計算更新路網整體的信息素，分配t2時刻的出行者。

4)重復步驟2)3)，直到所有出行者選擇了出行路徑。t1、t2、t3、t4時刻出行者選擇路徑結果見表2。

表2 出行選擇結果

當路段S1(1，2)、S2(2，5)的v/c為1時，交通發生擁堵情況(v/c為1時，路段飽和代表交通擁擠)，臭味信息素開始發揮作用，導致下一時刻出行者選擇路徑時，路段S1(1，2)、S2(2，5)的信息素濃度為0，路段S1(1，2)、S2(2，5)被選擇的概率為0，見表2。由表2可知：t1、t2、t3時刻各條路徑的交通量未達到飽和狀態，各條路徑被選擇概率大小的差異性逐漸縮小，出行者的空間分布更加均勻。分析每個時刻路徑的信息素濃度，總結得出各條路徑的信息素變化情況如圖3所示。

圖3 有效路徑信息素更新過程

3 結果分析

保持α=1不變，β由0～2逐漸增大，各條路徑分擔率的波動情況如圖4所示。由圖4可知：當β由0～2逐漸增大時，出行者的空間分布更加均勻。

圖4 β變化對各條路徑分擔率大小的影響

圖5 路網流量廣義費用估計值隨參數的變化

保持α=1不變，β由0～2逐漸增大，用各條路徑的廣義通行費用之和作為整體路網費用的估計值，計算4個時刻路網的廣義費用，結果如圖5所示。由圖5可知：隨著參數β的增大，路網費用不斷減小。

4 結語

采用改進蟻群算法并通過信息素平滑機制建立路徑各條路段的聯系，根據不同出行者的特征合理確定啟發信息素的重要程度α與信息素的重要程度β，能使路網的廣義通行費用逐漸減小并且出行者的空間分布更加均勻，因此，改進的蟻群算法能夠較好的模擬出行者的路徑選擇過程。