陳柯 劉曉莉

（長(zhǎng)安大學(xué)，陜西 西安 710064）

基于混合優(yōu)化算法的城市應(yīng)急疏散公交車(chē)輛路徑優(yōu)化研究

陳柯 劉曉莉

（長(zhǎng)安大學(xué)，陜西 西安 710064）

本文就突發(fā)事件條件下，研究用公交車(chē)進(jìn)行疏散的路徑選擇的模型，叫做混合優(yōu)化算法求解模型，該模型是基于粒子群算法和螞蟻群算法。用粒子群算法的粒子位置向量得到每輛公交車(chē)所需運(yùn)送的人群種類(lèi)，用蟻群算法優(yōu)化單車(chē)路徑，根據(jù)優(yōu)化的總路徑評(píng)價(jià)得到最優(yōu)解。

車(chē)輛路徑；粒子群算法；螞蟻群算法

目前城市交通應(yīng)急管理大多集中在宏觀管理體系建設(shè)方面，針對(duì)公交應(yīng)急疏散救援理論和方法的研究幾乎沒(méi)有進(jìn)行?？紤]到這一方面，本文將公交車(chē)作為疏散主要研究對(duì)象，研究在應(yīng)急情況下，如何選擇道路最優(yōu)疏散路徑的問(wèn)題。運(yùn)用了粒子群算法和螞蟻群算法，建立一種混合算法的城市公交應(yīng)急疏散公交車(chē)輛路徑優(yōu)化模型。

1 粒子群算法與螞蟻群算法模型的改進(jìn)

1.1 粒子群算法

粒子群算法是模仿鳥(niǎo)之間的集體協(xié)作使群體覓食路徑達(dá)到最優(yōu)。本文將其運(yùn)用到城市公交應(yīng)急疏散公交車(chē)輛路徑優(yōu)化中，并進(jìn)行適當(dāng)?shù)男薷摹Ｏ葮?gòu)造一個(gè)有R個(gè)粒子的D維空間，每一維對(duì)應(yīng)需運(yùn)送的一種人群體，記為隨機(jī)的公交車(chē)號(hào)l，即粒子r的D維位置向量Xr（Xr=xr1，xr2，…，xrd）表示所有車(chē)輛分配到的一種人群體。由于粒子群算法的位置向量得到的是每輛公家車(chē)所需運(yùn)送的人群體，但得不到車(chē)輛所走的順序，所以單車(chē)優(yōu)化路徑還要另算出。

1.2 螞蟻群算法

螞蟻群算法是一種基于種群的模擬進(jìn)化算法。先進(jìn)行參數(shù)和初始化種群的設(shè)置，接著進(jìn)行螞蟻構(gòu)造路徑，采用局部更新的規(guī)則，循環(huán)結(jié)束后，若不符合要求則重新構(gòu)造，若符合要求則進(jìn)入找出最短路徑并應(yīng)用全局更新規(guī)則，不滿足終止條件則重新進(jìn)行螞蟻構(gòu)造路徑，直至滿足終止條件再結(jié)束，該路徑就為最優(yōu)路徑。

2 城市公交應(yīng)急疏散公交車(chē)輛路徑優(yōu)化研究

城市應(yīng)急疏散公交車(chē)輛路徑優(yōu)化研究問(wèn)題中要求將每個(gè)乘客安全快速地疏散，這就要求至少訪問(wèn)一次與乘客相關(guān)的所在地、疏散目的地，而一輛公交車(chē)一次運(yùn)輸能力常滿足不了疏散中心的總乘客數(shù)，所以需要單輛公交車(chē)多次訪問(wèn)或多輛公交車(chē)一次訪問(wèn)。為了方便，本文把乘客相關(guān)的所在地、疏散地統(tǒng)稱(chēng)為節(jié)點(diǎn)。由于疏散地的乘客要送往的目的地不同，將乘客按照從所在地到疏散地不同進(jìn)行分類(lèi)，成為人群種類(lèi)。

2.1 模型參數(shù)確定

