基于層次蝙蝠算法的應(yīng)急車輛調(diào)度與交通疏散協(xié)同決策

段曉紅，吳家新，周芷晴

(北方工業(yè)大學(xué)a.經(jīng)濟(jì)管理學(xué)院；b.企業(yè)管理智能決策研究中心；c.電氣與控制工程學(xué)院，北京100144)

0 引言

早期應(yīng)急車輛調(diào)度的研究假設(shè)救援路徑靜態(tài)已知，以時間最短、成本最低等為目標(biāo)，從非路徑的角度研究調(diào)度問題[1].事故和救援環(huán)境的動態(tài)變化決定了應(yīng)急車輛調(diào)度是一個復(fù)雜動態(tài)過程.學(xué)者將動態(tài)問題沿著時間軸劃分為多個靜態(tài)問題，在各靜態(tài)問題中實(shí)時獲取參數(shù)并更新調(diào)度方案.劉亞杰等[2]基于模型預(yù)測控制方法建立多周期滾動優(yōu)化調(diào)度模型，在各周期內(nèi)根據(jù)實(shí)時信息對調(diào)度策略進(jìn)行調(diào)整.一些學(xué)者通過構(gòu)建時間依賴函數(shù)描述決策參數(shù)的動態(tài)變化過程.Ozdamar等[3]將時變資源供給和需求作為關(guān)鍵因素，以總救援延遲時間最短為目標(biāo)，分階段求解物資配送策略.Duan等[4]以預(yù)測行程車速函數(shù)為路段權(quán)值，構(gòu)建應(yīng)急車輛動態(tài)調(diào)度與路徑選擇模型.為求解多目標(biāo)多變量的調(diào)度模型，蟻群算法[5]、粒子群算法[6]等智能優(yōu)化算法得到廣泛應(yīng)用.

分析文獻(xiàn)發(fā)現(xiàn)，國內(nèi)外學(xué)者考慮路網(wǎng)的動態(tài)特性，基于實(shí)時或時變的路況信息規(guī)劃路徑并求解調(diào)度策略，引導(dǎo)應(yīng)急車輛避開擁堵路段.然而，一旦發(fā)生交通事故，路網(wǎng)整體通行能力將大幅下降，應(yīng)急救援時效仍難以保證，此時合理的交通疏散是快速調(diào)度應(yīng)急車輛的有力保障.現(xiàn)有應(yīng)急交通疏散相關(guān)研究集中在應(yīng)急區(qū)域疏散問題，是在一定的時限內(nèi)，將人員從危險區(qū)域轉(zhuǎn)移到安全地點(diǎn)的過程.通?；诰W(wǎng)絡(luò)流或交通分配模型，配合交通控制措施實(shí)現(xiàn)疏散效果的優(yōu)化[7]，鮮有研究應(yīng)急車輛調(diào)度中的交通疏散問題.基于此，本文在應(yīng)急車輛調(diào)度中加入交通疏散因素，針對調(diào)度與疏散問題間的層級制約關(guān)系，采用雙層規(guī)劃方法構(gòu)建模型，并設(shè)計一種雙層蝙蝠算法實(shí)現(xiàn)模型的求解.

1 問題描述與建模

1.1 路網(wǎng)模型構(gòu)建

將路網(wǎng)抽象為一個時變有向網(wǎng)絡(luò)模型[N,E,T(t)?Q,T(l)(t)?Q,T(d)(t)?Q].I個節(jié)點(diǎn)構(gòu)成集合N={n1,n2,…,nI}，若第i個節(jié)點(diǎn)ni與第j個節(jié)點(diǎn)nj相連，ni,nj∈N且i≠j，它們之間的連接線構(gòu)成路段ei,j=(ni,nj)∈E，E為路段集合，路段長度為Li,j，路段交通容量為Q是感興趣的時間區(qū)間，以Δ為間隔將其劃分為Φ+1個離散時間段，則Q={[t0,t0+Δ),[t0+Δ,t0+2?Δ),…,[t0+t?Δ,t0+(t+1) ?Δ) ,…,[t0+Φ?Δ,Qend] }，其中，t0為初始決策時刻，Qend為時間區(qū)間Q的右端點(diǎn)，將t0+t?Δ時刻記為t時刻.T(t)、T(l)(t)和T(d)(t)分別為定義在時間區(qū)間Q上的行程時間矩陣、交通負(fù)荷矩陣和交通需求矩陣.分別表示路段在t(t=0,1,…,Φ)時刻的行程時間、交通負(fù)荷和交通需求.H輛應(yīng)急車輛構(gòu)成集合S，第h輛應(yīng)急車輛sh所在節(jié)點(diǎn)為，sh∈S.t0時刻發(fā)生的D起事故構(gòu)成集合F，第d起事故fd所在節(jié)點(diǎn)為，fd∈F，應(yīng)急車輛需求為rd，救援時間窗為，事故嚴(yán)重程度為，應(yīng)急車輛sh到事故fd的最短行程時間為

