基于避险设施的火灾救援及避灾路线算法

第36卷第7期 北京科技大学学报 Vol.36 No.7 2014年7月 Journal of University of Science and Technology Beijing Jul.2014 基于避险设施的火灾救援及避灾路线算法 詹子娜”，金龙哲2区，白楠”，王奕” 1)北京科技大学土木与环境工程学院，北京1000832)矿山避险技术研究中心，北京100083 ☒通信作者，E-mail:lzim@ustb.cdu.cm 摘要以VC#.net、SQL Server20O8和地理信息系统为平台，对矿井地图进行了具有地理属性开发的研究，建立了图形库、 数据库、方法库和知识库，并构建了基于避险设施的矿井火灾应急救援系统。对矿井火灾进行了实时在线模拟，分析和预测 了火灾动态发展趋势，实现了矿井火灾烟流传播和最佳避灾路线的动态可视化显示功能。引入安全性、通行效率等因素对灾 后巷道通行能力的变化进行修正，制定了基于避险设施的最优避灾路线选择原则和“理想一可行一逃生”等级路线。利用堆 栈数据结构对Dijkstr算法进行改进，提高了在线运算速度。该系统已应用到潞安常村煤矿。 关键词矿山火灾：矿山数援：计算机模拟：路径算法：最佳路线：通行能力 分类号TD77:X936 Fire rescue and optimal escape route algorithm based on refuge chambers ZHAN Zi--na”,JIN Long=he2,BAl Nan”,WANG Yi 1)School of Civil and Environmental Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Mine Emergency Technology Research Center.Beijing 100083,China Corresponding author,E-mail:Izjin@ustb.edu.cn ABSTRACT Based on platforms including VC#.net,SQL Server 2008 and geographic information systems (GIS),the mine map was developed with geographical attributes.A rescue system based on refuge chambers during the mine fire period was constructed after the graphics library,database,method library and knowledge base were established.Due to real time simulation of mine fire,analysis and prediction of its dynamic trend,the rescue system achieved a dynamic visual display of fire plume spreading and the optimal escape route based on refuge chambers in an underground coal mine.At the same time,roadway safety and traffic efficiency were introduced to amend the traffic capacity of post-disaster roadways.The principles for selecting the optimal rescue route based on refuge chambers were determined,and the "ideal-viable-escape"level of escape routes was divided.Since the optimal escape route was calculated using Dijkstra algorithm which was improved by the stack data structure,the computing speed of the rescue system online increased. The rescue system has been applied to Changcun Coal Mine owed to Lu'an Group. KEY WORDS mine fires;mine rescue;computer simulation:routing algorithms:optimal routing:traffic capacity 矿井火灾引起的恶劣复杂环境条件极易造成通 许多学者进行了大量的研究，并取得了许多成 风系统的风流紊乱和结构变化，往往造成更大的人 果-习。国内学者“-针对矿井火灾烟流或高温对 员伤亡和损失。仅凭主观判断矿井火灾情况，不能 避灾路线判别、巷道当量长度及解算方法进行了深 及时科学地指挥井下人员避险和救灾。只有使用计 入分析和建模，但系统应用可操作性较差，参数选择 算机模拟的方法，才能获得较全面的火灾时期风流 繁琐。国外更注重于救援机制和最短路径算法的研 状态和巷道状态及通行能力，计算最优的避灾路线， 究，以降低网络解算复杂度，矿井实际应用中更偏重 从而为救灾决策提供依据四。在20世纪90年代， 于前期应急培训演练工作和避灾路径的规划，灾后 收稿日期：2013-1014 基金项目：“十二五”国家科技支撑计划基金资助项目(2012BAK09B00) DOI:10.13374/j.issn1001-053x.2014.07.017:http://journals.ustb.edu.cn

第 36 卷 第 7 期 2014 年 7 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 7 Jul． 2014 基于避险设施的火灾救援及避灾路线算法 詹子娜1) ，金龙哲1，2) ，白 楠1) ，王 奕1) 1) 北京科技大学土木与环境工程学院，北京 100083 2) 矿山避险技术研究中心，北京 100083  通信作者，E-mail: lzjin@ ustb． edu． cn 摘 要 以 VC#． net、SQL Server 2008 和地理信息系统为平台，对矿井地图进行了具有地理属性开发的研究，建立了图形库、 数据库、方法库和知识库，并构建了基于避险设施的矿井火灾应急救援系统。对矿井火灾进行了实时在线模拟，分析和预测 了火灾动态发展趋势，实现了矿井火灾烟流传播和最佳避灾路线的动态可视化显示功能。引入安全性、通行效率等因素对灾 后巷道通行能力的变化进行修正，制定了基于避险设施的最优避灾路线选择原则和“理想—可行—逃生”等级路线。利用堆 栈数据结构对 Dijkstra 算法进行改进，提高了在线运算速度。该系统已应用到潞安常村煤矿。 关键词 矿山火灾; 矿山救援; 计算机模拟; 路径算法; 最佳路线; 通行能力 分类号 TD 77; X 936 Fire rescue and optimal escape route algorithm based on refuge chambers ZHAN Zi-na1) ，JIN Long-zhe1，2)  ，BAI Nan1) ，WANG Yi1) 1) School of Civil and Environmental Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Mine Emergency Technology Ｒesearch Center，Beijing 100083，China  Corresponding author，E-mail: lzjin@ ustb． edu． cn ABSTＲACT Based on platforms including VC#． net，SQL Server 2008 and geographic information systems ( GIS) ，the mine map was developed with geographical attributes． A rescue system based on refuge chambers during the mine fire period was constructed after the graphics library，database，method library and knowledge base were established． Due to real time simulation of mine fire，analysis and prediction of its dynamic trend，the rescue system achieved a dynamic visual display of fire plume spreading and the optimal escape route based on refuge chambers in an underground coal mine． At the same time，roadway safety and traffic efficiency were introduced to amend the traffic capacity of post-disaster roadways． The principles for selecting the optimal rescue route based on refuge chambers were determined，and the“ideal-viable-escape”level of escape routes was divided． Since the optimal escape route was calculated using Dijkstra algorithm which was improved by the stack data structure，the computing speed of the rescue system online increased． The rescue system has been applied to Changcun Coal Mine owed to Lu’an Group． KEY WOＲDS mine fires; mine rescue; computer simulation; routing algorithms; optimal routing; traffic capacity 收稿日期: 2013--10--14 基金项目: “十二五”国家科技支撑计划基金资助项目( 2012BAK09B00) DOI: 10． 13374 /j． issn1001--053x． 2014． 07． 017; http: / /journals． ustb． edu． cn 矿井火灾引起的恶劣复杂环境条件极易造成通 风系统的风流紊乱和结构变化，往往造成更大的人 员伤亡和损失。仅凭主观判断矿井火灾情况，不能 及时科学地指挥井下人员避险和救灾。只有使用计 算机模拟的方法，才能获得较全面的火灾时期风流 状态和巷道状态及通行能力，计算最优的避灾路线， 从而为救灾决策提供依据［1］。在 20 世纪 90 年代， 许多学者进行了大量的研究，并取得了许多成 果［2 － 3］。国内学者［4 － 6］针对矿井火灾烟流或高温对 避灾路线判别、巷道当量长度及解算方法进行了深 入分析和建模，但系统应用可操作性较差，参数选择 繁琐。国外更注重于救援机制和最短路径算法的研 究，以降低网络解算复杂度，矿井实际应用中更偏重 于前期应急培训演练工作和避灾路径的规划，灾后

