基于剝奪成本分析的應急救援路徑優化研究

嚴能裕, 高景鈺，曹克讓

(沈陽化工大學 計算機科學與技術學院， 遼寧 沈陽 110142)

目前因自然災害頻發，應急物流體系的實時優化得到了許多學者的關注，相比于之前單救援運輸工具，使用直升機-車輛協同配送應急救援物資成為主要的救援運輸工具.阮俊虎等[1]在醫療物資的運輸中采取載具協同配送方式；薛星群等[2]在災后應急物資的聯合調度中也是采取了協同運輸模式；針對路徑優化以及多目標優化問題，李雙琳等[3]研究了震后初期應急物資配送的路徑優化問題，在需求模糊的情況下聯合運輸，將總耗時最短和受災點應急物資未滿足的總損失最小為目標建立了一個多目標選址-多式聯運模型加以求解；朱莉等[4]研究了受災差異跨區域的并且帶有時間窗限制的路徑優化問題；韓景倜等[5]從技術實施與應用角度研究應急救援物資的調度問題,以時間性、經濟性和可靠性為優化目標,建立了多目標決策模型;張國富等[6]面向多儲備點、多發放點、多種應急救援物資的并發分配與調度多目標優化模型,提出一種基于二維NSGA-Ⅱ與蟻群優化的混合智能搜索算法并進行求解.

在協同運輸救援患者時，文獻[7-9]發現從主觀角度出發，考慮患者的心理痛苦差異程度可以提高救援的公平性以及緩解患者的心理創傷，Pérez-Rodríguez等[10]在應急物資分配與調度過程中采用剝奪成本(deprivation cost)度量受災點被救人員因物資需求未及時分配而遭受的心理痛苦代價;朱莉[11]在對跨區域應急救援的研究時，構建了兼顧效率和公平的跨區域協同應急救援路徑選擇模型，將區域獨自應急和基于時間和距離的協同應急等不同情形進行對比并分析.綜上所述，考慮到自然災害情境中部分研究沒有針對通行受限采取聯合運輸或者是采取聯合運輸卻沒有對患者的心理痛苦差異程度進行充分考慮，所以部分學者在決定決策目標時也未把各受災點被救人員的絕對和相對層面痛苦差異性作為決策目標之一.因此，筆者構建了多目標、多式聯運，綜合考慮時間效率和公平的模型，以傷員總剝奪成本最小和總等待時間最小為決策目標，設計了針對模型的蟻群算法并通過實驗論證得出該模型的可行性.

1 問題描述與模型構建

問題研究的背景描述：某地震災害波及A區域(省或者市范圍內)，在A區域內有一個急救中心，擁有1輛直升機和4輛急救汽車，設定坐標為(0,0)，受災點一共有25個且坐標在(-30,30)內隨機生成,并且輕傷和重傷患者數量也隨機生成.任選3個點為具有通行約束的受災點，通行約束的受災點由于路面受損具有一定的時滯性，需要耗費時間進行疏通清理，所以依賴高效且運輸環境靈活的直升機進行救援，不具有通行約束的受災點由急救車輛和直升機進行協同救援.為了降低重傷患者的心理創傷差異性(用剝奪成本衡量)，需要給救援工具賦予不同的職能，尋求可通行路段中的最短路徑[12].由急救車運輸輕傷患者，直升機運輸重傷患者，應在重傷患者總等待時間耗時最短、不同傷員的心理創傷差異性程度最小的決策目標下對通行路徑進行選擇.聯合救援示意圖如圖1所示.

圖1 聯合救援示意圖Fig.1 Collaborative rescue schematic

1.1 假設條件

(1) 每個區域均有一個救護中心，救護中心在災情開始時并沒有傷員，不受救援時間窗限制.

(2) 受災區域內受災點，受傷人員數量已知，受災點部分有通行約束.

(3) 任意受災點受傷人員數量不超過車輛最大荷載數量，車輛容量已知且型號相同.

(4) 任意受災點重傷人員數量不超過直升機最大荷載數量，直升機容量已知且型號相同.

(5) 車輛行駛速度與各受災點道路損壞程度有關.

(6) 車輛與直升機在各點停留時間與受傷人員數量呈正相關.

(7) 由于各區域受災害的毀壞程度不同，受災點的受傷人員被救治的時間窗約束和傷員的疼痛忍受時長均存在差異性.

