應(yīng)急車輛動態(tài)路徑選擇的兩階段優(yōu)化模型

楊楓，種大雙

(河南中醫(yī)藥大學，a.管理學院；b.信息技術(shù)學院，鄭州 450046)

0 引言

隨著城市化進程的加快，城市突發(fā)事件發(fā)生的概率越來越大，給經(jīng)濟生活帶來了很多不利影響。因城市內(nèi)道路交通狀況是實時變化的，故在突發(fā)事件發(fā)生后，必須要考慮應(yīng)急車輛在路上的行程時間，動態(tài)進行路徑選擇，確保以最短時間對被困人員進行施救。

目前，國內(nèi)外學者對突發(fā)事件發(fā)生時復(fù)雜路網(wǎng)狀況下應(yīng)急車輛救援速度優(yōu)化問題展開了大量研究。文獻[1]基于水波學原理，建立交通影響等級閾值模型，實現(xiàn)交通影響等級劃分，有效提高了應(yīng)急救援的響應(yīng)速度。文獻[2]提出基于路段行程時間相似性的典型車輛分析方法，比較接近真實的路網(wǎng)狀態(tài)。文獻[3]研究多源交通信息下的動態(tài)路徑選擇模型和算法，提出一種動態(tài)網(wǎng)絡(luò)的先進先出(FIFO)一致性約束準則，實現(xiàn)多源信息下的車輛調(diào)度優(yōu)化。文獻[4]引入時間相關(guān)的最短路徑和車輛路徑問題，優(yōu)化目標為車輛總移動時間最小，為城市道路擁堵問題提出一種解決方案。應(yīng)急車輛救援速度優(yōu)化的核心問題是尋找一種最優(yōu)的動態(tài)最短路徑算法，目前此類問題的研究相對較少。文獻[5]提出面向城市交通網(wǎng)絡(luò)的具有多項式時間復(fù)雜度的K 最短路徑(KSP)集合搜索算法，該算法明顯優(yōu)于傳統(tǒng)方法。此外，由于車輛路徑的行程時間具有顯著的不確定性，有少數(shù)學者在選擇車輛行駛路徑時考慮了路徑通行可靠性因素。文獻[6]以行程時間的可靠性作為路徑選擇權(quán)重，采用Dijkstra 算法求解，可以更準確地反映實際車輛路徑選擇。

綜上，對于應(yīng)急車輛動態(tài)路徑選擇問題，學者多從車輛整體救援速度或者動態(tài)最短路徑等角度進行研究，對突發(fā)事件下路網(wǎng)狀況的復(fù)雜性考慮不足。本文充分考慮突發(fā)事件帶給路網(wǎng)狀況的實時變化，以車輛最短行程時間和車輛行駛路徑最大可靠性為兩階段優(yōu)化目標，建立應(yīng)急車輛動態(tài)路徑選擇的兩階段模型。

1 動態(tài)路徑選擇模型構(gòu)建

1.1 問題描述

在復(fù)雜的城市路網(wǎng)中，應(yīng)急車輛需要經(jīng)過多條道路才能到達待救點，如果用路徑行程時間表示行駛完該路段所需的時間，那么總行程時間由各個路徑行程時間組成。因此，路徑選擇的目標是從眾多路徑中選取最優(yōu)路徑，使得總行程時間最短。以路徑行程時間為權(quán)值，將路網(wǎng)抽象為由節(jié)點和邊所組成的圖G(R,E)，其中，R為節(jié)點集合，E為邊的集合，i,j為正整數(shù)。在任意一個路段中，車的速度是動態(tài)變化的，因此行程車速的預(yù)測值必須融合時變信息。在調(diào)度決策時刻t0之后，如果用行程車速的預(yù)測值對車速函數(shù)進行擬合，擬合后的結(jié)果必然與實際車速函數(shù)之間存在偏差，從而導(dǎo)致路段行程時間函數(shù)與實際函數(shù)之間存在偏差，所求得的最短時間路徑不一定是最優(yōu)路徑，因此需要構(gòu)建動態(tài)路徑選擇模型。