第7期 詹子娜等：基于避险设施的火灾救援及避灾路线算法 ·967· 因素的实时影响并未考虑，避灾路线选择的智能化 自动形成包括应急预案、应急响应级别、救援力量、 现场适用性不强则。现今随着煤矿“六大系统” 救援物资调度等应急救援方案。火情及救援方案的 的全面构建，紧急避险在全国矿井的逐步推进可， 判断主要通过对历史火灾处理和实践丰富的专家经 给矿工提供了三级避险安全保障体系@，为最大程 验的提炼，具有较强的可操作性和实用性。 度上发挥紧急避险系统的作用和功能，并在最短时 应急预案 间内确定人员到紧急避险设施内的最佳避灾路线成 通风系统 图形数据 为矿井应急避险救灾亟待解决的重要问题。 监测监控 监测信息 应急响应 本文针对全国首个紧急避险系统示范矿—常 人员定位 易燃物信息 专家库 村煤矿，着重阐述了基于紧急避险设施的矿井火灾 紧急避险设施 数学模型 救援力量和物资 应急救援系统构建的理念和功能，以及基于避险设 图形库 数据库 方法库 知识库 施的最佳避灾路线选择的原则和准则，并利用堆数 救援决策系统 据结构对Dijkstra算法进行了改进和仿真模拟 人机交互界面 分析。 用户 1矿井火灾救援系统的构建 图1救援系统结构图 Fig.1 Structure of the rescue system 1.1矿井火灾救援系统的理念 矿井火灾应急救援系统是基于紧急避险系统的 1.2救援系统功能的实现 构建与规划对接了矿井“六大系统”平台，形成了煤 救援系统的功能主要为实现火灾计算机模拟最 矿新型安全防护体系，革新了传统应急救援与避险 佳避灾与救援避险的动态选择进行开发和编码，为 的概念，救援系统结构如图1所示。 灾后控制方案的制定提供依据。利用地理信息系统 (1)图形库。针对井下工作面不断变化的特 (GS)的强大空间分析功能和扩展性的，开发并实 点，为提高地面决策人员对井下网络系统及火灾发 现地理属性分布数据的采集、储存、管理、运算、分析 展趋势的认知水平，利用VC#语言开发了具有地理 和显示功能，并采用非稳态模拟方法中的时间步长 属性的交互式图形可视化系统。该系统同时实现了 法对火灾时期风网参数随时间的变化规律进行跟踪 在线和后台同步绘制、修改和上传的功能，并以此建 和分析。这里主要采用了烟流温度、火风压等数学 立了井下通风系统、紧急避险系统、井下人员定位系 模型进行网络中风流计算和迭代)。关于数学模 统、消防和救援设备及设施、供水施救管路、可燃物 型不再赘述，模拟流程与仿真结果如图2和图3 和安全监测监控系统等位置的图层库和关联关系。 所示。 实现与绘制软件Auto CAD和ArcGIS的互联。 火灾模拟 火源位置确定 (2)数据库。为满足井下正常时期日常管理的 需求，建立了通风网络数据库，存储其通风网络管线 通风网络解算 异常数据和 状态分析与推理 的风网参数和巷道通行能力参数。针对火灾特殊时 风流 期，为满足火灾发展的动态特殊要求，利用数据库 逆转 监测系统 SQL Server2008开发了具有存储、显示、修改、导入 否 人员位置 及与ArcGIS具有兼容性的数据库。数据根据系统 火灾能响范围显示 设计的不同模块的安排，在计算机上不同功能区域 避险设施布置 能够直接显示。 最佳避灾路线选择 改进Dijkstra (3)方法库。本系统为解决井下火灾的判断的 图2火灾救援系统模拟流程图 模糊性，基于井下监测监控系统，采用基于规则的产 Fig.2 Flow chart of fire rescue system simulation 生和推理方法)，通过监测监控传输的异常参数数 据，判断火源位置，对灾情进行预警警报，并根据数 矿井火灾模拟功能的实现，首先用户界面会根 学模型进行计算描述，包括风网解算、火灾模拟计算 据监测监控系统传输的数据和异常状态进行判断和 以及基于避险设施的最佳避灾路线模型。 演绎分析，确定可能的火源位置，并实现火灾的音频 (4)知识库。主要根据火灾事故模拟的结果， 预警和报警。用户根据计算机提示的火源位置，只 判断火灾灾情的影响程度。利用专家推理的方法， 需用鼠标在系统图上左键一点，并在功能菜单上选

