應急救援資源最短路徑配送方法

曲　娜, 王　瀟, 胡衛(wèi)建, 曲　芳, 苗于惠

(1. 沈陽航空航天大學 安全工程學院, 遼寧 沈陽　110136;

2. 中國地震應急搜救中心, 北京　100049)

?

應急救援資源最短路徑配送方法

曲娜1, 王瀟1, 胡衛(wèi)建2, 曲芳1, 苗于惠1

(1. 沈陽航空航天大學 安全工程學院, 遼寧 沈陽110136;

2. 中國地震應急搜救中心, 北京100049)

摘要:研究了應急救援物資配送理論及模型,探討了應急物資配送途徑和方式.認為突發(fā)性災害事件往往會造成重大的人員傷亡和財產損失,嚴重威脅著人類的生存和發(fā)展;應急救援資源配送直接關系到能否有效對各種突發(fā)性災害事件進行控制,進而使損失最小化;提高應急物資配送管理水平,對進一步完善和優(yōu)化應急救援資源的配送模式具有重要的理論意義和實踐價值.

關鍵詞:應急救援資源; 配送模型; 動態(tài)規(guī)劃法; 最小路徑

1研究的背景及意義

我國幅員遼闊、人口眾多, 是受自然災害影響最嚴重的國家之一.災害種類多、發(fā)生頻度高、區(qū)域性和季節(jié)性很強. 特別是近些年, 自然災害頻發(fā), 如2008年發(fā)生的冰凍災害, 南方多個城市的交通系統(tǒng)接近癱瘓, 造成重大的經濟損失; 四川汶川地震也給人民生命和財產帶來了巨大的損失. 國外近些年來也發(fā)生了很多嚴重的災難事故, 如卡特里那颶風、印度洋地震海嘯、日本地震及核泄漏等均帶來了重大的人員傷亡和財產損失. 面對如此嚴峻的形勢, 為維護社會秩序穩(wěn)定, 保持經濟健康發(fā)展, 提高災害應急搶險救援能力已經成為國家政府工作的重中之重.

如何進行防災減災成為擺在人們面前亟待解決的問題.相關研究人員開始設計并制定突發(fā)災害下的防災減災應急預案,保證災后能夠第一時間展開救援行動,盡可能地減少受災損失并保障人民的生命財產安全.在應急救援過程中,路徑的選取是一關鍵環(huán)節(jié),科學優(yōu)化救援路徑可以有效地減少抵達事故區(qū)域的時間,提高應急救援的效率,有效避免因盲目選取應急措施導致的救援任務延誤和資源浪費.

2研究現(xiàn)狀

對于路徑選擇,國內外的學者們進行了大量的研究.總體上,主要集中在路段權值的確定、構建數學模型以及設計相應的算法方面,通過計算機仿真模擬和數學建模的方法來實現(xiàn).

Victor J.Blue等針對多目標的路徑選擇問題,提出了基于雙目標模型的車輛路徑搜索算法,并給出了相應的算例,通過計算機模擬的方法,提出車輛在出行前的路徑選擇策略[1].Zhihong等人針對突發(fā)災害下的應急救援,提出把應急救援問題分成兩階段來考慮,即計劃階段和操作階段[2].Bard等人針對地震災害,分析了震后城市交通系統(tǒng)的需求變化和路網的損壞程度,通過應用蒙特卡羅模擬算法,解決了在路徑選擇中應用非線性效用函數獲得最短路徑的問題[3].Arun Jotshi等人在應急救援信息及時準確的情況下,提出應用計算機仿真的方法對應急救援車輛最短救援路徑進行模擬[4].我國對車輛路徑問題的研究在20世紀90年代才逐漸開始[5],與國外相比處于落后階段.我國理論界多關注車輛路徑問題的解決方法,主要集中在啟發(fā)式算法上,如對各種啟發(fā)式算法進行改進以及對不同的VRP問題進行算法設計等,已經取得了比較顯著的成果.

