重大事故救灾路线双目标优化模型及算法

第36卷第4期 北京科技大学学报 Vol.36 No.4 2014年4月 Journal of University of Science and Technology Beijing Apr.2014 重大事故救灾路线双目标优化模型及算法 盖文妹2》，蒋仲安，邓云峰”，李竞》，杜焱” 1)北京科技大学土木与环境工程学院，北京1000832)国家行政学院，北京1000893)中国安全科学生产研究院，北京100012 ☒通信作者，E-mail:jzal963@263.met 摘要运用运筹学的理论和方法，建立一种重大事故救灾路线双目标优化数学模型.基于启发式算法思想，提出适合该模 型且收敛速度较快的优化算法.该算法通过构造辅助函数调用Dijkstr.算法，在最优解的近似区间内多次迭代逐渐逼近最优 解，实现了双权重网络图最短路的求解，是一种近似的、快速的算法.基于所构造辅助函数的性质，给出实现该算法的具体步 骤.对误差进行线性估计，分析了该算法收敛速度的影响因素，并讨论了算法的时间复杂度及优势.最后在案例分析中编译 并运行该算法，证实其模拟结果与理论分析结论相吻合 关键词矿山救援：路径规划：优化：启发式算法：数学模型 分类号X913.3 Bi-objective optimization model and algorithm of rescue routes during major accident time GAI Wen-mei),JIANG Zhong-un,DENG Yun-feng,LI Jing,DU Yan 1)School of Civil and Environmental Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Chinese Academy of Government,Beijing 100089,China 3)China Academy of Safety Science and Technology,Beijing 100012,China Corresponding author,E-mail:jzal963@263.net ABSTRACT A bi-objective optimization model of rescue routes was built by using the operations research theory.An algorithm which suites to solve the model and has rapid convergence rate was proposed on the basis of heuristic algorithms.This algorithm calls the Dijkstra algorithm by constructing auxiliary functions,gradually approach optimal solutions in the approximate range of optimal solutions by multiple iterations and finally obtain the shortest path of the double-weighted network,therefore it is a fast,approximate algorithm. The specific steps of the algorithm were listed by analyzing the nature of auxiliary functions.The error and influence factors on the convergence rate were analyzed,and the time complexity and the advantages of the algorithm were also discussed.Finally,the algorithm was compiled and implemented in a specific case,and the results are proved to be consistent with theoretical conclusions. KEY WORDS mine rescue;path planning:optimization:heuristic algorithms:mathematical models 近年来，因重大事故灾害对人类社会造成的 受灾群众的正常生活.因此研究最佳疏散路 损失不断加剧，如江西省新余市庙上煤矿“1·8”重 线、最佳救灾路线及救灾物资的最佳调度路线等 大火灾事故、重庆“12·23”天然气井喷事故、“5· 应急救援方案的优化问题，对确保最大限度地减 12”汶川特大地震均给国民经济和人民生命财产 轻事故灾害造成的损失及各项救灾装备及人力的 带来巨大损失.面对煤矿瓦斯爆炸、建筑物火灾及 有效运用有重要意义B-6 毒气泄漏等突发事故，需要将受灾人群疏散转移 以重大毒气泄漏事故中的最佳疏散路线为例， 至安全地带，或者向受灾地点运送救援物资，保证 含硫化氢天然气井一旦发生井喷失控事故，大量天 收稿日期：201302-12 基金项目：国家自然科学基金资助项目(71173198)：国家科技支撑计划资助项目(2012BAK03B05,2012BAK20B02) DOI:10.13374/j.issn1001-053x.2014.04.017:http://journals.ustb.edu.cn

第 36 卷 第 4 期 2014 年 4 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 4 Apr． 2014 重大事故救灾路线双目标优化模型及算法 盖文妹1，2) ，蒋仲安1) ，邓云峰2) ，李 竞3) ，杜 焱1) 1) 北京科技大学土木与环境工程学院，北京 100083 2) 国家行政学院，北京 100089 3) 中国安全科学生产研究院，北京 100012  通信作者，E-mail: jza1963@ 263． net 摘 要 运用运筹学的理论和方法，建立一种重大事故救灾路线双目标优化数学模型． 基于启发式算法思想，提出适合该模 型且收敛速度较快的优化算法． 该算法通过构造辅助函数调用 Dijkstra 算法，在最优解的近似区间内多次迭代逐渐逼近最优 解，实现了双权重网络图最短路的求解，是一种近似的、快速的算法． 基于所构造辅助函数的性质，给出实现该算法的具体步 骤． 对误差进行线性估计，分析了该算法收敛速度的影响因素，并讨论了算法的时间复杂度及优势． 最后在案例分析中编译 并运行该算法，证实其模拟结果与理论分析结论相吻合． 关键词 矿山救援; 路径规划; 优化; 启发式算法; 数学模型 分类号 X913. 3 Bi-objective optimization model and algorithm of rescue routes during major accident time GAI Wen-mei 1，2) ，JIANG Zhong-an1)  ，DENG Yun-feng2) ，LI Jing3) ，DU Yan1) 1) School of Civil and Environmental Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Chinese Academy of Government，Beijing 100089，China 3) China Academy of Safety Science and Technology，Beijing 100012，China  Corresponding author，E-mail: jza1963@ 263． net ABSTＲACT A bi-objective optimization model of rescue routes was built by using the operations research theory． An algorithm which suites to solve the model and has rapid convergence rate was proposed on the basis of heuristic algorithms． This algorithm calls the Dijkstra algorithm by constructing auxiliary functions，gradually approach optimal solutions in the approximate range of optimal solutions by multiple iterations and finally obtain the shortest path of the double-weighted network，therefore it is a fast，approximate algorithm． The specific steps of the algorithm were listed by analyzing the nature of auxiliary functions． The error and influence factors on the convergence rate were analyzed，and the time complexity and the advantages of the algorithm were also discussed． Finally，the algorithm was compiled and implemented in a specific case，and the results are proved to be consistent with theoretical conclusions． KEY WOＲDS mine rescue; path planning; optimization; heuristic algorithms; mathematical models 收稿日期: 2013--02--12 基金项目: 国家自然科学基金资助项目( 71173198) ; 国家科技支撑计划资助项目( 2012BAK03B05，2012BAK20B02) DOI: 10． 13374 /j． issn1001--053x． 2014． 04． 017; http: / /journals． ustb． edu． cn 近年来，因重大事故灾害对人类社会造成的 损失不断加剧，如江西省新余市庙上煤矿“1·8”重 大火灾事故、重庆“12·23”天然气井喷事故、“5· 12”汶川特大地震均给国民经济和人民生命财产 带来巨大损失． 面对煤矿瓦斯爆炸、建筑物火灾及 毒气泄漏等突发事故，需要将受灾人群疏散转移 至安全地带，或者向受灾地点运送救援物资，保证 受灾群众的正常生活［1--2］． 因此研究最佳疏散路 线、最佳救灾路线及救灾物资的最佳调度路线等 应急救援方案的优化问题，对确保最大限度地减 轻事故灾害造成的损失及各项救灾装备及人力的 有效运用有重要意义［3--6］． 以重大毒气泄漏事故中的最佳疏散路线为例， 含硫化氢天然气井一旦发生井喷失控事故，大量天