第 7 期 詹子娜等: 基于避险设施的火灾救援及避灾路线算法 因素的实时影响并未考虑，避灾路线选择的智能化 现场适用性不强［7 － 8］。现今随着煤矿“六大系统” 的全面构建，紧急避险在全国矿井的逐步推进［9］， 给矿工提供了三级避险安全保障体系［10］，为最大程 度上发挥紧急避险系统的作用和功能，并在最短时 间内确定人员到紧急避险设施内的最佳避灾路线成 为矿井应急避险救灾亟待解决的重要问题。 本文针对全国首个紧急避险系统示范矿———常 村煤矿，着重阐述了基于紧急避险设施的矿井火灾 应急救援系统构建的理念和功能，以及基于避险设 施的最佳避灾路线选择的原则和准则，并利用堆数 据结 构 对 Dijkstra 算法进行了改进和仿真模拟 分析。 1 矿井火灾救援系统的构建 1. 1 矿井火灾救援系统的理念 矿井火灾应急救援系统是基于紧急避险系统的 构建与规划对接了矿井“六大系统”平台，形成了煤 矿新型安全防护体系，革新了传统应急救援与避险 的概念，救援系统结构如图 1 所示。 ( 1) 图形库。针对井下工作面不断变化的特 点，为提高地面决策人员对井下网络系统及火灾发 展趋势的认知水平，利用 VC#语言开发了具有地理 属性的交互式图形可视化系统。该系统同时实现了 在线和后台同步绘制、修改和上传的功能，并以此建 立了井下通风系统、紧急避险系统、井下人员定位系 统、消防和救援设备及设施、供水施救管路、可燃物 和安全监测监控系统等位置的图层库和关联关系。 实现与绘制软件 Auto CAD 和 ArcGIS 的互联。 ( 2) 数据库。为满足井下正常时期日常管理的 需求，建立了通风网络数据库，存储其通风网络管线 的风网参数和巷道通行能力参数。针对火灾特殊时 期，为满足火灾发展的动态特殊要求，利用数据库 SQL Server 2008 开发了具有存储、显示、修改、导入 及与 ArcGIS 具有兼容性的数据库。数据根据系统 设计的不同模块的安排，在计算机上不同功能区域 能够直接显示。 ( 3) 方法库。本系统为解决井下火灾的判断的 模糊性，基于井下监测监控系统，采用基于规则的产 生和推理方法［11］，通过监测监控传输的异常参数数 据，判断火源位置，对灾情进行预警警报，并根据数 学模型进行计算描述，包括风网解算、火灾模拟计算 以及基于避险设施的最佳避灾路线模型。 ( 4) 知识库。主要根据火灾事故模拟的结果， 判断火灾灾情的影响程度。利用专家推理的方法， 自动形成包括应急预案、应急响应级别、救援力量、 救援物资调度等应急救援方案。火情及救援方案的 判断主要通过对历史火灾处理和实践丰富的专家经 验的提炼，具有较强的可操作性和实用性。 图 1 救援系统结构图 Fig． 1 Structure of the rescue system 1. 2 救援系统功能的实现 救援系统的功能主要为实现火灾计算机模拟最 佳避灾与救援避险的动态选择进行开发和编码，为 灾后控制方案的制定提供依据。利用地理信息系统 ( GIS) 的强大空间分析功能和扩展性［12］，开发并实 现地理属性分布数据的采集、储存、管理、运算、分析 和显示功能，并采用非稳态模拟方法中的时间步长 法对火灾时期风网参数随时间的变化规律进行跟踪 和分析。这里主要采用了烟流温度、火风压等数学 模型进行网络中风流计算和迭代［13］。关于数学模 型不再赘述，模拟流程与仿真结果如图 2 和图 3 所示。 图 2 火灾救援系统模拟流程图 Fig． 2 Flow chart of fire rescue system simulation 矿井火灾模拟功能的实现，首先用户界面会根 据监测监控系统传输的数据和异常状态进行判断和 演绎分析，确定可能的火源位置，并实现火灾的音频 预警和报警。用户根据计算机提示的火源位置，只 需用鼠标在系统图上左键一点，并在功能菜单上选 · 769 ·

·968 北京科技大学学报 第36卷 避险人员提供一道生命保障的防线 (2)建立人员就近避险的制度。基于地理信息 系统建立人员区域管理属性，规定：火灾时工作面人 员进入可移动式救生舱；工作面其他人员及大巷内 人员进入避难硐室；非火灾影响的采区工作人员尽 可能逃生出井。 (3)研究火灾时高温、有毒有害气体，烟流传播 范围对巷道可通行能力的影响的，建立巷道安全性 和通行效率对巷道当量长度影响的权重因子k,对 图3井下火灾模拟及最佳避灾路线仿真应用 Fig.3 Simulation of mine fire and the optimum escape routes 巷道灾后的当量长度进行修正。巷道当量长度的计 算由于篇幅有限，不再赘述。各因素影响准则如下 择火源燃烧类型和模拟总时间，计算机即可对井下 所述。 火灾进行仿真数学模拟，分析火灾不同时刻下火灾 ①巷道安全的定义即选择安全条件最好的巷 烟流污染巷道的温度分布和风流状态。本程序界面 道。井下巷道通行安全受到火灾的影响，使其原本 的操作简单易懂，克服了以往计算机模拟火灾时要 可安全通行的巷道因烟流的蔓延而无法通行，规定： 输入发火巷道始末节点的参数要求，提高了计算机 灾前原本可完全通行的巷道安全系数a=1,不可通 火灾模拟时复杂网络的计算速度。本系统使救援指 行的巷道安全系数a=0:而灾后高温（大于60℃）、 挥人员对井下火灾灾情有直观清晰的认识，并为应 高浓度有毒有害气体(C0监测体积分数于0.08%) 急避险和救援工作的开展和指挥提供了支持。 污染巷道α=0，即非常危险不能通行：有危险可通 2 避灾路径选择原则和算法改进 行的巷道a=0.3:安全可通行的巷道a=0.7。 ②针对巷道温度对人员行走能力的影响，依次 2.1基于避险设施的避灾路线选择原则制定 以30℃和60℃为界限，划分为理想一可行一逃生 矿井火灾时期避灾路线的选择受到烟流污染范 的三级逃生路线。 围、烟流温度、有毒有害气体及巷道特性的影响，要 ③巷道通行效率是避险撤离时最短时间要求的 结合路径安全性、通行效率、灾后动态变化等多因素 特征值。巷道通行效率受到巷道高度、宽度、照明、 进行求解判断。本文着眼于紧急避险系统的全矿井 坡度、障碍物、运输工具、烟流等因素的影响。利用 规划，结合紧急避险设施布置的原则，系统地制定矿 不同条件下不同行走姿势的行进速度作为衡量参数 井火灾时期最佳避灾路线选择的原则。 进行建模，以自由行走作为参考标准，规定通行效率 紧急避险系统的构建克服了以往避灾路线单一 b。=1,其他状态按照行走速度的比例进行计算，即 化的问题，不单单地从进风巷道内选择。在紧急情 况下可提高回风巷道内避险人员的逃生几率，增加 如=上=也，其中b,为非自由行走条件下通行效 by bi uo 避灾路线可选择性和安全性。 率，和山1分别为自由和非自由状态下行走速度。 (1)建立正确的避险理念。遵循“升井最安全， 以常村煤矿矿工佩戴自救器行走测定为例，结果如 避险设施内避灾”的原则，避险系统在灾变时需为 表1所示。 表1常村煤矿井下人员通行效率 Table 1 Traffic efficiency of miners in Changcun Coal Mine 行走姿势 行进速度/(ms1) 通行效率 行走姿势 行进速度/(m·sl) 通行效率 爬行 0.20 5.00 熟悉黑暗中 0.60 1.70 弯腰行走 0.45 2.00 陌生黑暗中 0.20 5.00 自由行走 1.00 1.00 烟雾中 0.24 4.00 小跑 2.50 0.40 运输工具 4.00 0.25 快跑 3.80 0.25 2.2最佳避灾路线算法的改进 或出井口和矿工位置求解两点之间满足某些条件时 本文考虑的最佳避灾路线是基于井下避险设施 的最短路径a。Dijkstra算法是求解网络中两节点

