基于改進(jìn)蟻群算法的高速公路疏散路徑研究

李巧茹，張 倩，陳 亮，崔 寧

(1．河北工業(yè)大學(xué) 土木工程學(xué)院，天津 300401；2．河北省土木工程技術(shù)研究中心，天津 300401)

?

基于改進(jìn)蟻群算法的高速公路疏散路徑研究

李巧茹1，2，張 倩1，陳 亮1，2，崔 寧1

(1．河北工業(yè)大學(xué) 土木工程學(xué)院，天津 300401；2．河北省土木工程技術(shù)研究中心，天津 300401)

根據(jù)高速公路應(yīng)急疏散的特點(diǎn)，在交通分配中應(yīng)用改進(jìn)蟻群算法模型。首先引入路段交通量和通行時(shí)間函數(shù)作為算法轉(zhuǎn)移規(guī)則的一部分，從而在進(jìn)行搜索時(shí)優(yōu)先考慮容量大和通行時(shí)間較短的路徑。其次通過實(shí)驗(yàn)分析蟻群算法參數(shù)對(duì)計(jì)算結(jié)果和收斂速度的影響，給出了最優(yōu)的參數(shù)組合。最后將最優(yōu)參數(shù)組合應(yīng)用于改進(jìn)蟻群算法中，并通過仿真實(shí)驗(yàn)將改進(jìn)蟻群算法與基礎(chǔ)蟻群算法的路徑搜索結(jié)果進(jìn)行對(duì)比。結(jié)果表明：采用最優(yōu)參數(shù)組合的蟻群算法不但加快了搜索速度，而且優(yōu)化了全局最優(yōu)解，通過基于GIS的高速公路應(yīng)急疏散系統(tǒng)進(jìn)行路徑分析，得到系統(tǒng)最優(yōu)的可視化疏散路徑。

交通工程；疏散路徑；蟻群算法；參數(shù)分析

0 引 言

出行者在高速公路上進(jìn)行應(yīng)急疏散路徑選擇時(shí)，需要根據(jù)道路的實(shí)時(shí)信息進(jìn)行疏散路線判斷，采用動(dòng)態(tài)路徑分析模型，并且結(jié)合合理的路徑搜索算法以最短時(shí)間進(jìn)行路徑信息分析。王旭，等[1]將蟻群算法應(yīng)用于路徑規(guī)劃中，通過仿真實(shí)驗(yàn)比較蟻群算法和Dijksrta算法，發(fā)現(xiàn)蟻群算法可以較快地找到一條近似最優(yōu)路徑；劉勇[2]指出人工智能算法是模擬自然界中生物為優(yōu)化其生存狀態(tài)，而進(jìn)行適應(yīng)環(huán)境的無意識(shí)尋優(yōu)行為的優(yōu)化仿生算法，這類算法具有不確定性，或理解為伴有一定的隨機(jī)性，這種不確定性體現(xiàn)在自然界生物的生理機(jī)制，在求解某些復(fù)雜問題時(shí)優(yōu)于Floyd算法和Dijksrta算法等確定型算法；徐勛倩，等[3]將蟻群算法應(yīng)用于動(dòng)態(tài)交通網(wǎng)絡(luò)的用戶均衡配流問題，但對(duì)非平衡問題沒有做相應(yīng)研究；孫華燦，等[4]提出將基礎(chǔ)蟻群算法引入容量限制模型中，將交通分配的確定性與用戶出行的隨機(jī)性融入路徑的搜索過程，并通過實(shí)例證明其可行性。這些文獻(xiàn)證明了蟻群算法進(jìn)行路徑分析時(shí)有較好的隨機(jī)性、適用于大規(guī)模網(wǎng)絡(luò)，并且對(duì)于相同規(guī)模的網(wǎng)絡(luò)其比傳統(tǒng)路徑算法用時(shí)短。

