賈樂樂　白云　張黎翔

摘要：在城市交通路網(wǎng)中誘導(dǎo)車輛規(guī)劃較優(yōu)出行路線，來提高人們的出行質(zhì)量。本文分別研究了蟻群算法和粒子群算法，并根據(jù)其優(yōu)缺點(diǎn)進(jìn)行了算法融合。同時(shí)學(xué)習(xí)和分析了Transmodeler4.0軟件，建立城市路網(wǎng)，加入仿真數(shù)據(jù)，并模擬了融合算法下的路徑優(yōu)化模型。結(jié)合實(shí)例，通過路徑對(duì)比，提出優(yōu)化方案。

關(guān)鍵詞：蟻群算法；粒子群算法；Transmodeler；路徑仿真

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）36-0166-02

針對(duì)目前智慧城市的要求，出行者迫切需要一個(gè)避免擁堵，安全方便，高效率的出行服務(wù)，交通管理者也需要合理的分配城市路網(wǎng)的交通流，使出行者的行駛路徑達(dá)到最大優(yōu)化[1， 2]。那么，路徑優(yōu)化的研究具有很大的意義。

算法的選擇，直接影響了優(yōu)化結(jié)果的精度。目前，廣泛應(yīng)用于路徑選擇和網(wǎng)絡(luò)路由策略等領(lǐng)域的算法，常見的有群智能優(yōu)化算法的粒子群算法（Particle Swarm Optimization，PSO）和模擬進(jìn)化算法的蟻群算法（Ant Colony Optimization，ACO）。而交通仿真是再現(xiàn)復(fù)雜的真實(shí)交通現(xiàn)象，并對(duì)其進(jìn)行問題解釋、環(huán)境分析、現(xiàn)象預(yù)測(cè)，最終找出問題所在并解決優(yōu)化，并對(duì)所研究的系統(tǒng)進(jìn)行改進(jìn)、比選和評(píng)價(jià)。Transmodeler4.0軟件以地理信息系統(tǒng) （ GIS ）為基礎(chǔ)，采用較為實(shí)用的仿真模型，能夠體現(xiàn)優(yōu)化方案的科學(xué)性和可行性是仿真軟件參數(shù)設(shè)定的最終目標(biāo)，同時(shí)具有結(jié)果評(píng)價(jià)和分析等功能。

本文根據(jù)PSO和ACO兩算法的優(yōu)缺點(diǎn)進(jìn)行算法的融合使用，加入實(shí)例，選出最優(yōu)路徑，并利用Transmodeler4.0軟件對(duì)所選路徑進(jìn)行了仿真模擬，實(shí)驗(yàn)結(jié)果較好。

1 蟻群算法與粒子群算法

1.1 ACO的基本原理

ACO是應(yīng)用最廣的一種算法，其思想源于螞蟻覓食行為，盡管螞蟻個(gè)體非常簡(jiǎn)單，但能表現(xiàn)出強(qiáng)大的社會(huì)群體行為。

若m只螞蟻被隨機(jī)分配到m個(gè)地點(diǎn)。設(shè)各個(gè)路徑上初始信息濃度值為[τ0]，可定為[τ0=m/cmn]，m為螞蟻數(shù)量。變化后的信息濃度為[τijn]。設(shè)定過小的初始信息濃度[τ0]，容易使搜索陷入局部空間；[τ0]過大時(shí)，只有信息素?fù)]發(fā)一部分之后，螞蟻釋放的信息素才能發(fā)揮指引作用。位于地點(diǎn)i的螞蟻選擇地點(diǎn)j依據(jù)如下概率公式[3]：

[pkij（t）=ταij（t）ηβij（t）s∈allowkταis（t）ηβis（t），j∈allowk0，j?allowk]

式中：

[τ0]——路徑（i， j）的信息素濃度；

[nij]——地點(diǎn)間距離的啟發(fā)式信息，[nij=1/dij]；

α，β——兩個(gè)啟發(fā)式信息的參數(shù)，決定啟發(fā)式信息對(duì)螞蟻選擇地點(diǎn)影響的程度；

allow——螞蟻未訪問的地點(diǎn)的集合。

