CN101532842A - 确定从起点到终点的目标路线的路径规划方法及其装置 - Google Patents

Abstract

本发明提供一种确定从起点到终点的目标路线的路径规划方法及其装置，该方法包含有：从数据库中获取起点到终点的多条候选路段；依据对应的兴趣点分布状况，对于每一条候选路段获得探测结果；以及依据多个探测结果确定目标路线，目标路线包含有从多条候选路段中选取的多条路段。该装置包含有，第一存储装置，用于存储数据库；第二存储装置，用于存储包含第一程序码、第二程序码与第三程序码的路径规划程序；路径规划单元。本发明的路径规划方法可依据路段邻近或路段上的兴趣点的分布状况来选择目标路线，从而克服了现有技术中路径规划方法的不足，更好地满足了使用者的需求。

Description

确定从起点到终点的目标路线的路径规划方法及其装置

技术领域

本发明是有关于一种路径规划方法及其装置，尤其是有关于一种依据兴趣点(Point of Interest，POI)分布状况来确定目标路线(target route)的方法及其装置。

背景技术

常规的车辆导航系统或手持设备(如手机、个人数字助理等)中的导航系统通常包含全球导航卫星系统(Global Navigation Satellite System，GNSS)与地理信息系统(Geographic Information System，GIS)，以为使用者提供精确的定位及道路探寻功能。也就是说，导航系统可提供路径规划功能来帮助使用者到达目的地。举例来说，使用者可依据导航系统的路径规划功能选择从起点到终点的最短路线或最短时间。此外，GIS包含目标区域中的许多重要兴趣点(Point of Interest，POI)，如商店、加油站、医院、路标、博物馆等等。使用者可搜寻POI的特性，如名称、地址以及电话号码。导航系统可设定一条由GNSS所确定的当前位置到使用者选定的一个POI的目标路线(target route)，并在前行过程中显示详细地图，当使用者偏离常规路线时重新生成新的目标路线，并依据当前驾驶速度预计到达所选POI所需的时间。

现有技术中导航系统的路径规划功能虽然看似功能多样，却仍然难以满足所有使用者的需求，如依据POI分布状况的路径规划。有些情况下，如在午餐时间，使用者可能希望选择一条餐馆分布密集的目标路线，或者一条购物商店密集的目标路线。然而，现有技术的导航系统仅能被动地提供一个POI的相关信息，而无法依据POI的分布情况为使用者提供路径规划程序。

发明内容

为了解决上述无法依据兴趣点(Point of Interest，POI)的分布情况为使用者提供路径规划功能的技术问题，本发明技术方案的一实施例提供一种确定从起点到终点的目标路线(target route)的路径规划方法。此路径规划方法包含有：从数据库中获取起点到终点的多条候选路段(path)；依据对应的POI分布状况，对于每一条候选路段获得探测结果；以及依据多个探测结果确定目标路线，目标路线包含有从多条候选路段中选取的多条路段。

依据本发明的另一实施例，还提供一种确定从起点到终点的目标路线的路径规划装置。此路径规划装置包含第一存储装置、第二存储装置以及路径规划单元。第一存储装置用于存储数据库。第二存储装置用于存储包含第一程序码、第二程序码与第三程序码的路径规划程序。路径规划单元耦合于第一存储装置与第二存储装置，用于执行第一程序码，从存储在第一存储装置的数据库中获得起点到终点的多条候选路段；执行第二程序码，依据对应的POI分布状况，对于每一条候选路段获得探测结果；以及执行第三程序码，以依据多个探测结果确定目标路线，目标路线包含从多条候选路段中选取的多条路段。

本发明的方法及装置与现有技术相比，其有益效果至少包括：使用者可依据路段邻近或路段上的POI的分布状况来选择目标路线，从而克服了现有技术中路径规划方法的不足，更好地满足了使用者的需求。

附图说明

图1是依据本发明的一实施例，在地理信息系统数据库与兴趣点数据库相连接时计算路段一定范围内兴趣点密度的方法的流程图；

