基于改進蟻群算法的公交疏散策略研究

趙惠光，何勝學(xué)，黃 清，向樂佳

(1.上海理工大學(xué) 管理學(xué)院，上海 200093；2.周口師范學(xué)院 新聞與傳媒學(xué)院，河南 周口 466001；3.上海同技聯(lián)合建設(shè)發(fā)展有限公司，上海 200092)

基于改進蟻群算法的公交疏散策略研究

趙惠光1，何勝學(xué)1，黃 清2，向樂佳3

(1.上海理工大學(xué) 管理學(xué)院，上海 200093；2.周口師范學(xué)院 新聞與傳媒學(xué)院，河南 周口 466001；3.上海同技聯(lián)合建設(shè)發(fā)展有限公司，上海 200092)

針對無預(yù)警災(zāi)難發(fā)生后的大規(guī)模人群疏散問題，提出了應(yīng)急救援的公交疏散策略，通過對動態(tài)的疏散路網(wǎng)和疏散者的時間加載離散化處理，采用時空網(wǎng)絡(luò)和數(shù)值分析的方法以疏散總時間最短，傷亡人數(shù)最少建立公交疏散的非線性混合整數(shù)規(guī)劃模型，并將整個公交疏散過程與改進的蟻群算法相結(jié)合，通過信息素全局更新對疏散模型進行求解，最后以一個簡單的公交疏散網(wǎng)絡(luò)作為算例來求解最優(yōu)疏散路徑。結(jié)果表明，通過多次計算不僅驗證了改進蟻群算法的有效性，同時求解疏散路徑的速度和質(zhì)量也得到提高。

非線性混合整數(shù)規(guī)劃；公交疏散；蟻群算法；應(yīng)急救援

無征兆自然災(zāi)害、突發(fā)社會生產(chǎn)事故以及恐怖主義襲擊往往會造成嚴重的人員傷亡，財產(chǎn)損失，如印度洋海嘯和8·12天津濱海新區(qū)爆炸事故等，對于社會安全和應(yīng)急疏散體系構(gòu)成較大的威脅，使得各國開始重視緊急疏散策略的研究[1]。目前我國的災(zāi)后疏散一般由應(yīng)急疏散部門調(diào)集大運量的公交在短時間內(nèi)疏散事故區(qū)域內(nèi)人群至安全避難區(qū)域，是一種較為可行的災(zāi)后疏散交通組織形式。

緊急公交疏散路徑的優(yōu)化問題屬于組合優(yōu)化問題，是NP-hard問題，其中Bish[2]以最小化最大行車成本為目標，構(gòu)建了基于弧段的混合整數(shù)規(guī)劃模型。Yamada[3]運用最小成本流問題進行疏散交通分配，提出了最短路撤退規(guī)劃方法。Tuydes 和Ziliaskopoulos[4]提出了一個基于混合線性整數(shù)規(guī)劃的分階段疏散模型。何勝學(xué)[5]提出了將時間滾動式的流量加載模式與經(jīng)典遺傳算法相結(jié)合來確定公交疏散中車輛的最佳路徑問題。

本文將從以時空網(wǎng)絡(luò)的形式引入路網(wǎng)的交通動態(tài)特征，同時考慮疏散者的時間流量加載性，對應(yīng)急救援公交疏散策略進行檢驗。

1 基本描述

1.1 路網(wǎng)轉(zhuǎn)化

時空網(wǎng)絡(luò)是離散時間下的動態(tài)網(wǎng)絡(luò)流建模方法[6]，它通過將節(jié)點和弧構(gòu)成的靜態(tài)的網(wǎng)絡(luò)按一定的時間間隔在離散時間框架下進行相應(yīng)的節(jié)點“復(fù)制”和弧段更新，從而形成“新”的網(wǎng)絡(luò)，然后按照靜態(tài)網(wǎng)絡(luò)流問題的建模方法在“新”網(wǎng)絡(luò)上進行建模，對“動態(tài)”路徑規(guī)劃問題的分析[7]。為體現(xiàn)動態(tài)的交通網(wǎng)絡(luò)特征，假設(shè)弧段上的運行時間在疏散過程中保持不變，這里將現(xiàn)實中的交通路網(wǎng)轉(zhuǎn)變成時空網(wǎng)絡(luò)來研究，如圖1所示。

圖1 靜態(tài)的時空網(wǎng)絡(luò)

(1)圖中所示的時空網(wǎng)絡(luò)。G=(A,H),A=AD∪AC∪AS∪AE，其中，A是時空網(wǎng)絡(luò)中所有節(jié)點的集合;AD為車站節(jié)點集合;AC為所有上車點集合(包括公交站點和車站節(jié)點);AS為避難點集合;AE為一個虛擬終點節(jié)點(代表所有公交車和待疏散者最終的目的地)；

