基于层次分析法的GIS应急救援最优路径优化法.pdf

第2 6 卷第2 期 20O7 年6 月 计算技术与自动化 二 m p u t i n gT e c h n o l o g ya n dA u t o m a t i o n V 0 1 2 6 N 2 J u n 2 7 文章编号 1 0 0 3 6 1 9 9 2 0 0 7 20 0 8 l 一0 4 基于层次分析法的G I S 应急救援最优路径优化法 樊玲 乐山师范学院物理与电子信息科学系 四川乐山6 1 4 0 0 4 摘要 安全事故发生后 为了让救援物质 装备 人员以最快的速度到达事故发生地 以最大限度减少 人员伤亡和物质财产损失 开发一个基于层次分析法的智能G I s 救援系统 该系统能够在收到报警信息 后 立即联系相关救援单位 并依据事故发生地周围道路交通情况 计算出一条最快到达事故发生地的路 线 为决策者提供第一时间信息 关键词 G I s 层次分析法 最优路径 标准道路 中图分类号 T P 3 1 1 1 l文献标识码 A G I S sB e s tP a t hA n a l y s i sO fE m e r g e n c yD e c i s i o nS y s t e m B a s e dO nI m p r o V e dA H P F A NL i n g L eS h a nT e a c h e r sC o l l e g e L e s h a n6 1 4 0 0 4 C h i n a A b s t m c t W i t ht h ec o m p l i c a t e de n v i r O n m e n t i n c r e a s i n ga 赫o u n to fp e p l e m a n yi n 的l v e dr e s c u ed e p a r t m e n t s i ti sv e r yi m p o r t a n tt oi n s t a n t l yc o n t a c tw i t ht h ed e p a r t m e n t s S ow h i c hc a na r r i v et h es i t ef o rf i r s ta i da f t e ra c c i d e n t T h ea r t i c l ed e v e l o p sar e s c u es t e mb a s e do nG I S w h i c hc a na u t o m a t i c a l l yc r e a t eas c h e m ei n c l u d i r 培c o m m u n i c a t i n gt h ed e p a r t m e n t sa n ds h o wt h es h o r t e s t r o u t e st oa c c i d e n ts i t e s T h ea p p l i c a t i o no fA H Pi sd i s c u s s e di nd e t a i l K e yw o I d s G I S a n a l y t i ch i e r a r c h yp r o c e s s b e s tp a t h s t a n d a r dp a t h 1 引言 灾害发生时 紧急物质的调度是十分必要的 应急决策的最显著特点表现为时间的紧迫性 决策 者应以较短的时间完成调度方案 该方案应使物质 能以尽可能小的代价到达应急地点 此时决策过程 中最优路径的选择尤为重要 j 因此 最优路径 的选择问题直接关系到人民群众生命财产安全 具 有很强的现实意义 基于此 本文给出了一套基于 优化层次分析法的应急救援最优路径算法 能够实 时反应出当前事故发生地与救援单位之间的道路 情况 并主动搜索出两者之间的最短路径 以满足 消防 医疗 安全等部门的需求 2 层次分析法 2 1 层次分析的概念 美国运筹学家T L S a a t v 教授在2 0 世纪7 0 年代提出的层次分析法 A n a l y t i cH i e r a r c h yP r o c e s s A H P 是一种确定权向量行之有效的方法 这一方法基于对问题的全面考虑 将定性与定量分 析相结合 将决策者的经验予以量化 是比较实用 的决策方法之一L 2J 运用层次分析法解决问题时 首先对问题所涉 及到的所有因素进行分类 找出相互关系 构造层 次结构 全部因素分为目标类 准则类 方案类 再 求出各个评价准则对最终目标的重要程度 权重 再分析各个待选方案对各个评价准则的重要程度 收稿日期 2 0 0 6 0 9 0 4 作者简介 樊玲 1 9 7 7 女 四川眉山人 讲师 研究方向 信号处理 E m a i l f a n l i n g l 6 t o m c o m 万方数据 计算技术与自动化 权重 最后 计算出各个待选方案对最终目标的 重要程度 权重 3J 2 2 层次分析的特点 A H P 层次分析 具有十分广泛的应用 这与 它在理论上的合理及应用上的简便分不开的 它 主要具有以下几个特点 1 系统性 A H P 方法的思想基础与系统分析的原则是一 致的 它要求决策者在对问题进行决策分析时 首 先要姜分析对象的诸因素建立彼此相关的层次递 阶系统结构 这种层次递阶的系统结构可以清晰 地反映出诸相关因素 目标 准则 对象 地彼此关 系 2 综合性 A H P 方法在对事物进行决策分析时 能对定 性问题与定量问题进行综合分析处理 并能得到明 确的定量化结论 以优劣排序的形式表现出来 3 简便性 A H P 方法对事物的评判决策过程十分简便 若有计算机及相关程序 则整个计算就更方便 更 迅速了 4 准确性 A H P 的准确性表现在它丰富的数学原理为该 方法的准确性提供了可信的基础 同时 A H P 方 法还能吸取决策者个人或集团的阅历 经验 智慧 判断能力 从而使得决策建立在更扎实的基础上 2 3 层次分析的步骤 层次分析法的基本计算问题是计算判断矩阵 的最大特征值入m a x 和相应的特征矢量w 按照 经典的层次分析法 一般分析步骤如下 1 定义问题 确定要完成的目标 2 从最高层 管理目标 通过中间层 判断标 准 到最低层 方案 构成一个层次结构模型 3 构造一系列下层各因素对上一层准则的二 二比较判断矩阵 4 在第3 步里建立判断矩阵所需要的n n 一 1 2 个判断 5 完成所有的二二比较 输入数据 计算最大 特征值 计算一致性指标C R 6 对各层次完成第3 4 5 步的计算 7 层次合成计算 8 如整个层次综合一致性不通过 要对某些判 断作适当的改善 例如修改成对比较判断时所提出 的问题 如一定要修改问题的结构 则就要回到第 二步 不过只要对层次结构中有问题的部分作相应 修改即可 4 3 应用层次分析 3 1 建立层次结构 在本系统中 认为最近的交叉路口之间的一段 为一条道路 救援或事故单位到任意最近的一个交 叉路口之间的一段为一条道路 依据层次分析法 分析步骤 找出每条道路因为道路等级 拥堵 天 气 地址灾害等可变因素造成汽车在这条道路上行 驶的权值 进一步计算出汽车行驶的速度 然后利 用已知确定的道路长度 计算得到在这条道路上行 驶的时间 在实际情况下 对道路交通的影响因素有很 多 为了方便我们模拟计算 在这里我们只选择其 中相对重要的三项 下面我们按照层次分析的步骤 构建层次结构模型如下 鲎壁壑笪塑塞 丕氢堕堡壅堕笠堡塑堑丛塑 幽幽迪 垃堕 趟 假设三者影响因素之间的相对重要关系见 表1 表1 影响因素之问的关系 根据上面的表格可以构建如下等式 用矢量 A A W 1 V 矿2 W 2 V 矿2 V 矿3 W 2 W 1 W 3 V 矿2 V 矿3 V 矿3 V 旷3 r W l zW 2 L V 矿3 j 用矢量w w 1 W 2 W 3 7 1 右乘矩阵A 乘积结 果为n w 为了从比例矩阵A 得到向量W 必须求 解问题 A w z w 或 A 一咒J W 0 这是一个齐次线性方程 它有非零平凡解的充 1 1 2 1 3 1 1 2 3 w w w 一 w w w W w 万方数据 第2 6 卷第2 期樊玲 基于层次分析法的G I s 应急救援最优路径优化法 要条件是行列式IA 一 z 为零 即卵是矩阵A 的 一个特征值 由于A 的每一行等于A 的第一行和 某个常数的乘积 因此矩阵A 的秩为1 A 的竹个 特征值A 在本例中i 1 2 3 除了一个以外都 为零 而我们知道矩阵的所有特征值之和应等于对 角元素之和 即 卯 所以矩阵A 只有一个特征值 最大特征值 Am a x 7 2 其余皆为零 我们再把 A 的各列经过规范化处理 即分量和为1 得到的 解是唯一的bJ 在这个简单问题中 矩阵A 具有正互反性 即 盘 1 盘 0 而且A 的元素还满足以m 以 A n 即A 具有规范一致性 由P e r r o n 定理 矩 阵A 存在最大特征值A 删我们可以证明 A 咒 当A 是一致时A 起 当A 不一致时A 咒 为了测试评判的可靠性或一致性 可以建立一 个一致性指标L 4 j 在层次分析中引入判断矩阵A 的最大特征值A 和咒之差与犯一1 的比 作为度 量判断矩阵偏离一致性的指标 即用 c 等早 来检查决策者判断思维的一致性 为了和一致性指标作相对比较 以判断矩阵是 否具有满意一致性 引入判断矩阵的平均随机一致 性指标R I 即随机地用l9 标度中地1 2 3 4 5 6 7 8 9 及其倒数填满样本矩阵的上三角各项 至 对角线各个元素始终为1 对应转置位置项为上述 对应位置的随机数的倒数 对5 0 0 个随机样本矩阵 分别计算一致性指标C 值 然后取平均值 得到平 均随机一致性指标R J 4J 判断矩阵一致性指标C J 和同阶平均随机性一致性指标R J 之比称为随机一 致性比率C R 当C 尺在1 0 左右时 认为判断矩 阵具有满意地一致性 因此上面表格表示的矩阵 A 11 1 了了 713 5喜1 j 经过计算 其 A 3 0 6 5 C 0 0 3 2 浓 0 0 5 6 经过规范化处理后的向量w 0 0 7 2 0 6 5 2 0 2 7 8 可见选择的数据具有较高的满意一致 性 符合精度要求 3 2 优化层次法确定道路权值 由于实际情况下涉及的道路很多 按照经典的 层次分析法的成对比较分析将会使得计算数据成 几何级上升 并且最后得不到统一标准的有向权 图 这不符合实现本系统的初衷 在此 本系统对经典的层次分析法进行了改 进 系统舍弃了成对比较方法 每次只考虑三条道 路 其中固定的选择两条情况一般的道路作为标准 道路 其他道路和两条标准道路分别做比较 得到 各自的权值 为r 说明设计思路 我们假没当时两 条标准道路和道路X 状况为表2 表3 表4 三种道 路状况 表2道路状况 1 利用合成排序公式结果见表5 表5合成排序后的道路状况 这样得到三条道路最终合成排序矢量w 0 3 7 2 0 3 0 2 0 3 2 8 T 即道路x 与标准道路的 比值 权值 3 3确定道路交通速度 为了表征在该道路上的速度大小 根据实际测 量标准道路1 平均行驶车速为可1 标准道路2 平均 万方数据 计算技术与自动化 行驶车速为u 2 利用三条道路的排序矢量 根据插 值公式L 6J 得到道路权值所对应的道路行驶速度 值 再分别对其他道路按照此方法进行插值计算 最后得到所有道路的速度值 为了进一步加强插值 计算数据与实际道路权值的一致性 可以适当增加 标准道路的数量 但是会相应增加数据的计算量 减慢系统应急救援的反应速度 因此标准道路的选 定和数量要根据实际情况做相应的调整 同理也可 增加对道路交通影响因素的个数 增加如地质灾 害 突发事故等因素 这同样也会加大系统计算量 最后分别用道路的长度除以该道路的速度值 即得到该条道路行驶的时问值 由此得到整个道路 交通网的行驶时间有向权图 为最优路径的搜索奠 定基础 4 系统算法实现 4 1 系统架构 为了尽量减少算法实现的困难 我们舍弃了传 统的C S 模式 整个系统采用B S 架构 使得整个 系统具有很好的操作性和安全性 并且在开发的 时候使用 n e t S Q LS e r v e r 作为工具软件 因为 n e t 具有较强的灵活性 而且容易扩展其他功能 矢量图形系统是G I S 系统最重要的组成部分 也 是 n e t 开发G I S 系统的重点所在 S Q LS e r v e r 作 为G I S 系统的数据库 和 n e t 一样都是微软公司 的产品 因此二者具有很好的通用型和兼容性 而 且S Q LS e r v e r 具有很好的稳定性和对 n e t 方便的 数据接口 4 2 搜索方法 根据上面建立的有向权图 我们采用一般图最 短路问题的D i j k s t r a 算法来实现路径搜索 该算 法是解单源最优路径问题的贪心算法 J 基本思想是 给定带权有向图G V E 设 置顶点集合S 并不断地做贪心选择来扩充这个集 合 一个顶点属于集合S 当且仅当从源到该顶点 的最短路径长度已知 初始时 S 中仅含有源 设 u 是G 的某一个顶点 把从源到u 且中间只经过S 中顶点的路称为从源到u 的特殊路径 并用数组 d i s t 记录当前每个顶点所对应的最短特殊路径长 度 D i j k s t r a 算法每次从V S 中取出具有最短特 殊路长度的顶点u 将u 添加到s 中 同时对数组 d i s t 进行必要的修改 一旦s 包含了所有V 中顶 点 d i s t 就记录了从源到所有其他顶点之问的最短 路径长度 具体代码略 4 3 运行结果 通过对系统在实际运行情况下的测评 车辆在 道路上的实际运行时问与系统计算时问具有较高 的一致性 而且系统计算给定的路线 在实际情况 下 有相当高的参考价值 为应急救援提供了第一 手的信息 系统运行界面如图1 所示 5结束语 图1系统运行界面图 通过对层次分析法基本原理的研究 将层次分 析的思想引入到应急救援系统中来解决最优路径 问题 详细讨论了算法的实现和性能 提出了算法 的改进 即舍弃了传统的成对比较法 提出了标准 道路概念 不但实现了算法的应用 而且加强了实 用性 仿真实验证明该算法在解决决策支持系统 中的最优路径是可行的 对提高应急决策的效率有 一定帮助 但是该算法还有待于在更广泛的应用问 题上加以测试 参考文献 1 戴更新 达庆利 多资源组合应急调度问题的研究 J 系统 工程理论与实践 2 0 0 0 2 0 9 5 2 5 5 2 王明明 赵宝元 刘小峰运筹与决策基础 M 北京 中国林 业出版社 2 0 0 1 3 8 4 6 3 常志雁 萨殊利 范鹏飞层次分析法在G I s 事故救援系统总 的应用 J 武汉理工大学学报 交通科学与工程版 2 0 0 4 2 8 2 2 5 5 2 5 7 4 刘新宪 朱道立 选择与判断一A H P 层次分析法 决策 M 上海 上海科学普及出版社 1 9 9 0 3 1 3 2 5 同济大学出版社 线性代数 M 北京 北京高等教育出版 社 1 9 9 0 1 0 8 1 2 6 6 胡兵 李清朗 现代科学与工程计算基础 M 四川 四川大 学出版社 2 0 0 3 2 5 2 9 7 王晓东 算法设计与分析 M 北京 清华大学出版社 2 0 0 5 3 6 6 3 6 9 万方数据 基于层次分析法的GIS应急救援最优路径优化法基于层次分析法的GIS应急救援最优路径优化法 作者 樊玲 FAN Ling 作者单位 乐山师范学院 物理与电子信息科学系 四川 乐山 614004 刊名 计算技术与自动化 英文刊名 COMPUTING TECHNOLOGY AND AUTOMATION 年 卷 期 2007 26 2 被引用次数 2次 参考文献 7条 参考文献 7条 1 戴更新 达庆利 多资源组合应急调度问题的研究 期刊论文 系统工程理论与实践 2000 09 2 王明明 赵宝元 刘小峰 运筹与决策基础 2001 3 常志雁 萨殊利 范鹏飞 层次分析法在GIS事故救援系统总的应用 期刊论文 武汉理工大学学报 交通科学与工程 版 2004 02 4 刘新宪 朱道立 选择与判断 AHP 层次分析法 决策 1990 5 同济大学出版社 线性代数 1990 6 胡兵 李清朗 现代科学与工程计算基础 2003 7 王晓东 算法设计与分析 2005 相似文献 10条 相似文献 10条 1 期刊论文 梁爽 樊艳伟 马小玉 LIANG Shuang FAN Yan wei MA Xiao yu 粗集理论和层次分析法在GIS空间分析 中的应用研究 测绘与空间地理信息2010 33 4 随着地理信息理论与技术的不断发展 地理信息系统 GIS 已在各行各业广泛应用开来 GIS的专题应用常常涉及对数据进行多因子分析 而因子分析中 权重的确定是一个常见且重要的问题 层次分析法能够从大量因子中选取出对评价或决策影响很大的因子 但是这些因子所占的权重具有很大的主观性 而 粗集理论在确定因子的权重时更好地消除了人为因素的影响 这两者结合应用在GIS空间分析中 能够使得空间分析更客观 有效 2 期刊论文 许冲 戴福初 姚鑫 陈剑 涂新斌 孙瑜 王志一 Xu Chong DAI Fuchu Yao Xin Chen Jian Tu Xinbin Sun Yu Wang Zhiyi GIS支持下基于层次分析法的汶川地震区滑坡易发性评价 岩石力学与工程学报2009 28 z2 2008年5月12日14时28分 四川汶川发生了M s8 0级大地震 地震诱发了数以万计的滑坡灾害 在大约48 678 km 2的区域内 采用震后遥感影像解译并 结合野外调查的方法 共解译出48 007个滑坡 应用GIS技术 建立了汶川地震诱发滑坡灾害及相关地形 地质空间数据库 分析了断层 岩性 高程 坡度 坡向 河流 公路等7个因素与滑坡分布的关系 应用滑坡面积百分比这一标准来分别衡量每个因素中各个级别对滑坡的影响程度 然后使用层次分析法 对这7个参数进行权重分析 在GIS平台下对这些参数进行综合分析 通过分析结果将研究区内滑坡按易发程度分为极高易发区 高易发区 中易发区 低 易发区与极低易发区5类 极高易发区与高易发区面积约8 211 km 2 占研究区总面积的16 9 最后 使用汶川地震滑坡数据库对研究结果进行检验 检验曲 线表明分区效果良好 其中极高易发区与高易发区内实际发生滑坡面积为430 km 2 占滑坡总面积的60 5 3 期刊论文 戴晓爱 仲凤呈 兰燕 刘珊红 DAI Xiao ai ZHONG Feng cheng LAN Yan LIU Shan hong GIS与层次分 析法结合的超市选址研究与实现 测绘科学2009 34 1 位置的选择是修建超市的先决条件 地理信息系统依靠其强大的空间分析和可视化功能使商业选址更具直观性和科学性 本文提出了一个解决选址模 型的思路 即在GIS地理信息系统的支持下结合层次分析法 对提取的指标和建立的模型用可视化的方法来清晰 直观地解决选址问题 4 期刊论文 刘庄 谢志仁 沈渭寿 提高区域生态环境质量综合评价水平的新思路 GIS与层次分析法的结合 长江 流域资源与环境2003 12 2 区域生态环境质量综合评价涉及众多要素 同时又需要反映生态环境质量状况的空间格局 层次分析法在多要素综合评价方面具有独特优势 而GIS技 术拥有强大的空间分析能力 将GIS与层次分析法相结合应用于江苏省生态环境质量综合评价 可以充分发挥两种方法的优势 首先 根据江苏省生态环境的 基本特点确定生态环境质量综合评价的指标体系和基本评价单元 通过层次分析法 确定各评价指标的权重 计算出每个评价单元的生态环境质量综合指数 和分指数 然后运用GIS技术 根据每个评价单元的质量指数和分指数 自动生成江苏省生态环境综合评价等级图 在此基础上 对江苏省生态环境整体及各 不同侧面质量状况的空间分异规律进行分析和研究 结果显示 江苏省生态环境质量基本上由南向北逐渐降低 与自然环境状况的空间格局大体吻合 但局 部地区有差异 表明自然条件对江苏省生态环境质量的空间分异起决定性作用 但社会经济和环境污染等因素同样对生态环境具有重要影响 在某些情况下 甚至可以成为决定因素 并在一定程度上改变生态环境的空间格局 5 期刊论文 陈南祥 姜新慧 基于GIS与层次分析法的地下水资源分区研究 人民黄河2010 32 11 提出了基于GIS和层次分析法的地下水资源分区方法 选取降水量 流域水系 蒸发量 含水层富水性 地形地貌 包气带岩性为分析因子 应用层次 分析法确定各因子的权重 并结合GIS空间分析功能 得到中牟县地下水资源分区结果 结果表明 基于GIS和层次分析法的地下水资源分区方法是合理和可 行的 6 期刊论文 陈海生 刘国顺 刘大双 陈伟强 CHEN Hai sheng LIU Guo shun LIU Da shuang CHEN Wei qiang GIS支持下的河南省烟草生态适宜性综合评价 中国农业科学2009 42 7 目的 根据河南省烟草生产的实际情况 利用GIS技术及层次分析法和模糊数学原理 对河南省各烟草种植区进行烤烟生态适宜性综合评价 方法 用 特尔菲法进行各生态因子评价指标的选择 从气候 土壤 地形条件3个方面确定了17个评价指标 建立了河南省烟草生态适宜性评价指标体系 根据各生 态因子对烤烟生长与品质效应建立各隶属度函数 并将层次分析法运用于各指标权重的定量计算 采用地理信息系统软件MAPGIS绘制河南省烟草种植区烤 烟生态适宜性综合评价状况图 结果 河南省西部和南部大部分地区为烤烟生产最适宜区 占研究区总面积的22 52 南部 中部的部分地区为适宜区 占 研究区总面积的34 99 北部和东部的大部分地区为次适宜区 这部分面积占研究区总面积的35 54 结论 层次分析法和多因素模糊综合评价方法与 GIS技术有效的整合 可以快速准确地对河南省烤烟的生态适宜性进行科学的综合评价 河南省大部分地区的烤烟生态适宜性都在中等程度以上 计算出的 适宜性分布区域与实际生产水平完全吻合 7 期刊论文 张海涛 周勇 汪善勤 唐红华 柳洪 雷新美 王德华 利用GIS和RS资料及层次分析法综合评价江汉平原 后湖地区耕地自然地力 农业工程学报2003 19 2 利用GIS与RS并结合农业行业标准 NY T309 1996 和样区实际情况对江汉平原后湖地区耕地自然地力进行综合评价 从而实现土壤信息交流与共享 促 进土地资源合理利用与科学管理 根据耕地资源特点及耕地地力评价的原理 在分析了多种耕地等级评价因子类型基础上 确定了每个评价因子的指数 并 将层次分析 AHP 的原理和方法引入耕地地力评价以确定参评因子的权重 通过这些模型方法与GIS和RS结合 快速准确地完成耕地地力评价 并将评价结果 成图输出 结果表明 江汉平原后湖地区的耕地地力可分为一 二 三 四等 其面积所占比例分别为20 99 47 43 19 38 12 20 其中大部分耕地 地力处于中上水平 说明该地区的耕地质量的总体水平比较高 利用GIS和RS技术可以建立耕地资源数据库 快速准确地获取评价数据和确定评价单元 提高 评价工作效率 通过分析不同等级地力水平可找出障碍因素 从而确定土壤改良方向和管理措施 8 期刊论文 刘兴旺 朱大明 GIS在城市社区子区域火灾风险评估中的应用 地理空间信息2009 7 5 讨论了利用专家调查法和层次分析法