多蟻群雙信息素疏散路徑規(guī)劃算法

吳世旺

(上海平可行智能科技有限公司，上海 200235)

0 引 言

對于人員疏散的研究，國內(nèi)外從研究角度上可以劃分為基于網(wǎng)格的微觀疏散模型和基于路網(wǎng)的宏觀疏散模型。

基于網(wǎng)格的微觀疏散模型考慮了疏散細(xì)節(jié)，將路徑規(guī)劃策略加入到模擬模型中，以微觀引導(dǎo)手段來改善疏散效率。吳鵬飛等[1]針對地鐵應(yīng)急疏散場景，在基本ACO算法的基礎(chǔ)上對路徑選擇策略、啟發(fā)式函數(shù)和信息更新策略進(jìn)行改進(jìn)，提高正反饋?zhàn)饔煤褪諗克俣?，為整個(gè)疏散群體求解更優(yōu)的疏散路徑。郭陽勇等[2]結(jié)合元胞蟻群算法和卡爾曼濾波提出了一種新的疏散模型PECA,利用元胞蟻群算法和卡爾曼濾波對最短疏散時(shí)間的優(yōu)化模型進(jìn)行求解。YE等[3]將ACO算法和元胞自動機(jī)模型(CA)結(jié)合，上層采用ACO算法進(jìn)行路徑選擇，底層使用CA模型實(shí)現(xiàn)人員在離散空間上的移動和位置沖突的解決。

基于路網(wǎng)的宏觀疏散模型忽略人員疏散細(xì)節(jié)，將疏散環(huán)境抽象為動態(tài)網(wǎng)絡(luò)圖，通常使用啟發(fā)式算法進(jìn)行求解。YUAN等[4]針對復(fù)雜環(huán)境下的應(yīng)急疏散，以最小化疏散時(shí)間和擁擠度為目標(biāo)，改進(jìn)基本ACO算法進(jìn)行求解；LIU等[5]將疏散場景劃分為疏散區(qū)域、過渡區(qū)域和安全區(qū)域，提出改進(jìn)的量子蟻群疏散路徑規(guī)劃算法。董崇杰等[6]針對人車混合的大型公共場所，使用改進(jìn)的布谷鳥算法對目標(biāo)函數(shù)進(jìn)行求解。FANG等[7]為解決體育場的應(yīng)急疏散路徑優(yōu)化問題，將環(huán)境抽象為分層有向網(wǎng)絡(luò)，提出了HMERP-ACO算法。

如何均衡路段的通行量負(fù)載，為疏散個(gè)體合理配置路徑，提升疏散效率，是綜合交通樞紐常規(guī)疏散研究的重點(diǎn)。本文結(jié)合綜合交通樞紐常規(guī)疏散特點(diǎn)，基于疏散路網(wǎng)，以最小化網(wǎng)絡(luò)清空時(shí)間、人均疏散時(shí)間和累計(jì)擁堵系數(shù)為疏散目標(biāo)，提出多蟻群雙信息素算法(multi-ant colony double pheromone algorithm，MACDPA)來研究綜合樞紐內(nèi)的常規(guī)疏散路徑規(guī)劃問題。

1 綜合交通樞紐常規(guī)疏散問題描述

1.1 疏散路網(wǎng)

選取綜合樞紐內(nèi)的樓梯、自動扶梯、出入口和乘車點(diǎn)等作為關(guān)鍵節(jié)點(diǎn)，將疏散環(huán)境抽象為二維網(wǎng)絡(luò)圖：

G=(N,E,R)

(1)

式中：N為疏散節(jié)點(diǎn)；E為節(jié)點(diǎn)間的連線；R為路段通行屬性。

R=(L,W,SC,LC)

(2)

SC=L×W×ρS

(3)

LC=L×W×ρL

(4)

