地理信息系统在灾害决策中的应用

摘 要：本文从地理信息系统和海洋科学的概念出发,引出地理信息系统在海洋灾害决策中的应用,用迪杰斯特拉算法解决最短路径问题.

关 键 词：地理信息系统海洋科学海洋灾害迪杰斯特拉算法最短路径

一

随着计算机技术的飞速发展,空间技术的日新月异,以及计算机图形学理论的日渐完善,地理信息系统（GeographicInformationSystem）技术也日趋成熟,并且逐渐被人们所认识和接受.它处理、管理的对象是多种地理空间实体数据及其关系,包括空间定位数据、图形数据、遥感图像数据、属性数据等,用于分析和处理在一定地理区域内分布的各种现象和过程,解决复杂的规划、决策和管理问题.

海洋科学则是研究海洋的自然现象、性质及其变化规律,以及与开发利用海洋有关的知识体系.它的研究对象是占地球表面71%的海洋,包括海水,溶解和悬浮于海水中的物质,生活于海洋中的生物,海底沉积和海底岩石圈,以及海面上的大气边界层和河口海岸带.因此海洋科学是地球科学的重要组成部分.海洋科学的研究领域十分广泛,其主要内容包括对于海洋中的物理、化学、生物和地质过程的基础研究,和面向海洋资源开发利用,以及海上军事活动等的应用研究.由于海洋本身的整体性、海洋中各种自然过程相互作用的复杂性和主要研究方法、手段的共同性而统一起来,使海洋科学成为一门综合性很强的科学.

近年来,地理信息系统被世界各国普遍重视,尤其是“数字地球”概念的提出,使其核心技术GIS更为各国政府所关注.目前以管理空间数据见长的GIS已经在全球变化与监测、军事、资源管理、城市规划、土地管理、环境研究、农作物估产、灾害预测、交通管理、矿产资源评价、文物保护、湿地制图,以及政府部门等许多领域发挥着越来越重要的作用.当前GIS正处于急剧发展和变化之中,研究和总结GIS技术发展,对进一步开展GIS研究工作具有重要的指导意义.GIS技术在我国愈发得到重视,由于全球环境变化研究及海洋资源和环境管理的需求,其应用从传统的城市规划、土地利用、测绘、环境保护、电力、电信、减灾防灾等陆地领域,逐步渗透到海洋资源与管理、矿产资源调查等方面.21世纪是海洋的世纪,开发海洋资源、保护海洋环境和维护海洋权益已引起世界各沿海国家的广泛关注和高度重视.“数字海洋”是“数字地球”必不可少的重要组成部分.海洋为GIS的发展提供广阔的发展空间,是GIS发挥优势、施展才华的地方.将GIS技术引进海洋领域,使海洋信息数据的建库和管理向科学化、可视化、便捷化方向发展,实现海洋信息数据的自动化成图和成果资料的网络发布、共享,符合未来“数字地球”、“数字海洋”的发展趋势.

同时GIS在海洋自然灾害应急管理系统中有很大的作用.

第一,提供空间数据和相关属性数据的快速存取和管理功能.自然灾害管理系统需要快速处理大量空间、属性数据,GIS提供高速的空间、属性数据一体化处理和管理能力,能满足污染数据查询、更新、统计、模拟分析和预测评价的需要.

第二,提供分层的可视化的显示功能.可直观地将灾害属性信息以图形方式显示在屏幕上.

第三,提供空间和属性数据间的互动查询.GIS的互动双向查询功能可方便地找到灾害源的相关信息.

第四,提供空间、属性数据一体化的统计分析功能.

第五,缓冲区分析（范围、距离等）.

第六,除上述基本功能外,GIS还可与灾害分析预测模型相结合,生成有效的决策支持信息,如GIS与灾害扩散模拟模型、元胞自动机模型、专家知识系统等相结合,可构筑功能更强、更先进的快速应急管理系统.

要充分发挥GIS在自然灾害应急管理系统中的作用,就要重点考虑以下问题：第一要建立一个空间数据库,并把空间数据库与相应的环境数据库、监测数据库等连接起来.第二,灾害处置需要操作大量数据、应用多种分析方法,因此需要开发一套完善的、智能化的数据处理分析方法.第三,建立一套灾害模拟分析评价模型,才能适应灾害应急的需要.第四,GIS系统与灾害分析模型的联结,以及整个系统的集成,避免中间数据交换,提高系统运行的速度,增强系统的分析能力.系统建设要求将以空间位置信息、特征信息,以及灾害种类、扩散范围、地理信息等搜集、整理,建立完整的数据库,通过灾害应急管理系统进行有效的组织和管理,再经过系统地分析和处理,提出事故应急处置预案.

二

下面来讲述迪杰斯特拉算法在灾害决策系统中的一个应用.

遇到紧急灾害发生时,受灾人们要被紧急疏散到事先选定的安置点.而撤退路径是灾害决策系统研究的问题之一.可靠安置点的选择是根据地理位置、安全系数和经济状况等因素确定.如何从众多的安置点中,选定一个或多个作为核心安置点,重点进行灾前建设,灾后配给救援人员和救灾物资,高效地在安置点间进行紧急物资和医疗资源的调配,也是不容忽视的问题.核心安置点应满足的条件之一是到达其余最远安置点最近,即所需时间最短.将该问题转化为在各个安置点中选取到达最远安置点路径最短的问题.最短路径是图论中的经典问题,该问题分成2种：单源最短路径问题和所有顶点间最短路径问题.前者是基础,此类问题的求解方法有动态规划法,启发式算法,A*算法,迪杰斯特拉,Bellman-算法等,其中,迪杰斯特拉算法最为经典,它的时间复杂度是0（n2）,n是图中的点数,在此算法基础上,相继有很多的改进及应用.