張杰等針對應急車輛的救援路徑優(yōu)化問題,分析了突發(fā)事件時路段運行時間的均值、方差和阻斷概率對路徑的影響,結合路徑行程時間可靠性、路徑阻斷風險,以及路徑復雜性等因素,提出了應急救援路徑選擇的多目標規(guī)劃模型,并采用多目標遺傳算法對模型求解[6].鐘志新等結合路網的連通可靠性與k最短路徑,將連通可靠性和運輸效率作為目標函數,建立了應急車輛運輸路徑選擇雙層規(guī)劃模型,該模型重點考慮了在應急救援過程中的效率及安全性問題[7].劉楊、云美萍和彭國雄等重點針對城市應急救援車輛路徑選擇優(yōu)化問題,綜合考慮了道路通行的可靠性、安全性、道路條件限制等,并將最小化行程時間以及最大化行程時間可靠度作為目標函數,建立了應急車輛路徑選擇的多目標規(guī)劃模型[8].徐寅峰等針對方格路網上道路堵塞的位置和數量信息不完全的情形,研究了兩輛應急救援車的在線路徑選擇問題,使得最多有k條邊堵塞時,至少一輛車盡快到達事故點進行救援.

3問題的提出

應急救援的根本宗旨是在最短時間內完成指定救援工作,所以,時間為第一約束條件.假設每一條路徑上的運輸容量滿足該條路徑上配送物資的最大需求量,同時假設有一受災點E,A表示配送中心,考慮如何選取從配送中心A經城市B、C、D到達受災點E的最短路徑的方法,如圖1所示.其中,A到E之間的每個結點代表城市,由每個節(jié)點引出的路徑上的加權值表示各個城市間的距離.

圖1　城市應急救援路線圖

3.1問題分析與求解

在圖1中,A為起點,E為終點,從一條路徑的某一結點到下一路徑的某一結點,可以由階段初的城市名稱和階段末的城市名稱來確定,圖中用結點間的連線表征.同時可以將兩結點間的距離作為兩城市間的路程長度,標注在結點間的連線上.

整個城市的救援路徑可劃分為4個階段,用K=1, 2, 3, 4表示.其中,K=1表示第一階段:從A級結點到B級結點(B1,B2);K=2表示第二階段:從B級結點(B1,B2)到C級結點(C1,C2);K=3表示第三階段:從C級結點(C1,C2)到D級結點(D1,D2,D3);K=4表示第四階段:從D級結點(D1,D2,D3)到E級結點.顯然,每兩個結點間的距離是一定的,用d(i,j)表示,且d(i,j)=d(j,i).因此,可以將從配送中心A經城市B、城市C、城市D到達城市E的最短路徑問題轉化為從階段1的結點A至階段4的結點E的最短路徑求解問題.

動態(tài)規(guī)劃算法能夠有效地求解上述多階段最優(yōu)決策過程問題,按照求解的方向可分為:順序遞推法和逆序遞推法.針對上述問題,在起始點A、目標點E恒定的條件下,最短路徑解是唯一的,因此順序遞推法和逆序遞推法的解是相同的.本文將采用順序遞推法求解應急資源最小路徑配送問題.

3.2順序遞推法

考慮第一個階段,即當K=1時,最短路程記作f1(Bi), i=1, 2.其中,f1(B1)=50, f1(B2)=80.

聯(lián)合考慮前兩個階段,即當K=2時.第一階段與第二階段的最短路程之和記為f2(Ci),i=1, 2.其中,f2(C1)=min{d(B1,C1)+f1(B1),d(B2,C2)+f1(B2)}=min{20+50, 10+80}=70,即從A結點至C1結點最短路徑為A-B1-C1;f2(C2)=min{d(B1, C2) +f1(B1), d(B1,C2)+f1(B2)}=min{30+50,20+80}=80, 即從A結點至C2結點最短路徑為A-B1-C2.

聯(lián)合考慮前三個階段,即當K=3時,前三個階段的最短路程記為f3(Di),i=1, 2, 3.其中,f3(D1)=min{d(C1, D1)+f2(C1), d(C2, D1)+f2(C2)}=min{80+70, 40+80}=120,即從A結點至D1結點最短路徑為A-B1-C1-D1;f3(D2)=min{d(C1, D2)+f2(C1), d(C1, D2)+f2(C3)}=min{70+70,20+80}=100,即從A結點至D2結點最短路徑A-B1-C2-D2;f3(D3)=min{d(C1, D3)+f2(C1), d(C2, D3)+f2(C3)}=min{80+70, 40+80}=120,即從A結點至D3結點最短路徑為A-B1-C2-D3.

聯(lián)合考慮前四個階段,即K=4時,前四個階段的最短路程記作f4(E),f4(E)=min{d(D1, E)+f3(D1), d(D2, E)+f3(D2), d(D3, E)+f3(D3)}=min{40+120, 80+100, 30+120}=150, 即從A到E的最短路徑為A-B1-C2-D3-E.也就是說,從城市A經B1、C2、D3至城市E為最短應急救援路徑.