(2)H表示時空網(wǎng)絡(luò)中所有弧段的集合：H=HW∪HC∪HE∪HS，圖1中HW為等待弧子集，即相鄰兩個時段，同一上車點時空網(wǎng)絡(luò)節(jié)點之間的連接弧，其時間間隔Δt,用短虛線來表示； 為移動弧子集，弧上的最大通行能力為弧上總的公交車輛容量，相應(yīng)的運行時間為Δt=tj-ti，用實線來表示；HE為終點連接弧子集，是避難點節(jié)點與終點節(jié)點之間的連接弧，代表成功疏散弧段，將其行程時間設(shè)置為ti,AE=0，最大通行能力為無限大。HS是上車點節(jié)點與終點節(jié)點之間的連接弧，最大通行能力也為無限大，為最大程度的減少傷亡人數(shù)，給其疏散時間一個給定的很大的懲罰因子Z，ti,AE=Z，以此來代表傷亡人數(shù)用長虛線表示。

1.2 基本參變量

考慮無預(yù)警緊急疏散的時間緊迫性，一般假設(shè)每一輛公交車輛在有效救援時間內(nèi)只進行一次從車站到避難點的疏散[8]。

路段：對任一路段(i,j)，這里i和j分別是弧段頭尾節(jié)點，定義tij，xij，yij分別表示該路段上的行程時間，待疏散者流量和參與救援的公交車數(shù)量。

節(jié)點：節(jié)點AD、AC和AS具有位置pi和時間ti兩個屬性[9]，位置屬性根據(jù)原疏散網(wǎng)絡(luò)中的相應(yīng)位置而生成，一共包含T+1層，每一層代表一個時間段，時間段ti∈{0,1,2,…,T}；時間間隔Δt的選取需要滿足所有弧段的運行時間是選取的最短時間間隔時長的整數(shù)倍，即t有效=TΔt；AE時間屬性定義為tAE=T+1。

對于xij，yij分別定義二值指示變量μij,ηij來表征弧段上疏散者的流量狀態(tài)[10]，μij,ηij∈{0,1};μij和ηij的具體值可參考式(1)和式(2)。

(1)

(2)

V表示所有可獲得的用于疏散的公交車所構(gòu)成的集合，因此有|V|=V。Vi和Vij分別表示穿過點i和弧段(i,j)的公交車輛所構(gòu)成的集合，于是有yij=|Vij|。

2 應(yīng)急公交疏散策略

2.1 基本約束條件

這里考慮公交車輛的不同載客量、有容量限制的避難點、疏散者和救援公交車輛的流量守恒等因素，將相關(guān)約束條件詳細介紹如下。

在路段節(jié)點處待疏散者流量守恒[11]，相關(guān)約束如下

(3)

在路段節(jié)點處公交車輛流量守恒，相關(guān)約束如下

(4)

(5)

(6)

對公交車輛載客量進行約束，即弧段上的疏散者人數(shù)不能超過弧段上公交車的總裝載容量，相關(guān)約束如下

(7)

對避難點的容納容量進行約束，即到達所有避難點的待疏散者總?cè)藬?shù)不能超過該避難點的最大容納能力，相關(guān)約束如下

xASAE≤CS

(8)

(9)

對任意等待弧(i,j)，如果與該弧相關(guān)聯(lián)的上車點上有待疏散者等待卻沒有公交車，那么離開該上車點的公交車一定沒有剩余容量，相應(yīng)約束如下

(10)

除等待弧之外的其他弧上待疏散者人數(shù)與當(dāng)前公交車的加載量之間的關(guān)系可用下式來表示

(11)

待疏散者登上公交車后不允許中途變更車輛，相關(guān)約束如下

Qv(t)≤Qv(t+1),?v∈Vt∈{1,2,3,…,T}

(12)

待疏散者流量和公交車流量為非負整數(shù)，相關(guān)約束如下

xij,yij∈Z+∪{0},(i,j)∈H

(13)

以上式(1)～式(13)即為建立無預(yù)警式公交疏散路徑模型的相關(guān)約束條件。

2.2 考慮加權(quán)的公交疏散路徑規(guī)劃模型

目標函數(shù)分為5 部分，利用參數(shù)ηij將等待弧進行區(qū)分計算，則待疏散者在公交車外的等待時間

TWO=∑(i,j)∈HW(1-ηij)xijtij

(14)

待疏散者在公交車內(nèi)的等待時間

TWI=∑(i,j)∈HWηijxijtij

(15)

待疏散者在公交車上的運行時間

TR=∑(i,j)∈HCxijtij

(16)

未成功疏散的待疏散者的懲罰時間

TZ=∑(i,j)∈HSxijtij

(17)

公交車的總運行時間

TV=∑(i,j)∈Hyijtij

(18)

同樣給每一部分分別設(shè)定一個非負權(quán)重，分別為αWO、αWI、αR、αZ和αV，那么目標函數(shù)為