北 京 科 技 大 学 学 报 第 36 卷 图 3 井下火灾模拟及最佳避灾路线仿真应用 Fig． 3 Simulation of mine fire and the optimum escape routes 择火源燃烧类型和模拟总时间，计算机即可对井下 火灾进行仿真数学模拟，分析火灾不同时刻下火灾 烟流污染巷道的温度分布和风流状态。本程序界面 的操作简单易懂，克服了以往计算机模拟火灾时要 输入发火巷道始末节点的参数要求，提高了计算机 火灾模拟时复杂网络的计算速度。本系统使救援指 挥人员对井下火灾灾情有直观清晰的认识，并为应 急避险和救援工作的开展和指挥提供了支持。 2 避灾路径选择原则和算法改进 2. 1 基于避险设施的避灾路线选择原则制定 矿井火灾时期避灾路线的选择受到烟流污染范 围、烟流温度、有毒有害气体及巷道特性的影响，要 结合路径安全性、通行效率、灾后动态变化等多因素 进行求解判断。本文着眼于紧急避险系统的全矿井 规划，结合紧急避险设施布置的原则，系统地制定矿 井火灾时期最佳避灾路线选择的原则。 紧急避险系统的构建克服了以往避灾路线单一 化的问题，不单单地从进风巷道内选择。在紧急情 况下可提高回风巷道内避险人员的逃生几率，增加 避灾路线可选择性和安全性。 ( 1) 建立正确的避险理念。遵循“升井最安全， 避险设施内避灾”的原则，避险系统在灾变时需为 避险人员提供一道生命保障的防线［14］。 ( 2) 建立人员就近避险的制度。基于地理信息 系统建立人员区域管理属性，规定: 火灾时工作面人 员进入可移动式救生舱; 工作面其他人员及大巷内 人员进入避难硐室; 非火灾影响的采区工作人员尽 可能逃生出井。 ( 3) 研究火灾时高温、有毒有害气体，烟流传播 范围对巷道可通行能力的影响［15］，建立巷道安全性 和通行效率对巷道当量长度影响的权重因子 k，对 巷道灾后的当量长度进行修正。巷道当量长度的计 算由于篇幅有限，不再赘述。各因素影响准则如下 所述。 ①巷道安全的定义即选择安全条件最好的巷 道。井下巷道通行安全受到火灾的影响，使其原本 可安全通行的巷道因烟流的蔓延而无法通行，规定: 灾前原本可完全通行的巷道安全系数 a = 1，不可通 行的巷道安全系数 a = 0; 而灾后高温( 大于 60 ℃ ) 、 高浓度有毒有害气体( CO 监测体积分数于 0. 08% ) 污染巷道 a = 0，即非常危险不能通行; 有危险可通 行的巷道 a = 0. 3; 安全可通行的巷道 a = 0. 7。 ②针对巷道温度对人员行走能力的影响，依次 以 30 ℃ 和 60 ℃ 为界限，划分为理想—可行—逃生 的三级逃生路线。 ③巷道通行效率是避险撤离时最短时间要求的 特征值。巷道通行效率受到巷道高度、宽度、照明、 坡度、障碍物、运输工具、烟流等因素的影响。利用 不同条件下不同行走姿势的行进速度作为衡量参数 进行建模，以自由行走作为参考标准，规定通行效率 b0 = 1，其他状态按照行走速度的比例进行计算，即 b0 b1 = 1 b1 = u1 u0 ，其中 b1 为非自由行走条件下通行效 率，u0和 u1分别为自由和非自由状态下行走速度。 以常村煤矿矿工佩戴自救器行走测定为例，结果如 表 1 所示。 表 1 常村煤矿井下人员通行效率 Table 1 Traffic efficiency of miners in Changcun Coal Mine 行走姿势 行进速度/( m·s － 1 ) 通行效率 行走姿势 行进速度/( m·s － 1 ) 通行效率 爬行 0. 20 5. 00 熟悉黑暗中 0. 60 1. 70 弯腰行走 0. 45 2. 00 陌生黑暗中 0. 20 5. 00 自由行走 1. 00 1. 00 烟雾中 0. 24 4. 00 小跑 2. 50 0. 40 运输工具 4. 00 0. 25 快跑 3. 80 0. 25 2. 2 最佳避灾路线算法的改进 本文考虑的最佳避灾路线是基于井下避险设施 或出井口和矿工位置求解两点之间满足某些条件时 的最短路径［16］。Dijkstra 算法是求解网络中两节点 · 869 ·