图2是依据本发明的一实施例，在地理信息系统数据库与兴趣点数据库无连接时计算路段一定范围内兴趣点密度的方法的流程图；

图3是依据本发明的一实施例显示图2中步骤206的详细操作的流程图；

图4是依据本发明的一实施例显示图3中多个矩形与最小边界矩形的关系的示意图；

图5是依据本发明的一实施例通过计算多条候选路段的成本值来确定起点到终点的目标路线的方法的流程图；

图6是显示在图形用户界面上的目标路线的示意图，其中目标路线是通过路径规划方法来获得；

图7是依据本发明的一实施例，为用户提供路径规划策略选项的图形用户界面的示意图；

图8是依据本发明的一实施例，为用户提供兴趣点类型选项的图形用户界面的示意图；

图9是依据本发明的一实施例，为用户提供路段扩展距离临界值选项的图形用户界面的示意图；

图10是依据本发明的一实施例，为用户提供路径规划优先选项的图形用户界面的示意图；

图11是依据本发明的一实施例的具备路径规划功能的电子装置的方框图。

具体实施方式

在本说明书以及权利要求当中使用了某些词汇来指称特定的元件，本领域的技术人员应可理解，硬件制造商可能会用不同的名词来称呼同一个元件，本说明书及权利要求并不以名称的差异来作为区分元件的方式，而是以元件在功能上的差异来作为区分的准则，在通篇说明书及请求项当中所提及的“包含有”是一开放式的用语，故应解释成“包含有但不限定于”，此外，“耦接”一词在此包含任何直接及间接的电气连接手段，因此，若文中描述第一装置耦接于第二装置，则代表第一装置可以直接电气连接于第二装置，或通过其它装置或连接手段间接地电气连接至第二装置。

阅读了下文对附图所示优选实施例的详细描述之后，本发明对所属技术领域的技术人员而言将显而易见。

本发明提供一种参考数据库中获得的兴趣点(Point of Interest，POI)分布状况的路径规划方法。导航系统中包含两种地理信息系统(GeographicInformation System，GIS)数据库，一种是道路信息与存储在POI数据库中的邻近环境信息相连接的，另一种是无连接的。请参考图1，图1是依据本发明的一实施例，在GIS数据库与POI数据库相连接时计算路段(path)一定范围内POI密度的方法的流程图。图1中的步骤不必严格按照所示的顺序执行，也可获得相同的结果。本实施例中，计算路段一定范围内POI密度的方法包含下列步骤：

步骤102：从GIS数据库中选择一条路段。

步骤104：计算从GIS数据库中选择的路段的邻近区域内的POI数量。

步骤106：计算POI数量与所选择的路段长度的比值。

步骤108：获得所选择的路段的POI密度。

上述实施例中，由于GIS数据库已连接于POI数据库，邻近环境的信息可直接从POI数据库中获取。因此，仅需计算POI数量与路段长度的比值即可获得路段的POI密度。

请参照图2，图2是依据本发明的一实施例，在GIS数据库与POI数据库无连接时计算路段一定范围内POI密度的方法的流程图。图2中的步骤不必严格按照所示的顺序执行，也可获得相同的结果。本实施例中，计算路段一定范围内POI密度的方法包含下列步骤：

步骤202：从GIS数据库中选择一条路段。

步骤204：设定一个覆盖依据输入的距离临界值与所选路段的形状扩展得到的多个矩形的搜寻区域。

步骤206：依据空间索引方法找到搜寻区域内的POI。

步骤208：计算搜寻区域内的POI的数量。

步骤210：计算POI数量与所选路段长度的比值。

步骤212：获得所选路段的POI密度。

上述实施例中，由于GIS数据库未连接于POI数据库，必须首先设定依据路段形状从各路段扩展的矩形区域，以确定搜寻区域，从中得到POI数量，然后方可计算得到路段的POI密度。图2中，步骤206所使用的空间索引方法包含图3所示流程图中的步骤：

