姚 佼，邵楚薇，鮑雨婕，李宇航

(上海理工大學(xué) 管理學(xué)院，上海 200093)

0 引言

城市化進程的加劇，城市多種功能的聚集化，突發(fā)應(yīng)急事件發(fā)生的概率不斷上升，如何降低其發(fā)生后的人員傷亡和財產(chǎn)損失值得關(guān)注[1]。救援時間作為應(yīng)急交通的關(guān)鍵參數(shù)，一直是應(yīng)急交通管理的主要目標，相關(guān)的研究表明，路網(wǎng)應(yīng)急交通產(chǎn)生前的車輛調(diào)度，及產(chǎn)生后在路網(wǎng)中路徑選擇對其影響尤為顯著[2]。因此，如何將二者進行有效的集成，針對不同類型應(yīng)急救援車輛，精準施策，進行有效的集成，對于降低突發(fā)事件的影響，減輕其發(fā)生后果的嚴重性，具有十分重要的意義。

對不同類型應(yīng)急救援車輛的合理地調(diào)度，并對其在路網(wǎng)的行駛路徑進行優(yōu)化，一直是應(yīng)急交通系統(tǒng)優(yōu)化的研究熱點和難點。關(guān)于應(yīng)急車輛調(diào)度，?zdamar等[3]對自然災(zāi)害下應(yīng)急救援中多階段的救災(zāi)物資配送問題進行了研究，并結(jié)合拉格朗日松弛法對動態(tài)救災(zāi)模型進行分析求解；計雷[4]提出應(yīng)急調(diào)度救援的本質(zhì)是運輸費用成本和時間成本，因此他將模型簡化為多目標優(yōu)化問題并求最優(yōu)解；在應(yīng)急交通的路徑選擇方面，Potvin等[5]以突發(fā)事件為背景，研究了應(yīng)急救援車輛路徑問題，并且解決一個考慮客戶實時請求和車輛動態(tài)行駛時間的時間窗動態(tài)車輛路徑問題；劉勇等[6]根據(jù)基本蟻群模型，進行了最優(yōu)路徑蟻群模型的改進研究，在蟻群算法的轉(zhuǎn)移概率中引入路徑權(quán)重，得到了應(yīng)急救援的最優(yōu)路線，同時結(jié)合調(diào)度路徑優(yōu)化問題進行了多方面的考慮。

雙層規(guī)劃模型綜合考慮了上下兩層目標的協(xié)調(diào)，從而可以取得整個系統(tǒng)的最優(yōu)解。Calvete等[7]基于此，構(gòu)建了以生產(chǎn)調(diào)度問題為核心的雙層規(guī)劃模型，上層模型的目標是將時間成本和費用成本最小化，下層模型將生產(chǎn)成本最小化，并結(jié)合蟻群算法對模型進行求解；楊忠振等[8]建立的配送選擇與路徑優(yōu)化雙層規(guī)劃模型，證明其可以有效降低配送系統(tǒng)的總成本，提高了配送的整體效率。在應(yīng)急救援交通的管控中，若單獨從一個角度進行優(yōu)化，會因為考慮不夠全面，無法得到整體最優(yōu)的決策方案。只有將調(diào)度與路徑問題綜合考慮,彼此反饋，全面協(xié)調(diào)應(yīng)急救援中的各個環(huán)節(jié)，才能針對應(yīng)急救援城市道路的特點制訂成熟的、實時的應(yīng)急救援方案。本研究綜合雙層規(guī)劃模型在生產(chǎn)調(diào)度、物流配送及路徑優(yōu)化等方面的效果，根據(jù)不同應(yīng)急救援車輛類型，結(jié)合路網(wǎng)交通狀態(tài)的動態(tài)變化[9]， 將應(yīng)急救援的調(diào)度和路徑選擇進行集成，構(gòu)建相應(yīng)的雙層規(guī)劃模型，并進行求解。

因此，本研究的重點主要聚焦在：

(1)基于城市應(yīng)急救援事件發(fā)生后，針對不同應(yīng)急救援車輛類型進行調(diào)度，以及動態(tài)路網(wǎng)下應(yīng)急車輛最優(yōu)路徑選擇問題，提出了基于雙層規(guī)劃的應(yīng)急救援調(diào)度與動態(tài)路徑集成優(yōu)化模型。