傳統(tǒng)蟻群算法在求解路徑優(yōu)化問題中存在收斂速度慢、容易陷入局部最優(yōu)路徑等不足，然而由于蟻群算法具有正反饋、分布式計(jì)算等優(yōu)勢(shì)，其參數(shù)組合問題已經(jīng)成為不同應(yīng)用者關(guān)注的焦點(diǎn)[5-7]。胡耀民，等[8]通過引入信息素更新算子并改進(jìn)能見度啟發(fā)因子α，改進(jìn)了蟻群算法，能準(zhǔn)確找出滿足路徑質(zhì)量約束的最優(yōu)路徑，但其運(yùn)行速度較慢；胡啟國，等[9]通過重新設(shè)計(jì)算法的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則，解決了蟻群算法容易陷入局部最優(yōu)解和搜索時(shí)間過長(zhǎng)的問題，但其旨在解決最優(yōu)冗余分配問題。

綜上所述，筆者針對(duì)高速公路疏散路徑問題采用路徑分配模型在基礎(chǔ)蟻群算法的基礎(chǔ)上進(jìn)行局部更新和全局更新兩種信息素更新方式，并采用和分析不同的信息素?fù)]發(fā)系數(shù)ρ，σ。以河北省高速公路調(diào)查數(shù)據(jù)為基礎(chǔ)，建立容量限制動(dòng)態(tài)分配模型，改進(jìn)路徑搜索和交通量分配算法；在基礎(chǔ)蟻群算法的基礎(chǔ)上引入了μij變量對(duì)蟻群的轉(zhuǎn)移規(guī)則進(jìn)行改進(jìn)，從道路的實(shí)際情況出發(fā)，進(jìn)行動(dòng)態(tài)信息素分配，提高算法的收斂速度。通過多組實(shí)驗(yàn)數(shù)據(jù)分析改進(jìn)模型中的參數(shù)最優(yōu)組合，并以ArcGIS Engine、Visual Studio+C#為開發(fā)環(huán)境，搭建高速公路應(yīng)急疏散系統(tǒng)進(jìn)行疏散路徑分析。

1 基于改進(jìn)蟻群算法路徑分析模型

容量限制分配是非平衡模型中的一種動(dòng)態(tài)分配模型，這種分配模型在考慮路段路阻的前提下，可以通過對(duì)路徑搜尋方法以及交通量加載方法進(jìn)行改進(jìn)，并且在交通分配模型中將最優(yōu)分配與用戶隨機(jī)分配兩種方式分配相結(jié)合。筆者在孫華燦，等[4]的研究基礎(chǔ)上對(duì)蟻群算法的轉(zhuǎn)移規(guī)則和信息素更新方式進(jìn)行改進(jìn)，以提高算法的收斂性和收斂精度。

1.1 交通路阻

在公路上出行者所花費(fèi)的時(shí)間與該路段上的交通流量成正比，其時(shí)間與交通量之間的關(guān)系可表達(dá)為：

ta=f(qa)

(1)

式中：ta為通過路段a所花費(fèi)的時(shí)間；qa為路段a上的交通量。

對(duì)于行駛在公路上的時(shí)間函數(shù)模型有基于交通3參數(shù)的路阻函數(shù)模型，我國學(xué)者將非機(jī)動(dòng)車因素考慮進(jìn)BPR函數(shù)中而提出的路阻函數(shù)模型，但是使用最為普遍的還是由美國聯(lián)邦公路局開發(fā)的路阻函數(shù)，BPR模型表達(dá)式為：

(2)

1.2 適用于路徑分析的蟻群算法

蟻群算法中的基本變量為[10]：m為蟻群中的螞蟻數(shù)量；n為交通網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)；τij為邊(i,j)上蟻群釋放的信息軌跡強(qiáng)度；Δτij(t)為螞蟻在邊(i,j)上留下的單位長(zhǎng)度的信息素含量(信息素增量)；α2為信息啟發(fā)因子，可以表示運(yùn)動(dòng)軌跡的重要程度，α2值越大說明螞蟻趨向于其他螞蟻所走路徑的概率越大；β2為期望啟發(fā)式因子，反映能見度的重要程度，β2值越大說明轉(zhuǎn)移概率越接近于貪心規(guī)則。

1.2.1 轉(zhuǎn)移規(guī)則的改進(jìn)

在基本蟻群算法中，螞蟻根據(jù)隨機(jī)比例規(guī)則進(jìn)行下一步路徑選擇，而在改進(jìn)后的蟻群系統(tǒng)中使用的是偽隨機(jī)比例規(guī)則。第k只在某節(jié)點(diǎn)選擇下一個(gè)允許到達(dá)的節(jié)點(diǎn)j的規(guī)則如式(3)：