第7期 詹子娜等：基于避险设施的火灾救援及避灾路线算法 ·969· 间最短路径的最基本和使用最广泛的算法，传统D- 内燃烧状况，使部分巷道通行能力发生改变，造成了 jkstra算法是贪心的搜索解算；但由于矿井系统网络 高温和有毒气体环境。计算机根据火灾污染的情 的复杂性，导致解算重复度较高和时间较长。依据 况，通过对巷道通行安全性和通行效率的计算，得到 井下最佳路径的选择原则，对Dijkstra算法进行改 巷道灾后权重k=b/a,并对最短路径长度进行修正 进，进行无向有权求解。改进思路和方法为：①计算 d=min(d+0,Cm),救援系统仿真模拟结果如图3 时只考虑从矿工位置到避险设施或出井口之间的最 所示。利用ArcGIS的Weh服务和分析技术，实现 短路径：②将最短路径问题分解为始末两节点同时 火灾污染范围和最佳避灾路线的动态可视化显示功 进行求解；③利用数据结构“堆”的特性和方法， 能，并在数秒内可同时实现某时刻下不同位置人员 简化节点和分支的标记，优化求解步骤，降低其计算 基于避险设施的最佳避灾路线。通过GS图层的关 重复度以提高计算速度，可将其复杂度降为O((m 联性设定，可实现矿工有序正确的基于救生舱或避 +n)lgn)2。基于堆结构的算法改进，可大大避免 难酮室的避灾路线的选择。救援系统的开发在一定 全网络分支的搜索标记，可实现计算机Wb在线的 程度上为矿上井下救援和避险提供了动态实时的情 快速解算及最佳路线的动态显示。 景再现，给救援避险和决策指挥提供科学的依据。 采取面向对象的方法通过对网络分析所用到的 具体解算过程以位置7人员的逃生路线为例， 地理实体属性进行面向对象封装以实现Dijkstra算 N3采区井巷网络如图4和图5所示。虚线表示火 法的运算和最短路径的可视化显示。 灾后受到高温和有毒有害气体影响而无法通行的巷 给定带权无向网络图D,n个节点，m条边，C 道；带括号的数字为巷道通行效率。 表示i与j两节点间的路径长度。当节点i=j,C,= 2) 0;若i与j不相连时，C=,用d,表示i与j两节点 ④0) ⑤ 间的最短路径。特定源点v和终点u,求v到u的最 ① (1) ⑦ 短路径。构建堆矩阵heap,和heap2,及索引矩阵in- 6 dex,最短路径树SPTree。算法主要步骤如下： 2 ①输入最短路径的起始节点u和终结点v。 O ②初始化堆结构heap,和heap2,其元素分别为 ⑥05 ⑧ ① ④ 起点v和终点w的相连接点，并按照其d的大小依 次堆栈排序，主要根据二维节点数组的权值C], 图4井下N3采区灾前井巷网络 Fig.4 Pre-disaster roadway network in the mine 调用Heap-insert方法实现初始化操作。 ③判断heap,和heap2的堆顶元素是否相同，若 (2) ④ 相同转到⑥：否则，转到④。 ④取heap,和heap2内堆顶元素i和j,调用De- ① crease-Key方法将其从栈内删除，分别对heap,和 ⑩ ⑨ )6 heap2堆内其他元素heap1(x)和heap2(y)进行修正， ③ 满足da=min(Ca'dn.+Ca），d=min(C,d+ 心 / 0.58 ⑦ C)。 ④ (6) ⑤利用堆顶元素i和j对其相连的非堆内元素s 图5井下N3采区灾后井巷网络 和t进行修正，取de.=min(Ces,dn.+Ct),dn=min Fig.5 Disaster roadway network in the mine (Ca'd,+Cg),通过Heap-insert方法将其分别加入 到heap,和heap,堆结构内，并按照d.和d,的大小 设井下人员从2号出发，需到达16号处的避险 对堆内元素依此排序，转到③。 设施，按照避灾路线选择原则和改进的dijkstra算法 ⑥若i=j,则v到w的最短路径为d=min 进行仿真运算，如表2所示。N3永久避险设施的构 (Cw,d.+C,),输出最短路径树SPTree,并退出。 建，增加了回风巷内监测人员通行回风巷进入避难 酮硐室而避险几率，在无火灾下，回风大巷2中的监测 3仿真模拟分析与应用 人员可直接通过下风向的大巷而进入避难硐室内， 通过常村煤矿N3采区的火灾模拟，模拟节点 此状态下路径长度最短，但引入通行安全效率权重 11下方向分支（胶带运输机巷道）50m胶带20min 后，巷道的通行时间较长，通过优化后，位置7的监