(2)采用基于非優(yōu)勢排序和精英策略的遺傳算法和改進蟻群對模型進行求解。

(3)通過實際的案例分析與驗證，驗證模型在減少應(yīng)急車輛的調(diào)度成本、在途行程時間、降低路網(wǎng)擁堵程度等方面的實用性。

1 應(yīng)急救援調(diào)度和路徑選擇的目標分析

應(yīng)急救援的主要目標是盡可能降低突發(fā)事件造成的影響[10]，同時讓應(yīng)急交通能在最短時間內(nèi)抵達事故發(fā)生點。因此，應(yīng)急救援主要從應(yīng)急交通的調(diào)度和路徑動態(tài)選擇兩方面進行考慮。其中，應(yīng)急車輛的調(diào)度是一個涉及多因素的復(fù)雜問題[11]，不僅要兼顧應(yīng)急救援時間，還要考慮受到出救小區(qū)資源調(diào)度分配的公平性、路徑費用、救援不及時造成的損失等多方面的影響。本研究考慮單應(yīng)急救援請求點、多應(yīng)急出救點、不同類型應(yīng)急救援車輛(如消防車、救護車、公安警車、工程搶險車)[12]，在應(yīng)急調(diào)度階段，將優(yōu)化的主要目標分為3個：以最小的時間成本實現(xiàn)對應(yīng)急救援請求點的響應(yīng)、以最小的固定成本實現(xiàn)各出救小區(qū)的選擇、以最優(yōu)的容量成本限制求解各出救小區(qū)中不同類型應(yīng)急車輛的調(diào)度數(shù)量；在路徑選擇階段，則重點考慮應(yīng)急車輛到達救援點的時間盡可能短[13-14]，即不僅考慮救援路徑沿線的交叉口數(shù)量，及信號延誤時間，還需要加入救援路徑上的動態(tài)交通狀態(tài)的影響。

基于上述目標的分析，考慮將應(yīng)急救援的車輛調(diào)度和路徑選擇結(jié)合，建立雙層規(guī)劃模型，進行集成優(yōu)化，其中上層應(yīng)急調(diào)度中的時間成本是在下層路徑行程時間的基礎(chǔ)上，考慮不同出救點的車輛數(shù)量計算得到，其固定成本反映了各個應(yīng)急小區(qū)的車輛出動情況，也會影響下層的路徑選擇，從而最終影響行程時間，上下兩層間的目標不斷相互反饋，最終結(jié)果趨于最優(yōu)解，模型的研究流程如圖1所示。

圖1 應(yīng)急救援交通調(diào)度與路徑優(yōu)化集成的雙層規(guī)劃 模型研究流程Fig.1 Flowchart of studying bi-level programming model of integrated traffic scheduling and route optimization of emergency rescue

2 模型描述

應(yīng)急救援的調(diào)度與路徑選擇可以看作是一個雙層規(guī)劃[15]，為降低研究的復(fù)雜性，本研究設(shè)計不同類型應(yīng)急救援車輛的出動位置以交通小區(qū)為單位進行劃分，并根據(jù)該交通小區(qū)相應(yīng)半徑范圍內(nèi)是否存在車輛的集合地(如救護車的出動是考慮小區(qū)內(nèi)是否存在醫(yī)院以及數(shù)量，消防車考慮小區(qū)內(nèi)是否存在消防站及其數(shù)量，工程搶險考慮小區(qū)內(nèi)是否存在市政搶險單位及其數(shù)量)，來確定該出救小區(qū)是否能出動相應(yīng)類型的應(yīng)急車輛進行救援。

決策部門根據(jù)各類應(yīng)急交通資源的所處交通小區(qū)的位置，以及已知應(yīng)急救援請求點的需求，在允許的各類應(yīng)急車輛數(shù)約束下確定最佳的應(yīng)急車車輛調(diào)度方案；對于各類應(yīng)急車輛在出救點和救援請求點之間的路徑選擇，考慮路網(wǎng)交通狀態(tài)的變化，動態(tài)優(yōu)化應(yīng)急交通的出行路徑[16]。以最優(yōu)化應(yīng)急救援交通調(diào)度評價函數(shù)和最優(yōu)路徑選擇評價函數(shù)為目標[17]，采用雙層規(guī)劃的建模方法[18]，構(gòu)建了動態(tài)的調(diào)度與路徑選擇的集成優(yōu)化模型[19]。

