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

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

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

?

應(yīng)急救援資源最短路徑配送方法

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

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

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

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

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

1研究的背景及意義

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

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

2研究現(xiàn)狀

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

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

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

3問題的提出

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

圖1　城市應(yīng)急救援路線圖

3.1問題分析與求解

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

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

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

3.2順序遞推法

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

聯(lián)合考慮前兩個階段,即當(dāng)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結(jié)點至C1結(jié)點最短路徑為A-B1-C1;f2(C2)=min{d(B1, C2) +f1(B1), d(B1,C2)+f1(B2)}=min{30+50,20+80}=80, 即從A結(jié)點至C2結(jié)點最短路徑為A-B1-C2.

聯(lián)合考慮前三個階段,即當(dāng)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結(jié)點至D1結(jié)點最短路徑為A-B1-C1-D1;f3(D2)=min{d(C1, D2)+f2(C1), d(C1, D2)+f2(C3)}=min{70+70,20+80}=100,即從A結(jié)點至D2結(jié)點最短路徑A-B1-C2-D2;f3(D3)=min{d(C1, D3)+f2(C1), d(C2, D3)+f2(C3)}=min{80+70, 40+80}=120,即從A結(jié)點至D3結(jié)點最短路徑為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經(jīng)B1、C2、D3至城市E為最短應(yīng)急救援路徑.

4結(jié)論

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

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

參考文獻(xiàn):

[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]. 濟(jì)南:山東師范大學(xué), 2007:3-6.

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

[6] 張杰,王志勇,許維勝,等. 突發(fā)事件下應(yīng)急救援路徑選擇模型的構(gòu)建和求解[J]. 計算機(jī)應(yīng)用研究, 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] 鐘志新,薛茂炎,黃武國. 災(zāi)害情況下應(yīng)急運輸路徑選擇問題研究[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] 劉楊,云美萍,彭國雄. 應(yīng)急車輛出行前救援路徑選擇的多目標(biāo)規(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.)

【責(zé)任編輯: 祝穎】

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

文獻(xiàn)標(biāo)志碼:A

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

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

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

收稿日期:2015-08-03