步骤300：设定最小边界矩形区域，包括由所选路段扩展的多个矩形组成的多边形区域。

步骤302：依据更新后的搜寻范围，即最小边界矩形区域的空间索引获得系列POI数据包。

步骤304：从POI数据包顺序读取各POI。

步骤306：确定POI是否落在多边形区域内部，并放弃多边形区域以外的POI。

步骤308：计算多边形区域内的POI的数量。

图3中，多个矩形包含于最小边界矩形区域，以简化多边形内部的POI数量的计算。图4是依据本发明的一实施例显示图3中多个矩形与最小边界矩形的关系的示意图。本例中，依据距离临界值TH(如50米)从所选路段扩展得到三个矩形R1、R2和R3，因此包含矩形R1、R2、R3的最小边界矩形区域MR也随之确定。但是，由于最小边界矩形可能大于多个矩形形成的多边形区域，也就是说，某些计数的POI可能落在多个矩形区域之外，因此需要依据POI的坐标系进行再核查操作，以去除不需要的POI，如图3中步骤306所示。请注意，图4所示的例子仅用于阐释本发明的目的，并非限定本发明。换句话说，从所选路段扩展的矩形数量可依据设计需要而有所不同。从所选路段扩展的矩形数量越多，得到的搜寻区域中POI的数量精确度越高。

从上文可见，目标路线(target route)中的各路段的POI密度在GIS数据库与POI数据库相连接时，可由步骤102～108获得，而在GIS数据库与POI数据库无连接时，可由步骤202～212获得。得到各路段的POI密度之后，其成本值可通过计算路段长度与各路段的加权因子的乘积得到。基于传统路径规划计算方法，本发明实施例中路段的加权因子是对应路段的POI密度设定的，以指示POI分布状况与路段周围POI的类型。加权因子通过实验及测试获得。举例来说，假设选定一条具有最小成本值的路段作为目标路线，当使用者倾向于一条繁华路线时，系统将据此较小的成本值设定一个附近POI密度较高的路段的加权因子，反之亦然，以满足使用者的探询需求。

最后，目标路线的成本值可通过对目标路线中的所有路段的成本值进行求和得到。图5的流程图是对上述程序的详细描述。图5是依据本发明的一实施例通过计算多条候选路段的成本值来确定起点到终点的目标路线的方法的流程图。图5中的步骤不必严格按照所示的顺序执行，也可获得相同的结果。确定目标路线的方法包含下列步骤：

步骤500：计算与起点相连的所有路段的成本值并将这些路段归入一个排序堆。

步骤502：从排序堆中选取具有最小实际成本值的路段path_i，并同时将其从排序堆中移除。此外，path_i的实际成本值记为“G_i”。

步骤504：判断path_i是否连接至终点。若是，转到步骤520；若否，继续执行步骤506。

步骤506：设定j＝0。

步骤508：找到路段path_ij，其连接至所选路段path_i。

步骤510：计算路段path_ij的POI密度“d_ij”。

步骤512：依据POI密度d_ij选择相应的加权因子w_ij。

步骤514：以G_ij＝G_i+w_ij*L_ij更新path_ij的实际成本值G_ij，其中L_ij是path_ij的路段长度；然后将path_ij归入排序堆。

步骤516：判断是否所有与path_i相连接的路段“path_ij”均已处理。若是，转到步骤502，若否，继续执行步骤518。

步骤518：设定j＝j+1并执行步骤508，继续处理与path_i相连接的下一路段path_ij。

步骤520：路径规划结束。

