油气管道应急资源调配最优路径研究

聂宸菡

（北京建筑大学 测绘与城市空间信息学院，北京100044）

在过去较长时间内，由于我国缺乏对各类油气管道事故管理的重视，基于我国拥有12 万公里陆上油气管道的现实，而其中30%以上的管道运行时间超过10 年，形成了管道事故率偏高的现状。油气管道事故发生后，由于管道是连续的，往往会同时或者延后出现多个事故点。并且油气管道事故发生后会引起泄露，大量易燃、易爆、有毒有害物质的释放，又将会导致火灾、爆炸、中毒等严重事故的产生[1]。

基于此本文将探讨研究如何选取应急资源调配的最优路径，来满足油气管道自身特点以及灾害后的应急需求。

1 最优路径的常见算法

1.1 Dijkstra 算法

Dijkstra 算法，基于贪心算法。算法的中心思想是解决地图中单个节点到其他顶点的最短路径问题。Dijkstra 算法是一种比较典型的最短路径算法，它用于计算一个节点到其他所有顶点的最短路径[2]。

Dijkstra 算法的具体原理以及实现步骤如下，首先设A 为起点节点，求A 到其他所有顶点B、C、D、E 和F 的最短路径。

图1 Dijkstra

（1）将图中所有顶点分为S 和V 两个集合：首先，先将A 节点选入进S 集合中，此时S=（A）；这时的最短路径是A=0，以A为中心点。V 是未知最短路径顶点的集合；

（2）选入B 顶点进入S 集合，此时集合中A,B 以B 为中心点，求得起点节点到B 点的最短路径；

（3）遍历V 集合，寻找距离起点最近的顶点，将此顶点放置于S 集合中，求出起点到当前顶点间的最短路径；

（4）重复（3）步，直至V 集合为空集合，算法终止，求出起点节点A 到图中其他所有顶点（B-F）之间的最短路径。

1.2 Best-First 算法

Best-First 算法又称作最佳优先搜索算法，这是一种启发式搜索算法（Heuristic Algorithm），且是基于广度优先搜索算法[3]。不同点在于Best-First 算法依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。

算法实现步骤如下：

（1）从S 中选择出权重最高的节点A，并生成子节点B。如果B 不在S 和V 集合中，通过评估函数计算出B 节点的权重，并添加进S 中，根据评估价对S 集合中的节点进行排序；

（2）反之，如果B 节点在S 中，则通过评估函数计算B 节点的权重，如果权重高于B 节点的权重，则替换原先权重，并对S中的节点排序；

（3）如果B 节点在V 中，先通过评估函数计算出B 节点的权重，如果高于V 中的权重，移除B 节点，添加到S 中，并对S中的节点排序；

（4）把A 节点从S 移除并添加到V；

（5）循环上述操作直到找到目标点，或者S 没有节点为止。

1.3 A*算法

A*算法是比较流行的启发式搜索算法之一，同时也是路径搜索中最欢迎的选择[4]。因为A*算法相当灵活，并且能用于多种多样的情形之中。

A*算法的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价该节点处于最短路线上的可能性的量度。A*算法的如下式：

f（n）=g（n）+h（n）

A* 算法设置两个列表，开启列表（open） 和关闭列表（closed）。A*算法的具体步骤为：

图2

2 最优路径算法的比较分析

本文利用实验室项目数据做了实验，如下表。

搜索结果

从实验结果的表格可以看出，A*算法所消耗内存、扩展节点、时间优越于另外两种算法。A*算法和Dijkstra 算法总能找到最优路径，但由于Best-First 基于贪心策略，仅仅考虑到达目标节点的花费，而忽略了当前已花费，导致找到的路径有可能不是最优路径。

3 结论

油气管道事故发生后，为了使应急救援资源快速到达事故现场，减少灾害损失，深入分析了三种经典的最优路径算法。首先，对这三种最优路径的核心思想与算法流程进行完整的描述；然后，对这三种最优路径算法进行全面的比较分析，通过实验对比，得出在求解最优路径时，A*算法作为一种经典的启发式搜索算法优越于另外两种算法，能够高效的找到两点之间的最优路径。A*作为一种启发式算法，构造合适的启发式函数，所求得的最优路径将更符合实际情况，致力于改进和完善传统的最优路径搜索A*算法将会成为我们的下一步工作。