第 7 期 詹子娜等: 基于避险设施的火灾救援及避灾路线算法 间最短路径的最基本和使用最广泛的算法，传统 Di￾jkstra 算法是贪心的搜索解算; 但由于矿井系统网络 的复杂性，导致解算重复度较高和时间较长。依据 井下最佳路径的选择原则，对 Dijkstra 算法进行改 进，进行无向有权求解。改进思路和方法为: ①计算 时只考虑从矿工位置到避险设施或出井口之间的最 短路径; ②将最短路径问题分解为始末两节点同时 进行求解; ③利用数据结构“堆”的特性和方法［17］， 简化节点和分支的标记，优化求解步骤，降低其计算 重复度以提高计算速度，可将其复杂度降为 O( ( m + n) lgn) /2。基于堆结构的算法改进，可大大避免 全网络分支的搜索标记，可实现计算机 Web 在线的 快速解算及最佳路线的动态显示。 采取面向对象的方法通过对网络分析所用到的 地理实体属性进行面向对象封装以实现 Dijkstra 算 法的运算和最短路径的可视化显示。 给定带权无向网络图 D，n 个节点，m 条边，Cij 表示 i 与 j 两节点间的路径长度。当节点 i = j，Cij = 0; 若 i 与 j 不相连时，Cij = ∞ ，用 dij表示 i 与 j 两节点 间的最短路径。特定源点 v 和终点 u，求 v 到 u 的最 短路径。构建堆矩阵 heap1和 heap2，及索引矩阵 in￾dex，最短路径树 SPTree。算法主要步骤如下: ①输入最短路径的起始节点 u 和终结点 v。 ②初始化堆结构 heap1和 heap2，其元素分别为 起点 v 和终点 w 的相连接点，并按照其 dij的大小依 次堆栈排序，主要根据二维节点数组的权值 C［i］， 调用 Heap-insert 方法实现初始化操作。 ③判断 heap1和 heap2的堆顶元素是否相同，若 相同转到⑥; 否则，转到④。 ④取 heap1和 heap2内堆顶元素 i 和 j，调用 De￾crease-Key 方法将其从栈内删除，分别对 heap1 和 heap2堆内其他元素 heap1 ( x) 和 heap2 ( y) 进行修正， 满足 dvx = min( Cvx，dvi + Cxi ) ，dwy = min( Cwy，dvj + Cyj) 。 ⑤利用堆顶元素 i 和 j 对其相连的非堆内元素 s 和 t 进行修正，取 dvs = min( Cvs，dvi + Csi ) ，dwt = min ( Cwt，dvj + Ctj) ，通过 Heap-insert 方法将其分别加入 到 heap1和 heap2堆结构内，并按照 dvx和 dwy的大小 对堆内元素依此排序，转到③。 ⑥若 i = j，则 v 到 w 的最短路径为 dvw = min ( Cvw，dvi + Cvj) ，输出最短路径树 SPTree，并退出。 3 仿真模拟分析与应用 通过常村煤矿 N3 采区的火灾模拟，模拟节点 11 下方向分支( 胶带运输机巷道) 50 m 胶带 20 min 内燃烧状况，使部分巷道通行能力发生改变，造成了 高温和有毒气体环境。计算机根据火灾污染的情 况，通过对巷道通行安全性和通行效率的计算，得到 巷道灾后权重 k = b / a，并对最短路径长度进行修正 d = min( dvw + wijCvw ) ，救援系统仿真模拟结果如图 3 所示。利用 ArcGIS 的 Web 服务和分析技术，实现 火灾污染范围和最佳避灾路线的动态可视化显示功 能，并在数秒内可同时实现某时刻下不同位置人员 基于避险设施的最佳避灾路线。通过 GIS 图层的关 联性设定，可实现矿工有序正确的基于救生舱或避 难硐室的避灾路线的选择。救援系统的开发在一定 程度上为矿上井下救援和避险提供了动态实时的情 景再现，给救援避险和决策指挥提供科学的依据。 具体解算过程以位置 7 人员的逃生路线为例， N3 采区井巷网络如图 4 和图 5 所示。虚线表示火 灾后受到高温和有毒有害气体影响而无法通行的巷 道; 带括号的数字为巷道通行效率。 图 4 井下 N3 采区灾前井巷网络 Fig． 4 Pre-disaster roadway network in the mine 图 5 井下 N3 采区灾后井巷网络 Fig． 5 Disaster roadway network in the mine 设井下人员从 2 号出发，需到达 16 号处的避险 设施，按照避灾路线选择原则和改进的 dijkstra 算法 进行仿真运算，如表 2 所示。N3 永久避险设施的构 建，增加了回风巷内监测人员通行回风巷进入避难 硐室而避险几率，在无火灾下，回风大巷 2 中的监测 人员可直接通过下风向的大巷而进入避难硐室内， 此状态下路径长度最短，但引入通行安全效率权重 后，巷道的通行时间较长，通过优化后，位置 7 的监 · 969 ·

·970· 北京科技大学学报 第36卷 测人员应该选择上行而进入皮顺巷至避难硐室内为 法实现了基于避险设施的人员最佳避灾路线的动态 最佳路径。可见，巷道路径最短的避灾路线并不一 可视化功能，为煤矿应急管理和应急救援指挥提供 定是最安全、疏散最有效的路线。在发生火灾后，随 了一种新型的信息化、智能化的平台。 着时间的延续和烟流的蔓延，回风大巷会逐渐被烟 流污染，灾前规划的路径己不安全或无法通行，重新 参考文献 考虑灾后巷道通行安全效率，位置7的监测人员应 [1]Wang L D,Zhang R X,Zhao Z G,et al.Emergency rescue com- mand and management information system for coal mine.J Ligon- 及时下风向行走而进入轨顺大巷内至避险设施，同 ing Tech Univ,2006,25(5):655 时满足了安全性最好、通行时间最少的条件。所以 (王铃丁，张瑞新，赵志刚，等.煤矿应急救援指挥与管理信 在没有考虑灾后巷道安全通行性和通行效率的因素 息系统.辽宁工程技术大学学报，2006,25(5)：655) 下，所求得路线并非最佳避灾路线。 ] Li Y H,Zhang R W,Bi Y F,et al.Research and application of decision-making system in mine fire.Sof Coal Mines,2012,43 表2仿真模拟结果与分析 (3):15 Table 2 Simulation results and analysis (李英华，张人伟，毕岩峰，等。矿井火灾决策系统的研究及 状态 最佳路径 结果分析 应用.煤矿安全，2012,43(3)：15) 灾前 2-3-59-16 路径最短 E Cheng W M,Yao Y J,Wu L R,et al.Fluent-ased numerical 灾前优化2一11一13一14一15一16 通行时间最少 simulation of temperature and concentration during mine fire.Saf Coal Mine,2011,43(2):20 灾后 2-3-59—16 路径不正确，无法通行 (程卫民，姚玉静，吴立荣，等.基于Fumt的矿井火灾时期 灾后优化 2—46-89-16 安全性最好，通行时间最少 温度及浓度分布数值模拟.煤矿安全，2011,43(2)：20) [4 Wang D M,Wang X S,Cui G.Travel ability of shaft and roadway 综上所述，本文制定的基于避险设施的最佳避 in a mine fire hazard and selection of optimal rescue and escape 灾路线原则，在一定程度上弥补了灾后主要因素对 routes.J China Coal Soc,1994,19(1)58 巷道通行性的影响，在平时应急培训演练及灾时避 (王德明，王省身，崔岗.矿井火灾时期井巷可通行性及选择 险救援中可为指挥人员救援决策和最佳避险路线制 最佳救灾与避灾路线的研究.煤炭学报，1994,19(1)：58) [5] Li H S.Improvement on Control Technology and Simulation on Air- 定奠定了基础，为提高矿山应急救援水平和效率提 Alow Status in Fire Period [Dissertation].Beijing:Beijing Gradu- 供科学的方法。 ate School of China University of Mining,1995 (李湖生.矿井火灾时期风流状态模拟与优化控制技术[学位 4结论 论文].北京：中国矿业大学北京研究生部，1995) (1)与以往的一般专家系统相比，矿井火灾救 [6]Jia JZ,Liu J,Zhao Q L.Study of mine fire rescue decision sup- 援决策系统引入了监测监控演绎推理方法，更为强 port system for No.2 mine area of Jinchuan Company.China Saf Sai,2006,16(4):131 调其实际应用价值和可操作性，能够使人机相互补 (贾进章，刘剑，赵千里.金川公司二矿区矿井火灾救灾决策 充和优化，使决策者掌握更为符合实际的信息而进 支持系统研究.中国安全科学学报，2006,16(4)：131) 行指挥。 ] Barker-read G R,Li H.Automatic selection of safe egress routes (2)本文探索性地利用GIS技术，建立具有地 away from underground fires.Min Sci Technol,1989,9(3):289 [8]Jalali E,Noroozi M.Determination of the optimal escape routes 理信息的空间物理属性和数据属性的地图和图层关 of underground mine networks in emergeney cases.Saf Sci,2009, 联关系，为井下火灾演变及污染范围的动态可视化 47(8):1077 显示提供了技术支持；对火灾时期烟流发展状态进 9] State Administration of Work Safety,State Administration of Coal 行有效的模拟和动态显示，是分析和预测矿井火灾 Mine Safety.Notice on the construction and improvement of six 发展趋势和避险救援工作开展的一种有效手段。 safety systems in coalmines [EB/OL].State Administration of Work Safery Online (2010-0826)[2013-0-01].http://www. (3)根据火灾对巷道通行能力的影响，制定了 chinasafety.gov.cn/newpage/Contents/Channel4188/2010/ 基于避险设施的避险路线选择原则和“理想一可 0826/106414/content_.106414.htm. 行一极限”三级避灾路线划分，提出了灾后影响避 (国家安全监管总局，国家煤矿安监局.关于建设完善煤矿井 灾路线选择的井巷安全通行性和通行效率的影响 下安全避险“六大系统”的通知EB/OL].国家安全监管总局 因素。 (2010-08-26)[2013-10-01].http://www.chinasafety.gov. (4)利用数据结构堆对Dijkstra网络算法进行 cn/newpage/Contents/Channel_4188/2010/0826/106414/con- tent_106414.htm.） 了改进，在GS的网络分析的基础上，实现了其网络 [10]Gao N,Jin L Z,Fan J G,et al.Research on the protection sys- 解算，降低了搜索重复度，提高了系统运行速度。算 tem of refuge haven of underground mine.I Saf Sci Technol