4結論

突發(fā)災害發(fā)生后,應急救援管理人員希望快速、安全地選擇應急救援路徑,這對于防災減災具有重要意義.本文就是從這個角度出發(fā),根據國內外在應急救援路徑選擇方面的研究現(xiàn)狀,考慮了怎樣選擇最小應急救援路徑的問題.在應急救援過程中,以時間為主要約束目標,應用動態(tài)規(guī)劃方法,建立解決該類問題的數學模型并進行求解,獲得了唯一的最優(yōu)路徑.

在未來的研究工作中,將考慮更加實際和復雜的情況,如中間結點的城市更多、路線的距離不同且難易程度不同、多個起點和多個終點等,在那種情況下怎樣采用動態(tài)規(guī)劃方法或者近似動態(tài)規(guī)劃方法進行建模和求解.

參考文獻:

[1]BLUEVJ,ADLERJL.Real-timemulti-objectivepathssearchforin-vehiclerouteguidancesystems[J].TransportationResearchRecord, 1997,40(16):10-17.

[2] SHEN Z H, DESSOUKY M, Ordóńez F. The stochastic vehicle routing problem for large-scale emergencies[Z]. Ise Working Paper. 2007:1-33.

[3] BARD J F, BENNETT J E. Arc reduction and path preference in stochastic acyclic networks[J]. Management Science, 1991,37(2):195-215.

[4] JOTSHI A, GONG Q, BATTA R. Dispatching and routing of emergency vehicles in disaster mitigation using data fusion[J]. Socio-Economic Planning Sciences, 2009,43(1):1-24.

[5] 史玉敏. 物流配送環(huán)節(jié)中車輛路徑問題(VRP)的研究[D]. 濟南:山東師范大學, 2007:3-6.

(SHI Y M. Research on vehicle routing problems in logistics distribution[D]. Jinan: Shandong Normal University, 2007:3-6.)

[6] 張杰,王志勇,許維勝,等. 突發(fā)事件下應急救援路徑選擇模型的構建和求解[J]. 計算機應用研究, 2011,28(4):1311-1314.

(ZHANG J, WANG Z Y, XU W S, et al. Model and solution of rescue path selection in emergency[J]. Application Research of Computers, 2011,28(4):1311-1314.)

[7] 鐘志新,薛茂炎,黃武國. 災害情況下應急運輸路徑選擇問題研究[J].公路與汽運, 2010(4):37-40.

(ZHONG Z X, XUE M Y, HUANG W G. Research on route choice of emergency transportation in disaster situations[J]. Highways & Automotive Applications, 2010(4):37-40.)

[8] 劉楊,云美萍,彭國雄. 應急車輛出行前救援路徑選擇的多目標規(guī)劃模型[J]. 公路交通科技, 2009,26(8):135-139.

(LIU Y, YUN M P, PENG G X. A multi-objective programming model of route choice of emergency vehicles before travel[J]. Journal of Highway and Transportation Research and Development, 2009,26(8):135-139.)

【責任編輯: 祝穎】

Dispatching Approaches of Shortest Path for Emergency Rescue Resource

QuNa1,WangXiao1,HuWeijian2,QuFang1,MiaoYuhui1

(1. School of Safety Engineering, Shenyang Aerospace University, Shenyang 110136, China; 2. National Earthquake Response Support Service, Beijing 100049, China)

Abstract:The dispatching theory and model of emergency rescue resource are studied. It considers that the disaster incidents tend to cause significant casualties and property losses, which is threatening the human survival and development. The dispatching of emergency rescue resources is directly related to the effective response for disaster incidents, and further the losses are minimized. Therefore, researching the dispatching model and theory of emergency resource, exploring the resource dispatching paths and modes as well as improving management level of emergency resources dispatching have important significance in theory and practice for perfecting and optimizing the dispatching model of emergency resources.

Key words:emergency resources; dispatching model; dynamic programming method; shortest path

中圖分類號:TU 984.116

文獻標志碼:A

文章編號:2095-5456(2016)01-0030-03

作者簡介:曲娜(1979-),女,遼寧大石橋人,沈陽航空航天大學講師,博士研究生.

基金項目:國家科技支撐計劃(2013BAK03B01).

收稿日期:2015-08-03