考慮研究問題的復(fù)雜性，模型的建立進行了如下的假設(shè)：(1)救援請求點、出救點所在交通小區(qū)的地理位置，以及需要各類應(yīng)急救援交通的車輛數(shù)均已知，且不存在變化；(2)路網(wǎng)中所有路段均連通，且路段長度、道路通行能力等參數(shù)均已知；(3)應(yīng)急救援交通車輛類型較多，本研究選取較為關(guān)鍵的3類應(yīng)急救援車輛類型進行研究；(4)本研究出現(xiàn)的各類型應(yīng)急救援車輛的速度已知而且固定，終點均為救援請求點，且不考慮完成救援任務(wù)后的返回；(5)相同類型的應(yīng)急車輛在救援中假定同時出動，不考慮車輛出動順序。

2.1 上層模型構(gòu)建

上層主要從應(yīng)急救援車輛調(diào)度過程中的固定成本、容量成本和救援時間成本3個方面進行分析，構(gòu)建不同類型應(yīng)急救援車輛的調(diào)度模型。具體而言：

目標函數(shù)：

ck(t)。

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

λp={0,1}。

(8)

模型中有兩類符號,決策變量和模型參數(shù)。

其中，決策變量：λp為出救小區(qū)p是否派出車輛進行救援，如果是λp=1，否則λp=0。

在上層規(guī)劃中，式(1)的目標函數(shù)為最小化應(yīng)急車輛調(diào)度的整體費用成本(包括固定成本、容量成本和時間成本)；式(2)的約束表示各出救小區(qū)是否參與救援的判斷參數(shù)；式(3)的約束表示該出救小區(qū)中同一救援車輛類型的容量限制判斷參數(shù)；式(4)的約束表示應(yīng)急車輛出救小區(qū)中可自由調(diào)度的車輛總數(shù)不能小于實際參與調(diào)度的車輛總數(shù); 式(5)的約束表示實際出救小區(qū)中調(diào)度的各類應(yīng)急車輛總數(shù)等于救援請求點的車輛需求總量；式(6)的約束表示至少要選擇一個出救小區(qū)進行應(yīng)急救援；式(7)的約束表示選擇應(yīng)急車輛出救小區(qū)的總費用不能大于應(yīng)急救援小區(qū)的總固定成本上限；式(8)為決策變量的取值約束。

2.2 下層模型構(gòu)建

下層主要從應(yīng)急救援車輛出動救援時的路段行程時間和信號延誤時間兩個方面進行分析，構(gòu)建不同類型應(yīng)急救援車輛的動態(tài)路徑選擇模型。該模型基于救援前制定的靜態(tài)最優(yōu)路徑，并根據(jù)實時路網(wǎng)交通狀態(tài)調(diào)整最優(yōu)路徑[20]。因此，本研究固定的時間間隔，采用馬爾可夫過程對路網(wǎng)交通狀態(tài)進行預(yù)測[21]，不同類型應(yīng)急車輛出動前，根據(jù)時變的路徑信息，更新下一步的優(yōu)化救援路徑，直至到達救援請求點。

具體目標函數(shù)為：

(9)

約束條件：

(10)

(11)

(12)

(13)

(14)

模型主要包含兩類符號,決策變量和模型參數(shù)。

模型參數(shù)：T′p為從p出救小區(qū)到事故發(fā)生點的在途行程時間；Tc為不同類型救援車輛在交叉口(路網(wǎng)拓撲中的節(jié)點)的延誤時間，具體的延誤時間計算參考經(jīng)典的交叉口延誤模型[22]；tij為應(yīng)急車輛從節(jié)點i行駛到節(jié)點j的行程時間；fZ(Δtl)為表示路徑交通狀態(tài)參數(shù)；Δtc為交叉口等待的時間差；kij(Δtl)為時間間隔Δtl路徑ij的交通狀態(tài)影響值。