1.2 路段行程時間分析

對于時間段U，假如以Δt為最小時間間隔，將U分割為H個離散時間區(qū)間，則U=其中γ=0,1,…,H-1，t0為初始時刻，為最后一個時刻，應(yīng)急車輛能夠在內(nèi)到達事故節(jié)點。事實上，t0時刻的車輛實時路段行程車速可以獲得，而時間段U內(nèi)的其他實時路段行程車速只能與歷史車速數(shù)據(jù)相融合，并進行預(yù)測。假設(shè)從歷史車速數(shù)據(jù)中取得樣本集，選取t0時刻前后幾個連續(xù)采集周期內(nèi)的行程車速作為樣本向量，該樣本集的各子類樣本聚集于中心其中，vc(t)表示樣本xc中t時刻的路段行程車速，d為樣本的維數(shù)，φ1、φ2為任意兩個正整數(shù)。初始時刻t0之后的第φ2個時刻的行程車速可預(yù)測為

式中：K為最近鄰樣本集所包含的樣本總數(shù)，k=1,2,…,K。

圖1 行程車速函數(shù)Fig.1 Travel speed function

車速函數(shù)為

式中：C1，Ci為積分常數(shù)，i=2,3,…,H-1，通過原函數(shù)的連續(xù)性求得。

令式(3)等于路徑長度Lij，則應(yīng)急車輛駛出路段的時間x為

式中：ρ為μ的反函數(shù)?？傻寐范涡谐虝r間函數(shù)為

1.3 路徑可靠程度分析

在城市突發(fā)事件中，城市路網(wǎng)尤其是突發(fā)事件區(qū)域周邊的道路通行必然受到影響，因此在應(yīng)急車輛路徑選擇時，需保證路徑中某些路段的預(yù)計行程時間與實際值發(fā)生偏差時，對整體行程時間產(chǎn)生的不利影響最小。本文采用路徑可靠度對此進行衡量。

正常情況下，路段(ri,rj)交通流密度是理論正常值，應(yīng)急車輛處于自由行駛狀態(tài)時，行程車速接近道路限速值，此時路段行程時間為Tij。對于一條從始發(fā)點rs到終點rd的路徑，其中，s,d為路網(wǎng)中節(jié)點的編號。根據(jù)路段行程時間的預(yù)測值，應(yīng)急車輛在ti時刻進入路段(ri,ri+1)，并經(jīng)過Ti,i+1(ti)后駛出，考慮到應(yīng)急車輛進入節(jié)點ri的實際時間與ti存在偏差，假設(shè)實際進入的時間區(qū)間為，其中。在此區(qū)間內(nèi)進入時，應(yīng)急車輛行駛完路段所需的最大行程時間為

1.4 動態(tài)最優(yōu)路徑選擇兩階段模型

將城市路網(wǎng)抽象為時間依賴網(wǎng)絡(luò)模型(R,E,T×U)，其中，R={r1,r2,…,rM} 表示節(jié)點集合，相鄰節(jié)點之間的連接弧為路段(ri,rj)∈E，U為時間區(qū)間，Tij(t)為定義在區(qū)間U上的路段行程時間函數(shù)，表示應(yīng)急車輛在t時刻進入，從節(jié)點ri行駛到節(jié)點rj所需的時間，?t∈U，對于t ＞t0+H·Δt，定義Tij(t)=∞。假設(shè)應(yīng)急車輛位于節(jié)點rs，事故所在節(jié)點為rd，應(yīng)急車輛在t0時刻出發(fā)，則應(yīng)急車輛到達事故節(jié)點的最優(yōu)路徑為Psd(t0)，最短行程時間為Tsd(t0)。在動態(tài)最短路徑模型的基礎(chǔ)上優(yōu)化路徑可靠度，建立兩階段目標優(yōu)化模型為

