D0I:10.13374/i.issnl001t03.2008.07.027 第30卷第7期 北京科技大学学报 Vol.30 No.7 2008年7月 Journal of University of Science and Technology Beijing Ju.2008 基于MapObject的矿井火灾动态最佳救灾路线数学 模型和算法 高 蕊)蒋仲安)董枫)杜丙申)巩文保)王德胜)陈永现) 1)北京科技大学土木与环境工程学院教有部金属矿山高效开采与安全重点实验室，北京100083 2)河北金牛能源股份有限公司东庞矿，邢台054201 摘要运用运筹学中图论的理论和方法建立了井下火灾动态救灾路线数学模型，用改进的Dijkstra算法求解该模型并用 MapObjee©t控件实现.结合井下火灾时期救灾路线动态选择过程详细介绍了改进的D时ksra算法运算的各个步骤，拟合出矿 井火灾时期人员停留和行走时间与温度的关系函数·以东庞矿矿井灾害应急救援项目为例，通过程序运算，在东庞矿井下巷 道分布示意图上动态搜索救灾人员营救受灾人员的最佳救灾路线，不但实现了可视化要求而且效率高，为矿井火灾救灾提供 了有力的技术支持. 关键词矿井火灾；改进Dijkstra算法：救灾路线：数学模型；MapObject;应急救援 分类号TD75+2:TD77+3:P208 Mathematical model and algorithm of a dynamic optimum rescue route during mine fire time based on MapObject GAO Rui,JIA NG Zhong'an),DONG Feng,DU Bingshen2),GONG Wenbao2).WANG Desheng2),CHEN Yongxian?) 1)Key Laboratory of the Ministry of Education of China for High-efficient Mining and Safety of Metal Mines.Civil and Environmental Engineering School.University of Science and Technology Beijing.Beijing 100083.China 2)Dongpang Coal Mine.Hebei Jinniu Energy Resources Co..Ltd.,Xingtai 054201.China ABSTRACT The graph-theory method was used to build a mathematical model of the optimum rescue route during mine fire time and an improved Dijkstra algorithm was brought forward to calculate it.Then each step of the Dijkstra algorithm was discussed.and the residence and moving time-temperature function was fitted.Finally,taking the mine hazard emergency rescue system of Dong- pang mine as an example,through operation the decision maker can get the optimum rescue route on the Dongpang mine tunnel distri- bution sketch map.The software realizes the requirement of visualization with high efficiency and provides powerful technical support for mine fire rescue. KEY WORDS mine fire:improved Dijkstra algorithm:rescue route:mathematical model:MapObject:emergency rescue 矿井火灾是威胁煤矿安全生产的重大灾害之 烟气的流动失去控制，进一步扩大灾区范围，煤矿 一，煤矿井下一旦发生火灾，会给井下工作人员的生 井下到处都存在大量的易燃物，火灾极易发展蔓延， 命带来极大的威胁.井下空间狭小，矿井通风及巷 高温烟气在巷道中蔓延遇到新鲜风流时，可能在渗 道联通关系复杂，供风量有限，矿井火灾产生的大量 风地点形成新的火源.此外，矿井火灾还可能引起 高温、有毒有害烟气在井下不易散失，在巷道通风的 瓦斯、煤尘的爆炸山， 情况下高温、有毒有害烟流能随风迅速传播到很远 矿井火灾救灾过程中一个重要的环节就是制定 的范围，矿井火灾发展到一定程度时会出现火风 出最佳的救灾路线，随着计算机技术的发展，用于 压，可能造成矿井通风网路风流方向的变化，从而使 求解城市道路两点之间最短路径算法的研究已有所 收稿日期：2007-06-16修回日期：2007-08-18 基金项目：北京市教育委员会共建项目(N。,XK100080432) 作者简介：高蕊(1980-)，女，博士研究生：蒋仲安(1963一)，男，教授，博士生导师，E-mail:za1963@263.net
基于 MapObject 的矿井火灾动态最佳救灾路线数学 模型和算法 高 蕊1） 蒋仲安1） 董 枫1） 杜丙申2） 巩文保2） 王德胜2） 陈永现2） 1） 北京科技大学土木与环境工程学院教育部金属矿山高效开采与安全重点实验室北京100083 2） 河北金牛能源股份有限公司东庞矿邢台054201 摘 要 运用运筹学中图论的理论和方法建立了井下火灾动态救灾路线数学模型用改进的 Dijkstra 算法求解该模型并用 MapObject 控件实现．结合井下火灾时期救灾路线动态选择过程详细介绍了改进的 Dijkstra 算法运算的各个步骤拟合出矿 井火灾时期人员停留和行走时间与温度的关系函数．以东庞矿矿井灾害应急救援项目为例通过程序运算在东庞矿井下巷 道分布示意图上动态搜索救灾人员营救受灾人员的最佳救灾路线不但实现了可视化要求而且效率高为矿井火灾救灾提供 了有力的技术支持． 关键词 矿井火灾；改进 Dijkstra 算法；救灾路线；数学模型；MapObject；应急救援 分类号 TD75＋2；TD77＋3；P208 Mathematical model and algorithm of a dynamic optimum rescue route during mine fire time based on MapObject GA O Rui 1）JIA NG Zhong’an 1）DONG Feng 1）DU Bingshen 2）GONG Wenbao 2）W A NG Desheng 2）CHEN Yongxian 2） 1） Key Laboratory of the Ministry of Education of China for High-efficient Mining and Safety of Metal MinesCivil and Environmental Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China 2） Dongpang Coal MineHebei Jinniu Energy Resources Co．Ltd．Xingtai054201China ABSTRACT T he graph-theory method was used to build a mathematical model of the optimum rescue route during mine fire time and an improved Dijkstra algorithm was brought forward to calculate it．T hen each step of the Dijkstra algorithm was discussedand the residence and moving time-temperature function was fitted．Finallytaking the mine hazard emergency rescue system of Dongpang mine as an examplethrough operation the decision maker can get the optimum rescue route on the Dongpang mine tunnel distribution sketch map．T he software realizes the requirement of visualization with high efficiency and provides powerful technical support for mine fire rescue． KEY WORDS mine fire；improved Dijkstra algorithm；rescue route；mathematical model；MapObject；emergency rescue 收稿日期：2007-06-16 修回日期：2007-08-18 基金项目：北京市教育委员会共建项目（No．XK100080432） 作者简介：高 蕊（1980—）女博士研究生；蒋仲安（1963—）男教授博士生导师E-mail：jza1963＠263．net 矿井火灾是威胁煤矿安全生产的重大灾害之 一煤矿井下一旦发生火灾会给井下工作人员的生 命带来极大的威胁．井下空间狭小矿井通风及巷 道联通关系复杂供风量有限矿井火灾产生的大量 高温、有毒有害烟气在井下不易散失在巷道通风的 情况下高温、有毒有害烟流能随风迅速传播到很远 的范围．矿井火灾发展到一定程度时会出现火风 压可能造成矿井通风网路风流方向的变化从而使 烟气的流动失去控制进一步扩大灾区范围．煤矿 井下到处都存在大量的易燃物火灾极易发展蔓延 高温烟气在巷道中蔓延遇到新鲜风流时可能在渗 风地点形成新的火源．此外矿井火灾还可能引起 瓦斯、煤尘的爆炸［1］． 矿井火灾救灾过程中一个重要的环节就是制定 出最佳的救灾路线．随着计算机技术的发展用于 求解城市道路两点之间最短路径算法的研究已有所 第30卷 第7期 2008年 7月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．7 Jul．2008 DOI:10．13374／j．issn1001－053x．2008．07．027
.706 北京科技大学学报 第30卷 论述，但针对矿井火灾可视化最佳救灾路线进行的 因素包括灾变烟流（有毒有害气体）浓度、温度等与 研究和应用还为数不多，由于矿井火灾时期，影响 矿井灾害发展状况密切相关并且随时变化的信息， 救灾路线选择的因素非常多，救灾人员到达救灾地 1.2巷道通行性的判定 点的路线不仅要最短而且要考虑到各种因素的影 选择救灾路线时，救灾人员佩戴氧气呼吸器及 响，保证救灾人员安全迅速地救灾，因此，建立起最 备用装置，并且经过专门的训练，可在具有一定条件 佳救灾路线的数学模型，设计出适合模型的算法并 的灾变烟流中通行，此时影响可通行的条件主要是 且在矿井巷道布置图上动态搜索最佳的路线具有重 温度，但由于氧气呼吸器供氧量有限，应估算救灾人 要的意义， 员的需氧量以保证救灾人员的安全，《煤矿救护规 传统的利用计算机技术选择井下最佳路线时， 程》第128条列出了巷道中人员在高温时佩戴氧气 巷道和节点的属性信息被存储在关系数据库中，图 呼吸器停留和行走允许时间表，为了便于计算，根 形信息表示为CAD图形.实际上，随着矿井灾害的 据表中数据作最小二乘拟合，得出巷道中空气的温 变化，巷道的通行条件一直都在动态变化，巷道的属 度在27~60℃时，巷道停留时间与温度的关系为： 性信息和图形信息是个有机的整体，随着地理信息 1(t)=2106.0036e-0.1o04 (1) 系统的发展此问题迎刃而解].现有的巷道通行条 水平巷道中前进，倾斜、急倾斜巷道中下行时间与温 件的判定是根据假定的各种参数和条件模拟火灾灾 度的关系为： 变的动态变化过程，而实践证明模拟结果往往与实 2(t)=6767.0175e-0.1584 (2) 际情况相差甚远，再根据模拟得出的结果作为巷道 倾斜、急倾斜巷道中上行时间与温度的关系为： 通行性的判定依据，显然会有相当大的误差，随着 3(t)=4242.9498e-0.1579 (3) 井下监测系统的不断完善，监测系统的抗灾能力和 式中，t为穿越高温巷道允许的通行时间，min;t为 数据传输能力增强，将传感器探测到的数据（温度、 巷道中空气的温度，℃ 有毒有害烟气浓度等)直接传输给计算机，可实现最 当某条巷道中空气的温度在27~60℃并且通 佳救灾路线的动态选择，现有矿井救、避灾路线的 过时间超过式(1)~(3)计算结果时，则判定该巷道 选择，大多只显示出巷道的示意图而缺乏井下采掘 不可通行.巷道中空气的温度低于27℃时均视为 工作面、重大危险源、井下通讯设备分布等环境信 可通行，高于60℃时以人类对高温环境的最大耐受 息；而将此类信息以图形形式同时显示，可加强直观 性，有助于救灾工作的开展 时间的极限条件作为判别井巷可通行性的依据，根 据国内外大量人类对高温环境的耐受试验，用最小 1矿井火灾最佳救灾路线的数学模型 二乘法拟合出人在高温环境中最大耐受时间的指数 曲线方程山： 救灾路线指救护人员从救护基地到受灾地点的 抢险救灾路线山，最佳的救灾路线要求在安全可靠 Tmam=1812e-0.046 (4) 的条件下行走时间最短， 式中，Tmax为人在高温环境中最大耐受时间，min· 井下巷道错综复杂，从救护基地到受灾地点要 1.3最佳救灾路线求解数学模型的建立 经过多条巷道，可选择不同的巷道组合，选择最佳的 在求解最住救灾路线时，综合考虑巷道本身和 救灾路线是从若干组可能的方案中寻求一组在保证 灾变影响，将对人类行走速度较大的影响因素用一 救护人员安全的条件下能以最短的时间从救护基地 个系数表示，计算各条巷道的当量长度，再运用图论 到受灾地点的巷道，井下巷道易于用图形的形式直 的方法对从救护基地到受灾地点的可通行的巷道组 观地描述和表达，数学上把这种与图相关的结构称 合的当量长度求和，寻找当量长度之和最短的路 为网络 线 1.1影响救灾路线选择的因素 i、j节点间巷道的当量长度值为： 由于井下环境的特殊性，选择救灾路线时，不仅 g,=kgk,与+之 lijm (5) 要考虑巷道的实际长度，还应考虑到影响救灾人员 =1 行走的因素，将影响因素分为两类：第1类因素包括 式中，lw,为i,j节点间巷道的当量长度：为取决 巷道高度、坡度、局部通行障碍物（风门、跨越胶带、 于巷道高度的影响系数：k,为取决于巷道中交通工 爬行梯子间等)、积水情况、巷道维护状态、可载人的 具的影响系数；k。为取决于巷道坡度的影响系数； 交通工具速度等灾害发生前可了解的信息；第2类 k,为取决于巷道中风速的影响系数；，为i、j节点
论述但针对矿井火灾可视化最佳救灾路线进行的 研究和应用还为数不多．由于矿井火灾时期影响 救灾路线选择的因素非常多救灾人员到达救灾地 点的路线不仅要最短而且要考虑到各种因素的影 响保证救灾人员安全迅速地救灾．因此建立起最 佳救灾路线的数学模型设计出适合模型的算法并 且在矿井巷道布置图上动态搜索最佳的路线具有重 要的意义． 传统的利用计算机技术选择井下最佳路线时 巷道和节点的属性信息被存储在关系数据库中图 形信息表示为 CAD 图形．实际上随着矿井灾害的 变化巷道的通行条件一直都在动态变化巷道的属 性信息和图形信息是个有机的整体随着地理信息 系统的发展此问题迎刃而解［2］．现有的巷道通行条 件的判定是根据假定的各种参数和条件模拟火灾灾 变的动态变化过程而实践证明模拟结果往往与实 际情况相差甚远再根据模拟得出的结果作为巷道 通行性的判定依据显然会有相当大的误差．随着 井下监测系统的不断完善监测系统的抗灾能力和 数据传输能力增强将传感器探测到的数据（温度、 有毒有害烟气浓度等）直接传输给计算机可实现最 佳救灾路线的动态选择．现有矿井救、避灾路线的 选择大多只显示出巷道的示意图而缺乏井下采掘 工作面、重大危险源、井下通讯设备分布等环境信 息；而将此类信息以图形形式同时显示可加强直观 性有助于救灾工作的开展． 1 矿井火灾最佳救灾路线的数学模型 救灾路线指救护人员从救护基地到受灾地点的 抢险救灾路线［1］．最佳的救灾路线要求在安全可靠 的条件下行走时间最短． 井下巷道错综复杂从救护基地到受灾地点要 经过多条巷道可选择不同的巷道组合选择最佳的 救灾路线是从若干组可能的方案中寻求一组在保证 救护人员安全的条件下能以最短的时间从救护基地 到受灾地点的巷道井下巷道易于用图形的形式直 观地描述和表达数学上把这种与图相关的结构称 为网络． 1∙1 影响救灾路线选择的因素 由于井下环境的特殊性选择救灾路线时不仅 要考虑巷道的实际长度还应考虑到影响救灾人员 行走的因素将影响因素分为两类：第1类因素包括 巷道高度、坡度、局部通行障碍物（风门、跨越胶带、 爬行梯子间等）、积水情况、巷道维护状态、可载人的 交通工具速度等灾害发生前可了解的信息；第2类 因素包括灾变烟流（有毒有害气体）浓度、温度等与 矿井灾害发展状况密切相关并且随时变化的信息． 1∙2 巷道通行性的判定 选择救灾路线时救灾人员佩戴氧气呼吸器及 备用装置并且经过专门的训练可在具有一定条件 的灾变烟流中通行此时影响可通行的条件主要是 温度但由于氧气呼吸器供氧量有限应估算救灾人 员的需氧量以保证救灾人员的安全．《煤矿救护规 程》第128条列出了巷道中人员在高温时佩戴氧气 呼吸器停留和行走允许时间表．为了便于计算根 据表中数据作最小二乘拟合得出巷道中空气的温 度在27～60℃时巷道停留时间与温度的关系为： τ1（ t）＝2106∙0036e —0∙1004t （1） 水平巷道中前进倾斜、急倾斜巷道中下行时间与温 度的关系为： τ2（ t）＝6767∙0175e —0∙1584t （2） 倾斜、急倾斜巷道中上行时间与温度的关系为： τ3（ t）＝4242∙9498e —0∙1579t （3） 式中τ为穿越高温巷道允许的通行时间min；t 为 巷道中空气的温度℃． 当某条巷道中空气的温度在27～60℃并且通 过时间超过式（1）～（3）计算结果时则判定该巷道 不可通行．巷道中空气的温度低于27℃时均视为 可通行高于60℃时以人类对高温环境的最大耐受 时间的极限条件作为判别井巷可通行性的依据．根 据国内外大量人类对高温环境的耐受试验用最小 二乘法拟合出人在高温环境中最大耐受时间的指数 曲线方程［1］： τmax＝1812e —0∙046t （4） 式中τmax为人在高温环境中最大耐受时间min． 1∙3 最佳救灾路线求解数学模型的建立 在求解最佳救灾路线时综合考虑巷道本身和 灾变影响将对人类行走速度较大的影响因素用一 个系数表示计算各条巷道的当量长度再运用图论 的方法对从救护基地到受灾地点的可通行的巷道组 合的当量长度求和寻找当量长度之和最短的路 线［1—4］． i、j 节点间巷道的当量长度值为： lWij＝kh kt kg kv lij＋ ∑ n j＝1 lijm （5） 式中lWij 为 ij 节点间巷道的当量长度；kh 为取决 于巷道高度的影响系数；kt 为取决于巷道中交通工 具的影响系数；kg 为取决于巷道坡度的影响系数； kv 为取决于巷道中风速的影响系数；lij为 i、j 节点 ·706· 北 京 科 技 大 学 学 报 第30卷
第7期 高蕊等：基于MapObject的矿井火灾动态最佳救灾路线数学模型和算法 ·707, 间巷道的实际长度；lm为i、j节点间巷道中第m个 数 局部通行障碍物当量长度值，1≤m≤n;n为i、j节 2.2 Dijkstra算法 点间巷道中局部通行障碍物的个数. 设图G=(V,E),图中每条边具有非负长度， 从图论角度来看，井下错综复杂的巷道实际上 有一个特异顶点u称为源，假定(u,v)是E中的 是一个连接的网络图，巷道为图的边，巷道之间的交 边，cu,是边的长度，如果把顶点集合V划分为两 点抽象成图的点的集合，组成网络图的顶点；在无向 个集合S和T,S中所包含的顶点到u的距离己经 网络图上赋予救灾路线选择的影响因素，以巷道当 确定，T中所包含的顶点到的距离尚未确定.同 量长度作为边的长度，把整个井下巷道网络布局转 时，把源顶点u到T中顶点x的距离d,x定义为从 化为图的拓扑优化问题，优化目标是使从救灾基地 “出发，经过S中的顶点，但不经过T中其他顶点， 到受灾地点路线的当量长度最短，作为图论的经典 而直接到达T中的顶点x的最短路径的长度，则 问题，最短路径问题的定义是在一个赋权图的两个 Dijkstra算法的思想方法如下：开始时，S={u}, 顶点之间找出一条具有最小权值的路径.可用于解 T=V一{u}.对T中的所有顶点x,如果u到x存 决矿井灾害时期最佳救灾路线的选择问题， 在边，置d,x=cu,x;否则置du,x=o,然后，对T 2基于VEpObject的矿井火灾救灾路线算法的 中的所有顶点x,寻找du,x最小的顶点t,即： 研究 du,t=mini du,xx∈T} (6) 则d,就是顶点t到顶点u的最短距离.同时，顶 在许多地理信息系统开发平台中，都提供了最 点t也是集合T中的所有顶点中距离u最近的顶 短路径的函数或方法，比如说MapEngin,Supermap, 点，把顶点t从T中删去，把它并入S.然后，对T 但是，这些函数或方法都进行了封装，并且是解决不 中与t相邻接的所有顶点x,用下式更新d,x的值： 含权的最短路[]，如果要解决含权巷道的最短路， du.xmini du.x,du,c.x (7) 或者在排除某一条或几条巷道（具有超过人体耐受 继续上面的步骤，一直到T为空. 极限的高温烟流)之后的最短路，就需要在最短路中 增加一些附加条件，并且附加条件可修改， 由此，如果令p(x)是从顶点u到顶点x的最 短路径中x的前一顶点，那么，Dijkstra算法可以用 MapObject是美国环境系统研究所(ESRI)开发 的一种地理信息系统控件，其优点是可以嵌入到其 下面的步骤来描述]： 他软件中.Ma即Object采用面向对象编程，对电子地 (1)置S=iu},T=V-{uf. 图进行分层管理，每层对应一个数据库文件，层间进 (2)对Hx∈T,若(u,x)∈E,则d,x=cu,x, 行分目标、分物体管理，最终将电子地图上的物体对 p(x)=u;否则du,x=oo,p(x)=一1. 应到数据库中相应的字段上[]， (3)寻找t∈T,使得d,=min du,xx∈T, 2.1传统最短路径算法 则du,就是t到u的距离 传统的最短路径算法主要有Floyd算法和 (4)S=SU1t},T=T-{t}. Dijkstra算法等，其中Floyd算法是用于计算所有点 (5)若T=0,算法结束；否则，转步骤(6). 对点之间的最短路径.Dijkstra算法用于计算一个 (6)对与t相邻接的所有顶点x,如果d,.≤ 源节点到其他节点的最短代价路径，有较高的应用 du,t十c,x,直接转步骤(3)；否则，令du,x=du,t十 价值.Cherkassky于1993年在SUN Spare-10工作 c,xp(x)=t,转步骤(3) 站上对17种最短路径算法进行了测试，实验证明没 2.3 Dijkstra算法改进及在MlapObject中实现 有哪一种算法能够适应所有类型的网络.1996年 在选择矿井火灾救灾路线时，需要对Dijkstra Zhan和Noon使用实际交通网络测试了Cherkassky 算法进行改进并且编程实现，在弄清楚Dijkstra算 测试的17种算法中的15种，测试结果表明：计算一 法的基本思想和算法步骤后，编程实现显得比较容 点到所有其他点的最短路径最快的算法是Dijkstra 易，结合矿井救灾的实际情况，在以下几个方面对 算法，对于非负带权图而言，Dijkstra单源最短路径 Dijkstra算法进行改进[9l5] 算法(single-source shortest paths,SSSP)的时间复 (I)根据Dijkstra算法流程，顶点集V的大小 杂度为O(m十lgn),而多源的最短路径算法 将直接影响算法的速度.步骤(2)一(5)是一个循环 (all-pairsshortestpaths,APSP)的时间复杂度为 比较的过程，如果没有经过任何处理，则要选择一个 O(mn十n1gn),m为边的条数，n为节点的个 权值最小的节点将需要扫描V中所有的节点，这无
间巷道的实际长度；lijm为 i、j 节点间巷道中第 m 个 局部通行障碍物当量长度值1≤ m≤ n；n 为 i、j 节 点间巷道中局部通行障碍物的个数． 从图论角度来看井下错综复杂的巷道实际上 是一个连接的网络图巷道为图的边巷道之间的交 点抽象成图的点的集合组成网络图的顶点；在无向 网络图上赋予救灾路线选择的影响因素以巷道当 量长度作为边的长度把整个井下巷道网络布局转 化为图的拓扑优化问题优化目标是使从救灾基地 到受灾地点路线的当量长度最短．作为图论的经典 问题最短路径问题的定义是在一个赋权图的两个 顶点之间找出一条具有最小权值的路径．可用于解 决矿井灾害时期最佳救灾路线的选择问题． 2 基于 MapObject 的矿井火灾救灾路线算法的 研究 在许多地理信息系统开发平台中都提供了最 短路径的函数或方法比如说 MapEngin、Supermap． 但是这些函数或方法都进行了封装并且是解决不 含权的最短路［5］．如果要解决含权巷道的最短路 或者在排除某一条或几条巷道（具有超过人体耐受 极限的高温烟流）之后的最短路就需要在最短路中 增加一些附加条件并且附加条件可修改． MapObject 是美国环境系统研究所（ESRI）开发 的一种地理信息系统控件其优点是可以嵌入到其 他软件中．MapObject 采用面向对象编程对电子地 图进行分层管理每层对应一个数据库文件层间进 行分目标、分物体管理最终将电子地图上的物体对 应到数据库中相应的字段上［6］． 2∙1 传统最短路径算法 传统的最短路径算法主要有 Floyd 算法和 Dijkstra算法等其中 Floyd 算法是用于计算所有点 对点之间的最短路径．Dijkstra 算法用于计算一个 源节点到其他节点的最短代价路径有较高的应用 价值．Cherkassky 于1993年在 SUN Sparc—10工作 站上对17种最短路径算法进行了测试实验证明没 有哪一种算法能够适应所有类型的网络．1996年 Zhan 和 Noon 使用实际交通网络测试了 Cherkassky 测试的17种算法中的15种测试结果表明：计算一 点到所有其他点的最短路径最快的算法是 Dijkstra 算法．对于非负带权图而言Dijkstra 单源最短路径 算法（single-source shortest pathsSSSP）的时间复 杂度 为 O（ m＋ nlg n）而 多 源 的 最 短 路 径 算 法 （al-l pairsshortestpathsAPSP ） 的 时 间 复 杂 度 为 O（ mn＋ n 2lg n）m 为边的条数n 为节点的个 数［7］． 2∙2 Dijkstra 算法 设图 G＝（ V E）图中每条边具有非负长度 有一个特异顶点 u 称为源．假定（ uv ）是 E 中的 边cuv 是边的长度．如果把顶点集合 V 划分为两 个集合 S 和 TS 中所包含的顶点到 u 的距离已经 确定T 中所包含的顶点到 u 的距离尚未确定．同 时把源顶点 u 到 T 中顶点 x 的距离 dux定义为从 u 出发经过 S 中的顶点但不经过 T 中其他顶点 而直接到达 T 中的顶点 x 的最短路径的长度则 Dijkstra 算法的思想方法如下：开始时S ＝｛u｝ T＝ V —｛u｝．对 T 中的所有顶点 x如果 u 到 x 存 在边置 dux＝cux；否则置 dux＝∞．然后对 T 中的所有顶点 x寻找 dux最小的顶点 t即： dut＝min｛dux｜x∈ T｝ （6） 则 dut就是顶点 t 到顶点 u 的最短距离．同时顶 点 t 也是集合 T 中的所有顶点中距离 u 最近的顶 点．把顶点 t 从 T 中删去把它并入 S．然后对 T 中与 t 相邻接的所有顶点 x用下式更新 dux的值： dux＝min｛duxdut＋ctx｝ （7） 继续上面的步骤一直到 T 为空． 由此如果令 p （ x）是从顶点 u 到顶点 x 的最 短路径中 x 的前一顶点那么Dijkstra 算法可以用 下面的步骤来描述［8］： （1） 置 S＝｛u｝T＝ V —｛u｝． （2） 对∀ x∈ T若（ ux）∈ E则 dux＝ cux p（ x）＝ u；否则 dux＝∞p（ x）＝—1． （3） 寻找 t∈ T使得 dut＝min｛dux｜x∈ T｝ 则 dut就是 t 到 u 的距离． （4） S＝S∪｛t｝T＝ T—｛t｝． （5） 若 T＝∅算法结束；否则转步骤（6）． （6） 对与 t 相邻接的所有顶点 x如果 dux ≤ dut＋ctx直接转步骤（3）；否则令 dux ＝ dut＋ ctxp（ x）＝t转步骤（3）． 2∙3 Dijkstra 算法改进及在 MapObject 中实现 在选择矿井火灾救灾路线时需要对 Dijkstra 算法进行改进并且编程实现．在弄清楚 Dijkstra 算 法的基本思想和算法步骤后编程实现显得比较容 易．结合矿井救灾的实际情况在以下几个方面对 Dijkstra 算法进行改进［9—15］． （1） 根据 Dijkstra 算法流程顶点集 V 的大小 将直接影响算法的速度．步骤（2）～（5）是一个循环 比较的过程如果没有经过任何处理则要选择一个 权值最小的节点将需要扫描 V 中所有的节点这无 第7期 高 蕊等： 基于 MapObject 的矿井火灾动态最佳救灾路线数学模型和算法 ·707·
,708 北京科技大学学报 第30卷 疑是一个制约算法速度的瓶颈，当Dijkstra算法求 ④计算最短路径h=d(vm)十e(vn),l2= 解最短路径的过程中，通常执行了许多与此无关的 d(vx)十e(v,)十l(vx,v,),式中l(vx,v,)表示vx、 顶点的最短路径，增加了额外的运算量，从而降低了 v,相邻两点的路权值.l(vx,vy)>0;vx∈P;v,∈ 算法的效率，因此，不需要计算从救灾地点到所有 Q.最短路径为lmim=min{lh,l2}. 地点的最短路径，只需计算从救灾地点到受灾地点 (3)井下情况复杂，火灾灾变时期，巷道通行状 之间的最短路径，将受灾地点是否进入集合S作为 况是不断变化的，选择出的最佳救灾路线也要随着 运算停止判断的条件，可减少Dijkstra算法的标记 巷道状况的变化而变化，因此，在设计程序时应充 步数 分考虑到巷道灾变时的特点，选出的救灾路线随着 (2)考虑将最短路径问题分解为多个子问题进 巷道条件的变化而改变.例如，三水平轨道巷发生 行求解。这样可以降低问题复杂度，符合并行处理 火灾时，救灾人员需从主井出发到达受灾地点，在搜 思想，Dikstra最短路径算法是从起点到终点求最短 索救灾路线之前，可用鼠标选择想要查看的巷道， 路径，同样也可以表述为从终点到起点求最短路径， 如选择一480北翼运输大巷，此时弹出显示巷道属性 于是考虑最短路径问题可以分解为由起点到终点求 的界面（见图1），点击“灾变时期各参数输入”按钮， 解最短路径和由终点到起，点求解最短路径两个子问 可查看并更改一480北翼运输大巷灾变时期的情况 题.算法步骤为： (见图2)，图2(a)中高温烟流的温度为20℃， ①开始时，P=0,Q=0,vm=v1,vn=vN 图2(b)中高温烟流的温度为58℃.当高温烟流的 P、Q分别是由开始点1、终点N开始的扩展点 温度为20℃时，救灾人员可从一480北翼运输大巷 (固定标号)集合，vm、vm分别是集合P、Q的当前 通过，搜索出的最佳救灾路线如图3(a)所示，当高 扩展点 温烟流的温度为58℃时，计算机根据一480北翼运 ②d(m)=m吧d(:),e(w）= 输大巷首末节点的标高，判断出救灾人员上行或者 m(,),其中d(um)和e(vn)分别为起点到 下行，若判断结果为水平行进或者下行，根据式(2) vm、终点到vm的最短路径，PU{vm}→P,OU 判断此巷道是否可通行；若判断结果为上行，则根据 式(3)判断此巷道是否可通行.经计算，58℃时480 n0 北翼运输大巷不可通行，搜索出的最佳救灾路线如 ③重复②直到P∩Q={m)且vm唯一时 图3（凸）所示. 终止 天安时梨各参影推入 图1一180北翼运输大巷属性 Fig.1 Attribute of-480 north wing transportation roadway
疑是一个制约算法速度的瓶颈．当 Dijkstra 算法求 解最短路径的过程中通常执行了许多与此无关的 顶点的最短路径增加了额外的运算量从而降低了 算法的效率．因此不需要计算从救灾地点到所有 地点的最短路径只需计算从救灾地点到受灾地点 之间的最短路径将受灾地点是否进入集合 S 作为 运算停止判断的条件可减少 Dijkstra 算法的标记 步数． （2） 考虑将最短路径问题分解为多个子问题进 行求解．这样可以降低问题复杂度符合并行处理 思想．Djkstra 最短路径算法是从起点到终点求最短 路径同样也可以表述为从终点到起点求最短路径． 于是考虑最短路径问题可以分解为由起点到终点求 解最短路径和由终点到起点求解最短路径两个子问 题．算法步骤为： ① 开始时P＝∅Q＝∅v m＝ v1v n＝ v N． P、Q 分别是由开始点 v1、终点 v N 开始的扩展点 （固定标号）集合v m、v n 分别是集合 P、Q 的当前 扩展点． ② d （ v m ） ＝ min v x∈P ｛d （ v x ）｝e （ v n ） ＝ min v y∈ Q ｛e（ v y）｝其中 d （ v m ）和 e（ v n ）分别为起点到 v m、终点到 v n 的最短路径P ∪｛v m｝→ PQ ∪ ｛v n｝→ Q． ③ 重复②直到 P∩ Q ＝｛v m ）且 v m 唯一时 终止． ④ 计算最短路径 l1＝ d （ v m ）＋ e （ v n ）l2＝ d（ v x）＋e（ v y）＋ l（ v xv y）式中 l（ v xv y）表示 v x、 v y 相邻两点的路权值．l（ v xv y）＞0；v x∈ P；v y∈ Q．最短路径为 lmin＝min｛l1l2｝． （3） 井下情况复杂火灾灾变时期巷道通行状 况是不断变化的选择出的最佳救灾路线也要随着 巷道状况的变化而变化．因此在设计程序时应充 分考虑到巷道灾变时的特点选出的救灾路线随着 巷道条件的变化而改变．例如三水平轨道巷发生 火灾时救灾人员需从主井出发到达受灾地点在搜 索救灾路线之前可用鼠标选择想要查看的巷道． 如选择—480北翼运输大巷此时弹出显示巷道属性 的界面（见图1）点击“灾变时期各参数输入”按钮 可查看并更改—480北翼运输大巷灾变时期的情况 （见图2）．图2（a） 中高温烟流的温度为20℃ 图2（b）中高温烟流的温度为58℃．当高温烟流的 温度为20℃时救灾人员可从—480北翼运输大巷 通过搜索出的最佳救灾路线如图3（a）所示．当高 温烟流的温度为58℃时计算机根据—480北翼运 输大巷首末节点的标高判断出救灾人员上行或者 下行．若判断结果为水平行进或者下行根据式（2） 判断此巷道是否可通行；若判断结果为上行则根据 式（3）判断此巷道是否可通行．经计算58℃时—480 北翼运输大巷不可通行搜索出的最佳救灾路线如 图3（b）所示． 图1 —480北翼运输大巷属性 Fig．1 Attribute of —480north wing transportation roadway ·708· 北 京 科 技 大 学 学 报 第30卷
第7期 高蕊等：基于MapObject的矿井火灾动态最佳救灾路线数学模型和算法 .709. 一大有明弹小就 。利制泰 量了一车 面南香市汽通体发国一—面为卡 在速重行一燕华量 习 (a) (b) 图2高温烟流温度为20℃(a)和58℃(b)时巷道情况 Fig.2 Tunnel condition when the temperature of smoke is 20C (a)and 58C(b) (a) (b) 图320℃(a)和58℃(b)时最佳数灾路线 Fig.3 Optimum rescue routes when the temperature is 20C (a)and 58C (b) fire.Saf Coal Mines.2006.383:32 3结论 (付恩俊，唐安东。并下火灾期间最佳避灾路线的选择。煤矿 安全，2006,383.32) (1)运用运筹学中图论的理论和方法建立了井 [4]LiS L,Cao K.Peng L H.et al.The confirmation of the best 下火灾动态救灾路线数学模型，用改进的Dijkstra route for evading accident under the pit.J Liaoning Tech Univ 算法求解该模型并利用MapObject控件实现. Nat Sci Ed,1999,18(1):27 (2)本文中矿井火灾最佳救灾路线的数学模型 (李舒伶，曹坤，彭连会，等。井下最佳避灾路线确定，辽宁工 适用于井下火灾也可扩展到井下其他灾害. 程技术大学学报：自然科学版，1999,18(1)：27) (3)利用改进Dijkstra算法和Mapobject控件 [5]Guo J K.Zhang R P.Zou S K.et al.Updated Dijkstra algorithm and its application to GIS.Comput Syst Appl.2007(1):59 进行程序编制，实现了救灾路线的动态搜索，效率较 (郭建科，张仁平，邹孙楷，等.Dijkst ra改进算法及其在地理信 高，并且形象直观 息系统中的应用.计算机系统应用，2007(1)：59) (4)救灾路线的确定对于矿井灾害救援预案的 [6]Fan R X.Zeng Z.Application of MapObject control in the multi- 编制具有极重要的意义： media software for an intelligent building district.J Beijing Inst Technol,2002,22(3):373 参考文献 (范瑞霞，曾治.MapObiect控件在智能小区多媒体软件中的应 用，北京理工大学学报，2002,22(3)：373) [1]Wang D M.Li YS.Mine Fire Rescue Decision-Making Support System.Beijing:China Coal Industry Press.1996 [7]Chen Z H,Wang XZ.LiS Y,et al.Design and implementation of a route analysis algorithm for traffic network based on MapOb- (王德明，李永生，矿井火灾救灾决策支持系统.北京：煤炭工 jects.Geospatial Inf,2005,3(3):6 业出版社，1996) (陈志辉，王新洲，李少元，等.基于MapObjects的城市路网 [2]LiG.Study on Mine Safety Monitoring and Production Dis- 路径分析算法的设计与实现.地理空间信息，2005,3(3)：6) patching System Baed on GIS [Dissertation ]Xwhou:China University of MiningTechnology.2000 [8]ZhengZ H.Zheng X M.Algorithm Design and Analysis.Bei- (李钢.GS支持下的矿井安全监测与生产调度系统研究[学 jing:Tsinghua University Press.2005 (郑宗汉，郑晓明·算法设计与分析·北京：清华大学出版社， 位论文]徐州：中国矿业大学，2000) 2005) [3]Fu EJ.Tang A D.Choose the optimum escape route during mine (下转第755页)
图2 高温烟流温度为20℃（a）和58℃（b）时巷道情况 Fig．2 Tunnel condition when the temperature of smoke is20℃ （a） and58℃ （b） 图3 20℃（a）和58℃（b）时最佳救灾路线 Fig．3 Optimum rescue routes when the temperature is20℃ （a） and58℃ （b） 3 结论 （1） 运用运筹学中图论的理论和方法建立了井 下火灾动态救灾路线数学模型用改进的 Dijkstra 算法求解该模型并利用 MapObject 控件实现． （2） 本文中矿井火灾最佳救灾路线的数学模型 适用于井下火灾也可扩展到井下其他灾害． （3） 利用改进 Dijkstra 算法和 Mapobject 控件 进行程序编制实现了救灾路线的动态搜索效率较 高并且形象直观． （4） 救灾路线的确定对于矿井灾害救援预案的 编制具有极重要的意义． 参 考 文 献 ［1］ Wang D MLi Y S．Mine Fire Rescue Decision-Making Support System．Beijing：China Coal Industry Press1996 （王德明李永生．矿井火灾救灾决策支持系统．北京：煤炭工 业出版社1996） ［2］ Li G．Study on Mine Safety Monitoring and Production Dispatching System Based on GIS ［Dissertation ］．Xuzhou：China University of Mining ＆ Technology2000 （李钢．GIS 支持下的矿井安全监测与生产调度系统研究 ［学 位论文］．徐州：中国矿业大学2000） ［3］ Fu E JTang A D．Choose the optimum escape route during mine fire．Saf Coal Mines2006383：32 （付恩俊唐安东．井下火灾期间最佳避灾路线的选择．煤矿 安全2006383：32） ［4］ Li S LCao KPeng L Het al．The confirmation of the best route for evading accident under the pit．J L iaoning Tech Univ Nat Sci Ed199918（1）：27 （李舒伶曹坤彭连会等．井下最佳避灾路线确定．辽宁工 程技术大学学报：自然科学版199918（1）：27） ［5］ Guo J KZhang R PZou S Ket al．Updated Dijkstra algorithm and its application to GIS．Comput Syst Appl2007（1）：59 （郭建科张仁平邹孙楷等．Dijkstra 改进算法及其在地理信 息系统中的应用．计算机系统应用2007（1）：59） ［6］ Fan R XZeng Z．Application of MapObject control in the multimedia software for an intelligent building district．J Beijing Inst Technol200222（3）：373 （范瑞霞曾治．MapObject 控件在智能小区多媒体软件中的应 用．北京理工大学学报200222（3）：373） ［7］ Chen Z HWang X ZLi S Yet al．Design and implementation of a route analysis algorithm for traffic network based on MapObjects．Geospatial Inf20053（3）：6 （陈志辉王新洲李少元等．基于 MapObjects 的城市路网 路径分析算法的设计与实现．地理空间信息20053（3）：6） ［8］ Zheng Z HZheng X M．Algorithm Design and A nalysis．Beijing：Tsinghua University Press2005 （郑宗汉郑晓明．算法设计与分析．北京：清华大学出版社 2005） （下转第755页） 第7期 高 蕊等： 基于 MapObject 的矿井火灾动态最佳救灾路线数学模型和算法 ·709·
第7期 胡水平等：连续变断面挤压制品组织的变化规律 .755. [2]Arakawa H.Present situation and future of manufacturing tech- (黄贞益，王萍.变新面细长产品成形方法探讨.金属成形工 nology for equipment of aerospace.Jpn J Soc Technol Plast, 艺，1999(6)：33) 1996,37,1005 [6]Hu S P,Li S F,Ren X P.Development of continuous taper ex- (荒川.航空宇宙机器制造技术)现状上将来.塑性上加工， trusion process.Chin J Mech Eng.2005(12):173 1996,37:1005) (胡水平，李少峰，任学平，连续变断面挤压工艺的开发，机械 [3]Gao J,Zhao G Q,Li L H.Status and development trend of ex- 工程学报，2005(12)：173) trusion technology of aluminum alloy profile.Chin J Automob [7]Hu P,Ren X P.Tang D.The research of continuous taper ex- Technol Mater,2002(6):21 trusion forming.Chin J Plast Eng.2005(1):64 (高军，赵国群，李丽华，铝合金型材挤压技术现状与发展趋 (胡水平，任学平，唐获·连续变断面挤压成形方法的研究，塑 势.汽车工艺与材料，2002(6)：21) 性工程学报，2005(1)：64) [4]Laue K,Stenger H.Extrusion.Ohio:American Society for [8]Li L K.Ye S F.Influence of fine aluminum's heterogeneous an- Metals.1981 neal on microstructure and property.Chin J Light Met.1994 [5]Huang Z Y.Wang P.Make an inquiry into method of variable (2):50 cross section long thin product.Chin J Met Form Technol,1999 (李念奎，叶淑芬·均匀化退火对高纯铝箔的组织和性能的影 (6):33 响.轻金属，1994(2)：50) (上接第709页) planning algorithms.J Univ Sci Technol Beijing.2005.27 [9]Ye Q.YuZ W.The improved shortcut algorithm and it's appli- (3):367 cation in selecting ship's optimum route.Navig China.2003. (李擎，宋顶立，张双江，等.两种改进的最优路径规划算法： (55):15 北京科技大学学报，2005,27(3)：367) (叶清，郁振伟，改进最短路径算法在最佳航线选择中的应用· [13]Liu Y L.Wang P T.Optimization model of complicated net- 中国航海，2003，(55)：15) work and shortest path algorithm.J Tianjin Univ Technol, [10]Zhang X Y,Huang Y,Yang S G.Improved Dijkstra algorithm 2006,22(1):33 used in embedded-GIS system.Comput Eng Des.2007,28 (刘彦良，王鹏涛，复杂网络的优化模型及最短路径求解，天 (2):412 津理工大学学报，2006,22(1)：33) (张雪燕，黄寅，杨晟刚，一种改进的Dkst算法应用于嵌入 [14]Stanley R Michalski.The Jharia mine fire control technical assis- 式GIS系统.计算机工程与设计，2007,28(2)：412) tance project:an analysis.Int J Coal Geol,2004.59:83 [11]Gu LL.The optimization of Dijkstra in GIS route analysis [15]Yang Z B.Li Z Y.Lv W.An algorithm for finding the local Comput Digital Eng.2006.34(12):53 shortest path based on MapX.Comput Syst Appl,2006,(3): (古凌岚，GIS最短路径分析中Dijkstra算法的优化·计算机 83 与数字工程，2006,34(12)：53) (杨中宝，李朝艳，吕伟.基于Ma即X的局部最短路径搜索算 [12]Li Q,Song D L:Zhang S J,et al.Two improved optimum path 法.计算机系统应用，2006，(3)：83)
［2］ Arakawa H．Present situation and future of manufacturing technology for equipment of aerospace． Jpn J Soc Technol Plast 199637：1005 （荒川．航空宇宙机器制造技术の现状と将来．塑性と加工 199637：1005） ［3］ Gao JZhao G QLi L H．Status and development trend of extrusion technology of aluminum alloy profile． Chin J A utomob Technol Mater2002（6）：21 （高军赵国群李丽华．铝合金型材挤压技术现状与发展趋 势．汽车工艺与材料2002（6）：21） ［4］ Laue KStenger H． Extrusion．Ohio：American Society for Metals1981 ［5］ Huang Z YWang P．Make an inquiry into method of variable cross-section long thin product．Chin J Met Form Technol1999 （6）：33 （黄贞益王萍．变断面细长产品成形方法探讨．金属成形工 艺1999（6）：33） ［6］ Hu S PLi S FRen X P．Development of continuous taper extrusion process．Chin J Mech Eng2005（12）：173 （胡水平李少峰任学平．连续变断面挤压工艺的开发．机械 工程学报2005（12）：173） ［7］ Hu S PRen X PTang D．The research of continuous taper extrusion forming．Chin J Plast Eng2005（1）：64 （胡水平任学平唐荻．连续变断面挤压成形方法的研究．塑 性工程学报2005（1）：64） ［8］ Li L KYe S F．Influence of fine aluminum’s heterogeneous anneal on microstructure and property．Chin J L ight Met1994 （2）：50 （李念奎叶淑芬．均匀化退火对高纯铝箔的组织和性能的影 响．轻金属1994（2）：50） （上接第709页） ［9］ Ye QYu Z W．The improved shortcut algorithm and it’s application in selecting ship’s optimum route．Navig China2003 （55）：15 （叶清郁振伟．改进最短路径算法在最佳航线选择中的应用． 中国航海2003（55）：15） ［10］ Zhang X YHuang YYang S G．Improved Dijkstra algorithm used in embedded-GIS system． Comput Eng Des200728 （2）：412 （张雪燕黄寅杨晟刚．一种改进的 Dijkstra 算法应用于嵌入 式 GIS 系统．计算机工程与设计200728（2）：412） ［11］ Gu L L．The optimization of Dijkstra in GIS route analysis． Comput Digital Eng200634（12）：53 （古凌岚．GIS 最短路径分析中 Dijkstra 算法的优化．计算机 与数字工程200634（12）：53） ［12］ Li QSong D LZhang S Jet al．Two improved optimum path planning algorithms． J Univ Sci Technol Beijing200527 （3）：367 （李擎宋顶立张双江等．两种改进的最优路径规划算法． 北京科技大学学报200527（3）：367） ［13］ Liu Y LWang P T．Optimization model of complicated network and shortest path algorithm． J Tianjin Univ Technol 200622（1）：33 （刘彦良王鹏涛．复杂网络的优化模型及最短路径求解．天 津理工大学学报200622（1）：33） ［14］ Stanley R Michalski．The Jharia mine fire control technical assistance project：an analysis．Int J Coal Geol200459：83 ［15］ Yang Z BLi Z YLv W．An algorithm for finding the local shortest path based on MapX．Comput Syst Appl2006（3）： 83 （杨中宝李朝艳吕伟．基于 MapX 的局部最短路径搜索算 法．计算机系统应用2006（3）：83） 第7期 胡水平等： 连续变断面挤压制品组织的变化规律 ·755·