应急救援资源最短路径配送方法

曲　娜, 王　潇, 胡卫建, 曲　芳, 苗于惠

(1. 沈阳航空航天大学 安全工程学院, 辽宁 沈阳　110136;

2. 中国地震应急搜救中心, 北京　100049)



应急救援资源最短路径配送方法

曲娜1, 王潇1, 胡卫建2, 曲芳1, 苗于惠1

(1. 沈阳航空航天大学 安全工程学院, 辽宁 沈阳110136;

2. 中国地震应急搜救中心, 北京100049)

摘要:研究了应急救援物资配送理论及模型,探讨了应急物资配送途径和方式.认为突发性灾害事件往往会造成重大的人员伤亡和财产损失,严重威胁着人类的生存和发展;应急救援资源配送直接关系到能否有效对各种突发性灾害事件进行控制,进而使损失最小化;提高应急物资配送管理水平,对进一步完善和优化应急救援资源的配送模式具有重要的理论意义和实践价值.

关键词:应急救援资源; 配送模型; 动态规划法; 最小路径

1研究的背景及意义

我国幅员辽阔、人口众多, 是受自然灾害影响最严重的国家之一.灾害种类多、发生频度高、区域性和季节性很强. 特别是近些年, 自然灾害频发, 如2008年发生的冰冻灾害, 南方多个城市的交通系统接近瘫痪, 造成重大的经济损失; 四川汶川地震也给人民生命和财产带来了巨大的损失. 国外近些年来也发生了很多严重的灾难事故, 如卡特里那飓风、印度洋地震海啸、日本地震及核泄漏等均带来了重大的人员伤亡和财产损失. 面对如此严峻的形势, 为维护社会秩序稳定, 保持经济健康发展, 提高灾害应急抢险救援能力已经成为国家政府工作的重中之重.

如何进行防灾减灾成为摆在人们面前亟待解决的问题.相关研究人员开始设计并制定突发灾害下的防灾减灾应急预案,保证灾后能够第一时间展开救援行动,尽可能地减少受灾损失并保障人民的生命财产安全.在应急救援过程中,路径的选取是一关键环节,科学优化救援路径可以有效地减少抵达事故区域的时间,提高应急救援的效率,有效避免因盲目选取应急措施导致的救援任务延误和资源浪费.

2研究现状

对于路径选择,国内外的学者们进行了大量的研究.总体上,主要集中在路段权值的确定、构建数学模型以及设计相应的算法方面,通过计算机仿真模拟和数学建模的方法来实现.

Victor J.Blue等针对多目标的路径选择问题,提出了基于双目标模型的车辆路径搜索算法,并给出了相应的算例,通过计算机模拟的方法,提出车辆在出行前的路径选择策略[1].Zhihong等人针对突发灾害下的应急救援,提出把应急救援问题分成两阶段来考虑,即计划阶段和操作阶段[2].Bard等人针对地震灾害,分析了震后城市交通系统的需求变化和路网的损坏程度,通过应用蒙特卡罗模拟算法,解决了在路径选择中应用非线性效用函数获得最短路径的问题[3].Arun Jotshi等人在应急救援信息及时准确的情况下,提出应用计算机仿真的方法对应急救援车辆最短救援路径进行模拟[4].我国对车辆路径问题的研究在20世纪90年代才逐渐开始[5],与国外相比处于落后阶段.我国理论界多关注车辆路径问题的解决方法,主要集中在启发式算法上,如对各种启发式算法进行改进以及对不同的VRP问题进行算法设计等,已经取得了比较显著的成果.

张杰等针对应急车辆的救援路径优化问题,分析了突发事件时路段运行时间的均值、方差和阻断概率对路径的影响,结合路径行程时间可靠性、路径阻断风险,以及路径复杂性等因素,提出了应急救援路径选择的多目标规划模型,并采用多目标遗传算法对模型求解[6].钟志新等结合路网的连通可靠性与k最短路径,将连通可靠性和运输效率作为目标函数,建立了应急车辆运输路径选择双层规划模型,该模型重点考虑了在应急救援过程中的效率及安全性问题[7].刘杨、云美萍和彭国雄等重点针对城市应急救援车辆路径选择优化问题,综合考虑了道路通行的可靠性、安全性、道路条件限制等,并将最小化行程时间以及最大化行程时间可靠度作为目标函数,建立了应急车辆路径选择的多目标规划模型[8].徐寅峰等针对方格路网上道路堵塞的位置和数量信息不完全的情形,研究了两辆应急救援车的在线路径选择问题,使得最多有k条边堵塞时,至少一辆车尽快到达事故点进行救援.

3问题的提出

应急救援的根本宗旨是在最短时间内完成指定救援工作,所以,时间为第一约束条件.假设每一条路径上的运输容量满足该条路径上配送物资的最大需求量,同时假设有一受灾点E,A表示配送中心,考虑如何选取从配送中心A经城市B、C、D到达受灾点E的最短路径的方法,如图1所示.其中,A到E之间的每个结点代表城市,由每个节点引出的路径上的加权值表示各个城市间的距离.

图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的最短路径求解问题.

动态规划算法能够有效地求解上述多阶段最优决策过程问题,按照求解的方向可分为:顺序递推法和逆序递推法.针对上述问题,在起始点A、目标点E恒定的条件下,最短路径解是唯一的,因此顺序递推法和逆序递推法的解是相同的.本文将采用顺序递推法求解应急资源最小路径配送问题.

3.2顺序递推法

考虑第一个阶段,即当K=1时,最短路程记作f1(Bi), i=1, 2.其中,f1(B1)=50, f1(B2)=80.

联合考虑前两个阶段,即当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.

联合考虑前三个阶段,即当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.

联合考虑前四个阶段,即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结论

突发灾害发生后,应急救援管理人员希望快速、安全地选择应急救援路径,这对于防灾减灾具有重要意义.本文就是从这个角度出发,根据国内外在应急救援路径选择方面的研究现状,考虑了怎样选择最小应急救援路径的问题.在应急救援过程中,以时间为主要约束目标,应用动态规划方法,建立解决该类问题的数学模型并进行求解,获得了唯一的最优路径.

在未来的研究工作中,将考虑更加实际和复杂的情况,如中间结点的城市更多、路线的距离不同且难易程度不同、多个起点和多个终点等,在那种情况下怎样采用动态规划方法或者近似动态规划方法进行建模和求解.

参考文献:

[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] 史玉敏. 物流配送环节中车辆路径问题(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] 张杰,王志勇,许维胜,等. 突发事件下应急救援路径选择模型的构建和求解[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] 刘杨,云美萍,彭国雄. 应急车辆出行前救援路径选择的多目标规划模型[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