F(x,y)=αWOTWO+αWITWI+αRTR+αZTZ+αVTV

(19)

最后由約束條件式(1)～式(18)構(gòu)成的約束集H(x,y)和目標函數(shù)式(19)，建立應(yīng)急公交疏散策略規(guī)劃模型為

(20)

3 算法設(shè)計

針對應(yīng)急公交疏散路徑規(guī)劃問題，本文將改進的蟻群算法[12]融合到應(yīng)急公交疏散策略中去，求解步驟如下：

步驟1 初始化參數(shù)。假設(shè)有效的疏散時間t有效和時間間隔Δt，則ti∈T={0,1,2,…,t有效/Δt}；未成功疏散者的疏散懲罰時間Z；最大迭代次數(shù)為ε；弧段上的初始信息素強度為τij；各弧段的長度以及用于疏散的公交車集合V；改進蟻群算法的信息素更新[13]的改進公式為

(21)

轉(zhuǎn)移概率[14]為

(22)

(23)

ZK=第K只螞蟻完成一次尋優(yōu)任務(wù)后，其所走過的路徑長度；Q為一個常數(shù)。設(shè)迭代次數(shù)K=1；

步驟2 路網(wǎng)轉(zhuǎn)化。將給定的原始的公交疏散路網(wǎng)轉(zhuǎn)化成相應(yīng)的時空網(wǎng)絡(luò)G=(A,H)；

步驟3 公交疏散路徑的優(yōu)化步驟。對所有螞蟻即所提供的公交車集合V中的所有公交車進行如下操作：

(1)當(dāng)t(K)=0時，將所有螞蟻放置在時空路網(wǎng)中節(jié)點(1, 0)的初始車站節(jié)點，此時每只螞蟻的剩余裝載容量Remain為最大載客量；

令t(K)=t(K)+1,i=j;

(3)若螞蟻的時間屬性t(K)≥T或螞蟻的位置屬性p(K)=AS時，則將螞蟻強制移動到最終的終點AE處，則螞蟻找到一條弧段。待所有螞蟻全部到達終點后，轉(zhuǎn)到步驟4；否則，轉(zhuǎn)到步驟(2)；

步驟4 信息素全局更新[16]。待所有螞蟻全部到達終點后，計算每只螞蟻生成的弧段長度Zk，并計算出總疏散時間，保存目前為止所找到的最優(yōu)弧段。根據(jù)公式更新信息素的軌跡強度τij； 令k=k+1，并重置Δτij=0，轉(zhuǎn)到步驟5；

步驟5 迭代終止。如果當(dāng)前迭代次數(shù)τ=ε，計算終止；否則，轉(zhuǎn)到步驟3；

步驟6 輸出所有螞蟻最優(yōu)疏散弧段及疏散總時間。

4 算例分析

針對應(yīng)急公交疏散的實際情況，以一個簡單的公交疏散網(wǎng)絡(luò)來計算最優(yōu)疏散路徑，并驗證改進蟻群算法的有效性。

圖2是一個公交疏散路網(wǎng)圖，節(jié)點1 代表車站節(jié)點；節(jié)點2、3 和4 代表上車點節(jié)點；節(jié)點5 代表避難所節(jié)點。

圖2 公交疏散網(wǎng)絡(luò)圖

需要利用公交車進行疏散的待疏散者到達公交站站點的到達情況如表1所示。

表1 疏散者到達公交站點的情況

假設(shè)有效的疏散時間t有效=4，時間間隔Δt=1，那么相應(yīng)的時間段為ti∈T={0,1,2,3,4}，時空網(wǎng)絡(luò)分為5層，終點節(jié)點對應(yīng)的時間段為5，規(guī)定待疏散者和公交車最終全部到達終點節(jié)點。

設(shè)定未成功疏散懲罰時間為Z=1，蟻群算法中最大迭代次數(shù)為ε=10，各個路段上的初始信息素強度為τij=0，初始信息素強度增量為Δτij=0，給出常數(shù)Q的值、信息素強度的相對重要性α=1及能見度的相對重要性β=1，信息素揮發(fā)因子ρ=0.5，各路段的長度均為1， 3輛公交車V1、V2和V3從車站1出發(fā)，最大載客量為90，設(shè)定非負權(quán)重αWO=1、αWI=1、αR=1、αZ=1和αV=1。

經(jīng)過計算分析，相關(guān)結(jié)果如下，相應(yīng)疏散路線及流量如表2～表4 所示。

表2 公交疏散時間及相關(guān)路段的流量

表3 公交疏散時間及相關(guān)路段的流量

表4 公交疏散時間及相關(guān)路段的流量

當(dāng)常數(shù)Q取3時，算例能夠得到一個比較滿意的結(jié)果，不僅提高模型的求解速度，解得質(zhì)量也得到提高。