式(11)為路徑可靠度目標，使所選路徑的可靠度最大。式(12)為路徑行程時間目標，由于應(yīng)急救援的時間緊迫性，優(yōu)化目標定義為最小化應(yīng)急車輛行程時間，即應(yīng)急車輛所經(jīng)過各個路段的行程時間之和最小。式(13)計算從出發(fā)點rs起，應(yīng)急車輛進入各個路段的時刻ti。式(14)～式(16)為約束條件，保證路徑序列是一條沒有回路的通路。

2 求解應(yīng)急車輛動態(tài)路徑選擇問題的混合布谷鳥搜索算法

2.1 混合布谷鳥搜索算法

布谷鳥搜索算法(Cuckoo Search Algorithm，CSA)具有搜索能力強、輸入?yún)?shù)少等優(yōu)點，但其搜索步長為定值，并且布谷鳥萊維(Levy)飛行習性造成長距離步長占比較少，容易陷入局部最優(yōu)解[7]。本文將蛙跳局部搜索和混沌原理引入到布谷鳥搜索算法中，提出一種混合布谷鳥搜索算法(Hybrid Cuckoo Search Algorithm,HCSA)，首先利用混沌原理進行種群的初始化，使得初始種群具備多樣性特征，然后引入蛙跳算法的局部搜索機制來加強局部搜索能力，并在萊維飛行的隨機搜索中加入線性遞減策略的慣性權(quán)重來增強其全局尋優(yōu)能力。

布谷鳥根據(jù)萊維飛行模式選窩產(chǎn)卵，布谷鳥選窩產(chǎn)卵的路線和位置更新公式為

式中：m為迭代次數(shù)；為第i個鳥窩在m+1代時的鳥窩位置；⊕為點對點乘法為第i個鳥窩在第m代的鳥窩位置；L(λ)為萊維飛行隨機搜索路徑；α為常數(shù)步長控制量，一般取α=0.01。將L(λ)進行簡化處理并經(jīng)過傅里葉變換得到概率密度函數(shù)[8]為

式中：λ為冪次系數(shù)。

在進行算法編程時，采用文獻[9]中Mantegna提出的模仿萊維飛行的跳躍路線公式，且文獻[10]證明了可以采用Mantegna算法實現(xiàn)等價計算。

式中：ζ為萊維飛行的飛行跳躍路線L(λ)；參數(shù)β與式(18)中λ的關(guān)系為λ=β+1，0＜β ＜2，通常在布谷鳥搜索算法中β=1.5；μ、τ為正態(tài)分布隨機數(shù)，服從的正態(tài)分布分別為

μ，τ所對應(yīng)標準差σμ，στ的取值分別為

式中：Γ 為標準的Gamma函數(shù)。

采用Logistic混沌映射[11]對布谷鳥搜索算法的解進行初始化。Logistic映射來源于動力學系統(tǒng)的人口統(tǒng)計，文獻[12]給出的系統(tǒng)方程為

式中：x(m)∈[0,1]；?為控制參數(shù)。假如混沌變量的值域為[a,b]，可利用線性變換公式u(k)=a+(b-a)x(m)將混沌變量的值域映射到優(yōu)化問題的定義域內(nèi)。

使用蛙跳算法增強局部搜索能力，假如將η個青蛙分成θ個族群，每個族群的青蛙個數(shù)為p，那么

式中：?為青蛙個體的更新矢量；rand 為在(0,1)內(nèi)隨機產(chǎn)生一個數(shù)；xw為青蛙的新位置；Smax為青蛙允許跳動的最大步長；Pw,i為第i個族群中最差的青蛙的位置；Pb,i為第i個族群中最好的青蛙的位置。將慣性權(quán)重引入布谷鳥尋窩產(chǎn)蛋的路線位置為

慣性權(quán)重ω采用文獻[13]提供的一種非線性遞減策略，即