(8) 以急救中心為原點，各受災點、傷員隨機分布.

1.2 符號說明

m：急救中心.

A={1,2,3,…,a,a+1,…,A}：受災區域的集合，相鄰之間的區域記作a和a+1.

N=(1,2,3,…,i，j,…,N)：各區域受災點的集合，任一受災點記作i和j.

K=(1,2,3,…,k,…,K)：各區域內急救車的集合.

L=(1,2,3,…,l,…,L)：各區域內直升機的集合.

Wk：車輛最大荷載數.

Wl：直升機最大荷載數.

p：區域內受災點的傷員.

pa,i：區域a內受災點i需要救援的傷員數量.

da,ij：區域a內受災點i與受災點j的距離.

da,im：區域a內的受災點i與急救中心m的距離.

ta,ijk：車輛k在區域a內從受災點i到受災點j行駛所耗的時間.

ta,imk:車輛k在區域a內從受災點i返回急救中心m所花費時間.

ta,iml:直升機l在區域a內從受災點i返回急救中心m所花費的時間.

Ta,ip：區域a內受災點i的傷員p從等待救援到到達急救中心m的總剝奪成本.

v0a,ijk：未受災時救護車輛k在區域a內從受災點i到受災點j的平均行駛速度.

ua,ijk：受災時車輛的速度衰減系數.

va,ijk：受災時車輛的行駛速度.

pa,i：受災點i處需要被救援的傷員數量.

Oi,a：救護車輛的救援時間窗，必須在時間窗內趕到受災點處進行初步救助.

Qa,ip：區域a內受災點i的傷員p得到救助前的最大承受時間.

ta,ik：區域a內受災點i處車輛k為了給病人初步救助和轉移病人所耗費的時間.

Sa,ik：區域a內受災點i處車輛k接收到的時刻.

Sa,mp：區域a內傷員p返回急救中心m處的時刻.

Xa,ijk：0-1決策變量,用來描述應急救援路徑的選擇,區域a內車輛k從受災點i經過受災點j時為1，否則為0.

筆者借鑒文獻[8-10]提出的以剝奪成本衡量傷員的心理創傷這一概念，并用總剝奪成本作為該模型可行性的一個決策目標.朱莉[12]認為傷員心理創傷的主觀感受應隨緊急救援過程的實施呈三階段形態.第一階段為受災點患者在災害發生后等待救援時，自身遭受的絕對剝奪成本隨著等待時間的增加呈指數型上升.第二階段為救援人員抵達災區后給患者進行初步的救助，患者自身的痛苦開始得到緩和，絕對剝奪成本由起始的指數型增加轉變為線性下降.在得到初步救助之后的運輸途中，車內患者所感知的心理創傷差異值又會隨著時間的增長而增加，從而導致相對剝奪成本的增加，相比較于第一階段，第三階段的絕對剝奪成本雖然也呈指數型增加，但由于已經得到初步救助，所以此階段上升速率較第一階段更為緩和.筆者根據該三階段概率密度函數表示式總結出總剝奪成本函數表達式為

∑k,l∈Nf2(t)[g1(t)+g2(t)]+

第一階段為不同傷情患者等待救助時產生的剝奪成本;第二階段為輕傷患者與重傷患者得到救助時剝奪成本的緩慢增加階段;第三階段為不同傷情的患者的剝奪成本進行求和運算得到的總剝奪成本.

1.3 模型構建

考慮成本和總耗時較小的基礎上，筆者以傷員總剝奪成本最小和總等待時間最小作為決策目標，為多區域救援應急模式的實施提供可行性分析.

重傷患者總等待時間最小和心理創傷差異性最小目標函數分別表示為:

min∑a∈A∑i,j∈N∑k∈K∑l∈Ltijk×Xa,ijk+

tmbl×Xa,mbl,

直升機的飛行速度(不受通行約束的影響)為va,l.

車輛的行駛速度(受通行約束影響)為

va,k=v0a,k×ua,k.

車輛從受災點i到受災點j所花費時間為

ta,ijk=da,ij/va,k.

車輛k從受災點i行駛到受災點j的0-1決策變量為

∑k∈K∑j∈NXa,ijk=1.

確保救援車輛救助若干受災點處的患者總人數不超過該車輛的荷載量，即

∑i,j∈Npa,i×Xa,ijk≤Wk.

確保直升機運輸若干受災點處的患者總人數不超過該直升機的荷載量，即