式中：L、W分別為路段長度、寬度；SC為安全容量，當(dāng)該路段上的人數(shù)小于SC時(shí)，行人可以按期望速度自由移動；LC為路段極限容量，當(dāng)該路段上的人數(shù)大于等于LC時(shí)，擁擠度達(dá)到極限，人群緩慢推進(jìn)或停止移動；ρS為個(gè)體不受影響可以按照意愿自由行走的人群密度常量；ρL為人群擁擠度達(dá)到極限只能緩慢推進(jìn)或者完全停止移動的人群密度常量。根據(jù)文獻(xiàn)[8]，令ρS=0.39 人/m2，ρL=3.8 人/m2。

1.2 疏散目標(biāo)函數(shù)及約束

綜合交通樞紐常規(guī)疏散路徑優(yōu)化的目標(biāo)函數(shù)描述如下：

minf1=max(T1,T2,…,Tk,…Tm)

(5)

(6)

(7)

式中：f1為最小化網(wǎng)絡(luò)清空時(shí)間；f2為最小化累計(jì)擁堵系數(shù)；f3為最小化人均疏散時(shí)間；m為疏散人員總數(shù)；Tk為人員的疏散時(shí)間；Cij(t)為t時(shí)刻路段(i,j)上的擁堵系數(shù)。

模型約束如下所示。

(8)

(9)

(10)

(11)

(12)

2 多蟻群雙信息素算法

本文結(jié)合具體研究對象及優(yōu)化目標(biāo)，提出MACDPA算法，將疏散人員當(dāng)作螞蟻，根據(jù)乘車意向劃分為多個(gè)種群，改進(jìn)ACO算法中啟發(fā)式信息和信息素函數(shù)，考慮人員在實(shí)際疏散過程中，偏向于選擇較短路徑，且有意避免路段過度擁擠，引入種群信息素和部落信息素的概念。利用種群信息素的正反饋?zhàn)饔脕硪龑?dǎo)同一種群的螞蟻進(jìn)行最短疏散路徑尋優(yōu)，利用部落信息素的負(fù)反饋?zhàn)饔脕肀苊饴范芜^度擁擠，實(shí)現(xiàn)路徑資源均衡分配的同時(shí)，提高疏散效率。

2.1 算法設(shè)計(jì)

1) 啟發(fā)式信息搜索策略

(13)

(14)

2) 信息素更新策略

引入種群信息素和部落信息素，借助于二者的綜合作用，避免算法收斂于局部最優(yōu)，均衡路段負(fù)載，改善疏散效率。

種群信息素：同一種群的螞蟻產(chǎn)生的信息素，該信息素作為種群內(nèi)部通信的媒介，正反饋機(jī)制引導(dǎo)同種群的螞蟻選擇較短的路徑。更新策略為：

τij(n+1)=(1-ρ1)τij(n)+ρ1Δτij(n)

(15)

(16)

(17)

部落信息素：所有螞蟻產(chǎn)生的信息素，該信息素作為所有螞蟻共享的通信媒介，負(fù)反饋機(jī)制避免過多螞蟻聚集在同一路段。更新策略為：

φij(n+1)=(1-ρ2)φij(n)+ρ2Δφij(n)

(18)

(19)

(20)

3) 狀態(tài)轉(zhuǎn)移概率

(21)

式中：α為信息素因子；β為啟發(fā)函數(shù)因子；NextLINK_set為螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到下個(gè)節(jié)點(diǎn)j的可選節(jié)點(diǎn)集。

2.2 算法實(shí)現(xiàn)步驟

MACDPA算法求解綜合交通樞紐內(nèi)的常規(guī)疏散問題的過程描述如下：

Step1：初始化模型參數(shù)

初始化模型參數(shù)，設(shè)置最大迭代次數(shù)NCmax，迭代計(jì)數(shù)器NC=1，初始化種群信息素τij(0)=c，部落信息素φij(0)=c。

Step2：選擇路徑