兩階段目標優(yōu)化是從下至上逐層尋優(yōu)的過程，核心是求解K 條最短路徑的混合布谷鳥算法(HCSA-KSP)，如圖2所示。

圖2 兩階段混合布谷鳥算法原理Fig.2 Principle of two-stage HCSA

2.2 編碼方案與適應(yīng)度函數(shù)設(shè)計

在混合布谷鳥算法中，每個布谷鳥個體作為路網(wǎng)節(jié)點信息的載體，用向量進行表示，每個向量對應(yīng)于優(yōu)化問題的一個可行解。編碼是從優(yōu)化問題的決策空間到混合布谷鳥算法搜索空間的一個映射，算法的搜索空間由所有布谷鳥位置向量組合構(gòu)成，是整型空間的子集。因此，需要根據(jù)決策變量的特點將其映射到整型空間。動態(tài)最短時間路徑模型的決策向量為從應(yīng)急車輛出發(fā)節(jié)點rs到事故節(jié)點rd的路徑選擇方案，其中為正整數(shù)集合。采用 整數(shù)編碼方案將路徑編碼為，則對于包含M個節(jié)點的城市路網(wǎng)，可能的編碼方案為Md種，此時算法的搜索空間遠大于動態(tài)路徑問題的約束空間，算法容易陷入局部最優(yōu)，因此需要在整數(shù)編碼方案中加入路徑連通性約束，設(shè)計一種新的編碼，從而縮小算法的搜索空間。如圖3包含17個節(jié)點的城市路網(wǎng)中，應(yīng)急車輛從其所在的節(jié)點r14到事故節(jié)點r7的一條可行路徑為r14→r15-r16→r11→r7，相應(yīng)的布谷鳥位置編碼為Cuckoo:14 15 16 11 7。

圖3 城市路網(wǎng)模型Fig.3 Urban road network model

為保證布谷鳥位置對應(yīng)的路徑序列滿足連通性，提出一種隨機整數(shù)編碼方案，具體如下。

定義節(jié)點ri的鄰接節(jié)點集合為，當前路徑序列為，假如有集合，從其中隨機選擇一個節(jié)點作為有效節(jié)點ri+1，則有

式中：ε為一個隨機數(shù)，0＜ε ＜1。將當前路徑序列更新為，由此逐一搜索至事故點rd，形成布谷鳥的位置編碼X=。

適應(yīng)度是衡量個體優(yōu)劣的標志，是驅(qū)動布谷鳥種群進化的動力。根據(jù)動態(tài)最優(yōu)路徑模型的第1階段目標函數(shù)，定義HCSA-KSP 算法的適應(yīng)度函數(shù)為

2.3 局部尋優(yōu)策略

對于滿足FIFO 條件的城市路網(wǎng)，必須保證車輛行駛的每一個路段都滿足最短時間路徑要求，即如果一條最短時間路徑經(jīng)過rq，則一定是從源節(jié)點rs到節(jié)點rq的最短時間路徑。

事實上，每條最短時間路徑的子路徑也是最短時間路徑。由此設(shè)計布谷鳥算法的局部尋優(yōu)策略如下：首先標記最優(yōu)布谷鳥位置和最差布谷鳥位置中的相同節(jié)點；然后從第1 個重合節(jié)點起，比較路徑與的行程時間與；若，則對于來說，從源節(jié)點rs到節(jié)點之間，存在1 條時間更短的路徑，并將節(jié)點標記為瓶頸節(jié)點，否則令k=k+1，繼續(xù)比較和，直到標記出瓶頸節(jié)點；最后采用隨機編碼方案生成1條從節(jié)點(標志位)到瓶頸節(jié)點的路徑，去代替原中的相應(yīng)路徑，由此完成1次對最差布谷鳥位置的更新。

2.4 算法設(shè)計

求解動態(tài)最優(yōu)路徑的兩階段混合布谷鳥搜索算法以獲得K條最優(yōu)路徑為基礎(chǔ)，并以路徑可靠度為優(yōu)化目標，最終得到最優(yōu)路徑，HCSA-KSP 算法的步驟如下。

