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