在下層規(guī)劃中，式(9)目標函數(shù)最小化應(yīng)急車輛路段行程時間的在途行程時間(包括路段行程時間和信號延誤時間)；式(10)的約束表示應(yīng)急車輛從每個出救小區(qū)至救援請求點，均得到一條最優(yōu)路徑; 式(11)的約束為交通狀態(tài)影響值的求解；式(12)約束為應(yīng)急車輛路徑的連續(xù)性限制，如果救援車輛從一個節(jié)點進入，也應(yīng)從同一個節(jié)點離開；式(13)和(14)均為變量取值的約束。

3 模型求解

本研究上下層模型分別建立在NSGA-II算法和改進蟻群算法的基礎(chǔ)上，結(jié)合全局搜索進行最終結(jié)果的求解。首先，從下層應(yīng)急車輛最優(yōu)路徑選擇著手，篩選出符合條件的最優(yōu)路徑，然后，將結(jié)果代入上層應(yīng)急車輛調(diào)度中，由此，得到所有類型應(yīng)急車輛最優(yōu)路徑結(jié)果均相同的雙層規(guī)劃最優(yōu)解；由于某一類型的應(yīng)急車輛出動救援，路網(wǎng)交通狀態(tài)可能發(fā)生變化，因此需不斷更新下層路徑選擇最優(yōu)解，并將更新結(jié)果反饋給上層調(diào)度模型；如此循環(huán)往復(fù)多次，如果在一定的迭代次數(shù)內(nèi)，全部類型的應(yīng)急救援車輛均已出動，且當(dāng)前上層調(diào)度的費用成本和下層路徑選擇的時間成本的總最優(yōu)解均不發(fā)生改變，則終止計算，輸出當(dāng)前上、下層的最優(yōu)解[23]，作為雙層規(guī)劃模型的最優(yōu)解。具體的模型求解流程如圖2所示。

圖2 調(diào)度和路徑優(yōu)化集成的雙層規(guī)劃模型的求解流程Fig.2 Flowchart of solving bi-level programming model of integrated traffic scheduling and route optimization

4 案例分析與驗證

選取江蘇省蘇州市工業(yè)園區(qū)相關(guān)實際路網(wǎng)，模擬高峰時段轄區(qū)內(nèi)第五元素網(wǎng)球場突發(fā)火災(zāi)的緊急救援交通調(diào)度和路徑優(yōu)化進行案例分析研究。

根據(jù)相關(guān)的信息統(tǒng)計，路網(wǎng)共有36個路段節(jié)點，55條相交路段。

根據(jù)蘇州的實地建筑分布情況，以及該交通小區(qū)半徑范圍300 m內(nèi)是否存在醫(yī)院、公安派出所和消防站，明確消防車、救護車、警車等各類應(yīng)急車輛的出救小區(qū)位置。據(jù)此根據(jù)實地的調(diào)查，案例路網(wǎng)中存在5個應(yīng)急車輛不同類型的出救小區(qū)，具體的分布如圖3所示。

圖3 案例路網(wǎng)及各類型應(yīng)急車輛的出救小區(qū)分布Fig.3 Road network of case study and distribution of emergency vehicles’ rescue zones

結(jié)合火災(zāi)發(fā)生時間段(工作日上午8時—9時)的路網(wǎng)交通狀態(tài)等相關(guān)信息，確定應(yīng)急救援分配和應(yīng)急車輛動態(tài)最優(yōu)路徑選擇，并根據(jù)前述的雙層規(guī)劃模型和求解算法，進行仿真驗證。

基于歷史統(tǒng)計數(shù)據(jù)，進行相關(guān)的參數(shù)標定，相應(yīng)參數(shù)設(shè)置如下:

(1)需求點和出救小區(qū)：發(fā)生火災(zāi)的救援請求點用節(jié)點19#表示；根據(jù)附近公安派出所、消防站和醫(yī)院的相應(yīng)位置，確定應(yīng)急車輛出救小區(qū)重心的分布，確定各類應(yīng)急車輛的出救起始節(jié)點，標記為節(jié)點1#，3#，12#，21#和33#，并根據(jù)實際數(shù)據(jù)，調(diào)查各出救小區(qū)各類應(yīng)急車輛的可供應(yīng)量，如表1所示。

表1 各出救小區(qū)的應(yīng)急車輛資源分布Tab.1 Distribution of emergency vehicle resources in each rescue zone