图5中，流程首先选择与使用者设定的起点相连接的所有路段，并将初始选定的所有路段归入一个存储在内存中的排序堆，然后从排序堆中选择具最小实际成本值的路段。如果所选择的具最小实际成本值的路段是目标路线的最后一段，即其连接至终点，则具最小成本值的目标路线已经成功确定，路径规划程序完成；反之，流程继续计算紧接在当前选定的具最小成本值(如最小累积成本值)的路段之后的后续路段的成本值，此计算操作是通过将各后续路段的长度与对应于POI密度的加权因子相乘而实现，其中POI密度由图1或图2所示步骤获得。图5所示的流程将计算结果与所选路段的实际成本值相加以更新紧随所选路段(即path_i)后的各后续路段(即path_ij)的累积成本值。换句话说，G_ij＝G_i+w_ij*L_ij。请注意，处理过的路段(如path_ij)将归入排序堆，而步骤502中所选定的路段将从排序堆移除。当处理完与初始选定的路段“path_i”相连接的所有路段“path_ij”后，流程会再次比较当前排序堆中所有路段的成本值，并重新选择具最小成本值的路段，也就是说，如果最新添加到排序堆中的路段“path_ij”的成本值与排序堆中的其它路段相比不是最小，步骤502将选定排序堆其它路段中具最小成本值的路段作为新的路段，而不是最新添加到排序堆的路段“path_ij”中具最小成本值的路段。

举例来说，路段L1、L2、L3各具有一个作为起点的端点，将L1、L2、L3均归入排序堆。然后比较L1、L2、L3的成本值C1、C2、C3以找到最小值。如果成本值C1为最小值，则路段L1将被选定并从排序堆移除。假设选定的路段L1之后有四条路段L11、L12、L13、L14。L11、L12、L13、L14的成本值C11、C12、C13、C14会被计算出来并与选定路段L1的成本值C1相加，以获得L11、L12、L13、L14的累积成本值。这样，具有实际成本值C1+C11、C1+C12、C1+C13、C1+C14的路段L11、L12、L13、L14便归入排序堆。需要注意的是，当前排序堆包含有路段L2、L3、L11、L12、L13、L14。然后，比较L2、L3、L11、L12、L13、L14的成本值以找到一条具最小实际成本值的路段。上述流程持续执行，直到选定的具最小实际成本值的路段具有一个作为终点的端点为止。这就意味着目标路线的最后一段具最小成本值的路段已经找到。因此，从上述搜寻过程来看，具最小成本值的目标路线就成功确定了。图6是显示在图形用户界面(Graphical User Interface，GUI)上的目标路线的示意图，其中目标路线是通过路径规划方法来获得。需要注意的是，图5所示流程仅用于阐释本发明，任何参考POI分布状况来寻找目标路线的方法均符合本发明的精神范围。举例来说，本发明的另一实施例中，从目标路线一定预设距离的区域内的数据库获得POI数量，然后据此进行路径规划，此实施例的详细步骤类似于上文所描述的实施例，因此不再赘述。

使用者可通过图形用户界面输入指令来操作路径规划系统。请参照图7至图10。图7中，使用者可基于POI分布状况在三个选项中选择路径规划方法：最短距离、最短时间及POI分布状况。图8中，使用者可根据需要进一步选择菜单中列出的POI类型(一种、几种或所有类型)，菜单包含了所有类型的选项，如旅馆、餐馆、公共服务以及电信与邮局等。此外，使用者可选择POI与路段的最远距离(即上述距离临界值)，举例来说，在路段扩展距离50米、100米、或150米以内，如图9所示。另外，使用者可在图10所示的界面中确认想要选择POI分布稀疏的目标路线还是POI高度集中的目标路线。需要注意的是，图7～图10所示的图形用户界面所显示的选项仅用于阐释本发明，而并非用于限定本发明。