1.2 應(yīng)急車輛調(diào)度與交通疏散模型構(gòu)建

應(yīng)急車輛調(diào)度和交通疏散是相互作用的決策過程，表述為一個雙層規(guī)劃問題.上層決策以總救援時間最短為目標(biāo)選擇最優(yōu)出救車輛；下層決策通過控制車輛行駛路徑上的路段流入率，在交通需求和交通容量約束下求取最優(yōu)路徑.

1.2.1 上層應(yīng)急車輛調(diào)度模型構(gòu)建

式(1)為目標(biāo)函數(shù)，使帶事故嚴(yán)重程度加權(quán)的應(yīng)急救援時間最短.式(2)保證派往事故fd的應(yīng)急車輛數(shù)滿足其需求rd.式(3)保證應(yīng)急車輛最晚到達(dá)事故fd的時間不超過其救援時效上限.式(4)保證應(yīng)急車輛sh只能被派往事故fd或?yàn)榭臻e車輛.式(5)保證應(yīng)急車輛總數(shù)為H.式(6)和式(7)為決策變量yh,d和的狀態(tài)約束.

1.2.2 下層交通疏散模型構(gòu)建

下層模型包含兩個階段：①以長度為路段權(quán)值，構(gòu)建K最短路徑模型，規(guī)劃出節(jié)點(diǎn)到節(jié)點(diǎn)的前K條長度最短的路徑，將它們作為備選救援路徑；②以行程時間最短為目標(biāo)，對K條備選路徑進(jìn)行交通疏散，并從中選取行程時間最短的一條作為最終救援路徑.K最短路徑(KSP)模型為

2 基于蝙蝠算法的模型求解

2.1 蝙蝠算法基本原理

蝙蝠算法(Bat Algorithm,BA)是Yang在2010年提出的一種元啟發(fā)式算法[8]，它模仿蝙蝠回聲定位捕食行為，具有結(jié)構(gòu)簡單、收斂速度快、自動切換全局和局部尋優(yōu)等優(yōu)勢.由A只蝙蝠組成種群M，第a只蝙蝠ma的位置xa表示問題的一種可行解，它對應(yīng)與問題優(yōu)化目標(biāo)相關(guān)的適應(yīng)度函數(shù)值Pf(xa)，a=1,2,…,A.在適應(yīng)度函數(shù)Pf的引導(dǎo)下，任一蝙蝠個體ma不斷更新飛行速度和位置xa以實(shí)現(xiàn)種群的全局尋優(yōu).隨著種群逐漸接近獵物，為當(dāng)前最優(yōu)位置添加一個逐漸減小的擾動，由此實(shí)現(xiàn)個體的局部尋優(yōu).

(1)全局尋優(yōu)時，φ時刻個體ma的飛行速度和位置xa更新策略為

(2)局部尋優(yōu)時，從當(dāng)前種群中選擇一個最優(yōu)位置xold，采用隨機(jī)游走方案產(chǎn)生新的局部解xnew，即

式中：ε是一個隨機(jī)數(shù)，ε∈[-1,1]；是所有蝙蝠在同一時間段的平均聲波響度.

蝙蝠ma的聲波響度和脈沖發(fā)射速率更新公式為

式中：α為音量衰減系數(shù)；γ為脈沖發(fā)射速率增加系數(shù)；分別為蝙蝠ma的初始聲波響度和脈沖發(fā)射速率.

(3)基本蝙蝠算法的實(shí)現(xiàn)步驟.

Step 1參數(shù)初始化.

Step 2對于蝙蝠ma,a=1,2,…,A執(zhí)行如下操作

Step 2.1根據(jù)式(24)～式(26)更新速度和位置xa.

