（安全技术及工程专业论文）消防灭火救援最优路径算法研究.pdf

s u b j e c t s p e c i al t y n a m e i n s t r u c t o r ：s t u d i e so no p t i m a lp a t ha l g o r i t h m si nf i r ef i g h t i n ga n d r e s c u e ：s a f e t ye n g i n e e r i n g ：w e ix i n y u ：z h a n gj i a n r a n g a b s t r a c t ( s i g n a t u r e ) ( s i g n a t u r e ) t h ec i t yf i r ep r o t e c t i o ni sa l li m p o r t a n tp r o b l e mt h a tr e l a t e st ot h es o c i e t ys t a b i l i t ya n d p u b l i cs a f e t y w i t ht h ec i t yd e v e l o p m e n ti nc h i n a ，t h ef i r es i t u a t i o ng o e si n t oam o r er i g o r o u s p e r i o d t h et r a d i t i o n a lm e t h o dc a n ts a t i s f yt h ed e m a n do ft h em o d e mf i r ep r o t e c t i o n i ti s n e e d e dt ob u i l dap r a c t i c a lc i t yf i r ep r o t e c t i o ng e o g r a p h yi n f o r m a t i o ns y s t e m ，p r o v i d et h e p r o je c to ft h ef i r ef i g h t i n gf o r c ed i s p a t c hq u i c k l ya n dp r o v i d ea s s i s t a n c ed e c i s i o nq u i c k l y t h e l i m i t e dm a n p o w e ra n dm a t e r i a lr e s o u r c e sc a nb ew e l lu s e dt or e d u c et h el o s st ot h el e a s t a n d i nt h i ss y s t e m ，t h eo p t i m a ld i s p a t c ho ft h ef i r ef i g h t i n gf o r c ei sa v e r yi m p o r t a n tp a r t i nt h i sp a p e r ，t h ed e v e l o p m e n tc o n d i t i o no ft h eg e o g r a p h yi n f o r m a t i o ns y s t e m ( g i s ) a n d t h ed e v e l o p i n gt r e n di nt h ef i r ep r o t e c t i o nr e a l mi si n t r o d u c e db a s eo nt h ef i r es i t u a t i o ni n c h i n a t h ed e v e l o p m e n tc o n d i t i o na n dc l a s s i f i c a t i o ns y s t e mo ft h es h o r t e s tp a t ha l g o r i t h mi s a n a l y z e d t h ec i r c u m s t a n c eo fa c t u a li n s t a n c ei nf i r ep r o t e c t i o ni sa n a l y z e d ，a n dt h eo p t i m a l d i s p a t c hm o d e li nf i r ef i g h t i n ga n dr e s c u ei sb u i l t b a s eo nt h i sm o d e l ，t h ec l a s s i c a ls h o r t e s t p a t ha l g o r i t h m - d i jk s t r aa l g o r i t h mi ss t u d i e dd e t a i l e d l y t h ea l g o r i t h mi so p t i m i z e db y b i n a r yh e a pf o rt h ea l g o r i t h m ，b yw h i c ht h et i m ec o m p l e x i t yo fd i j k s t r aa l g o r i t h mi sl o w e r e d a n dt h ee f f i c i e n c yi se l e v a t e d t h et r a f f i cn e ti so p t i m i z e db yh i e r a r c h i c a ls p a t i a lr e a s o n i n gi n t h et r a f f i cn e t w o r k i ti ss h o w nt h a tt h eo p t i m i z e da l g o r i t h mc a n s a t i s f yt h ed i s p a t c ho ft h ef i r e f i g h t i n gf o r c ep r a c t i c a b l yi nt h ea c t u a la p p l i c a t i o n f i n a l l y ，t h eo p t i m i z e da l g o r i t h mi sa p p l i e d t ot h eo r b i to fx i a nn o 1f i r eb r i g a d e i ti si n d i c a t e dt h a tt h ea l g o r i t h mm a t c h e st h ea c t u a l c i r c u m s t a n c ea n di sm o r ep r a c t i c a lb yt h er e s u l t s k e y w o r d s ：f i r ep r o t e c t i o n f i r e f i g h t i n ga n dr e s c u e o p t i m a lp a t ha l g o r i t h m a h pg i s d i j k s t r aa l g o r i t h m t h e s i s ：a p p l i c a t i o ns t u d y 西妥料技太学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知。除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名豸混新雪日期乏形。么，p 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名确多 指导教师签名：与杉1 应蛐莎年谚月，少日 1 绪论 1 1 问题的提出 1 1 1 我国火灾形势分析 1 绪论 近年来，随着我国经济建设的快速发展，导致火灾的因素也大量增加，火灾形势日 趋严峻。据统计，2 0 0 0 年至2 0 0 4 年五年内，全国共发生火灾11 7 18 9 9 次，造成死亡 1 28 0 8 人，受伤1 76 6 6 人，直接财产损失7 7 2 亿人民币( 以上统计数字均不包括港、澳、 台地区，也不包括森林、草原、军队、矿井地下火灾，下同) 。火灾次数逐年增多，火 灾的伤亡人数和损失也呈逐年上升的趋势。表1 1 给出了2 0 0 0 2 0 0 4 年五年间我国的火 灾统计数字【1j 【2 j 。 表1 12 0 0 0 2 0 0 4 年我国火灾情况 据统计【2 儿引，2 0 世纪5 0 年代我国的火灾直接财产损失平均每年不到5 0 0 0 万元，6 0 年代平均每年为1 2 亿元，7 0 年代每年近2 5 亿元，8 0 年代平均每年为3 2 亿元，9 0 年 平均每年1 1 6 亿元，2 0 0 0 年后火灾直接财产损失平均达到1 5 亿多元，约为建国初期的 四番多，8 0 年代初期的两番多。这半个世纪以来，我国火灾发生数和火灾中的人员伤亡 数也呈增多趋势。特别是进入9 0 年代以后，接连发生一次死亡几十人、上百人甚至几 百人的恶性火灾事故。现阶段，我国经济和社会发展正处在上升期。这一时期的火灾明 显地呈现了严重化的趋势，主要表现在以下两个方面： ( 1 ) 随着经济社会的发展，火灾损失呈上升趋势 1 9 9 1 年至2 0 0 4 年，我国国民生产总值、固定资产投资和城镇人均可支配收入分别 增加了5 3 倍、1 1 5 倍和4 5 倍，城市建成区面积增加1 1 6 ，城市人口增加4 4 9 9 万人， 能源消耗总量增加9 3 1 0 8 t ，公路线路长度增加8 3 1 0 5 k m ，私人汽车拥有量增加1 5 6 倍p 儿驯一j 。经济社会的快速发展带来了较为严重的消防问题，在这1 3 年间火灾起数和火 灾经济损失分别增长4 6 倍和2 2 倍。与发达国家相比，我国的工业化和城市化发展水 西安科技大学硕士学位论文 平以及火灾起数与损失都还较低，随着我国经济的快速发展，火灾还有一个潜在的上升 空间【2 】【3 】【8 】。经验表明，人均g d p 在1 0 0 0 美元至3 0 0 0 美元之间，通常是一个国家的 社会结构变动剧烈、各种矛盾突出的时期【4 2 j 。从2 0 0 3 年开始，我国人均g d p 已经超过 1 0 0 0 美元，正处于这样一个特殊的历史时期，也是安全事故易发期和群死群伤事故高发 期。 ( 2 ) 特大火灾呈波动下降趋势，群死群伤火灾问题突出 经济社会的快速发展给人们的生产和生活方式带来了显著变化，人员聚集场所、易 燃易爆场所和超大规模与复杂建筑增多，大量新技术、新材料、新工艺和新能源的采用， 增加了致灾因素与火灾风险。图1 1 和图1 2 显示出2 0 世纪9 0 年代以来我国特大火灾 的基本情况。 1 0 0 0 8 0 0 餐6 0 0 01 占4 0 0 k 、 2 0 0 0 1 6 0 1 4 0 1 2 0 藕1 0 0 萋墓g 4 0 2 0 0 1 9 9 11 9 9 21 9 9 31 9 9 41 9 9 51 9 9 61 9 9 71 9 9 81 9 9 92 0 0 02 0 0 12 0 0 22 0 0 32 0 0 4 年度 图1 12 0 世纪9 0 年代以来特大火灾起数与经济损失 6 0 0 0 0 5 0 0 0 01 苌 r 4 0 0 0 0 了 t 入 3 0 0 0 0 辎 蟋 2 0 0 0 0 蕊 1 0 0 0 0 蔷 0 1 9 9 11 9 9 21 9 9 31 9 9 41 9 9 51 9 9 61 9 9 71 9 9 81 9 9 92 0 0 02 0 0 12 0 0 22 0 0 32 0 0 4 年度 图1 22 0 世纪9 0 年代以来特大火灾伤亡人数 9 0 年代初，我国特大火灾增多，群死群伤火灾时有发生。1 9 9 3 年和1 9 9 4 年分别发 生特大火灾1 2 4 起和1 5 l 起，火灾造成的直接经济损失为5 4 亿元和5 0 亿元，火灾死 籁 s 似 伽瑚咖 佃伽伽咖咖伽枷。 1 绪论 亡人数分别为4 3 3 人和8 5 5 人，出现了9 0 年代以来群死群伤火灾的第一个峰值。两年 中发生一次死亡1 0 人以上或死亡、重伤2 0 人以上的群死群伤火灾3 1 起，造成1 2 1 8 人 死亡。1 9 9 5 年以后，特大火灾一度得到遏制，但在1 9 9 7 年出现第二个峰值，发生群死 群伤火灾1 9 起，死亡4 3 3 人。2 0 0 0 年出现第三个峰值，发生了一次火灾死亡3 0 9 人与 死亡7 4 人的特大火灾事故。近年来，通过提高防灭火工作的科技水平，加大治理火灾 隐患的力度，在预防和遏制群死群伤火灾方面取得了明显成效，火灾形势基本稳定。2 0 0 1 年至2 0 0 4 年特大火灾年均3 1 起，死亡人数年均8 9 人，直接经济损失年均1 5 亿元，其 中，群死群伤火灾年均3 8 起，火灾死亡人数年均7 9 人。 1 1 2 我国火灾发展趋势 从一些西方经济发达的国家看，其经济上升期也都存在着相似的火灾严重化趋势的 特征。二次世界大战结束后，西方各国都从战争时期转为经济恢复期，此期间火灾危害 相对较小。据火灾统计资料，美国1 9 4 6 年火灾为6 0 8 万起。可是经过一段经济的恢复， 随着经济的快速发展，火灾危害日趋严重起来。美国到7 0 年代中后期，火灾危害达到 顶峰时期，全年火灾近3 3 0 万起，比1 9 4 6 年增加5 倍多，特别是1 9 7 6 年1 2 月5 日布 鲁克林剧院火灾死亡2 9 5 人、1 9 7 7 年3 月2 7 日加那利群岛特纳里夫机场火灾死亡5 8 1 人和1 9 7 7 年5 月2 8 日肯塔基州佛利山庄夜总会火灾死亡1 6 2 人，引起美国政府的高度 重视。随后美国国会成立了由各方专家组成的消防安全委员会，研究提出具体整治火灾 的措施，从而使美国消防工作得到加强，而势随着经济的发展8 0 年代后期火灾形势保 持相对平稳。表1 2 是美国从1 9 2 6 年到2 0 0 4 的一些火灾统计数据。 表1 2 美国部分年份火灾数据的统计 表中的数据表明：在城市发展的初期，火灾危害相对较小，随着城市的不断发展， 火灾危害也日趋严重：在城市发展的快速阶段，火灾进入了多发期，并起伏相间地发展 到火灾危害的顶峰；尔后，又随着经济的发展、科技的进步以及消防工作的加强，火灾 离开了这个多发期，并逐步降到相对平稳的阶段。其它西方发达国家在经济上升期，城 市迅速发展，火灾的危害也同样趋向严重化。 西安科技大学硕士学位论文 目前，我国正处在经济快速上升期，经济建设、城市发展、社会生活正日新月异， 生产技术日趋复杂，生产和生活采用的能源多样化且用量急剧增长，引发火灾的危险性 增大，势必导致火灾的多发性以及火灾危害的日趋严重。因此，我国火灾的“高危期” 在今后将会持续相当一段时间，火灾对国民经济和社会发展的潜在威胁和危害还将继续 扩大。其中，城市火灾的形势更是严峻，己引起国家的高度重视和全社会的关注。城市 消防灭火救援对减少火灾的损失意义重大，而消防地理信息系统是消防灭火救援工作一 个很好的工具。 1 1 3 消防地理信息系统 地理信息系统( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，g i s ) 是计算机科学、地理学、测量 学、地图学等多门学科集成的系统。它是一门多学科综合的边缘学科，其核心是计算机 科学，基本技术是数据库、地图可视化及空间分析【4 1 。 地理信息系统产生于2 0 世纪6 0 年代初，加拿大的r o g e r f t o m l i n s o n 和美国的d u a n e f m a r b l e 在不同的地方、从不同的角度提出了地理信息系统。1 9 6 2 年，t o m l i n s o n 教授 提出利用数字计算机处理和分析大量的土地地图数据，并建议加拿大土地调查局建立加 拿大地理信息系统c g i s ，以实现专题地图的叠加、面积量算等。到1 9 9 2 年，加拿大的 地理信息系统全面投入运行与使用，成为世界上第一个运行的地理信息系统。加拿大地 理信息系统在技术上取得了重大突破，如地图数据的扫描输入、栅格矢量数据转换；在 系统的设计上，提出空间分块、专题分层的数据结构、空间数据与属性数据相连接等思 赤目【4 】【5 】 jl ! 一o 与此同时，m a r b l e 教授在美国西北大学研究利用数字计算机研制数据处理软件系 统，以支持大规模城市交通研究，并提出建立地理信息系统软件的思想。同期，计算机 辅助制图系统的研究开始发展起来，并对地理信息系统发展有着深刻的影响。来自美国 西北技术研究所的h o w a r df i s h e r 教授在福特基金会的资助下，建立了哈佛计算机图形 与空间分析实验室。开发了s y m a p 、o d y s s e y 软件包。s y m a p 对当今栅格地理信 息系统有一定的影响，o d y s s e y 被认为是当今矢量地理信息系统的原型。另外，还有 一些发达国家也相继开展地理信息系统技术的相关研究，如英国的d a v i dr b i c k k m o r e 在英国自然环境研究会资助下，成立了实验制图部，从事计算机制图与研究【5 】【6 1 。 地理信息系统在最近的3 0 年内取得了惊人的发展，并广泛应用于资源调查、环境 评估、区域发展规划、公路设施管理、交通安全等领域，形成了一个跨学科、多方向的 研究领域【4 0 j 。 城市11 9 消防地理信息系统是城市消防部门应用地理信息技术提高城市消防工作水 平和能力的新技术。具体来说，它就是在计算机软件和硬件的支持下，运用系统论、信 息论的理论和方法，结合计算机科学、软件工程、计算机图形学、城市地理学、数据库 4 1 绪论 技术、现代通讯技术、网络技术和空间定位技术产生的能够科学管理和综合分析具有空 间内涵的城市消防信息的一种软件系统。它能够提供消防业务上的数据处理、统计、指 挥调度以及控制显示、接警实时处理等功能，能够提高消防部门指挥决策的现代化水平， 提高消防整体作战能力和对突发事件的快速反应能力。 消防地理信息系统起步较晚，从城市地理信息系统中完全独立出来、针对消防部门 的g i s 还很少。在国际上较早应用的是美国加利福尼亚的圣地亚哥市，在它的城区和所 属地区共有2 8 个部门参与建成了一个共同的g i s 区域城市信息系统( r u i s ) ，消防 就是其中一个部门。在我国第一次把g i s 技术应用于城市治安管理的是1 9 9 0 年由公安 部第一研究所研制的警务指挥调度系统。由于数据和技术力量的缺乏，该系统只是在少 数几个试点城市应用，并没有得到推广。1 9 9 5 年公安部以郑州、南宁、大连和厦门作为 试点城市，建立以城市公安g i s 为中心的1 1 0 接警处警系统，消防业务的实现仅仅是其 中的一部分，但这却为消防g i s 的研制奠定了基础。随着城市消防工作的不断发展，一 些城市建立了专门针对城市消防的g i s 。现在，消防地理信息系统主要应用于城市的消 防通信指挥系统，其主要功能是电子地图显示以及通过电信公司提供的来电号码、地址 进行电话定位。此外，是在电子地图上查询重点保护单位的灭火预案，个别有应用全球 定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) 定位等，从而使调度指挥员能充分利用各 种地理信息进行快速、准确的通信指挥。目前各地采用的消防地理信息系统软件平台各 式各样。地理信息系统的数据基本都采用矢量格式，基础数据大部分由开发公司提供， 消防专用数据则由消防部门自行采集，基础数据来源、数据格式也各不同，数据质量差 别也较大。所以在应用质量上差别也较大【8 】【9 1 。 在诸多火灾事故中，如果在火灾发生后的短暂时间内，消防力量能有效地控制火势， 则火灾损失会大大减少。火灾的经济损失有很大的波动性，它与火灾的持续时间、燃烧 物的类别、过火面积等因素有关。但是，对于一个具体的建筑物子系统，火灾损失的变 化主要与火灾持续时间有关，通过对众多火灾案例进行火灾损失与扑救延时的数值关系 分析，两者近似成线性增函数【i o 】，即 f 0 三= 口( 丁一15 ) i ，r l “m a x t 瓦弧 其中：三火灾损失值； 丁扑救前的火灾延时； 口损失随扑救延时的增益系数，可考虑各子系统燃烧的对象价值、易燃性等 因素，进行评估得出； 瓦。火灾最大持续时间，即当消防灭火不成功，可燃物燃尽而自灭的时间； 西安科技大学硕士学位论叉 三。、消防不成功时的最大损失值。 其中1 5 表示消防队必须在1 5 分钟【i o 】内达到火场出水，这是基于我国通讯、道路 和消防装备的实际情况以及对大量的火灾案例的分析得出的，这样才能有效地扑救火灾 并防止火势继续蔓延。 。 但在实际工作中往往由于消防资源调度不当等各种迟滞因素使得消防人员不能尽 早赶到火灾事故现场，丧失了对早期火灾扑救的良好时机。因此，对消防灭火救援中的 优化调度问题的研究很有必要性【1 1 | 。地理信息系统中的网络分析与最短路径算法可以很 好的解决这个问题。同时，这种最优路径的选取可作为消防地理信息系统的一个重要的 模块。 1 2 最优路径算法研究现状 消防灭火救援中的优化调度问题就是搜索网络中两点之间通行能力最强的路径，其 核心是最短路径问题。最短路径是运筹学、图论等应用数学领域中一个基本概念【1 2 】，关 于它的算法研究已得到这些领域的学者长期关注，并已有许多的研究成果；最短路径是 交通规划中一个基本概念，最短路径算法是各种交通分配方法的一个共有的基本成分； 最短路径分析是网络最优化中一个很重要、很基础的问题，不仅许多最优路径问题可以 转化为最短路径问题，网络最优化的许多其它问题也都可以转为最短路径问题或者用最 短路径的算法作为其求解的子过程 8 】【1 2 】 2 1 】。 最短路径是指网络图中一个点对之间总边权最小的连接起讫点的边的序列。在交通 规划中就是指两点之间总的综合出行阻抗最小的一串依次为相连路段的序列。 在实际中常见的最短路径问题，如司机用汽车运输货物从a 城到b 城，他就会考 虑走路程最短或者时间最少的道路。又如要在a 地到b 地之间铺设煤气管道，如何铺 设才能使总的造价最小，这是考虑费用的最短路径问题。另外，在城市规划、机器人行 走、线路安排、厂区布局、电子导航、交通转车等方面均需要考虑到最短路径问题。随 着3 s ( 地理信息系统，g i s ；全球定位系统，g p s ；遥感，r s ) 技术发展，最短路径分析 己成为各类导航系统、旅游系统及其它分析决策系统不可缺少的功能【2 l 】。 长期以来，许多学者围绕着最短路径分析进行着探讨。1 9 5 9 年，荷兰数学家d i j k s t r a 提出了d i j k s t r a 算法【l 引。此后，为了减少计算量和存储资源，出现了许多改进算法。如 采用最大邻接点法来改进算法的存储空间；采用k 叉堆优先级队列、快速排序的f i f o 队列、桶算法等来改进算法的效率【1 4 】。 但d i j k s t r a 算法是一种全向搜索，为了保证起点至当前节点的路径最优性，它要求 对所有子节点进行搜索，包括反方向搜索。于是，为了大幅度地提高效率，产生了基于 方向策略的限制搜索区域方法，基于角度优先搜索思想的算法，但是限制区域的确定并 非易事，甚至有可能加大算法的复杂度【1 4 】。 6 1 绪论 1 2 1 最短路径算法的分类 由于最短路径问题特征、网络特性等的纷繁复杂，最短路径算法表现出多样性。总 的来说，最短路径算法可通过对所求问题类型、网络特征以及求解技术的不同来进行分 米【1 4 】【1 7 】【2 l 】 大 o ( 1 ) 按问题类型分类 按照起终节点及路径的数目和特征，最短路径问题可分为5 种类型，即单对节点间 的最短路径、所有节点间的最短路径、k 则最短路径、动态最短路径和指定必经节点的 最短路径问题，其中又可衍生出其它一些特殊的最短路径问题，如限制环段数目最短路 径、含环最短路径等。分类体系如图1 3 所示。 ( 2 ) 按拓扑结构的网络特征分类 在研究不同类型的最短路径问题，所选用的拓扑结构的网络特征也不一样，如在分 析交通道路网的拓扑结构时，一般都是稀疏网络，而要研究互联网路由器的寻址问题， 一般都是带环的稠密网络。分类系统如图1 4 所示。 ( 3 ) 按路径问题的实现技术分类 按技术分类大致有预处理技术、路径搜索技术、路径记录和重构技术以及更新技术。 其中路径搜索技术又可分为组合技术和代数方法两种。组合技术主要有标号算法 ( l a b e l i n ga l g o r i t h m s ) 。标号算法也是绝大多数路径寻优问题的核心部分。按照不同的标 号节点策略，标号算法又可分为标号设定( l a b e ls e t t i n g ) 和标号改正( l a b e lc o r r e c t i n g ) 两 大体系。代数方法通过运筹学中的线性规划形式化、所定义代数系统中的联立线性方程 集合形式化和矩阵乘法等方法来求解最短路径问题。具体的分类如图1 5 所示。 二二= _ _ = 二二二。二二 i 单源 ；i多源所有节 路径 ：?路径点对 图1 3 按最短路径的问题类型分类 西安科技大学硕士学位论文 台 匿 葺 + 冀 图1 4 按最短路径的网络特征分类 8 1 绪论 图1 5 按最短路径问题的实现技术分类 9 西安科技大学硕士学位论文 1 2 2 经典最优路径算法分析 ( 1 ) 传统d i j k s t r a 算法 传统d i j k s t r a 算法是求解最短路径问题的经典算法，d i j k s t r a 算法是建立在抽象的网 络模型上，把路线抽象为网络中的边，以边的权值来表示道路的相关的参数，算法确定 了赋权网络中从某点到所有其它节点的具有最小权的路，d i j k s t r a 算法是求解最小权问 题的通用算法，它忽略了网络模型的个体特性，因此它的算法复杂度较高，在城市道路 网的路径寻优问题中，网络模型具有如下特点： 网络模型中的顶点数多，一般顶点数多达上千或上万。 对网络模型中的路线查询一般需要一定的动态性的。 因此，虽然传统d i j k s t r a 算法理论上是可行的，但是考虑到计算机硬件水平等其它 限制，如果直接使用到实际中，基本不能满足要求。不过当前的许多流行的最短路径算 法很多还是基于d i j k s t r a 算法的，不同的是都是根据实际的网络拓扑环境的限制条件、 自身特征的因素等进行修改。有一点值得注意的是d i j k s t r a 算法描述的是算法的实现方 法，与网络的存储结构无关，不同的实现方法决定了不同的时间复杂度。现实世界的空 间地物各式各样，在干变万化的空间数据中不乏有这样一类空间数据模型，他们由点一 线构成空间网络，而且可以用一个坐标系统来标志空间网络中的各点，网络中的线具有 长度的属性。例如生活中的道路网、管线网、河流网等。这类空间网络可以表示为矢量 化的网络模型g ，g 可以用一个有序三元组( 矿，e ，国) 表示，其中y 是网络模型g 的顶点 集合，e 是边集，而缈是函数，缈( p ) 表示边p ( p e ) 的长度，也就是g 中边p 对应的顶 点对( “，v ) 之间的距离，因此缈也可以表示为国( 甜，v ) 。 传统d i j k s t r a 的基本原理【1 5 】【1 6 】： 引进一个辅助向量d ( “，v ) ，它的每个分量d ( “，v ) 表示当前找到的从起点“到终点v 的最短路径长度。在算法过程中d ( u ，v ) 的值是在不断逼近最终结果，但在过程中不一定 就等于最短路径长度。它的初始状态为：若从“到v 有弧，则d ( 甜，_ ) 为弧上的权值；若 不连通，则置d ( “，v ) 为o 。显然，长度为d ( “，_ ) = m i n d ( 甜，v f ) i v y 的路径就是从“ 1 0 i 绪论 出发的长度最短的一条最短路径。路径为d ( 甜，_ ) 。 假设该次短路径的终点是唯，则这条路径或者是( 甜，y k ) ，或者是( “，_ ，咋) 。它的长 度或者是从甜到k 的弧上的权值，或者是d ( 甜，_ ) 和从_ 到咋的弧的权值之和。 d i j k s t r a 算法过程的具体描述如下： 如果( 甜，v ) 之间没有直接存在弧，则置缈( “，v ) 为。s 为已找到从“出发的最短 路径的终点的集合，初始状态为空集。那么，从起点“到图上其余各项点v 可能到达的 最短路径长度的初值为a ( u ，_ ) = 缈( “，_ ) ，v 是与起点邻接的点。 选择_ ，使得d ( “，v j ) = m i n d ( “，v ) iv f v - s ) 。 修改从顶点v s 出发到集合v - s 任一顶点唯可达的最短路径长度，如果 d ( “，_ ) + 缈( _ ，咋) d ( “，咋) ，则修改d ( 甜，k ) = d ( ”，匕) + 国( _ ，心) 。 重复操作( 2 ) ，( 3 ) 共，7 1 次，由此求得从“到图上其余各顶点的最短路径长度是递 增序列，并且就可以得到最短路径。 d i j k s t r a 算法最初设计是从一点出发计算到网络上其它各点的最短路径，所以当应 用于道路网的最优路径计算时，由于得知道起点和终点，所以可以改进d i j k s t r a 算法， 从起点开始搜索，当搜索到终点，可以停止搜索，就可得到最短路径，如果是基于道路 网拓扑结构，以道路的长度做为道路的权值，得到就是最短路径。 从算法过程中不难发现，d i j k s t r a 算法虽然适用的网络类型非常广，但是该算法随 着网络的复杂，计算量也都增加，如果把它直接应用于道路网的最优路径计算，计算量 非常大。 ( 2 ) f l o y d 算法 f l o y d 算法可以一次求出所有点对之间的最短有向路径。它的基本思想是： 假设求从定点到v ，的最短路径。如果从v 净0v ，有弧，则从v 。到v ，存在一条长度为 a r c s i j 】的路径，该路径是不是最短路径，尚需进行门次试探。首先考虑路径( v ，v o ，v ，) 是否存在。如果存在，则比较( v ，_ ) 和( k ，v o ，_ ) 的路径的长度取较短者为从v 到_ 的顶 西安科技大学硕士学位论文 点序号不大于0 的最短路径。假如在路径上再增添一个顶点v i ，也就是说，如果( v ，h ) 和 ( v 。，_ ) 分别是当前找到的顶点的序号不大于0 的最短路径。那么( _ ，h ，_ ) 就有可能是从 v 到v ，的中间节点序号不大于1 的最短路径。将它和已经得到的从v 到中间顶点序号 不大于0 的最短路径进行比较，从中选出中1 9 顶点的序号不大于1 的最短路径之后，再 增加一个顶点，继续进行试探。依次类推，在一般情况下，若( _ ，k ) 和( 咋，_ ) 分别是 从v f 到k 和从k 到v ，的序号不大于k - 1 的最短路径，则将( ，k ，v ，) 和已经得到的从v 到 v ，的中间节点不大于k 一1 的最短路径相比较，其长度较短者便是从v 到v ，的中间顶点不 大于k 的最短路径。这样，经过f 次比较后，最后求得的必是从v 到v ，的最短路径【1 3 】。 f l o y d 算法是穷举型算法，它在求每一对顶点之间的最短路径的时候要把网络中的 所有具有连通性的顶点作为中间顶点来运算，对于我们有上万个顶点的城市道路网来说 这个时间复杂度是相当大的。 ( 3 ) 启发式搜索( h e u r i s t i cs e a r c h ) 算法a 木算法 搜索是人工智能中的一个基本问题，搜索可分为盲目搜索和启发式搜索。盲目搜索 的特点是按预定的控制策略在搜索过程中获得中间信息，不用来改变控制策略。由于搜 索总是按照预先规定的路线来进行，没有考虑问题本身的特性，所以这种搜索具有盲目 性，效率不高，不便于复杂问题的求解。广度优先搜索、深度优先搜索、代价树广度优 先搜索以及代价树的深度优先搜索都属于盲目搜索策略。而启发式搜索的特点是在搜索 中加入了与问题有关的启发性信息，这些信息可以指导搜索朝着问题希望的方向发展。 a 木算法在人工智能中是一个典型的启发式搜索算法。a 木算法也是一种很好优先搜 索算法，只不过要加上一些约束条件。a 木算法的估价函数表示为【1 4 】： 厂( j ) = g ( ) + 办+ ( j )( 1 2 ) 其中g ( ) 是从起点到当前节点的实际代价的度量，h ( j ) 是从当前节点到终点 的最佳代价的估计。我们注意到若h ( j ) = 0 即没有任何全局信息，这时的a 宰算法就变 成了经典d i j k s t r a 算法。这也就说明了d i j k s t r a 算法是a 宰算法的特殊情况。 虽然a 冰算法从理论上可以证明适合求解城市道路网的问题，但是在一般情况下， a 木算法是无法避免指数爆炸的。这是因为很难估计到准确的全局信息所造成的。在这种 ：睛况下，使用a 木算法的算法复杂度就是无法估计的，也即不可行的。 1 2 l 绪论 从上面的分析可知，目前的最短路径算法主要存在着以下问题：交通信息表达不足， 如一般未考虑交叉口转向限制及延误，只能够提供出行距离最短的路线，实用性较差。 针对消防灭火救援，必须寻求存储量小、高效的算法，且应考虑到消防灭火救援自身的 特点。因此，有必要在这些方面进行研究与探讨。 1 3 论文的研究内容及技术路线 1 3 1 论文的研究内容 本文研究的内容主要是为消防灭火救援设计一个合适的、高效的最优路径算法。以 优化道路交通网中路段的权值为出发点，结合消防工作实际情况的特点，运用模糊数学 中的层次分析法综合评定道路的权值，建立消防灭火救援最优调度模型。针对d i j k s t r a 算法算法效率低的问题，对算法本身通过建立二叉堆优先级队列进行优化；在交通路网 方面，通过引入层次空间推理的概念对道路网进行分层优化。从而提高d i j k s t r a 算法的 运行效率。通过建立电子地图，以西安市消防一中队辖区为背景，对经过优化的算法进 行验证。 本篇论文的主要工作可以分为下面三个部分： 研究各类最优路径算法，设计一个合适的算法用于消防灭火救援，并结合道路网的 特点改进算法，使之在稳定性、准确性上符合消防灭火救援实际工作要求。 基于地理信息系统数据设计一个数字化电子地图，它具有缩小、放大、任意方向移 动等功能。此外，为了适应消防工作的需要增加一部分特定的图层。 在上面两部分工作的基础上，以电子地图为平台，实现消防灭火救援最优路径算法。 1 3 2 论文的技术路线 本文采用的技术路线如图1 6 所示。 图1 6 本论文的技术路线 西安科技大学硕士学位论文 1 4 本章小结 ， 本章首先从目前我国的火灾形势及其发展趋势出发引出了研究消防灭火救援最优 路径算法的研究意义，对最优路径算法及其在消防救援方面的应用进行了概述；对现有 的最优路径算法进行了分类研究，具体分析三个具有代表性的最优路径算法算法。以这 些分析为基础结合实际情况给出了本文的研究内容及技术路线。 1 4 2 路段权重的综合评定 2 1 问题概述 2 路段权重的综合评定 火灾是城市中较为频繁的灾害，其损失经常是巨大的。为将损失降低到最低程度， 消防部门面临的问题是如何迅速调动消防救援力量到达事故地点及时扑灭火灾，这就涉 及到路径选取的问题。对消防车辆从起点到终点的最优路径的计算，是一个受路网交通 状况影响的路径选择过程。路线选择所依据的原则便是使起止点间的交通阻抗最小。交 通阻抗是一个广义的概念，阻抗的主要因素是交通时间，所以通常将交通行程时间作为 阻抗的主要度量。这是因为：其一，经验研究表明交通行程时间是出行者的主要阻抗因 素。其二，几乎所有的其它因素都与交通时间密切相关，且呈现出与交通时间相同的变 化趋势。其三，交通时间比其它因素更易于测量。 d i j k s t r a 算法在通用路径选择算法中，对最短路的衡量标准是通过计算路径的边权 来决定的。如何确定边权，使设定的边权更符合系统实际的需要，是建立算法参数标准 的重要因素，其值设定的好坏，直接决定了算法的适用性。在实际城市交通网络中，道 路长度最短的路径不一定是耗时最短的。如何设定最优路径的标准也是设计权值的重要 前提。影响消防车辆到达火灾事故现场时间的因素很多，如车流量、车道数、时间段、 路面状况等等 8 1 。考虑到消防灭火救援工作的实际特点i 就需要综合考虑道路的各种迟 滞因素后得出如何在最短的时间里对火灾事故做出及时有效的响应。 一般的算法是根据道路的长度利用经典的最短路径算法求出行车的最短距离路径。 由于影响消防车辆到达时间的因素很多，最短的路径不一定耗时最短，仅考虑道路长度 得出的结果往往不太理想，所以有些文献中把车流量、车道数、道路等级、路面状况、 时间段等因素综合考虑后对道路网的弧段权值进行了修正【8 】【1 7 】。传统求解最优路径，只 考虑单个目标，而对于实际问题，决策者所要考虑的远远不止一个因素。而且这些因素 中绝大多数是无法精确确定的，带有很大的模糊性，用传统的方法很难得到最优解。而 用模糊数学方法来表示模糊量则比较合理。本章利用模糊数学中的层次分析法，对道路 权重进行综合评定，提出了基于层次分析法的道路权重层次结构模型。 2 2 最优指标的选取 消防灭火救援最优路径算法首先需要决定的就是最优目标如何选取的问题。 2 2 1 救援距离最短 若直接将出行距离最短确定为最优目标，相应的道路权重可直接选取路段属性中的 西安科技大学硕士学位论文 路段长度。这是一种简单、直观的方案，道路权重可直接获得，但实用性较差。该方案 只适用于畅通度极好的路网，或节点较少、可选路线较少、绕行路线较远、负荷度不大 的路网。因为在这些情况下，距离基本上能够作为衡量路线优劣的尺度。但是，在一般 的城市路网中，交通情况复杂，拥堵程度较高，路网密度大，里程近似的可选路线极多， 距离最短的路线中往往包含经常发生堵塞的路口或路段。在这种情况下，距离最短己无 多少实际意义和参考价值，不能适合紧急情况下消防灭火救援的需要。 2 2 2 救援时间最短 经验研究表明对于运行于道路上的车辆来说交通行程时间是主要阻抗因素。而且几 乎所有的其它因素都与交通时间密切相关，且呈现出与交通时间相同的变化趋势。因此， 在紧急情况下，救援时间最短的路线对消防部门来说，是最期望得到的一种最优路线。 若将救援时间最短作为最优目标，相应的道路权重如何标定是一个非常值得研究的问 题。一般而言，确定以出行时间度量的道路权重有以下3 种方案。 方案1 ： 选取车辆通过某一路段的平均行程时间作为道路权重，平均行程时间可根据下式计 算： 路段的平均行程时间= 路段长度设计车速 这是一个非常简化的模型，只引入设计车速这一反映道路技术等级的静态变量，没 有反映当前交通流的特性，不能较好地反映现实情况，因而只具有一定的参考价值。 方案2 ： 完全以实时的路段行程时间为权重。从灭火救援工作的实际效果而言，这是最理想 的方案。但它的实现需要有非常完善的通信基础设施和交通检测技术作保证。而我国现 阶段的技术和基础设施状况尚无法达到使该方案得以大范围实施的程度。 方案3 ： 引进表征路段行程时间与交通流量之间关系的路阻函数模型以及交叉口延误模型， 计算当前时段的路段行程时间及交叉口延误，以此确定道路权重。这样既考虑了交通流 的特性，体现了实时因素，又在当前基础设施状况允许的范围内。该方案较好地反映了 现实情况，且技术上切实可行，综合考虑了实用性与可行性。 2 3 基于层次分析法的道路权重的评定 2 3 1 层次分析法介绍 2 0 世纪7 0 年代初期，美国运筹学家匹兹堡大学萨迪( a l s a a t y ) 教授提出了著名的 层次分析法( t h ea n a l y t i ch i e r a r c h yp r o c e s s ，以下简称a h p ) 1 引。之后，萨迪于1 9 7 1 年曾 1 6 2 路段权重的综合评定 用a h p 为美国国防部研究所谓“应急计划”，1 9 7 2 年为美国国家科学基金会研究电力在 工业部门的分配问题，1 9 7 3 年为苏丹政府研究了苏丹运输问题。1 9 7 7 年萨迪在第一届 国际数学建模会议上发表了“无结构决策问题的建模层次分析法”。从那时起，a h p 开始引起人们的注意，并逐步应用于计划制定、资源分配、方案排序、政策分析、冲突 求解及决策预报等相当广泛的领域中。 随着a h p 应用范围的扩大，它的理论也得到了发展并逐步完备。近年来，近百位 学者在发展a h p 的理论和推广a h p 的应用方面做了大量工作，以a h p 为基本方法的 决策支持系统“专家选择系统”软件己商品化，在国际市场受到欢迎。 a h p 作为一种决策方法是在1 9 8 2 年1 1 月召开的中美能源、资源、环境学术会议上 由萨迪教授的学生高兰尼柴( h g h o l a m n e z h a d ) 首先向中国学者介绍的。之后，在短短的 5 年多的时间里，层次分析法在国内能源系统分析、城市规划、经济管理、科研成果评 价等许多领域中得到了应用。在a h p 的理论方面，我国学者对a h