·536 北京科技大学学报 第36卷 然气泄漏至大气中形成含硫毒性云团，事故气井周 短路问题的研究现状进行分类和概括后指出，对于 边居民如不及时撤离而暴露于毒性云团中，会使呼 双目标最短路问题，通常的处理方法是对不同的目 吸道、皮肤和眼睛受到损伤，神经系统受抑制甚至引 标进行线性加权或是将某些目标转化为约束条件， 发死亡.特别是高含硫气井较一般气井井喷失控的 对于线性加权法而言，其权重的确定是一件很困难 可能性更大，加之我国天然气井很多地处山区地形， 的事情，而有约束的最短路问题已经被证明是NP 给事故后的人员疏散带来较大困难).复杂的地 完全问题，有时因为其算法复杂性太高而无法进行 形条件使得不同路段的受灾风险不同，为保证受灾 求解，显然无法满足应急救援中对优化方案快速求 人员及时和安全地疏散，有必要寻找一条最佳疏散 解的需要 路线0，既要保证疏散速度最快，又要保证路线上 本文提出了应急救援双目标优化搜索算法，以 的风险值在可接受范围之内. 满足应急救援中对两个目标同时优化及结果快速求 以矿井火灾中的最佳救灾路线为例，井下空间 解的需要，其基本思路是基于启发式近似算法，通过 狭小，矿井通风及巷道联通关系复杂，供风量有限， 构造辅助函数调用Dijkstra算法，将两个优化目标 矿井火灾产生的大量高温、有毒有害烟气在井下不 中的某一优化目标转化为约束条件，反复迭代求解 易散失，在巷道通风情况下高温、有毒有害烟流能随 构造权重的最短路来寻找另一优化目标的最小值， 风迅速传播到很远的范围，高温烟气在巷道中蔓延 不仅权重易于确定，而且能在较短时间内获得符合 遇到新鲜风流时，可能在渗风地点形成新的火源，而 误差限值的近似最优解 且矿井火灾还可能引起瓦斯和煤尘爆炸，因此有必 1问题描述及数学模型 要派遣救灾队伍辅助井下受灾人员逃生.救灾人员 佩戴氧气呼吸器及备用装置，并且经过专门的训练， 1.1重大事故救灾路线双目标优化问题的提出 可在具有一定条件的灾变烟流中通行，但由于氧气 为清晰地叙述本文所研究的应急救援双目标优 呼吸器供氧量有限，应估算救灾人员的需氧量以保 化问题，在此以应急救援优化问题之一一最佳救 证救灾人员的安全.因此在制定最佳救灾路线时， 灾路线问题进行描述.从图论角度来看，受灾区域 既要保证救灾速度最快，即所选救援道路的“当量 错综复杂的道路实际上是一个连接的网络图，道路 长度”最短，还要确保路线上的总耗氧量不能超过 为图的边，道路之间的交点抽象成图的点的集合，组 氧气呼吸装置中的可用氧气总量 成网络图的顶点：在无向网络图上赋予救灾路线选 以地质灾害中的救灾物资最佳调度路线为例， 择的影响因素，把灾区周边道路网络布局转化为图 我国疆域辽阔，地质环境复杂，地震、滑坡、泥石流等 的拓扑优化问题.作为图论的经典问题，最短路径 已成为对我国危害最大的地质灾害.尤其是近年 问题的定义是在一个赋权图的两个项点之间找出一 来，随着矿产资源开采及山区工程开发活动的增强， 条具有最小权值的路径 崩塌、滑坡、泥石流等地质灾害更为严重☒.为保 本文考虑的最佳救灾路线问题，除了主要的优 证灾后救灾物资车辆的高效运行，有必要选择一条 化目标外，还有次要优化目标，即限制条件.在此， 最佳的救灾物资调度路线-，既要实现救灾物资 根据图论的理论及方法，可将应急救援双目标优化 的运送时间最短，还要保证该路线的运输成本不超 问题描述为：对于网络G=(V,E),其中V(G)= 过经济承受能力， {:}为图G的节点集，任一顶点：∈V(G)对应于平 以上涉及的最佳疏散路线、最佳救灾路线及救 面内的点(x,y:);E(G)={ele=(up,v,）=（ug' 灾物资最佳调度路线等最佳应急救援方案的求解问 t,),p,U,∈)为图G的边集，|E1=n.,lul=n, 题均含有两个方面的优化目标，可以最终转化为运 Z,(p,s,t)和Z2(p,s,t)是分别从源节点s出发至目 筹学中的双目标优化问题，利用图论的理论和方法 标节点t之间的两个优化目标函数，Z,（pP,s,t)和 求得最佳方案.随着计算机技术的发展，应急救援Z,(,s,)≥0，根据两个优化目标，给边赋予两个不 方案优化研究已有所论述，其中最短路算法是解决 同的权重，求节点s至节点t之间的双目标最短路. 优化问题中的一种经典算法，如Dijkstra算法和 这样把一个救灾路线的优化问题和一个赋双权的完 Floyd算法6-切，但这些算法多局限于单一目标优 全图之间建立了同构关系.最短路问题是图论中的 化.本文研究的重大事故应急救援方案优化问题需 经典问题，但传统的最短路算法不能直接求解双权 要同时考虑两个优化目标，在求解过程中就需要对 重网络图的最短路，需根据实际问题建立合理的数 不同的目标进行折衷.Current等8-9对双目标最 学模型并设计出适合模型的算法

北 京 科 技 大 学 学 报 第 36 卷 然气泄漏至大气中形成含硫毒性云团，事故气井周 边居民如不及时撤离而暴露于毒性云团中，会使呼 吸道、皮肤和眼睛受到损伤，神经系统受抑制甚至引 发死亡． 特别是高含硫气井较一般气井井喷失控的 可能性更大，加之我国天然气井很多地处山区地形， 给事故后的人员疏散带来较大困难［7--8］． 复杂的地 形条件使得不同路段的受灾风险不同，为保证受灾 人员及时和安全地疏散，有必要寻找一条最佳疏散 路线［9--10］，既要保证疏散速度最快，又要保证路线上 的风险值在可接受范围之内． 以矿井火灾中的最佳救灾路线为例，井下空间 狭小，矿井通风及巷道联通关系复杂，供风量有限， 矿井火灾产生的大量高温、有毒有害烟气在井下不 易散失，在巷道通风情况下高温、有毒有害烟流能随 风迅速传播到很远的范围，高温烟气在巷道中蔓延 遇到新鲜风流时，可能在渗风地点形成新的火源，而 且矿井火灾还可能引起瓦斯和煤尘爆炸，因此有必 要派遣救灾队伍辅助井下受灾人员逃生． 救灾人员 佩戴氧气呼吸器及备用装置，并且经过专门的训练， 可在具有一定条件的灾变烟流中通行，但由于氧气 呼吸器供氧量有限，应估算救灾人员的需氧量以保 证救灾人员的安全． 因此在制定最佳救灾路线时， 既要保证救灾速度最快，即所选救援道路的“当量 长度”最短，还要确保路线上的总耗氧量不能超过 氧气呼吸装置中的可用氧气总量［11］． 以地质灾害中的救灾物资最佳调度路线为例， 我国疆域辽阔，地质环境复杂，地震、滑坡、泥石流等 已成为对我国危害最大的地质灾害． 尤其是近年 来，随着矿产资源开采及山区工程开发活动的增强， 崩塌、滑坡、泥石流等地质灾害更为严重［12］． 为保 证灾后救灾物资车辆的高效运行，有必要选择一条 最佳的救灾物资调度路线［13--15］，既要实现救灾物资 的运送时间最短，还要保证该路线的运输成本不超 过经济承受能力． 以上涉及的最佳疏散路线、最佳救灾路线及救 灾物资最佳调度路线等最佳应急救援方案的求解问 题均含有两个方面的优化目标，可以最终转化为运 筹学中的双目标优化问题，利用图论的理论和方法 求得最佳方案． 随着计算机技术的发展，应急救援 方案优化研究已有所论述，其中最短路算法是解决 优化问题 中 的 一 种 经 典 算 法，如 Dijkstra 算 法 和 Floyd 算法［16--17］，但这些算法多局限于单一目标优 化． 本文研究的重大事故应急救援方案优化问题需 要同时考虑两个优化目标，在求解过程中就需要对 不同的目标进行折衷． Current 等［18--19］对双目标最 短路问题的研究现状进行分类和概括后指出，对于 双目标最短路问题，通常的处理方法是对不同的目 标进行线性加权或是将某些目标转化为约束条件， 对于线性加权法而言，其权重的确定是一件很困难 的事情，而有约束的最短路问题已经被证明是 NP 完全问题，有时因为其算法复杂性太高而无法进行 求解，显然无法满足应急救援中对优化方案快速求 解的需要． 本文提出了应急救援双目标优化搜索算法，以 满足应急救援中对两个目标同时优化及结果快速求 解的需要，其基本思路是基于启发式近似算法，通过 构造辅助函数调用 Dijkstra 算法，将两个优化目标 中的某一优化目标转化为约束条件，反复迭代求解 构造权重的最短路来寻找另一优化目标的最小值， 不仅权重易于确定，而且能在较短时间内获得符合 误差限值的近似最优解． 1 问题描述及数学模型 1. 1 重大事故救灾路线双目标优化问题的提出 为清晰地叙述本文所研究的应急救援双目标优 化问题，在此以应急救援优化问题之一———最佳救 灾路线问题进行描述． 从图论角度来看，受灾区域 错综复杂的道路实际上是一个连接的网络图，道路 为图的边，道路之间的交点抽象成图的点的集合，组 成网络图的顶点; 在无向网络图上赋予救灾路线选 择的影响因素，把灾区周边道路网络布局转化为图 的拓扑优化问题． 作为图论的经典问题，最短路径 问题的定义是在一个赋权图的两个顶点之间找出一 条具有最小权值的路径． 本文考虑的最佳救灾路线问题，除了主要的优 化目标外，还有次要优化目标，即限制条件． 在此， 根据图论的理论及方法，可将应急救援双目标优化 问题描述为: 对于网络 G = ( V，E) ，其中 V( G) = { vi} 为图 G 的节点集，任一顶点 vi∈V( G) 对应于平 面内的点( xi，yi ) ; E( G) = { e | e = ( vp，vq ) = ( vq， vp ) ，vp，vq∈V} 为图 G 的边集，| E | = ne，| v | = nv， Z1 ( p，s，t) 和 Z2 ( p，s，t) 是分别从源节点 s 出发至目 标节点 t 之间的两个优化目标函数，Z1 ( p，s，t) 和 Z2 ( p，s，t) ≥0，根据两个优化目标，给边赋予两个不 同的权重，求节点 s 至节点 t 之间的双目标最短路． 这样把一个救灾路线的优化问题和一个赋双权的完 全图之间建立了同构关系． 最短路问题是图论中的 经典问题，但传统的最短路算法不能直接求解双权 重网络图的最短路，需根据实际问题建立合理的数 学模型并设计出适合模型的算法． ·536·

第4期 盖文妹等：重大事故救灾路线双目标优化模型及算法 ·537· 1.2重大事故救灾路线双目标优化模型的建立 Z,(ps,t)和Z2（Pa,s,t)实际上是关于的a函数， 为得到时变网络下的双目标路径选择模型，假 分别记作Z,（pP,s,t)=f（a）和Z2（p,s,t)= 设Z,为主要优化目标，Z2为次要优化目标，令P表 f方(a),其中，0≤x≤1p∈P,并有如下性质成立. 示节点s至节点t的任一可行路径（可用方案），则 性质1f(a)为0,1]上的减函数，当a=1 双目标最短路模型可以如下表示： 时，f(a)有最小值：方(a)为0,1]上的增函数，当 Z (p',s,t)=minz (p,s,t), (1) a=0时，2(a)有最小值. Z2(p,s,t)≤l, (2) 证明：设利用Dijkstra算法求得满足minf(a1） Z,(p,s,t）=∑w' (3) 和minf(a2）的路径Pa和P,且a1l,那么p无解；当a=1时，若 构造辅助函数直接调用Dijkstra算法，在最优解的 近似区间内多次迭代逐渐逼近最优解的双目标优化 满足minf(a)的路径p.存在，且f方(1)≤l,则p= 搜索算法，算法的每一步迭代是通过搜索当前近似 P 证明：当a=0时，w3=w2,则minf(0）= 区间得到一个改进的解，使得权重易于确定，而且收 敛速度较快 minZ2(p,s,t)=5(0).若f5(0)>l,那么s=☑，p 2.1辅助函数及相关性质 无解：当=1时，若满足minf(a)的路径p.存在， 为实现双目标最短路问题的求解，本文利用目 03=01,则min时(1)=minZ,（p,s,t)=Z,(pas,t）, 标权重01和限制权重w为边(u,)构造一个新 其中p,Pa∈P,若f(1)≤l,由性质2可知f(a)≤l 对于a∈D,1]恒成立，根据式(1)和式(2)可知 的权重，即0对=a05+(1-a)02g(0≤a≤1)，对于 指定源节点s和目标节点t,若存在一条可行路径P, p=Ps 可构造如下函数： 如果将区间0,1]平均分成n份，对于k=0, 1,…,n-1,若假定a=0时，求得满足minf(a)的 fa)=∑awg+(1-a）02g]. (5) (p ep 路径Pof方(O)=o;a=1时，求得满足minf(a)的路 对任一a∈[O,1],利用Dijkstra算法求满足 径P1(1)=1.基于所构造辅助函数的上述性质， minf(a)的最短路径Pa,根据式(3)和式(4)可分别 容易推得如下结论 求得Pa对应的两个目标函数值Z,(pa,s,t)和 结论1当x=k/n时，满足minf(a)的路径Pa Z2(pas,t),且每一个Z1（pus,t）和Z2（pu,s,t)的 存在，且f方(a)=L,则不可能有另一路径p∈P,同时 值均和0,1]区间内的一个α一一对应，所以 满足peS且Z1(p,s,t)<Z1(Pms,t)