Step 2.2產(chǎn)生隨機(jī)數(shù)，在種群中選擇一個最優(yōu)個體，并根據(jù)式(27)在附近產(chǎn)生一個新的局部解

Step 2.3產(chǎn)生隨機(jī)數(shù)，則接受，并根據(jù)式(28)和式(29)調(diào)整響度和發(fā)射速率

Step 3根據(jù)適應(yīng)度從大到小的順序?qū)ΨN群排序，查找并替換最佳蝙蝠位置x*.

Step 4重復(fù)步驟Step 2～Step 3直至最大迭代次數(shù)Z，輸出全局最優(yōu)解x*.

2.2 求解雙層規(guī)劃模型的蝙蝠算法

設(shè)計一種具有雙層架構(gòu)的蝙蝠算法，上層算法(BA_EVD)求解EVD模型，下層算法集成了兩個蝙蝠算法BA_KSP和BA_TE，分別求解KSP模型和TE模型.

(2)下層算法計算最優(yōu)控制策略ue,k,h,d(t)，uw,i,e,k,h,d(t)和最短行程時間

②BA_TE算法計算路段ek,h,d和wi,e,k,h,d，wi,e,k,h,d∈Wi,e,k,h,d在t∈Q時刻的最佳流入率，獲得路徑在最佳控制措施下的行程時間，并傳遞給上層算法.

2.3 求解K條最短路徑的蝙蝠算法

為滿足路徑連通性約束，在基本蝙蝠算法步驟的基礎(chǔ)上，重新定義初始編碼方案、全局和局部尋優(yōu)策略.

(1)初始編碼方案.

采用整數(shù)編碼方案進(jìn)行路徑編碼，并通過隨機(jī)鄰接搜索策略確保路徑的連通性.定義節(jié)點(diǎn)ni的鄰接節(jié)點(diǎn)集合為Ai，當(dāng)前路徑集合為在節(jié)點(diǎn)集合N中的補(bǔ)集)中隨機(jī)選擇一個節(jié)點(diǎn)ni+1，將當(dāng)前路徑集合更新為一搜索至事故節(jié)點(diǎn)，形成蝙蝠的位置編碼.

(2)全局尋優(yōu)策略.

φ時刻蝙蝠ma的位置為路徑序列x(a)φ，從中隨機(jī)選擇兩個不同的節(jié)點(diǎn)位置，構(gòu)成φ+1時刻ma的速度

2.4 求解交通疏散模型的蝙蝠算法

2.5 求解應(yīng)急車輛調(diào)度模型的蝙蝠算法

應(yīng)急車輛調(diào)度模型的決策變量是0-1變量yh,d，將其轉(zhuǎn)換為整型變量yh，表示應(yīng)急車輛sh(h=1,2,…,H)的調(diào)度方案.sh(sh∈S)可派往事故fd(fd∈F)或?yàn)榭臻e車輛，則yh的可行解集為yh={0,1,2,…,D}.任一蝙蝠的位置編碼可表示為

適應(yīng)度函數(shù)與目標(biāo)函數(shù)式(1)，約束條件式(2)和式(3)相關(guān)，即

3 算例驗(yàn)證

采用圖1所示的路網(wǎng)驗(yàn)證模型和算法的有效性，時間區(qū)間Q=[9 : 30,10:30]，時間間隔Δ=60 s，路網(wǎng)內(nèi)分布有H=10輛應(yīng)急車輛，具體參數(shù)如表1所示.t=9:30時發(fā)生D=4起事故，具體參數(shù)如表2所示，事故救援時間上限為1 800 s.

圖1 路網(wǎng)圖Fig.1 Road network

表1 應(yīng)急車輛參數(shù)Table 1 Emergency vehicle parameters

表2 事故參數(shù)Table 2 Accident parameters

(1)計算最短路徑.

(2)計算疏散方案.

采用BA_TE算法計算任意一條最短路徑上各路段及其相連路段的流入率，算法參數(shù)設(shè)置如表6所示.以路徑n13→n24→n25→n26→n27為例，算法尋優(yōu)過程如圖3所示，運(yùn)行結(jié)果如表7和表8所示.

表 3 BA_KSP算法參數(shù)設(shè)置Table 3 Selection of parameters of BA_KSP algorithm

圖2 BA_KSP算法尋優(yōu)過程Fig.2 Evolutionary process of BA_KSP algorithm