北 京 科 技 大 学 学 报 第 36 卷 测人员应该选择上行而进入皮顺巷至避难硐室内为 最佳路径。可见，巷道路径最短的避灾路线并不一 定是最安全、疏散最有效的路线。在发生火灾后，随 着时间的延续和烟流的蔓延，回风大巷会逐渐被烟 流污染，灾前规划的路径已不安全或无法通行，重新 考虑灾后巷道通行安全效率，位置 7 的监测人员应 及时下风向行走而进入轨顺大巷内至避险设施，同 时满足了安全性最好、通行时间最少的条件。所以 在没有考虑灾后巷道安全通行性和通行效率的因素 下，所求得路线并非最佳避灾路线。 表 2 仿真模拟结果与分析 Table 2 Simulation results and analysis 状态 最佳路径 结果分析 灾前 2—3—5—9—16 路径最短 灾前优化 2—11—13—14—15—16 通行时间最少 灾后 2—3—5—9—16 路径不正确，无法通行 灾后优化 2—4—6—8—9—16 安全性最好，通行时间最少 综上所述，本文制定的基于避险设施的最佳避 灾路线原则，在一定程度上弥补了灾后主要因素对 巷道通行性的影响，在平时应急培训演练及灾时避 险救援中可为指挥人员救援决策和最佳避险路线制 定奠定了基础，为提高矿山应急救援水平和效率提 供科学的方法。 4 结论 ( 1) 与以往的一般专家系统相比，矿井火灾救 援决策系统引入了监测监控演绎推理方法，更为强 调其实际应用价值和可操作性，能够使人机相互补 充和优化，使决策者掌握更为符合实际的信息而进 行指挥。 ( 2) 本文探索性地利用 GIS 技术，建立具有地 理信息的空间物理属性和数据属性的地图和图层关 联关系，为井下火灾演变及污染范围的动态可视化 显示提供了技术支持; 对火灾时期烟流发展状态进 行有效的模拟和动态显示，是分析和预测矿井火灾 发展趋势和避险救援工作开展的一种有效手段。 ( 3) 根据火灾对巷道通行能力的影响，制定了 基于避险设施的避险路线选择原则和“理想—可 行—极限”三级避灾路线划分，提出了灾后影响避 灾路线选择的井巷安全通行性和通行效率的影响 因素。 ( 4) 利用数据结构堆对 Dijkstra 网络算法进行 了改进，在 GIS 的网络分析的基础上，实现了其网络 解算，降低了搜索重复度，提高了系统运行速度。算 法实现了基于避险设施的人员最佳避灾路线的动态 可视化功能，为煤矿应急管理和应急救援指挥提供 了一种新型的信息化、智能化的平台。 参 考 文 献 ［1］ Wang L D，Zhang Ｒ X，Zhao Z G，et al． Emergency rescue com￾mand and management information system for coal mine． J Liaon￾ing Tech Univ，2006，25( 5) : 655 ( 王铃丁，张瑞新，赵志刚，等． 煤矿应急救援指挥与管理信 息系统． 辽宁工程技术大学学报，2006，25( 5) : 655) ［2］ Li Y H，Zhang Ｒ W，Bi Y F，et al． Ｒesearch and application of decision-making system in mine fire． Saf Coal Mines，2012，43 ( 3) : 15 ( 李英华，张人伟，毕岩峰，等． 矿井火灾决策系统的研究及 应用． 煤矿安全，2012，43( 3) : 15) ［3］ Cheng W M，Yao Y J，Wu L Ｒ，et al． Fluent-based numerical simulation of temperature and concentration during mine fire． Saf Coal Mines，2011，43( 2) : 20 ( 程卫民，姚玉静，吴立荣，等． 基于 Fluent 的矿井火灾时期 温度及浓度分布数值模拟． 煤矿安全，2011，43( 2) : 20) ［4］ Wang D M，Wang X S，Cui G． Travel ability of shaft and roadway in a mine fire hazard and selection of optimal rescue and escape routes． J China Coal Soc，1994，19( 1) : 58 ( 王德明，王省身，崔岗． 矿井火灾时期井巷可通行性及选择 最佳救灾与避灾路线的研究． 煤炭学报，1994，19( 1) : 58) ［5］ Li H S． Improvement on Control Technology and Simulation on Air￾flow Status in Fire Period［Dissertation］． Beijing: Beijing Gradu￾ate School of China University of Mining，1995 ( 李湖生． 矿井火灾时期风流状态模拟与优化控制技术［学位 论文］． 北京: 中国矿业大学北京研究生部，1995) ［6］ Jia J Z，Liu J，Zhao Q L． Study of mine fire rescue decision sup￾port system for No． 2 mine area of Jinchuan Company． China Saf Sci J，2006，16( 4) : 131 ( 贾进章，刘剑，赵千里． 金川公司二矿区矿井火灾救灾决策 支持系统研究． 中国安全科学学报，2006，16( 4) : 131) ［7］ Barker-read G Ｒ，Li H． Automatic selection of safe egress routes away from underground fires． Min Sci Technol，1989，9( 3) : 289 ［8］ Jalali S E，Noroozi M． Determination of the optimal escape routes of underground mine networks in emergency cases． Saf Sci，2009， 47( 8) : 1077 ［9］ State Administration of Work Safety，State Administration of Coal Mine Safety． Notice on the construction and improvement of six safety systems in coalmines ［EB /OL］． State Administration of Work Safety Online ( 2010-08-26) ［2013-10-01］． http: / /www． chinasafety． gov． cn / newpage /Contents/Channel _ 4188 /2010 / 0826 /106414 /content_106414． htm． ( 国家安全监管总局，国家煤矿安监局． 关于建设完善煤矿井 下安全避险“六大系统”的通知［EB /OL］． 国家安全监管总局 ( 2010--08--26) ［2013--10--01］． http: / /www． chinasafety． gov． cn / newpage /Contents/Channel _ 4188 /2010 /0826 /106414 /con￾tent_106414． htm． ) ［10］ Gao N，Jin L Z，Fan J G，et al． Ｒesearch on the protection sys￾tem of refuge haven of underground mine． J Saf Sci Technol， · 079 ·