以上是個(gè)體螞蟻的行為特征，要想得到局部最優(yōu)解，需要多只螞蟻多此尋找路徑，一旦發(fā)現(xiàn)新的最短路徑，就將此路徑記錄下來。

1.2 PSO的基本原理

在[D]維的搜索空間內(nèi)，一個(gè)由[M]個(gè)粒子組成的群體按照一定的速度進(jìn)行不斷運(yùn)動(dòng)[7]。粒子[pi]在[t]時(shí)刻[D]維空間里的狀態(tài)如下：

位置記為：[Xti=xti1，xti2，xti3，???，xtid]，i=1，2，3，…，[M]。[xtid∈xmind，xmaxd]，[xmind]，[xmaxd]分別代表搜索空間[D]的下限和上限；

飛行速度為：[Vti=vti1，vti2，vti3，???，vtid]，i=1，2，3，…，[M]。[vtid∈vmind，vmaxd]，

[vmind]，[vmaxd]分別為粒子飛行的最小和最大速度；

個(gè)體最優(yōu)位置：[Pti=pti1，pti2，pti3，???，ptid]，整體最優(yōu)：[Ptg=ptg1，ptg2，ptg3，???，ptgd]；

其中[1≤d≤D]，[1≤i≤M]，粒子群算法進(jìn)行優(yōu)化迭代中，則粒子[pi]在[t+1]時(shí)刻按照以下公式進(jìn)行速度的不斷更新和位置的不斷更新：

PSO的基本算法步驟大概描述如下：

（1）初始化。設(shè)PSO中各類參數(shù)：搜索空間[D]的下限[xmind]和上限[xmaxd]；學(xué)習(xí)因子[c1]，[c2]；算法最高迭代次數(shù)[Tmax]和尋優(yōu)誤差系數(shù)[θ]；粒子的速度上限和下限為[vmind]，[vmaxd]。隨機(jī)初始化各個(gè)粒子的速度[vi]和位置[xi]。

（2）計(jì)算和評(píng)價(jià)每一個(gè)粒子的適應(yīng)值，并記錄粒子的個(gè)體極值[Pti]和全局極值[Ptg]。

（3）將粒子個(gè)體歷史的最好位置[Pti]的適應(yīng)值于當(dāng)前粒子位置適應(yīng)值進(jìn)行比較，[Pti]取優(yōu)。

（4）將每個(gè)粒子的位置的適應(yīng)值和全體粒子最佳位置[Ptg]的適應(yīng)值做比較，[Ptg]取優(yōu)。

（5）根據(jù)以上公式更新粒子的速度和位置。

（6）檢驗(yàn)是否滿足結(jié)束條件。如果當(dāng)前的迭代次數(shù)達(dá)到了最高迭代次數(shù)[Tmax]或結(jié)果誤差小于尋優(yōu)誤差系數(shù)[θ]，那么停止迭代，輸出最優(yōu)解。否則轉(zhuǎn)到步驟（2）。

1.3 算法融合

PSO收斂速度較慢，易陷入局部?jī)?yōu)先，而ACO的搜索具有很大的盲目性。本文針對(duì)兩算法的缺點(diǎn)和實(shí)際交通路徑規(guī)劃在計(jì)算時(shí)間和精度上的高要求，分別對(duì)ACO和PSO做出改進(jìn)，建立混合型算法，模糊缺點(diǎn)，發(fā)揮各自在路徑搜索上的優(yōu)勢(shì)。

利用粒子群算法得到一組優(yōu)化路徑，然后在整體的環(huán)境已經(jīng)加入相同信息素，再?gòu)倪@組路徑中選取部分路徑，加大信息素濃度作為蟻群算法新的初始化信息素，從起點(diǎn)和終點(diǎn)一起進(jìn)行精搜索，從而形成雙向搜索模式，選出最優(yōu)路徑。所謂最優(yōu)，并不是指路程最短，而是時(shí)間與路程的結(jié)合分析。從[O]點(diǎn)到[D]點(diǎn)的所有路徑中，經(jīng)過粒子群的篩選，以下三條路徑可以作為蟻群算法的初始路徑。

2 仿真實(shí)例

