最优路径算法 [关于消防救援工作最优路径问题的探索研究]

　　摘要:消防部队在执行突发任务时,如何在不给城市交通带来大影响的前提下,选择最优路径[1][2],在最短时间内安全到达指定位置的问题值得我们研究。本文结合实际情况,应用数学方法建立体现城市道路交通路网模型,再用图论中的有向图思想将路网抽象成数学模型描述,基于经典的狄杰斯特拉(Dijkstra)算法和动态规划,应用LINGO软件设计了可应用于实际道路网络中的最优路径算法,采用该算法可求解带有限制的最优路径问题。通过研究具体算例表明,该算法能够解决满足要求的问题。
　　关键词:消防 最优路径 Dijkstra算法 动态规划 优化 LINGO
　　中图分类号: 文献标识码:A文章编号:1007-9416(2010)05-0000-00
　　
　　1 课题研究的背景[3]和意义
　　2001―2008年我国化工企业共发生较大及其以上级别事故119起,其中,死亡510人,重伤105人,轻伤377人。从2001年到2008年我国化工企业较大及其以上级别事故发生总趋势为波动上升,且单事故中伤亡人数在逐渐增加。尤其是从2004年开始,化工企业较大及以上级别事故的发生数量居高不下。目前,我国正处于经济快速上升期,工业发展正在不断加快,化工企业的生产技术日趋复杂,势必导致事故的多发性以及事故危害的日趋严重。城市消防救援对减少事故的损失意义重大,但在实际工作中往往由于消防救援路程不畅等各种迟滞因素使得消防人员丧失了对事故早期救援的良好时机。因此,对消防救援中最优路径选择问题的研究很有必要。
　　
　　2 最短路径问题的基本理论
　　2.1 传统Dijkstra算法概述
　　传统Dijkstra算法过程的具体描述如下:
　　1)如果(u,)之间没有直接存在弧,则置w(u,)为 。S为已找到的从u出发的最短路径的终点的集合,初始状态为空集。那么,从起点u到图上其余各项点 可能到达的最短路径长度的初值为d(u,)= w(u,), 是与起点邻接的点。2)选择 ,使得d(u, )=min{d(u,)/ ∈V-S}。
　　3)修改从顶点V∈S出发到集合V-S任一顶点唯可达的最短路径长度,如果d(u, )+w( , ) 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文