(2)道路網(wǎng)絡(luò)配置參數(shù)：統(tǒng)計案例路網(wǎng)的相關(guān)靜態(tài)參數(shù)，調(diào)查相應(yīng)道路的交通量，各路段相關(guān)參數(shù)如表2所示。

表2 案例路網(wǎng)的相關(guān)參數(shù)Tab.2 Parameters of road network of case study

(3)應(yīng)急資源需求信息：根據(jù)《突發(fā)事件應(yīng)急管理》中規(guī)定的生產(chǎn)安全事故等級標準，判斷該突發(fā)性火災(zāi)的規(guī)模屬于較大規(guī)模的突發(fā)事件。已知該火災(zāi)發(fā)生時消防車輛、救護車輛和警車均需到達現(xiàn)場進行應(yīng)急救援。查詢應(yīng)急管理部對火災(zāi)現(xiàn)場應(yīng)急處置措施，及較大火災(zāi)對這3類應(yīng)急車輛的的需求量，整理得到救援請求點應(yīng)急車輛的需求量如表3所示。

表3 救援請求點各類應(yīng)急交通需求分析Tab.3 Analysis of emergency traffic demand at rescue request point

(4)應(yīng)急車輛調(diào)度時間成本：根據(jù)公安部相關(guān)火災(zāi)損失統(tǒng)計和損失計算方法[24]，并參考《江蘇省醫(yī)療服務(wù)項目價格手冊》，計算不同類型應(yīng)急救援交通的調(diào)度時間成本相關(guān)參數(shù)，如表4所示。同時，結(jié)合表2中的相關(guān)的路徑長度，計算不同類型應(yīng)急救援車輛路徑選擇的路段行程時間，結(jié)合表4中的行駛費用，最終計算出各類應(yīng)急救援車輛的調(diào)度時間成本。

表4 不同類型應(yīng)急救援車輛調(diào)度成本分析Tab.4 Analysis of scheduling cost of different types of emergency vehicles

(5)調(diào)度容量限制成本：通過上述參考文獻，計算每個出救小區(qū)出動車輛的固定成本為300元，進而求得不同類型應(yīng)急救援車輛調(diào)度的固定成本；根據(jù)應(yīng)急車輛出動所花費的時間，判斷不同類型應(yīng)急救援車輛出發(fā)的時間間隔為5 min，以此為固定的間隔時間更新路徑交通狀態(tài)信息，并計算不同類型應(yīng)急救援車輛沿線路徑的交叉口處的信號延誤時間。每種應(yīng)急車輛調(diào)度的容量成本情況如表5所示，結(jié)合模型可計算應(yīng)急車輛調(diào)度的容量成本。

表5 應(yīng)急調(diào)度車輛的容量限制分析Tab.5 Analysis of capacity limitation of scheduling emergency vehicles

結(jié)合上述的雙層規(guī)劃的模型參數(shù)，進行求解。上層應(yīng)急車輛的調(diào)度為整個雙層規(guī)劃模型的主程序，先假設(shè)每個出救小區(qū)到救援請求點的行駛時間僅考慮最短路徑長度，在迭代完成時，將不同應(yīng)急出救小區(qū)選擇和各類型應(yīng)急車輛的調(diào)度方案導(dǎo)入到下層模型下層根據(jù)上層的初始方案進行計算，并考慮到每條路徑的交通狀態(tài)，更新路網(wǎng)交通狀態(tài)，分別為初始、5 min和10 min的路網(wǎng)交通狀態(tài)。

通過計算求得各個出救小區(qū)到救援請求點的最優(yōu)路徑，同時將最優(yōu)路徑行駛的時間結(jié)果返回到上層的調(diào)度模型中，上層模型再次調(diào)整調(diào)度方案，重復(fù)迭代此過程，直至得出最終的出救小區(qū)選擇、車輛出動數(shù)量及路徑優(yōu)化方案。