∑b∈B∑m∈Apa,iXa,bml≤Wl.

區域a內車輛k到達受災點i花費的時間小于該受災點的時間窗約束為

Sa,ik≤Oa,i.

為確保患者能及時得到救助，區域a內受災點i處的傷員p得到救助的時間必須小于該患者的最大承受時間，即

Sa,mp-Sa,ip≤Qa,ip.

車輛和直升機通過路徑的0-1決策變量為

Xa,ijk,Xa,bml∈{0,1}.

車輛k到達受災點i處接收患者花費的總時間為

∑i∈N∑k∈Kt1=ta,ik×pa,i.

1.4 應急策略描述

傳統的協同運輸應急救援模式主要是由急救中心派發急救車輛與直升機前往受災點進行救援，急救車輛根據地形受損情況和受災點與急救中心的距離遠近選擇路徑，直升機首先選擇具有通行約束的受災點進行救助.出于人道主義的考慮，新模型在應急救援決策中重視患者心理層面上一些負面情緒的緩解，筆者選用剝奪成本描述患者的心理創傷，同時用總剝奪成本衡量救援的時效性并提出了一個新模型.新模型為急救中心根據受災點內的重傷與輕傷患者的分布，給救援載具賦予不同的職能，急救車輛負責救助輕傷患者,直升機負責救助重傷患者，借此減少總剝奪成本.

2 算法設計

筆者構建的模型屬于帶時間窗限制的協同運輸路徑優化模型，是NP-hard問題，由于剝奪成本的相關函數并不完全屬于線性形式，所以筆者采用優化算法中的蟻群算法進行算例求解.蟻群算法可以作為一種并行算法，其根據螞蟻之間的信息素傳遞和增強最優路徑選擇[13-14]得出全局最優解.基本的蟻群算法流程如圖2所示.

圖2 基本的蟻群算法流程Fig.2 Basic ant colony algorithm flowchart

步驟1 初始化參數.例如螞蟻的數量m、迭代的次數Nc、受災點之間的距離dij、受災點i和j上殘留信息的相對重要性α，以及啟發式信息的重要程度β等.

步驟2 構造解集空間.在N個受災點中隨機分配不同的螞蟻個數，螞蟻h在運動過程中根據每條路徑上的信息素濃度決定移動方向，Pk,ij(t)表示在t時刻螞蟻k由受災點i轉移到受災點j的概率，公式[15]為

其中:Nh,j為螞蟻h還未經過的受災點的集合；τij為受災點i與受災點j之間的信息素濃度；ηij為能見度，表示從受災點i轉移到受災點j的啟發式信息，公式為

式中：λ表示的是因為地震災害所導致的道路路況信息，λ的值越大意味著道路受損的程度越大，則該路徑的ηij值越小.

螞蟻h到達下一個受災點后，馬上判斷是否超出自己的最大荷載量，如果滿足條件則會接著遍歷剩余的受災點然后轉步驟3，否則，螞蟻會重新根據轉移概率規則重新篩選接下來需要訪問的受災點.

步驟3 計算各螞蟻的目標函數值.判斷約束條件，將不滿足約束條件解集中的路徑行駛時間設置為一個最大值.

步驟4 按照更新規則修改軌跡.交換路徑中的部分路線，如果交換后使得通行時間縮短，則更新可行解.

步驟5 更新信息素濃度.螞蟻在完成一次遍歷后，按照相應的規則將各路徑的信息素濃度進行更新.

τij(t+1)=(1-ρ)τij(t)+Δτij.

其中:ρ為信息素τij(t)表示為隨時間流逝而減弱的程度，ρ∈(0,1);Δτij為信息素增量.

步驟6 判斷是否結束.如果循環次數Nc<預定的最大迭代次數，則Nc+1且轉到步驟2，否則終止運算，輸出最優解.

3 算例分析

實驗使用Windows10,4 GB內存，intel 四核2.20 GHz處理器，算法在Pycharm 2021.1版本中進行求解操作.蟻群算法具有一定的正反饋機制，所以相比于遺傳算法和蜂群算法等優化算法，蟻群算法求解所耗時間為23 s左右，而遺傳算法和蜂群算法耗時分別為58 s和67 s左右才完成算例求解.

表1為救災運輸工具信息，因地震過后道路受損的原因，急救車的行駛速度受衰減系數影響，部分地區的時速可能降至20 km/h，所以采用加和平均方式得出急救車的平均時速，而直升機的時速受粉塵影響，時速也有所降低.

