一种基于GPS轨迹的路线规划方法

姜波

摘要：本发明提供了一种利用路线轨迹点信息来进行路线规划的方法，包括：获取包括一系列轨迹点的坐标的路线轨迹点信息；在电子地图上按照该一系列轨迹点的坐标形成与该一系列轨迹点对应的正向链路或反向链路；在以当前位置为中心的预定范围内，找到正向链路或反向链路与电子地图中路网的交叉点，作为正向链路或反向链路的备选切入点，其中备选切入点的数日大于预定值；获得从当前位置到每一个备选切入点的路线，计算所述路线的权值，并将权值最小的路线所对应的备选切入点作为最佳切入点，并将权值最小的路线作为最佳切入路线，将最佳切入路线与从最佳切入点到正向链路或所述反向链路的终点的正向链路或反向链路连接，形成正向或反向规划路线。

关键词：汽车导航；GPS轨迹；路线规划；路线切入

技术领域

本文涉及导航技术领域，更为具体地，涉及一种利用轨迹点进行导航路线规划的方法。

背景技术

随着公共交通设施的不断发展，驾驶者越来越需要导航设备来进行路线导航。通常情况下，导航设备都能够记录当前位置的GPS信息，其中包括当前位置的经纬度信息。例如，每隔一段时间或者距离，提取GPS信息当中的当前位置的经纬度信息并记录下来，这种记录点通常称为轨迹点。一系列轨迹点的经纬度信息称为路线轨迹。用户可以利用导航设备把轨迹保存在轨迹文件中，用户还可以记录旅途感受等文字信息或在旅途中拍摄的照片、视频、音频等信息，然后通过工具，把这些信息（统称为POI信息）附加到轨迹点上，形成包含轨迹信息、多媒体信息的旅途轨迹记录。

在电子地图数据中，存储着包含道路数据在内的丰富的地图信息。Link 是能够和实际的道路相对应的、电子地图当中的道路数据的基本构成元素。Link中包括了道路编号、名称、宽度、方向、交通规则等道路信息。

把旅途轨迹记录和电子地图同时显示，可以直观地看出旅途上都经过了哪些地方。

用户可以从网络上下载这种旅途轨迹记录，从而可以根据所下载的旅途轨迹记录当中的轨迹点信息，从自己的当前位置开始，“重新走过”一段路途，游览前人推荐的地点，曾经住宿的宾馆，曾经吃过的饭店等，由此实现省心、省力又能得到比较好的服务和享受的目的。

目前，多数导航设备能够显示旅途轨迹记录，用户在驾车的时候可以一边看旅途轨迹记录，一边对照自己的位置，判断自己走到哪里。

图1示出了在电子地图上显示的旅途轨迹记录的一个示例。

比上述方法更进一步地，在现有的导航设备中，通常采用以下两种方式来利用旅途轨迹记录。

第一种方式是用户进行手动操作，将旅途上的一些重要地点设定为一系列目的地，然后利用导航装置规划出一条经过这些目的地的经路，如图2所示。然而，通常情况下，利用导航装置规划出来的经路与所下载的旅途轨迹记录的轨迹所示的经路并不相同，从而导致用户不能充分地利用所下载的旅途轨迹记录中所记录的信息。

第二种方式是通过导航装置自动寻找轨迹上距离当前位置最近的点作为切入点，提示用户切入点的位置，让用户决定利用旅途轨迹记录当中轨迹的哪一段（是“切入点到旅途轨迹起点”，还是“切入点到旅途轨迹终点”) ，如图3所示。

在确定出利用哪一段后，在导航装置上显示这段旅途轨迹记录上的轨迹和信息，但是不能进行路线规划，或者如第一种方式类似，将该段旅途轨迹记录上的所有POI作为有序目的地，利用导航装置进行路线规划。在这种情况下，同样存在利用导航装置规划出来的经路与所下载的旅途轨迹记录的轨迹所示的经路并不相同，从而导致用户不能充分地利用所下载的旅途轨迹记录中所记录的信息的问题。此外，用户当前位置和切入点之间简单连线可能不和实际道路对应。

解决方案

鉴于上述问题，本文提供了一种新的用于路线规划的方法及装置，其利用路线轨迹点信息和导航装置中存储的电子地图，形成正向链路或反向链路，根据用户的当前位置以及所述正向链路或反向链路，确定从当前位置切入所述正向链路或反向链路的最佳切入点以及所述正向链路或反向链路的最佳切入路线，将所述正向链路或反向链路的最佳切入路线与所述正向链路或反向链路的最佳切入点到所述正向链路或反向链路的终点的正向链路或反向链路连接，形成利用路线轨迹点信息的正向规划路线或反向规划路线。流程如图4所示。

按照这种方式，可以使得用户能够以合适地方式，最大限度地利用旅途轨迹记录当中的路线轨迹点信息，从用户的当前位置开始，重新走过一段路程，从而最真实地再现旅途轨迹记录所描述的路线。

这里要说明的是，旅途轨迹记录当中的路线轨迹是有方向的，正向轨迹路线（也称为正向链路）指的是与所述的旅途轨迹记录当中的路线轨迹匹配并且方向一致的轨迹路线，而反向轨迹路线（也称为反向链路）指的是与所述的旅途轨迹记录当中的路线轨迹匹配并且方向相反的轨迹路线。

本方案提供了一种利用路线轨迹点信息来进行路线规划的方法，包括：

1. 获取路线轨迹点信息，所述路线轨迹点信息包括一系列轨迹点的坐标；