(3)

(4)

(5)

(6)

式中：p為螞蟻k由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的轉(zhuǎn)移概率；q為[0,1]上均勻分布的隨機(jī)數(shù)；q0∈[0,1]，為一個(gè)參數(shù)；allowedk表示螞蟻k下一步能選擇的城市或節(jié)點(diǎn)，且allowedk={1,2,3, …,n}-tabuk，tabuk為螞蟻設(shè)置的禁忌表，它記錄了當(dāng)前時(shí)刻螞蟻所搜索過的城市(節(jié)點(diǎn))，約束螞蟻不能在此次循環(huán)中第二次訪問這些城市；dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離；tij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間；qij為節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的交通容量；μij為路阻的函數(shù)，它的引入保證了算法在路徑搜索時(shí)更傾向于通行時(shí)間短和交通容量較大的路段。

在算法的開始階段，初始化參數(shù)時(shí)，各路段的初始信息素相差不大，使得ηij和μij可以提供有助于在循環(huán)初期算法快速收斂的局部信息。在迭代進(jìn)行的過程中，信息素會(huì)隨著路徑的搜索而不斷改變，這時(shí)ηij和μij在體現(xiàn)解信息方面的重要性在不斷提高。鑒于此，提出對(duì)ηij和μij設(shè)計(jì)一種倒指數(shù)關(guān)系曲線以體現(xiàn)其重要性，同時(shí)由于在算法迭代過程中行駛時(shí)間和交通量對(duì)路徑影響較大，所以在設(shè)計(jì)中μij的權(quán)重比ηij的權(quán)重相對(duì)要大一些，故而關(guān)系曲線如式(7)、式(8)：

(7)

(8)

式中：NC=1，2，…，NC_max，為當(dāng)前迭代。

1.2.2 信息素更新方式的改進(jìn)

由概率選擇公式可知，當(dāng)在一個(gè)選擇交叉點(diǎn)上時(shí)，若其中一個(gè)選擇的信息素濃度高于其他選擇時(shí)，螞蟻選擇這個(gè)解的概率大，隨著循環(huán)的不斷進(jìn)行，這條路徑上的信息素濃度不斷加強(qiáng)，則會(huì)導(dǎo)致螞蟻不斷地重復(fù)選擇同一條路徑而出現(xiàn)停滯現(xiàn)象。同時(shí)若是某條路徑上的信息素濃度過低對(duì)進(jìn)行全局搜索也是不利的。因此根據(jù)最大-最小蟻群系統(tǒng)的優(yōu)化思想，將信息素濃度的取值設(shè)定在[τmin, τmax]范圍內(nèi)，要求每一次循環(huán)過后，信息素濃度必須符合這個(gè)限制：若τij(t)>τmax，取τij(t)=τmax；若τij(t)<τmin，則取τij(t)=τmin。對(duì)信息素濃度進(jìn)行上限設(shè)置，避免在路徑搜索過程中各路段之間的信息素濃度差異過大；對(duì)信息素濃度進(jìn)行下限設(shè)置，避免當(dāng)某些選擇的概率非常小時(shí)信息素不至于為0，盡量降低停滯現(xiàn)象發(fā)生的機(jī)率。τmin和τmax的計(jì)算如式(9)、式(10)：

(9)

(10)

式中：Lnn為采用最鄰域算法求解初始路徑的最短距離。

每一次迭代完成后找出新的最優(yōu)解Lgb，則τmax按式(11)更新：

(11)

考慮到在迭代不斷進(jìn)行的過程中，信息素濃度的變化，將各路徑的初始值設(shè)為τmax，可以避免信息素濃度相對(duì)之間差異的不斷增加，還可以提高算法在初期的尋優(yōu)能力，改善螞蟻系統(tǒng)求解最優(yōu)值的性能。

1)在搜索過程中，若某一條道路上的信息素濃度過高，則會(huì)引起路徑算法早熟，出現(xiàn)局部最優(yōu)的情況，因此有必要引入局部更新規(guī)則。在局部更新規(guī)則中，當(dāng)螞蟻k完成某一個(gè)路段的搜索后，其所經(jīng)過路段的信息素按局部更新規(guī)則更新。信息素更新規(guī)則如下：

