路径规划的方法及系统

摘要

本发明提供一种用于城市道路交通网络中路径规划的方法，该方法首先基于给定的路网密度将由起点和终点确定的待搜索的区域划分为多个子区域；接着将多个子区域映射成一维的离散点，并基于所述离散点形成Voronoi图；然后，基于Voronoi图确定各子区域间的邻接关系并判断邻接的子区域之间的连通性；以及基于所选出的互相邻接且连通的子区域的集合构建新的道路网络，并在所构建的新的道路网络中搜索起点与终点之间的最优路径。该方法不仅降低了路网拓扑结构的构建时间，而且缩小路径的搜索范围和搜索时间，提高了搜索效率。

主权项

一种路径规划的方法，所述方法包括：步骤1，根据起点和终点确定待搜索的区域；步骤2，基于给定的路网密度将该区域划分为多个子区域，其中每个子区域的路网密度不大于该给定的路网密度；步骤3，经划分后得到的多个子区域映射成一维的离散点，并基于所述离散点形成Voronoi图；步骤4，基于Voronoi图确定各子区域间的邻接关系并判断邻接的子区域之间的连通性；步骤5，从所述多个子区域中选出互相邻接且连通的子区域；步骤6，所选出的子区域的集合构建新的道路网络，并在所构建的新的道路网络中搜索起点与终点之间的最优路径。