基于GIS的路径规划算法研究

基于GIS的路径规划算法研究

阚晓军

（江苏远大地信科技有限公司，江苏扬州 225002）

摘要：本文对基于GIS的路径规划算法进行综述，着重介绍了三种路径规划算法的寻优能力、效率、优缺点以及总结算法的改进方式、方案，并对未来的改进方向进行了展望。

关键词：GIS；路径规划；算法

1引言

地理信息系统(GIS)就是一种利用计算机对有关地理、空间位置的数据信息进行存储、处理、查询和显示的计算机支持系统。GIS的发展始于60年代， 90年代以来，随着互联网络的发展及国民经济信息化的推进，地理信息系统作为大的地理信息中心，进入日常办公室和千家万户之中，从面向专业领域的项目开发到综合性城市与区域的可持续发展研究。21世纪以来，3D可视化技术发展势头迅猛，已经实现GIS环境下的三维建筑物室外室内漫游、信息查询、空间分析、剖面分析和阴影分析等，基于虚拟现实技术的真三维GIS将使人们在现实空间外，可以同时拥有一个Cyber空间。随着寻径算法已经越来越贴近我们的生活，面向各种用户群的导航应用也逐渐深入我们的生活，另一方面，随着我国各个城市建设的发展，每个城市地图变的越来越复杂，信息量越来越大，在单一层面的寻径算法已经遇到了性能上的瓶颈，因此，结合GIS技术的路径规划算法研究显得格外重要。

2 GIS 路径规划

从技术方面， GIS路径规划系统集成嵌入式地理信息系统、数据库技术为一体，以电子地图为基础数据库，以Windows CE、EVC++为开发平台，根据用户需求实时规划出一条最佳路径。地理信息系统(GIS)是收集、管理、操作、分析和显示空间数据的计算机软硬件系统，集成了计算机数据库技术和计算机图形辅助设计软件。目前用于GIS应用软件开发的模式有很多，其中组件式GIS软件开发是目前较为流行、高效、快速的开发模式。组件GIS是指基于组件对象平台，以一组具有标准通信接口、允许跨语言应用的组件提供的GIS应用。Super Map即是超图公司自主研制的嵌入式GIS开发平台，具有精简内核，运行时占用资源非常少，速度快，可以在各种高低端的嵌入式设备中运行，提供精简的PMI文件格式，支持压缩和加密，对于资源紧缺的嵌入式设备非常重要。 随着路径规划算法的深入研究与改进，与GIS 技术结合的路径规划算法更加智能化、自主化，但同时也存在一些问题，由于不同行业和领域中的应用需求不同，所存在的问题也不同，因此，需要对不同的问题进行分析改进。

（1）算法局限性问题。经典单一算法无法处理一切路径规划，在简单环境中操作简易、使用方便、效率高，但复杂环境该会表现出自身局限性；对于混合算法虽然可以处理大部分路径规划问题，但是开发新的混合算法复杂程度高且不一定有效。针对算法局限性方面，应在传统算法上引入突变思想，提高算法局限性，增强算法适应性。

（2）环境建模问题。建立更加符合真实情况的环境模型与算法相融合是一个跨学科。现有的环境模型多是将目标作为一个质点在任务空间中模拟，这种环境模型过于理想化，便于求解，忽视了现实情况的复杂性，从而导致真实情况下的路径规划效果差。针对环境建模问题，应提高建模环境的复杂性，增加约束条件，同时考虑目标自身的特点。

（3）实时动态监测问题。现有的路径优化算法多是在障碍物及目的地已知不变的情况下，但实际情况存在许多不确定性，使得目标在面对突发情况时的路径规划无法应对。针对实时动态监测方面，应结合启发式算法提高环境的动态性，增强算法的动态规划能力。

3 GIS 路径规划算法

3.1.几何模型GIS 路径规划算法