(12)

(13)

式中：τ0為初始信息素濃度；N為路網(wǎng)中的節(jié)點(diǎn)個(gè)數(shù)；Lnn為初始最短路徑的長(zhǎng)度；ρ為信息素局部揮發(fā)系數(shù)，取值在[0，1]之間，表示信息素?fù)]發(fā)的快慢。

2)對(duì)信息素進(jìn)行全局更新是指當(dāng)所有螞蟻均完成對(duì)所有路徑搜索之后，在全局信息素更新中僅允許生成最優(yōu)解的螞蟻對(duì)信息素進(jìn)行釋放。公式如下：

(14)

(15)

式中：δ∈[0,1]，表示全局信息素衰減系數(shù)；R為常數(shù)；Lgb為目前迭代中找出的全局最優(yōu)解。

2 模型的參數(shù)分析

由于在算法進(jìn)行過程中，螞蟻在選擇下一個(gè)行駛路段時(shí)會(huì)根據(jù)信息素信息進(jìn)行判斷，因此在每次實(shí)驗(yàn)中只改變一個(gè)參數(shù)，其他參數(shù)不變，重復(fù)對(duì)每一組做20次試驗(yàn)，然后比較所得結(jié)果的平均值，目的是消除偶然因素對(duì)算法參數(shù)的影響。根據(jù)高速公路道路網(wǎng)的規(guī)模，選取76個(gè)節(jié)點(diǎn)(最優(yōu)解108 159)，在ArcGIS中讀取這些點(diǎn)狀物的坐標(biāo)，作為算法分析的基礎(chǔ)數(shù)據(jù)，選定起始點(diǎn)和終點(diǎn)不變，根據(jù)經(jīng)驗(yàn)將初始參數(shù)設(shè)置為α2=1、ρ=0.1，δ=0.1、m=10，NC_max=5 000。筆者提出的改進(jìn)算法中，大多數(shù)變量參數(shù)是隨著迭代過程中信息素、交通量、路段通行時(shí)間的變化而改變。由于沒有精確的公式進(jìn)行初始設(shè)置，部分參數(shù)根據(jù)應(yīng)用領(lǐng)域的不同而采用不同的取值，因此筆者對(duì)α2，ρ，σ，m這4個(gè)參數(shù)進(jìn)行實(shí)驗(yàn)分析，從而獲得參數(shù)的最優(yōu)組合。

2.1 啟發(fā)因子的實(shí)驗(yàn)分析

筆者對(duì)α2以0.5為間隔取10個(gè)不同的值進(jìn)行結(jié)果比對(duì)。α2反映的是在算法進(jìn)行過程中信息素對(duì)螞蟻進(jìn)行路徑選擇的相對(duì)重要程度，而當(dāng)其取值較小時(shí)，會(huì)減弱信息素對(duì)螞蟻的影響，這時(shí)螞蟻主要受啟發(fā)信息的影響，容易過早的收斂于局部最優(yōu)解；當(dāng)α2的取值較大時(shí)，信息素在螞蟻的移動(dòng)過程中發(fā)揮主要作用，有時(shí)會(huì)淹沒啟發(fā)信息，所以此時(shí)螞蟻選擇已走過路徑的概率增大，使得算法結(jié)果變差。

圖1為算法搜索的迭代次數(shù)與全局最優(yōu)解隨α2變化的趨勢(shì)。由圖1可知全局最優(yōu)解以及算法的迭代次數(shù)隨著α2不斷增大呈近似線性增長(zhǎng)的趨勢(shì)。當(dāng)α2較小時(shí)，算法過早收斂，且容易陷入局部最優(yōu)解；當(dāng)α2較大時(shí)，收斂速度較慢，由于正反饋?zhàn)饔?，使得全局最?yōu)解比較大。綜合考慮全局最優(yōu)解及迭代次數(shù)，當(dāng)α2∈[1,2]時(shí)，算法的求解性能較好，本研究取α2=1.5。

圖1 α2對(duì)算法運(yùn)行結(jié)果的影響

2.2 局部信息素?fù)]發(fā)系數(shù)的實(shí)驗(yàn)分析

