基于改進蟻群系統的動態交通分配

孫琦，袁才鴻

（214072 江蘇省 無錫市 無錫市政設計研究院有限公司）

0 引言

隨著經濟發展和城市化的推進，交通擁堵日益加劇。發達國家研究的智能交通系統（ITS）的核心之一就是動態交通分配（DTA）。1978 年，Merchant 和Nemhauser[1]首次提出了動態交通分配模型，為交通管控和誘導提供了新方法和思路。經過長期的研究，其體系已較為完備，其中又以最優控制模型最為成熟。最優控制模型根據不同的目標可分為動態系統最優（DSO）和動態用戶最優（DUO）。它們最大的差別在于DSO 不必對出行者的路徑選擇行為進行假設，雖然更簡單但不符合實際，因此，DUO 更具有實際應用價值。

學者們大都使用Frank-Wolf、連續平均法等數值算法求解動態分配模型，雖然能降低計算復雜度，但卻無法適用于實際大規模網絡。為了解決這一問題，學者們開始使用啟發式算法求解DTA 模型，例如神經網絡、遺傳算法等。其中，蟻群算法（Ant Colony Optimization，ACO）由于其分布式并行計算的特性，在動態交通分配領域得到了廣泛應用。學者們也提出了許多ACO 的改進算法，但這些改進算法的主要目標是改進算法求解質量和效率，而忽略了時變的出行狀況在算法中的體現，例如，實際出行中出行者易于通過手機地圖、車載導航、道路狀況播報屏等獲得較為準確的實時道路情況，根據所得信息動態調整出行路線。因此，蟻群算法在保證算法效率的同時，在增加實際性方面還有很大的改進空間。

1 動態用戶最優配流模型

DSO 是從管理者的角度力求路網的流量分布達到均衡，使整個系統的阻抗最低。但是出行者作為獨立的個體，他們的擇路行為具有不確定性，在大規模路網中DSO 往往不能體現出這一復雜性。而DUO 是從用戶角度出發，每個出行者都能選擇自身感知最小阻抗的路徑，達到個體的阻抗最優，進而促成系統的動態平衡。魏秋月[2]認為，DUO 假定每個出行者都能了解路網并選擇感知阻抗最小路徑的說法不太符合實際，她認為，出行者并不能完全了解路網實時狀態。但是在智能交通設施日益完善的今天，一些手機導航軟件、車載導航設備都能夠提供較為準確的實時路況信息，路口、路段安裝的智能視頻監控設備也能將檢測的實時流量在電子顯示屏實時播報，出行者可從多方渠道獲取較為準確的實時路況信息，從而合理規劃、調整出行路線。由此看來，DUO 更符合現代智能化出行條件下出行者的擇路行為。

將DUO 模型的[0，T]時段分成K+1 個部分進行離散化，表達式具體如下：目標函數：

式中：xa(t)，ua(t)，va(t)——t 時刻路段 a 上的流量、流入率、流出率；時刻進入路段a 要到終點s 去的流量、流入率、流出率；ca(t)（瞬時阻抗）=g1a[xa（t），ua（t）]（運行時間）+g2a[xa（t），va（t）]（等待延誤時間）；gls（t）——節點l 新產生的流量。

2 基于阻抗動態反饋的蟻群系統算法

蟻群算法由Dorigo[3]于1991 年提出，在DTA領域得到了長足發展，許多改進蟻群算法也相繼被提出，如帶精英策略的螞蟻系統、基于排序的螞蟻系統、最大-最小螞蟻系統等，其中以蟻群系統的綜合性能最佳，但是蟻群系統在大規模問題的計算中仍然存在全局搜索能力差的缺點。

2.1 蟻群系統（ACS）模型

蟻群系統由Dorigo[4]于1996 年提出，在ACO 的基礎上進行了如下改進。

（1）ACS 在狀態轉移規則中添加了偽隨機比例規則，能夠利用以信息素形式存儲的信息等先驗知識，進行更有傾向性的探索

（2）ACS 重新定義了信息素更新規則。規定每次循環后更新局部信息素，避免螞蟻收斂到同一路徑；螞蟻全部到達終點后，只在最優螞蟻路徑上更新全局信息素，這種改進使得最優路徑和其他路徑間信息素的差異越來越大，使得搜索能很快地集中于最優和次優路徑的解集范圍內，極大提高了搜索效率。

局部信息素更新規則：

全局信息素更新規則：

式中：λ——揮發參數（0<λ<1）；ρ——信息素揮發系數（0<ρ<1）；Lgb——當前全局最優路徑。

2.2 基于阻抗動態反饋的改進ACS 模型

