一种面向动态城市交通路网的快速路径规划方法

摘要

本发明公开了一种面向动态城市交通路网的快速路径规划方法，首先基于第一种动态规划模型构建RSA算法，基于第二种动态规划模型构建FSA算法；然后根据路网拓扑信息和起终点矩阵构造二分图，其中左、右点集合分别用X和Y表示；使用匈牙利算法计算二分图的最大匹配；在二分图的最大匹配中找到能覆盖二分图所有边的最少的点；最后对X集合中被染色的节点使用FSA算法求解，对Y集合中未被染色的节点使用RSA算法求解。相比于RSA算法或FSA算法的单独使用，本发明能综合RSA算法和FSA算法的优势，并克服RSA算法和FSA算法的不足，通过自适应起终点矩阵选择最佳计算策略从而大幅提高计算效率。