第 4 期 盖文妹等: 重大事故救灾路线双目标优化模型及算法 1. 2 重大事故救灾路线双目标优化模型的建立 为得到时变网络下的双目标路径选择模型，假 设 Z1为主要优化目标，Z2为次要优化目标，令 p 表 示节点 s 至节点 t 的任一可行路径( 可用方案) ，则 双目标最短路模型可以如下表示: Z1 ( p* ，s，t) = minZ1 ( p，s，t) ， ( 1) Z2 ( p* ，s，t) ≤l， ( 2) Z1 ( p，s，t) = ( v ∑i ，vj ) ∈p w1ij ， ( 3) Z2 ( p，s，t) = ( v ∑i ，vj ) ∈p w2ij ． ( 4) 其中，若 p* 同时满足式( 1) 和式( 2) ，则称 p* 为模 型的最优解，记路径 p 的集合为 P，p∈P，满足式( 2) 的路径集合记作 S; w1ij和 w2ij分别为边( vi，vj ) 上的目 标权重和限制权重; l 表示第二优化目标的最大允 许值． 本文在第二部分讨论适合该模型的算法，根据 算法的步骤，详细分析其误差、时间复杂度及优势 所在． 2 重大事故救灾路线双目标优化算法 1996 年 Zhan 和 Noon 使用实际交通网络测试 了 Cherkassty 测试的 17 种算法中的 15 种． 测试结 果表明: 计算一点到所有其他点的最短路径最快的 算法是 Dijkstra 算法，但 Dijkstra 算法仅适用于单目 标最短路问题的求解，不能直接求解双目标最短路 问题［11，19］． 为求解应急救援双目标优化模型，同时 保证求解效率，本文基于启发式思想，提出一种通过 构造辅助函数直接调用 Dijkstra 算法，在最优解的 近似区间内多次迭代逐渐逼近最优解的双目标优化 搜索算法，算法的每一步迭代是通过搜索当前近似 区间得到一个改进的解，使得权重易于确定，而且收 敛速度较快． 2. 1 辅助函数及相关性质 为实现双目标最短路问题的求解，本文利用目 标权重 w1ij和限制权重 w2ij为边( vi，vj) 构造一个新 的权重，即 w3ij = αw1ij + ( 1 － α) w2ij( 0≤α≤1) ，对于 指定源节点 s 和目标节点 t，若存在一条可行路径 p， 可构造如下函数: f( α) = ( v ∑i ，vj ) ∈p ［αw1ij + ( 1 － α) w2ij ］． ( 5) 对任 一 α ∈［0，1 ］，利 用 Dijkstra 算 法 求 满 足 minf( α) 的最短路径 pst，根据式( 3) 和式( 4) 可分别 求得 pst 对应的两个目标函数值 Z1 ( pst，s，t) 和 Z2 ( pst，s，t) ，且每一个 Z1 ( pst，s，t) 和 Z2 ( pst，s，t) 的 值均 和［0，1］区 间 内 的 一 个 α 一 一 对 应，所 以 Z1 ( pst，s，t) 和 Z2 ( pst，s，t) 实际上是关于的 α 函数， 分别 记 作 Z1 ( p，s，t) = f1 ( α) 和 Z2 ( p，s，t) = f2 ( α) ，其中，0≤α≤1，p∈P，并有如下性质成立． 性质 1 f1 ( α) 为［0，1］上的减函数，当 α = 1 时，f1 ( α) 有最小值; f2 ( α) 为［0，1］上的增函数，当 α = 0时，f2 ( α) 有最小值． 证明: 设利用 Dijkstra 算法求得满足 minf( α1 ) 和 minf ( α2 ) 的路径 pst1 和 pst2，且 α1 ＜ α2，根据式 ( 3) ～ 式( 5) ，有 α1Z1 ( pst1，s，t) + ( 1 － α1 ) Z2 ( pst1，s，t) ≤ α1Z1 ( pst2，s，t) + ( 1 － α1 ) Z2 ( pst2，s，t) ， α2Z1 ( pst1，s，t) + ( 1 － α2 ) Z2 ( pst1，s，t) ≥ α2Z1 ( pst2，s，t) + ( 1 － α2 ) Z2 ( pst2，s，t) ， 所以 α1 ( Z1 ( pst1，s，t) － Z1 ( pst2，s，t) ) + ( 1 － α1 )· ( Z2 ( pst1，s，t) － Z2 ( pst2，s，t) ) ≤0， α2 ( Z1 ( pst1，s，t) － Z1 ( pst2，s，t) ) + ( 1 － α2 )· ( Z2 ( pst1，s，t) － Z2 ( pst2，s，t) ) ≥0． 又因为 0≤α1 ＜ α2≤1，所以有 Z1 ( pst1，s，t) － Z1 ( pst2，s，t) ≥0， Z2 ( pst1，s，t) － Z2 ( pst2，s，t) ≤0， 即 f1 ( α1 ) ≥f1 ( α2 ) ，f2 ( α1 ) ≤f2 ( α2 ) ． 因此 f1 ( α) 为减函数，f2 ( α) 为增函数． 因为 0≤α≤ 1，所以 α = 0 时 f2 ( α) 取得最小值，α = 1 时 f1 ( α) 取 得最小值． 性质 2 假设已知第二优化目标的限值为 l: 当 α = 0 时，若 f2 ( 0) ＞ l，那么 p* 无解; 当 α = 1 时，若 满足 minf( α) 的路径 pst存在，且 f2 ( 1) ≤l，则 p* = pst ． 证 明: 当 α = 0 时，w3 = w2，则 minf( 0) = minZ2 ( p，s，t) = f2 ( 0) ． 若 f2 ( 0) ＞ l，那么 s = ，p* 无解; 当 α = 1 时，若满足 minf( α) 的路径 pst 存在， w3 = w1，则 minf( 1) = minZ1 ( p，s，t) = Z1 ( pst，s，t) ， 其中 p，pst∈P，若 f2 ( 1) ≤l，由性质 2 可知 f2 ( α) ≤l 对于 α∈［0，1］恒成立，根据式( 1) 和式( 2) 可知 p* = pst ． 如果将区间［0，1］平均分成 n 份，对于 k = 0， 1，…，n － 1，若假定 α = 0 时，求得满足 minf( α) 的 路径 p0，f2 ( 0) = l0 ; α = 1 时，求得满足 minf( α) 的路 径 p1，f2 ( 1) = l1 ． 基于所构造辅助函数的上述性质， 容易推得如下结论． 结论 1 当 α = k /n 时，满足 minf( α) 的路径 pst 存在，且 f2 ( α) = l，则不可能有另一路径 p∈P，同时 满足 p∈S 且 Z1 ( p，s，t) ＜ Z1 ( pst，s，t) ． ·537·