Dijkstra 算法(狄克斯特拉算法)是一种基于贪婪策略，采用广度优先搜索思想，以拓扑连通图的起始点为中心逐步向四周扩展来找寻最优路径的经典全局路径规划算法，被广泛应用于二维环境中有向图最短路径问题。该算法适用性高，适合大多数场景，但在复杂情况下，存在着时间复杂度高，遍历节点多，效率低下等缺点。针对传统Dijkstra 算法在复杂情况下路径规划时间复杂度高的问题，某文献中将蚁群算法的思想加入经典Dijkstra 算法中，加入类似信息素的判别因子，减少最优路径的冗余杂点。某文献中提出了一种多标号并行的方法对遍历过程做出改进，同时，对于模型处理的速度，采用并行求解的方式来提升，大幅缩短运行时间，提高了路径规划效率。针对多目标寻优问题，某文献中在传统的Dijkstra 算法中加入预搜索实现算法的回溯功能，通过使用归一化熵权法建立评价函数，简化路径优化模型，此外，在预搜索遍历过程中加入跳出机制，解决了传统Dijkstra 算法在多约束条件下搜索失败率高，运算时间久的问题。某文献中提出了一种双向搜索最优路径的方法，即从目的地和终点同时进行搜索，调整搜索区域面积，减少搜索节点的数量，该算法时间权重更少，综合性能更好。某文献中提出了一种改进的动态路径规划算法，通过分析环境因素对道路权重的影响程度来改进算法，不同的影响因子设置不同的弧段权值，提高了传统算法的路径规划时间。

3.2启发式GIS 路径规划算法

遗传算法最早由美国教授提出，是借用自然选择，通过生物遗传、变异、交叉等模拟生物自然进化论的一种自适应并行全局优化搜索算法。其基本原理是效仿自然界生物“物竞天择，适者生存”的法则，提高各个个体的适应性。该算法具有高效、实用、鲁棒性强等优点，被广泛应用于神经网络、机器学习、模式识别等领域求解NP 问题、多峰函数和多目标优化问题，但也存在着过早趋同，计算密集等缺陷。针对传统遗传算法在多约束条件下寻优能力差，算法收敛速度慢，易于陷入局部最优解问题，某文献中通过构建栅格地图，设置约束条件，在目标函数中增加删除算子提高算法迭代效率，并引入小生境法避免算法过早的陷入局部最优解。为解决遗传算法在路径规划中由于交叉和突变产生不可行路径的问题，某文献对路径表示采用二进制编码的方式，再与粒子群算法结合，重建变异算子，在适应度评估中加入惩罚因子，避免陷入局部最优解，最后，对无效路径，加入修复机制，保持种群多样性。某文献提出了一种新的突变方法，该方法根据总路径的适应度接受节点，同时检查靠近突变节点的所有自由节点，提高了传统遗传算法的收敛速度。

某文献利用Voronoi图对路径规划的区域进行划分，并将传统遗传算法与贪婪算法结合，建立了一种新的遗传交叉算子—贪婪交叉算子，改善了遗传算法的收敛性。

3.3混合路径规划算法

单一算法各有优劣，因此，除了在传统算法的基础上进行改进之外，国内外学者尝试将不同的算法进行结合，使得新算法在路径规划中效率更高。某文献将爬山算法的局部搜索能力与蚁群算法结合，设计了一种新算法弥补蚁群算法的早熟现象。首先对蚂蚁走过的路径进行归一化处理，改进信息素增量函数；其次，挑选经历第一次蚁群算法的随机数量蚂蚁进行爬山操作得到爬山最优解，再将爬山最优解代入蚁群算法中再次挑选，直至迭代完成得到最优解。某文献将爬山算法、蚁群算法和遗传算法结合起来，首先，利用遗传算法的随机搜索性和全局收敛性，将爬山策略用于遗传选择，与轮盘赌法相结合，增强寻优效果，在初始种群中不断迭代，选择出初始最优解集；其次，将遗传算法得到的最优解作为信息素，利用蚁群算法的并行性、正反馈机制对初始最优解集反复进行局部搜索获得最优解。针对遗传算法局部搜索能力弱的问题，某文献将爬山算法与遗传算法相结合，对每一代最优个体采用多次爬山策略代替原个体，增强算法的局部搜索能力，提高了算法的计算效率和稳定性。

4结束语

结合GIS 技术的路径规划算法发展至今已经日趋成熟，本文主要阐述了基于几何模型、基于启发式和基于混合的路径规划算法，从算法的时间复杂度、多目标寻优及搜索效率等角度分析了基于GIS技术的路径规划算法，并从算法的局限性、环境建模、动态监测等方面进行分析展望。当前，静态路径规划算法已相对成熟，但实时动态路径规划算法仍存在着很多问题，因此，接下来的研究方向应着重考虑多学科交叉融合形成更加高效的路径规划算法。

参考文献：

[1]严寒冰,刘迎春.基于GIS城市道路网最短路径算法探讨[J].计算机学报,2016,23(2):210～215.

[2]吴京,景宁,陈宏盛.最佳路径的层次编码及查询算法[J]计算机学报,2019,23(2):184～189.

[3]袁丰桥.基于GIS的校园路径规划系统设计与开发[D]:杭州: 浙江工业大学, 2020.