??? 摘 要：交通資源規劃是一種比較典型的組合優化問題，新型的仿生算法——蟻群算法，由于具有正反饋性、魯棒性、并行計算、協同性等特點，非常適合于解決交通資源規劃問題。針對出租車路徑規劃問題的特點以及蟻群算法在這方面應用的一些不足，提出了一種改進的蟻群算法。根據同一蟻群的信息素相互激勵，不同蟻群之間信息素相互抑制的原理，該算法實現了出租車資源的合理分布。
??? 關鍵詞：交通資源規劃；出租車路徑規劃；蟻群算法；多蟻群
?
??? 隨著經濟的發展和城市的急速擴張，城市交通問題一直是制約很多大城市發展的問題之一。
??? 出租車路徑規劃問題的背景是出租車公司如何調度所屬的出租車完成顧客提出的具體服務要求。對于某個出租車公司，在出租車資源需求不變的情況下，如何減少出租車的空駛時間，減少預期乘客等待時間，取決于出租車在空駛時的路線運行行為[1]。
??? 出租車調度的優化目標就是讓所有出租車在完成特定的交通需求前提下，使得所有出租車所行的總里程數最小，繼而達到總費用最低和節省能源的目標[2]。
1 基本蟻群算法原理
??? 蟻群算法是通過對真實蟻群行為研究而提出的。仿生學家經過長期研究發現螞蟻在尋找食物時，能在其經過的路徑上釋放一種特殊的分泌物——信息素，使得一定范圍內的其他螞蟻能夠感覺到這種物質，且傾向于朝著該物質強度高的方向移動，因此，蟻群的集體行為表現為一種信息正反饋現象：某條路徑上經過的螞蟻數越多，其上留下的信息量也就越多(當然，隨著時間的推移會逐漸蒸發掉一部分)，后來螞蟻選擇該路徑的概率也越高，從而增加了該路徑上信息素的強度。這樣最優路徑上的信息量越來越大，而其他路徑上的信息量卻會隨著時間的流逝而逐漸減少，最終整個蟻群會找出最優路徑[3]。
??? 目前，人們已總結出螞蟻在覓食過程中的一些簡單規則。假設在t時刻位于節點i的螞蟻k，利用路徑(i, j)上的信息素濃度tij(t)，則下一個節點j∈Ni的轉移概率pijk(t)可表示為：
??? 
??? 其中，allowedk={0,1,…,n-1}-tabuk表示螞蟻k當前能選擇的節點集合；tabuk為禁忌表，記錄螞蟻k已走過的節點；α為信息啟發式因子，表示路徑的相對重要性；ηij(t)為t時刻的能見度，反應由節點i轉移到節點j的期望程度；β為啟發式因子，表示能見度的相對重要性[4]。
同時，為了避免殘留信息素過多引起殘留信息淹沒啟發信息，可以規定在一個時間段完成一次循環后，對殘留信息進行更新。路徑(i, j)的信息素強度τij(t)的更新方程為：
其中，ρ為信息素的持久系數(0<ρ<1)，則(1-ρ)為信息素的揮發系數；表示完成一次循環后路徑(i, j)上的信息素增量；
表示第k只螞蟻在本次循環中留在路徑(i, j)上的信息量，一般來說，最基本的取值形式為：
(4)式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度，表示第k只螞蟻在本次循環中所走路徑的總長度。
由式(1)可知，當ηij>0時，螞蟻i按概率
從節點i轉移到節點j；當ηij≤0時，螞蟻i作鄰域搜索。也就是，螞蟻要么轉移至其他螞蟻走過的路徑，要么進行鄰域搜索，最終螞蟻走的路徑取以前螞蟻所走路徑的最優值。一旦有足夠多的螞蟻對定義區間進行這種地毯式的搜索，這種尋優方式便能逐漸收斂到全局最優解。
2? 改進的蟻群算法在出租車路徑規劃中的實現
2.1 改進蟻群算法的基本原理
利用蟻群算法進行交通資源調度是一個比較新的思路。由于交通資源分配屬于優化問題，交通資源調度就是在有限的交通資源條件下[5]，緩解城市交通資源時間和空間分布不均勻的現狀，最大限度滿足市民對于交通資源的需求。而出租車的調度相比于其他交通資源，有更大的靈活性和可操作性。可以在滿足城市各區域市民出行需求的前提下，最大限度減少出租車的空駛時間和路程，減少資源浪費。
針對出租車路徑規則對比蟻群算法的基本原理，做出如下改進：
(1)跟蟻群算法找到單一食物作為蟻群目的地不同，空載出租車需要考慮到各個區域市民的出租車需求量，從而將出租車資源合理有效地分配到這些地區，不僅滿足出行需求熱點地區市民的交通需求，還要在一定程度上照顧次熱點乃至偏遠地區市民的出行需求。
(2)由于每個交通區域一些固有交通特性不同，相當于信息素的持久系數ρ，例如寫字樓集中區域在上下班時間交通需求大，而在其他時間段交通需求則少，因而這些區域信息素持久系數要低，以免大量冗余的信息素殘留導致過了交通高峰期后仍有大量出租車趕去系統認為的這些“熱點”地區。
(3)由于交通需求的特殊性，根據時間而變化的交通需求異常顯著。因而在不同時間由區域i轉移到區域j的概率，可以根據時間t的變化決定的能見度。
2.2 改進蟻群算法的設計
通過以上分析，可以對算法進行如下改進：文中根據不同出租車公司所屬的出租車組相互競爭來實現這種交通資源合理分配的規劃算法。同一個出租車公司所屬的出租車之間通過信息素來進行正向反饋，而不同出租車公司所屬的出租車之間則通過信息素相互抑制[6]。
將m個出租車公司假設為蟻群A1，A2，A3，…Am-1，Am，t時刻對應的信息素濃度分別為τ(t，1),τ(t,2),τ(t,3)，…τ(t,n-1)，τ(t,n)。則屬于蟻群An(1≤n≤m)的螞蟻k由區域i行駛到區域j的轉移概率可表示為：
??? 
??? 其中，τij(t,n)是t時刻蟻群n在路徑(i, j)上的信息素，ηij(t, n)是t時刻蟻群n在路徑(i, j)上的啟發程度，由區域交通需求變化量決定，這個量可能發生變化，值越大表明啟發程度越高。α為信息啟發式因子，表示路徑的相對重要性；β為啟發式因子，表示能見度的相對重要性；allowedk表示螞蟻k未走過且當前能選擇的節點集合；
表示其他蟻群對蟻群選擇路徑(i, j)的概率抑制因子之和。θij(t, n)的計算公式如下：
??? 
??? 其中，allowedk表示蟻群Au尚未走過且當前能選擇的節點集合。
??? 這樣，通過多個蟻群在同一路徑上的相互抑制，便能有效防止很多蟻群擁擠到同一條路徑上。同時，為了保證只有同一個蟻群的螞蟻才能通過信息素進行正向反饋，因而τij(t, n)的計算公式如下：
其中，ρ為信息素的持久系數(0<ρ<1)；Δτij(u)表示完成一次循環后蟻群Au中的螞蟻留在路徑(i, j)上的信息素增量。
表示屬于蟻群Au中的所有螞蟻在本次循環中留在路徑(i, j)上的信息量總和，一般來說，
最基本的取值形式為：
??? 
??? (9)式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環中所走路徑的總長度。
??? 值得注意的是，該改進算法在只對單一蟻群進行規劃時退化為傳統的蟻群算法。
3? 實驗結果及分析
??? 如圖1所示，假設a、b、c、d為4個不同區域，取α=1，β=2，ρ=0.7，Q=100，所有路徑成本均取1，使用Matlab6.5進行仿真試驗。得到每個時段區域b的出租車需求量均為80，區域c的出租車需求量為40，區域d的需求量為20。初始信息素濃度為τinit=0。設有3個出租車公司所屬的出租車數目比為4∶2∶1，則位于區域a的空載出租車路徑選擇概率分布如圖2所示。
?
?
?
??? 觀察圖2可知：
??? (1)當區域a點的空載出租車數量小于20時，選擇路徑ab的概率為1，而選擇路徑ac與路徑ad的概率為0；
??? (2)當區域a點的空載出租車數量大于20小于40時，路徑ac上的轉移概率開始增大，路徑ab上的轉移概率開始減小，但此時路徑ad上的轉移概率仍然為0；
??? (3)當區域a點的空載出租車數量大于40小于140時，路徑ac和路徑ad上的轉移概率都增大，路徑ab上的轉移概率減小；
??? (4)當區域a點的空載出租車數量大于140時(即空載出租車供給量大于需求量時)，路徑ab、路徑ac、路徑ad的轉移概率接近于80∶40∶20。
??? 通過試驗可進一步得出空載出租車路徑選擇情況分布圖，如圖3所示。
?
?
??? 觀察圖3可知：
??? (1)當區域a點的空載出租車數量大于20時，開始有空載出租車選擇路徑ac；
??? (2)當區域a點的空載出租車數量大于40時，開始有空載出租車選擇路徑ad；
??? (3)當區域a點的空載出租車數量小于140時，選擇路徑ab、路徑ac、路徑ad的空載出租車數量比例接近于80∶40∶20。
??? 由此可以看出，改進蟻群算法不僅能有效引導空載出租車轉移到能最快找到乘客的交通區域，而且能有效防止過度將交通資源集中于最熱點地區，通過改進蟻群算法中蟻群間的相互抑制作用達到將交通資源更合理分布到各個不同交通區域的目的。
??? 本文將蟻群算法應用到出租車交通資源的路徑規劃問題，提出一種基于改進蟻群算法的空載出租車路徑規劃算法，不僅發揮了蟻群算法的正反饋機制的優點，同時也符合現實交通狀況中的資源分布需求。蟻群算法在交通資源規劃中的應用目前還不完善，本算法的效率和優化度還待進一步改進。
參考文獻
[1]?BELL J E，MCMULLEN P R.Ant colony optimization techniques for the vehicle routing problem [J].Advanced Engineering Informatics，2004，18(1)：41-48.
[2]?JINNIFER L.A computational study of vehicle routing applications[D].Ph.D.thesis，RICE，UNIVERSITY，Huston，1999.
[3]?李士勇.蟻群算法的改進及應用研究進展[J].計算機測量與控制， 2003，11(12)：911-917.
[4]?楊志曉，郭勝國．基于改進蟻群算法的機器人路徑規劃算法[J]．微計算機信息，2008，7(2)：252-253.
[5]?周濤.基于蟻群算法的車輛優化調度系統[D].成都：電子科技大學，2007.
[6]?肖曉麗，田悅宏，李振.一種基于螞蟻算法的網絡負載分擔路由方法[J].計算機應用， 2006,26(7).