导航装置及用于依赖于时间的路线计算的方法

摘要

本发明涉及一种使用包含多个可导航路径的地图数据来确定路线的方法，所述地图数据被划分成多个区。所述方法包含使用至少一个处理设备以：接收所述地图数据上的起点及目的地以及行进时间，使用所述地图数据及识别所述地图数据的区之间的最小成本路径的最小成本数据来确定从所述起点到所述目的地的路线。在不同时间在所述区中的一对区之间存在不同最小成本路径的情况下，所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含从包含所述起点及所述目的地的所述对区的所述最小成本路径中识别按所述行进时间具有最低成本的最小成本路径。

主权项

一种使用地图数据确定从起点到目的地的路线的成本概况的方法，所述地图数据被划分成多个区，所述地图数据包含：多个可导航段，其表示所述地图数据的可导航路径的段，每一可导航段具有相关联的时变成本函数；及在所述地图数据的每个区中的用于所述可导航段的最小成本数据，其识别对于每一个其它区可导航段是否为任一时间周期到所述其它区的最小成本路径的部分，所述方法包含使用至少一个处理设备来：搜索从起点到目的地的路线，所述搜索包含确定连接到节点的一组可导航段中的一个或一个以上可导航段是否被所述最小成本数据识别为包含所述起点及所述目的地的区的最小成本路径的部分，且在所述组的所述可导航段中的一个或一个以上可导航段被识别为最小成本路径的部分的情况下，从所述组仅探索被识别为最小成本路径的部分的所述一个或一个以上可导航段；且根据所探索的所述可导航段的所述时变成本函数而随着时间的过去确定所述路线的成本概况，所述成本概况表示在不同行进时间所述起点和所述目的地之间的最佳路线的成本；其中确定随着时间的过去所述一个或一个以上路线的成本概况包含：当第一及第二最小成本路径在节点处相交时，将与所述第一最小成本路径相关联的第一成本概况同与所述第二最小成本路径相关联的第二成本概况组合以确定至少一个组合成本概况，并进一步从所述节点传播所述至少一个组合成本概况。