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