基于改进Dijkstra算法的瓦斯应急模拟演练研究
时间:2019-04-15 13:53:09 来源:伽师信息网 作者:匿名
基于改进Dijkstra算法的瓦斯应急模拟演练研究 作者:未知 摘要:在应急气体应急响应中,应急人员需要在第一时间到达现场。城市道路的最短路径搜索是应急人员第一次到达现场的关键,但考虑到实际的道路状况比较复杂,如果只有最佳路径可能导致该路段因其他路径而通过临时交通管制等因素。 通过引入时间权重和邻接矩阵以及改进的Dijkstra算法进行最优路径搜索,为应急响应者提供多条最短路径,并使用Anylogic软件模拟气体应急泄漏事故的应急响应,验证Anylogic软件的可行性。燃气应急响应仿真评估。 关键词:燃气应急;应急响应; Dijkstra算法;最佳路径; AnyLogic的;时间重量;邻接矩阵 中图分类号:TN913.1?34文献标识码:A文章编号:1004?373X(2018)20?0018?06 关键词:燃气应急事件;应急处置; Dijkstra算法;最佳路径; AnyLogic的;时间重量;邻接矩阵0 近年来,中国主要及以上燃气安全事故的数量已成为燃气行业面临的严峻问题。当发生事故时,第一次紧急治疗尤为重要。 气体应急响应者是否能够在收到报警后第一时间赶到现场是应急响应的关键。 今天的城市交通道路很复杂,可能有最短时间的多条最佳路径。然而,基于当前的气体应急响应情况,基本上只提供一条最佳路径,这通常导致提供最佳路径,因为临时气体紧急响应者在交通控制和其他原因不可用时无法快速选择剩余的最佳路线。因此,为了避免上述情况和综合城市交通道路的实际情况,本文提出利用改进的Dijkstra最短路径搜索算法为燃气应急响应者提供多条最短路径,使燃烧獯χ嗽嗽筛? ?根据实时情况最佳地选择道路状况并在最短的时间内到达事故现场以确保应急响应的黄金时间。 同时,利用Anylogic软件模拟了瓦斯事故泄漏事故的应急响应,验证了Anylogic软件在瓦斯应急响应仿真评估应用中的可行性。 1 Dijkstra最短路径算法 路径规划的核心是最短路径算法。研究最短路径的算法有很多,如启发式搜索算法,神经网络方法,基于遗传算法的最短路径搜索和蚁群算法。 传统的最短路径搜索算法主要包括Floyd算法和Dijkstra算法。 Dijkstra算法是典型的单源最短路径算法,用于计算从一个节点到所有其他节点的最短路径。 它的主要特征是从起始点扩展到外层,直到它延伸到终点;第二,它是一种具有高应用价值的代表性最短路径算法[1]。 Dijkstra算法也称为双标签方法。 所谓的双重标记是将两个标签[Pvi,λi]分配给图中的点[vi]:第一个标签[Pvi]表示从起始点[v1]到[vi]的最短路径长度;第二个标签[Λi]表示[v1]到[vi] [vi]最短路径上的前一个相邻点的下标,用于表示路径,以便到达起点的终点可以回溯,找到[v1]到[vn的最短路径]。 以下是Dijkstra算法的内容:2改进Dijkstra算法 基于对Dijkstra算法的分析,可以看出Dijkstra算法在最短路径上仅默认为顶点的一个前导码。 但事实上,最短路径上的顶点可能有多个邻居。从源点到顶点,可能存在具有相同权重的多个最短路径。采用Dijkstra算法的改进来解决多路径的最短问题。 2.1邻接矩阵 为了更好地实现Dijkstra算法,邻接矩阵用于表示无向加权图,并且设置无向加权图[G1=V,E](参见图1)。顶点集[V]为[V=V1,V2,...,V5],边长[E=E1,E2,...,E6],则5阶方阵的邻接矩阵为无向加权图如图2所示。 矩阵反映了顶点和顶点之间的关系。矩阵的每个元素表示顶点之间的边的权重。 如果矩阵元素[aij]是[∞],则两个顶点之间没有直接连接的边;如果矩阵元素[aij]是正整数[ωij],则在两个顶点之间存在边缘,边缘权重为[ωij];如果矩阵元素[aij]为0,则表示邻接矩阵的主对角线上的元素都是0。 使用邻接矩阵来表示加权图更直观,并且Dijkstra算法需要多次修改顶点的最短路径长度。邻接矩阵用于表示加权图,矩阵中的元素也易于修改。 2.2算法改进 本文中使用的改进的Dijkstra算法是[2]中提出的方法。它主要解决Dijkstra算法中的多个最短路径问题和多个相邻点。算法设计和改进如下: 1)初始化 对所有顶点进行编号并构造邻接矩阵。 起点设置为永久标签(p标签),其余顶点不是永久标签。 根据起点,找到起点邻近点的最短路径,前一个邻点及其数量。 2)找到下一个永久标签的顶点(p标签) 通过邻接矩阵,找到没有永久标签和最短路径长度的顶点v。 如果顶点v的最短路径长度是无穷大,则退出算法,否则,将顶点v设置为永久标签(p标签)。 通过顶点v和邻接矩阵,获得顶点v和前一个相邻点的相邻点x的最短路径长度及其数量。 如果通过顶点v到相邻点x的起始点的路径长度小于相邻点x的现有最短路径长度,则顶点x的最短路径长度是从顶点v到顶点v的路径长度。顶点x的起点。3)找到下一个永久标签的顶点(p标签)。如果所有顶点都有永久标签,请退出程序[2],否则转到步骤2)。 3城市交通道路模型的建设 城市动态交通路径选择系统分为两部分:一是建立城市交通路径拓扑;另一个是建立城市交通道路选择的数学模型。 由于实验时间和其他条件的限制,一些城市交通路线图被模拟以抽象城市交通拓扑。 模拟的城市交通路线图如图3所示。 假设模拟了城市交通道路地图中的道路相关信息。每条道路的相关信息主要包括:设计速度,路段名称,路段长度,道路拥堵系数(以0和1,0表示,0表示正常道路,1表示道路)完全拥挤,无法通过)。 在本文中,所选链接的权重与链接的长度和链接的传播时间相结合。如果两个节点没有连接,则两个节点之间的距离为∞,用∞表示。 相应的路径拓扑如图4所示。 节点代表交集;单条实线代表路段。 权重是道路某些特征属性的定量表示。 因为权重是Dijkstra算法计算最短路径的基础,找到最短路径,即起点和终点之间的最低消耗,因此确定权重是准确性的关键。算法。 在本文中,对应于每个路段的权重被设置为相等,即,每个边缘具有一个且仅一个权重。 在传统的Dijkstra算法中,权重仅表示两个节点之间的距离。 由于道路状况,道路旁路距离和交通状况的影响,不同交通路线所需的时间虽然车辆行驶的距离相同,但仍然不同。 因此,判断是否是城市交通道路距离的最佳路径的方法不准确。 本文主要解决了燃气应急应急响应中的路径优化问题,即应急调度员接收调度中心指挥调度,并通过该旅的位置冲向事故现场的路径优化过程。 该问题与一般路径优化问题的不同之处在于它需要考虑实际的道路环境,例如道路拥堵程度和行驶速度。从紧急情况来看,本文的最优路径搜索是在最短的时间内完成的。 因此,本文以最短到达时间为准则,改进了权重的设定。当考虑最优路径时,通过组合道路的距离和拥塞系数来确定权重,使得最优路径搜索结果是具有最短时间的路径。 经过研究和研究,发现在消除突发事件影响的条件下,城市主干道路的日常拥堵情况相似,并提出在下列拥堵条件下实施该算法。 设置[QDi?Dj] [i,j=1,2,...,17]来表示道路的权重[CDi?Dji,j=1,2,...,17](以下简称道路) C),[YDi?Dj] [i,j=1,2,...,17]表示道路C的拥堵系数,[LDi?Dj] [i,j=1,2,...,17 ]表示道路C的路径长度,[VDi?Dj] [i,j=1,2,...,17]表示车辆的实际行驶速度,并且车辆的行驶速度与实际相结合情况。假设每辆车的正常行驶速度[V0]为60km/h,则不同。在道路拥堵的情况下,车辆的速度公式为: 通过上述道路重量确定公式,确定模拟城市交通道路地图的道路权重,如表1所示。 4 Anylogic建模分析 4.1紧急维修团队 应急救援队包含一般气体应急应急响应所需的人员和车辆设备,包括指挥,控制,压力控制,泄漏检测,泄漏检测,管道定位,管道修复,防腐修复,土方工程,环境浓缩监督几类人员。 紧急救护队在收到调度中心的紧急维修任务清单时,必须携带必要的维修材料和车辆到现场进行维修。 4.2气体泄漏应急处理过程 气体泄漏应急处理过程主要包括以下步骤:浓度检测和环境监测,管道压力控制,边缘控制和疏散,泄漏检测定位,挖掘光亮管,配方计划,操作修复和精加工回收。 4.3 Anylogic建模在Anylogic中,对应急救援队的应急救援模式进行了建模和分析,以验证应急救援队应急响应模式的可行性。根据气体泄漏应急处理流程,应急响应中涉及的人员和材料分别由代理人代表,并使用代理修复理论对修复过程进行建模,从而构建基于此的应急响应处理模型。 Anylogic平台上的Multi?Agent。 以检测定位人员模型的建立为例,总结了模型的建立过程。 为建立人员检测和定位模型,首先要明确检查人员在气体泄漏应急响应过程中的职责和标准行为。 责任和标准行动如下: 1)接到维修任务清单后,按照紧急救援队赶到事故现场; 2)对现场泄漏现场的管道进行定位检测,确定管道信息; 3)将测试结果报告给指挥官; 4)回到现场等候区。 在Anylogic平台中,检查员的位置是根据城市交通路线图确定的,检查员是以状态图的形式建模的。检查员的模型如图5所示。 5 Anylogic实验模拟 5.1在Anylogic中实现Dijkstra算法 为了验证Dijkstra最优路径算法在气体泄漏应急响应中的有效性,Dijkstra算法在Anylogic平台上以Java语言实现。 以图3的城市交通仿真图为实验场景,假设D1是应急修复旅的位置,D12是事故现场的位置。 已经计算了道路重量。 图6是城市交通道路的无向加权图。 从图6中可以清楚地看到每条道路的重量。可以看出,道路D8~D9,D6~D10具有较大的重量并且是道路的较长部分。 为了更好地研究和编程Dijkstra算法,邻接矩阵用于表示图6中城市交通道路的无向加权图。 图7是部分邻接矩阵,示出了使用邻接矩阵的城市交通道路的无向加权图。 最优路径算法的运行路径为D1,目标顶点为D12。获得两条最优路径:D1?D13?D12; D1?D3?D11?D12。 5.2 Anylogic气体泄漏应急处理模拟演习通过Anylogic平台模拟燃气泄漏应急处理过程,验证应急救援队和Anylogic软件在燃气应急响应评估中的可行性,为燃气应急响应标准化提供支持。 Anylogic气体泄漏应急模拟演练的城市交通图是图3的模拟城市交通图。 图8是Anglogic软件中的气体泄漏应急响应模拟的3D视图。 6实验结果分析 在Anylogic软件中,基于城市交通道路模拟图建立交通道路模型。 根据道路长度和拥堵系数等参数确定道路的权重属性。 在确定属性之后,将城市交通道路地图转换为无向加权地图,并且使用邻接矩阵来表示无向加权地图。 邻接矩阵被编程到改进的Dijkatra算法程序中,以在Anylogic软件中实现改进的Dijkstra算法。 改进的Dijkstra算法在Anylogic中实现,并且获得具有相同权重的以下两个最短路径:D1≤D13≤D12; D1?D3?D11?D12。 图9中的紫色表示具有相同重量的最短路径。 为燃气应急响应者提供两条最佳路径。当D1?D3?D11?D12的其中一条道路由于临时交通控制或其他意外情况而更加拥挤时,通过该路段将花费更多。通常更多的时间,所以燃气应急响应者可以选择最佳的道路,D1?D13?D12,根据实时路况。 图10显示了在结合实际道路状况后沿最佳路径的Anylogic软件操作中的气体应急响应者。 在Anylogic中运行改进的Dijkstra算法,获得具有相同权重的两个最佳路径。传统的Dijkstra算法在最短路径上只有一个前导码点。只能获得最短路径的结果。在上述情况下,不能给出剩余的最短路径结果。 在Anylogic软件中,对到达现场后的应急维修队进行了仿真,验证了气体泄漏应急处理过程的可行性,验证了Anylogic软件在气体应急响应仿真评估中的可行性。具体的修复过程如图11所示。 7结论 针对基于Anylogic气体泄漏应急处理的气体泄漏应急处置和模拟的最优路径,建立了模拟城市交通道路的数学模型。 引入时间权重和邻接矩阵的方法采用传统Dijkstra算法的改进,为气体应急响应者提供相同权重的多个最短路径,并采用改进的Dijkstra算法结合气体泄漏应急处理仿真模拟进行验证。为气体应急响应人员到达事故现场之前计划的多条最佳路线。 燃气应急响应人员可以结合当前的路况选择最佳路径,验证了Anylogic模拟评估应用在燃气应急响应中的可行性。 引用 [1]袁琳,王媛,孙建彪,等。基于权重的Dijkstra停车道规划算法优化与实现[J]。湖北大学学报(自然科学版),2017,39(3):279?284。 袁琳王媛孙建云等基于权重计算的停车路线规划优化Dijkstra算法设计与实现[J]。湖北大学学报(自然科学版),2017,39(3):279?284。 [2]王淑玺,李安珍。 Dijkstra算法中的多个邻点和多个最短路径问题[J]。计算机科学,2014,41(6):217?224。 王淑曦,李安宇Dijkstra算法的多邻接顶点和多最短路径问题[J]。计算机科学,2014,41(6):217?224。 [3]王宏。集装箱海铁联合运输优化路径算法设计与仿真[D]。北京:北京交通大学,2017。王红集装箱海铁运输最优路径算法的设计与仿真[D]。北京:北京交通大学,2017。 [4]段义东,侯志群,朱大明。基于Java的Dijkstra最短路径算法的实现[J]。价值工程,2016,35(21):208?210。 段如东,侯志群,朱大明基于Java的Dijkstra最短路径算法的实现[J]。价值工程2016,35(21):208?210。 [5]严倩。燃烧修复中模拟练习与辅助决策的关键因素及相关性研究[D]。北京:北京建筑大学,2015。 严倩气体尺寸抢修中模拟钻井辅助决策的关键因素及相关性研究[D]。北京:北京建筑工程学院,2015。 [6]张旭峰。第三方物流企业配送网络演化规律及路径优化研究[D]。北京:北京工业大学,2012。 张旭峰第三方物流企业配送网络演化规律及路径优化研究[D]。北京:北京工业大学,2012。[7]刘超。输气输配应急管理模拟系统研究[D]。北京:北京建筑大学,2014。 刘超输气输配应急管理模拟系统研究[D]。北京:北京建筑工程学院,2014。 [8] MCNALLY P,MINYARD E.石油和天然气勘探和生产的应急准备[C] //SPE E的会议记录

http://web.yaolirong.cn 360doc个人图书馆