第7期 詹子娜等：基于避险设施的火灾救援及避灾路线算法 ·971· 2011,7(11):169 (盛武，高明中，杨力.煤矿井下紧急避险系统模型构建.西 (高娜，金龙哲，樊品光，等.矿井避难阴室防护系统研究 安科技大学学报，2011,31(6)：799) 中国安全生产科学技术，2011,7(11)：169) [15]Wang J H,Zhang Y J,Zhu L Q,et al.Study on the mathemati- [1]Li L T.Discussion on coal mine emergency rescue system based cal modeling and mechanism of optimal path of underground on refuge chamber system.Saf Enriron Eng,2012,19(2):110 Hedge.Met Mine,2013,443(5):128 (李隆庭.基于井下避摊阴室系统的煤矿应急救援体系探 (汪金花，张亚静，朱令起，等.井下避险最优路径机理与数 讨.安全与环境工程，2012,19(2)：110) 学建模研究.金属矿山，2013,443(5)：128) [12]Li X J.Lin B Q.Application of coal mine disaster emergency 161 Gao R,Jiang Z A,Dong F,et al.Mathematical model and algo- rescue system based on GIS.J Min Sof Eng,2008,25(3):327 rithm of a dynamic optimum rescue route during mine fire time (李希建，林伯泉.基于GS的煤矿灾害应急救援系统的应 based on MapObject.J Univ Sci Technol Beijing,2008,30(7): 用.采矿与安全工程学报，2008,25(3)：327) 705 [13]Li Y F.Numerical Simulation Study of Change Law of Fume Pa- (高蕊，蒋仲安，董枫，等.基于MapObject的矿井火灾动态 rameter During Mine Fires [Dissertation].Fuxin:Liaoning 最佳救灾路线数学模型和算法.北京科技大学学报，2008， Technical University,2012 30(7):705) (李玉福.矿井火灾过程中烟流参数变化规律数值模拟研究 [17]Wang Z H,Ling Y.The optimization and implementation of the [学位论文].阜新：辽宁工程技术大学，2012) shortest path Dijkstra algorithm.Softcare Temporal,2007,23 [14]Sheng W,Gao MZ,Yang L.Underground mine emergency ref- (11):275 uge system model construction.J Xi'an Univ Sci Technol,2011, (王志和，凌云.Dijkstra最短路径算法的优化及其实现.软 31(6):799 件时空，2007,23(11)：275)

第 7 期 詹子娜等: 基于避险设施的火灾救援及避灾路线算法 2011，7( 11) : 169 ( 高娜，金龙哲，樊晶光，等． 矿井避难硐室防护系统研究． 中国安全生产科学技术，2011，7( 11) : 169) ［11］ Li L T． Discussion on coal mine emergency rescue system based on refuge chamber system． Saf Environ Eng，2012，19( 2) : 110 ( 李隆庭． 基于井下避难硐室系统的煤矿应急救援体系探 讨． 安全与环境工程，2012，19( 2) : 110) ［12］ Li X J，Lin B Q． Application of coal mine disaster emergency rescue system based on GIS． J Min Saf Eng，2008，25( 3) : 327 ( 李希建，林伯泉． 基于 GIS 的煤矿灾害应急救援系统的应 用． 采矿与安全工程学报，2008，25( 3) : 327) ［13］ Li Y F． Numerical Simulation Study of Change Law of Fume Pa￾rameter During Mine Fires ［Dissertation］． Fuxin: Liaoning Technical University，2012 ( 李玉福． 矿井火灾过程中烟流参数变化规律数值模拟研究 ［学位论文］． 阜新: 辽宁工程技术大学，2012) ［14］ Sheng W，Gao M Z，Yang L． Underground mine emergency ref￾uge system model construction． J Xi’an Univ Sci Technol，2011， 31( 6) : 799 ( 盛武，高明中，杨力． 煤矿井下紧急避险系统模型构建． 西 安科技大学学报，2011，31( 6) : 799) ［15］ Wang J H，Zhang Y J，Zhu L Q，et al． Study on the mathemati￾cal modeling and mechanism of optimal path of underground Hedge． Met Mine，2013，443( 5) : 128 ( 汪金花，张亚静，朱令起，等． 井下避险最优路径机理与数 学建模研究． 金属矿山，2013，443( 5) : 128) ［16］ 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) ［17］ Wang Z H，Ling Y． The optimization and implementation of the shortest path Dijkstra algorithm． Software Temporal，2007，23 ( 11) : 275 ( 王志和，凌云． Dijkstra 最短路径算法的优化及其实现． 软 件时空，2007，23( 11) : 275) · 179 ·