基于改进K次短路径算法的有效路径搜索算法及实现

为提高有效路径搜索效率,结合ArcGIS具有的路径分析功能,以K次短路径算法为基础,依据重叠惩罚算法的原理,提出基于改进K次短路径算法的有效路径搜索算法。以ArcGIS为平台,给出了算法的实现方法。经过对实际路网的可视化测试,验证了改进算法具有较高的运行效率,为有效路径相关理论在ArcGIS平台的应用提供了一种技术手段和方法。

关于k次短路径问题的分析与求解

分析了前k条最短路径的图论理论基础,在计算出最短路径的基础上,提出了一种基于前k-1条最短路径的k次短路径的求解方法,该方法能方便高效地找出次短路、再次短路,一直到k次短路。该算法的时间复杂度为O(n2),可以很好地满足实际应用需要。

基于改进A*算法的AGV路径规划

自动引导小车(Automatic Guided Vehicles,AGV)广泛应用于物流自动化系统,针对AGV的路径规划问题,提出了一种改进的A*算法,该算法引入转弯因素,使规划的AGV路径更加平滑;并充分利用求解的最短路径信息,采用一种删除边的算法来求解k次短路径问题;实例仿真证明了改进的A*算法的可行性,通过与其他求解k次短路径问题的算法进行对比,证明删除边的算法简单、可行。