1. 引言
GIS技术(Geographic Information Systems) [1] [2] [3] [4] [5] ，即地理信息系统技术，是近些年迅速发展起来的一门综合性的、多种学科交叉的空间信息分析技术。因其具有体积小、重量轻、密封性好、运行可靠性高、运输周期短及成本低等优点，被广泛应用于农业、林业生产、土地资源、生态环境以及自然灾害等领域。通过与遥感技术、地图学以及摄影测量学等学科技术相结合，在路径规划问题中得到了广泛的应用。GIS可以有效地动态监测和分析多时期的环境资源状况及生产活动变化，将收集起来的信息、数据、决策等综合为一个信息流，提高工作效率。在现实环境中，由于环境的多变及突发情况的不确定性，如果以GIS技术为载体，结合定位技术和路径规划算法，找寻出一条不同约束条件下的最优化路径，将会极大地缩短时间，减少人力资源成本的浪费。因此，结合GIS技术的路径规划算法 [6] [7] [8] [9] [10] 研究显得格外重要。
本文主要对GIS技术相结合的路径规划算法进行综述，着重介绍了每种路径规划算法的寻优能力、效率、优缺点以及总结算法的改进方式、方案，并对未来的改进方向进行展望。
2. GIS路径规划分类
路径规划不能只考虑始发点与终点之间的最短路径，同时还要考虑这两点间的道路情况，如在城市道路中，需要考虑红绿灯、道路长度、堵车、天气等一些突发状况。而GIS技术可以了解到实际情况，通过对这些信息的综合，就可以获得真实距离。获取道路真实情况是前提，而更好、更快、更精确的规划出一条最优路径最重要的部分是算法的选取。GIS路径规划算法最重要的是效率高、鲁棒性好，因此，选择合适的路径规划算法不仅可以保证全局最优化，而且可以更好的与GIS技术结合，提高各个领域工作效率和工作能力。目前，国内外学者对GIS技术路径规划算法进行了大量研究，并且在基本算法上做出改进创新。本文根据GIS路径规划实现方式，将算法分为三类，一类是几何模型的GIS路径规划算法，如Dijkstra算法 [11] [12] [13] [14] [15] ，A*算法 [16] [17] [18] 等；另一类是启发式GIS路径规划算法，如蚁群算法(ACO) [19] [20] [21] ，遗传算法(GA) [22] [23] [24] [25] ，模拟退火算法(SA) [26] [27] [28] [29] ，爬山算法(HC) [30] 等；最后一类是将各种单一算法结合起来的混合路径规划算法 [31] [32] [33] 。具体分类如图1所示。
Figure 1. The GIS path-planning algorithm
图1. GIS路径规划算法
3. GIS路径规划算法
3.1. 几何模型GIS路径规划算法
3.1.1. Dijkstra算法
Dijkstra算法(狄克斯特拉算法)是一种基于贪婪策略，采用广度优先搜索思想，以拓扑连通图的起始点为中心逐步向四周扩展来找寻最优路径的经典全局路径规划算法，被广泛应用于二维环境中有向图最短路径问题。该算法适用性高，适合大多数场景，但在复杂情况下，存在着时间复杂度高，遍历节点多，效率低下等缺点。
针对传统Dijkstra算法在复杂情况下路径规划时间复杂度高的问题，文献 [11] 中将蚁群算法的思想加入经典Dijkstra算法中，加入类似信息素的判别因子，减少最优路径的冗余杂点。文献 [12] 中提出了一种多标号并行的方法对遍历过程做出改进，同时，对于模型处理的速度，采用并行求解的方式来提升，大幅缩短运行时间，提高了路径规划效率。针对多目标寻优问题，文献 [13] 中在传统的Dijkstra算法中加入预搜索实现算法的回溯功能，通过使用归一化熵权法建立评价函数，简化路径优化模型，此外，在预搜索遍历过程中加入跳出机制，解决了传统Dijkstra算法在多约束条件下搜索失败率高，运算时间久的问题。文献 [14] 中提出了一种双向搜索最优路径的方法，即从目的地和终点同时进行搜索，调整搜索区域面积，减少搜索节点的数量，该算法时间权重更少，综合性能更好。文献 [15] 中提出了一种改进的动态路径规划算法，通过分析环境因素对道路权重的影响程度来改进算法，不同的影响因子设置不同的弧段权值，提高了传统算法的路径规划时间。
3.1.2. A*算法
A* (A-Stra)算法是一种很常用图形路径寻优算法，在二维栅格地图上寻优效果最好，同时也是求解静态路网中最短路径最有效的直接搜索方法，结合了贪心算法(深度优先)与经典的Dijkstra算法(广度优先)，在Dijkstra算法中加入启发函数和代价评估函数进行约束，优先计算代价更低的方向，估价函数如下：
(1)
其中f(n)表示代价，即从起点f(n)开始经过某一个位置H再到达终点的代价；g(n)为当前代价，即从起点到H的实际代价；h(n)为预估代价，即位置H到达终点的代价(此代价由曼哈顿距离判断)。
该算法的基本原理是使用两个集合来表示待遍历的节点，已经遍历过的节点，从起点开始对当前位置的8个相邻节点进行位置评估，设置父节点，加入待遍历的节点列表中，计算最小代价，选取代价值最小优先级最高的节点作为下一个待遍历的节点进行搜索，重复以上操作，直到找到目标点，从终点开始，每个节点沿着父节点移动直至起点，形成实际路径。该算法具有结构简单、应用广泛、计算时间短等优点。但在大型环境中，该算法时间、空间复杂度高，搜索效率低。
针对传统A*算法搜索效率差、拐点多、最优路径中存在冗余杂点的问题，文献 [16] 中选用对角线距离作为启发函数对A*算法进行修改，并且，提出了转弯惩罚项来减少转弯次数，同时，提出路径再优化策略，删除路径中的冗余杂点，减少拐弯次数，有效的提高了路径规划的效率。文献 [17] 中将全局路径划分为距离相等的若干段局部路径，计算物体与邻近节点的相对距离和相对角度，通过将相邻两节点的欧氏距离进行累加对启发函数进行修改，减少路径规划中所需的计算量，提高了算法的稳定性。文献 [18] 中将父节点加入评价函数当前节点中，减少往返搜索次数；在二维环境中限制4个搜索方向，并且通过修改启发函数中h(n)的计算方式缩短路径及遍历空间，在三维环境中基于B样曲线对轨迹节点进行平滑处理，减少不必要的冗余杂点和拐点，提高路径搜索效率。
3.2. 启发式GIS路径规划算法
3.2.1. 蚁群算法
蚁群算法(Ant Clony Optimization, ACO)是一种源于蚂蚁集体寻径觅食行为而提出来的基于种群的启发式全局优化算法，该算法于20世纪90年代由意大利学者M. Dorigo，V. Maniezzo等人提出。它的基本原理是蚂蚁在觅食寻径的过程中，会留下信息素进行信息传递，并且通过感知这种信息素来决定自己的运动方向。因此，蚁群集体行为便会产生一种信息正反馈现象，即信息素浓度越高的路径，选择该路径的可能性越大，走过的蚂蚁就越多。该算法可以多个个体同时并行计算，有很强的鲁棒性，被广泛应用于求解旅行商(TSP)问题、分配问题等，但也存在着收敛速度慢、易于陷入局部最优等问题。
针对传统蚁群算法局限性，文献 [19] 采用CRITIC法熵权TOPSIS法改进蚁群算法，通过修改期望函数与信息素浓度更新规则，在计算最优路径时引入时间成本和环境成本，避免ACO过早陷入局部最优解问题。针对传统蚁群算法收敛速度慢，动态避障存在缺陷等问题，文献 [20] 中提出了一种基于拉普拉斯分布的改进算法，通过修改启发函数，增强信息素的引导作用；其次，引入拉普拉斯分布调节信息素挥发；最后，对蚁群得到的路径进行双向冗余节点删除平滑处理，使得二次路径优化更加平滑。针对巨大环境中的路径寻优问题，文献 [21] 中提出了一种拓展蚁群优化的SoSACO-v2算法，该算法赋予蚁群嗅觉，将食物作为特权节点，当靠近足够多的特权节点时，直接引导它们到特权节点，是一种提供更快响应的算法。
3.2.2. 遗传算法
遗传算法(Genetic Algorithm, GA)最早由美国的J. H. Holland教授提出，是借用自然选择，通过生物遗传、变异、交叉等模拟生物自然进化论的一种自适应并行全局优化搜索算法。其基本原理是效仿自然界生物“物竞天择，适者生存”的法则，提高各个个体的适应性。该算法具有高效、实用、鲁棒性强等优点，被广泛应用于神经网络、机器学习、模式识别等领域求解NP问题、多峰函数和多目标优化问题，但也存在着过早趋同，计算密集等缺陷。
针对传统遗传算法在多约束条件下寻优能力差，算法收敛速度慢，易于陷入局部最优解问题，文献 [22] 中通过构建栅格地图，设置约束条件，在目标函数中增加删除算子提高算法迭代效率，并引入小生境法避免算法过早的陷入局部最优解。为解决遗传算法在路径规划中由于交叉和突变产生不可行路径的问题，文献 [23] 对路径表示采用二进制编码的方式，再与粒子群算法(PSO)结合，重建变异算子，在适应度评估中加入惩罚因子，避免陷入局部最优解，最后，对无效路径，加入修复机制，保持种群多样性。文献 [24] 提出了一种新的突变方法，该方法根据总路径的适应度接受节点，同时检查靠近突变节点的所有自由节点，提高了传统遗传算法的收敛速度。文献 [25] 利用Voronoi图对路径规划的区域进行划分，并将传统遗传算法与贪婪算法结合，建立了一种新的遗传交叉算子—贪婪交叉算子，改善了遗传算法的收敛性。
3.2.3. 模拟退火算法
模拟退火算法(Simulated Annealing, SA)是一种基于Monte Carlo迭代求解策略的随机寻优算法，从理论上说，是一种全局最优算法，最早于1953年由Metropolis等人提出。该算法的基本原理是模拟物理固体退火过程，在高温时，加速粒子运动，物体内部的分子相对自由成无序状态，当温度慢慢下降后，热能原子的可动性就会消失，重新分布成一个有序状态，确保能量达到最低状态。该算法鲁棒性好、不易陷入局部最优解，被广泛应用于模式识别、路径规划等工程领域。
针对传统模拟退火算法局限性问题，文献 [26] 中提出了一种融合遗传算法思想的模拟退火算法，在栅格环境下，以贪心算法为基础，定义最优解和次优解系数作为优良路径进行两两配对，产生新路径，输出退火过程的最优解。针对传统模拟退火算法解决复杂非线性规划路径问题，文献 [27] 中提出了一种加入粒子群的模拟退火算法，设置迭代次数最大值，通过比较个体粒子的适应度与全局适应度，更新粒子速度和粒子位置得到最优解，完成对模拟退火算法的改进，提高了路径规划的质量。针对算法不能有效实施全局搜索的问题，文献 [28] 在原有算法的基础上提出了回火操作使全局搜索与局部搜索实现平衡，改变最优解在迭代过程的接受规则；针对多约束问题，提出了领域变换策略，同时构建满足问题约束的初始解，生成算法整体框架，提高了多约束条件下的路径规划效率。文献 [29] 提出了一种基于动态概率的模拟退火算法，首先通过蒙特卡洛模拟算法随机生成多个初始解，并选择当前解作为最优解；其次，使用交换法、移位法、倒序法产生新解，并根据对应的目标函数计算动态概率；最后，迭代终止，输出当前解作为最优解，提高了算法的收敛精度和全局寻优能力。
3.2.4. 爬山算法
爬山算法(Hill Climbing, HC) [30] 采用启发式方法对深度优先搜索进行改进，是一种简单的贪心搜索算法。该算法的基本原理是从山峰开始向高处攀爬寻找最高点，即从当前节点开始和临近节点进行比较，如果当前节点最高，则用当前节点作为局部最优解，反之，选择最高邻节点作为局部最优解，直至找到最高点。爬山算法虽然避免遍历、效率高，但同时存在着随机性，不一定能搜索到全局最优解，常与其他算法结合使用。
3.3. 混合路径规划算法
单一算法各有优劣，因此，除了在传统算法的基础上进行改进之外，国内外学者尝试将不同的算法进行结合，使得新算法在路径规划中效率更高。
文献 [31] 将爬山算法的局部搜索能力与蚁群算法结合，设计了一种新算法弥补蚁群算法的早熟现象。首先对蚂蚁走过的路径进行归一化处理，改进信息素增量函数；其次，挑选经历第一次蚁群算法的随机数量蚂蚁进行爬山操作得到爬山最优解，再将爬山最优解代入蚁群算法中再次挑选，直至迭代完成得到最优解。文献 [32] 将爬山算法、蚁群算法和遗传算法结合起来，首先，利用遗传算法的随机搜索性和全局收敛性，将爬山策略用于遗传选择，与轮盘赌法相结合，增强寻优效果，在初始种群中不断迭代，选择出初始最优解集；其次，将遗传算法得到的最优解作为信息素，利用蚁群算法的并行性、正反馈机制对初始最优解集反复进行局部搜索获得最优解。针对遗传算法局部搜索能力弱的问题，文献 [33] 将爬山算法与遗传算法相结合，对每一代最优个体采用多次爬山策略代替原个体，增强算法的局部搜索能力，提高了算法的计算效率和稳定性。
3.4. 总结
本节将结合GIS技术的路径规划算法简单的分为三大类——基于几何模型、基于启发式、基于混合的路径规划算法。其中，基于几何模型的路径规划算法适用于二维环境中，该类算法结构简单、适用性高，但需要遍历更多的节点，因此效率不高。基于启发式的路径规划算法搜索效率高、鲁棒性好，但存在易于陷入局部最优解、收敛速度慢等问题。基于混合的路径规划算法搜索效率高，但存在时间复杂度高、计算量大等问题。
4. 存在问题及后续展望
随着路径规划算法的深入研究与改进，与GIS技术结合的路径规划算法更加智能化、自主化，但同时也存在一些问题，由于不同行业和领域中的应用需求不同，所存在的问题也不同，因此，需要对不同的问题进行分析改进。
1) 算法局限性问题。经典单一算法无法处理一切路径规划，在简单环境中操作简易、使用方便、效率高，但复杂环境该会表现出自身局限性；对于混合算法虽然可以处理大部分路径规划问题，但是开发新的混合算法复杂程度高且不一定有效。针对算法局限性方面，应在传统算法上引入突变思想，提高算法局限性，增强算法适应性。
2) 环境建模问题。建立更加符合真实情况的环境模型与算法相融合是一个跨学科。现有的环境模型多是将目标作为一个质点在任务空间中模拟，这种环境模型过于理想化，便于求解，忽视了现实情况的复杂性，从而导致真实情况下的路径规划效果差。针对环境建模问题，应提高建模环境的复杂性，增加约束条件，同时考虑目标自身的特点。
3) 实时动态监测问题。现有的路径优化算法多是在障碍物及目的地已知不变的情况下，但实际情况存在许多不确定性，使得目标在面对突发情况时的路径规划无法应对。针对实时动态监测方面，应结合启发式算法提高环境的动态性，增强算法的动态规划能力。
5. 结语
结合GIS技术的路径规划算法发展至今已经日趋成熟，本文主要阐述了基于几何模型、基于启发式和基于混合的路径规划算法，从算法的时间复杂度、多目标寻优及搜索效率等角度分析了基于GIS技术的路径规划算法，并从算法的局限性、环境建模、动态监测等方面进行分析展望。当前，静态路径规划算法已相对成熟，但实时动态路径规划算法仍存在着很多问题，因此，接下来的研究方向应着重考虑多学科交叉融合形成更加高效的路径规划算法。
NOTES
*通讯作者。