將螞蟻放在起始節(jié)點(diǎn)上，在節(jié)點(diǎn)i上的個(gè)體k根據(jù)Pij來選擇下一個(gè)節(jié)點(diǎn)j，重復(fù)這個(gè)過程，直到k到達(dá)目標(biāo)節(jié)點(diǎn)，當(dāng)所有疏散個(gè)體獲得相應(yīng)的疏散路徑后，完成一次迭代。

Step3：更新Pareto解集

完成步驟2中的一次迭代，每一個(gè)疏散個(gè)體建立了疏散路徑，所有的疏散路徑構(gòu)成一個(gè)可行解sn。計(jì)算目標(biāo)函數(shù)值，如果sn是非支配解，將sn加入到Pareto解集中，并移除被sn支配的解。

Step4：更新信息素

用φij(t+1)更新每條邊上的部落信息素。若本次迭代產(chǎn)生的解是pareto解，則使用新的τij(t+1)更新每條邊上的種群信息素，否則，不更新種群信息素。

Step5: 終止條件

令NC=NC+1，若NC

3 試驗(yàn)結(jié)果及分析

以某綜合交通樞紐為試驗(yàn)對象，路網(wǎng)圖如圖1所示，其中：節(jié)點(diǎn)1為火車出口；節(jié)點(diǎn)59為火車入口；節(jié)點(diǎn)4、5為輕軌乘車點(diǎn)；節(jié)點(diǎn)10為長途客運(yùn)乘車點(diǎn)；節(jié)點(diǎn)17為出租乘車點(diǎn)；節(jié)點(diǎn)18為公交乘車點(diǎn)。

相應(yīng)的參數(shù)設(shè)置如表1所示。初始時(shí)，將人群分布在起始節(jié)點(diǎn)1上，試驗(yàn)選擇三種算法進(jìn)行比較：ACO算法、HMERP-ACO算法和本文提出的MACDPA算法。

表1 算法參數(shù)設(shè)置

試驗(yàn)結(jié)果如圖2～圖5所示。圖2～圖5分別為三種算法的網(wǎng)絡(luò)清空時(shí)間、累計(jì)擁擠度、人均疏散時(shí)間和人均疏散長度?？梢钥闯觯啾绕渌麅煞N算法，MACDPA算法通過適當(dāng)?shù)厥共糠秩恕吧峤筮h(yuǎn)”，有效地均衡了路徑負(fù)載，提高了疏散效果。

表2為三種算法得到的Pareto解對應(yīng)的目標(biāo)函數(shù)值，圖6為三種算法得到的目標(biāo)函數(shù)值的分布。由表2可知，MACDPA得到的Pareto解無論在質(zhì)量還是數(shù)量上都優(yōu)于其他兩種算法。

表2 三種算法的Pareto解

圖7是三種算法對應(yīng)的疏散曲線。在前200 s，三種算法的疏散人數(shù)基本相同；在200 s～350 s，MACDPA算法相比其他兩種算法，疏散人數(shù)較少；350 s后，MACDPA算法的疏散人數(shù)明顯多于其他兩種算法。

試驗(yàn)結(jié)果表明，本文提出的MACDPA算法，相比其他兩種算法能夠提供更優(yōu)的疏散路徑規(guī)劃方案。

4 結(jié)束語

城市綜合交通樞紐作為一個(gè)為市民提供公共換乘服務(wù)的公共場所，在保證正常運(yùn)營的前提下，均衡利用交通樞紐內(nèi)的現(xiàn)有資源，盡量降低人員擁擠度，改善疏散人員體驗(yàn)度，提高路徑資源利用率及樞紐運(yùn)營效率，具有重要意義。本文針對相應(yīng)的疏散目標(biāo)，基于蟻群算法，改進(jìn)啟發(fā)式函數(shù)，引入種群信息素和部落信息素的概念，提出多蟻群雙信息素MACDPA算法，并將其與ACO和HMERP-ACO算法進(jìn)行對比。試驗(yàn)結(jié)果表明，本文提出的算法能夠?yàn)榫C合交通樞紐的常規(guī)疏散提供更優(yōu)的疏散路徑規(guī)劃方案。