·538 北京科技大学学报 第36卷 结论2当a=k/n时，满足minf(a)的路径p1 (6）)k←-k+1,转(4) 存在，且5（a)l,根据性质1和2 算法中步骤(3)~(7)为嵌套循环，(4)~(6) 可知此时可能有另一路径p∈P,满足Z(p,s,t)≤ 为内部循环，其余为外部循环 Z2(p,s,t)≤l,且Z1(P2,s,t)≤Z(p,s,t)≤Z,（p1, 2.3算法误差、时间复杂度及优势分析 s,t). 假定双目标优化模型的最优解p存在，且在 结论3若a取遍k/n(k=0,1,…,n-1), a=时获得，则(a）=l,Z1（p,s,t)= 求解满足minf(ac)的所有路径，可以获得两个目标 f(a).当a=0时求得满足mimf(a)的路径po,则 函数的变化趋势曲线和f.根据曲线和方可知， Z,(Po,s,t)=maf(a).若算法外部迭代到第m次 设置的第二优化目标的限值不同，最优解p的结果 时获得了最优解的一个近似解p,显然此时算法 不同，若满足1≥l1则p=P1,若满足l=。则p= 的误差无法预先精确计算得到，不妨假设第一优化 Po,若满足ll,则p可以在区间 Z1(p,s,t)）(a1-）= u,内通过前面构造的辅助函数求出，并称区间 Z (po's,t)-(Z (po,s,t)-Z (p',s,t))k/n u,]为最优路径的近似区间，路径P.为最优路径 当i=2时， 的一个近似解，记作p;若满足minf(a)的路径存 a2=0+k/n+k2/m2(1≤k2≤n-1), 在且在α=a处求得，即方2（α）=l,该路径即为 Z.(p,s,t）=Z(pos,t)-(Z,(pos,t）- 所求的最优解p. Z(p,s,t))(k/n+k2m2). 如果每次均把u,]细分成n份，k=0,1, 利用递推法可知，当i=m时， …,n-1,如果存在最优或近似最优路径，就可以通 am =0+k/n +k2/n2+.+k/n" 过反复迭代搜索当前近似区间山，]方式不断逼近 (1≤k≤n-1,1≤j≤m), 理想值，直至获得最优解搜索结束.满足minf(a) Z (p",s,t)=Z (po,s,t)-(Z (po,s,t)- 的路径可以调用Dijkstra算法求出，因此双目标优 Z(p,s,t)(k/n+2/n2+…+kmn), 化搜索算法步骤描述如下： 那么算法的误差可以表示为 (1)a←-l,调用Dijkstra算法求源节点s到目标 d-ps,）-Zps,） 节点t的满足minf(a)的路径P1· Z (p',s,t) (2)若Z2（p1,s,t)≤l,p←-P1,算法结束；否则 (Z (po's,t)-Z (p',s,t)) aO,调用Dijkstra算法求源节点s到目标节点t的 Z(p",s,t) 满足minf(a)的路径Po;若Z2（po,s,t)>l,无解，算 [-停+…川 (6) 法结束：若Z2(Po,s,t)=l,p←-Po,算法结束：否则 pe←-Po,u←0，-1，i-1. d≤（Zpos,0-Z(ps, -x Z (p",s,t) (3)△←-(m-）/n,k←-1. (4)a←-u+kM,调用Dijkstra算法求源节点s 1-(后+片+…+川= 到目标节点t的满足minf(a)的路径Pk: (5)若Z2(Ps,t)=l,p←-P,算法结束；若 n" (7) Z2（ps,t）<l,pw←-P,u←-a,若k=n-1,转(7)； 器小 否则-a,转(7). 令A=ma听(a)乐(a),则

北 京 科 技 大 学 学 报 第 36 卷 结论 2 当 α = k /n 时，满足 minf( α) 的路径 p1 存在，且 f2 ( α) ＜ l; 当 α = ( k + 1 ) /n 时，满 足 minf( α) 的路径 p2存在，且 f2 ( α) ＞ l，根据性质 1 和 2 可知此时可能有另一路径 p∈P，满足Z2 ( p1，s，t) ≤ Z2 ( p，s，t) ≤l，且 Z1 ( p2，s，t) ≤Z1 ( p，s，t) ≤Z1 ( p1， s，t) ． 结论 3 若 α 取遍 k /n ( k = 0，1，…，n － 1) ， 求解满足 minf( α) 的所有路径，可以获得两个目标 函数的变化趋势曲线 f1和 f2 ． 根据曲线 f1和 f2可知， 设置的第二优化目标的限值不同，最优解 p* 的结果 不同，若满足 l≥l1则 p* = p1，若满足 l = l0则 p* = p0，若满足 l ＜ l0则 p* 无解，若满足 l0 ＜ l ＜ l1则可以 在区间［0，1］内通过细分法获得满足 f2 ( α) ≤l 的一 系列最优解的采样值，这些采样值中满足 minf1 ( α) 的路径即为最优解 p* ． 2. 2 双目标优化搜索算法 假定由源节点 s 到目标节点 t 的最优路径 p* 存 在，α∈［u，v］( 其中 0≤u，v≤1) ，根据结论 1 和 2 可知: 若 α = u 和 α = v 时满足 minf( α) 的路径 pu及 pv存在，且 f2 ( u) ＜ l，且 f2 ( v) ＞ l，则 p* 可以在区间 ［u，v］内通过前面构造的辅助函数求出，并称区间 ［u，v］为最优路径的近似区间，路径 pu为最优路径 的一个近似解，记作 papp ; 若满足 minf( α) 的路径存 在且在 α = α* 处求得，即 f2 ( α* ) = l，该路径即为 所求的最优解 p* ． 如果每次均把 ［u，v］细分成 n 份，ki = 0，1， …，n － 1，如果存在最优或近似最优路径，就可以通 过反复迭代搜索当前近似区间［u，v］方式不断逼近 理想值，直至获得最优解搜索结束． 满足 minf( α) 的路径可以调用 Dijkstra 算法求出，因此双目标优 化搜索算法步骤描述如下: ( 1) α←1，调用 Dijkstra 算法求源节点 s 到目标 节点 t 的满足 minf( α) 的路径 p1 ． ( 2) 若 Z2 ( p1，s，t) ≤l，p* ←p1，算法结束; 否则 α←0，调用 Dijkstra 算法求源节点 s 到目标节点 t 的 满足 minf( α) 的路径 p0 ; 若 Z2 ( p0，s，t) ＞ l，无解，算 法结束; 若 Z2 ( p0，s，t) = l，p* ←p0，算法结束; 否则 papp ←p0，u←0，v←1，i←1． ( 3) Δ←( v － u) /n，k←1． ( 4) α←u + kΔ，调用 Dijkstra 算法求源节点 s 到目标节点 t 的满足 minf( α) 的路径 pik ． ( 5) 若 Z2 ( pik，s，t) = l，p* ←pik，算法结束; 若 Z2 ( pik，s，t) ＜ l，papp ←pik，u←α，若 k = n － 1，转( 7) ; 否则 v←α，转( 7) ． ( 6) k←k + 1，转( 4) ． ( 7) i←i + 1，若 i≤m，转( 3) ． 算法中步骤( 3) ～ ( 7) 为嵌套循环，( 4) ～ ( 6) 为内部循环，其余为外部循环． 2. 3 算法误差、时间复杂度及优势分析 假定双目标优化模型的最优解 p* 存在，且在 α = α* 时 获 得，则 f2 ( α* ) = l，Z1 ( p* ，s，t ) = f1 ( α* ) ． 当 α = 0 时求得满足 minf( α) 的路径 p0，则 Z1 ( p0，s，t) = maxf1 ( α) ． 若算法外部迭代到第 m 次 时获得了最优解的一个近似解 papp ，显然此时算法 的误差无法预先精确计算得到，不妨假设第一优化 目标关于系数 α 的函数 f1 ( α) 随系数 α 线性变化， 令 i 代表外部循环次数计数器，可通过下述过程估 计迭代到第 m 次时算法的相对误差． 当 i = 0 时， α0 = 0，Z1 ( papp ，s，t) = Z1 ( p0，s，t) ． 当 i = 1 时， α1 = 0 + k1 /n( 1≤k1≤n － 1) ， Z1 ( papp ，s，t) = Z1 ( p0，s，t) － ( Z1 ( p0，s，t) － Z1 ( p* ，s，t) ) ( α1 － α0 ) = Z1 ( p0，s，t) － ( Z1 ( p0，s，t) － Z1 ( p* ，s，t) ) k1 /n． 当 i = 2 时， α2 = 0 + k1 /n + k2 /n2 ( 1≤k2≤n － 1) ， Z1 ( papp ，s，t) = Z1 ( p0，s，t) － ( Z1 ( p0，s，t) － Z1 ( p* ，s，t) ) ( k1 /n + k2 /n2 ) ． 利用递推法可知，当 i = m 时， αm = 0 + k1 /n + k2 /n2 + … + km /nm ( 1≤kj≤n － 1，1≤j≤m) ， Z1 ( papp ，s，t) = Z1 ( p0，s，t) － ( Z1 ( p0，s，t) － Z1 ( p* ，s，t) ) ( k1 /n + k2 /n2 + … + km /nm ) ， 那么算法的误差可以表示为 d = Z1 ( papp ，s，t) － Z1 ( p* ，s，t) Z1 ( p* ，s，t) = ( Z1 ( p0，s，t) － Z1 ( p* ，s，t) ) Z1 ( p* ，s，t) [ × 1 － ( k1 n + k2 n2 + … + km nm ) ] ， ( 6) d≤ ( Z1 ( p0，s，t) － Z1 ( p* ，s，t) ) Z1 ( p* ，s，t) [ × 1 － ( 1 n + 1 n2 + … + 1 nm ) ] = n － 2 + 1 nm n － 1 ·[ w1 ( p0 ) w1 ( p* ) － 1 ] ． ( 7) 令 λ = maxf1 ( α) /f1 ( α* ) ，则 ·538·

第4期 盖文妹等：重大事故救灾路线双目标优化模型及算法 ·539· n-2+1 优化目标要求的应急救援方案，即应急救援优化问 dx=(λ-1) n (8) 题的解决.同时，己知需要优化的两个目标，但某一 n-1 优化目标的限定数值未知，利用该算法可以获得两 根据式(8)可知算法具备收敛性，其收敛速度 个目标函数随着参数α(0≤α≤1)变化的趋势线， 受以下因素影响. 根据两条目标函数函数曲线，决策者可以根据需要 (1)细分次数n.令F(n)=（入-1)(n-2+ 为某一优化目标的限值设置不同的数值，形成不同 1/n)/(n-1),若入和m不变，可以证明dF(n)/ 的优化问题，即问题的提出. dn≥0对于n≥2恒成立，所以n的值设定的越大， 400,, 算法迭代到第m次时最坏情况下的相对误差越大， 350 算法的收敛速度趋于减慢，即总迭代步数趋于增加 一) 300 一min fa) (2)第二优化目标的限值1及图G的节点数 250 n因为A=Z1(po,s,t）/Z1(p,s,t)=maxf(a)/ 200 f(a),对于同一张网络图G,max(a)不变，根据 150 性质1和2，限值l=f(a)越大，f(α)越小，A越 100 大；对于不同的网络图，当节点数增加时，边数增多， 50H 源节点至目标节点的可用路径增加，显然maxf(ax) 0.2 0.40.6 0.8 趋于增大，同时f(α)趋于减小，入有增大趋势.若 图1辅助函数随参数α变化趋势图 n和m不变，显然入越大算法迭代到第m次时最坏 Fig.I Variation tendency of three auxiliary functions with parameter a 情况下的相对误差越大.所以，第二优化目标的限 值或是图的节点数增加，算法迭代到第m次时最坏 3案例分析 情况下的相对误差增大，算法的收敛速度趋于减慢， 即总迭代步数趋于增加. 以高含硫井场重大毒气泄漏事故为例.毒气泄 对于非负带权图而言，Dijkstra单源最短路径算 漏事故发生后，为保证受灾人员的及时撤离至安全 法的时间复杂度为O(n.+n,lgn,),而多源的最短路 区域，需要由佩戴氧气呼吸器及备用装置的救援人 径算法的时间复杂度为O(n.n、+nlgn,),其中n.和 员前往救灾辅助撤离.救灾路线选择的影响因素主 n,分别表示图G的节点总数和边的总数.利用n分 要有两个方面：一是救灾人员的通行时间，一般以道 近似算法若求G中到节点，到节点，的最优路径， 路“当量长度”衡量0；二是佩戴呼吸装置及设备的 第(1)和第(2)步求以0=ac1+(1-a)w2为权值 救灾人员在路线上的呼吸耗氧总量.若以道路“当 的最短路径，两次可以利用Dijkstra算法进行，所需 量长度”作为边的权重，高含硫井场重大毒气泄漏 的时间最差为O(2),其中专=n。+n,lgn,为常数. 事故最佳救灾路线的优化目标是使从救灾基地到受 步骤(3)~(7)的内部循环计数器k最大可能取到 灾地点路线的总当量长度最短；若以路段上救灾人 n-1,每次循环均调用一次Dij认sta算法：外部循环 员的耗氧量作为边的权重，优化目标是使救灾人员 计数器i最大取到m,所以步骤(3)~(7)所需的时 从救灾基地到受灾地点路线上的呼吸耗氧总量不超 间最差为O(mn-m),则利用该算法计算G中到 过可用氧气总量.作为应急救援方案的决策者，在 节点t的单源最优路径的时间复杂度为O(mn- 对救灾路线进行优化时，需要同时实现这两个目标， m+2).若求G中所有节点到节点t的最优路径， 既要保证救援效率，又要保证救灾人员的自身安全， 则上述算法需要循环调用n,次，因此利用该算法求 即寻找含有两种权值的网络图的最短路. G中到节点t的多源最优路径，同理可以推出算法 系统的用户层用net架构的C#语言来发，底层 的时间复杂度为0(mn叱-m叱+2)，其中g=n.n,+ 用Python0的NetworkX库，直接调用封装好的 n1gn,为常数. Dijkskra算法，获取数据的方法可以从EXCEL导入 根据本文所构造的辅助函数的性质2及结论3 或者动态从数据库中读取如.导入该气田周边的 可知，本文提出的算法不仅利于应急救援优化方案 地理信息数据后，以救灾基地(0,0)点为源节点，取 的决策者解决问题，还可以根据算法绘制的曲线 0018井的应急计划区回中(3,2)点作为目的节 (图1)提出问题.当己知两个优化目标及某一优化 点.把源节点到目标节点之间的道路交通网定义为 目标的限定值，决策者可以利用该算法求得符合该 一张网络图，路段即为图的边，路段之间的交点为图

第 4 期 盖文妹等: 重大事故救灾路线双目标优化模型及算法 dmax = ( λ － 1) n － 2 + 1 nm n － 1 ． ( 8) 根据式( 8) 可知算法具备收敛性，其收敛速度 受以下因素影响． ( 1) 细分次数 n． 令 F( n) = ( λ － 1) ( n － 2 + 1 /nm ) /( n － 1) ，若 λ 和 m 不变，可以证明 dF( n) / dn≥0 对于 n≥2 恒成立，所以 n 的值设定的越大， 算法迭代到第 m 次时最坏情况下的相对误差越大， 算法的收敛速度趋于减慢，即总迭代步数趋于增加． ( 2) 第二优化目标的限值 l 及图 G 的节点数 nv． 因为 λ = Z1 ( p0，s，t) /Z1 ( p* ，s，t) = maxf1 ( α) / f1 ( α* ) ，对于同一张网络图 G，maxf1 ( α) 不变，根据 性质 1 和 2，限值 l = f2 ( α* ) 越大，f1 ( α* ) 越小，λ 越 大; 对于不同的网络图，当节点数增加时，边数增多， 源节点至目标节点的可用路径增加，显然 maxf1 ( α) 趋于增大，同时 f1 ( α* ) 趋于减小，λ 有增大趋势． 若 n 和 m 不变，显然 λ 越大算法迭代到第 m 次时最坏 情况下的相对误差越大． 所以，第二优化目标的限 值或是图的节点数增加，算法迭代到第 m 次时最坏 情况下的相对误差增大，算法的收敛速度趋于减慢， 即总迭代步数趋于增加． 对于非负带权图而言，Dijkstra 单源最短路径算 法的时间复杂度为 O( ne + nv lgnv ) ，而多源的最短路 径算法的时间复杂度为 O( nenv + n2 v lgnv ) ，其中 ne和 nv分别表示图 G 的节点总数和边的总数． 利用 n 分 近似算法若求 G 中到节点 vs到节点 vt的最优路径， 第( 1) 和第( 2) 步求以 w = αw1 + ( 1 － α) w2 为权值 的最短路径，两次可以利用 Dijkstra 算法进行，所需 的时间最差为 O( 2ξ) ，其中 ξ = ne + nv lgnv为常数． 步骤( 3) ～ ( 7) 的内部循环计数器 k 最大可能取到 n － 1，每次循环均调用一次 Dijkstra 算法; 外部循环 计数器 i 最大取到 m，所以步骤( 3) ～ ( 7) 所需的时 间最差为 O( mnξ － mξ) ，则利用该算法计算 G 中到 节点 t 的单源最优路径的时间复杂度为 O( mnξ － mξ + 2ξ) ． 若求 G 中所有节点到节点 t 的最优路径， 则上述算法需要循环调用 nv次，因此利用该算法求 G 中到节点 t 的多源最优路径，同理可以推出算法 的时间复杂度为 O( mnζ － mζ + 2ζ) ，其中 ζ = nenv + n2 v lgnv 为常数． 根据本文所构造的辅助函数的性质 2 及结论 3 可知，本文提出的算法不仅利于应急救援优化方案 的决策者解决问题，还可以根据算法绘制的曲线 ( 图 1) 提出问题． 当已知两个优化目标及某一优化 目标的限定值，决策者可以利用该算法求得符合该 优化目标要求的应急救援方案，即应急救援优化问 题的解决． 同时，已知需要优化的两个目标，但某一 优化目标的限定数值未知，利用该算法可以获得两 个目标函数随着参数 α( 0≤α≤1) 变化的趋势线， 根据两条目标函数函数曲线，决策者可以根据需要 为某一优化目标的限值设置不同的数值，形成不同 的优化问题，即问题的提出． 图 1 辅助函数随参数 α 变化趋势图 Fig． 1 Variation tendency of three auxiliary functions with parameter α 3 案例分析 以高含硫井场重大毒气泄漏事故为例． 毒气泄 漏事故发生后，为保证受灾人员的及时撤离至安全 区域，需要由佩戴氧气呼吸器及备用装置的救援人 员前往救灾辅助撤离． 救灾路线选择的影响因素主 要有两个方面: 一是救灾人员的通行时间，一般以道 路“当量长度”衡量［10］; 二是佩戴呼吸装置及设备的 救灾人员在路线上的呼吸耗氧总量． 若以道路“当 量长度”作为边的权重，高含硫井场重大毒气泄漏 事故最佳救灾路线的优化目标是使从救灾基地到受 灾地点路线的总当量长度最短; 若以路段上救灾人 员的耗氧量作为边的权重，优化目标是使救灾人员 从救灾基地到受灾地点路线上的呼吸耗氧总量不超 过可用氧气总量． 作为应急救援方案的决策者，在 对救灾路线进行优化时，需要同时实现这两个目标， 既要保证救援效率，又要保证救灾人员的自身安全， 即寻找含有两种权值的网络图的最短路． 系统的用户层用 net 架构的 C#语言来发，底层 用 Python ［20］ 的 NetworkX 库，直接调用封装好的 Dijkskra算法，获取数据的方法可以从 EXCEL 导入 或者动态从数据库中读取［21］． 导入该气田周边的 地理信息数据后，以救灾基地( 0，0) 点为源节点，取 001--8 井的应急计划区［2］中( 3，2) 点作为目的节 点． 把源节点到目标节点之间的道路交通网定义为 一张网络图，路段即为图的边，路段之间的交点为图 ·539·

·540 北京科技大学学报 第36卷 的节点，节点的数目代表图的规模.在此，将路段 至(3,2)点的双目标最佳救灾路线.输入参数和 的当量长度作为第一优化目标，将路径上的总耗 优化结果见表1和表2.由表可见，与Dijkstra算 氧量不超过呼吸装置可用氧气总量作为第二优化 法相比，双目标优化搜索算法所求方案可以同时 目标，据此可将路段的当量长度和路段上的呼吸 满足当量长度和耗氧量两个优化目标的要求.图 耗氧量作为边的两个权重，为各个边随机赋权值， 2中所示红线为利用双目标优化搜索算法求得的 编译并运行本文的双目标搜索算法，寻找(0,0)点 一条最佳救灾路线. 表1初始输入数据 Table 1 Parameters of the rescue network 路段编号 路段 当量长度/m 耗氧量/mL路段编号 路段 当量长度/m 耗氧量/(102ml) 0 (0,0)~(0,1) 333.3 30 9 (1,2)~(2,2) 52.6 多 (0,0)~(1,0) 166.7 60 10 (2,0)-(2,1) 111.1 9 2 (0,1)(0,2) 250.0 40 11 (2,0)~(3,0) 125.0 8 (0,1)≈(1,1) 83.3 120 12 (2,1)(2,2） 100.0 10 4 (0,2）~(1,2) 55.5 180 13 (2,1)(3,1) 71.4 14 (1,0)~(1,1) 166.7 60 14 (2,2)~(3,2) 50.0 20 6 (1,0)≈(2,0) 142.9 70 15 (3,0)(3,1) 83.3 12 > (1,1)(1,2) 142.9 70 16 (3,1)(3,2) 76.9 3 耗氧量限值1mL 51 表2优化结果对比 Table 2 Contrast of simulation results 算法 最优路线方案 总当量长度/m 总耗氧量/mL总迭代次数 Dijkstra算法，当量长度最短路 [0,0),(1,0),(1,1),(2,1),(3,1),(3,2)] 558.6 52 Dijkstra算法，耗氧量最短路 [0,0),(1,0),(2,0),(3.0),(3,1),(3,] 594.8 46 双目标优化算法 [0,0),(1,0),(2,0),(2,1),(3,1),(3,2] 569.0 49 14 分次数设置为3时，总迭代步数一般在30次左右即 可获得双目标优化救灾路线的近似最优解，证明该 算法收敛速度较快 70 一外部循环迭代次数 60 一总选代次数 50 40 30 001-8井 图2救灾基地至0018井应急救灾计划区内某一点的双目标最 10 15 优救灾路线 细分次数 Fig.2 Bi-objective optimization relief route from the relief base to 图3迭代次数与细分次数关系曲线 the emergency relief plan area of the 0018 well Fig.3 Curve of iteration number to segment number 为验证双目标优化算法的收敛速度的影响因 素，在Python平台上反复运行双目标优化搜索算 4 结论 法，得到算法迭代次数随细分次数、第二优化目标的 (1)本文运用运筹学中图论及优化问题的理论 限定数值及图的规模（选取的节点数）的变化趋势. 及方法建立了重大事故救灾路线双目标优化的数学 由图3和图4可知，模拟结果和前文理论分析相吻 模型，提出适合该模型的双目标优化搜索算法.该 合.此外，即使网络图的节点数达到10000时，当细 算法使得双目标优化问题的权重易于确定，而且收

北 京 科 技 大 学 学 报 第 36 卷 的节点，节点的数目代表图的规模． 在此，将路段 的当量长度作为第一优化目标，将路径上的总耗 氧量不超过呼吸装置可用氧气总量作为第二优化 目标，据此可将路段的当量长度和路段上的呼吸 耗氧量作为边的两个权重，为各个边随机赋权值， 编译并运行本文的双目标搜索算法，寻找( 0，0) 点 至( 3，2) 点的双目标最佳救灾路线． 输入参数和 优化结果见表 1 和表 2． 由表可见，与 Dijkstra 算 法相比，双目标优化搜索算法所求方案可以同时 满足当量长度和耗氧量两个优化目标的要求． 图 2 中所示红线为利用双目标优化搜索算法求得的 一条最佳救灾路线． 表 1 初始输入数据 Table 1 Parameters of the rescue network 路段编号 路段 当量长度/m 耗氧量/mL 路段编号 路段 当量长度/m 耗氧量/( 10 － 2 mL) 0 ( 0，0) ～ ( 0，1) 333. 3 30 9 ( 1，2) ～ ( 2，2) 52. 6 19 1 ( 0，0) ～ ( 1，0) 166. 7 60 10 ( 2，0) ～ ( 2，1) 111. 1 9 2 ( 0，1) ～ ( 0，2) 250. 0 40 11 ( 2，0) ～ ( 3，0) 125. 0 8 3 ( 0，1) ～ ( 1，1) 83. 3 120 12 ( 2，1) ～ ( 2，2) 100. 0 10 4 ( 0，2) ～ ( 1，2) 55. 5 180 13 ( 2，1) ～ ( 3，1) 71. 4 14 5 ( 1，0) ～ ( 1，1) 166. 7 60 14 ( 2，2) ～ ( 3，2) 50. 0 20 6 ( 1，0) ～ ( 2，0) 142. 9 70 15 ( 3，0) ～ ( 3，1) 83. 3 12 7 ( 1，1) ～ ( 1，2) 142. 9 70 16 ( 3，1) ～ ( 3，2) 76. 9 13 耗氧量限值\mL 51 表 2 优化结果对比 Table 2 Contrast of simulation results 算法 最优路线方案 总当量长度/m 总耗氧量/mL 总迭代次数 Dijkstra 算法，当量长度最短路 ［( 0，0) ，( 1，0) ，( 1，1) ，( 2，1) ，( 3，1) ，( 3，2) ］ 558. 6 52 — Dijkstra 算法，耗氧量最短路 ［( 0，0) ，( 1，0) ，( 2，0) ，( 3，0) ，( 3，1) ，( 3，2) ］ 594. 8 46 — 双目标优化算法 ［( 0，0) ，( 1，0) ，( 2，0) ，( 2，1) ，( 3，1) ，( 3，2) ］ 569. 0 49 14 图 2 救灾基地至001--8 井应急救灾计划区内某一点的双目标最 优救灾路线 Fig． 2 Bi-objective optimization relief route from the relief base to the emergency relief plan area of the 001-8 well 为验证双目标优化算法的收敛速度的影响因 素，在 Python 平台上反复运行双目标优化搜索算 法，得到算法迭代次数随细分次数、第二优化目标的 限定数值及图的规模( 选取的节点数) 的变化趋势． 由图 3 和图 4 可知，模拟结果和前文理论分析相吻 合． 此外，即使网络图的节点数达到 10000 时，当细 分次数设置为 3 时，总迭代步数一般在 30 次左右即 可获得双目标优化救灾路线的近似最优解，证明该 算法收敛速度较快． 图 3 迭代次数与细分次数关系曲线 Fig． 3 Curve of iteration number to segment number 4 结论 ( 1) 本文运用运筹学中图论及优化问题的理论 及方法建立了重大事故救灾路线双目标优化的数学 模型，提出适合该模型的双目标优化搜索算法． 该 算法使得双目标优化问题的权重易于确定，而且收 ·540·

第4期 盖文妹等：重大事故救灾路线双目标优化模型及算法 ·541· 40 a 5( 35 一外部循环选迭代次数 40 ·总迭代次数 35 30 2n 25 一外部循环选代次数 20 +总迭代次数 15 10 10 5 29 3. 32 33 34 50010001500200025003000 第二优化日标限值L 网格图节点数 图4迭代次数与第二目标限值()和网格图节点数(b)关系曲线 Fig.4 Curves of iteration number with the second target limit (a)and the node number of the gridding map (b) 敛速度较快，所得优化方案是一种近似最优解.该 (席学军，董文彤，郭再富.复杂山区地形高含硫气井安全防 模型适用应急救援问题优化也可扩展到其他优化 护距离研究.中国安全科学学报，2009,19(12)：66) 问题. [8]Liu J,Li J,Deng Y F.Design and implementation of the scene data acquisition and management system for major incident after (2)本文提出的算法不仅利于应急救援优化方 logging of high risks gas field.J Saf Sci Technol,2011,7(6):58 案的决策者解决问题，还可以根据算法得到两个目 (刘品，李竞，邓云峰.三高气田钻完井重大事故现场监测数 标函数的变化趋势曲线提出问题 据采集管理系统的设计与实现.中国安全科学生产技术， (3)利用地理信息系统的Python控件进行程 2011,7(6):58) 序编制，实现了含硫气田井喷事故最优救灾路线的 9] Yang H C,Sun B.Optimization of evacuation based on PERT and shortest path theory.Fire Sci Technol,2011,30(2):103 搜索，证明该算法具有较高的求解效率。应急救援 (杨海潮，孙冰.基于PERT和最短路理论的人员疏散最优 双目标优化方案的确定对于重大事故灾害救援预案 化.消防理论研究，2011,30(2)：103) 的编制具有极重要的意义. [10]Xiao G Q,Wen L M,Chen B Z,et al.Shortest evacuation route on toxic leakage.J Northeast Univ Nat Sci,2001,22(6):674 参考文献 (肖国清，温丽敏，陈宝智，等.毒气泄漏时的最佳疏散路 [Urbina E,Wolshon B.National review of hurricane evacuation 径.东北大学学报：自然科学版，2001,22(6)：674) plans and policies:a comparison and contrast of state practices. [11]Gao R,Jiang ZA,Dong F,et al.Mathematical model and algo Transp Res Part A,2003,37(3):257 rithm of a dynamic optimum rescue route during mine fire time Yuan J P,FangZ,Lu Z M,et al.Large-scale evacuation of peo- based on MapObject.J Unin Sci Technol Beijing,2008,30(7): ple from urban disaster.J Nat Disasters,2005,14(6):116 705 (袁建平，方正，卢兆明，等.城市灾时大范围人员应急疏散 (高蕊，蒋仲安，董枫，等.基于MapObject的动态最佳救灾 探讨.自然灾害学报，2005,14(6)：116) 路线数学模型和算法.北京科技大学学报，2008,30(7)： B]Cheng H,Li R.Song FX,et al.Overview on foreign standards of 705) emergency management and rescue.J Catastrophol,2011,26 [12]He MC,Xiao Z Q,Li G F,et al.Regional Engineering Disaster (3):133 RMON Warning Integrated Management Systems and Applica- (陈虹，李蕊，宋富喜，等.国外突发事件应急救援标准综述 tions.Beijing:China Architecture and Building Press,2012 灾害学，2011,26(3)：133) (何满潮，肖志强，李国峰，等.区域性工程灾害远程监控预 4]Deng Y F.Study on Pedestrian Evacuation Model for Accident Re- 警一体化综合管理系统及应用.北京：中国建筑工业出版 leasing Toric Vapors [Dissertation].Beijing:University of Sei- 社，2012) ence and Technology Beijing,2008 03] Sun L,Zhao L D.Collaborative allocation problem of rescue sup- (邓云峰.毒气泄露事故人员疏散模型及应用研究[学位论 plies under danger source diffusion.J Southeast Unie Nat Sci Ed, 文].北京：北京科技大学，2008) 2007,11(SupplⅡ)：367 5]Tufekci S,Wallace W A.The emerging area of emergency man- (孙立，赵林度.危险源扩散环境下救援物资协同调度问题 agement and engineering.IEEE Trans Eng Manage,1998,45 东南大学学报：自然科学版，2007,11（增刊Ⅱ）：367) (2):103 14]Niu H R,Li P,Shi T Y.Modeling and simulation on uncertainty 6]Gorge M.Crisis management best practice:where do we start shortest path problem in emergency resource dispatching.J Nan- from?Comput Fraud Secur,2006,2006(6):10 jing Unie Sci Technol Nat Sci,2009,33 (Suppl):178 ]XiX J.Dong WT,GuoZ F.A method for calculating safety dis- (牛宏睿，李平，史天运，应急资源调度中最短路边权不确 tance of high-sulfide gas well in complex mountainous terrain.Chi- 定性问题的建模与仿真.南京理工大学学报：自然科学版， na Saf Sci J,2009,19(12):66 2009,33(增刊)：178)

