专利名称：导航装置及在其上实行的方法
技术领域：
本发明涉及使用地图数据确定路线的计算机化方法及相关系统。明确地说(但非排它地)，所述方法可用于导航装置中，用以促进路线规划。
背景技术：
已知路线规划算法(例如，迪科斯彻(Dijkstra)方法、k*方法或穆尔/裴帕 (Moore/Pape)方法)。然而，这些路线规划算法可能有些慢。在US 6 636 800中展示了如何可增加此路线规划的速度的实例，所述案的教示特此以引用的方式并入本文中。US 6 636 800教示通过将地图划分成多个区且确定到所述地图的每一区的最短路径(最小成本路径)的树而预处理地图数据。将此经预处理的数据存储在存储器中，且在路线的计算期间使用此经预处理的数据。
更具体地说，当起点位于一个区内且目的地位于另一区内时，可将预先确定的最短路径的树用以迅速确定将用作路线的部分的在所述区之间的路径。此方法减少了确定路线所需的处理的等级，因为其减少了当用户请求确定路线时所探索的路径的数目 。
将理解，“最短”路径未必表示最短距离的路径，而是表示具有最小成本的路径。路径的成本将取决于如指定于成本函数中的所考虑的因素，且可考虑例如最快速路线及燃料使用等因素。
当区之间的最短路径保持静态时，此方法为极成功的。然而，若用户想要使用不同于针对其已确定最小成本数据的成本函数的成本函数，那么必须从头开始确定路线选择， 从而显著增加确定路线所用的时间。此外，交通条件随时间的变化可改变为区之间的最短路径的路径，使得经预处理的树不再识别区之间的真正最短路径。这可导致针对指定准则来说并非最佳路线的路线被确定。发明内容
根据本发明的第一方面，提供一种使用包含多个可导航路径的地图数据确定路线的方法，所述地图数据被划分成多个区，所述方法包含使用至少一个处理设备以接收所述地图数据上的起点及目的地以及对多个成本函数中的一者的选择，且使用所述地图数据及识别所述地图数据的区之间的最小成本路径的最小成本数据确定从所述起点到所述目的地的路线，所述方法的特征在于，针对不同成本函数在所述区中的一对区之间存在不同最小成本路径的情况下，所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含从包含所述起点及所述目的地的所述对区的所述最小成本路径中识别针对所述选定成本函数具有最低成本的所述最小成本路径。
本发明可增加处理器针对所述多个成本函数中的任一者确定从所述起点到所述目的地的路线的速度。成本函数可为用于确定最快路线、最具燃料效率的路线或其类似路线的函数。
在一种布置中，如果所述对区之间在不同时间存在不同最小成本路径，那么最小成本数据可针对所述多个成本函数中的每一者包含一个以上最小成本路径，且确定路线包含从包含所述起点及所述目的地的所述对区的所述最小成本路径识别针对选定成本函数及指定时间具有最低成本的最小成本路径。所述指定时间可为由用户输入的行进时间。
每一最小成本路径可为针对所述多个成本函数中的一个以上成本函数的最小成本路径。每一最小成本路径可通过指针或旗标链接到所述多个成本函数中的一者或一者以上，在路线选择期间，仅考虑链接到所述选定成本函数的最小成本路径。识别所述最小成本路径可包含识别所述对区的链接到所述选定成本函数的最小成本路径。
在另一实施例中，最小成本数据可不识别哪一(哪些)最小成本路径适用于哪一 (哪些)成本函数。在此实施例中，识别最小成本路径可包含针对所述对区的所述最小成本路径中的每一者使用选定成本函数来确定成本，及识别具有最低成本的最小成本路径。
此布置可在不同时间在区中的一对区之间存在不同最小成本路径的情况下，相对于使用不识别在所 述对区之间的一个以上最小成本路径的数据而增加识别按行进时间所述区之间的最小成本路径的可能性。然而，使用最小成本数据使得能够比在使用从头开始确定最小成本路径的方法时更迅速地确定路线。举例来说，交通条件的可预测改变(例如， 规则的高峰时间)可变更区之间的最小成本路径。预先计算在不同时间在区之间的最小成本路径允许考虑到此些周期性改变。
确定所述路线可包含独立于时间根据所述最小成本数据识别一对区之间的最小成本路径，且针对从行进时间得出的一个或一个以上相关时间而对所述经识别的最小成本路径实行成本分析以确定按所述行进时间的最小成本路径。这可允许最小成本数据具有小得多的大�。蛭赜谧钚〕杀韭肪兜氖莶恍枰徊娌慰妓雎肪段钚〕杀韭肪兜氖奔�。例如导航装置等路线规划器可确定由最小成本数据识别的路径子集中的哪一路径为在相关时间时的最小成本路径。此布置确实将小的额外处理负担转移给路线规划器，但是作为回报，大量节省了最小成本数据的大小。
然而，在替代布置中，所述最小成本数据针对每一最小成本路径识别所述路径为所述最小成本路径的参考时间，且确定路线包含根据所述最小成本数据选择具有对应于从所述行进时间得出的一个或一个以上相关时间的参考时间的最小成本路径。此布置具有优点，因为将必须探索较少潜在路线以找到最小成本路线。
相关时间可为到达由最小成本路径连接的节点的预测时间。节点为地图上的可导航路径发生交叉/分叉的点或可导航路径的终点。因此，经由基于成本的分析而识别或经选择以用于路线中的最小成本路径将不会全部针对单个时间，而是将针对不同时间(视到达沿着路线的节点的时间而定)。举例来说，如果预测出花费一小时来行进过一路线，那么将基于到达沿着所述路线的节点的时间而识别/选择针对所述小时中的时间的最小成本路径。此外，分析/选择最小成本数据及确定路线可联合进行，因为仅可在已确定路线的一部分的情况下选择最小成本数据。
行进时间可为从起点的出发时间、到达目的地的时间，或到达沿着路线的特定所在地(例如，节点)的时间。
已发现，为了实现所要等级的精确性，最小成本数据的时间分辨率应具有秒的数量级，优选具有十分之一秒的数量级，且最优选具有百分之一秒的数量级。已发现，使用具有较粗略等级的时间样本的最小成本数据导致不可接受的精确性等级。此外，在以十分之一秒或百分之一秒为基数的范围内处理可相对于以60秒为基数的处理简化计算。可能需要避免比百分之一秒精细的等级，因为这可需要较大数目个位来存储数据。应理解，可将百分之一秒的时间分辨率存储为32位串，而较高分辨率可能需要64位串。
地图数据可包含识别在不同时间在路径上的预期速度的速度概况数据。可将所述地图数据的多条路径划分成多个可导航段，且速度概况数据可识别每一可导航段的速度概况。可至少部分地根据构成路径的可导航段的速度概况确定所述路径的成本。
在一个实施例中，所述方法包含根据速度概况数据确定针对相关时间的速度，其中根据所考虑的路线中的每一者的所确定的速度来计算成本。
在替代实施例中，所述方法包含根据正考虑的路线的可导航段的速度概况的多个值(而非单个值)来确定成本概况。换句话说，成本函数接收概况(即，多个值)作为输入， 且输出表示在不同时间路线的成本的概况。以此方式，可确定随着时间的过去的路线 的成本的变化。
所述方法可包含确定针对不同行进时间在共同起点与目的地之间的多条路线。举例来说，所述多条路线可用以比较不同行进时间如何影响路线及/或用以沿着在起点与目的地之间的路线行进的预测时间。举例来说，在高峰时间期间干线公路可能并非区之间的最小成本路径，但在高峰时间外可变成最小成本路径。这可导致针对不同行进时间的在起点与目的地之间的不同路线及行进的时间。确定多条路线可允许用户基于对所确定的路线的比较而就行进时间作出决策。
可将多条路线的确定与成本概况的产生组合以产生所述多条路线的从起点到目的地的成本概况。
所述方法可包含接收概况请求以确定针对所定义准则在起点与目的地之间的最佳行进时间，且作为响应，确定多条路线的成本概况(每一路线针对一不同行进时间)，且将结果显示给用户。
结果的显示可为最佳路线的行进时间的显示。因此，所述方法可包含根据所述成本概况(例如，通过比较成本概况的值而筛选结果)来确定针对所定义的准则所述多条路线中的哪一路线为最佳路线。以此方式，处理设备为用户确定最佳路线，且不需要由用户进行分析。
或者，结果的显示可为成本概况的显示(例如，图)。以此方式，用户可基于对所定义准则的评估以及选择最适合他/她的时间来选择路线。举例来说，在起点与目的地之间行进的最快速时间可能为在晚上，但用户可选择次最佳的路线，因为其在更方便的行进时间(例如，白天期间的某时间)。通过显示所述多条路线中的全部路线或至少一条以上路线的结果，用户可就行进时间及此如何影响路线作出明达的决策。
在一个实施例中，概况请求包括对路线的搜索受限于其内的时段。举例来说，用户可指定行进时间应在两个时间之间(例如，在上午6点与上午9点之间)，或在某一天(例如，在星期一)，在某个日期(例如，7月I日)，某个星期或某个月。或者，处理设备可自动搜索行进时间落在用户指定的行进时间的窗内(例如，用户行进时间±30分钟)的路线， 且在发现具有不同行进时间的路线比具有用户指定的行进时间的路线具有较低成本时，向用户建议替代行进时间。
在一个实施例中，所述方法包含经由用户接口从用户接收行进时间，且致使显示器显示所确定的路线的图像。所述方法可包含使得用户能够在检视展示所确定的路线的地图数据的图像的同时改变行进时间。举例来说，响应于行进时间的改变，可针对改变的指定行进时间确定新路线，且用所述新路线的图像来更新显示。或者，可已(例如，经由如上文所描述的成本概况的确定)预先确定针对其它时间的最小成本路线。可“实时”(例如，在毫秒的数量级)发生显示的更新，例如，小于1000毫秒且优选小于500毫秒。可经由使用用以识别区之间的最小成本路径的经预处理的最小成本数据而获得此些快速重新计算时间。 可通过刷新整个屏幕、使旧路线淡出及使新路线淡入及/或其它适当动画来实行显示的更新。将理解，新路线可能与旧路线相同或不同于旧路线，取决于针对不同时间最小成本路径中是否存在差异。
在一个实施例中，所述方法可包含致使显示表示行进时间的滑动条，且响应于用户与所述滑动条互动而确定新路线且以所述新路线的图像更新显示。所述方法可包含确定并显示新路线，使得对用户来说在所述用户改变行进时间之时与新路线的显示之时之间存在难以察觉的延迟。举例来说，在用户移动滑动条与显示新路线之间的延迟小于I秒且优选小于O. 5秒。
所述方法可包含致使显示器显示所述所确定路线的图像，从而使所述用户能够在检视所述图像时改变所述选定成本函数；及更新所述显示器以显示针对所述新选择的成本函数确定的路线的图像。所述显示器的更新可“实时地”(例如以毫秒数量级，例如在少于 1000毫秒且优选少于500毫秒的时间内)发生。可经由使用用以识别区之间的最小成本路径的经预处理的最小成本数据获得此些快速重新计算时间。所述显示器的更新可通过刷新整个屏幕、旧路线的淡出及新路线的淡入及/或其它适当动画来进行。将理解，取决于针对不同成本函数的最小成本路径是否存在差异，所述新路线可与所述旧路线相同或不同。
根据本发明的第二方面，提供一种上面存储有指令的数据载体，所述指令在由处理设备执行时致使所述处理设备执行根据本发明的第一方面的方法。
根据本发明的第三方面，提供一种数据载体，其上面存储有包含多个可导航路径的地图数据，所述地图数据被划分成多个区；及针对多个成本函数中的每一者识别在所述地图数据的所述区之间的最小成本路径的最小成本数据。
此数据载体为有利的，因为其可用于根据本发明的第一方面的对路线的确定。
根据本发明的第四方面，提供一种包含存储器及处理设备的计算机装置，所述存储器中存储有包含多个可导航路径的地图数据，所述地图数据被划分成多个区，识别所述地图数据的所述区之间的最小成本路径的最小成本数据；所述处理设备经布置以接收所述地图数据上的起点及目的地及对多个成本函数中的一者的选择，且使用所述地图数据及所述最小成本数据来确定从所述起点到所述目的地点的路线，所述计算机装置的特征在于， 针对不同成本函数在所述区中的一对区之间存在不同最小成本路径的情况下，所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含根据包含所述起点和所述目的地的所述对区的所述最小成本路径识别针对选定成本函数具有最低成本的最小成本路径。
根据本发明的另外方面，提供一种使用包含多个可导航路径的地图数据确定路线的方法，将所述地图数据划分成多个区，所述方法包含使用至少一个处理设备来接收所述地图数据上的起点及目的地，且使用所述地图数据及识别所述地图数据的区之间的最小成本路径的最小成本数据来确定从所述起点到所述目的地的路线，所述方法的特征在于，如果在一对区之间在不同时间存在不同最小成本路径，那么所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含识别包含所述起点及所述目的地的所述对区的每一最小成本路径何时具有最低成本。
根据本发明的另一方面，提供一种包含存储器的计算机装置，所述存储器中存储有包含多个可导航路径的地图数据，所述地图数据被划分成多个区；识别所述地图数据的所述区之间的最小成本路径的最小成本数据，且处理设备经布置以接收所述地图数据上的起点及目的地，且使用所述地图数据及识别所述地图数据的区之间的最小成本路径的最小成本数据来确定从所述起点到所述目的地的路线，所述计算机装置的特征在于，如果在一对区之间在不同时间存在不同最小成本路径，那么所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含识别包含所述起点及所述目的地的所述对区的每一最小成本路径何时具有最低成本。
根据本发明的又一方面，提供一种产生跨越电子地图从起点位置到目的地位置的路线的(计算机实施的)方法，所述电子地图包含表示由所述电子地图涵盖的区域中的可导航路线的段的多个向量，所述方法包含
-利用提供对所述电子地图的校正的数据，其包含指示先前并非所述电子地图的部分的向量的数据；
_修正指示所述电子地图中的哪些向量为所述最低成本路线的部分以指示所述新向量为所述最低成本路线的部分的路线选择加速数据，以形成经修正的路线选择加速数据 '及
-产生所述起点位置与所述目的地位置之间的路线，所述产生包括利用所述经修正的路线选择加速数据。
此方法为有利的，因为其将允许在利用路线选择加速数据时在路线选择过程中考虑所述新向量。如果所述新向量未如此标记，那么所述新向量不会被使用所述路线选择加速数据的路线选择方法考虑，因为在产生路线选择加速数据时尚未考虑所述新向量；所述路线选择加速数据是针对特定电子地图预先产生的，从而指示所述电子地图中的哪些向量形成到目的地的最低成本路线的部分。
所述方法可包括下载提供对所述电子地图的校正的数据，藉此允许利用来自远程源的数据。
根据本发明的其它方面，提供一种机器可读媒体，其含有在读取到至少一个机器上时致使所述机器执行上述方法中的任一者的指令。
关于本发明的一个方面或实施例所描述的任何特征可加以必要变更而适当地与本发明的任何其它方面或实施例一起使用。
所属领域的技术人员将了解，可以软件、固件、硬件或其任何组合提供本发明的实施例。
现在接着是仅举例来说的参看附图对本发明的 实施例的详细描述，其中
图I为可由导航装置使用的全球定位系统(GPS)的示范性部分的示意性说明；
图2为跨越通信信道而通信的服务器与导航装置的示意图3a为导航装置的不意图3b为由图3a的导航装置使用的架构堆叠的示意性表示；
图4为导航装置的透视图5展示如由本发明的实施例产生的实例地图的一部分；
图6展示图5的地图，其上展示了用于路线选择的节点；
图7展示在处理之后的图5的地图8展示在一些实施例中节点如何被分配到图7的地图的实例；
图9说明地图如何可被分割成多个巢式区的实例；
图9a说明图9的分割的增强；
图10展示由本发明的实施例利用的位向量的实例集合；
自图IOa说明如何在网络的迪科斯彻探索期间利用时间分析(time profiled)的信；& ;
图11展示本发明的实施例的文件的实例文件格式；
图12展示可如何编码图11的区重新映射表及区ID列表的实施例；
图13展示如图3中所说明的最粗略巢式区的实例文件格式；
图14展示除了最粗略巢式区之外的巢式区的实例文件格式；
图15示范编码方案内的位的聚结；
图16示范聚结位的效应；
图17也示范聚结位的效应；
图18展示使用现有技术路线选择技术来醒目提示所考虑的路线的地图19展示通过本发明的实施例来醒目提示所考虑的路线的地图20展示k*搜索方法(现有技术)的实例；
图21展示由本发明的至少一些实施例使用的对图20的修改；
图22展示概述本方法的步骤的流程图23展示说明路线的可导航段上的预期速度的导航装置的显示器；
图24展示说明在起点与目的地之间的一个或一个以上路线的成本概况的导航装置的显示器；
图25展示说明在起点与目的地之间的一个或一个以上路线的成本概况的导航装置的显示器；
图26展示说明针对特定行进时间的在起点与目的地之间的路线及用于改变行进时间的控件的导航装置的显示器；
图27展示在用户已变更行进时间之后对图26的显示的更新；
图28展示在用户已进一步变更行进时间之后对图27的显示的更新；
图29展示导航装置的一系列显示，其中向用户建议行进时间；
图30展示说明在交叉节点处两个竞争路线的成本概况的曲线图31展示从图30中所展示的成本概况得出的上界及下界成本概况；及
图32展示显示在导航装置上的用以选择成本函数的菜单。
具体实施方式
贯穿以下描述，相同参考数字将用以识别相同部分。贯穿对各个实施例的描述，对参考标号处于19xx系列中的图22的流程图进行了参考。
图I示意性地展示全球定位系统(GPS)，全球定位系统(GPS)为基于卫星-无线电的导航系统，其可用以确定无限数目个用户的连续位置、速度、时间，及(在一些情况下)方向信息。过去被称为NAVSTAR的GPS并入有在极其精确的轨道中绕地球运转的多个卫星。 基于这些精确轨道，GPS卫星可将其所在地作为GPS数据中继到任何数目个接收单元。然而，将理解，可使用例如GL0SNASS、欧洲伽利略(Galileo)定位系统、COM PASS定位系统或 IRNSS(印度区域导航卫星系统)等全球定位系统。
当经专门配备以接收GPS数据的装置开始扫描无线电频率以寻找GPS卫星信号时，实施GPS系统。在从GPS卫星接收到无线电信号后，所述装置即刻经由多种不同常规方法中的一者来确定所述卫星的精确所在地。在多数情况下，所述装置将继续扫描以寻找信号，直到其已获得至少三个不同的卫星信号(注意，可使用其它三角测量技术通过仅两个信号来确定位置，虽然这并非常例)。在实施几何三角测量的情况下，接收器利用三个已知的位置来确定其自己相对于所述卫星的二维位置。可以已知方式进行此确定。另外，获得第四卫星信号允许接收装置以已知方式通过相同几何计算来计算其三维位置。无限数目个用户可在连续基础上实时更新位置及速度数据。
如图I中所展示，GPS系统100包含围绕地球104运转的多个卫星102。GPS接收器106从所述多个卫星102中的若干卫星接收作为扩频GPS卫星数据信号108的GPS数据。 从每一卫星102连续地发射扩频数据信号108，所发射的扩频数据信号108各自包含数据流，所述数据流包括识别所述数据流所源于的特定卫星102的信息。GPS接收器106通常需要来自至少三个卫星102的扩频数据信号108，以便能够计算二维位置。对第四扩频数据信号的接收使GPS接收器106能够使用已知技术计算三维位置。
因此，GPS系统允许具有GPS接收器106的装置的用户将其在地球上的位置确定到几米范围内。为了利用此信息，常见做法是依赖于允许在其上展示用户的位置的电子地图。例如TeleAtlas (http://www. teleatlas· com)等提供商不范此些地图。
此些电子地图不仅允许使用GPS系统(或通过其它方式)将用户的位置展示于电子地图上，而且其允许用户规划行程路线等(路线选择目的)。为了进行此路线规划，由导航装置来处理电子地图，所述导航装置可由通用计算装置提供。
导航装置的特定实例包括卫星导航装置(Sat. Nav)，其方便地称作便携式导航装置(PND)。然而，应记�。痉⒚鞯慕淌静幌抻赑ND，而是可改为普遍适用于经配置以处理电子地图(通常)以便提供路线规划及导航功能性的任何类型的处理装置。因此，由此可见， 在本申请案的背景下，导航装置意在包括(但不限于)任何类型的路线规划及导航装置，无论所述装置是体现为PND、例如汽车等交通工具、便携式计算资源(例如，执行路线规划及导航软件的便携式个人计算机(PC)、移动电话或个人数字助理(PDA))或服务器，或是体现为跨越网络提供此功能性的其它计算装置。
在图3a及4b中展示所述呈PND的形式的导航装置的实例，且应注意，导航装置 200的框图不包括所述导航装置的所有组件，而是仅为许多实例组件的代表。导航装置200 位于外壳(未图示)内。导航装置200包括处理电路，所述处理电路包含(例如)上文所提到的处理器202，所述处理器202耦合到输入装置204及显示装置(例如，显示屏206)。 虽然此处以单数形式提到输入装置204，但所属领域的技术人员应了解，输入装置204表示任何数目个输入装置，包括键盘装置、话音输入装置、触摸面板及/或用以输入信息的任何其它已知输入装置。同样，显示屏206可包括例如液晶显示器(LCD)等任何类型的显示屏。
在导航装置200中，处理器202经由连接210而操作性地连接到输入装置204且能够经由连接210从输入装置204接收输入信息，且经由相应的输出连接212而操作性地连接到显示屏206及输出装置208中的至少一者，以将信息输出到所述至少一者。导航装置200可包括输出装置208，例如，可听输出装置(例如，扬声器)。在输出装置208可为导航装置200的用户产生可听信息的同时，应同等地理解，输入装置204还可包括用于接收输入话音命令的麦克风及软件。另外，导航装置200还可包括任何额外输入装置204及/或任何额外输出装置，例如，音频输入/输出装置。
处理器202经由连接216而操作性地连接到存储器214，且进一步适于经由连接 220从输入/输出(I/O)端口 218接收信息/将信息发送到输入/输出(I/O)端口 218，其中I/O端口 218可连接到在导航装置200外部的I/O装置222。外部I/O装置222可包括 (但不限于)外部收听装置，例如，听筒(earpiece)。到I/O装置222的连接可另外为到任何其它外部装置(例如汽车立体声单元)的有线或无线连接，以用于(例如)免提操作及/ 或用于话音激活的操作、用于连接到听筒或头戴式耳机及/或用于连接到(例如)移动电话，其中移动电话连接可用以创建在导航装置200与(例如)因特网或任何其它网络之间的数据连接，及/或用以创建经由(例如)因特网或某一其它网络到服务器的连接。
导航装置200的存储器214包含非易失性存储器的一部分(例如以存储程序代码)及易失性存储器的一部分会(例如以在所述程序代码被执行时存储数据)。所述导航装置还包含端口 228，所述端口 228经由连接230而与处理器202通信，以允许可装卸存储卡(通常被称作卡)被添加到装置200。在所描述的实施例中，所述端口经布置以允许添加 SD (安全数字)卡。在其它实施例中，所述端口可允许连接其它格式的存储器(例如，压缩快闪(CF)卡、Memory Stick 、xD存储卡、USB (通用串行总线)快闪驱动器、MMC (多媒体) 卡、智能媒体卡、微驱动器等)。
图2进一步说明经由连接226的在处理器202与天线/接收器224之间的操作性连接，其中天线/接收器224可为(例如)GPS天线/接收器，且因而将充当图I的GPS接收器106。应理解，为了说明而示意性地组合由参考数字224表示的天线及接收器，但天线及接收器可为单独定位的组件，且天线可为(例会)GPS片状天线或螺旋天线。
另外，图3及4的便携式或手持型导航装置200可以已知方式连接或“对接”到例如自行车、摩托车、汽车或船等交通工具。可接着将此导航装置200从对接所在地移除以用于便携式或手持型导航用途。实际上，在其它实施例中，装置200可布置为手持型的以允许用户的导航。
参看图3a，导航装置200可为包括集成输入及显示装置206及图3a的其它组件(包括但不限于，内部GPS接收器224、处理器202、电力供应器(未图示)、存储器系统214 等)的单元。
导航装置200可位于臂状物252上，可使用吸盘254将臂状物252本身紧固到交通工具仪表板/窗/等等。此臂状物252为导航装置200可对接到的对接台的一个实例。可通过将导航装置200搭扣连接到臂状物252而将导航装置200对接或以其它方式连接到对接台的臂状物252。导航装置200可接着可在臂状物252上旋转。为了释放导航装置200 与对接台之间的连接，可(例如)按压导航装置200上的按钮(未图示)。用于将导航装置 200耦合到对接台及将导航装置200从对接台去耦的其它同等合适的布置是所属领域的技术人员众所周知的。
转到图3b，处理器202与存储器214合作以支持BIOS (基本输入/输出系统)282， 其充当导航装置200的功能硬件组件280与由所述装置执行的软件之间的接口。处理器 202接着从存储器214加载操作系统284，所述操作系统284提供应用程序软件286 (其实施所描述的路线规划及导航功能性中的一些或全部)可运行的环境。应用程序软件286提供操作环境，所述操作环境包括支持导航装置的核心功能(例如，地图检视、路线规划、导航功能及与此相关联的任何其它功能)的图形用户接口(GUI)。就此来说，应用程序软件 286的部分包含视图产生�？�288。
在正描述的实施例中，导航装置的处理器202经编程以接收由天线224接收到的 GPS数据，且不时地将所述 GPS数据连同表示GPS数据被接收的时间的时戳一起存储在存储器214内以积累导航装置的一系列位置。经如此存储的每一数据记录可被认为是GPS定位；即，其为导航装置的所在地的定位且包含纬度、经度、时戳及精确性报告。此系列位置可被认为是定位数据。
在一个实施例中，大体上周期性地(例如，每5秒)存储数据。所属领域的技术人员将了解，其它周期将为可能的，且在数据分辨率与存储器容量之间存在平衡；即，随着通过取得更多样本而使数据的分辨率增加，需要更多存储器来保持数据。然而，在其它实施例中，分辨率可为大体上每I秒、10秒、15秒、20秒、30秒、45秒、I分钟、2. 5分钟(或实际上， 这些周期之间的任何周期)。因此，在装置的存储器内，积累了装置200在各时间点处的行踪的记录。
在一些实施例中，可发现，所捕捉的数据的质量随着周期增加而减小，且同时降级的程度将至少部分地视导航装置200移动的速度而定(约略15秒的周期可提供合适上限)。
另外，处理器202布置成不时地将装置200的行踪的记录(S卩，GPS数据及时戳) 上载到服务器。在导航装置200具有将其连接到服务器的永久的或至少通常存在的通信信道的一些实施例中，周期性地发生数据的上载(其可为(例如)每24小时一次)。所属领域的技术人员将了解，其它周期为可能的，且可大体上为以下周期中的任一者15分钟、30 分钟、每小时、每2小时、每5小时、每12小时、每2天、每周或在这些周期之间的任何时间。 实际上，在此些实施例中，处理器202可经布置以大体上实时地上载行踪的记录，但这可能不可避免地意味着事实上数据被不时地发射而在发射之间具有相对较短的周期，且因而数据可被较为正确地认为是伪实时的。在此些伪实时实施例中，导航装置可经布置以在存储器214内及/或插入于端口 228中的卡上缓冲GPS定位，且当已存储预定数目时发射这些12GPS定位。此预定数目可为大约20、36、100、200，或这些数目之间的任何数目。所属领域的技术人员将了解，所述预定数目部分地由存储器214/端口 228内的卡的大小控管。
在不具有通常存在的通信信道的其它实施例中，处理器可经布置以在通信信道被创建时将记录上载到服务器。这可(例如)在导航装置200连接到用户的计算机时发生。 并且，在此些实施例中，导航装置可经布置以在存储器214内或插入于端口 228中的卡上缓冲GPS定位。如果存储器214或插入于端口 228中的卡变得充满GPS定位，那么导航装置可经布置以删除最旧的GPS定位，且因而，其可被认为是先入先出(FIFO)缓冲器。
在正描述的实施例中，行踪的记录包含一个或一个以上迹线，其中每一迹线表示导航装置200在24小时周期内的移动。每一 24小时周期经布置成与日历日一致，但在其它实施例中，无需为此情况。
服务器150经布置以接收装置的行踪的记录，且将此存储在大容量数据存储装置内以供处理。因此，随着时间过去，大容量数据存储装置累积已上载了数据的导航装置200 的行踪的多个记录。一般来说，服务器将收集多个导航装置200的行踪。
服务器可接着经布置以根据所述装置或每一装置的所收集的行踪而产生速度数据。此速度数据可包含时变速度概况，其展示沿着地图的可导航段的平均速度如何随着时间变化。
图7展示电子地图的实例，在所描述的实施例中，跨越网络(在此情况下为因特网)在导航装置上检视所述电子地图。在本文中正描述的实施例中的任一者中的第一步骤为产生此电子地图 1900。可在 http://routes, tomtom, com/ Lid= l#/map/ center =55. 01 % 2C-3. 445&zoom = 4&map = basic 检视所述地图。
为了实现图7的将被用于路线选择目的的电子地图，所述电子地图具有一系列节点，所述电子地图的用户通�？床坏剿鼋诘�。因而，节点等等可通常被称作地图数据。然而，为了便于理解，在图6中展示节点300中的一些节点。这些节点被设在可导航段(在此情况下为道路段)的交叉点、末端区等等处，且被用于路线选择的目的。当用户要求其导航装置规划在两个点或两个以上点之间的路线时，所述导航装置规划地图的相关节点之间的路线。因而，地图数据可用以根据由导航装置的用户设定的至少一个准则来产生路线。
所属领域的技术人员将了解，电子地图还包含提供道路段的形状、建筑物的入口的所在地等等的其它节点。
因此，每一节点300具有从其发出的、用户可沿其行进的至少单个道路段，且通常为多个道路段。举例来说，节点302具有四个此种道路段304a、b、c、d。在其它实施例中，可导航段可表示并非道路的路径的段，例如，人行道、自行车道、沟渠、铁路、道路段、轨道等。 然而，为方便起见，参考道路段。因此，如图7中所展示的地图向其用户展示多个道路段，所述多个道路段中的每一者表示在由所述地图覆盖的区域中的可导航路线的一部分。
已知路线规划方法(例如，迪科斯彻(Dijkstra)方法、A*方法或穆尔/裴帕 (Moore/Pape)方法)。然而，这些路线规划方法在计算时间方面可为极其慢的。在US 6 636 800中展示了如何可增加此路线规划的速度的实例，所述案的教示特此以引用的方式并入本文中。
本文中所描述的实施例在预处理步骤中产生含有最小成本数据的所谓的侧文件 (side file)，所述最小成本数据由导航装置用以在处理电子地图时加速路线的产生。可将此信息以可被称为位向量的形式保持为二进制数据；即，O与I的串。因而，所述侧文件还可被认为是地图数据，但可与电子地图一起或不与电子地图一起供应侧文件(例如，如图8 中所展示)。因此，本发明的一些实施例可将地图数据提供为可与侧文件分离的地图，而本发明的其它实施例可组合地图与侧文件数据。
然而，所属领域的技术人员将了解，如果使用侧文件，那么所述侧文件应与电子地图(针对其而产生所述侧文件)一起使用。如果并未执行此，那么可想象，将获得不正确路线(例如，未使由其用户设定的成本公式最小化的路线)。
并且，本发明的不同实施例可指定用于产生最小成本数据的不同参数(在此实施例中，为一系列位向量)。因而，如果使用所产生的地图数据的后续路线规划使用了与用以创建最小成本数据的所述参数不同的参数，那么所述最小成本数据不太可能对所述路线规划有用。
举例来说，一些实施例可产生用于乘汽车行进穿过地图的最小成本数据。如果后续路线规划系用以产生用于步行的路线，那么汽车特定最小成本数据不太可能为有用的。 在另一实例中，一些实施例可产生在假定用户乐于沿着高速公路、收费道路等等行进的情况下的最小成本数据。在后续路线规划中，如果用户请求利用高速公路、收费道路等等的路线，那么所述最小成本数据不太可能为有用的。
本发明的一些实施例可产生最小成本数据的多个集合，其各自具有预定准则的不同集合。举例来说，本发明的实施例可约略产生以下各项中的任一者2、3、4、5、6、10、15，或更多集合的最小成本数据。
因此，在一些实施例中且为了产生侧文件，在地图预处理步骤中，将节点划分到多个区中，且因而，任何地图均被划分成已知数目个区-例如，N个，且确定所述区之间的最小成本路径。此预处理产生可与地图一起利用的数据以便增加路线规划方法的速度。
通常，在使用地图数据之前执行预处理，而不管所述地图数据将用于网站上还是用于例如PND等装置上。因而，预处理步骤常常被称作服务器侧进程。
虽然任何通用计算装置均将适于执行预处理，但所属领域的技术人员将了解，装置的性能越高，预处理将执行得越快。通常，将X86架构计算装置用于预处理。此种X86架构装置将通常运行例如Microsoft Windows 、UNIX、LINUX、OSX 等等的操作系统(OS)。 然而，其它实施例可使用例如RISC架构等其它计算平台。
并且，如别处所论述，可并行执行预处理，且因而，可在多个计算装置上或至少在多个处理器核心(其可为虚拟或真实处理器核心)上执行预处理。
作为下一预处理步骤，处理一区内的每一道路段(例如，304a_d)以确定其是否为到所述地图内的所述数目(N)个区中的每一区的最小成本路径的部分，且产生位向量(最小成本评估)。因此，对于一区的每一道路段，位向量针对地图的每一区包含一位。即，位向量包含N-I个位(除在考虑中的区外，每一区I个)，其经设定成O或I，取决于所述道路段是否形成到由所述位表示的区的最小成本路径的部分。一些实施例可添加额外位以提供进一步信息，例如，标头、可见度区域、相邻区域等等。
所属领域的技术人员将了解，在此意义上，可对照若干不同成本准则确定最小成本路径。举例来说，可对照以下准则中的任一者判断最小成本最短距离；最短行进时间； 花费最小(在环境影响方面)；使用最少汽油；产生最少CO2，等等。在本实施例中，对照最短行进时间来判断最小成本。
在本发明的此实施例中，针对多个成本准则(成本函数)中的每一者确定最小成本路径。因此，所得侧档案可识别任何两个区之间的可适用于任何一个时间的一个以上最小成本路径，每一最小成本路径针对一不同成本准则(成本函数)。举例来说，最快路线的最小成本路径可不同于最具燃料效率的路线的最小成本路径。
因此，所属领域的技术人员将了解，对于覆盖大量区域的地图来说，N很可能为较大的。因此，预处理可花费大量时间。
因此，在(例如)覆盖西欧及中欧的实例地图中，通�？赡艽嬖�40，000，000个节点，其具有100，000，000个道路段。假定在地图内存在100个区，那么N等于100，且存在 100，000，000X 100 (N)个；即，需要IOxlO9个位来存储所述地图的每一道路段的99 (即， N-1)个位。在使用下文所描述的本发明的实施例的情况下，此地图可能使用约略500Mb的存储装置。
W02009/053410论述指派速度概况的方法，所述速度概况提供随着时间而变的沿着地图的可导航段的速度。此申请案的内容特此以引用的方式并入本文。因而且出于路线选择的目的，可导航段是否构成到另一区的最快速路线的部分将根据时间而变化。即，随着交通密度增加/减小(例如，在高峰时间等)，使用可导航段分别将变得较不/较合意。·
一些实施例可针对每一道路段存储多个位向量。所属领域的技术人员将了解，记录速度的分辨率越高，所需位向量的数目越高。然而，其它实施例可利用时变函数来对最快速路线作出评估(非常像W02009/053410中所描述)。
在跨越电子地图进行路线规划时，相信，有必要能够使用约略百分之一秒精确度的时间粒度进行路线规划；即，能够将从节点的出发时间指定到0.01秒的精确度以便正确地确定最低成本路线。
因此，在考虑此精确性的等级时，将了解，上文所考虑的具有40，000，000个节点及100，000，000个道路段的地图具有穿过其中的100，000，OOO2个可能的路线。当进一步考虑时间维度时，路线的数目进一步增加7(s卩，每周天数)X24( S卩，每日小时数)X3600(即，每小时秒数)XlOO (即，每秒的百分之一秒数)X 100，000，OOO2 = 604. 80 O. 000. 000. 000. 000. 000. 000 (千的七乘方)个可能的路线。在当前处理等级且在使用在每一时间间隔处探索每一段的单纯方法的情况下，将花费19. 178. 082. 191. 780. 821年。申请人当前销售的西欧及中欧的地图具有120，000，000个道路段，藉此进一步增加此时间。
因此，将了解，为了在预处理阶段中存储并处理数据，需要大量数据。
因而，本发明的实施例使用技术以便显著减少预处理的量。现在更详细地描述这些技术，且本发明的一些实施例可能利用所有所述技术，而其它实施例可能仅利用所述技术中的一些技术。
本发明的不同实施例可使用下文所概述的特征的不同组合。因而，一些实施例可利用所描述的全部技术以减少信息的量。在另一极端，其它实施例可能不利用所述技术当中任一者来减少数据。
本发明的一些实施例不计算不符合预定准则的道路段的位向量_如步骤1902所展示。举例来说，如果不可能以预定运输类别沿着道路段行进，那么可能不计算所述道路段的位向量。
因此，在将运输模式的准则设定成汽车的实例中，可能不计算以下道路段的位向
铁路；
·存在于地图数据中的未对应于道路段的段；
·错误(非法)方向上的单行道路；
·不可由某运输形式通行的道路段(例如，在考虑汽车的驾驶性时的行人徒步区、 人行道)；
·非决策点处的道路段(即，不能从道路段避开)；
网络的减小
一种技术为减小经考虑以评估道路段是否形成最小成本路径的部分的网络的大�。患跎俚缆范蔚氖炕峒跣〗屑扑闼ǚ训氖奔淞浚绮街�1904处所展示。
为了说明此技术，还在图6中展示如图7中所展示的道路网络，但从其删除了对于最小成本评估来说没有用的道路段。对网络的此减小旨在提供最小子网络，应对所述最小子网络进行最小成本评估。
在数学术语中，被留下的且如图7中说明的网络可被描述为图7的道路网络的最大强组成部分的不定向表示的最大的双向连接的组成部分。通过将标准技术应用于两种强连接性(还称为双向连接性)同时适应于道路交通规则(例如，转弯限制及本地准入 (Iocalaccess))来确定核心网络。所属领域的技术人员将了解，强连接性指示在两个节点之间在两个方向(即，从A —B以及B —A)上行进为可能的。
因此，参看图5与7两者，可见，已删除例如死胡同250、冗余环路252等等的无出口的路。然而，将看见，在已被移除的道路段的起点处剩余有节点(例如，图7中的400)。 这是由于下文中所论述的原因。
在减小到核心网络之后(例如，如图7中所展示)，分割核心网络以提供上文所描述的区。在所描述的实施例中，根据多路弧分离器(multiway arc separator)来分割网络。 所属领域的技术人员将了解，在此网络中，如果由区边界等分的道路段(即，弧)被移除，那么留在任一区中的道路段将不连接到任何其它区。
分割网络-步骤1906
然而，在执行分割之前，进行以下步骤
I.独立地确定并分割岛屿。岛屿趋向于与网络的其它部分物理上分离，且藉此通过例如轮渡链等等的方式而链接。这些以与典型道路段不同的方式表现(即，平均速度显著较低，等等)，且如果此些链接被包括于分割中，那么所述方法不会有像预期一样好的性倉泛。
2.收缩由网络中的一个以上节点表示的十字路口、环形道及其它接点，使得属于同一十字路口等等的节点不会落到不同区中。
3.收缩所有可导航段共享相同特性集合(例如，轮渡段、禁止驾驶、禁止通行等等)的简单路径(即，不具有转弯可能性的两个节点之间的连接)以减小传递到分割系统的网络的输入大小。举例来说，查看图6，可将节点308折叠到道路310上。
本发明的正描述的实施例使用分治(divide and conquer)方法，在http:// labri. fr/perso/pelegrin/scotch处概述所述分治方法。本文中所概述的方法划分地图以包含若干个区，所述区并不基于地图的区域，而是基于区内所含有的节点的数目。具有经如此组织的节点具有以下优点其可有助于使使用所述区的路线选择更有效率，因为其有助于递送具有类似本地搜索直径的区。
每一节点具有与其相关联的包括区ID的身份编号，且因而，同一区中的节点具有相同区ID号。节点属于在L个层级式等级处的区。按照惯例，等级O为最粗略等级(用于长距离路线选择)。等级L-I为详细等级。
方便地对节点的最大数目设定上限且允许低于此上限的某种灵活性，而不是设定任一区内含有的节点的绝对数目。举例来说，所述方法可指定每区最大节点数目为100个， 这可导致每区通常有60个到100个节点的节点散布。上限被认为比固定数目个节点有利， 因为固定数目可导致具有强制形状的区，这又导致在使用所述区时的次最佳的路线选择。
多个等级
在所描述的实施例中，执行分割以提供多个等级的巢式区，在图9中在概念上示范所述区。从图9将清楚，存在层级本质，其中将最低等级(O)再分以提供等级1，又将等级 I再分以提供等级2。
每一区中的节点的数目在等级之间变化，且与较低等级相比，较粗略等级(其趋向于覆盖较大地理区域)具有更多节点。因而，通常出于长程路线选择目的而使用正描述的实施例中的较粗略等级(例如，等级O)，而较精细等级(例如，等级2)用于短程的路线选择。
每一道路段的位向量的一部分包含针对所述等级中的每一者的位。位的数目为每一等级中的区的数目。
为了提供要编码的数据量的概念(在典型实施例中，等级的数目将通常为L = 3)
全局等级=O,将通常具有100个区。
·中间等级=1，将通常针对等级O的每一区具有10个区(即，100X 10)。
最详细等级=2，将通常针对等级I的每一区具有5个区(即，100X 10X5)。
使用层级式等级为有利的，因为其减小(可能显著减小)所需的处理量。在正描述的本实施例中，存在100 X 10 X 5个区(S卩，5000个区)。因此，在具有相同数目个区的平坦结构中，将要求本文中所概述的方法涉及5000个区。然而，在本文中所描述的实施例中， 可通过参考处于适当等级中的节点来减少此数目。
一旦已知地图的各个因素，等级的数目及每等级的区的数目将通常被调谐。举例来说，多少存储装置可被分配给地图，以及路线选择的应有执行速度。所属领域的技术人员将了解，存在折衷，因为随着预处理的量增加，那么地图大小变得较大以保持数据，但是可使用所述地图来计算较快速路线。
在一个实施例中，存在3个等级的区。然而，在其它实施例中，可能存在任何数目个等级。举例来说，可能约略存在以下数目个等级中的任一者1、2、4、5、6、7、8、9或10。
因此，在使用上文的实例(通常具有40，000，000个节点及100，000，000个道路段的西欧及中欧的地图)的情况下，使用最单纯编码将针对每一等级的每个节点的区ID使用固定大小编码，且针对每一等级的每一道路段使用固定大小位向量(arp旗标)。因此，可易于将此基本编码的大小计算如下
·等级O处的每一节点区ID将使用log_2(100)位=7个位
·等级I处的每一节点区ID将使用log_2(10)位=4个位
·等级2处的每一节点区ID将使用log_2(5)位=3个位
·等级O处的每一位向量(arp旗标)将使用100个位(100个区减去针对当前区的I)
·等级I处的每一位向量(arp旗标)将使用10个位(10个区减去针对当前区的 I)
等级2处的每一位向量(arp旗标)将使用5个位(5个区减去针对当前区的I)
图9展示最粗略的区等级600，其在所述图中提供6个区I到6。将这些区中的每一者再分成更多的区(在此实施例中，九个子区)，如由粗略区等级600内的虚线道路段表示。在所描述的实施例中，使用另一等级的再分，其中还再分由虚线道路段提供的区中的每一者，因而提供三个等级的分割，但为了便于参考未在图9中展示这些等级。其它实施例当然可使用较多等级(例如，4、5、6、7个或更多等级)或较少等级(例如，I或2个等级)。
因此，本发明的实施例针对较精细等级区引入所谓的可见度区域，步骤1908。k区的可见度区域为一组(k-Ι)个区，其中可在旗标集合中的所述区自己的位上区别所述区。 自然地，可见度区域总是包括给定k区所属于的(k-Ι)区。另外，可见度区域可能含有一些相邻的(k-Ι)区。将在预处理期间计算可见度区域，且将可见度区域与位向量相关联地存储。
还可从相反侧看出k区与其(k-Ι)等级的可见度区域之间的关系每个(k-Ι)区知晓其由位于邻域的k等级区组成的外围(outskirt)。以此方式,可看出道路段的旗标集合不再贯穿整个地图具有固定长度；实情为，每个I区中的位向量具有其特定长度A+B+C+N 外围0+N外围I。其中A指代区的最粗略等级，B指代中间粒度区,且C指代最精细粒度的区(在存在三个等级的实施例中)。
后续预处理在最短路径计算之前计算可见度区域以产生位向量。可将找到可见度区域的方法描述如下
对于每一 k区来说，开始区相邻图中的广度优先搜索；
接着对于每一到访过的k区(其位置足够接近开始区)，将其含有的(k-Ι)区添加到可见度区域。
“接近”关系应将地理量度(例如，区中值点之间的距离)与图理论距离两者考虑在内。(因此，如果一区在地理上为远的但通过快速连接而链接到当前区，那么所述区可为 “接近”的。同样，如果难以在区之间行进，那么一区可被认为“遥远的”(即使其在地理上接近))。
确切的阈值可经受实验调谐，因为其视地图特定的特性(如都市区域的平均直径)而定，其最易受上文所描述的负面效应(例如，增加的预处理等等)影响。具有格外长行进时间的可导航段(如轮渡或禁止驾驶的道路段)在相邻图遍历(adjacency graph traversal)期间被隐藏,这样可见度区域总是限于单一岛ill与或属于同一区的小群岛山与。
因此，在广度优先搜索期间到访过的区构成R的邻域。完全覆盖所述邻域的下一较粗略等级的区的包括最小(inclusion-minimal)集合被称为R的可见度区域。反向关系被称为附近(vicinity):区Q(等级L处)的附近列表是由在等级L+1处的在其可见度区域中有Q的所有区组成。
为了提供特定实例，且参看图9，可见度区域的实例如下
如果决定每一 I区与其可见度区域的边缘之间的最小距离应为至少1，那么一些选定I区的可见度区域将由以下O区组成(自己的O区可被省略，因为其总是存在)
· 15
( S卩，等级I区第15号不具有可见度区域，因为其处于其等级O区的中心)。
· 28 5
(即，等级I区第28号具有为区(等级O)第5号的单个可见度区)。
· 37 2,5,6
(即，等级I区第37号具有三个可见度区，其为等级O区2、5及6)
除了考虑等级I区的等级O邻居，还确定每一等级O区的等级I邻居。因此，作为实例，
· I =21,24,27,28,41,42,43,51
(即，对于等级O区第I号，等级I区为:21、24、27、41、42、43、51)。
因此，在此实例中，可看出，区28被列出，尽管其不在区2的最左侧列中。这(例如)可能因为区28具有到区I的快速链接，且因而当在时间而非距离方面进行考虑时为接近的。所属领域的技术人员将了解，可对照例如环保性(greenness)(最少CO2或其类似者) 等其它量度来判断接近性。
邻居列表的编码
与图9相比，图9a展示可使用的等级的更多细节。等级O为最粗略等级且可被认为是等级k-Ι。为简易起见，在图9a中，仅展示区I到区4(即，602 ;604 ;606 ;608)。这些 k-Ι区中的每一者进一步被划分成9个区(I到9)，其可被称作k等级区或等级I区。另外， 这些等级I区中的每一者被划分成4个k+Ι等级区(即，等级2区)。
位向量的产生
一旦网络已被分割成三个等级的区，那么其经处理以确定到所述区中的每一者的最小成本路径，且为区内的每一道路段创建位向量，步骤1910。因此，如上文所论述，关于成本公式来分析任一区内的每一道路段，以确定其是否为到每个其它区的最低成本路径的部分。产生一区中的每一道路段的位向量，如图7中所展示，为便于理解，图7展示简化的位向量。
还应了解，确定最小成本路径，其不仅针对单个时间段，而是针对多个时间段来计算(如下文中所描述)。
针对图7中所展示的网络(即，减小的网络)来执行此计算。网络的已被移除的部分被有效地折叠到其所源于的节点上。举例来说，图5上所展示区250被折叠到图7中的节点400上。
将看出，每一位向量包含三列含有在考虑中的道路段的起始处的节点的身份编号的最左侧列700 ;含有在考虑中的道路段的末端处的节点的身份编号的第二列702 ;及含有所述道路段的位向量的第三列704。因此，将看出，每一道路段由两个节点识别，在道路段的每一末端处存在一个节点。
可使用任何合适的路线选择方法来确定道路段是否为最低成本路线的部分。在此特定实施例中，使用众所周知的迪科斯彻方法来探索整个网络。
然而，可通过使用各种策略来减少处理时间的量。所属领域的技术人员应了解，上文所描述的用于减小网络的技术还将减小处理时间的量。本发明的实施例可使用以下各项中的任一者或一者以上
同时计算对应于一区的 所有位向量条目。在反向图中，针对每一边界节点得出最短路径树。此方法为有利的，因为可并行处理每一区，藉此减少处理时间。
·减少对类似最短路径子树的重新计算。
·不重新计算已经产生的位向量。
因此，总之，一个实施例可执行以下操作以便产生位向量
准备步骤
I.如所属领域的技术人员将了解，经由电子地图的搜索可由有向非循环图(DAG) 表示。此图及伴随数据结构(转弯成本及长扩展表)为反向的。
2.收缩关于最精细等级的简单道路段(即，将端节点一者折叠到另一者上，如别处所论述)。如果道路段由次数=2的一个或一个以上节点组成(所有节点均位于给定等级的同一区中)，且可导航段具有相同属性例如“是轮渡”、“禁止通行”及“禁止驾驶”，那么所述道路段被称为简单的。
3.对于每一区，视头(即，来自_节点)及/或尾(即，去往_节点)节点是否属于所述区而定，将道路网络的道路段分类成三组出端口、入端口及内部道路段。即，如果头与尾两者在同一区内，那么道路段被称为内部道路段；如果头在区内但尾不在区内，那么道路段被称为出端口道路段；且如果尾在区中但头不在区中，那么道路段被称为入端口道路段。
4.对离开禁止通行及禁止驾驶区域的所有道路段设立特殊转弯限制。
预处理例程以从下到上方式进行，以最精细分割等级-即，在正描述的实施例中以等级2开始。在每一等级的区处，针对每一区R重复以下步骤
I.确定R的探索区域。在最高等级(例如，正描述的实施例中的区O)，其为整个图，在较精细等级，其为由R的可见度区域限制的子图(如上文所描述)。
因此，在中间等级(S卩，等级I)处，仅针对等级O区的含有所述等级I区的可见度区域执行以下步骤。在等级O(应记住，其用于长程路线选择)处，考虑整个图的道路段。
收集可见度区域的入端口道路段，S卩，从区域外部的节点通向所述区域内的道路段。接着收集边境道路段，即，在入端口道路段之后的道路段。如果头(LI)=尾(L 2)且不禁止从LI到L2中的转弯，那么将道路段L2称为在LI之后(及LI在L2之前)。为了找到边境道路段，将复杂十字路口收缩成单一节点。具有“禁止驾驶”属性的轮渡道路段及道路段不被视为边境道路段。
以此方式收集入端口道路段可减少(可能显著减少)在下文中所描述的探索步骤中所需的处理量。探索步骤可减少对图的探索而考虑那些到给定区的包括入端口路线的路线。
2.对于R的每一出端口道路段来说，找出根道路段及探索步骤的数目。如果出端口道路段为其位于R内的前任者(predecessor)中的至少一者的唯一后继者，那么此出端口道路段为仅有的根道路段，且执行单个探索步骤。否则，如果出端口道路段为双向的(即，可在两个方向上行驶)，那么将所述道路段自身及其相反(入端口)道路段取作单个探索步骤的根道路段。否则，如果出端口道路段为单向的，那么将每一前置的内部道路段 (且如果存在，其相反道路段)取作用于单独探索步骤的根道路段。最后，不管出端口道路段的种类是什么，对于穿过出端口道路段的每一交通扩展路径，将所述扩展的开始道路段 (如果其位于R内)取作用于单独探索步骤的根道路段。
在较精细等级(即，除了等级O之外的所有等级)上，特殊对待出端口轮渡道路段。如上文所提到，在确定区的邻域时，忽略轮渡道路段。如果轮渡道路段的头部区不属于 R的可见度区域，那么将执行单个探索步骤，其中轮渡道路段为唯一根道路段，且探索区域被约束到头部区自身。
3.执行经调度的探索步骤(下文中所描述)。
4.追溯从探索区域内的道路段到根道路段的最短路径。在除了最高等级(即，等级O)之外的所有等级处，相应跟踪起始于的道路段的排序会影响结果。假设R为等级L区 (其中L > O)，那么首先处理等级(L-I)区的出端口道路段，接着处理等级L处的剩余出端口道路段，并依此处理到最精细等级；相对于最精细等级来说为内部(且尚未被移除)的道路段被最后处理。每当遇到已在较早跟踪中到访过的道路段时，都没有必要再次沿着所述路径前进。在跟踪的同时，为每一到访过的道路段设定适当的目标位向量。在除了最高等级(即，等级O)之外的所有等级处，进行额外动作
在路径已初次横穿某等级L区边界之后，用运输道路段旗标来标记所述边界道路段及去往根道路段的所有其它道路段；
用U形转弯旗标来标记最短路径进行U形转弯的节点。
最后，在除了最精细等级外的所有等级处，填充相关矩阵条目。
在处理所述级的所有区之后，针对下一等级而简化所述图。首先，移除未标记为运输道路段的所有道路段。接着，收缩积累的新的简单路径；保留被标记为U形转弯节点的节
最后，根据相关矩阵将位向量传播到在处理此等级之前移除的道路段。
相关矩阵
本发明的一些实施例使用相关矩阵，其存储对道路段设定位向量所需的目标区之间的关系。在除了最精细等级之外的每一等级L处，产生且使用新的相关矩阵。在等级L 处，矩阵的行按等级(L+1)区编索引，列按等级L区编索引，且每一矩阵条目为零或零个以上等级(L+1)区的集合。在较低等级处，大多数矩阵条目等于空集，即，矩阵为稀疏的。
相关矩阵的目的是为了帮助对已在较早阶段删除的道路段设定位向量。这些道路段未包含于由等级L探索步骤导致的有向非循环图中，但如果其尚未被删除，那么其将包含于有向非循环图中。更精确地说，相关矩阵用以对在S的探索区域中的道路段(在> L(其中L不为最精细等级)的某等级的计算期间，其已被删除)上的某等级L区S设定位向量。对于包含于S的探索区域中的等级(L+1)区R，矩阵元素M[R，S]将最终为在R的可见度区域的边界处的等级(L+1)区的集合，使得从S到R的所有最短路径(在反向图中) 均穿过所述区中的一者。
当创建矩阵时，将所有条目初始化成空集。接着，对于所有等级L区S，执行以下两个动作。21
I.矩阵创建对于根道路段I在S及所得有向非循环图D中或上的每一探索步骤， 针对包含于S的探索区域中的每一等级(L+1)区R，及针对R的每一入端口道路段Γ，将矩阵元素M[R，S]更新如下
用A表示R的探索区域(如较早针对等级L+1而计算)。在D中从Γ追溯路径到 I且检查其是否离开A :如果此路径上的道路段从等级(L+1)区T转到等级(L+1)区T'(其中T仍包含于A中，但Iw未包含于A中)，那么将T添加到集合M [R，S]，且处理下一 Γ。
2.读取矩阵对于S的探索区域中的已在等级L计算开始之前被删除的每一道路段，令R为所述道路段结束于的等级(L+1)区(再一次，相对于反向图来说)。现在将在所述道路段上的区S的位向量位设定成区T的位向量位的逻辑“或”，其中T包括M[R，S]的所有元素。
注意，将已在较早等级处直接根据某有向非循环图或按照涉及某较低等级处的相关矩阵的类似程序设定每一 T的位向量位。
探索
探索步骤由创建以给定道路段(对)为根的最小成本路径的有向非循环图组成。 此是通过使用用于最小成本计算的众所周知的迪科斯彻方法的变化形式来实现。可自由选择要最小化的目标函数，例如，行进时间或估计燃料消耗，或别处所论述的其它因素中的任一因素。
一个实施例使用行进时间、路径长度及抑制不当转弯及机动的其它惩罚项的加权总和。
对经典(迪科斯彻)方法作出以下修改
I.其对道路段图起作用，S卩，正到访、放松等等的项目为道路段，而非节点。此有用于允许所述方法考虑到转弯限制及/或交通扩展。
2.标签中的目标函数为在根道路段的针对到达时隙的固定集合的两个一组(行进时间、成本)的向量。选择时隙以使得覆盖所有相关交通模式(自由流动、工作日早晨高峰时间、傍晚高峰时间，等等)。在下文关于评估多个时间段时的成本的论述中进一步详述此内容。
3.可针对给定道路段存储一个以上标签。如果两个标签上的待决(未完成的) 交通扩展的集合不相等，那么所述标签自身被称为独立的且两者均在随后道路段上不断传播。否则，如果不同到达时隙的成本函数值之间的关系不交替(即，一个标签明显比另一标签好)，那么丢弃较差标签。否则，通过合并每一时隙的较好值而产生新标签，将其代替原始标签来传播。经合并标签的前任者集合于是为原始标签的前任者集合的联合。
4.在每一双向道路段上产生特殊U形转弯标签。所述标签编码在两个方向上开始真实(非反向)路线的可能性。不传播U形转弯标签，且不可将U形转弯标签与一般标签合并。然而，U形转弯标签影响设定位向量时的回溯阶段仅在开始标签不比同一道路段上的U形转弯标签差时，最短路径才被加上旗标。
在较精细等级处(其中将探索区域限于区的集合)，永久地监看如上文所界定的边境道路段。一旦搜索前端到达所有边境道路段，就根据每时隙的最大(=最差)成本函数值创建监看梳(watch comb)。接着,在探索区域外部的道路段上的标签在弹离堆积时,仅在所述标签在至少一个时隙中的成本函数值低于当前监看梳的情况下被传播。如果探索区域伸展越过若干岛屿，那么针对每一岛屿维持单独的监看梳。
时变函数
本发明的一些实施例可计算展示在多个时间段而不是在单个时间处跨越网络的最小成本路径的位向量。所属领域的技术人员将了解，穿过道路网络的最低成本路线可归因于交通密度等等的影响而随着时间变化。因此，对于任一节点，可能存在两个或两个以上最小成本路径，每一最小成本路径是针对不同时间。在此实施例中，不以关于何时最小成本路径可适用的时间基准来译码位向量。位向量仅被设定成将可导航段识别为是最小成本路径的部分或不是最小成本路径的部分。因此，当使用最小成本数据进行路线选择时，路线选择算法将必须考虑来自节点的所有可能的最小成本路径。现在借助于图IOa简要描述此过程。
在网络的标准迪科斯彻探索中，当探索网络时，所述方法使用为了到达网络中的所述点迄今所发生的总成本加上尚待发生的预期成本。
因此，一些实施例利用函数而非离散值来作出在每一节点处的成本评估。因此，在图IOa中，图751的正被探索的每一节点(例如，750)具有与之相关联的成本函数，其识别正探索的参数(例如，时间、花费的燃料或其类似者)如何随着时间而变化。
成本函数可与道路段而非节点相关联。
所述方法接着处理花费的成本以通过将当前节点处的函数与迄今已累积的成本求和来添加估计成本以产生新函数。图IOa中所展示的实例在752处展示已在节点750处通过搜索方法产生的成本函数，且展示行进时间(y轴)如何随着出发时间(X轴)而变化。 将看出，成本函数归因于早晨及傍晚高峰时间而在点754及756处增加。
在一个特定实施例中，以5分钟间隔存储成本函数(例如，道路段上的平均速度)； 即，其为具有5分钟的时间周期的经量化函数而非连续变化的函数。
如果道路段针对任何成本函数在任何时间段均为最低成本路线(最小成本路径) 的部分，那么设定所述道路段的位向量。
将核心数据投射到整个网络
上文描述了如何减少地图中所含有的网络以便减少必须由分割方法考虑的道路段及节点的数目。然而，还应进一步考虑在减少步骤中被删除的节点，以便路线选择方法仍可产生去往或来自被删除的道路段及节点的路线。
因而，将被删除的节点及道路段指派到与在核心网络中其所连接到的节点相同的区。
压缩
如所论述，所产生的位向量的大小为非常大的，且因此需要压缩信息。本发明的实施例可以不同方式执行此压缩。然而，一个实施例利用各种技术来压缩、聚结位向量及/或使位向量相关，接着是对所述位向量的后续霍夫曼编码。
因此，一些实施例可试图并确保存在位向量的不均匀分布，因为这可有助于确保霍夫曼编码比在其它情况下更有效率。
举例来说，如果位向量分布如下
00000____ (49%的时间)
11111____ (49%的时间)
··· (2 % 的时间)
那么可能需要在霍夫曼编码之前操控位向量以具有更不均匀的分布，例如
00000. ... (79 % 的时间)
11111____ (19%的时间)
··· (2 % 的时间)
减少所产生的位向量
为了减少需要产生的位向量的量，本发明的实施例可使用以下策略中的任一者或一者以上
并非针对所有节点使用区ID，而使仅针对可导航节点产生区ID (例如，忽略对应于铁路的节点)。
并非所有道路段均需要位向量，且位向量可用于决策节点周围的决策道路段。可通过查看道路段数据来确定决策节点及决策道路段(如本文献中所描述)。
尽管存在许多可能的位向量，但一些位向量远比其它位向量频繁，所以特殊编码可用于最频繁的位向量(例如，000. ..000及111... 111)。
并非000. ..000或111... 111的位向量的大多数位仍常常设定成1，或设定成O。所以部分块的霍夫曼码应相当高效地编码所述位向量。
·在彼此接近的节点中，位向量常常相同，所以增量(delta)编码可高效地编码所述位向量。
可通过按源区将目的地区ID重新排序来使不同区具有更类似的位向量模式(想法描述于本文献中)。
·或者节点的道路段周围的所有位向量应总是给出111... 111。这适当地可用以更高效地编码位向量。
下文中进一步详细论述这些情况中的一些情况。
这里值得注意的是，本文中所描述的技术旨在减小位向量的大小。然而，应注意， 出于路线选择的目的使用地图数据的装置需要对数据的随机存取。通常，对数据的高效编码需要可变大�。欢饨柚苟允莸乃婊嫒�。
因而，本发明的实施例可使用一种折衷，其中数据被编码为一系列加索引的页，且接着利用所述页内的可变编码。在此些实施例中，可实现对每一页的随机存取(经由索引)。一旦一页已被存�。敲词凳├伤婧蠼饴胝鲆�。这提供效率与地图大小之间的折衷-增加每页的节点的数目会减小地图大�。故荽嫒”渎�。本发明的一个特定实施例使用每页16个节点。将了解，任何一个节点还可具有离开所述节点的不同数目或道路段。因而，即使可能存在相同数目个节点，每页仍可存在可变量的道路段。另外，对于存储在每一页上的位向量中的每一者，还可发生不同压缩。
此结构可导致如图11中所展示的地图格式。在此图中，对Arp旗标的参考与位向量同义。将数字“η”存储在标头内，且可针对不同地图变更所述数字“n”，以便优化所述地图的性能。
调谐“η”为在地图大小与在解码地图数据时的存取速度之间的折衷
·大的η值将把许多节点分组在一起，这对于地图压缩有益，但对于对数据的随机存取的速度不利。
·小的η值将把少数节点分组在一起，这对于对数据的随机存取的速度有益，但对于地图压缩不利。
·可将“η”设定成(例如)4，S卩，16个始发节点(始发节点在道路段的开始端处_即，图10的列700)的页，但应记�。恳皇挤⒔诘憔哂腥舾筛龅酱锏缆范� (to-roadsegment),所以在假定平均有3个到达道路段的情况下，每一者意味着每一页的存储量相当于约48个道路段。
在此格式中，取决于经编码的区的等级，数据具有不同格式。图12展示等级0(SP， 最粗略区)的格式的实例，且图12展示其它等级的区的实例格式。
位向量及相关信息存储在数据结构中，在图11中展示所述数据结构的格式，所述格式包含以下各项标头800 ;用于稍后描述的霍夫曼编码中的霍夫曼树802 ;每一层级中的区计数804(在每等级具有恒定数目个区的情况下为空的)；区邻居806 (在无区邻居的情况下为空的)；区ID重新映射表808 ;位向量页索引(2n个节点)810 ;及区ID与位向量 812。可将保持位向量的数据结构保持于单个文件内，或可将其保持于多个文件内。
在一些实施例中，地图标头800经布置成含有指示以下各项的进一步信息
等级的最大数目
·最短邻居列表的长度。
·最长邻居列表的长度。
·含有所有邻居列表的区段的字节偏移。
保持信息的文件或每一文件可具有用以编码邻居列表的区段。首先编码所有列表的大小。相对于最短列表长度、在由BitsRequired(所需位)(最长列表长度-最短列表长度(longestListLength-shortestListLength))确定的固定数目个位上编码每一列表长度。注意，如果所有列表具有相同长度，那么不需要位来编码所述长度。
接着编码所有列表的内容。每一列表由邻居区ID的若干元组构成等级O处的对、等级2处的3元素元组，等等。
注意，不编码始发区元组(ASCII文件中的在“”之前的部分)。其为隐含的，因为所有区的列表以递升次序存储。举例来说，如果地图具有100X10X5的3个等级(等级 O处的100个区、等级I处的10个区、等级2处的5个区)，那么
在等级O处，存储始发区1、2、3、... UOO的列表(以此次序的100个列表)。这些列表中的每一者含有若干对。
·在等级 I 处，存储始发区 I. 1、1. 2,1. 3、···、1· 10,2. 1,2. 2、···、2· 10,3. I、· · ·、100. 9、100. 10的列表(以此次序的1000个列表)。这些列表中的每一者含有3元素元组。
·在等级2处不存储任何东西，因为其为最后等级，所以不存在邻居。
将元组中的每一组成部分存储为η位。根据处于对应等级的区的数目确定每一等级的位的数目。所以，有可能随机存取列表。在3个等级100X10X5的情况下，编码元组 a. b. c将针对a使用7个位(因为在等级O处存在100个区)，针对b使用4个位(因为在等级I处存在10个区)，且针对c使用3个位(因为在等级2处存在5个区)。
实例假定100 X 10 X 5个区有如下分割粗略等级O处的100个区、中间等级I处的10个区，及详细等级2处的5个区。
在等级O处的文件中，含有邻居列表的区段将含有
指示处于等级O的100个区的列表的长度的100个数目。根据BitsRequired (所 需位)(longestListLength-shortestListLength(最长列表长度-最短列表长度))计算 位的数目。每一数目是相对于所述级处的最短列表(最短列表存储在标头中)。 接着为100个列表的内容(100对)。在7个位上编码每一对的第一元素(因为 在等级O处存在100个区)，且在4个位上编码每一对的第二元素(因为在等级I处存在 10个区)。在等级I处的文件中，含有邻居列表的区段将含有· · 100X10 = 1000个数目，其指示等级I处的1000个区的列表的长度。· ·接着为1000个列表的内容(1000个3元素元组)。在7个位上编码每一元组 的第一元素(因为在等级O处存在100个区)，在4个位上编码每一元组的第二元素(因为 在每一等级O区中存在10个等级I区)，且在3个位上编码每一元组的第三元素(因为在 每一等级I区中存在5个等级2区)。在等级2处的文件中，不需要存储任何内容，因为其为最后等级。对于编码器输入文件，可米用任一形式的列表。因此，一旦已执行分割为三个等级，就将每一节点指派给每等级一个区；即三个 区。标头800通常，用于本发明的实施例中的标头为较小的，且因而，不需要为了减小其大小而 使所述大小优化。通常，为了方便起见，全部内容均为字节对准或字对准的· (4个字节)编码版本(每次地图格式改变时会增加)· (4个字节)地图旗标(用以开启或关闭特征，最初为0，但以后在需要添加任选 特征的情况下可被使用)· (4个字节)地图中的节点的总数目· (4个字节)地图中的道路段的总数目· (4个字节)区段霍夫曼树的字节偏移· (4个字节)区段区二进制大型对象(blob)的字节偏移· (4个字节)区段区页信息的字节偏移· (4个字节)区段位向量页信息的字节偏移· (4个字节)区段可变大小记录的字节偏移*(4个字节)最大位向量(arp旗标)页(以位计)(可由路线规划方法用以在启 动时预分配位流解码器的较坏情况)· (4个字节)平均位向量(arp旗标)页大小(以位计)(用以内插位向量页位 置)· (4个字节)最小位向量(arp旗标)页增量(用以使得所有增量> =0，从而避 免存储位正负号)· (2个字节)位向量(arp旗标)历史的最大大小(可由路线规划方法用以在启 动时预分配历史缓冲器)· (2个字节)每页的道路段的最大数目(当前未使用)· (I个字节)此文件的阿波罗(Apollo)等级
· (I个字节)每位向量(arp旗标)的位
· (I个字节)每位向量(arp旗标)页增量的位(位向量(arp旗标)页的固定大小记录中的字段)
· (I个字节)每二进制大型对象索引的位(区页信息的固定大小记录中的字段)
· (I个字节)每区计数的位(区页信息的固定大小记录中的字段)
· (I个字节)每非平凡(trivial)位向量(arp旗标)块的位
· (I个字节)区节点页大小的log_2()
· (I个字节)位向量(arp旗标)页大小的log_2()
· (I个字节)用以编码本地区ID的霍夫曼树的数目
· (I个字节)用以编码位向量(arp旗标)历史代码的霍夫曼树的数目
霍夫曼树802
用来编码在每一节点周围的道路段的数目的霍夫曼树极小的，仅大约10个码， 仅存在于等级O处的文件中)
·用来存储非平凡位向量(arp旗标)的块的霍夫曼树最大霍夫曼树，对于压缩来说，越大越好，但在路线规划方法中所需的存储器越多(在地图压缩与路线规划方法中的存储器使用之间的折衷)。
·当历史大小为O时位向量(arp旗标)增量码的霍夫曼树极小的，仅3个码
·当历史大小为I时位向量(arp旗标)增量码的霍夫曼树极小的，仅4个码
·当历史大小>=η时位向量(arp旗标)增量码的霍夫曼树极小的(存储在标头中的霍夫曼树的数目)
·当在区页中存在3个区时区ID的霍夫曼树极小的，仅3个码
·当在区页中存在4个区时区ID的霍夫曼树极小的，仅4个码
·当在区页中存在>=η个区时区ID的霍夫曼树极小的(存储在标头中的霍夫曼树的数目)。
区重新映射表804及区ID列表806
虽然区ID 806比图11的文件格式的其它部分�。箍裳顾跚鳬D 806，如图14 中示范。其中，可使用地理相关以便减少所使用的数据量。
每一区页在所述区页中存储相异区的列表。在大多数情况下预期此列表为较小的 (事实上，许多页很可能仅含有I个至少在等级O的区)。区的列表具有可变大小。应可随机地存取页内的数据(即，随机存取)且因而，使用固定表大小以允许此情况。
将相异区的每一列表按每一区中的节点的频率排序列表的第一兀素对应于所述页中具有最大数目个节点的区，列表的最后元素为所述页中具有最小数目个节点的区。
对于区页中的每一节点，可使用本地区ID (对页来说为本地的)来编码其区ID。 此本地ID为页中的区的索引(其为较小的整数，常常为0，因为O对应于区页中的最普遍的区)。
将节点的区ID存储如下
含有区ID的区阵列存储页中的区的所有可能的重叠列表。区的列表为所述阵列中的连续区ID。列表可(且确实)重叠。所述阵列不存储每一列表的开始及结束(此由区页信息表进行)。
区页信息表为固定大小的记录表(因此可随机存取)，且每一记录含有在列表的开始的阵列中的索引+所述列表中的项目的数目。
·每一节点含有本地节点ID (相对于其页来说为本地的)。
在下文中进一步界定这些概念中的每一者。
区阵列
区阵列编码页的所有可能的区列表。区阵列为区ID的简单阵列，其中区ID的列表可重叠。区阵列的大小应为较小的，因为列表重叠。在区段区页信息中进一步描述所述区阵列。
区页信息
使用区页信息表的固定大小记录中的2个字段指定区页表中的区ID的列表
·区计数(此页中的区的数目，预期为较小的)。
·向区列表的阵列中的偏移(区的列表开始之处)。
在一个实施例中，此在图12中描述。
偏移字段指向区阵列中(例如)在假定在每一等级中总是存在小于256个区的情况下(其为合理假定)，每区ID具有I字节的固定大小记录是足够的(但如果每等级256 个位被认为太有限制性，那么使得每个区ID大于8个位为易于实现的)。区页表记录中的区计数指示在指定偏移处在阵列中有多少区要被考虑。
如果若干区具有相同列表，那么其可指向相同所在地，其应为紧凑的，因为可预期许多页共享相同列表或共享所述相同列表的部分。
参考图12来更详细解释此，图12展示具有2~nr个节点((例如)nr = 9以将512 个节点分组在一起)的页的实施例。
注意区ID的阵列900紧凑的程度，因为若干页可指向阵列中的同一所在地或重叠的所在地(图中所标记的区二进制大型对象)。事实上，增加页的数目可能不增加阵列的大�。蛭恳灰辰幼旁诮仙俚那现氐宰楹系目赡苄约跣�。所以此阵列应允许创建许多页，而无需太多地图空间，也无需所产生的地图数据被加载于其中的装置上的过多存储器。
所述方法旨在使含有区ID的列表的阵列900尽可能地小。所述方法旨在在阵列中尽可能经常地重新使用相同的区ID列表。所述方法可自由地将列表的最后2个元素重新排序，因为其不会影响霍夫曼码的大小。
举例来说，当列表含有2个区10及34时，存储列表10、34或34、10 (与频率无关) 为等效的，因为当仅存在2个节点时，霍夫曼树在所有情况下仅使用I个位。换句话说，对于最后2个区来说，放松了根据频率排序的要求。类似地，还可将3个元素10、34、40的列表存储为10、40、34，因为仅第一个码10(最频繁的)将使用I个位，且其它码40及34均使用2个位(与次序无关)。
因此，查看图12，可看出，阵列900存储两个值长度及从区数据的开始的偏移。 因此，以第一行(3:0)为例，此指代从文件的开始偏移了 O的三条数据(即，10、34、40)。作为另一实例，阵列条目(1:2)指代单个区(即，长度为I)，其中从文件的开始的偏移为二 ； (即，区40)。
在替代实施例中，根据以下方法来编码区页信息
此区段编码每一区中的子区的数目。子区的数目可在每等级中可变。然而，每一等级的子区的数目常常为恒定的。相对于每一等级处的区的最小数目且使用log_2(max_ number_of_regions-min_number_of_region(区的最大数目-区的最小数目))个位来编码子区的数目。所以如果区的数目为恒定的，那么将O个位用以编码区计数，且此区段为空的。区的最小数目及最大数目存储在侧文件的标头中。
区邻居区段(关于图6及6a来论述邻域)的编码
此区段针对在给定等级L处的每一区层级而编码在更详细等级L+1处的区邻居的列表。举例来说，等级L= I处的区3.9可具有以下在等级L = 2处的邻居的列表:3.5. 43. 6. 33. 6. 44. 7. 14. 7. 3。如别处所论述，可使用邻居的列表来增加用以产生所述侧文件或每一侧文件的预处理的速度。
此区段被分裂成2个子区段
用以编码所有邻居列表(与在给定等级处存在的区数目一样多)的长度的子区段。相对于最短列表来编码所述长度，且接着，将位的数目计算为log_2 (length_longest_ list-length_shortest_list (最长列表长度-最短列表长度))。如果所有列表具有相同长度，那么使用O个位来编码长度(且因此，区段就为空的)。
用以编码所有邻居列表(与在给定等级处存在的区数目一样多)的子区段。
区ID重新映射表的编码
仅在等级O的侧文件中编码此区段。所述编码编码二维表，所述二维表被用以重新排序且聚结等级O处的每一区中的位(以便高效地编码位向量，在本文献中在下文进一步描述聚结及位重新排序)。进行对位向量中的位的重新排序及聚结以优化对位向量的霍夫曼编码。此表由路线规划方法用以在知晓以下各项时找到位向量中的要解码的位位置
·当前节点的始发区ID
·原始的到达位(to-bit)索引(即，在解聚结位向量位之后的位索引)
二维表的2个索引为
·始发区ID
·目的地位索引(目的地的区)
此区段由2个子区段构成
用以编码等级O处的每一区的经聚结位的数目的区段。用以编码每一数目的位数目为log_2 (max_number_of_coalesed_bits (经聚结位的最大数目))
用以编码位重新映射表的区段。因为在进行路线选择时，目的地位元不改变(在进行路线选择时目的地保持相同)，但始发区ID改变(视在进行路线选择时所探索的节点而定)，矩阵按目的地位的行进行存储。在每一行中，存储每一始发区的位重新排序数目。 路线规划方法在进行路线选择时应通常仅将对应于给定路线选择目的地的I行加载于存储器中。路线规划方法不需要将整个二维矩阵存储在存储器中。路线规划方法可随机存取所述行。将用以编码每一重新映射条目的位数目计算为log_2(经聚结位的最大数目)。
图13针对等级O区(见图9)扩展了图11中所展示的文件的位向量区段812。可看出，每一页包含道路段计数、区ID及位向量。
图14针对除了等级O之外的等级扩展了图11中所展示的文件的位向量区段812。 可看出，对于其它区来说，存储位向量，且不存储道路段计数或区ID (针对等级O存储道路段计数或区ID)。
鉴于由每一等级的区覆盖的区域的差别，在每等级中每页的节点的数目可变化。 举例来说，由于等级O内的区覆盖较大的区域，因此对于等级0，每区每页可能存在较多节点。举例来说，对于等级0，一些实施例每区每页可存储512个节点。因而，更详细等级可具有较小数目个节点_例如，256个节点、128个节点、64个节点、32个节点、16个节点或其类似者。实际上，某实施例可利用每页1024个节点、2048个节点或4096个节点。
位向量810、812的编码
表810含有固定大小的记录。始发节点ID被一起分组于具有2n个的页中。
将数据分组于具有多个连续节点的页中是方便的，因为预期位向量对于相同邻域中的若干道路段具有类似模式。通过使用页，有可能以增量编码若干道路段且实现良好压缩。类似地，有可能以增量将节点的区ID编码于页中。另一方面，这意味着存取一个道路段的数据需要将若干道路段的数据解封装(无直接随机存取)。可将必须将若干节点或道路段解封装以存取一个道路段或节点的数据认为是可接受的，因为
数据可被高速缓存，所以在存取一个道路段时读取的额外数据常常并非无用的。 可能为以下情况此额外数据不久之后将为有用的(这类似于磁盘高速缓存的预先读取 (read-ahead)参数)。
·当与迪科斯彻A*路线选择比较时，使用所述位向量的路线选择将扩展搜索的大小减小了一数量级。通过按页分组数据，仅地图的小部分仍需要解码(沿着实际路径的页)。
·归功于对区ID及位向量的增量压缩，其应显著减小经编码的数据大小。
·页减小索引的大小，因为如所描述，数据将存储在侧文件中。
表810内的每一记录含有一“增量”字段，其用以找出每一页的可变大小的开始的位置(相对于经内插位置的增量)。针对每一增量的位的数目存储在标头中。
为了存取区ID及位向量812，解码器可通过进行以下线性内插而计算开始页的估计偏移
interpolated_offset (经内插一偏移)=from_node_id*avg_page_size (始发节点id*平均页大小)
其中avg_page_size为存储在标头中的以位计的平均页大小(可能在固定点中以改进精确性)。可接着将数据的偏移计算如下
偏移=interpolated_offset+min_delta+delta(经内插一偏移+ 最小一增量 + 增量)
其中min_delta为所有页的所有增量字段的最小值(存储在标头中)，且增量为存储在页中的无正负号字段。min_delta值确保所有增量字段为正值(不存储位正负号)。
经由先前所描述的位向量页信息的“增量”字段来存取可变大小的记录。
每一记录含有2n个节点的数据(始发节点的区ID及其在所有等级处的所附接道路段的位向量)。同一编索引方案因此将被用于所有等级。
可变大小记录存储
·页码-针对整个页指示所述页内的节点是否为同一区的部分的码；
在位向量页中的每一节点周围的道路段的数目(仅在等级O处存储，因为其对于所有等级将为相同的)；
·页中的始发节点的区ID，每等级有一个ID(针对所有等级的信息存储在等级O 处的文件中{{ap_0_*. dat)
·仅等级i处的在页中的节点周围(仅在具有> 2个所附接道路段的节点周围) 的道路段的位向量。此为数据的最大部分。
·在每一节点周围的道路段的数目的编码
对于位向量页中的2n个节点中的每一者来说，霍夫曼码编码在所述节点周围的道路段的数目。此信息并非具体到所有等级，且其仅存储在等级O处的文件中(ap_0_*. dat)。
知晓在节点周围的道路段的数目是用以解码位向量(见1000，图13)。此信息与已经存在于其它文件中的信息重复，但其使得更容易且快速地解码页中的位向量，而无须在别处查找所述信息；藉此大小方面的小增加提供性能的增加。
可变大小记录中的区ID的编码
在编码每一节点周围的道路段的数目1000(见编码布局)之后，即刻在可变大小记录中编码节点的区ID 1002。为了执行使用在预处理中产生的位向量的路线选择，通常需要存取给定节点的所有等级处的区ID 1002，所有等级的区ID被彼此靠近地存储在同一文件中，而不是被分裂于每等级的不同文件中。
具有2n个节点(例如，η = 4)且具有3个阿波罗等级的位向量页因此将把节点ID 存储如下
节点#0 ；:本地_区__id_等级_O本地_区__id_等级_.1本地_区__id_等级
节点#1 :本地_区__id_等级_O本地_区__id_等级_.1本地_区__id_等级
节点#2 ；:本地_区__id_等级_O本地_区__id_等级_.1本地_区__id_等级
节点#15:本地-区_id_等级_0本地-区_id_等级_1本地-区_id_等§
另外
·在具有I或2个所附接道路段的节点周围，不编码任何东西(即，对于存储O作为所附接道路段的数目的节点来说)。
·当在给定等级设定了页码中的位时，则知晓所有节点均处于所述级处的相同区 ID中，且接着仅将所述级处的区ID编码一次(对于具有>=3个所附接道路段的第一节点)。用来编码区ID的位的数目为log_2 (regionCount-1 (区计数-I))。
·除了页中的区ID经编码的第一节点之外，在编码每一区ID之前还编码一位。此位指示区ID是否与处于同一等级的先前经编码的节点ID相同。当此位被设定时，无需编码所述区ID，因为其与所述级处的先前所编码者相同。当此位为O时，以 log_2 (regionCount-1)个位编码区ID。由于许多连续节点在同一区中，因此常常仅需要I 个位来编码区ID。
对本地区索引的霍夫曼编码为高效的，因为
在每一区页中按频率将区分类(所以本地索引O比本地索引I更频繁，...)
·对于页中的每一数目个区存在相异的专门的霍夫曼树(对于页中的3个区存在 I个霍夫曼，对于页中的4个区存在I个霍夫曼树，等等)。霍夫曼树为较小的，且因而有可能在不使用大量存储器的情况下存储若干个霍夫曼树。
·无论如何，至少在等级O处，具有3个区或3个区以上应为相当罕见的(但在其它等级处并不罕见)。
可变大小记录中的位向量的编码
每一可变大小记录含有在页中的页周围的所有道路段的位向量。仅在具有3个或 3个以上所附接道路段(道路段)的节点周围编码位向量。对于具有I个或2个所附接道路段的节点来说，路线选择方法可将位向量值111. .. 111)隐含地赋予所述节点。
不编码到达节点。
参看图10，应注意，可由两个节点指定一道路段；在所述道路段的每一末端处有一个节点。因此，当考虑方向时，在方向的开始处的节点可被称作from_node (始发节点)， 且在末端处的节点可被称作to_node(去往节点)。
在编码内使用关于位向量的各种性质以使得编码有效率
·所述位向量中的许多位向量为000. . . 000或111. . . 111。
对于位向量的其它值(即，非000. . . 000或111. . . 111)，很可能存在重复且相同值将很可能被重复。
·并且，给定节点周围的所有位向量的“或”应为111... 111。
将位向量编码为第一霍夫曼码及任选的其它霍夫曼码。第一霍夫曼码指示位向量是否为
·针对平凡位向量000. . . 000的码O
·针对平凡位向量111. .. 111的码I
码2，或用以指示在所述页中尚未遇到非平凡位向量。在此情况下且仅在此情况下，后接有其它霍夫曼码以编码新遇到的位向量。
·当位向量与在当前页中先前遇到的位向量相同时(忽略平凡位向量000. . . 000 及111... 111)，码>=2。此编码因此使用所述页中先前遇到的码的历史。所述码因而实际上按所有先前遇到的码的历史给出索引。
不同于此霍夫曼码，仅在于历史中未找到非平凡位向量的情况下，需要编码更多信息(码=2)。在此情况下，紧接在霍夫曼码==2之后，编码
·否定位
用以通过N个位的块编码η个区的位向量的若干霍夫曼码(N及η给出于地图标头中)。举例来说，使用11个位的块编码100个区(99位位向量)需要编码9个霍夫曼码 (9X11 = 99)。
由于大多数位向量主要含有O或含有1，因此否定位指示所述位向量是否被存储为否定的。这使得能够在霍夫曼树中存储决大多数含有O的码(因此，改进块的霍夫曼编码)。仅在块的大小小于区的数目的情况下存在否定位，此为实际上在等级O处的情况，但在等级I或2处，可能在仅I个块中编码整个位向量，所以否定位为不需要的。
如果存在100个区；Ν = 100 (因此，99位的位向量)，那么第一块编码针对目的地区I到11的位，第二块编码区12到22，等等。在第一块中，LSB(Oxl)对应于目的地区1， 下一位(0x2)对应于区2，下一位(0x4)对应于区3，等等。
对于使用历史的位向量来说，历史阵列的深度为页中的先前遇到的相异位向量的数目(不考虑平凡位向量000. .. 000及111. .. 111)。不管历史向量含有O个元素、I个元素、2个元素、3个元素等等，使用不同霍夫曼树。使所述霍夫曼树倍增为可接受的，因为所32有霍夫曼树均较小，且因而不需要相当大的存储装置
·当历史具有O个元素时，霍夫曼树具有3个码针对000. ..000的O、针对 111. . . 111的I、针对新位向量的2。
·当历史具有I个元素时，霍夫曼树具有4个码针对000. . .000的O、针对 111... 111的I、针对新位向量的2、针对与历史中的元素#0相同的位向量的3。
·当历史具有2个元素时，霍夫曼树具有5个码针对000. ..000的O、针对111... 111的I、针对新位向量的2、针对与历史中的元素#0相同的位向量的3、针对与历史中的元素#1相同的位向量的4。
·等等。
预期位向量页的大小较小(例如，2n个始发节点)，所以预期霍夫曼树的数目较小。
然而，有可能将霍夫曼树的大小限于最大值例如，每当历史含有H以上个元素时，就将使用单个霍夫曼树(值H存储在地图标头中)。
此编码仅编码每一页中的相异位向量+ —些码。
在较大的索引页的情况下，所述编码在大小上较有效率，但代价是为了使用位向量来进行路线选择目的而减慢了解码(页中有更多位向量要解码)。
统计数据
此处为在按254个区(I等级)编码比荷卢经济联盟(Benelux)时的文件格式的详细统计数据。使用以下输入参数
每位向量块的位数目11
每位向量页的节点数目2~4 = 16
每区页的节点数目2~9 = 512
提供统计数据以在地图大小方面给出地图形式的概念，且基于一些实际数据说明地图格式的描述
—全局统计计数器
节点计数.......................................................1598632
线路计数.......................................................1598632(100. 000% )
跳过具有I条线路的节点周围的线路.........220180(13. 773% )
跳过具有2条线路的节点周围的线路.........727138(45. 485% )
—等级=[O]处的统计数据
地图计数器......................................................87437736(100.000% )
经编码平凡arp 旗标 000. . . 000..................... 1310914(31. 651% )
经编码平凡arp 旗标 111. ·· 111...................... 913348(22. 052% )
历史中的经编码arp旗标............................362432(8. 751% )
不在历史中的经编码arp旗标...................607717(14. 673% )
否定块...................................................235171 (5. 678%)
地图大小(以位计)..................................87437736(100. 000% )
全局标头...................................................496(0. 001% )
霍夫曼树...................................................28808(0. 033% )
区一进制大型对象....................................52664(0. 060% )
区页信息...................................................56216(0. 064% )
arp旗标页信息...........................................2497880 (2. 857% )
可变大小记录............................................84801672(96. 985% )
节点周围的线路计数.............................2847844(3. 257% )
节点区ID.................................................2112451(2. 416% )
arp旗标...................................................79841370(91.312% )
码平凡 000. . . 000..................................1689322(1. 932% )
码平凡 111. . . 111.................................1826696(2. 089% )
在历史中找到的码...............................1668053(1. 908% )
未在历史中找到.................................74657299(85. 383% )
未在历史中找到的码......................1463183(1. 673% )
否定位...............................................607717(0. 695% )
M.....................................................72586399(83. 015% )
所有大小以位计。总地图大小为87，437，736个位(10，929，717个字节)。
缩进反映了层级。可变大小记录信息为目前为止最大的一条信息(地图大小的96. 975%;)。在可变大小记录中，子项目(缩进的)给出更多细节。位向量为目前为止可变大小记录中要存储的最大的一条信息(91.312%)。且在位向量中，存储在历史中尚未遇到的非平凡位向量构成了地图的最大部分(83.015% )。
关于霍夫曼树的统计数据
此节给出在按255个区(即，针对上文所展示的地图数据)编码比荷卢经济联盟时的霍夫曼树的统计数据。
在每一节点周围的道路段的数目的霍夫曼树[霍夫曼树Nr个线路]
权利要求
1.一种使用包含多个可导航路径的地图数据确定路线的方法，所述地图数据被划分成多个区，所述方法包含使用至少一个处理设备来接收所述地图数据上的起点及目的地及对多个成本函数中的一者的选择；使用所述地图数据及识别所述地图数据的区之间的最小成本路径的最小成本数据来确定从所述起点到所述目的地的路线，所述方法的特征在于， 如果针对所述多个成本函数中的不同成本函数在一对所述区之间存在不同最小成本路径， 那么所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含从包含所述起点及所述目的地的所述对区的所述最小成本路径中识别针对所述选定成本函数具有最低成本的所述最小成本路径。
2.根据权利要求I所述的方法，其包含致使显示器显示所述所确定路线的图像；及使所述用户能够在检视所述图像时改变所述选定成本函数；以及响应于所述选定成本函数的变化，用针对所述新选定成本函数确定的新路线的图像来更新所述显示器。
3.一种数据载体，其上存储有在由处理设备执行时致使所述处理设备执行根据权利要求I或权利要求2所述的方法的指令。
4.一种数据载体，其上存储有包含多个可导航路径的地图数据，所述地图数据被划分成多个区；及针对不同成本函数识别所述地图数据的所述区之间的最小成本路径的最小成本数据。
5.一种计算机装置，其包含其中存储有以下各项的存储器包含多个可导航路径的地图数据，所述地图数据被划分成多个区；识别所述地图数据的所述区之间的最小成本路径的最小成本数据，且处理设备经布置以接收所述地图数据上的起点及目的地及对多个成本函数中的一者的选择且使用所述地图数据及所述最小成本数据来确定从所述起点到所述目的地点的路线，所述计算机装置的特征在于，如果针对所述多个成本函数中的不同成本函数而在一对所述区之间存在不同最小成本路径，那么所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含从包含所述起点及所述目的地的所述对区的所述最小成本路径中识别针对所述选定成本函数具有最低成本的所述最小成本路径。
6.一种导航装置，其包含定位系统、显示器、用户接口及根据权利要求5所述的计算机装置，其中所述处理设备经布置以经由所述用户接口上的输入导出所述起点及所述目的地，且将所述确定的结果显示在所述显示器上。
7.根据权利要求6所述的导航装置，其中所述显示器经布置以显示所述所确定路线的图像，所述用户接口经布置以使所述用户能够在检视所述图像时改变所述选定成本函数， 且响应于所述选定成本函数的变化，所述显示器用针对所述新选定的成本函数而确定的新路线的图像进行更新。
8.一种产生跨越电子地图从起点位置到目的地位置的路线的方法，所述电子地图包含表示由所述电子地图涵盖的区域中的可导航路线的段的多个向量，所述方法包含利用提供对所述电子地图的校正的数据，其包含指示先前并非所述电子地图的部分的向量的数据；修正指示所述电子地图中的哪些向量为所述最低成本路线的部分以指示所述新向量为所述最低成本路线的部分的路线选择加速数据，以形成经修正的路线选择加速数据；及产生所述起点位置与所述目的地位置之间的路线，所述产生包括利用所述经修正的路线选择加速数据。
9.根据权利要求8所述的方法，其中从远程服务器下载对所述电子地图的所述校正。
10.一种计算机装置，其包含其中存储有电子地图的存储器，所述电子地图包含表示由所述电子地图涵盖的区域中的可导航路线的段的多个向量，且处理设备经布置以利用提供对所述电子地图的校正的数据，其包含指示先前并非所述电子地图的部分的向量的数据；修正指示所述电子地图中的哪些向量为所述最低成本路线的部分以指示所述新向量为所述最低成本路线的部分的路线选择加速数据，以形成经修正的路线选择加速数据；且产生起点位置与目的地位置之间的路线，所述产生包括利用所述经修正的路线选择加速数据。
11.一种导航装置，其包含定位系统、显示器、用户接口及根据权利要求10所述的计算机装置，其中所述处理设备经布置以经由所述用户接口上的输入接收对所述电子地图的所述校正。
全文摘要
本发明涉及一种使用包含多个可导航路径的地图数据确定路线的方法，所述地图数据被划分成多个区。所述方法包含使用至少一个处理设备来接收所述地图数据上的起点及目的地及对多个成本函数中的一者的选择；且使用所述地图数据及识别所述地图数据的区之间的最小成本路径的最小成本数据来确定从所述起点到所述目的地的路线。如果针对不同成本函数在一对所述区之间存在不同最小成本路径，那么所述最小成本数据识别所述对区之间的一个以上最小成本路径，且确定路线包含从包含所述起点及所述目的地的所述对区的所述最小成本路径中识别针对所述选定成本函数具有最低成本的所述最小成本路径。
文档编号G01C21/34GK102947676SQ201180029763
公开日2013年2月27日 申请日期2011年1月13日 优先权日2010年4月23日
发明者�？啤は�, 埃格尼·高里洛, 莫里茨·希尔格, 安德列亚斯·普洛福斯, 于尔根·韦贝尔, 亚历山德鲁·谢尔伯内斯库 申请人:通腾科技股份有限公司, 通腾发展德国公司
专业数控铣床产品供应商
20年生产经验，实力工厂，精工品质，质量有保障