求解過程，上層調(diào)度的求解中運用 MATLAB編寫相關(guān)的應(yīng)急車輛調(diào)度優(yōu)化函數(shù)，運用NSGA-II算法求解，設(shè)置遺傳變異算子參數(shù)(種群規(guī)模50，迭代100次，交叉概率0.8，變異概率0.2)；下層的路徑選擇，根據(jù)案例的相關(guān)數(shù)據(jù)，通過MATLAB仿真軟件，運用改進的蟻群算法求解，參數(shù)設(shè)置為m=200，NCmax=100，α=0.5，β=1，ρ=0.1，最終求解僅考慮調(diào)度或路徑優(yōu)化，以及本研究基于雙層規(guī)劃的調(diào)度和路徑選擇集成的結(jié)果，如圖4所示，雙層規(guī)劃模型計算求得的調(diào)度成本、行程時間等參數(shù)如表6所示。

圖4 雙層規(guī)劃模型與單獨考慮調(diào)度或路徑選擇模型的結(jié)果對比Fig.4 Comparison of results of bi-level programming model with models only considering scheduling or route selection

為進一步驗證本研究所采用的雙層規(guī)劃模型對基于緊急車輛調(diào)度各路徑優(yōu)化研究的有效性，對僅考慮調(diào)度模型中，采用Dijkstra最短路徑分配法對路徑進行選擇；在僅考慮路徑選擇的模型中，采用全有全無分配法對以調(diào)度方案進行選擇，最后將3種情況下的費用成本和時間成本進行了對比分析，具體結(jié)果如表7所示。

從中可以看出，與僅考慮調(diào)度或路徑選擇的應(yīng)急車輛模型相比，由于雙層規(guī)劃模型將調(diào)度和路徑優(yōu)化集成，能夠根據(jù)下層道路情況的變化更新最優(yōu)路徑的選擇，同時反饋給上層調(diào)度，更新調(diào)度方案，上下兩層相互反饋，可以有效提高應(yīng)急救援的整體效率，優(yōu)化資源分配，故上層調(diào)度模型總成本降低了2.67%，下層路徑選擇后的在途行程時間減少了21.05%，具體的對比分析示意如圖5所示。此外，與僅考慮調(diào)度或路徑優(yōu)化的模型相比，基于雙層規(guī)劃的集成模型克服了重復(fù)選取同一條路徑的缺陷，降低路段的壓力，避免擁堵結(jié)果的產(chǎn)生。因此，基于雙層規(guī)劃的應(yīng)急車輛優(yōu)化研究模型所得到的方案要更優(yōu)越，實用性更高。

5 結(jié)論

本研究從不同類型應(yīng)急救援車輛的調(diào)度和動態(tài)路徑選擇的集成出發(fā)，從調(diào)度的固定成本、容量成本和時間成本，以及路徑選擇的路段行程時間和信號延誤時間等多個角度著手，構(gòu)建了基于雙層規(guī)劃模型的不同類型應(yīng)急車輛調(diào)度和路徑選擇集成優(yōu)化模型，進而采用全局搜索，結(jié)合NSGA-II算法和改進蟻群算法對模型進行了求解。最后通過相關(guān)的案例，對模型的效果進行了分析對比，結(jié)果表明：本研究的集成優(yōu)化模型與僅考慮調(diào)度或路徑選擇的模型相比，在調(diào)度成本和路徑選擇的在途行程時間等方面有較好的改進，具有較好的實用性和應(yīng)用價值。

表6 應(yīng)急救援調(diào)度與動態(tài)路徑選擇集成的雙層規(guī)劃模型結(jié)果分析Tab.6 Analysis of result of bi-level programming model of integrated emergency rescue scheduling and dynamic route selection

表7 雙層規(guī)劃模型與單獨考慮調(diào)度或路徑選擇模型的費用時間對比Tab.7 Comparison of costs and time of bi-level programming model with models only considering scheduling or route selection

圖5 模型的調(diào)度成本和路徑行程時間對比Fig.5 Comparison of scheduling costs and route travel time of models

但應(yīng)該注意的是，為了簡化運算，研究的案例是基于固定時間的進行路網(wǎng)更新，而現(xiàn)實中路網(wǎng)的變化更為復(fù)雜，部分路段的變化情況可能被錯誤預(yù)估。因此，面對不同類型應(yīng)急車輛救援，可在本研究模型的基礎(chǔ)上進一步調(diào)整，如針對不同類型車輛的出動優(yōu)先性也可在后續(xù)進一步深入研究。