CN102506886B - 导航设备中实现路径规划的方法 - Google Patents

Abstract

导航设备中实现路径规划的方法，涉及交通领域中的路径规划，特别是路径规划的算法。该方法依赖于导航设备中的处理器实现，在与处理器配套的内存中存储有路径规划图以及图中各路口的交通规则，其特征在于：当确定起点和终点后，路径规划包含以下步骤：根据迪杰斯特拉路径规划原理、路径规划图以及图中各路口的交通规则，规划从起点到终点的路径，再规划从终点到起点的路径，然后选取上述两个步骤中成功的作为规划结果。采用此方法，可降低导航数据生产的技术度，提高导航性能。

Description

导航设备中实现路径规划的方法

技术领域

本发明涉及交通领域中的路径规划，特别是路径规划的算法。

背景技术

迪杰斯特拉算法（Dijkstra）是由荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。如果图中的顶点表示城市，而边上的权重表示城市间的距离，该算法可以用来找到两个城市之间的最短路径。

该算法的输入包含了一个有权重的有向图 G，我们以V表示G中所有顶点的集合。图中的边，是两个顶点所形成的有序元素对(Vi, Vj)，表示从顶点Vi到Vj有路径相连。我们以E表示所有边的集合，而边的权重则由权重函数w: E→[0, ∞]定义，权重可以表示距离。因此，w(Vi, Vj)就是从顶点Vi到顶点Vj的距离。图中任两点间路径的距离，就是该路径上所有边的距离总和。已知图中V有顶点V0，迪杰斯特拉算法可以找到V0到所有其他顶点的最短路径。

在计算V0到其他顶点的最短路径时，按下述步骤执行：

1. 首先，设置两个顶点集合S和T，S={V0},T={其余顶点}，T中顶点对应的距离值为d(V0,Vi),如果V0与Vi之间有边连接，则d(V0,Vi)=w(V0, Vj)，否则，d(V0,Vi)为∞，

2. 从T中选取顶点W，条件是W与V0的距离值最小，将W从集合T中移入集合S，

3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值。

重复上述步骤2、3，直到S中包含所有顶点，即S=T为止。

该算法因其算法的效率而在导航软件中被大量采用。

导航软件中用于路径规划的地图来自于现实中的道路交通网络，因此该图为典型的有向图，而且根据该图使用迪杰斯特拉算法做路径规划的过程中，还必须考虑到图中各个顶点（实际中为路口）上包含的交通规则。公知的导航软件路径规划，一般采用从路径规划的起点向终点进行发散的规划原则。同时为了缩短路径规划的时间，提高路径规划的效率，往往采用从起点发散到终点即告结束的原则，而事实上，这样的规划原则往往是以牺牲路径规划的合理性来缩短路径规划的时间提高路径规划的效率。

由于道路网络为有向图，同时在道路网络上的路口常常存在交通规则，考虑到迪杰斯特拉路径规划算法的特性：已确定最短路径的顶点不能被再次翻开，这样常常会导致从起点到终点的路径规划失败，其原因是：如果两个位置点都连通到一个公共点，则从公共点过来的路径规划过程中，该两点之间的道路不会被算法找到。如图1中，位置点B和C通过S4和S5连通到公共点D，则从D向B、C方向的路径规划过程中，B和C之间的道路S3不会被找到。

如图1所示，Start为起点，End为终点，交通规则规定：从道路S4经B点不能到达道路S2，我们根据迪杰斯特拉路径规划原理，从Start点出发，当G点、D点被依次翻开时， Start、G和D点为有最短路径的顶点的集合，

S={Start，G，D},

而End、A、B、C为尚未确定最短路径的顶点集合，

T={End、A、B、C}。

根据D点的拓扑关系，从D点再次向外发散可以翻开C点和B点，当C点和B点被翻开时，

S={Start，G，D，C，B}，

T={End、A}。

假设C点到Start点的距离小于B点到Start点的距离,因此应该先发散C点，但我们发现和C点相连的B点和D点均为有最短路径的顶点，从C点发散，已无顶点能再次被翻开，经由C点地路径规划到C点结束；排除C点后，我们会发现另一个有最短路径的顶点为B，根据B点的拓扑关系，从B点再次向外发散可以翻开的点只有A点，但分析B点地交通规划，从S4经B点不能到达S2，那么可以确定自S4到达B点地路径不能翻开A点，而B点也不存在其它可以翻开的点，因此可以确定，经由S4到达B点地路径规划在B点结束，自此，根据迪杰斯特拉路径规划原理结合实际的交通规则进行的路径规划全部结束，但从Start点发散到的节点只有B、C、G、D点，而A点和End点均未被发散到，也就是说从Start点到End点不存在最短路径。而实际上我们观察图形会发现：从Start点到End点的路径时存在的，既：

如何解决上述问题，是导航软件路径规划算法中普遍存在的技术难题。

发明内容

为解决上述问题，本发明提出以下技术方案：导航设备中实现路径规划的方法，依赖于导航设备中的处理器实现，与处理器配套的存储介质中存储有地图以及图中各路口的交通规则，当确定起点和终点后，路径规划包含以下步骤：