2. 在电子地图上按照所述一系列轨迹点的坐标形成与该一系列轨迹点对应的正向链路或反向链路；

3. 根据当前位置和所述正向链路或所述反向链路确定从所述当前位置切入所述正向链路或所述反向链路的最佳切入点；

4. 将所述正向链路或所述反向链路的最佳切入路线与所述正向链路或所述反向链路的最佳切入点到所述正向链路或所述反响链路的终点的正向链路或反响链路连接，形成利用路线轨迹点信息的正向规划路线或反向规划路线；

5. 其中所述确定最佳切入点以及最佳切入路线的步骤还包括：在以当前位置为中心的预定范围内，找到所述正向链路或所述反向链路与电子地图中路网的交叉点，作为所述正向链路或所述反向链路的备选切入点，其中所述备选切入点的数目大于预定值；

6. 获得从所述当前位置到每一个所述备选切入点之间的路线，计算所述路线的权值，并将所述权值最小的路线所对应的备选切入点作为所述正向链路或所述反向链路的最佳切入点，以及将所述权值最小的路线作为所述正向链路或所述反向链路的最佳切入路线。

具体实施方法

图4示出了利用路线轨迹点信息进行路线规划的方法的流程图。

如图4所示，在步骤S410中，通过导航装置获取路线轨迹点信息，所述路线轨迹点信息包括一系列轨迹点的坐标。所述路线轨迹点信息可以预先存储在导航装置中，也可以从网络下载。

然后，在步骤S420中，在电子地图上，按照所述一系列轨迹点的坐标，形成与该一系列轨迹点对应的正向链路或反向链路。关于正向链路的形成过程，参照图5。

反向链路的形成过程，参照图6。

在形成反向链路的过程中，如果轨迹匹配的路线是单行线，需要寻找“替代路线”，在近距离下有多段单行线的时候，合并处理：

如图7所示①、②之间是单行线，③、④之间也是单行线，因为②、③之间的距离很短（例如<3km）,所以把两部分合并处理，计算一条回避④到①之间的道路的路线，用这条路线替代原来的路线。

在形成正向链路或反向链路后，根据用户的当前位置和所述正向链路或反向链路，确定从当前位置切入所述正向链路或所述反向链路的最佳切入点以及所述正向链路或所述反向链路的最佳切入路线。

换言之，如图4所示，在形成正向链路或反向链路后，流程进行到步骤S430。在步骤S430，在以用户的当前位置为中心的预定范围内，找到所述正向链路或反向链路与电子地图中路网的交叉点，作为所述正向链路或反向链路的备选切入点，其中所述备选切入点的数目要大于预定值。例如，在以当前位置为中心的预定范围L（例如，以当前位置为中心的3km）内，找出所选择出的轨迹路线与实际路网之间的交叉点，作为备选切入点，如图8所示。

其中L是可变的距离参数。所述预定范围L可以是以当前位置为中心的同心圆或同心矩形。通常，要求备选切入点的数目人于或等于N,其中N可以是任何整数值，例如5。当备选切入点的数目小于N时，可以扩大预定查找范围L来重新进行查找，直到所找出的备选切入点的数目大于或等于N为止。

例如，图9所示，如果在预定范围L0内没有找到N个以上的备选切入点，则需要将预定范围扩大到L0 + L 、L0 + 2L 等。然后，在扩大后的查找范围内，查找备选切入点，直到找到N个以上的备选切入点为止。

这里要说明的是，如果整条轨迹路线都在查找范围内，所找到的备选切入点的数日仍然小于N，则停止查找，并将所找到的交叉点作为备选切入点。然后，流程进行到步骤S440。

在找出备选切入点后，在步骤S440，利用导航装置获得从所述当前位置到每一个所述备选切入点之间的引导路线，计算所述路线的权值，并将权值最小的路线所对应的备选切入点作为所述正向链路或反向链路的最佳切入点，以及将该权值最小的路线作为所述正向链路或反向链路的最佳切入路线。

在确定出最佳切入点以及最佳切入路线后，流程进行到步骤S450。在步骤S450中，将所述正向链路或反向链路的最佳切入路线与所述正向链路或反向链路的最佳切入点到所述正向链路或反向链路的终点的正向链路或反向链路连接，形成利用路线轨迹点信息的正向规划路线或反向规划路线。

实施效果

通过以上结合附图对实施方法的详细描述，不难看出：利用路线轨迹点信息和导航装置中存储的电子地图，形成正向链路或反向链路，根据用户的当前位置以及所述正向链路或反向链路，确定从当前位置切入所述正向链路或反向链路的最佳切入点以及所述正向链路或反向链路的最佳切入路线，将所述正向链路或反向链路的最佳切入路线与所述正向链路或反向链路的最佳切入点到所述正向链路或反向链路的终点的正向链路或反向链路连接，形成利用路线轨迹点信息的正向规划路线或反向规划路线。按照这种方式，可以使得用户能够以合适地方式，最大限度地利用旅途轨迹记录当中的路线轨迹点信息，从用户的当前位置开始，重新走过一段路程，从而最真实地再现旅途轨迹记录所描述的路线。

参考文献

[1] 专利名称：一种导航轨迹的记录方法、装置、设备以及导航方法；专利权人：凯立德欣技术(深圳)有限公司，专利申请号：CN200610157916.3

[2] 专利名称：路书制作方法和装置、路书制作与共享系统；专利权人：北京灵图软件技术有限公司；专利申请号CN200910236038.8

[3] 孙棣华 张星霞 张志良，地图匹配技术及其在智能交通系统中的应用[J].计算机工程与应用 2005.20