ρ是局部信息素?fù)]發(fā)系數(shù)，反映某一只螞蟻完成一次循環(huán)后信息素消失的快慢，它是在某一只螞蟻完成所有節(jié)點(diǎn)訪問后，對(duì)該螞蟻所走過的路徑上的信息素濃度進(jìn)行調(diào)整。當(dāng)ρ較小時(shí)，該螞蟻所走過的路徑上信息素殘留較大，容易吸引其他螞蟻向同一條路徑行駛，使算法收斂于局部最優(yōu)解；當(dāng)ρ較大時(shí)，這條路徑上的信息素?fù)]發(fā)較快，降低其中某些路段的被選中概率，使得算法收斂速度降低。

圖2為ρ的不同取值引起的迭代次數(shù)和全局最優(yōu)解的變化。從圖2可知全局最優(yōu)解在ρ較小或較大時(shí)比較敏感，變化趨勢(shì)較大，因此從最優(yōu)解的角度取值在區(qū)間[0.15，0.5]時(shí)，算法比較穩(wěn)定；若將迭代次數(shù)考慮進(jìn)去，ρ=0.15比較合適。

圖2 ρ對(duì)算法運(yùn)行結(jié)果的影響

2.3 全局信息素?fù)]發(fā)系數(shù)的實(shí)驗(yàn)分析

δ的取值大小對(duì)蟻群算法的全局搜索能力和收斂速度有著重要的影響，王穎，等[11]指出δ對(duì)蟻群算法的影響是具有雙重性的。當(dāng)δ較小時(shí)，將使得未被搜索過的路徑上的信息軌跡強(qiáng)度減弱，減小算法的搜索空間，加大陷入局部最優(yōu)解的可能性，反而增強(qiáng)收斂速度；當(dāng)δ較大時(shí)，搜索過的路徑上的信息軌跡強(qiáng)度減弱，擴(kuò)大了蟻群的搜索范圍，從而減低了算法的收斂性，但同時(shí)也減小了陷入局部最優(yōu)解的可能性。

圖3是全局揮發(fā)系數(shù)對(duì)算法結(jié)果的影響。當(dāng)δ值較小時(shí)，全局最優(yōu)解較大，且迭代次數(shù)也較多；當(dāng)δ值較大時(shí)，全局最優(yōu)解呈線性增長(zhǎng)，這說明δ的增大使得螞蟻再次選擇已搜索過路徑的可能性增大，降低了算法的隨機(jī)性和進(jìn)行全局搜索路徑的能力。從圖3中可知當(dāng)δ在[0.1，0.4)和(0.4,0.5]區(qū)間內(nèi)算法的計(jì)算性能穩(wěn)定，收斂速度和收斂性較好。而且通過對(duì)20組值進(jìn)行最優(yōu)解及最優(yōu)解出現(xiàn)次數(shù)的分析，可知當(dāng)δ=0.2時(shí)，算法的性能最好。

圖3 δ取值對(duì)算法運(yùn)行結(jié)果的影響

2.4 螞蟻數(shù)量的參數(shù)分析

蟻群算法是從多個(gè)候選解組成的群體在不斷進(jìn)化的過程中尋找到最優(yōu)解的，它的優(yōu)勢(shì)即為并行搜索[12]。螞蟻數(shù)目較多時(shí)，可以增強(qiáng)算法的全局搜索能力和其穩(wěn)定性，然而當(dāng)數(shù)目過多時(shí)，會(huì)出現(xiàn)已搜索過的路徑上的信息素濃度變化較為接近，降低算法的正反饋?zhàn)饔茫沟檬諗克俣葴p慢；而當(dāng)螞蟻數(shù)目過少時(shí)，使得已搜索和未被搜索的路徑上的信息素濃度差異較大，尤其是當(dāng)路網(wǎng)規(guī)模較大時(shí)，將會(huì)減弱算法的全局搜索能力和隨機(jī)性，雖然可以提高算法的收斂速度，但卻導(dǎo)致算法穩(wěn)定性變差。

圖4 m取值對(duì)算法運(yùn)行結(jié)果的影響

表1 螞蟻數(shù)量m與搜索時(shí)間的關(guān)系