A、设置存储区域SA，按照迪杰斯特拉原理，根据地图及交通规则计算从起点到终点的路径，并将结果转存到SA中，

B、设置存储区域SB，按照迪杰斯特拉原理，根据地图及交通规则，以设定的终点作为开始，设定的起点作为结束，计算路径，并将结果转存到SB中，

C、比较SA和SB中的结果，如果都有从起点到终点的路径，取其中距离短的路径作为本次路径规划的结果；如果只有一个从起点到终点的路径，将成功者作为本次路径规划的结果；当都没有从起点到终点的路径时，路径规划失败。

更具体地，在步骤B中，采用从起点到终点方向的交通规则。

使用本方法，从正、反两个方向进行路径规划，可以克服算法中“已确定最短路径的顶点不能被再次翻开”的缺陷，原理是如果某条道路从正向找不到的话，从反向可以找到，这样就能够避免因导航数据中存在类似图1所引起的路径规划的失败问题，提高了导航软件的导航性能和用户体验，同时降低了导航数据生产的技术度。

附图说明

图1为一个路径规划图。

其中：Start为起点，End为终点，A、B、C、D、G为中间点，S1为End点与A点间的道路，S2为A点与B点间的道路，S3为B点与C点间的道路，S4为B点与D点间的道路，S5为C点与D点间的道路，S6为D点与G点间的道路，S7为G点与Start点间的道路。

具体实施方式

导航设备中实现路径规划的方法，依赖于导航设备中的处理器实现，与处理器配套的存储介质中存储有地图以及图中各路口的交通规则，当确定起点和终点后，路径规划包含以下步骤：

A、设置存储区域SA，按照迪杰斯特拉原理，根据地图及交通规则计算从起点到终点的路径，并将结果转存到SA中，

B、设置存储区域SB，按照迪杰斯特拉原理，根据地图及交通规则，以设定的终点作为开始，设定的起点作为结束，计算路径，并将结果转存到SB中，

C、比较SA和SB中的结果，如果都有从起点到终点的路径，取其中距离短的路径作为本次路径规划的结果；如果只有一个从起点到终点的路径，将成功者作为本次路径规划的结果；当都没有从起点到终点的路径时，路径规划失败。

在步骤B中，采用从起点到终点方向的交通规则。

下面结合附图对本发明进行详细说明。

例1：参看图1，本例中没有特别的交通规则。

首先执行步骤A：根据迪杰斯特拉路径规划原理、路径规划图以及图中各路口的交通规则，规划从起点到终点的路径，过程如下：

结论：使用正向路径规划，得到Start到End的路径规划结果为：

总距离为：S7+S6+S4+S2+S1

将上述结果转存到存储区SA中。

然后执行步骤B1-B3：根据迪杰斯特拉路径规划原理、路径规划图以及图中各路口的交通规则，规划从终点到起点的路径，过程如下：

结论：使用反向路径规划，得到S到E的路径规划结果为：

   

总距离为：S7+S6+S4+S2+S1

将上述结果转存到存储区SB中。

在步骤C中，SA和SB中，起点到终点的路径规划一致，采用任何一个结果都可作为规划路线。

例2：参看图1，本例中在B点有交通规则：从S4经B点不能到达S2。

首先执行步骤A：根据迪杰斯特拉路径规划原理、路径规划图以及图中各路口的交通规则，规划从起点到终点的路径，过程如下：

结论：没有从S到达E的路径。

将上述结果转存到存储区SA中。

然后执行步骤B：根据迪杰斯特拉路径规划原理、路径规划图以及图中各路口的交通规则，规划从终点到起点的路径，过程如下：

结论：使用反向路径规划，得到Start到End的路径规划结果为：

   

总距离为：S7+S6+S5+S3+S2+S1

将上述结果转存到存储区SB中。

在步骤C中，采用SB中从起点到终点的路径作为规划路线。

在本例中，如图1所示：在反向路径规划中，End为已知点，根据End点地道路拓扑关系，End点可以翻开A点，再根据A点地道路拓扑关系，A点可以翻开B点，再根据B点地道路拓扑关系，B点可以翻开C点、D点，但因B点存在不能经S4到S2的道路通行规则，所以B点只能翻开C点，C点可以翻开D点，D点可以翻开G点，G点可以翻开Start点，当Start点被翻开时，路径规划结束。

Claims (1)

1.导航设备中实现路径规划的方法，依赖于导航设备中的处理器实现，与处理器配套的存储介质中存储有地图以及图中各路口的交通规则，其特征在于：当确定起点和终点后，路径规划包含以下步骤：

A、设置存储区域SA，按照迪杰斯特拉原理，根据地图及交通规则计算从起点到终点的路径，并将结果转存到SA中，

B、设置存储区域SB，按照迪杰斯特拉原理，根据地图及起点到终点方向的交通规则，以设定的终点作为开始，设定的起点作为结束，计算路径，并将结果转存到SB中，

C、比较SA和SB中的结果，如果都有从起点到终点的路径，取其中距离短的路径作为本次路径规划的结果；如果只有一个从起点到终点的路径，将成功者作为本次路径规划的结果；当都没有从起点到终点的路径时，路径规划失败。