第 4 期 盖文妹等: 重大事故救灾路线双目标优化模型及算法 图 4 迭代次数与第二目标限值( a) 和网格图节点数( b) 关系曲线 Fig． 4 Curves of iteration number with the second target limit ( a) and the node number of the gridding map ( b) 敛速度较快，所得优化方案是一种近似最优解． 该 模型适用应急救援问题优化也可扩展到其他优化 问题． ( 2) 本文提出的算法不仅利于应急救援优化方 案的决策者解决问题，还可以根据算法得到两个目 标函数的变化趋势曲线提出问题． ( 3) 利用地理信息系统的 Python 控件进行程 序编制，实现了含硫气田井喷事故最优救灾路线的 搜索，证明该算法具有较高的求解效率． 应急救援 双目标优化方案的确定对于重大事故灾害救援预案 的编制具有极重要的意义． 参 考 文 献 ［1］ Urbina E，Wolshon B． National review of hurricane evacuation plans and policies: a comparison and contrast of state practices． Transp Ｒes Part A，2003，37( 3) : 257 ［2］ Yuan J P，Fang Z，Lu Z M，et al． Large-scale evacuation of peo￾ple from urban disaster． J Nat Disasters，2005，14( 6) : 116 ( 袁建平，方正，卢兆明，等． 城市灾时大范围人员应急疏散 探讨． 自然灾害学报，2005，14( 6) : 116) ［3］ Cheng H，Li Ｒ，Song F X，et al． Overview on foreign standards of emergency management and rescue． J Catastrophol，2011，26 ( 3) : 133 ( 陈虹，李蕊，宋富喜，等． 国外突发事件应急救援标准综述． 灾害学，2011，26( 3) : 133) ［4］ Deng Y F． Study on Pedestrian Evacuation Model for Accident Ｒe￾leasing Toxic Vapors ［Dissertation］． Beijing: University of Sci￾ence and Technology Beijing，2008 ( 邓云峰． 毒气泄露事故人员疏散模型及应用研究［学位论 文］． 北京: 北京科技大学，2008) ［5］ Tufekci S，Wallace W A． The emerging area of emergency man￾agement and engineering． IEEE Trans Eng Manage，1998，45 ( 2) : 103 ［6］ Gorge M． Crisis management best practice: where do we start from? Comput Fraud Secur，2006，2006( 6) : 10 ［7］ Xi X J，Dong W T，Guo Z F． A method for calculating safety dis￾tance of high-sulfide gas well in complex mountainous terrain． Chi￾na Saf Sci J，2009，19( 12) : 66 ( 席学军，董文彤，郭再富． 复杂山区地形高含硫气井安全防 护距离研究． 中国安全科学学报，2009，19( 12) : 66) ［8］ Liu J，Li J，Deng Y F． Design and implementation of the scene data acquisition and management system for major incident after logging of high risks gas field． J Saf Sci Technol，2011，7( 6) : 58 ( 刘晶，李竞，邓云峰． 三高气田钻完井重大事故现场监测数 据采集管理系统的设计与实现． 中国安全科学生产技术， 2011，7( 6) : 58) ［9］ Yang H C，Sun B． Optimization of evacuation based on PEＲT and shortest path theory． Fire Sci Technol，2011，30( 2) : 103 ( 杨海潮，孙冰． 基于 PEＲT 和最短路理论的人员疏散最优 化． 消防理论研究，2011，30( 2) : 103) ［10］ Xiao G Q，Wen L M，Chen B Z，et al． Shortest evacuation route on toxic leakage． J Northeast Univ Nat Sci，2001，22( 6) : 674 ( 肖国清，温丽敏，陈宝智，等． 毒气泄漏时的最佳疏散路 径． 东北大学学报: 自然科学版，2001，22( 6) : 674) ［11］ Gao Ｒ，Jiang Z A，Dong F，et al． Mathematical model and algo￾rithm of a dynamic optimum rescue route during mine fire time based on MapObject． J Univ Sci Technol Beijing，2008，30( 7) : 705 ( 高蕊，蒋仲安，董枫，等． 基于 MapObject 的动态最佳救灾 路线数学模型和算法． 北京科技大学学报，2008，30 ( 7) : 705) ［12］ He M C，Xiao Z Q，Li G F，et al． Ｒegional Engineering Disaster ＲMON Warning Integrated Management Systems and Applica￾tions． Beijing: China Architecture and Building Press，2012 ( 何满潮，肖志强，李国峰，等． 区域性工程灾害远程监控预 警一体化综合管理系统及应用． 北京: 中国建筑工业出版 社，2012) ［13］ Sun L，Zhao L D． Collaborative allocation problem of rescue sup￾plies under danger source diffusion． J Southeast Univ Nat Sci Ed， 2007，11( Suppl Ⅱ) : 367 ( 孙立，赵林度． 危险源扩散环境下救援物资协同调度问题． 东南大学学报: 自然科学版，2007，11( 增刊Ⅱ) : 367) ［14］ Niu H Ｒ，Li P，Shi T Y． Modeling and simulation on uncertainty shortest path problem in emergency resource dispatching． J Nan￾jing Univ Sci Technol Nat Sci，2009，33( Suppl) : 178 ( 牛宏睿，李平，史天运． 应急资源调度中最短路边权不确 定性问题的建模与仿真． 南京理工大学学报: 自然科学版， 2009，33( 增刊) : 178) ·541·

