郑贵省,王　元，王　鹏，李月明，车亚辉

(1.军事交通学院 基础部，天津300161； 2.军事交通学院 研究生管理大队，天津300161)



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

郑贵省1,王元2，王鹏2，李月明2，车亚辉2

(1.军事交通学院 基础部，天津300161； 2.军事交通学院 研究生管理大队，天津300161)

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

有效路径；K次短路径算法；GIS

路网中有效路径的计算方法是交通规划中交通流分配的关键技术。现有的有效路径计算方法很多，主要有启发式的定向搜索算法[1]、分层定向搜索算法[2]、基于层次空间推理的搜索算法[3]，以及文献[4-5]提出的K次短路径算法、遍历算法等。虽然相关理论研究很多，但对算法效率和实现方面的研究较少。

地理信息系统(geographic information system，GIS)集数据管理、可视化和空间分析于一体，在诸多领域(尤其是交通领域)得到了广泛应用。路网具有很强的地理分布特性，基于GIS技术的优势，实现大规模实际路网中有效路径的快速搜索，是有效路径理论得以实际应用的必然趋势。现有GIS平台中的空间网络分析功能不断强化，已经可以实现实际路网中的最近设施点分析、服务区分析、选址等问题，如何结合其强大的空间分析功能和数据处理能力来实现其有效路径的搜索功能，将是需要研究的问题。……