表1 救災運輸工具信息Table 1 Disaster relief transportation information

表2為受災點信息.通過搜索受災點與急救中心距離的遠近，重傷患者人數，重傷患者的總剝奪成本和道路受損情況等指標性數據，綜合采用層次性分析定義受災點災害等級，在短時間內整理災害情況，得出災害點的受災傷情評估值，其中災害等級為1表示受災害影響較小，災害等級為2表示受災害影響一般，災害等級為3表示受災害影響中等，災害等級為4表示受災害影響最大，并且根據本文定義的數據模型對模型參數進行合理地設置，將有關數據列于表2.

表2 受災點信息Table 2 Information of disaster site

基于上述的算例場景分析和模型參數得出的最優解救援路徑，及其與傳統應急策略(基于距離和基于時間的協同應急策略)進行對比，討論在為載具劃分不同職能下新模型的適用性和有效性.傳統應急策略與新應急策略(基于載具職能劃分的應急救援策略)的比較信息見表3.在載具數量相同的情況下比較傳統應急策略和基于職能劃分的協同應急策略，不難發現由于給予載具不同的職能使路徑地劃分有了明顯的區分，新應急策略中急救車現需要負責5條路徑上的22個受災點，因為只需要負責救助輕傷人群，所以能夠救助的輕傷人群也得以增加，在符合時間窗的前提下可以接收5個受災點的輕傷患者，相應地也使輕傷患者的心理創傷差異值減少.在初期救援不考慮成本的前提下，直升機負責救助重傷患者，使重傷患者的等待時長下降到了8.89 h，從而極大地降低了總剝奪成本.

表3 傳統應急策略與新應急策略的比較Table 3 Comparison between traditional emergency strategies and new emergency strategies

通過表3的比較可知：新策略的行駛路徑總長度遠大于傳統應急策略，這意味著油耗成本增加，所以在救援初期為了達到減少重傷患者的總等待時間和總剝奪成本的目的，應該適當地降低經濟成本的優先級以保障救援的順利實施.如果重傷患者數量較少的情況下，可以優先考慮傳統應急策略，重傷患者數量超過一定數目時，傳統策略會由于重視時間成本和經濟成本而導致剝奪成本的優先級下降，最終導致高剝奪成本.

再比較本文所討論的相關決策目標值，在新策略的劃分下，急救車和直升機所負責的受災點數目適度地增加，所以總救援時長增加到20.63 h.由表3可知第一決策目標總剝奪成本下降到了14 053元，究其原因是急救車的荷載量有限，傳統模型在道路受損的條件下，對救援途中的輕傷患者和重傷患者都進行救助，雖然在傳統模型的救援過程中救援時長并沒有超過傷員的在途可堅持時長，但其等待車輛到達進行救助的時長也許會需要更多的時間，或者是在運輸途中經歷的在途運輸時長可能或多或少地延長一定的時間，而且患者的總剝奪成本函數在第一和第三階段是成指數型增長，每超過1 min患者的總剝奪成本都會翻倍增長，導致極大地增加患者的剝奪成本，所以在劃分了載具職能的協同應急策略中，由直升機負責重傷患者的救助，最小化了患者在第一階段和第三階段的剝奪成本.

4 結 論

基于“多受災點”、“多救援工具”的災害場景中，筆者分析了在地震災情后的協同救援問題，在載具的運力受限和地形的通行約束等條件下，筆者將總剝奪成本作為第一目標、總等待時長作為第二目標，制定了基于載具職能劃分的救援路線，在不超出傷員在途可堅持時長的條件下使得患者的總剝奪成本達到最小化，能夠在短時間內制定“直升機+車輛”的協同救援策略，為決策者在地震災害發生后提供載具協同救援方案.

在傳統的救援決策中，研究人員重視救援成本和救援效率，很少有研究者討論關于患者的心理創傷差異性以及患者的剝奪成本，筆者認為在考慮效率和公平的前提下，可適當地考慮患者的心理痛苦，從而加強救援的公平性.未來的研究將著重思考如何為直升機的救援提供幫助，因為直升機的起飛降落，以及處理傷員的時間在救援時長中的占比較多，所以可以選擇一個地理位置合適的受災點作為直升機和傷員的移交中轉站，以此來縮短這個階段所占時間.