因此通過設(shè)定初始值對(duì)算法中的參數(shù)進(jìn)行分析，可得到蟻群算法的最優(yōu)組合為α2∈[1,2]，ρ∈[0.15，0.5]，δ∈[0.1，0.4)∪(0.4,0.5]，m∈ [10，40]。根據(jù)實(shí)驗(yàn)對(duì)最優(yōu)值與初始值進(jìn)行對(duì)比，最優(yōu)組合參數(shù)為：α2=1.5，ρ=0.15，δ=0.2，m=30；初始設(shè)置參數(shù)：α2=1，ρ=0.1，δ=0.1，m=10；迭代次數(shù)均為5 000。圖5是參數(shù)更新前后對(duì)算法運(yùn)行結(jié)果的影響，參數(shù)更新前后的分析結(jié)果見表2。

圖5 參數(shù)更新前后對(duì)算法運(yùn)行結(jié)果的影響

表2 參數(shù)更新前后的分析結(jié)果

對(duì)圖5和表2分析可知，對(duì)蟻群算法的參數(shù)采用最優(yōu)組合后，不但提高了算法的收斂速度，同時(shí)也提高了全局搜索能力和算法的穩(wěn)定性。因此進(jìn)行路徑分析時(shí)模型參數(shù)的初始值采用最優(yōu)組合參數(shù)。

3 實(shí)例分析

3.1 GIS平臺(tái)及系統(tǒng)設(shè)計(jì)的基本原理

ArcGIS 10.1是美國環(huán)境系統(tǒng)研究公司(Environmental Systems Research Institute, Inc. 簡(jiǎn)稱ESRI)開發(fā)的地理信息系統(tǒng)軟件，ArcGIS Engine是一個(gè)簡(jiǎn)單的并且可以脫離應(yīng)用程序ArcObjects編程環(huán)境，是建立嵌入式GIS組件的自定義應(yīng)用程序的類庫。Microsoft Visual Studio 2010是面向組件模型COM使用C#語言的一種開發(fā)工具，在Visual Studio中新建一個(gè)Windows窗體應(yīng)用程序，可以添加TOCControl、ToolbarControl、MapControl、LicenseControl控件和相關(guān)引用。

高速公路應(yīng)急疏散路徑分配以ArcGIS 10.1、ArcGIS Engine以及C#為分析及開發(fā)平臺(tái)。主要技術(shù)為：①根據(jù)河北省交通圖制作ArcGIS的路網(wǎng)矢量圖，設(shè)置路網(wǎng)屬性；②使用ArcCatalog構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)集，為路徑分析做準(zhǔn)備；③使用C#語言于Visual Studio 2010軟件平臺(tái)編寫模型算法程序；④借助ArcGIS Engine進(jìn)行系統(tǒng)設(shè)計(jì)，調(diào)用ArcGIS 10.1服務(wù)引用，實(shí)現(xiàn)路徑分配。

3.2 高速公路應(yīng)急疏散路徑分析

選取河北省域內(nèi)交通局域網(wǎng)作為研究對(duì)象，其中包含的高速公路與國省干線有G4京港澳高速、G18榮烏高速、G5京昆高速、S52保阜高速(保滄高速)、G107國道、S232省道、S331省道、S335省道、S334省道、S382省道、S241省道、S237省道。通過ArcGIS的網(wǎng)絡(luò)分析工具條，設(shè)置停靠點(diǎn)如圖6，假設(shè)S52上從P2點(diǎn)向東方向與G107之間出現(xiàn)單向斷交情況。根據(jù)道路的屬性信息，在界面右側(cè)設(shè)置需要進(jìn)行疏散的交通量，疏散點(diǎn)為P1，事故點(diǎn)為P2，目的地為P3，然后進(jìn)行分析求解。蟻群算法的參數(shù)設(shè)置見表3，路徑分配結(jié)果見圖6和表4。

表3 蟻群模型參數(shù)設(shè)置

圖6 系統(tǒng)分配結(jié)果顯示

表4 分配結(jié)果

3.3 蟻群算法在應(yīng)急疏散路徑中的分析

取路網(wǎng)中節(jié)點(diǎn)坐標(biāo)為基礎(chǔ)數(shù)據(jù)進(jìn)行計(jì)算，比較采用最優(yōu)參數(shù)組合的改進(jìn)蟻群算法和基礎(chǔ)蟻群算法的性能。圖7是兩種蟻群算法的分析結(jié)果。

圖7 兩種蟻群算法的分析結(jié)果