2.1 仿真環(huán)境

Transmodeler軟件是目前應(yīng)用比較廣泛的仿真軟件之一。本文使用的是Transmodeler4.0版本，此可以詳細(xì)仿真從高速公路到城市道路各種道路網(wǎng)以及公交站點(diǎn)等設(shè)施[8]。二次開發(fā)是Transmodeler軟件最大的特性，可以使此軟件按照開發(fā)者需求或者城市道路變化需求完成有針對(duì)性的系統(tǒng)重構(gòu)，建立一個(gè)針對(duì)城市道路智能控制算法驗(yàn)證的仿真軟件平臺(tái)。

2.2 實(shí)例模擬

選取2016年5月15上午9點(diǎn)到10點(diǎn)為仿真時(shí)間段，從內(nèi)蒙古工業(yè)大學(xué)新城校區(qū)出發(fā)，目的地為呼和浩特市植物園。通過PSO-ACO融合算法，選出最優(yōu)路徑。

擬定工大新城校區(qū)到呼市植物園路線為仿真背景，在實(shí)際地圖上設(shè)置城市路網(wǎng)（如圖2），加入仿真流量，模擬區(qū)域簡(jiǎn)單仿真環(huán)境。步驟如下：

Transmodeler4.0軟件打開地圖“全景1.jpeg” →建立Simulation Project，并使用Road Editor工具箱，根據(jù)實(shí)況建立城市主干道、快速路、十字路口等仿真環(huán)境→加入仿真流量，以藍(lán)色路徑為仿真背景，通過設(shè)置車型、車速，以及各個(gè)路口的轉(zhuǎn)向流量等，真實(shí)的模擬車輛行駛路徑。

在9：01時(shí)，從工大南門出發(fā)自駕沿著愛民街直行，到達(dá)呼倫貝爾北路，向南經(jīng)歷第三個(gè)十字路口時(shí)，向西進(jìn)入新華大街，通過兩個(gè)路口進(jìn)入新華西街，在9：15時(shí)到達(dá)呼和浩特市植物園?？倸v程將近14分鐘，其中車輛速度根據(jù)實(shí)際情況不斷變化，最高達(dá)到72.4km/h。

3 結(jié)論

本文將粒子群和蟻群算法相結(jié)合，從始發(fā)到終點(diǎn)的路徑中，有效的選出相對(duì)最優(yōu)的路徑，并通過運(yùn)用Transmodeler4.0軟件加入實(shí)例，對(duì)兩節(jié)點(diǎn)間的多條路徑的距離和時(shí)間進(jìn)行對(duì)比分析，為城市道路優(yōu)化和出行提供了可靠的依據(jù)，并為智慧城市的研究提供很大幫助。

參考文獻(xiàn)：

[1] 刁陽， 雋志才. 基于仿真的城市路網(wǎng)動(dòng)態(tài)分配矩陣估計(jì)方法[J]. 系統(tǒng)管理學(xué)報(bào)， 2011， 20（3）：376-383..

[2] 趙明翠， 成衛(wèi)， 戢曉峰，等. 基于TransCAD與TransModeler的交通影響分析方法[J].科學(xué)技術(shù)與工程， 2010， 10（27）：6689-6694.

[3] 吳義虎， 李寧，王正武. 蟻群算法在車輛路徑誘導(dǎo)系統(tǒng)中的應(yīng)用[J].系統(tǒng)工程， 2007， 25（2）：27-31.

[4] 宋世杰， 劉高峰，周忠友，等. 基于改進(jìn)蟻群算法求解最短路徑和TSP問題[J].計(jì)算機(jī)技術(shù)與發(fā)展， 2010， 20（4）：144-147.

[5] 李曉東， 王東， 曾凡智，等. 城市交通時(shí)間最短路徑計(jì)算模型及應(yīng)用仿真[J].計(jì)算機(jī)仿真， 2014， 31（1）：172-175.

[6] 楊慧， 成衛(wèi)， 肖海承，等. 基于TransModeler的擁堵區(qū)域交通流量調(diào)控方法研究[J].科學(xué)技術(shù)與工程， 2011， 11（8）：1746-1750.