请参照图11，图11是依据本发明的一实施例的具备路径规划功能的电子装置的方框图。电子装置1100包含有：输入/输出界面1102、路径规划单元1104、第一存储装置1106、第二存储装置1108以及定位系统1110，但不限定于此。输入/输出界面1102是使用者界面，用于接收使用者的路径规划程序指令并为使用者显示图形用户界面。第一存储装置1106用于存储数据库如GIS数据库，而第二存储装置1108用于存储程序码来执行上述路径规划功能。路径规划单元1104(如微处理器)用于执行存储在第二存储装置的路径规划程序。举例来说，路径规划程序包含有第一程序码、第二程序码及第三程序码。因此，路径规划单元1104执行第一程序码，从存储在第一存储装置的数据库中搜寻连接起点与终点的多条候选路段；执行第二程序码，以依据对应的POI分布状况，对于每一条候选路段获得探测结果；以及执行第三程序码，以依据探测结果从候选路段中选择目标路线。路径规划方法的具体操作上文已经给出描述，为简洁起见，路径规划程序的执行细节不再赘述。

定位系统1110(如全球导航卫星系统)用于定位电子装置1100的当前位置。举例来说，电子装置1100的当前位置直接作为路径规划程序所要设定的目标路线的起点。然而，上述起点并不仅限于电子装置的当前位置(即使用者的当前位置)。此外，请注意，在导航系统中实现所揭露的路径规划方法仅作为举例，并不是用来限制本发明。也就是说，此路径规划方法可应用于任何需要设定起点至终点的目标路线的情况。再者，使用者的输入/输出界面1102不限于上述的图形用户界面。在另一可选设计中，使用者的输入/输出界面可以通过视频界面、音频界面或两者的结合来实现。需要注意的是，数据库(如GIS数据库)可以是存储在第一存储装置1106的内部数据库或从因特网服务器下载到第一存储装置1106中的数据库。在图11所示的实施例中，第一存储装置1106与第二存储装置1108显示为分离的元件。然而，在另一可选设计中，第一存储装置1106与第二存储装置1108也可以是同一存储装置中的两个模块。

简而言之，本发明可满足使用者依据POI分布状况搜寻目标路线的需要，克服了现有技术中路径规划功能的不足。

所属技术领域的技术人员可轻易完成的均等改变或润饰均属于本发明所主张的范围，本发明的权利范围应以权利要求书所限定的范围为准。

Claims (14)

1.一种确定从起点到终点的目标路线的路径规划方法，该方法包含有：

从数据库中获取该起点到该终点的多条候选路段；

依据对应的兴趣点分布状况，对于每一条候选路段获得探测结果；以及

依据该多个探测结果确定该目标路线，所述的目标路线包含有从所述的多条候选路段中选取的多条路段。

2.如权利要求1所述的确定从起点到终点的目标路线的路径规划方法，其特征在于，其中所述的依据对应的兴趣点分布状况对于每一条候选路段获得探测结果的步骤包含有：

确定位于该候选路段的距离临界值之内的多个兴趣点的数目；以及

依据该兴趣点数目生成该候选路段的该兴趣点分布状况。

3.如权利要求1所述的确定从起点到终点的目标路线的路径规划方法，其特征在于，其中所述的依据对应的兴趣点分布状况对于每一条候选路段获得探测结果的步骤包含有：

确定位于该候选路段的距离临界值之内的多个兴趣点的数目；

依据该兴趣点数目计算该候选路段的兴趣点密度；以及

依据该候选路段的该兴趣点密度生成该兴趣点分布状况。

4.如权利要求3所述的确定从起点到终点的目标路线的路径规划方法，其特征在于，其中所述的计算所述的候选路段的所述的兴趣点密度的步骤包含有：

计算所述的兴趣点数目与所述的候选路段的长度的比值来设定所述的兴趣点密度。

5.如权利要求1所述的确定从起点到终点的目标路线的路径规划方法，其特征在于，其中所述的依据对应的兴趣点分布状况对于每一条候选路段获得探测结果的步骤包含有：

确定位于所述的候选路段的距离临界值之内的多个兴趣点的数目；

依据该兴趣点数目计算所述的候选路段的兴趣点密度；

对应于所述的候选路段的所述的兴趣点密度确定加权因子；

依据该加权因子与所述的候选路段的长度的乘积计算所述的候选路段的成本值；以及

依据所述的候选路段的所述的成本值生成所述的兴趣点分布状况。