Step 1 初始化種群數(shù)量n，搜索維度d，最大迭代次數(shù)M，發(fā)現(xiàn)概率Pa，搜索空間范圍，蛙跳搜索組內(nèi)更新次數(shù)Ne，分組數(shù)θ，每組鳥窩的數(shù)量p，迭代計數(shù)器m=1。

Step 2 混沌初始化種群個體。根據(jù)隨機編碼方案，在決策空間內(nèi)產(chǎn)生F個布谷鳥個體組成的種群n，產(chǎn)生n維向量，保證每一個布谷鳥編碼是一條從應(yīng)急車輛出發(fā)節(jié)點rs到事故節(jié)點rd的通路，其中，。將Xf的每一維利用式(22)進行更新，產(chǎn)生混沌變量，然后利用載波公式映射到解空間。

Step 3 根據(jù)式(12)和式(13)計算F個鳥窩位置對應(yīng)的適應(yīng)度值f(Xf)，將所有的鳥窩個體按照適應(yīng)值降序排列，確定當前最佳鳥窩位置及其適應(yīng)值。

Step 4 將n個鳥窩分成θ組，每組p個。首先確定族群中最好的解和最差的解，并根據(jù)式(23)和式(24)進行更新。如果最差鳥窩位置得到了改善，即，則保留；否則，在該族群內(nèi)隨機產(chǎn)生一個鳥窩位置來替代最差的鳥窩位置。然后對族群重新進行混合，并按照降序排列，構(gòu)造新的布谷鳥種群，計算新的鳥窩位置對應(yīng)的適應(yīng)值，保留最優(yōu)位置，直到滿足局部搜索次數(shù)為止。

Step 5 按照式(17)～式(21)，式(25)和式(26)對新的鳥窩位置進行更新，得到1組新的鳥窩位置。

Step 6 隨機產(chǎn)生一個均勻分布的數(shù)r(0 ≤r≤1)，如果r ＞Pa，則隨機改變被發(fā)現(xiàn)的概率較大的鳥窩位置，保留被發(fā)現(xiàn)概率較小的鳥窩位置，從而獲得1組新的鳥窩位置。

Step 8 將各鳥窩位置的適應(yīng)值進行評估，然后將鳥窩的歷史最佳位置進行更新。

Step 9 如果算法滿足停止條件，則輸出結(jié)果；否則，返回Step 3～Step 9繼續(xù)執(zhí)行。

3 算例驗證

HCSA-KSP 算法是應(yīng)急車輛動態(tài)路徑選擇的核心，本文以圖4所示的某市某區(qū)部分區(qū)域城市路網(wǎng)為例，選取時間為2021年11月29日8:00-9:00，最短時間間隔Δt=5 min，利用網(wǎng)絡(luò)爬蟲獲取交通流數(shù)據(jù)，交通流數(shù)據(jù)包括車道寬度、車流密度、路段長度、路段行程時間、實時行程車速和路段預(yù)測行程車速，構(gòu)建實時路段行程車速函數(shù)，并求得路段行程時間函數(shù)。隨機選取10 個節(jié)點對，起點為救援車輛出發(fā)點，終點為事故發(fā)生點。為了模擬城市突發(fā)事件發(fā)生時的情境，選擇正常工作日的上班高峰期時間段作為事故發(fā)生后調(diào)度時間?？紤]復(fù)雜的動態(tài)路網(wǎng)變化，采用HCSA-KSP算法求解應(yīng)急車輛出發(fā)并到達終點的K條最短路徑及其行程時間，并與粒子群算法和經(jīng)典的布谷鳥算法作對比，驗證HCSA-KSP 算法的性能。然后在11月29日～12月3日，每天8:00-9:00 上班早高峰期間，通過秒表計時，按照優(yōu)化算法求解的動態(tài)選擇路徑，實地駕車獲取路徑行駛時間。11月29日～12月3日天氣情況均為晴間多云和微風狀況，8:00-9:00氣溫在10℃左右，可以認為這幾天的外部環(huán)境對獲取駕駛時間的影響相同，沒有太大差異。此外，在車輛起步和停止時刻通過秒表讀秒計時，因此時間最小單位設(shè)定為秒。HCSA-KSP算法參數(shù)如表1所示。