國內外學者對ACS 進行了很多研究。曹繼英[5]考慮道路容量限制，使用ACS求解DUO模型，并與MSA 算法比較證明其優越性；Alaya[6]等對ACS 的螞蟻數和信息素路徑進行參數化改進，并與其它算法進行了比較；常玉林[7]等考慮交叉口延誤因素對信息素更新機制進行調整，取得了很好的效果。可見，現有ACS 的改進大都是為了提高局部搜索效率，適用范圍僅限于小規模問題，卻沒有考慮到求解大規模搜索問題時，算法的全局搜索能力是和解的質量直接掛鉤的，所以，提高ACS 的全局搜索能力對求解大規模分配問題具有決定性的重要意義。

本文考慮通過在ACS 中加入實際因素的指導來改進算法的固有機制，從而增加算法的全局搜索能力。其原理為：根據螞蟻尋路的結果計算出路段實際阻抗，再反作用于螞蟻尋路，指引螞蟻去往阻抗更低的路段。如上節所述，全局信息素更新保證了局部搜索的效率，加入實際阻抗因素可以保證增加最優路段的周邊路段的競爭力，保證算法的全局搜索能力且更加符合實際出行情況。主要改進3 部分：

（1）基于元胞傳輸的實際阻抗計算

現有DUO 模型中計算阻抗的方法大都采用BPR 函數，雖然簡單但是精確度不高。本文基于一種宏觀交通流理論-元胞傳輸理論提出一種實際阻抗計算方法，保證實際阻抗計算的精確性。元胞傳輸理論顧名思義就是將路段劃分為一個個首尾相連元胞組，將車輛通過路段的過程離散化為車輛通過一個個元胞的過程，從而得到較為準確的路段實時的流量和密度[8]，進而可以計算出路段實際阻抗。方法具體如下：

以求解t 時刻流入路段a 的交通量ua(t)的實際阻抗為例，將這部分交通量看作車隊，車隊在將來t+x 個時段完全流出路段。對路段首尾元胞提取數據可以得到路段累計流入、流出量Ua(t)，Oa(t) 和路段車輛數Ca(t)，進而對t～t+x 的數據處理可得Ua(t)的實際阻抗，基礎關系式如下：

把ua(t)的行駛狀態分為3 種（如圖1 所示）。狀態1 和狀態3 分別為ua(t)的車頭和尾部開始流入和流出路段，這2 個狀態會有上、下一時刻的車輛混合流出路段，故對這兩個狀態離散化計算。狀態2 為ua(t)的主體連續流出路段，因此，考慮根據放行流率曲線進行積分計算，保證解的準確性，具體如下：

式中：ca（t）——ua（t）的平均實際阻抗；ca（t）'——狀態1 的實際阻抗，依此類推。根據狀態1，2，3 的分界時刻和式（9），分別計算如下：

圖1 流入量行駛狀態圖Fig.1 Traffic inflow driving state diagram

（2）對信息素更新機制的改進

全局信息素更新機制是為了使螞蟻很快集中到最優路徑范圍內，但在提高局部搜索效率的同時，卻喪失了全局搜索能力，因此，本文以路段實際阻抗作為決策因子動態調整路段信息素濃度，在進行信息素更新時，不光擴大最優路徑的信息素濃度，同時使周圍路段的信息素濃度小幅減小，保證周圍路段的吸引力，增加全局搜索能力，具體如下：

式（14）為信息素揮發系數自適應調整公式，ρmax和ρmin取經驗值分別為0.9 和0.1；cf——自由阻抗。

式（14）可以根據實際阻抗調整信息素揮發系數，從而改變路段信息素濃度，指導螞蟻選路。例如：假設某路段很擁堵，則實際阻抗就很大，根據式（14），該路段信息素揮發系數會變大，路段信息素快速揮發，濃度會驟降，對螞蟻的吸引力會變弱，螞蟻會更傾向于其他路段；反之，路段很暢通就會對應很小的信息素揮發系數，螞蟻不斷選擇該路段的同時，路段信息素小幅揮發，信息素濃度整體呈現增長趨勢，能夠持續吸引螞蟻直至路段變得擁堵。

（3）對狀態轉移概率公式的改進

狀態轉移概率公式的參數主要有路段信息素量和路段信息啟發程度，信息素量取決于信息素更新機制。曹繼英在文獻[9]中對ACS 的信息素啟發程度進行了改進，使用阻抗替換原有路段長度，即把ηij=1/lij替換為ηij=1/τij。但是出行者擇路時，會綜合考慮路段擁堵狀況和路段長度雙重因素，因此，本文考慮在信息素啟發程度中加入阻抗和路段長度的權重系數作為擇路依據，定義為ηij=1/（x·τij+y·lij），其中，x 和y 為阻抗和路段長度的權重，根據經驗分別取6 和4。綜合考慮阻抗和路段長度因素更符合實際情況。