6.如权利要求5所述的确定从起点到终点的目标路线的路径规划方法，其特征在于，其中所述的确定所述的兴趣点数目的步骤包含有：

依据所述的候选路段的形状与所述的距离临界值对所述的候选路段进行多个矩形扩展来确定搜寻区域；以及

从所述的数据库中搜寻位于所述的搜寻区域之内的任何兴趣点，以确定所述的兴趣点数目。

7.如权利要求6所述的确定从起点到终点的目标路线的路径规划方法，其特征在于，其中所述的搜寻区域是指最小边界的矩形，包括由所述的多个矩形所形成的多边形区域。

8.一种确定从起点到终点的目标路线的路径规划装置，其特征在于，该装置包含有：

第一存储装置，用于存储数据库；

第二存储装置，用于存储包含第一程序码、第二程序码与第三程序码的路径规划程序；以及

路径规划单元，耦合于该第一存储装置与该第二存储装置，用于执行该第一程序码，从存储在该第一存储装置的该数据库中获得所述的起点到所述的终点的多条候选路段；执行该第二程序码，依据对应的兴趣点分布状况，对于每一条候选路段获得探测结果；以及执行该第三程序码，以依据所述的多个探测结果确定所述的目标路线，所述的目标路线包含从所述的多条候选路段中选取的多条路段。

9.如权利要求8所述的确定从起点到终点的目标路线的路径规划装置，其特征在于，其中所述的路径规划单元执行所述的第二程序码，依据对应的兴趣点分布状况，对于每一条候选路段获得探测结果的功能是通过以下操作实现：

确定位于所述的候选路段的距离临界值之内的多个兴趣点的数目，以及依据所述的兴趣点数目生成所述的候选路段的所述的兴趣点分布状况。

10.如权利要求8所述的确定从起点到终点的目标路线的路径规划装置，其特征在于，其中所述的路径规划单元执行所述的第二程序码，依据对应的兴趣点分布状况，对于每一条候选路段获得探测结果的功能是通过以下操作实现：

确定位于所述的候选路段的距离临界值之内的多个兴趣点的数目；

依据所述的兴趣点数目计算所述的候选路段的兴趣点密度；以及

依据所述的候选路段的所述的兴趣点密度生成所述的兴趣点分布状况。

11.如权利要求10所述的确定从起点到终点的目标路线的路径规划装置，其特征在于，其中所述的路径规划单元通过计算所述的兴趣点数目与所述的候选路段的长度的比值来设定所述的兴趣点密度，从而实现执行所述的第二程序码以计算所述的候选路段的所述的兴趣点密度的功能。

12.如权利要求8所述的确定从起点到终点的目标路线的路径规划装置，其特征在于，其中所述的路径规划单元执行所述的第二程序码，依据对应的兴趣点分布状况，对于每一条候选路段获得探测结果的功能是通过以下操作实现：

确定位于所述的候选路段的距离临界值之内的多个兴趣点的数目；

依据所述的兴趣点数目计算所述的候选路段的兴趣点密度；

对应于所述的候选路段的所述的兴趣点密度确定加权因子；

依据所述的加权因子与所述的候选路段的长度的乘积计算所述的候选路段的成本值；以及

依据所述的候选路段的所述的成本值生成所述的兴趣点分布状况。

13.如权利要求12所述的确定从起点到终点的目标路线的路径规划装置，其特征在于，其中所述的路径规划单元执行所述的第二程序码以确定所述的兴趣点数目的功能通过以下操作实现：

依据所述的候选路段的形状与所述的距离临界值对所述的候选路段进行多个矩形扩展来确定搜寻区域；以及

从所述的数据库中搜寻位于所述的搜寻区域之内的任何兴趣点，以确定所述的兴趣点数目。

14.如权利要求13所述的确定从起点到终点的目标路线的路径规划装置，其特征在于，其中所述的搜寻区域是指最小边界的矩形，包括由所述的多个矩形所形成的多边形区域。

Images