·542 北京科技大学学报 第36卷 [15]Zhang Y,Guo X F,Wang X F.Route choice for transporting ex- [19]Wei H,Pu Y,Li J.An approach to biobjective shortest path. igency succor materials.J Saf Environ,2006,6(3):51 Syst Eng,2005,23(7):113 (张毅，郭晓汾，王笑风.应急救援物资车辆运输线路的选 (魏航，蒲云，李军.一种求解双目标最短路的方法.系统工 择.安全与环境学报，2006,6(3)：51) 程，2005,23(7)：113) [16]Yu G,Yang J.On the robust shortest path problem.Comput 0]Hanke M,Halchenko Y O,Sederberg P B,et al.PyMVPA:a 0 per Res,1998,25(6):457 Python toolbox for multivariate pattern analysis of fMRI data. [17]Current J.Marsh M.Multiobjective transportation network design Neuroinformatics,2009,7(1):37 and routing problems:taxonomy and annotation.Eur J Oper Res, 21]Pan X T.Analytical Model Based on the Python Controls to 1993,65(1):4 Achiere [Dissertation].Beijing:China University of Geosci- [18]Current J,Revelie C,Cohon J.An interactive approach to iden- ences,2008 tify the best compromise solution for two objective shortest path (潘雪婷.基于Python的控件分析模型的实现[学位论文]. problems.Comput Oper Res,1990,17(2):187 北京：中国地质大学，2008)