路網(wǎng)G=（P，A），V表示網(wǎng)絡(luò)圖中的全部點(diǎn)集，即節(jié)點(diǎn)i,j∈P，A表示網(wǎng)絡(luò)圖中全部?。籱v表示公交車(chē)的荷載量；T表示公交車(chē)輛總數(shù)，l表示第l輛公交車(chē)，l∈T；x1ij表示公交車(chē)輛l是否從節(jié)點(diǎn)i直接到節(jié)點(diǎn)j，取1表示是,取0表示否；di表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離；Lvmax表示公交車(chē)輛最大出行里程；表示公交車(chē)輛l的固定成本。

2.2 路徑優(yōu)化模型

為了使作用的公交車(chē)輛總路徑級(jí)車(chē)輛數(shù)最優(yōu)為目標(biāo)，本文將系統(tǒng)優(yōu)化的最優(yōu)方案為：

2.3 模型基本步驟的構(gòu)想

本文研究的算法是利用粒子算法、蟻群算法組成的混合算法進(jìn)行城市公交應(yīng)急疏散公交車(chē)輛路徑優(yōu)化研究，使得優(yōu)化結(jié)果全局最優(yōu)。先用粒子群算法的位置向量產(chǎn)生每輛公交車(chē)需要運(yùn)送的人群，再用螞蟻群算法為每輛公交車(chē)設(shè)計(jì)出路徑，最后進(jìn)行綜合評(píng)價(jià)，選出最優(yōu)路徑，使得全局盡可能最優(yōu)。

具體實(shí)現(xiàn)步驟：（1）確定粒子群算法；（2）蟻群算法的所需參數(shù)；（3）確定每個(gè)粒子位置向量Xr，其每一維隨機(jī)取[0，M-1]中的整數(shù)；（4）確定速度向量vr，其每一維隨機(jī)取[-（M-1），M-1]中的數(shù)；（5）找出每輛車(chē)需要配送的訂單號(hào)；（6）用蟻群算法得到車(chē)輛優(yōu)化路徑；（7）用評(píng)價(jià)函數(shù)評(píng)價(jià)所有粒子；（8）當(dāng)某一粒子的歷史最優(yōu)評(píng)價(jià)值劣于其現(xiàn)評(píng)價(jià)值時(shí)，記該粒子歷史最優(yōu)評(píng)價(jià)值為當(dāng)前評(píng)價(jià)值，記該粒子歷史最優(yōu)位置Pr為當(dāng)前位置，并優(yōu)化出車(chē)輛路徑；（9）尋找總?cè)后w內(nèi)最優(yōu)解，當(dāng)優(yōu)于歷史為最優(yōu)解時(shí)，則更新Pg及每輛車(chē)的出行路徑。當(dāng)有多個(gè)都為最優(yōu)值時(shí)，則隨機(jī)取其中一個(gè)為最優(yōu)解。

3 總結(jié)

在城市公交應(yīng)急疏散公交車(chē)輛路徑優(yōu)化模型中將疏散始、終地點(diǎn)的關(guān)系,疏散的人與公交車(chē)之間的關(guān)系模型化。對(duì)所有車(chē)輛及所有始、終點(diǎn)進(jìn)行路徑搜索,這樣能夠全面而科學(xué)地求解，并將粒子群算法和螞蟻群算法運(yùn)用到城市公交應(yīng)急疏散公交車(chē)輛路徑優(yōu)化中，易于實(shí)現(xiàn)全局最優(yōu)的目的。但是由于現(xiàn)實(shí)因素與自身?xiàng)l件的關(guān)系，本文所提出的方法還處于理論階段，未在現(xiàn)實(shí)中應(yīng)用，這既是本文模型的一個(gè)缺陷，也是進(jìn)一步研究的方向。

[1]Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents[J].Systems,Man and Cybernetics: Part B,1996,26(1):29-41.

[2]張麗艷,龐小紅,夏蔚軍,吳智銘,梁碩.帶時(shí)間窗車(chē)輛路徑問(wèn)題的混合粒子群算法[J],上海交通大學(xué)學(xué)報(bào),2006(11):130-134.

U491

A

1003-5168(2014)03-0155-01