表4 的前5條最短路徑Table 4 First five shortest paths from

表4 的前5條最短路徑Table 4 First five shortest paths from

images/BZ_167_554_468_1971_522.png1 2 3 4 5( n)2 →n8→n9→n10→n11→n12→n13→n14→n27→(n)s f 3( n)s 2→n8→n9→n10→n2→n3→n4→n13→n14→n27→(n)f 3( n)s 2→n8→n7→n1→n2→n3→n4→n13→n14→n27→(n)f 3( n)s 2→n8→n9→n10→n2→n3→n12→n13→n14→n27→(n)f 3 n(s)2 →n8→n7→n1→n2→n3→n12→n13→n14→n27→n(f)3 30.75 31.75 32.05 32.75 33.05

表 5 應(yīng)急車輛到事故的最短行程時間Table 5 Shortest travel time from emergency vehicles to accidents

表 6 BA_TE算法參數(shù)設(shè)置Table 6 Selection of parameters of BA_TE algorithm

(3)計算應(yīng)急車輛調(diào)度方案.

采用BA_EVD算法計算最優(yōu)調(diào)度方案，算法參數(shù)設(shè)置如表9所示.經(jīng)過圖4的尋優(yōu)過程，獲得結(jié)果為[1,0,3,2,4,3,4,2,0,3]，解碼后獲得調(diào)度方案如表10所示；與文獻(xiàn)[4]中的混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)進(jìn)行對比，結(jié)果如表11所示.

圖3 BA_TE算法尋優(yōu)過程Fig.3 Evolutionary processes of BA_TE algorithm

表 7 疏散后應(yīng)急車輛到事故的最短時間路徑Table 7 Shortest time paths from emergency vehicles to accidents after evacuation

表 8 疏散后應(yīng)急車輛到事故的最短行程時間Table 8 Shortest travel time from emergency vehicles to accidents after evacuation

表 9 BA_EVD算法參數(shù)設(shè)置Table 9 Selection of parameters of BA_EVD algorithm

(4)計算結(jié)果分析.

①交通疏散效果分析.

對比表5和表8可知，疏散前從應(yīng)急車輛所在節(jié)點(diǎn)到事故所在節(jié)點(diǎn)的40條路徑中，行程時間超過30 min的達(dá)到72.5%，而疏散后該比例下降為42.5%.疏散后行程時間較疏散前縮短139.00～2 070.61 s.表12分析了疏散前后滿足事故救援時效的應(yīng)急車輛數(shù)，顯然疏散后可用車輛數(shù)大幅度增加.

②應(yīng)急車輛調(diào)度結(jié)果分析.

BA_EVD算法獲得的最優(yōu)調(diào)度方案滿足事故的時間窗約束和資源需求約束.由表11可知，對于本文的最小化問題，BA_EVD算法獲得的最優(yōu)解的目標(biāo)函數(shù)值較混合蛙跳算法(SFLA)減小16.85%，運(yùn)行時間較SFLA算法縮短77.98%.

表10 最優(yōu)調(diào)度方案Table 10 Optimal scheduling scheme

表11 算法性能對比Table 11 Comparison of performances of two algorithms

表12 滿足事故救援時效的車輛數(shù)Table 12 Number of vehicles satisfied rescue timeliness of accidents

4 結(jié)論

首先以行程時間、交通負(fù)荷和長度等為路段權(quán)值，將路網(wǎng)抽象為一個時變有向網(wǎng)絡(luò)模型；然后，構(gòu)建雙層規(guī)劃模型描述應(yīng)急車輛調(diào)度和交通疏散間的協(xié)同制約關(guān)系；接著，設(shè)計一種雙層蝙蝠算法，通過上下層間的變量傳遞，實(shí)現(xiàn)雙層規(guī)劃模型的求解；最后，采用具有47個節(jié)點(diǎn)的路網(wǎng)驗(yàn)證模型和算法的有效性.結(jié)果表明：BA_KSP算法能夠獲得滿足路徑連通約束的前K條最短路徑；交通疏散前后應(yīng)急車輛節(jié)點(diǎn)到事故節(jié)點(diǎn)的最短行程時間得到明顯降低；BA_EVD算法能夠獲得滿足事故需求約束的優(yōu)化調(diào)度方案，且計算性能明顯優(yōu)于SFLA算法.