表1 HCSA-KSP算法參數(shù)設(shè)置Table 1 Parameter selection of HCSA-KSP

圖4 某市某區(qū)部分區(qū)域地圖與路網(wǎng)圖Fig.4 Map and road network map of some areas in a district of a city

為求得10 個節(jié)點之間的K 條最短路徑及其行程時間，運行HCSA-KSP 算法、粒子群算法和經(jīng)典布谷鳥算法，獲得的計算結(jié)果如表2所示。

分析表2最短路徑選擇結(jié)果可知，HCSA-KSP、PSO-KSP和CSA-KSP算法都能得到節(jié)點間的K條最短路徑及其行程時間，與實地駕車獲取的路徑行駛時間相比，各算法求解的結(jié)果誤差最大的為7.7%。

表2 K條最短路徑選擇結(jié)果Table 2 Results of K shortest paths selection

以節(jié)點r1到節(jié)點r37和節(jié)點r12到節(jié)點r46的路徑尋優(yōu)為例，HCSA-KSP算法與粒子群算法和經(jīng)典布谷鳥算法的收斂過程如圖5所示。從圖5可以看出，選擇節(jié)點r1到節(jié)點r37時，HCSA-KSP算法得到的行程時間在算法迭代到約18 代時達到全局收斂，而PSO-KSP 算法約在49 代時收斂，CSA-KSP算法約在71 代時收斂，HCSA-KSP 算法和CSAKSP 算法比PSO-KSP 算法得到更少的行程時間。選擇節(jié)點r12到節(jié)點r46時，HCSA-KSP 算法同樣比PSO-KSP 算法和CSA-KSP 算法收斂的要快，但是三者獲得相同的行程時間。

圖5 r1 到r37 和r12 到r46 路徑尋優(yōu)的3個算法進化過程Fig.5 Evolutionary processes of three algorithms in path optimization of r1 to r37 and r12 to r46

總體來講，對于相同的起點和終點，由于不同算法計算得到的最優(yōu)路徑不同。相比之下，HCSAKSP算法獲得的路徑最短行程時間要更優(yōu)，且算法的計算時間更短，算法能夠更快地收斂到最優(yōu)解。說明HCSA-KSP 算法解決應(yīng)急車輛動態(tài)路徑選擇問題相比其他算法性能更優(yōu)。

4 結(jié)論

城市路網(wǎng)的交通狀況是實時變化的，突發(fā)事件發(fā)生后救援車輛除了要考慮以最短的時間到達待救點之外，還必須考慮路網(wǎng)實時狀況。為此，本文創(chuàng)新性地提出以最大路徑可靠度為第1 階段優(yōu)化目標，以最短行程時間為第2階段目標的兩階段優(yōu)化模型。此外，本文設(shè)計了一種混合布谷鳥搜索算法，通過混沌搜索改進了布谷鳥算法的初始種群，并通過加入蛙跳算法改進了局部搜索能力，通過加入路徑連通性約束的編碼機制，縮小了算法的搜索空間。以某市某區(qū)部分路網(wǎng)為例，將實時交通數(shù)據(jù)應(yīng)用到模型和求解算法中得到的結(jié)果與實地駕車獲取的結(jié)果相比，誤差較小。本文提出的兩階段優(yōu)化模型成功獲得了應(yīng)急車輛的動態(tài)行駛路徑，得到了最優(yōu)的結(jié)果。本文僅選取了部分路網(wǎng)為研究實例，全路網(wǎng)多事故情境下研究將是未來的方向。