网站首页  词典首页

请输入您要查询的论文：

　

标题 Dijkstra算法在园区消防车最优路径中的应用
范文 张滔+李德堂+郑开举



摘要：本文针对当前园区消防车辆到达受灾点的事故蔓延状况随到达时间的延长而加重的问题，研究并提出了改进的Dijkstra算法。并且通过对传统Dijkstra算法与改进的Dijkstra算法进行比较，得出改进的Dijkstra算法求得的最优路径使消防车到达的时间更短。
关键词：园区事故 Dijkstra算法 改进的Dijkstra算法
中图分类号：U491.2 文献标识码：A
The improved Dijkstra algorithm application in optimal path selection of the campus fire truck
ZHANG Tao1，Li De-tang2，Zheng Kai-ju1（1. Ports and transportation engineering college， Zhejiang Ocean University；2. School of Naval Architecture and Mechanical-electrical Engineering， Zhejiang Ocean University、Offshore in Zhejiang
province key laboratory of ocean engineering technology Zhoushan 316000，China）
Abstract：In allusion to the problem of the current campus fire vehicles arrived at the point of accident along with the extension of time of arrival is aggravating， the research and the improved Dijkstra algorithm are put forward. By comparing traditional Dijkstra algorithm and the improved Dijkstra algorithm， it is concluded that the improved Dijkstra algorithm obtains the optimal path taking less time to make the fire engines arrived.
Key Words：The accident of industrial park Dijkstra algorithm The improved Dijkstra algorithm
由于全球经济的不断快速发展，园区经济最为促进经济快速增长的重要产业也在发生着巨大的变化。在园区发展过程中难免存在一定的危险源，当危险源在一定环境下会发生事故，在园区中较多的事故就是厂区爆炸或者火灾，针对这一情况最为紧迫的是找出最优路径，使消防车以最快的速度抵达始发地，避免二次事故的发生，保护生命安全，减少财产损失。对于最优路径的选择方法，Dijkstra算法是当前运用最普遍的。许多学者也都对Dijkstra算法进行了研究与发展，李擎等在经典Dijkstra算法中，针对当前不相连节点间路径长度为无穷大这一特点，首先对两个节点是否相连进行判断，若发现两个节点并不相连时，则舍去相应计算，从而减少计算量。丁浩等研究了如何利用Dijkstra算法来迅速寻找出快递车辆配送派件过程中的最短路径。楚志勇等运用Dijkstra算法解决了乡镇消防站选址的问题。武文越等采用Dijkstra算法快速找出了露天矿运输中的最短运输路径。黄冬梅等通过改进Dijkstra算法，同时采用Matlab进行仿真，可以减少撤离路径的次数，计算出受灾区域到各个安置点的最短路径。
以上研究在进行Dijkstra算法的研究时多数是从最短路径这一单一的目的入手，而现实中园区发生爆炸时，道路会受到一定的阻碍，那么在选择路径时考虑的影响因素则需要进行一下改变。文中主要考虑了园区道路疏通的时间，进而求得消防车最优路径。
一、传统Dijkstra算法的基本思想
（一）Dijkstra算法
设G=（V，E，W）是一个带权无向的简单连接图，其中V是G的顶点集合，E是G的边的集合，W是各边上权的集合（Wij≥0）。算法步骤如下：
Step1：给起点v1标上P标号P（1）=0，其余顶点标号T1（j）=∞，j=2，3，...，n。该标号表示从起点v1到起点自身的最短路权为0，到其他各个顶点的最短路权上限暂定为∞。
Step2：设经过了K-1步标号计算，顶点vi是刚得到P标号的点，则对所有没有得到P标号的点进行下一步新的标号，即第k步计算；考虑到所有与顶点vi相邻且没有标上P标号的点vj集合，分别修改其对应的T标号：Tk（j）=min{T（j），P（i）+dij}；在所有的T标号中，选出最小的T标号Tk（j0）：Tk（j0）=min{Tk（j），T（r）}。
Step3：给顶点j0标上P标号：P（j0）=Tk（j0）。
Step4：当所有顶点中已经没有T标号时，表示算法结束，从而得到起点v1到其他各点的最短路权，否则返回Step2。
符号说明：
P：集合P是已经求出最短路径的顶点集合；
T：集合T是其余未确定的最短路径的顶点集合；
P（）：括号内的数字表示顶点号，下标表示第几步标号；
Dij：表示顶点vi到顶点vj的距离（路权值）；
Tk（j）：表示第k步前的vj点的T标号；
T（r）：表示与vi点不相邻的点r的T标号；
W：r表示所有的P标号对应的最短路权值的集合，即W=P1UP2U......UPn-1UPn（n≧1）；
E：表示连接图中的各个顶点之间的边，即{Vi，Vj}∈E；
V：表示构成G的顶点集合，即{vi，vj}∈V，（i，j=1，2，3......n）（n≧1）。
（二）Dijkstra算法的应用举例
为了便于更好地理解Dijkstra算法，下面以具体实例来说明Dijkstra算法的具体应用。
例题1：利用Dijkstra算法计算以下路网中节点v1到节点v5的最优路径。
根据Dijkstra算法的基本步骤，其计算的过程可以表示为表1所示。从表1可以看出从节点v1到节点v5的最短路径为：1→3→5，而且节点v1到节点v5的最短路权为d（v1，v5）=3.5。
传统Dijkstra算法作为当前最优路径选择最常用的算法，有其自身的强大优点，但是当发生爆炸与灾害时，道路情况也是在不断变化之中。灾害发生后的道路与以往大不相同，人群四处散开，行人横穿、车流混乱行驶等干扰对交通状况有很大影响。因此需要在传统Dijkstra算法的基础上进行相应的改进，以适应城市爆炸、火灾发生时消防车紧急救援的路径选择。
三、改进的Dijkstra算法
（一）问题描述
G=（V，E，W，T）是一个带权无向的简单连接图，其中字母符号V，E，W，在传统Dijkstra算法中已经进行了相应说明，在此仅对新增变量T进行解释。变量T是发生爆炸、火灾时疏散道路车流、人流为消防车疏通道路后的时间集合即t（vi，vj）∈T，当爆炸发生时道路为畅通，不影响消防车的通行施救。
（二）算法改进的具体步骤
根据以上对于传统Dijkstra算法的分析以及对于园区爆炸时的情况简析以及李敬贤等人改进Dijkstra算法来求解震后最优路径的思路，文中改进的Dijkstra算法模型比传统Dijkstra算法模型增添了一个新的自变量t（道路疏通时间），因此需要对传统Dijkstra算法中的集合T进行相应的改进与更新。改进的Dijkstra算法主要将消防车时间作为主要因素，而消防车成本不予考虑，计算步骤如下：
Step1：数值初始化。当顶点集合（vi，vj）不属于G的边，则令：
w（vi，vj）=∞，t（vi，vj）=∞；同时变量集合T（vi）表示通过起点与顶点vi之间的某条路所花费的时间，起始之时，T（vm）=0，0≦m≦n；T（vn）=∞。
Step2：选取G中的一个顶点vp，且vp∈T，表示该顶点未标上P标号，且对于另外任意一顶点vq，vq∈T，T（vp）≦T（vq）。
Step3：介于T（vp）≦T（vq），则把顶点vi的T标号改为P标号，加入集合W.
Step4：更新所有的T（v）（v均未求出最短路径），对于任意一个顶点v，取得temp=max{T（vp），t（vp，vq）}，如果temp+w（vp，vq）Step5：继续重复Step2到Step4，直到将所有的顶点进行P标号改写，并加入集合W。
算法结束后，T即通过最优路径所花费的时间。
（三）举例分析
假设某工业园区的道路交通系统在园区爆炸前的路网结构如图1所示，图2是园区在发生爆炸后的交通路网结构，且图2加粗部分表示园区爆炸遭到破坏的路段，括号中的数字则表示疏通道路时间，求解爆炸发生后从消防站a抵达受灾点o的最优路径。
根据不同方法得出的最优路径不同，如下图3、4、5同时，在不同情况下得出的最短时间也不相同，如表2所示。
根据表2可以看出，当道路遇到突发情况而引起人车混乱、阻碍交通正常运行时，传统的Dijkstra算法所求得的路径有时不是最优路径，相比之下，改进的Dijkstra算法求得的路径比其更优越，能够为消防车迅速到达受灾地点选择合适路径，既节约成本，也可减少二次事故发生的几率。
四、结束语
随着科学技术的不断发展与更新，对于受灾地点的信息采集将会更加便捷。改进的Dijkstra算法可以充分利用获取的信息来进行园区受灾点的最优路径选择，缩短消防车的抵达时间，以此减轻爆炸等事故对园区的破坏，减少人员伤亡。
参考文献：
[1] 李擎，宋顶立，等.两种改进的最优路径规划算法[J].北京科技大学学报，2005，27（3）：6.
[2] 丁浩，苌道方. 基于Dijkstra算法的快递车辆配送路径优化[J].价值工程，2014（3）：15- 18.
[3] 楚志勇，侯遵泽.基于Dijkstra算法的乡镇消防站选址问题[J].中国安全生产科学技术，2011，07（2）：2.
[4] 武文越，宿海芬.Dijkstra算法在露天矿运输中的应用[J].现代矿业，2015，31（9）：9.
[5] 黄冬梅，方钱.改进的Dijkstra算法在风暴潮系统中的应用[J].计算机工程，2010， 36（20）：10.
[6] 巩艳芬，刘吟.Dijkstra算法在企业物流运输网络中的应用[J].大庆石油学院学报， 2005，29（4）：8.
[7] 陈飞儿，张仁颐.上海港集装箱内河集疏运网络优化[J].上海交通大学学报，2006，40（6）：6.
[8] 李敬贤，厉小润.求解震后最优路径的改进Dijkstra算法[J].计算机工程，2012， 38（6）：3.
[9] 刘春年，邓青菁.应急决策信息系统最优路径研究——基于路阻函数理论及Dijkstra算法[J].灾害学，2014（3）：7.

随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/3/10 6:49:08