最优路径算法在交通地理信息系统中的运用分析

2021-12-29胡卫荣

科学与信息化 2021年9期

胡卫荣

北京晶众智慧交通科技股份有限公司北京 100012

城市化建设步伐加快，交通压力一直困扰着城市交通发展，在这种情况，交通地理信息系统积极应用最优路径算法。在交通地理信息系统及时在收集城市交通数据与存储管理数据，详细分析数据，协调城市交通空间基础上，最优路径算法协助交通地理信息系统，能够将地图灵活变大或者缩小，并增加图层控制功能，及时进行地理信息查询服务，进一步完善交通信息查询模式，保证为公众提供实时准确的交通信息。不仅如此，最优路径算法还能够对站点覆盖率进行准确计算，科学分析交通缓冲区，为公众了解交通信息提供更多方便。

1 交通地理信息系统中最优路径算法设计思路

最优路径算法在交通地理信息系统中的应用，针对其具体特点与交通地理信息系统需要，积极进行优化设计。基本设计思路中，在交通地理信息系统中，设置好网络标号，以点（dj、pj）为中心，涉及起源点s、节点j之间的长度，此为dj，若s、j点之间无距离，则将其称之为零路。起点s、节点j相互连通中最短路径为pj。由此为设计载体，计算两点之间最优路径。

第一，提前将节点进行初始化处理。所有点的值均设置为空值，其中起始点除外的节点，dj在初始状态相当于无穷大，pj则代表任意点的任意值。将起源点s进行标记，并调整为s=k，不需要标注其他点[1]。

第二，将已标记节点进行统计，以k为代表，该点与其相连接的没有进行标记的节点，以j为代表，计算两者之间的距离，并得到：dj=min[dj,dk+1kj]，计算公式中，直接连接的距离为1kj。

第三，根据交通地理信息系统提供的信息，将下一节点提前选取完毕，其中dj的选择一定要符合未标记、最小要求。节点的选择公式如下di=min[dj,未标记点总和j]作为已标记点i，其在交通地理信息系统中，属于路径最优与最短点。连接节点i与其之前节点，结合已标记节点，连接之前节点j*，这期间，之前阶段与当前节点是同等关系。

第四，根据当前标志的节点，将节点途径位置全部纳入到标记点中，及时完成最优路径计算，并得到最终地理想路径。

2 最优路径算法进一步优化

最优路径算法在交通地理信息系统中的应用，根据其设计思路进一步简化，将标记点划分为未标记、永久标记与临时标记，方便最优路径计算与资料整理。初始化状态下，所有点均属于未标记类型，根据交通地理信息系统的搜索以及统计分析，选择出接近最短路径的点，设置为临时标记，因为最优路径计算具有循环性特点，所以临时标记点是计算参考的关键点。在搜索中寻找最优路径位置，并标注出最短位置，此标记类型为永久标记[2]。在循环标记过程中，不断增加临时标记点，将最优路径所有点均标记完毕，最优路径算法运行结束。改变临时标记无序存储的不足，打破最优路径算法运行瓶颈，可以更迅速地锁定需要搜索节点，不需要将全部临时标注一一过滤[3]。以最短路径为出发点将临时标记节点进行排序，减少临时标记过滤时间与数量，从而更快的得到最终的目标节点。

3 最优路径算法中的直线优化运用

针对最优路径算法在交通地理信息系统中的应用，采取直线优化的方式，将最优路径中的搜索范围有效缩减，减少冗余搜索，迅速确定目标节点。在平面网络基础上，起源点与临时标记点之间的距离，属于临时标记点重要属性值，同时目标点与临时标记点之间的距离同样属于临时标记点属性值。结合临时标记点属性值为永久标记点的选取重要依据，永久标记点尽可能选择属性值中的最小值。最优路径算法的直线优化升级，将搜索手段进行智能化处理，不仅节点数量明显减少，同时在很大程度上将搜索速度加快。

3.1 对比搜索过程的优势

最优路径算法的直线优化处理，改变原有算法应用期间，以起源点作为基础圆心，随后搜索过程中会生成很多同心圆，但是在过程中并没有对终点位置或者方向有过多地考虑，从圆心开始进行搜索，搜索速度与概率并相对较慢。但是直线优化后的最优路径算法，其在终点搜索期间，会设定终点、起源点之间的临时点作为搜索焦点，形成同心椭圆搜索路径，搜索速度明显加快。结合测试可以发现，整个搜索中，所有搜索目的均迅速集中在终点，根据临时节点的引导，搜索节点减少，搜索效率更高。

3.2 直线优化应用范围

最优路径算法中，直线优化处理后，相对原有算法，非常适用于弧长度计算，尤其是权值以网络中弧为主。设定网络系统这个整体为一个平面，在这个平面通过起源点、临时节点等计算最短路径。交通地理信息系统中，直线优化的最优路径算法更适合小范围地理搜索。在不同方面将搜索范围与速度进行了明显调整。以起源点为中心，在系统运行过程中逐渐向网络边界靠近，忽略掉不必要节点，以最快速度完成系统搜索。从节点数量上来讲，直线优化节点数量减少基础上，结合网络以及交通地理信息系统运行，及时进行差异性分析，调整更加灵活，搜索更加便利。在相同范围条件下，若起源点与终结点之间并不是连通状态，则需要将搜索范围调整到全部，节点不能作为终结点之间的媒介，而是全面性搜索。提前对节点数进行确定，根据节点数去确定计算最短与最优距离的数值，积极进行最优路径计算。