5 結(jié)束語

針對應(yīng)急救援中的公交疏散策略進行了研究，通過模擬實際的應(yīng)急疏散過程，利用改進的蟻群算法求解公交疏散模型，給出了模型的一個有效求解算法，可以看出改進的蟻群算法提高了求解模型的速度，為應(yīng)急公交疏散提供了一個具體可行的優(yōu)化方案。

[1] 劉小明,胡紅.應(yīng)急交通疏散研究現(xiàn)狀與展望[J].交通運輸工程學(xué)報,2008(3):108-115,121.

[2] Yamada T.A network of approach to a city emergency evacuation planning[J].International Journal of Systems Science,1996,27(10):931-936.

[3] Tuydes H,Ziliaskopoulos A.The network evacuation problem and solution algorithms[C]. San Francisco:Informs Annual Meeting,2005.

[4] Bish D.Planning for a Bus-based Evacuation[J]. ORSpectrum,2011,33(3):629-654.

[5] 何勝學(xué).無預(yù)警緊急疏散中公交車輛路徑的確定方法[J].運籌學(xué)學(xué)報,2014(3):47-59.

[6] 崔建勛,安實,崔娜.基于時間擴展網(wǎng)絡(luò)的區(qū)域疏散公交路徑規(guī)劃[J].華南理工大學(xué)學(xué)報:自然科學(xué)版,2010(3):64-69.

[7] 龐明寶,東方,任沙沙.基于時間依賴網(wǎng)絡(luò)的城市交通緊急疏散線路研究[J].公路交通科技,2011(1):100-106.

[8] 劉云忠,宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學(xué)報,2005(1):124-130.

[9] 徐梁,宋瑞.自然災(zāi)害下的公交疏散路線模型[J]. 物流技術(shù),2011(11):147-150,154.

[10] 黃隆飛,宋瑞,鄭鋰.大容量客車疏散路徑模型選擇[J].交通信息與安全,2009(5):85-89.

[11] 宋瑞,何世偉,章力.緊急疏散情況下的公交車運行計劃優(yōu)化研究[J].交通運輸系統(tǒng)工程與信息,2009(6):154-160.

[12] 倪慶劍,邢漢承,張志政,等.蟻群算法及其應(yīng)用研究進展[J].計算機應(yīng)用與軟件,2008(8):12-16.

[13] 陳迎欣.基于改進蟻群算法的車輛路徑優(yōu)化問題研究[J].計算機應(yīng)用研究,2012,29(6):151-156.

[14] 段海濱,王道波,朱家強,等.蟻群算法理論及應(yīng)用研究的進展[J].控制與決策,2004(12):1321-1326,1340.

[15] 高尚,楊靜宇.非線性整數(shù)規(guī)劃的蟻群算法[J]. 南京理工大學(xué)學(xué)報:自然科學(xué)版,2005(S1):126-129.

[16] 蘇紅畏,劉希玉,王曉敏.混合最大最小蟻群算法在VRPTW中的應(yīng)用[J].計算機技術(shù)與發(fā)展,2010(2):90-94.

Study on the Strategy of Bus Evacuation Based on Improved ant Colony Optimization

ZHAO Huiguang1，HE Shengxue1，HUANG Qing2，XIANG Lejia3

(1.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;2. College of Journalism and Communications,Zhoukou Normal University,Zhoukou 466001,China;3. Shanghai Tongji United Construction Development Co.,Ltd , Shanghai 200092,China)

Aim at the evacuation problems of large-scale crowd after the disaster without warning, presents the strategy of bus evacuation during the emergency rescue, puts forward the dynamic evacuation network and time load processing discretization, adopt the methods of numerical analysis and time-space network to shortest the total evacuation time ,minimum the casualties, then establish the mixed integer nonlinear programming model of bus evacuation, combined the evacuation process with improved ant colony optimization, proposed global pheromone updating to resolving the evacuation model, finally,to achieve the optimal evacuation path in an ordinary bus evacuation network.the results verified the validity of the algorithm by many times calculation ,and improved the speed and quality of solving the evacuation path.

bus evacuation;mixed integer nonlinear programming;ant colony optimization;emergency rescue

2016- 05- 26

國家自然科學(xué)基金資助項目(70672110);上海市(第三期)重點學(xué)科基金資助項目(S30504);上海市教委科技創(chuàng)新基金資助項目(10YS105);上海理工大學(xué)博士啟動基金資助項目(1D-00-307005)

趙惠光(1991-),男,碩士研究生。研究方向:系統(tǒng)工程等。 何勝學(xué)(1976-)，男，博士，副教授，碩士生導(dǎo)師。研究方向：系統(tǒng)工程等。

10.16180/j.cnki.issn1007-7820.2017.04.017

U491，TP301

A

1007-7820(2017)04-068-05