不确定环境下的地震应急救援路径优化研究

不确定环境下的地震应急救援路径优化研究-工程论文不确定环境下的地震应急救援路径优化研究 程国萍 CHENG Guo-ping；陈德旭 CHEN De-xu；关贤军 GUAN Xian-jun （同济大学经济与管理学院，上海 200092） 摘要：针对地震应急救援的特点，引入不确定理论，在地震灾害的背景下，研究震后动态网络环境下的应急救援路径选择问题。用不确定变量表示网络中各路段的破坏程度，综合考虑路径破坏程度及车辆路径连续性等约束条件，以救援时间最短为目标，基于不确定理论建立了动态优化模型，并用改进的遗传算法求解，最后设计算例验证了模型和算法的有效性。 关键词：地震应急救援；不确定理论；车辆路径问题；遗传算法 中图分类号：P315.9 文献标识码：A 文章编号：1006-4311（2015）17-0175-04 基金项目：国家自然科学基金（71272047）；浦江人才计划（13PJC100）。 作者简介：程国萍（1964-），女，上海人，博士，副研究员，研究方向为战略管理和公共关系；陈德旭（通讯作者）（1991-），男，吉林白山人，硕士生，研究方向为应急管理；关贤军（1972-），男，湖北仙桃人，博士，副教授，研究方向为应急管理和工程管理。 0 引言 地震是最严重的自然灾害之一。地震作为一种常见的重大突发事件，其具有突发性、不确定性、巨大破坏性、连锁性等特点。然而近年来地震等自然灾害频发，且有逐年上升的趋势。1-2唐山地震、汶川地震、印度洋地震、玉树地震、海地地震、雅安地震都造成了交通系统的破坏以及无数的生命财产损失。 地震一旦发生，灾区会有大量的人员伤亡，在短时间内有爆炸性的应急物资需求，但同时交通运输系统也会遭到一定程度的破坏。如果通往灾区的道路中断,救援队伍不能及时到达灾区,就会给震后救援和疏散带来很大的困难。3-6所以，应急救援物资的运输是救援工作的重中之重,而应急救援物资运输车辆的调度问题是确保这一项工作顺利进行的关键。 动态车辆路径问题（Dynamic Vihicle Routing Problem，简称DVRP）是运筹学领域的热门问题，但应急物流中的DVRP问题研究还不够成熟7-13 。在Sascha Wohlgemuth，Richard Oloruntoba，Uwe Clausen14的研究中，当每个点既有可能成为出救点、又有可能成为受灾点时，以延迟时间最小和系统利用率最高为目标，建立了多阶段整数规划模型解决了随机需求的情况。Min Wena，Jean-Franc-ois Cordeau，Gilbert Laporte，Jesper Larsen15研究了在多时段情况下，一个车场配送多个客户的问题，客户需求和服务时段都是动态的，并以最小化运送费用和客户等待时间为目标，通过整数线性规划得出最优解。李妍峰，高自友，李军16研究了实时交通信息条件下的城市动态网络车辆路径优化问题，考虑了常发性交通拥堵和偶发性交通拥堵两种情况，最后提出了一套初始路线安排和实时路线调整的规划方法。马祖军，胡萍17设计了一种实时、时变交通信息的结合策略，以救援时间最短为目标，利用虚拟处救点和滚动时域策略建立了CERFSVRP模型，通过改进后的遗传算法进行求解。 但以上学者并未对动态网络中路段的不确定性进行深入研究，而地震中的交通网络可能随时会受到破坏，因此整个网络具有非常大的不确定性，且每条线路发生破坏的概率及程度无法通过历史数据获得，所以不能用常规的随机或者模糊方法来处理，在此我们引入不确定理论来处理此问题。Liu18-20在2007年创立了不确定理论，之后大量的学者加入了研究，时至今日，不确定理论已经成为一个完整的数学系统，并应用到物流、金融、网络、数据挖掘和控制等一系列领域。当我们无法拥有充足的样本和历史数据，甚至连观测数据都暂时无法获得时，就不能应用概率论，不得不邀请该领域的专家给出他们对事件发生的信度，进而得出信度函数及其分布，应用不确定理论处理问题。本文将拟研究单出救点、单受灾点的网络布局，用不确定变量来刻画每条路段受灾后的破坏程度，研究不确定条件下的网络动态规划。 1 不确定理论 不确定理论由Liu18-20于2007年提出，其目的旨在解决不确定问题。不确定测度是不确定理论的基础，该理论是具有规范性、自对偶性、单调性、次可加性和乘积测度公理的数学系统。不确定理论已经发展为数学的一个分支，是研究不确定问题的强大数学工具。不确定理论在国内外专家学者的共同推动下飞速发展，在理论研究和应用研究上取得了一定的成就。 由Liu在18-20中提出： 1.1 不确定测度 1.2 不确定变量 定义1.2：若是从不确定空间（，M）到实数集R的可测函数，若对任意Borel集B，集合B=（）B是一个事件，则称是（，M）上的不确定变量。 1.3 不确定分布 定义1.3：设是不确定空间（，M）上的不确定变量，若对?坌xR满足（x）=M?燮x，则称是的不确定分布。 2 问题描述 将地震救援应急网络抽象为有向网络图G=（N，E），N代表网络中点的集合，E代表网络中弧的集合。网络中只存在一个出救点和一个受灾点，均用三角代表；其余点皆为路径中的节点，均用圆形代表；且路径由各个节点之间的路段组成。出救点处有足够的资源和车辆，且车型相同，网络整体受破坏程度未知。如图1，需要解决的问题是：当受灾点发生地震时，在每条路段的受破坏程度未知时，如何选择一条合适的路径，使应急救援资源以最短的时间从出救点运送到受灾点。 动态网络与静态网络的区别在于：静态网络在车辆行驶前就可以求出最优路径，而动态网络在车辆每行驶到下一个节点之前，都要根据当前路段情况重新做出决策。显然路段的破坏程度无法由历史数据获得，且没有充分的样本数据，但我们可以通过卫星通信和地理信息系统功能，对车辆行驶情况和网络中路段的破坏程度进行观测，由该领域专家对每个路段当前的破坏程度进行估计，通过导航系统把当前信息传达给司机，从而指导车辆的路线选择决策，提高车辆行驶效率。 行驶方案如下：车辆从出救点出发，每当车辆距离下一个节点还有t时间时（令t=30min），更新下一个节点相连的所有可能路段的信息，并由专家依据当前观测数据，对破坏程度进行估计，给出破坏程度信度，据此对路径规划方案作出动态调整。 3 模型建立 3.1 模型假设 出救点所存放资源可以满足受灾点的需求，且车辆储备充足，车型一致； 车辆（或车队）运送一次可以满足受灾点的需求，运送完毕后不返回出救点； 鉴于应急情况下对时效性要求较高，同时避免资源浪费，每个受灾点只能由一辆车服务，且每辆车只能服务一个受灾点。 3.2 参数说明 救援的目标是物资以最短时间到达受灾点： 表示目标函数为期望时间最小； 表示在每一个节点，只能选择1条路段继续行驶； 保证路径中没有回路出现； 规定了决策变量的取值范围和参数m、n的取值范围。 4 模型求解 不确定VRP问题是一个NP-hard问题，用传统的精确算法无法求出最优解，考虑到本问题需要对路径选择做出动态调整，具有一定的复杂性，所以本文采用比较成熟的遗传算法，并针对模型对交叉和变异算子做出相应的改变，合理规避非可行解和回路情况出现，在动态网络中求出时间最短路径。 4.1 遗传编码与种群初始化 本文采用一维向量作为解的表示方式。在网络图G=（N，E）中，从1到n的路径经过的节点个数是一样的，所以每条染色体的长度是一样的，令每条染色体Ck（1?燮k?燮R）（D1，D2，Dn-1，Dn）表示一条从起点到终点且不含环路的路径。设种群初始规模为R，即随机生成R条从1到n的路径，保证种群的多样性。 4.2 适应度函数和选择操作 适应度函数是遗传算法中的重要选择机制，以染色体适应度值的大小来决定染色体是否传到下一代。令fk=t（Ck），1?燮k?燮R，即适应度值等于每条染色体所代表路径的时间，适应度值越小时间就越小，解就更优。采用精英保留策略进行操作。 4.3 交叉操作 给定一个交叉概率pc，随机产生一个数r0，1，若r?燮pc，进行交叉操作；否则，不进行。 在此问题中，由于每条染色体的长度相同，单点交叉不会出现回路的情况，所以采用单点交叉的策略。如图2，具体步骤为： 对任意两条父代染色体，随机选择D4作为交叉点， 通过单点交叉产生两个新个体。 4.4 变异操作 给定一个交叉概率pm，随机产生一个数r0，1，若r?燮pm，进行交叉操作；否则，不进行。 在此问题中，由于每条染色体的长度相同，变异也不会出现回路的情况。如图3，具体步骤如下： 各条染色体起始点相同，对任意父代染色体，随机选出除了起始点1和终点n的基因D2进行变异，D2可由节点2变成节点3，4。 通过变异产生新个体。 4.5 终止条件 设最大迭代次数W，迭代W次后结束。 5 算例分析 应急救援网络如图1，共有16个节点，其中1为出救点，16为受灾点，网络参数图如表1所示。设置参数：更新时间t=30min，种群大小R=30，交叉概率pc=0.8，变异概率pm=0.2，最大迭代次数W=100。 网络如图1所示。 采用MatlabR2012a对上述算法进行编程，在Intel（R） Core（TM） i5-4200U CPU 1.60GHZ，内存6.00GB的计算机上对其进行求解，用九九法对不确定变量进行模拟，计算时间7.09S，得到最优路径为（1259111516），全部用时为72.015h，如表2所示。 从上述结果可以看出，地震应急救援是一个动态的过程，交通网络的破坏程度往往成为决定运送效率的关键，我们通过不确定变量来刻画当前交通网络的运行状况，通过模拟的方式得出最佳路线，并以此来帮助决策者指导应急救援。 6 结论 本文以地震应急救援为背景，指出应急救援是一个动态过程，并重点考虑了震后交通网络的破坏程度，在没有历史数据可以参考、样本完全未知的情况下，创新地用不确定变量来描述路段的破坏程度，建立了一个出救点到一个受灾点的规划模型，并设计了改进的遗传算法来求解该模型。算例分析结果表明，该模型可以有效快速地解决震后环境下应急动态网络的最短时路径选择问题，为决策者的地震救援路径规划提供了科学理论支持。 进一步的研究可能考虑多救点对多受灾点的情况，以及引进不确定随机变量来解决时变网络中更复杂的路径选择问题。 参考文献： 1冯蔚，李卫平，陈通，等.2012年全球地震灾害概要J.灾害学，2013，28（3）：133-137. 2张玮晶.特大地震灾害应急救援中理性战略的建立与实施J.灾害学，2014,29（4）：155-158. 3高娜，聂高众，邓砚.地震应急救援辐射效应分析以芦山7.0级地震为例J.灾害学，2014，29（2）：170-174. 4张杰，王志勇，许维胜，等.突发事件下应急救援路径选择模型的构建和求解J.计算机应用研究，2008，4（28）：1311-1314. 5王绍仁，马祖军.震害紧急响应阶段应急物流系统中的LRPJ.系统工程理论与实践，2011，31（8）：1497-1507. 6郭晓光.面向自然灾害的应急物流网络规划与运作研究D.北京，北京交通大学，2013. 7Ali Haghania, Soojung Jung. A dynamic vehicle routing problem with time-dependent travel timesJ. Computers Operations Research，32（2005）：2959-2986. 8Francesco Ferrucci ,Stefan Bock ,Michel Gendreau.A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goodsJ. European Journal of Operational Research，225 （2013）：130-141. 9Victor Pillac, Michel Gendreau, Christelle Guret, Andrs L. Medaglia. A review of dynamic vehicle routing problemsJ. European Journal of Operational Research，225 （2013）：1-11. 10Jean-Yves Potvin ,Ying Xu, Ilham Benyahia. Vehicle routing and scheduling with dynamic travel timesJ.Computers Operations Research，33 （2006）：1129-1137. 11范文璟，马祖军.时变网络环境下城市应急救援路径优化J.计算机应用，2011,6（31）：125-128. 12魏航，魏洁.随机时变网络下的应急路径选择研究J.系统工程学报，2009，24（1）：99-103. 13魏航，刘璇.时变随机网络下基于成功和风险的应急路径选择研究J.管理工程学报，2010,24（2）：68-74. 14Sascha Wohlgemuth, Richard Oloruntoba, Uwe Clausen. Dynamic vehicle routing with anticipation in disaster reliefJ. So