總體來說，本節對ACS 的改進是為了實現實際阻抗指導螞蟻選路，算法中螞蟻代表實際的流量，通過實際阻抗這一因子，實現螞蟻選路結果（即流量分布）和選路過程的循環相互作用，保留算法原有優勢機制的同時增強了全局搜索能力和實際性。

3 算法具體實現流程

使用上節提出的改進ACS 求解動態用戶最優分配模型，具體流程如下：

我姨媽是從她的嗓音里辨認出她的。姨媽擠在法庭外面的人群里，從懸在電線桿上的高音喇叭里聽見了她的證詞，盡管她用的是另一個名字。

Step1：初始化。確定參數：路網坐標（禁忌表）；OD 交通量；自由流速度vf；阻塞密度kjam；螞蟻數m；迭代次數NC；信息和期望啟發因子α、β；初始信息素揮發系數ρ0。

Step2：初始流量置0，初始信息素濃度Δτij（0，1）。將初始時段所有OD 對螞蟻放在起點，起點禁忌表值置為1。

Step3：尋路開始，根據禁忌表確定下一步的節點，判斷路段容量是否達到限制，進而根據式（6）確定下一個節點，并將所選節點對應禁忌表值置1。

Step4：根據式（7）局部更新信息素，并按式（10）—式（13）更新各路段流量和實際阻抗，將計算值存入阻抗矩陣。

Step5：根據阻抗矩陣中各路段的實際阻抗，對式（6）進行更新。

Step6：重復Step3，4，5 直到所有螞蟻都到達終點。

4 算例測試與分析

為了驗證上述提出算法的有效性，本文引用Nguyen-Dupius 經典路網模型[10]。路網算例如圖2 所示，共由13 個節點和19 條路段組成，共有2 組起點和終點：節點1 與4、節點2 與3，易知OD 對一共為4 對，可組合成25 條路徑。路段容量限制和自由阻抗采用陸化普[11]設置的屬性。

圖2 Nguyen-Dupius 路網Fig.2 Nguyen-Dupius network

分別使用ACS 和改進ACS 求解DUO 模型，將改進ACS 和基本ACS 對案例路網流量的分配結果如表1、圖3 所示。一般，ACS 與本文改進ACS 求解所得流量均具有路段2 最少和路段15最多的共同特征，且均未超過路段容量限制，基本ACS 流量分布在41-233 之間，改進ACS 流量分布在54-185 之間。

如表1 所示，除了路段1，2，9，17，19，改進ACS 的阻抗值比基本ACS 略高外，改進ACS 計算其余路段的阻抗均優于基本ACS，這是因為節點分岔處另一路段吸引大量車輛，改進算法自動將車輛分流至長度雖然較長但是阻抗較低的路段。通過比較各路段阻抗值比較可以明顯看出，改進ACS比基本ACS的分配結果更均衡合理。基本ACS 各路段分配流量標準差為49.2，阻抗標準差為15.0，改進ACS 各路段流量標準差為37.7，阻抗標準差為14.8，改進ACS 計算結果的各路段流量和阻抗更接近平均值，離散程度較小。將兩種算法計算阻抗結果按25 條路徑生成路徑阻抗散點圖，如圖4 所示。基本ACS 路徑阻抗差異大，改進ACS 計算阻抗相對集中，路網利用率更高。

表1 案例路網分配結果分析Tab.1 Analysis of assignment results of case network

圖3 路段分配流量圖Fig.3 Road assignment flow chart

圖4 路徑分配阻抗圖Fig.4 Path assignment impedance graph

5 結論

本文針對現有蟻群系統算法全局搜索能力差、無法計算大規模分配問題的缺點，基于ACS的固有機制，采用阻抗動態反饋的方法，通過每步螞蟻尋路結果動態調整信息素更新公式與狀態轉移概率公式，在保證ACS 局部搜索優勢的前提下，增加算法的全局搜索能力。通過使用改進前后的算法對案例路網進行求解，輸出路段流量和目標函數阻抗值，結果表明，改進算法分配結果更均衡，結果離散程度小，在最短路徑通行能力不佳的情況下能有效利用次優路徑，并根據路段阻抗保持路徑選擇的動態平衡，實現系統的阻抗最優，路網利用率高。下一步工作為使用改進算法和其他啟發式算法對實際大規模路網進行求解，驗證算法的有效性。