主权项 |
一种基于路链的导航路径规划方法,包括:1)从道路网中获取节点‑弧段信息,并利用节点—弧段信息提取路链信息;2)利用路链信息和导航系统的输入起点和终点位置,双向搜索从起点到终点的可行路径:2a)确定起点、终点所在的路链,用所有起点、终点所在路链分别组成起点路链集合S<sub>0</sub>和终点路链集合E<sub>0</sub>;2b)判断起点路链集合S<sub>0</sub>与终点路链集合E<sub>0</sub>是否存在公共路链,如果存在公共路链,则搜索从起点到终点的可行路径结束,执行步骤3),如果不存在公共路链,则执行步骤2c);2c)初始化路链集合等级n=1;2d)获得第n级起点路链集合S<sub>n</sub>,即查询路链集合S<sub>(n‑1)</sub>中的每一条路链的邻接路链,如果邻接路链已经被设置了父路链,则该邻接路链不存放在第n级起点路链集合S<sub>n</sub>中,如果邻接路链没有被设置父路链,则将当前查询的路链设置为其邻接路链的父路链,新设置了父路链的邻接路链存放在第n级起点路链集合S<sub>n</sub>中;2e)判断第n级起点路链集合S<sub>n</sub>与第n‑1级终点路链集合E<sub>(n‑1)</sub>是否存在公共路链,如果存在公共路链,则搜索从起点到终点的可行路径结束,执行步骤3);如果不存在公共路链,执行步骤2f);2f)获得第n级终点路链集合E<sub>n</sub>,即查询终点路链集合E<sub>(n‑1)</sub>中的每一条路链的邻接路链,如果邻接路链已经被设置了父路链,则该邻接路链不存放在第n级终点路链集合E<sub>n</sub>中,如果邻接路链没有被设置父路链,则将当前查询的路链设置为其邻接路链的父路链,新设置了父路链的邻接路链存放在第n级终点路链集合E<sub>n</sub>中;2g)判断第n级起点路链集合S<sub>n</sub>与第n级终点路链集合E<sub>n</sub>是否存在公共路链,如果存在公共路链,则搜索从起点到终点的可行路径结束,执行步骤3);如果不存在公共路链,n=n+1,返回步骤2d);3)获取最优路径:3a)利用标记的父路链,从公共路链开始分别逆序从每一级起点路链集合和终点路链集合提取路链,获得起点路链串集合和终点路链串集合,以公共路链为中间路链连接起点路链串集合与终点路链串集合,得到可行路径;3b)计算每一条可行路径的权重,取权重最小的路径为最优路径。 |