北 京 科 技 大 学 学 报 第 36 卷 ［15］ Zhang Y，Guo X F，Wang X F． Ｒoute choice for transporting ex￾igency succor materials． J Saf Environ，2006，6( 3) : 51 ( 张毅，郭晓汾，王笑风． 应急救援物资车辆运输线路的选 择． 安全与环境学报，2006，6( 3) : 51) ［16］ Yu G，Yang J． On the robust shortest path problem． Comput Oper Ｒes，1998，25( 6) : 457 ［17］ Current J，Marsh M． Multiobjective transportation network design and routing problems: taxonomy and annotation． Eur J Oper Ｒes， 1993，65( 1) : 4 ［18］ Current J，Ｒevelie C，Cohon J． An interactive approach to iden￾tify the best compromise solution for two objective shortest path problems． Comput Oper Ｒes，1990，17( 2) : 187 ［19］ Wei H，Pu Y，Li J． An approach to biobjective shortest path． Syst Eng，2005，23( 7) : 113 ( 魏航，蒲云，李军． 一种求解双目标最短路的方法． 系统工 程，2005，23( 7) : 113) ［20］ Hanke M，Halchenko Y O，Sederberg P B，et al． PyMVPA: a Python toolbox for multivariate pattern analysis of fMＲI data． Neuroinformatics，2009，7( 1) : 37 ［21］ Pan X T． Analytical Model Based on the Python Controls to Achieve ［Dissertation］． Beijing: China University of Geosci￾ences，2008 ( 潘雪婷． 基于 Python 的控件分析模型的实现［学位论文］． 北京: 中国地质大学，2008) ·542·