對(duì)圖7進(jìn)行分析可知，改進(jìn)蟻群算法在迭代次數(shù)為40次與120次之間保持穩(wěn)定，不再更新最優(yōu)解，但在140次迭代之后再次開始全局更新直至接近160次時(shí)搜索到全局最優(yōu)解，待全局最優(yōu)解不再更新之后停止迭代，算法結(jié)束；而基礎(chǔ)蟻群算法在100次與140次循環(huán)之間保持穩(wěn)定，從第160次迭代開始最短路徑長(zhǎng)度發(fā)生微小變化之后，在第200次迭代時(shí)停止，算法結(jié)束。由此可知改進(jìn)的蟻群算法節(jié)省了20次迭代所用的時(shí)間，加快了算法的運(yùn)行和收斂速度。

改進(jìn)蟻群算法雖在蟻群開始移動(dòng)初期搜索的最短距離大于基礎(chǔ)蟻群，但在算法進(jìn)行過程中逐漸顯示優(yōu)勢(shì)，蟻群搜索的最短路徑長(zhǎng)度出現(xiàn)較明顯的差異。改進(jìn)蟻群算法的全局最優(yōu)解的路徑比基礎(chǔ)蟻群全局最優(yōu)解的路徑長(zhǎng)度縮短近300 m，優(yōu)化了全局最優(yōu)解并且提高了收斂精度。

4 結(jié) 論

在分析高速公路路段阻抗的基礎(chǔ)上，從路徑分配模型參數(shù)研究入手，采用改進(jìn)的蟻群算法求解交通事件發(fā)生時(shí)高速公路應(yīng)急疏散路徑問題，得到如下結(jié)論：

1)采用改進(jìn)的蟻群算法可以提高算法的搜索速度和收斂性，本研究引入μij函數(shù)作為螞蟻的轉(zhuǎn)移規(guī)則，可以更好的體現(xiàn)容量限制分配中路阻的影響作用，使螞蟻在進(jìn)行下一個(gè)路段選擇時(shí)更傾向于通行時(shí)間短，交通容量大的路段，更加切合駕駛員行駛過程中的路徑選擇行為。

3)以ArcGISEngine和C#作為分析及開發(fā)平臺(tái)，設(shè)計(jì)高速公路應(yīng)急疏散系統(tǒng)，對(duì)應(yīng)急疏散路徑進(jìn)行分析，實(shí)現(xiàn)系統(tǒng)可視化疏散路徑，便于出行者對(duì)疏散路徑的理解和選擇，同時(shí)方便管理者決策。

[1] 王旭,崔平遠(yuǎn),陳陽舟．基于蟻群算法求路徑規(guī)劃問題的新方法及仿真[J]．計(jì)算機(jī)仿真,2005,22(7):60-62.WangXu,CuiPingyuan,ChenYangzhou.Anewmethodandsimulationforpathplanningproblembasedonantcolonyalgorithm[J].ComputerSimulation,2005,22(7):60-62.

[2] 劉勇．基于蟻群算法的應(yīng)急救援最優(yōu)路徑研究[D]．武漢:中國地質(zhì)大學(xué),2010. Liu Yong.The Research on the Optimal Path of Emergency Rescue Based on Ant Colony Algorithm[D].Wuhan:China University of Geosciences,2010.

[3] 徐勛倩,黃衛(wèi)．螞蟻算法處理動(dòng)態(tài)交通網(wǎng)絡(luò)用戶均衡配流問題[J]．公路交通科技,2005,1(1):111-114. Xu Xunqian,Huang Wei.Ant algorithm for users equilibrium assignment model of dynamic traffic network[J].Journal of Highway and Transportation Research and Development,2005,1(1):111-114.

[4] 孫華燦,李旭宏,劉艷忠,等．容量限制分配的蟻群優(yōu)化算法[J]．東南大學(xué)學(xué)報(bào):自然科學(xué)版,2009,39(1):177-180. Sun Huacan,Li Xuhong,Liu Yanzhong,et al.Ant colony optimization arithmetic of capacity restraint traffic assignment[J].Journal of Southeast University:Natural Science,2009,39 (1):177-180.