设有向图G等于（V,E）,V是点的集合,E是边的集合.每条边有一个非负的权值,即对每条边（u,v）∈E,有w（u,v）≥0.设s为起始点,D[i]为s到i的最短距离.该算法的基本思想是从选定的源点s出发,按照路径长度非递减的顺序逐一计算到其余各点（V-s）最短路径d,其中i∈{v-s}.

算法具体描述如下：

①将图G（V,E）中的V分为S和T.S是从源点s出发已求得最短路径的点的集合；T是尚未确定最短路径的点的集合,即T等于V-S.因此,最初时S等于{s},T等于V-{s}；用w〈i,j〉表示点i至点j之间的权值D[i]等于w（s,i）,〈s,i〉∈E∞,〈s,i〉?埸E

②选择V∈{V-s},使得D[j]等于Min{D[i]},V就是图中从V出发的最短路径的终点.更新S等于S∪{V}；

③修改从V出发到集合V-S上任一顶点Vk可达的最短路径长度.具体方法是：

如果D[j]+edges[j][k]

④如果S等于V,由此求得从Vs到图上其余各顶点的最短路径,结束；否则跳转至②.

迪杰斯特拉算法的改进：

以上迪杰斯特拉算法解决的是单源最短路径问题,可依次选定各个安置点作为源点,求出该安置点到其余点的最短路径.现对该算法上进行改进,以解决从候选安置点中选取核心安置点的问题.改进的算法如下.

①将安置点和点间的路径,抽象为有向图G（V,E）,V表示各安置点,n表示安置点数,E表示安置点间的连接,每个连接有权值,该权值可以是安置点间的距离、拥堵情况等；

②依次选取图G（V,E）各点作为源点,使用Dijkstra算法计算该点s（s∈V）到其余点I（i∈V,且i≠s）的最短路径,用D表示,得到n-1个最短路径值,构建得到表格中的一行.将图中所有点作为源点,可得到n行最短路径.

③在步骤②中每行最短路径中找出最大的最短路径值D（s∈V且i∈V）,作为步骤①表格中新的一列,该列用D表示（s∈V）.可知,从源点s到达安置点i最远；将每行的最短路径值求和,即T等于S（i∈V,且i≠s）；

④在D列中,找出最小值D,该值表示以i作为源点,出发到达最远安置点j速度最快；如果在第n列中,最小值D有多个相等,就从T列找出最小值,表示从安置点i出发到达最远安置点最近,且到达其余各安置点的路径之和最小,即到达其余安置点总耗时最少,故将安置点i选做核心安置点；

⑤根据求得的核心安置点s、到达其余安置点的最短路径D,可找出次核心安置点,依次类推.

如图1,有4个候选安置点,分别用点A,B,C和D表示.安置点之间有道路连接,根据道路是单向或双向用有向边连接,在紧急情况下可以取消或设定单向限制；有向边上的权值可以表示两个安置点之间的距离、路况等,对于双向通行的道路可能由于方向的不同,引发道路的拥堵情况不同,因此两个安置点间的有向边权值不同,如A和B之间的两条有向边.

图1各个安置点及位权关系

根据改进的迪杰斯特拉算法,分析计算如下.

（1）使用基本的迪杰斯特拉算法,对各点作为源点计算其到其余点的最短路径及其长度,结果如表1.

表1各安置点到达其余安置点的最短路径

（2）将（1）中各安置点到其余点的最短路径长度,最短路径长度中的最大值和从该点出发到其余各点的最短路径长度求和,汇总得到表2.

表2各安置点到其余点的最短路径情况表

（3）由表2可知,从安置点A出发到达最远安置点最快,选取安置点A作为核心安置点,最有利于灾害发生后在各安置点进行救援物资、医疗救护人员及设备等的调配.

若表2中,DS列最小值有2个以上,可从TS选取最小值.从而确定核心安置点.

（4）核心安置点A选定后,根据表2,进一步分析确定第二核心安置点.

在本问题中,选定A作为核心安置点,到达安置点B的最短路径是A→C→D→B；到达安置点C的最短路径是A→C；到达安置点D的最短路径是A→C→D；所以,选取安置点C作为次核心安置点.同理,依次选取第3核心安置点D和第4核心安置点.

将安置点A,B,C,D及点间的权值作为改进的迪杰斯特拉算法的输入.如图2中,黑色突出显示的安置点A即选定的核心安置点,黑色突出显示的有向路径A→C→D→B,即从核心安置点到达其余安置点的最短路径.仿真结果表明,改进后的算法可以得到到达最远安置点最快的最短路径选择.

图2算法仿真图

通过改进最短路径求解问题中的迪杰斯特拉算法,对灾害决策系统中核心安置点选择及建设问题,提供了一种可行方法.核心安置点的选定,有利于救灾过程中物资的调配和安置点规模的合理安排,对救灾工作有一定的实际应用价值.安置点间边的权值的确定及提高大规模情况下安置点的选择问题,可作为今后的研究方向.