路径搜索方法和系统

摘要

本发明提供了一种路径搜索方法和系统，其中，方法包括以下步骤：将道路映射成交通网络拓扑图中的结点，将道路的端点映射成交通网络拓扑图中的弧段；从原结点和目标结点双向搜索得到多个当前结点；依次计算多个当前结点到原结点和目标结点的代价，得到从原结点到目标结点的代价最小的当前结点；根据代价最小的当前结点和原结点以及目标结点，得到从原结点到目标结点的路线方案。本发明克服了现有技术中采用邻接矩阵的Dijkstra方法来存储交通网络拓扑数据，虽然可以在O(1)时间内完成(i；j)是否是一条网络边的查询，但对最短路径搜索最关键的关联结点的查询，其复杂度均为O(n)，导致查询的复杂度较高的问题。

主权项

一种路径搜索方法，其特征在于，包括以下步骤：A)将道路映射成交通网络拓扑图中的结点，将所述道路的端点映射成所述交通网络拓扑图中的弧段；B)从原结点和目标结点双向搜索得到多个当前结点；C)依次计算多个所述当前结点到所述原结点和所述目标结点的代价，得到从所述原结点到所述目标结点的代价最小的当前结点；所述代价为费用代价或距离代价或时间代价；D)根据所述代价最小的当前结点和所述原结点以及所述目标结点，得到从所述原结点到所述目标结点的路线方案；其中所述步骤C)具体包括：计算从所述原结点到多个所述当前结点的费用g(n)，g(n)＝g(n‑1)+D(n)×R(n)+T(n)，其中，g(n‑1)为到达结点n‑1所经过的弧段的实际费用值，D(n)为从结点n‑1到达结点n的路径的长度，R(n)为从结点n‑1到达结点n的路径的属性取值因子，R(n)＝360/m_rtCost[layerType][distType][methodType][roadClass]其中，360为经验值，layerType、distType、methodType和roadClass分别是所述结点n的道路层类型、道路长度类型、驾乘选项和道路功能等级属性，T(n)为从结点n‑1进入所述结点n时经过的导航路径的转向耗费，m_rtCost为导航费用参数；T(n)＝m_turnCost[methodType][turnDirection]，其中methodType和turnDirection分别是所述结点n的驾乘选项和道路转向属性，m_turnCost为转向费用参数；计算从所述结点n到所述目标结点的费用h′(n)：h′(n)＝μ×O(n)×R′(n)，其中，μ为耗费系数，其取值与所述原结点到所述目标结点的欧氏距离的平方相关；O(n)为所述结点n到所述目标结点的欧氏距离；R′(n)为所述结点n的后续费用估算的比例因子：R′(n)＝360/m_toCost[layerType][distType][methodType]，其中360是经验值，layerType、distType、methodType分别是从结点n‑1到达所述结点n的导航路线的道路层类型、道路长度类型和驾乘选项属性，m_toCost为到达费用参数；计算所述原结点到所述目标结点的总费用：f′(n)＝g(n)+h′(n)；将根据多个所述当前结点计算得到的多个所述总费用进行比较，得到所述总费用最小的当前结点。