[5] 詹士昌,徐婕,吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇[J].科技通報(bào),2003,19(5):381- 386. Zhang Shichang,Xu Jie,Wu Jun.The optimal selection on the parameters of the ant colony algorithm[J].Bulletin of Science and Technology,2003,19(5):381- 386.

[6] 徐紅梅,陳義保,劉加光,等.蟻群算法中參數(shù)設(shè)置的研究[J].山東理工大學(xué)學(xué)報(bào):自然科學(xué)版,2008,22(1):7-11. Xu Hongmei,Chen Yibao,Liu Jiaguang,et al.The research on the parameters of the ant colony algorithm[J].Journal of Shandong University of Technology:Natural Science,2008,22(1):7-11.

[7] 葉志偉,鄭肇葆.蟻群算法中參數(shù)α,β,ρ設(shè)置的研究——以 TSP 問題為例[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2004,29(7):597-601. Ye Zhiwei,Zheng Zhaobao.Configuration of parametersα,β,ρin ant algorithm[J].Geomatics and Information Science of Wuhan University,2004,29(7):597-601.

[8] 胡耀民,劉偉銘.基于改進(jìn)型蟻群算法的最優(yōu)路徑問題求解[J].華南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2010,38(10):105-110. Hu Yaomin,Liu Weiming.Solving of optimal path problem based on improved ant colony algorithm[J].Journal of South China University of Technology:Natural Science,2010,38(10):105-110.

[9] 胡啟國,胡小華,吳泳龍．改進(jìn)蟻群算法在系統(tǒng)可靠度最優(yōu)冗余分配的應(yīng)用[J].重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版,2013,32(3):543-546. Hu Qiguo,Hu Xiaohua,Wu Yonglong.Application of improved ant colony algorithm in system reliability optimization of redundancy allocation[J].Journal of Chongqing Jiaotong University:Natural Science,2013,32(3):543-546.

[10] Bonabeau E,Dorigo M,Theraulaz G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999,10-32.

[11] 王穎,謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[ J].系統(tǒng)仿真學(xué)報(bào),2002,14(1):31-33. Wang Ying,Xie Jianying.An adaptive ant colony optimization algorithm and simulation[J].Journal of System Simulation,2002,14 (1):31-33.

[12] 覃剛力,楊家本.自適應(yīng)調(diào)整信息素的蟻群算法[J].信息與控制,2002,31(3):198-201. Tan Gangli,Yang Jiaben.An improved ant colony algorithm based on adaptively adjusting pheromone [J].Information and Control,2002,31(3):198-201.

Study on Highway Evacuation Route Based on Improved Ant Colony Algorithm

Li Qiaoru1,2, Zhang Qian1, Chen Liang1,2, Cui Ning1

(1. College of Civil Engineering, Hebei University of Technology, Tianjin 300401, China; 2. Civil Engineering Technology Research Center of Hebei Province, Tianjin 300401, China)

According to the characteristics of expressway emergency evacuation, improved ant colony algorithm was applied in traffic assignment models. Firstly, the function of traffic flow and capacity was introduced as a part of the algorithm state transition rules. Consequently the paths with larger capacity and shorter travel time were chosen preferentially when searching. Secondly, the influences of ant colony algorithm parameters on calculation results and the convergence speed were studied by experimental analysis, then the optimal combination of algorithm parameters were presented accordingly. Finally, the optimal parameter combination was applied to the improved ant colony algorithm, and the searching results were compared with the basic ant colony algorithm through simulation experiments. The results show that ant colony algorithm with the optimal combination parameter has advantages in accelerating the search speed and optimizing the global optimal solution. The visual emergency evacuation paths are available through the path analysis via expressway emergency evacuation system based on GIS.

traffic engineering; evacuation route; ant colony algorithm; parametric analysis

10.3969/j.issn.1674-0696.2015.03.19

2013-11-21；

2014-03-06

河北省人力資源與社會(huì)保障廳留學(xué)人員科技活動(dòng)項(xiàng)目(D2011001)；河北省高等學(xué)?？茖W(xué)技術(shù)研究重點(diǎn)項(xiàng)目(ZD2014078)

李巧茹(1972—)，女，河北石家莊人，副教授，博士，主要從事交通運(yùn)輸規(guī)劃管理與控制方面的研究。E-mail：qiaoruli129@126.com。

U495

A

1674-0696(2015)03-086-07