CN107003141B - 替代路线 - Google Patents

Abstract

本发明揭示一种用于在由电子地图覆盖的区中产生路线的方法。所述地图包括多个路段，所述多个路段表示由所述电子地图覆盖的所述区中的可导航网络的可导航路段。从起点到目的地的主要路线以偏向是预定义子网络的路段的路段的方式穿过所述网络而产生。当用户开始行进时，所述方法涉及识别沿着行进的所述主要路线的第一决策点，所述第一决策点是所述子网络的决策点。以涉及偏向所述子网络的路段的方法来产生介于所述决策点与所述目的地之间的替代路线，且在所述方法中，阻断行进的所述主要路线的从所述第一决策点外出的路段。

Description

替代路线

技术领域

本发明涉及用于产生替代路线的方法及系统，且还扩展到经布置以产生替代路线的导航装置及服务器。本发明还扩展到用于在可导航网络中确定由用户在决策点处采取的路线的方法及系统，且扩展到用于将关于穿过可导航网络的替代路线的信息提供给用户的方法及系统。本发明的说明性实施例涉及便携式导航装置(所谓的PND)，特定来说包含导航卫星信号接收及处理功能性的PND。更一般来说，其它实施例涉及经配置以执行导航软件以便提供(举例来说)路线计划功能性及/或导航功能性的任何类型的处理装置。

背景技术

包含GPS(全球定位系统)信号接收及处理功能性的便携式导航装置(PND)是众所周知的且广泛地用作汽车内或其它交通工具导航系统。

一般来说，现代PND包括处理器、存储器(易失性及非易失性中的至少一者，且通常为两者)及存储于所述存储器内的地图数据。处理器与存储器协作以提供其中可建立软件操作系统的执行环境，且另外提供一或多个额外软件程序来使得能够控制PND的功能性及提供各种其它功能是常见的。

通常，这些装置进一步包括允许用户与装置交互及控制所述装置的一或多个输入接口，及可借以将信息中继到用户的一或多个输出接口。输出接口的说明性实例包含视觉显示器及用于可听输出的扬声器。输入接口的说明性实例包含一或多个物理按钮，其用以控制装置的开/关操作或其它特征(所述按钮不必位于装置本身上，但其可在装置被内建到交通工具中的情况下位于方向盘上)；及麦克风，其用于检测用户话音。在特别优选布置中，可将输出接口显示器配置为触敏式显示器(借助触敏式覆层或以其它方式)以另外提供用户可借以通过触摸来操作装置的输入接口。

此类型的装置通常还将包含一或多个物理连接器接口，可借以将电力信号及(任选地)数据信号发射到所述装置及从所述装置接收电力信号及(任选地)数据信号；及(任选地)一或多个无线发射器/接收器，以允许经由蜂窝式电信以及其它信号及数据网络(举例来说，Wi-Fi、Wi-Max、GSM等等)的通信。

此类型的PND装置还包含GPS天线，可借以接收包含位置数据的卫星广播信号且随后处理所述信号以确定所述装置的当前位置。

PND装置还可包含产生信号的电子陀螺仪及加速计，所述信号可经处理以确定当前角加速度及线性加速度且反过来又连同从GPS信号导出的位置信息一起来确定所述装置的速度及相对位移并因此确定其中安装所述装置的交通工具的速度及相对位移。通常，此类特征最为普遍地提供于交通工具内导航系统中，但还可在有利的情况下提供于PND装置中。

此类PND的效用主要表现在其确定第一位置(通常是开始或当前位置)与第二位置(通常是目的地)之间的路线的能力上。可由装置的用户通过各种各样的不同方法中的任一者而输入这些位置，举例来说，通过邮政编码、街道名称及门牌号、先前存储的“众所周知的”目的地(例如，著名地点、市政场所(例如运动场或游泳池)或者其它所关注点)及受喜爱或最近参观的目的地。

通常，PND是由用于从地图数据计算开始地址位置与目的地地址位置之间的“最佳”或“最优”路线的软件实现。“最佳”或“最优”路线是基于预定准则确定，且不必是最快或最短路线。沿着其引导驾驶员的路线的选择可为非常复杂的，且所选择路线可将历史、现有及/或所预测交通及道路信息考虑在内。

另外，装置可不断监视道路及交通状况，且因状况改变而提供或选择改变行程的剩余部分欲采取的路线。正使用基于各种技术(例如，移动电话数据交换、固定相机、GPS车队跟踪)的实时交通监视系统来识别交通延迟且将信息馈送到通知系统中。

此类型的PND通常可安装于交通工具的仪表板或挡风玻璃上，但还可形成为交通工具无线电的板上计算机的部分或实际上形成为交通工具本身的控制系统的部分。导航装置还可为手持式系统的部分，例如PDA(便携式数字助理)、媒体播放器、移动电话等等，且在这些情形中，借助在装置上安装软件来扩展所述手持式系统的正常功能性以执行路线计算及沿着所计算路线的导航两者。

还可由运行适当软件的桌上型计算资源或移动计算资源来提供路线计划及导航功能性。举例来说，在routes.tomtom.com处提供在线路线计划及导航设施，所述设施允许用户输入开始点及目的地，在所述用户的PC所连接的服务器上计算路线(其各方面可由用户规定)、产生地图且产生用于将所述用户从所选择开始点引导到所选择目的地的一组详尽导航指令。所述设施还提供所计算路线的伪三维再现及路线预览功能性，所述路线预览功能性模拟用户沿着所述路线行进且借此给所述用户提供所计算路线的预览。

在PND的背景下，一旦已计算路线，用户便与导航装置交互以任选地从所建议路线列表中选择所要所计算路线。任选地，(举例来说)通过规定特定行程将避开或强制性要求某些路线、道路、位置或准则，用户可干预或引导所述路线选择过程。PND的路线计算方面形成一个主要功能，且沿着此路线的导航是另一主要功能。

在沿着所计算路线的导航期间，此类PND通常提供视觉及/或可听指令以沿着所选择路线引导用户到达所述路线的尽头(即，所要目的地)。PND还通常在导航期间于屏幕上显示地图信息，此信息在屏幕上定期更新使得所显示的地图信息表示装置的当前位置且因此在装置正用于交通工具内导航的情况下表示用户或用户的交通工具的当前位置。

屏幕上所显示的图标通常表示当前装置位置且位于中心处，其中还正显示当前装置位置附近的当前道路及周围道路的地图信息以及其它地图特征。另外，导航信息可任选地显示于所显示的地图信息的上面、下面或一侧的状态栏中，导航信息的实例包含从用户所需要采取的当前道路到下一绕行的距离，所述绕行的性质可能由暗示特定类型的绕行(举例来说，左转或右转)的另一图标表示。导航功能还确定可借以沿着路线引导用户的可听指令的内容、持续时间及计时。如可了解，例如“100m内左转”的简单指令需要显著处理及分析。如先前所提及，可通过触摸屏幕或者另外或替代地通过转向柱安装的远程控制件，通过语言激活或通过任何其它适合方法来实现用户与装置的交互。

所述装置所提供的另一重要功能是在以下情况下的自动路线重新计算：用户在导航期间从先前所计算路线偏离(意外地或有意地)；实时交通状况指示替代路线将更有利且所述装置能够适合地自动辨识此类状况，或在用户出于任何原因主动致使所述装置执行路线重新计算的情况下。

虽然路线计算及导航功能对PND的总体效用来说是基础性的，但可仅出于信息显示或“自由驾驶”的目的来使用所述装置，其中仅显示与当前装置位置有关的地图信息，且其中所述装置尚未计算任路线且当前未执行任何导航。此操作模式通常可适用于用户已知晓期望沿着其行进且无需导航帮助的路线时。

上文所描述的类型的装置提供用于使得用户能够从一个位置导航到另一位置的可靠构件。

当沿着路线进行导航或计划路线时，可通过导航装置或具有路线产生功能性的其它系统来向用户呈现起点与目的地之间的替代路线。此给用户提供决定其出于某一原因而偏好若干个可能路线中的哪一者的机会，而不是仅给用户提供关于时间、距离或另一准则(例如燃料经济性)最优的单一路线。这些路线通常将并非关于给定准则(例如，时间)最优的，但可能是用户出于另一原因而偏好的，例如，因为其避开用户不喜欢的特定道路交叉点或伸展、风景更优美等。

产生及选择为用户可能希望使用的明智路线的替代路线提出一些挑战。将了解，理论上可提供与第一(例如，最快)路线在某一方面不同的众多路线。特定来说，为提供更可能有助于用户的更有用替代路线，替代路线与第一(例如，最快)路线在适当程度上不同是合意的。

用于产生起点与目的地之间的对主要路线的替代方案的一些现有技术已涉及阻断主要路线的中心部分，使得在用于产生替代路线的路线计划过程中可不将形成路线的此部分的路段考虑在内。然而，以此方式防止主要路线与替代路线的显著部分之间的重叠可迫使替代路线从主要路线显著地偏离，且包含不适当绕路。在图6中展示一组此类替代路线的实例。

已提出特定技术来尝试确保所产生的替代路线为明智的(即，用户友好替代方案)，例如通过考虑可准许重叠的程度等。已开发一些此类技术作为由欧洲委员会(European Commission)资助的标题为“针对移动用户的环境友好型城市多模式路线计划服务(eCO-friendly urban Multi-modal route PlAnning Services for mobileuSers)”的项目或电子罗盘(eCOMPASS)的部分，且(举例来说)根据可在http:// www.ecompass-project.eu/sites/default/files/eCOMPASS-Deliverable-D2.3.2- v1.4.pdf处获得的标题为“FP7—信息及通信技术：赠款协议号288094:D2.3.2—对用于环境友好型交通工具路线规划的算法的验证及实证评估：工作包WP2—用于交通工具路线规划的算法(FP7–Information and communication technologies:Grant AgreementNo.288094:D2.3.2–Validation and empirical assessment of algorithms for eco-friendly vehicle routing:Workpackage WP2–Algorithms for Vehicle Routing)”的文件的第5章进行描述。可在可于http://drops.dagstuhl.de/opus/volltexte/2013/4248/ pdf/10.pdf处获得的由安德里亚斯·帕拉斯基沃普洛斯(Andreas Paraskevopoulos)及克里斯托斯·扎罗利亚吉斯(Christos Zaroliagis)，ATMOS 2013—关于运输建模、优化及系统的算法方法的第13次研讨会，10.4230/OASIcs.ATMOS.2013.108的标题为“经改进替代路线计划(Improved Alternative Route Planning)”的文件中找到对用于产生替代路线的技术的进一步描述。这些应用两者的内容均以引用的方式并入本文中。在这些技术中，在起点与目的地之间提供重叠替代路线的网络(其路段可加入彼此或从彼此分割等)，而非在产生对路线的替代路线时仅阻断所述路线的中心部分。在图7中展示一组此类路线的实例。

申请人已意识到，仍需要用于在行进期间给用户提供替代路线选项的经改进方法及系统。在一些方面中，本发明可提供用于产生替代路线的方法及系统。根据一些其它方面，本发明可提供用于穿过可导航网络(其中替代路线选项存在)确定由用户采取的路线的方法及系统。根据其它方面，本发明可提供用于给用户提供替代路线选项的较高效且经改进方法。

发明内容

根据本发明的第一方面，提供一种穿过可导航网络产生路线的方法，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述方法包括：

定义所述可导航网络的子网络，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由所述电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点；

产生介于第二起点-目的地对的起点与目的地之间的主要路线；及

识别所述子网络的将沿着所述主要路线而遇到的第一决策点，及使用路线规划过程来产生介于所述决策点与所述第二起点-目的地对的所述目的地之间的替代路线，在所述路线规划过程中，阻断所述主要路线的部分的从表示所述第一决策点的节点外出的至少第一路段且偏向表示所述子网络的路段的所述子集。

因此，根据本发明，关于从(第二起点-目的地对的)起点到目的地的行进的主要路线(在本文中还称为“主动路线”)上的即将到来的决策点而确定到第二起点-目的地对的目的地的至少一个替代路线。所述决策点是对应于第一起点-目的地对的起点与目的地之间的(替代)路线的路段的路段的预定义子网络的决策点，且至少替代路线的产生偏向表示所述子网络的路段。通过以此方式参考指示预定义子网络的元素的数据以识别将关于其而产生替代路线的决策点，且还在产生替代路线时，已发现可以较高效方式产生有用替代路线。可仅关于对应于子网络的决策点的显著决策点而产生替代路线，从而提供较大处理效率，且避免因过多信息而给用户增加负担。通过在产生路线时偏向子网络的路段，可产生较适当路线。此外，当在决策点处产生替代路线时，阻断现有主要路线的外出路段。此可帮助确保获得明显不同于主要路线的有用替代路线。本发明可允许以较大数据效率获得替代路线，从而使得方法尤其适合于由移动装置(例如，导航装置)实施。

本发明扩展到一种用于执行根据本文中所描述的本发明的各方面或实施例中的任一者的方法的系统。

根据本发明的第二方面，提供一种用于穿过可导航网络产生路线的系统，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述系统包括：

用于定义所述可导航网络的子网络的构件，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由所述电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点；

用于产生介于第二起点-目的地对的起点与目的地之间的主要路线的构件；及

用于识别所述子网络的将沿着所述主要路线而遇到的第一决策点及使用路线规划过程来产生介于所述决策点与所述第二起点-目的地对的所述目的地之间的替代路线的构件，在所述路线规划过程中，阻断所述主要路线的部分的从表示所述第一决策点的节点外出的至少第一路段且偏向表示所述子网络的路段的所述子集。

如所属领域的技术人员将了解，本发明的此进一步方面可以且优选地确实视情况包含本文中关于本发明的其它方面中的任一者所描述的本发明的优选及选用特征中的任何一或多者或者所有特征。在未明确陈述的情况下，本文中的本发明的系统可包括用于执行关于本发明在其各方面或实施例中的任一者中的方法所描述的任何步骤的构件，且反之亦然。

如所属领域的技术人员将了解，本发明的这些其它方面可以且优选地确实视情况包含本文中关于本发明的其它方面中的任一者所描述的本发明的优选及选用特征中的任何一或多者或者所有特征。

本发明是计算机实施的发明，且关于本发明的各方面或实施例中的任一者所描述的步骤中的任一者可在一组一或多个处理器的控制下执行。所述用于执行关于所述系统所描述的步骤中的任一者的构件可为一组一或多个处理器。

本发明在其实施例中的任一者中的系统可呈任何适合装置(例如导航装置)的形式。一般来说，本发明的系统可为至少一个处理装置。所述处理装置或处理装置可为移动装置的装置(例如导航装置，无论是便携式导航装置(PND)还是集成式装置)或可为服务器的装置。

本发明的方法优选地实施于导航操作的背景中。因此，所述方法优选地由具有路线产生能力及/或导航功能性的装置或系统的一组一或多个处理器执行。举例来说，所述方法可由不具有导航功能性的计算机系统(例如，桌上型或膝上型系统)实施。

在优选实施例中，本发明在其各方面或实施例中的任一者中的方法是使用移动装置(例如导航装置)执行，且本发明扩展到经布置以执行本发明的各方面或实施例中的任一者的方法的步骤的移动(例如，导航)装置。导航装置可为PND或集成式(例如，交通工具内)装置。

根据本发明的各方面或实施例中的任一者，所述导航装置可包括用于向用户显示电子地图的显示器、经配置以存取数字地图数据且致使经由所述显示器向用户显示电子地图的一组一或多个处理器及可由用户操作以使得所述用户能够与所述装置交互的用户接口。因此，本发明的系统可为例如导航装置的处理装置的系统。

不管其实施方案如何，根据本发明在其各方面或实施例中的任一者中所使用的装置(例如，导航设备)可包括处理器、存储器及存储于所述存储器内的数字地图数据(或电子地图)。所述处理器与存储器协作以提供可在其中建立软件操作系统的执行环境。可提供一或多个额外软件程序以使得能够控制设备的功能性，且提供各种其它功能。本发明的导航设备可优选地包含全球导航卫星系统(GNSS)(例如，GPS或GLONASS)、信号接收及处理功能性。如将了解，导航设备可视需要使用用于确定其当前位置的其它构件，例如地面信标、移动电信网络等。所述设备可包括可借以将信息中继到用户的一或多个输出接口。除视觉显示器之外，所述输出接口还可包含用于可听输出的扬声器。所述设备可包括输入接口，所述输入接口包含一或多个物理按钮以控制所述设备的开/关操作或其它特征。

在其它实施例中，本发明在其各方面或实施例中的任一者中的方法可由服务器执行，且本发明扩展到经布置以执行本发明的各方面或实施例中的任一者的方法的步骤的服务器。本发明的其各方面或实施例中的任一者的系统可为例如服务器的处理装置的系统。

当然，本发明在其各方面或实施例中的任一者中的方法的步骤可部分地由服务器且部分地由导航设备执行。举例来说，路线产生可由服务器执行(例如，在导航装置的请求下)且提供到装置以供输出给用户。所述方法的所述步骤可排他地在服务器上执行，或者以任何组合一些步骤在服务器上执行且其它步骤在导航装置上执行，或者排他地在导航装置上执行。所述步骤中的一者或多者在服务器上执行可为高效的，且可减小置于导航装置上的计算负担。替代地，如果一或多个步骤是在导航装置上执行，那么此可减小网络通信所需的任何带宽。因此，本发明的系统可部分地由导航装置或其它移动装置提供，且部分地由服务器提供。

如本文中所使用的术语“路段”采取其在本技术领域中的通常含义。路段可为连接两个节点的可导航元素(或链路)或其任何部分。尽管本发明的实施例是参考道路路段来描述，但应意识到，本发明还可适用于其它可导航路段，例如路径、河流、水道、自行车道、纤道、铁路线等等的路段。为便于参考，将这些路段统称为道路路段，但对“道路路段”的任何参考可由对“可导航路段”或任何一个或若干特定类型的此类路段的参考替换。如由电子地图数据表示的可导航网络的节点包含表示连接真实世界中的可导航网络的路段的节点(例如交叉点、相交点等)的节点。由电子地图数据表示的节点还可包含人造节点，所述人造节点不表示真实世界中的节点。举例来说，当速度限制沿着可导航元素改变时，可添加人造节点。

本发明的方法涉及穿过由电子地图表示的可导航网络产生替代路线，且在所述可导航网络内定义子网络。所述子网络由表示可导航网络的路段及节点的多个路段及节点的子集表示。子网络的路段对应于定义介于第一起点-目的地对的起点与目的地之间的穿过可导航网络的相交路线的网络的路线的路段。路线网络的路段在子网络的节点处彼此相交。子网络的节点包含指示子网络的在其处存在两个或更多个外出路段的决策点的节点。因此，子网络的决策点是在其处子网络的路段偏离的点。

可以任何适合方式如此识别子网络的路段。举例来说，指示子网络的每一路段的电子地图数据可与所述路段属于子网络的指示相关联。替代地或另外，所述方法可包括存储指示形成子网络的部分的每一可导航路段的身份的数据，且使用所存储数据来识别形成子网络的部分且将在穿过可导航网络产生路线时被偏向的路段。

子网络由介于第一起点-目的地对的起点与目的地之间的穿过可导航网络的路线网络的路段构成。通过在确定介于沿着主要路线的决策点或点与第二起点-目的地对的目的地之间的所述或每一替代路线时偏向这些路段，路线产生过程将偏向对应于此路线网络的至少部分(例如，其路段)的路线。因此，路线网络引导路线产生过程，且帮助使搜索空间集中。

在一些实施例中，子网络由介于第一起点-目的地对的起点与目的地之间的穿过可导航网络的一组先前所行进路线的路段定义。子网络可因此称为个人网络，且包括先前由用户行进的路线。定义子网络的个人网络可本身由先前由用户行进的路线的子集(即，包含在不同起点目的地对之间行进的路线的较大个人网络的子集)定义。定义子网络的步骤可包括使用指示先前行进穿过可导航网络的路线的所存储数据来获得介于起点与目的地之间的提供子网络的路线网络。在这些实施例中，其路段定义子网络的路线对应于历史路线。在获得一组所存储先前行进的路线时所涉及的步骤可涉及(举例来说)在沿着路线行进期间存储位置数据的导航装置。

在其它实施例中，子网络包括在第一起点-目的地对的起点与目的地之间产生(即，计算)的一组多个替代路线的路段。因此，路线网络是介于起点与目的地之间的先前所产生的替代路线网络。因此，定义子网络的步骤可包括产生介于起点与目的地之间的一组多个替代路线以提供穿过可导航网络的路线网络(其路段定义子网络)。

将了解，可在产生介于第二起点-目的地对的起点与目的地之间的主要路线的步骤之前、之后或与其同时执行定义子网络的步骤。可导航网络的子网络及主要路线可独立于彼此而产生，或一者可通过参考另一者而产生。

举例来说，且当子网络优选地为个人网络的至少部分时，通常在产生主要路线之前将子网络定义于第一起点-目的地对(例如家与工作场所、家与健身房等)之间。此主要路线通常介于第二起点-目的地对(例如在接近于家位置的停车区中的起点，或接近于家位置的所关注点(例如店铺或商店))之间。可视需要使用电子地图的任何路段来在不偏向表示子网络的路段的子集中的路段的情况下产生此主要路线，且因此所述主要路线为介于第二起点-目的地对之间的最小成本(例如，最快、最短等)路线。在一些实施例中，可甚至在产生介于决策点与第二起点-目的地对的目的地之间的替代路线之前，将形成此所产生主要路线的路段添加到现有子网络。在其它实施例中，可偏向表示子网络的路段的子集中的路段而产生主要路线，使得所述主要路线有效地为穿过子网络的最小成本(例如，最快、最短等)路线。

因此，在一些实施例中，可在不参考主要路线的情况下定义子网络。可接着在产生主要路线之前、之后或与其同时定义子网络。举例来说，在子网络的替代路线为先前所行进路线的情况下，此可为适当的。第二起点-目的地对的起点及目的地可或可不接着不同于第一起点-目的地对的起点及目的地。在其中在产生主要路线之前定义子网络的一些实施例中，所述方法可包括通过子网络而产生主要路线的步骤。主要路线可经产生以便偏向子网络的路段或可为穿过子网络(即，仅包含子网络的路段)的路线。主要路线可为穿过子网络的最小成本路线。在其它实施例中，可在不参考子网络的情况下产生主要路线。在所产生的主要路线并不局限于子网络的情况下，可将所述主要路线添加到子网络以扩展所述网络。

在一些实施例中，且当子网络优选地为多个相交路线时，可视需要使用电子地图的路段来产生介于第一起点-目的地对之间的主要路线。可接着将主要路线用作(例如)电子罗盘项目中所开发的交替路线产生技术的基础以产生子网络。因此，在这些实施例中，首先计算主要路线且接着将所述主要路线用于定义(或产生)子网络。还将了解，在此类实施例中，第一起点-目的地对将通常与第二起点-目的地对相同。

因此，在一些实施例中，主要路线可用于获得替代路线的子网络。在一些实施例中，所述方法包括以下步骤：产生介于第二起点-目的地对的起点与目的地之间的主要路线，且将主要路线用于产生介于起点与目的地之间的对主要路线的一组多个替代路线，所述组多个替代路线提供定义子网络的所述组多个替代路线。可将可导航网络的所有路段或至少出于路线规划目的而将被考虑的所有路段(例如，在路线规划走廊中、在起点的给定区内等)考虑在内而产生主要路线。主要路线可为穿过网络的(例如)关于时间、距离或燃料消耗量等的任何最小成本路线。在这些实施例中，第一起点-目的地对的起点及目的地与第二起点-目的地对的起点及目的地相同。

因此，将了解，由介于第一起点-目的地对之间的替代路线的路段定义的子网络可适合于引导产生介于第二起点-目的地对之间的路线，其中第二起点-目的地对的起点及目的地对应于或至少接近于第一起点-目的地对的起点及目的地。第二起点-目的地对的起点可与第一起点-目的地对的起点相同或类似。同样，第二起点-目的地对的目的地可与第一起点-目的地对的目的地相同或类似。举例来说，第二起点-目的地对的起点或目的地可在第一起点-目的地对的起点或目的地中的对应一者的给定接近度(例如，1km)内。

第一起点-目的地对及/或第二起点-目的地对的起点及目的地可为任何适合起点及目的地，且可从任何适合一或若干源获得。起点及目的地可为用户规定的或自动选择的或者其组合。举例来说，起点及/或目的地可经由通信网络而接收。起点及目的地可由服务器从导航装置接收，或可由导航装置从服务器接收。第二起点-目的地对的起点至少可对应于用户的当前位置。

可根据任何适合技术而产生在其中替代路线为所计算路线(无论是否基于主要路线)的实施例中的定义子网络的所述组替代路线。在一些实施例中，路线是基于穿越可导航路段的网络中的路段的成本而产生的。举例来说，所述组路线可包含最小成本路线(或至少在已产生主要路线之后的最小成本路线)及一或多个次最小成本路线。成本优选地为至少部分地基于针对每一路段的穿越时间或穿越速度。这些实施例中所使用的穿越时间或速度可为基于历史数据的预期穿越时间或速度。可使用各种技术来尝试确保所述组替代路线为明智的(即，用户友好替代方案)，例如通过考虑可准许重叠的程度等。在一些优选实施例中，使用开发为上文所提及电子罗盘项目的部分的技术来产生所述组路线。

不管其如何产生，无论是基于个人路线还是其它先前所产生路线，路线网络(其路段定义可导航网络的子网络)是固定路线网络。路线并不动态地改变(例如，在用户行进穿过网络期间)，即，路线不被添加、修改或删除。因此，可将子网络视为预定义或静态子网络。

申请人已意识到，期望能够在已沿着主要路线开始行进之后给用户提供一或多个替代路线选项。此可提供较动态系统，其中给用户提供对其行程的较大控制。本发明提供使得能够关于决策点或沿着所行进路线的点较高效地产生此类替代路线选项的方法。由于替代路线是在沿着路线行进期间产生，因此此使得能够将实况数据(例如，指示可适用交通状况、天气状况等)考虑在内，而非依赖于子网络的预定义路线。

所述方法包括产生介于第二起点-目的地对之间的主要路线的步骤。在其中在产生主要路线之前定义子网络的实施例中，此可使用偏向子网络的路段的路线规划过程来执行。在一些实施例中，还产生介于第二起点-目的地对之间的至少一个替代路线。此可接着也使用偏向子网络(在已被定义的情况下)的路段的路线规划过程来执行。可在用户开始行进之前执行产生介于第二起点-目的地对的起点与目的地之间的主要路线及任选地至少一个替代路线的步骤。

优选地，产生介于第二起点-目的地对的起点与目的地之间的主要路线及任选地至少一个替代路线的步骤包括使用指示针对可导航网络的路段的穿越时间或速度的实况数据。优选地，在产生介于决策点与第二起点-目的地对的目的地之间的所述或每一替代路线时，也使用此数据。可将如本文中所提及的实况数据视为是当前的或至少相对当前的且提供对在网络的路段上正发生什么的指示的数据。实时数据可通常与路段上在最近15分钟、10分钟、5分钟或甚至更近内的状况相关。以此方式，可将(举例来说)网络上的当前交通状况、天气状况等考虑在内而产生主要路线及至少一个替代路线。举例来说，可经由通过无线通信信道的馈送而获得指示针对路段的实况穿越时间或速度的数据，如此项技术中已知。

可以任何适合方式产生介于第二起点-目的地对的起点与目的地之间的主要路线及任选地替代路线以及介于决策点与第二起点-目的地对的目的地之间的所述或每一替代路线。优选地基于穿越可导航网络的可导航路段的成本而产生路线。因此，在产生主要路线及替代路线时所使用的路线产生(或路线规划)过程优选地是基于穿越网络的可导航路段的成本。可使用成本函数来确定穿越可导航路段的成本。可基于与路段相关联的一或多个属性来确定穿越路段的成本。穿越路段的成本优选地为至少部分地基于用以穿越路段的时间。可使用任何已知方法(例如基于迪克斯特拉(Dijkstra)方法)来实现通过参考穿越成本获得路线。

优选地，介于第二起点-目的地对的起点与目的地之间的主要路线是所述起点与所述目的地之间的最小成本路线。最小成本路线可为最快路线、最短路线、最生态路线等或视需要其任何组合。最小成本路线可为基于使与穿越可导航网络的路段相关联的成本(所述成本使用适当成本函数来确定)最小化，即，此导致较低成本与具有被认为尤其合意的属性的路段相关联，或较高成本与被认为不合意的路段相关联。举例来说，可视情况(例如，基于用户输入)选择成本函数以产生为最短路线、最快路线、最生态路线等的最小成本路线。在一些实施例中，主要路线是穿过子网络的最小成本路线。在其中产生介于第二起点-目的地对的起点与目的地之间的一或多个替代路线的实施例中，所述或每一替代路线可为在主要路线之后介于起点与目的地之间的一或若干次最低成本路线。因此，主要路线可为介于起点与目的地之间的最小成本路线，且至少一个替代路线可为介于起点与目的地之间的一或若干次最小成本路线。然而，一或若干替代路线无需为次最小成本路线。举例来说，在产生替代路线的过程期间可施加其它约束(例如，关于与主要路线的重叠程度、复杂性等)。此类约束可包含用户规定的偏好。

根据其中在产生介于第二起点-目的地对的起点与目的地之间的主要路线之前定义子网络的本发明的一些实施例，在产生主要路线及(在适用的情况下)替代路线时偏向子网络的路段。根据本发明的所有实施例，在产生介于决策点与第二起点-目的地对的目的地之间的替代路线时，偏向子网络的路段。本文中关于偏向子网络的路段而产生介于第二起点-目的地对的起点与目的地之间的路线所描述的特征中的任一者在产生介于决策点与所述目的地之间的替代路线时同样地适用。偏向子网络的路段使所述路段较可能包含于穿过可导航网络产生的路线中。通过以此方式偏向路段，而非将路线产生过程限制于使用形成子网络的部分的路段，所产生的主要路线或替代路线将包含不形成子网络的部分的路段是可能的。举例来说，此可为以下情形：当前交通状况意味着尽管偏向所述路段，但其成本仍大于子网络外部的网络中的其它路段，且所述其它路段不受交通状况影响。因此，尽管本发明可能提供位于子网络内的替代路线及(在一些实施例中)主要路线，但对路线计划过程提供包含子网络外部的路段的灵活性，如果这些路段可产生总体较有利(例如，较低成本)路线的话。

在产生介于决策点与第二起点-目的地对的目的地之间的替代路线以及(在一些实施例中)介于第二起点-目的地对的起点与目的地之间的主要路线及任选地至少一个替代路线时，偏向子网络的路段，这是因为所述路段属于所述子网络。虽然子网络的路段对应于路线网络的路段，但至少在各实施例中，本发明仅偏向某些路段(这是因为所述路段形成所述子网络的部分)，且在路线产生过程中不将穿过子网络的形成所述网络的部分的路线考虑在内。因此，在定义子网络的路线网络的给定路线内的路段的次序是无关紧要的。

可出于穿过可导航网络的路线产生的目的以任何适合方式偏向所述或每一可导航路段，使得在产生主要路线或替代路线时，所述或每一路段对于包含在其中被较有利地考虑(即，相比于原本的情形)。

优选地，产生介于第二起点-目的地对的起点与目的地之间或决策点与所述目的地之间的路线是基于穿越可导航网络的可导航路段的成本。所述方法可接着包括通过降低与所述或每一可导航路段相关联的成本而出于路线产生的目的偏向子网络的所述或每一可导航路段。可使用成本函数来确定与穿越可导航路段相关联的成本。在各实施例中，可使用成本函数将成本降低应用于所述或每一可导航路段。举例来说，所述方法可包括使用成本函数来确定与穿越可导航网络的可导航路段相关联的成本，所述成本函数经布置以将额外成本降低应用于子网络的每一可导航路段(例如，仅应用于子网络的所述或每一可导航路段，这是因为所述可导航路段形成所述子网络的部分)。相对于将基于路段的属性而针对那一路段以其它方式获得的成本，成本降低可降低与穿越路段相关联的成本。在涉及于决策点处阻断主要路线的外出路段的过程中，介于第二起点-目的地对的起点与目的地之间的主要路线及在决策点与第二起点-目的地对的目的地之间产生的替代路线优选地为最小成本路线。基于阻断主要路线的第一外出路段及任何先前所产生替代路线，介于决策点与所述目的地之间的任何额外替代路线也可为最小成本路线。介于所述起点与所述目的地之间的替代路线通常将不是最小成本路线，而是可为(举例来说)次最低成本路线。

当然，设想出于路线产生的目的使子网络的路段为较有利的可以其它方式来实现，例如，通过使不形成子网络的部分的路段相比于原本的情形较不有利(例如，通过操纵与每一路段相关联的成本)。

在其中确定介于第二起点-目的地对的起点与目的地之间的主要路线及至少一个替代路线的实施例中，所述方法可包括将指示一或多个路线的存在的数据输出给用户。所述方法可包括将介于第二起点-目的地对的起点与目的地之间的主要路线的至少一部分及所述或每一替代路线的至少一部分显示给用户。举例来说，可提供每一路线的概述，所述概述指示介于第二起点-目的地对的起点与目的地之间的整个路线或其至少一部分。所述方法可进一步包括产生导航指令且在各实施例中将所述导航指令提供给用户以至少沿着主要路线引导用户。如本文中所提及的导航指令可呈路线的显示的形式，通常与指示将由用户采取的沿循路线的操纵及其它动作(其可以可听方式及/或以视觉方式给出)的一组一或多个指令组合。所述方法可包括给用户提供针对主要路线及所述或每一替代路线的比较数据(例如，指示当采取替代路线等时的所估计到达时间的差异、距离的差异等)。

所述方法进一步包括识别子网络的第一决策点(其位于沿着主要路线)，即，在从第二起点-目的地对的起点沿着主要路线行进时遇到的第一决策点。第一决策点是将在沿着路线行进期间遇到的子网络的下一决策点。使用其中偏向子网络的路段的路线规划过程来产生介于决策点与第二起点-目的地对的目的地之间的替代路线。此可以关于产生介于所述起点与所述目的地之间的主要路线及任选地至少一个替代路线的那些实施例所描述的方式中的任一者且以偏向子网络的路段的方式(即，基于穿越路段的成本)来执行。

除偏向子网络的路段之外，在产生介于决策点与第二起点-目的地对的目的地之间的替代路线时，还出于路线产生的目的阻断主要路线的延续的从决策点外出的至少第一路段。因此，一或若干所述路段在路线产生过程期间不仅被惩罚，而且被防止包含于路线中。在一些实施例中，仅阻断主要路线的部分的从决策点外出的第一路段。然而，设想还可阻断一或多个后续路段，以便减小所产生替代路线与主要路线之间的可能重叠。主要路线的部分的从决策点外出的第一路段是起源于表示决策点的节点处且在朝向第二起点-目的地对的目的地的方向上沿着主要路线延伸的路段。通过阻断主要路线的从决策点延伸的第一路段，迫使所产生的替代路线采取决策点处的外出路段或其它外出路段中的一者，使得到目的地的任何所产生的替代路线将在决策点处从主要路线偏离，从而在那一点处为用户提供替代路径。可接着向用户呈现决策点处的替代路线及主要路线以使得所述用户能够做出关于采取哪一路径的决策。

如在确定介于第二起点-目的地对的起点与目的地之间的主要路线的特定实施例中，将由形成子网络的部分的那些路段引导决策点处的替代路线的产生。举例来说，决策点处的替代路线优选地基于实况数据(例如，指示针对网络的路段的当前穿越时间或速度)而产生。以偏向子网络的路段的方式产生路线将往往在主要路线已从子网络偏离的情况下将路线带回到所述子网络。

可在开始沿着主要路线行进之前或在沿着路线行进期间执行识别沿着主要路线的子网络的第一决策点且产生介于决策点与第二起点-目的地对的目的地之间的替代路线的步骤。在一些实施例中，可在用户当沿着主要路线行进时接近第一决策点时(例如，当用户的当前位置在第一决策点的预定距离内时)触发产生替代路线的步骤。无论替代路线产生是否在开始沿着主要路线行进之前发生，通过确定决策点处的替代路线，可在用户接近决策点时将替代方案呈现给用户。

所述方法可包括，针对沿着主要路线的子网络的任何决策点(在其处产生到第二起点-目的地对的目的地的替代路线)，使用路线规划过程来另外产生介于决策点与所述目的地之间的至少一个其它替代路线，在所述路线规划过程中，阻断主要路线的延续及所述或每一已产生替代路线的从决策点外出的介于决策点与第二起点-目的地对的目的地之间的至少第一路段，且偏向子网络的路段。因此，以与通过偏向子网络的路段且阻断决策点处的至少第一外出路段的过程而确定介于决策点与第二起点-目的地对的目的地之间的第一替代路线相同的方式，可重复此步骤，此次另外阻断所述或每一已产生替代路线(例如，第一替代路线)的至少第一路段，以便提供不同于决策点处的主要路线及每一其它替代路线的到第二起点-目的地对的目的地的替代路线。

与主要路线一样，一旦已产生介于沿着主要路线决策点与所述目的地之间的所述或每一替代路线，所述方法便可包括将指示决策点处的所述或每一替代路线的存在的数据输出给用户。此可涉及将指示主要路线及所述或每一替代路线的任何适合信息输出给用户。当用户的当前位置在决策点的预定距离内时，可将指示决策点处的主要路线及至少一个替代路线的数据输出给用户。

决策点及所述或每一替代路线可由沿着路线的相应图标指示。替代地或另外，所述方法可包括将决策点以及介于决策点与第二起点-目的地对的目的地之间的主要路线的至少一部分及所述或每一替代路线的至少一部分显示给用户。主要路线的部分可包含当前位置。可输出决策点的区域中的每一路线(例如，从所述决策点发出)的至少一部分(例如，从当前位置到目的地)。表示可为可选择的以获得对路线的概述。

所述方法可包括将主要路线的示意性表示连同沿着路线的决策点的位置的指示及决策点处的所述或每一替代路线的指示一起显示给用户。在一些实施例中，路线的示意性表示是线性表示。主要路线的表示可为包含当前位置及决策点的路线的任何部分(例如，从当前位置或第二起点-目的地对的起点到决策点或第二起点-目的地对的目的地的路线的一部分)的表示。所述表示可具有如标题为“显示动态行进信息的导航装置(Navigationdevice displaying dynamic travel information)”的US 2007/0225902A1或标题为“指示交通延迟的方法、用于其的计算机程序及导航系统(Method of indicating trafficdelays,computer program and navigation system therefor)”的WO 2008/083862A1中所描述的形式，两个文件的全部内容以引用的方式并入本文中，其中示意性表示是从所计划路线的起点或导航装置的当前位置沿着所计划路线延伸到所计划路线的目的地的线性表示。然而，在优选实施例中，所述表示可具有如标题为“使用导航设备提供信息的方法及系统(Methods and systems of providing information using a navigationapparatus)”的WO 2014/060559A1中所描述的形式，所述文件的全部内容也以引用的方式并入本文中，其中示意性表示是将被沿循的路径的一部分的线性表示。如将了解，示意性表示并不打算提供供用于导航中的准确路径表示，而是将用于促进将行进路径的可视化且传达关于POI或者关于路径的事件(例如，交通、事故、障碍区(hazards)、测速相机、危险区带等)或(在此情形中)交替路线选项的信息(例如，通过对所述表示进行适当地注释)。在各实施例中，所述方法进一步包括与显示路径的部分的线性表示同时地显示2D或3D导航地图的表示。导航地图可提供当前位置的表示及当前位置定位于其上的道路的指示。导航地图可提供将从当前位置被采取以沿循路线的路径的指示。导航地图提供真实周围环境的表示以促进导航。路径的部分的所显示线性表示及/或其中显示所述表示的显示窗可沿着所显示导航地图的侧定位。所述侧可为底部边缘或顶部边缘或者较优选地连接地图的顶部边缘与底部边缘的侧边缘中的一者。在一些实施例中，线性表示沿着地图的侧垂直延伸。在一些优选实施例中，将线性表示及/或窗提供为叠加于2D或3D导航地图的背景图像上。

所述方法可包括给用户提供针对主要路线及所述或每一替代路线的比较数据(例如，指示当采取替代路线等时的所估计到达时间及/或将行进的距离及/或预期燃料消耗量的差异)。

优选地经由移动装置将指示介于第二起点-目的地对的起点与目的地之间或决策点与第二起点-目的地对的目的地之间的主要路线及任选地替代路线的数据输出给用户。移动装置可与用户正在其中行进的交通工具相关联，且优选地为导航装置。导航装置可为与交通工具相关联的集成式导航装置或便携式导航装置(PND)(例如，手持式装置)。所述装置优选地为执行根据本发明的穿过网络产生路线的步骤中的一些或所有步骤的相同装置。然而，设想路线产生步骤中的一些或所有步骤可通过远程装置(例如，服务器)而执行且被发射到所述装置以供输出给用户。

将看出，在沿着主要路线前进到第二起点-目的地对的目的地期间，可不断地重复针对沿着当前主要路线的子网络的下一决策点获得一或多个替代路线的过程，使得可关于子网络的即将到来的决策点而总是将至少一个替代路线呈现给用户。

在通过决策点之后，用户可选择在主要路线上继续或者可选择采取决策点处的所产生替代路线或所述所产生替代路线中的一者。所述方法可包括，当确定用户已选择在通过第一决策点之后在现有主要路线上继续时，识别沿着主要路线的子网络的下一决策点，且使用路线规划过程来产生介于决策点与第二起点-目的地对的目的地之间的替代路线，在所述路线规划过程中，阻断主要路线的部分的从决策点外出的至少第一路段且偏向子网络的路段。在确定用户已选择在第一决策点处采取替代路线的情况下，可采取替代路线作为新主要路线，且关于沿着新主要路线的网络的下一决策点产生一或多个替代路线。

可针对子网络的将在用户沿着主要路线行进期间遇到的每一“下一”决策点而重复这些步骤。将了解，术语“主要路线”是指当前主要路线，即，在通过子网络的先前决策点之后的主要路线。取决于由用户在沿着路线的子网络的每一决策点处所做的决策，如果用户决定采取替代路线，那么在通过决策点之后决策点处的替代路线可变为主要路线，如上文所描述。主要路线可有时称为“主动路线”即，用户当前沿着其行进且针对其提供导航指令的路线。

在优选实施例中，仅关于在沿着主要路线的当前位置前面的沿着主要路线的子网络的第一(即，下一)决策点而执行产生介于沿着主要路线的子网络的决策点与目的地之间的替代路线的步骤。由于不确信用户在即将到来的决策点处是将采取主要路线还是替代路线，因此通常存在于那一阶段处关于沿着当前主要路线的后续决策点而确定替代路线的极小(如果有)需要。此可导致不必要数据处理及存储。替代地，进行等待直到由用户在通过下一决策点之后采取的路线为已知的为止是较高效的。因此，仅需要向前看沿着当前路线的子网络的下一决策点以产生替代路线选项。一旦已通过决策点，便可此次关于在通过第一决策点之后所沿循的主要路线及到第二起点-目的地对的目的地的所产生的一或多个替代路线而重复识别下一决策点的步骤。再次，优选地仅关于下一决策点而执行此步骤。

尽管关于执行关于沿着主要路线的子网络的下一决策点确定替代路线的步骤而描述本发明，但将了解，无需关于沿着路线的子网络的每一决策点而执行所述方法。举例来说，可仅关于在其处期望给用户提供替代选项的显著决策点而执行所述方法。因此，第一决策点可未必是将遇到的下一决策点，而是即将到来的决策点，且在其中在通过第一决策点之后关于另一决策点而重复所述方法的实施例中，所述方法可包括执行关于后续决策点(其可未必是沿着主要路线的下一决策点)的方法的步骤。

可(例如)因用户的当前位置进入决策点的预定距离内或因用户通过先前决策点而触发关于沿着主要路线的决策点(例如，第一决策点或下一决策点)产生替代路线。优选地，在沿着主要路线行进期间(例如，当接近决策点时)执行产生从主要路线的决策点到目的地的替代路线的步骤。

在一些情形中，可确定在当前位置与第二起点-目的地对的目的地之间不存在子网络的其它决策点或存在少于预定数目个决策点。在一些此类情形中(例如，在到目的地的距离超过给定距离使得仍期望提供替代路线选项的情况下)，所述方法可接着包括定义介于当前位置与第二起点-目的地对的目的地之间的替代路线的新子网络。新子网络可为基于介于可适用位置之间的先前所行进路线，或可通过使用任何适合过程计算替代路线而产生，如关于原始子网络所描述。可接着识别沿着主要路线的此新子网络的第一决策点，且产生到所述目的地的一或若干替代路线，如关于原始子网络的第一决策点所描述。可针对子网络的后续决策点重复此直到到达目的地或需要产生另一子网络为止。将了解，每一子网络是静态子网络，即，当产生新路线时，所述子网络不改变。如果子网络不含有所需的区域中的决策点，那么通常替代地定义(或产生)新子网络而非修改现有子网络。

所述方法可包括关于第一决策点或任何后续决策点处的所产生替代路线中的至少一些或每一替代路线而产生导航指令。可与替代路线(导航指令与其相关)相关联地存储导航指令。此可使得能够在无需进一步处理的情况下将替代路线中的一者用作主要路线，且引导将指令输出给用户(如果确定用户已采取所述路线的话)。

可以各种方式执行确定用户何时已选择采取决策点(例如，第一决策点或关于其而执行所述方法的任何后续决策点)处的替代路线。在一些情形中，用户可提供输入以指示其希望采取替代路线。确定用户何时已选择采取替代路线的步骤可接着包括检测指示用户希望采取替代路线的用户输入。可在用户已采取替代路线之前或之后提供所述用户输入，但将通常在用户到达决策点之前提供所述用户输入。在其它实施例中，所述方法可包括自动检测用户何时采取决策点处的替代路线。在这些实施例中，在无需用户提供所采取或将采取的路线的任何指示的情况下推断用户的路线。此检测将为基于用户在通过决策点之后的路径。这些实施例可为有利的，这是因为不需要用户具体地指示其既定路线(例如，通过提供手动输入)。

可通过参考用户的当前位置而执行确定用户已采取决策点处的替代路线。所述方法可包括当在通过决策点之后确定用户的当前位置位于从决策点外出的替代路线的路段上而非位于从决策点外出的形成主要路线的延续的路段上时，推断用户已选择决策点处的替代路线。可使用适当地图匹配技术(即，用于相对于来自用户的绝对位置(例如，如从导航卫星信号获得)的电子地图确定用户的位置的技术)来做出此确定。所述方法可包括接着确定替代路线是新主要路线。

根据在其各方面或实施例中的任一者中的本发明，可使用具有定位确定能力(例如GPS或GSM位置确定能力)的装置来获得用户的当前位置。所述装置通常提供与计时数据(例如，时间戳)相关联的位置数据。所述装置可为其位置可经采取以对应于用户的位置的任何移动装置(例如，导航装置)。所述装置可与用户正在其中行进的交通工具(即，其正在起点与目的地之间行进)相关联。所述装置可为与交通工具相关联的集成式导航装置或便携式导航装置(PND)。所述装置优选地为将指示主要路线及替代路线的数据输出给用户的相同装置。所述装置可为执行本发明的路线产生步骤或执行本发明的其它方面中的任一者的步骤的相同装置。

确定用户的当前位置是否位于替代路线的路段上而非从决策点(或起点)外出的形成主要路线的延续的路段上可使用任何适当地图匹配技术来执行，且可涉及使用各种算法，如此项技术中已知。所述方法可包括试图将指示当前位置的数据与沿着电子地图的可导航路段中的一者的位置匹配。此可在沿着路线行进期间的不同时间执行以提供对用户的当前位置的持续估计，如此项技术中已知。所述方法可包括当用户沿着主要路线在第二起点-目的地对的起点与目的地之间行进时，试图将用户的当前位置与电子地图的路段匹配，且检测当前位置何时可不再与主要路线的路段匹配而是位于从决策点外出的替代路线的路段上。

在一些实施例中，所述方法包括，针对沿着主要路线的所识别第一决策点，存储指示所述或每一所产生替代路线的数据及/或指示包含于路线中的第一决策点处的外出路段的数据。将所述数据存储于一或多个数据库中，所述一或多个数据库在本文中称为“路线池(route pool)”。在各实施例中，路线池包括指示可预期在未来将被采取的多个可能替代路线的数据。所述方法可进一步包括产生导航指令以用于沿着每一路线引导用户。所述方法可包括与路线(导航指令与其相关)相关联地存储导航指令。

所述方法可包括，当用户的当前位置通过决策点时，确定用户的当前位置是否可与决策点处提供主要路线的延续的外出路段匹配，且如果当前位置可与所述外出路段匹配，那么维持现有主要路线作为到目的地的主要路线，且如果当前位置无法与所述外出路段匹配，那么确定用户的当前位置是否可与决策点处的与所存储替代路线相关联的外出路段匹配，其中，当所述当前位置可与决策点处的与所存储替代路线相关联的外出路段匹配时，所述方法包括获得所存储替代路线，且采取所述替代路线作为从决策点到目的地的新主要路线。

在一些情形中，用户可从形成路线池的部分的所产生路线(即，预期路线)中的任一者偏离。在各实施例中，当所述当前位置无法与决策点处的与所存储替代路线中的一者相关联的外出路段匹配时，所述方法可包括识别当前位置可与其匹配的外出路段、产生沿着所识别路段的从决策点到目的地的路线且使用所产生路线作为到目的地的新主要路线。此步骤可以偏向子网络的路段的方式执行。

可关于沿着行进的主要路线的子网络的任何进一步接近的决策点而重复以上步骤。

据信，获得并使用即将到来的决策点处的可能替代路线的数据库或“路线池”以自动确定由用户采取的路线本身是有利的。

根据本发明的第三方面，提供一种通过可导航网络确定由用户采取的路线的方法，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述方法包括：

识别沿着起点与目的地之间由用户行进的主要路线的即将到来的决策点(在所述决策点处存在多个外出路段)，且产生介于第一决策点与所述目的地之间的一或多个替代路线，其中每一替代路线沿着决策点处的外出路段中与提供所述主要路线的延续的外出路段不同的一者通过；

将指示每一所产生替代路线的数据与指示包含于路线中的决策点处的外出路段的数据相关联地存储于至少一个数据库中；

当用户的当前位置通过决策点时，确定用户的当前位置是否可与决策点处提供主要路线的延续的外出路段匹配，且如果当前位置可与所述外出路段匹配，那么维持现有主要路线作为从决策点到目的地的主要路线；

当所述当前位置无法与提供主要路线的延续的外出路段匹配时，确定用户的当前位置是否可与决策点处的与针对所述决策点获得的至少一个数据库中的所存储替代路线中的一者相关联的外出路段匹配，

其中，当所述当前位置可与决策点处的与针对所述决策点的所存储替代路线中的一者相关联的外出路段匹配时，获得指示所存储替代路线的数据，并采取所述替代路线作为从决策点到目的地的新主要路线，且

其中，当所述当前位置无法与决策点处的与针对所述决策点的所存储替代路线中的一者相关联的外出路段匹配时，识别当前位置可与其匹配的外出路段、产生沿着所识别路段的从决策点到目的地的路线且使用所产生路线作为从决策点到目的地的新主要路线。

本发明扩展到一种用于执行根据本文中所描述的本发明的各方面或实施例中的任一者的方法的系统。

根据本发明的第四方面，提供一种穿过可导航网络确定由用户采取的路线的系统，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述系统包括：

用于识别沿着由用户在起点与目的地之间行进的主要路线的即将到来的决策点并产生介于第一决策点与所述目的地之间的一或多个替代路线的构件，在所述决策点处存在多个外出路段，其中每一替代路线沿着决策点处的外出路段中的不同于提供所述主要路线的延续的外出路段的一者通过；

用于将指示每一所产生替代路线的数据与指示包含于路线中的决策点处的外出路段的数据相关联地存储于至少一个数据库中的构件；

用于进行以下操作的构件：当用户的当前位置通过决策点时，确定用户的当前位置是否可与决策点处的提供主要路线的延续的外出路段匹配，且如果当前位置可与所述外出路段匹配，那么维持现有主要路线作为从决策点到目的地的主要路线；

用于进行以下操作的构件：当所述当前位置无法与提供主要路线的延续的外出路段匹配时，确定用户的当前位置是否可和决策点处的与针对所述决策点获得的至少一个数据库中的所存储替代路线中的一者相关联的外出路段匹配，

其中，当所述当前位置可和决策点处的与针对所述决策点的所存储替代路线中的一者相关联的外出路段匹配时，获得指示所存储替代路线的数据，并采取所述替代路线作为从决策点到目的地的新主要路线，且

其中，当所述当前位置无法和决策点处的与针对所述决策点的所存储替代路线中的一者相关联的外出路段匹配时，识别当前位置可与其匹配的外出路段、产生沿着所识别路段的从决策点到目的地的路线且使用所产生路线作为从决策点到目的地的新主要路线。

本发明在这些其它方面中是一种计算机实施的发明，且关于本发明的各方面或实施例中的任一者所描述的步骤中的任一者可在一组一或多个处理器的控制下执行。用于执行关于所述系统所描述的步骤中的任一者的构件可为一组一或多个处理器。

如所属领域的技术人员将了解，本发明的这些其它方面可以且优选地确实视情况包含本文中关于本发明的其它方面中的任一者所描述的本发明的优选及选用特征中的任何一或多者或者所有特征。特定来说，可关于主要路线及替代路线来实施本发明的第三方面及第四方面的步骤，所述主要路线及替代路线是根据本发明的实施例中的任一者中的其第一方面或第二方面中的本发明而在具有子网络的主要路线的任何决策点处确定的。此外，根据本发明的实施例中的任一者中的其第三方面及第四方面的本发明可利用决策点处的主要路线及替代路线，所述决策点是子网络的决策点，其中所述主要路线及替代路线是根据本发明的实施例中的任一者中的其第一方面及第二方面而获得的。本发明的第三方面及第四方面的起点及目的地可对应于第一方面及第二方面的第二起点-目的地对的起点及目的地。

可以任何适合装置(例如导航装置)来实施这些其它方面及实施例中的本发明。本发明的系统可为此装置。一般来说，本发明的系统可为至少一个处理装置。所述处理装置或处理装置可为移动装置的装置(例如导航装置，无论是便携式(例如，手持式)导航装置还是集成式装置)或可为服务器的装置。

本发明根据第三方面及第四方面的方法优选地实施于导航操作的背景中。因此，所述方法优选地由具有导航功能性的装置或系统的一组一或多个处理器执行。在优选实施例中，本发明根据在其各实施例中的任一者中的第三方面及第四方面的方法是使用导航装置执行，且本发明扩展到经布置以执行本发明的第三方面及第四方面或实施例中的任一者的方法的步骤的导航装置。导航装置可包括用于将电子地图显示给用户的显示器、经配置以存取数字地图数据且致使电子地图经由显示器被显示给用户的一组一或多个处理器及可由用户操作以使得用户能够与装置交互的用户接口。因此，本发明在这些其它方面中的系统可为例如导航装置的处理装置的系统。

在其它实施例中，本发明根据第三方面及第四方面的实施例中的任一者的方法可由服务器执行，且本发明扩展到经布置以执行本发明在其第三方面及第四方面中的实施例中的任一者的方法的步骤的服务器。本发明的其各方面或实施例中的任一者的系统可为例如服务器的处理装置的系统。

当然，本发明在第三方面及第四方面的实施例中的任一者中的方法的步骤可部分地由服务器且部分地由导航设备执行。所述方法的所述步骤可排他地在服务器上执行，或者以任何组合一些步骤在服务器上执行且其它步骤在导航装置上执行，或者排他地在导航装置上执行。因此，本发明的系统可部分地由导航装置或其它移动装置提供，且部分地由服务器提供。

根据第三方面及第四方面以及包含对应步骤的第一方面及第二方面的那些实施例的本发明涉及存储指示沿着主要路线的即将到来的第一决策点处的一或多个替代路线的数据，指示每一路线的数据与指示决策点处的形成路线的部分的外出路段的数据相关联。将这些路线存储于一或多个数据库中，所述一或多个数据库在本文中称为路线池且指示可在未来由用户采取的预期替代路线。所述决策点是沿着主要路线的即将到来(即，在当前位置前面)的决策点。还存储指示主要路线及包含于所述路线中的决策点处的外出路段的数据。可或可不将此存储于路线池中。将已存储主要路线，这是因为所述主要路线是当前行进的路线。

在用户沿着主要路线行进期间执行获得替代路线并存储指示外出路段及其相关联路线的数据的步骤。当用户的当前位置在第一决策点的预定距离内时，可触发所述步骤。

主要路线可为介于起点与目的地之间的当前正行进的任何路线，且可为介于起点与目的地之间的任何适合路线(例如，最小成本路线)。所述方法可扩展到产生主要路线的步骤。还可以任何适合方式产生所述或每一替代路线。可以关于本发明的较早方面所描述的方式(例如，通过参考穿越可导航网络的路段的成本)产生主要路线及每一替代路线。优选地，当产生每一替代路线时，将实况数据(例如，实况穿越时间或速度数据)考虑在内。

将了解，可并不关于沿着主要路线的每个即将到来的决策点而执行本发明根据第三方面的方法。举例来说，可仅关于在其处期望向用户呈现替代路线选项的决策点(例如，显著决策点)而执行所述方法。因此，第一决策点可能并非沿着主要路线的下一决策点。在一些优选实施例中，可导航网络包括预定义子网络，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点。所述决策点优选地为子网络的决策点，且优选地为沿着主要路线的子网络的下一决策点。

无论所述决策点是否为子网络的决策点，在优选实施例中，可导航网络包括预定义子网络，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由所述电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点，且使用偏向子网络的路段的路线产生过程来产生所述或每一替代路线及任选地主要路线。此可根据较早所描述的实施例中的任一者来执行。

根据本发明的这些方面及实施例，识别决策点处的对应于主要路线的延续的外出路段。存在决策点处的一或多个额外外出路段。每一外出路段是从所述决策点发出的路段。产生到目的地的一或多个替代路线，所述一或多个替代路线中的每一路线沿着决策点处的外出路段中的不同于形成主要路线的延续的外出路段的相应一者(即，沿着所述额外外出路段或额外外出路段)通过。每一替代路线沿着第一决策点处的不同相应外出路段通过。在一些实施例中，仅产生一个替代路线。产生每一替代路线的步骤可包括阻断从决策点的主要路线的外出路段及(在适用的情况下)决策点处的形成已产生替代路线的部分的所述或每一外出路段。此类技术可为根据本发明的第一方面或第二方面。此将产生沿着决策点处的不同外出路段通过的替代路线。在其它布置中，设想可首先识别不同于提供主要路线的延续的外出路段的一或多个外出路段，且接着产生沿着所述或每一路段的到目的地的替代路线。

不管其如何获得，一旦已产生每一替代路线，便将指示替代路线的数据与指示包含于路线中的决策点处的外出路段的数据相关联地存储于路线池中。可与指示形成主要路线的部分的外出路段的数据相关联地存储指示那一路线的延续的数据。可将此数据存储于路线池中或另一数据库中别处。此使得能够容易地识别包含决策点处的特定外出路段的路线。外出路段的身份可用于查找相关联路线。所述数据可以任何方式相关联，且设想可存储形成路线的部分的外出路段的身份作为路线池数据的部分，前提是可出于本发明的目的而对所述身份进行存取。使外出路段数据与路线池中的可适用路线数据相关联使得可容易地识别由用户在通过决策点之后所采取的路线(通过考虑所述用户的当前位置可与网络的哪一路段匹配)。可以任何方式存储路线数据，从而使得能够在所述方法的其余部分中对所述路线数据进行存取及使用。在各实施例中，获得主要路线及替代路线数据的步骤由移动装置(例如，导航装置)执行。可将所述数据存储于所述装置的存储器中。优选地，产生多个替代路线，且将关于每一替代路线的数据添加到路线池。

将了解，存储于路线池中的沿着特定外出路段的替代路线可为沿着所述路段产生的多个替代路线中的一者。所存储的替代路线可为关于给定性质(例如，所估计到达时间、长度或燃料消耗量)而被优化的替代路线。

在一些实施例中，将多个替代路线存储于路线池中，每一替代路线关于不同给定性质(例如，所估计到达时间、长度及燃料消耗量)而被优化。此可允许向用户呈现可符合其特定偏好的路线。路线池可仅含有关于给定性质而被优化的替代路线。将了解，现有主要路线可为介于决策点与目的地之间的关于给定性质的最优路线。关于给定性质的经优化替代路线将为针对所述性质的最优替代路线(例如，在主要路线之后的次最优路线)。

将指示替代路线的所存储数据存储于一或多个数据库(即，路线池)中，所述一或多个数据库包括指示预期在未来(即，在第一决策点处)将被采取的替代路线的数据。所存储数据可起始路线池，或在已先前起始路线池(例如，关于较早决策点)的情况下更新路线池。路线池是动态改变的数据库，其在任何时间均包括指示可在沿着当前行进的主要路线的即将到来的决策点处采取的一或多个替代路线的数据。此数据将随着即将到来的决策点及主要路线的身份改变而自然地改变。因此，路线池包括在沿着路线行进到目的地期间的不同时间为不同(例如，在当接近第一决策点时的第一时间不同于在通过第一决策点之后且当接近后续决策点时的后续时间)的路线数据。优选地，路线池包括仅关于在给定时间的一个即将到来的决策点的此数据。所述决策点可为将遇到的下一决策点，或至少为关于其而期望能够提供替代路线信息的下一显著决策点。在一些实施例中，第一决策点是将遇到的子网络的下一决策点，如先前所描述。一旦已通过第一决策点，且确定在通过决策点之后的用户的主要路线，便不再需要且可删除针对第一决策点的路线池数据。优选地，路线池不包括关于任何先前所通过决策点的数据。

优选地，所述方法包括关于第一决策点处的至少一些及优选地每一所产生替代路线而产生导航指令的步骤。与相应路线相关联地存储导航指令，且可将所述导航指令存储于路线池中。此使得能够在无需进一步处理以产生导航指令的情况下将替代路线用作主要路线(如果所述路线由用户采取的话)。

所述方法可涉及在沿着主要路线从起点行进到目的地期间将用户的当前位置与主要路线的路段匹配，所述路段是到第一决策点的进入路段。

在本发明的这些其它方面中，可通过使用具有定位确定能力(例如GPS或GSM位置确定能力)的装置而以关于较早方面所描述的方式中的任一者获得用户的当前位置。所述装置通常提供与计时数据(例如，时间戳)相关联的位置数据。所述装置可为其位置可经采取以对应于用户的位置的任何移动装置(例如，导航装置)。所述装置可与用户正在其中行进的交通工具(即，其正在起点与目的地之间行进)相关联。所述装置可为与交通工具相关联的集成式导航装置或便携式导航装置(PND)。确定当前位置位于其上的路段可使用任何适当地图匹配技术来执行，且可涉及使用各种算法，如此项技术中已知。此可在沿着路线行进期间的不同时间执行以提供对用户的当前位置的持续估计，如此项技术中已知。

所述方法可包括将导航指令提供给用户以用于沿着主要路线引导用户。

所述方法可包括将指示第一决策点处的至少一些或者所述或每一替代路线的存在的数据输出给用户。此可涉及将指示主要路线及所述或每一替代路线的任何适合信息输出给用户。所述方法可包括将主要路线的示意性表示连同沿着路线的第一决策点的位置的指示及决策点处的所述或每一替代路线的指示一起显示给用户，例如如上文所描述。在一些实施例中，路线的示意性表示是线性表示。主要路线的表示可为包含当前位置及决策点的路线的任何部分(例如，从当前位置或起点到决策点或目的地的路线的一部分)的表示。决策点及所述或每一替代路线可由沿着路线的相应图标指示。替代地或另外，所述方法可包括将决策点以及介于决策点与所述目的地之间的主要路线的至少一部分及所述或每一替代路线的至少一部分显示给用户。主要路线的部分可包含当前位置。可输出决策点的区域中的每一路线(例如，从所述决策点发出)的至少一部分(例如，从当前位置到目的地)。表示可为可选择的以获得对路线的概述。所述方法可包括给用户提供针对主要路线及所述或每一替代路线的比较数据(例如，指示当采取替代路线时的所估计到达时间、距离、燃料消耗量等的差异)。当用户的当前位置在决策点的预定距离内时，可将指示决策点处的主要路线及至少一个替代路线的数据输出给用户。输出指示主要路线及替代路线的数据可根据关于本发明的较早方面所描述的技术中的任一者来执行，且给用户提供信息以使得所述用户能够做出关于在即将到来的第一决策点处采取哪一路径的决策。所述数据可由移动装置(例如，导航装置)输出，所述移动装置可为执行根据本发明的第三方面及第四方面的其它步骤中的一些或所有步骤的相同装置。

当用户的当前位置通过第一决策点时，执行各种步骤以确立由用户采取的路线。

确定用户的当前位置是否可与第一决策点处的提供主要路线的延续的外出路段匹配。当在通过第一决策点之后当前位置与其匹配的可导航网络的路段是主要路线的路段时，可假定用户已沿着主要路线继续。在用户通过第一决策点之后，继续将现有主要路线视为主要路线。

当所述当前位置无法与第一决策点处的提供主要路线的延续的外出路段匹配时，确定当前位置是否可和第一决策点处的与关于所述第一决策点获得的所存储替代路线中的一者相关联的外出路段匹配。此可通过将当前位置与其匹配的路段的识别符和与针对其而存储路线数据的替代路线相关联的外出路段的所述或每一识别符进行比较而执行。在当前位置可和与关于所述第一决策点获得的所存储替代路线相关联的外出路段匹配的情况下，采取所述所存储替代路线作为到目的地的新主要路线。当所述当前位置无法和关于所述第一决策点获得的所存储替代路线相关联的路段匹配时，产生沿着所述路段从第一决策点到目的地的另一替代路线。采取所产生路线作为到目的地的新主要路线。可以任何适合方式产生所述路线，如关于先前产生的所存储路线所描述。可以偏向可导航网络的子网络(在被定义的情况下)的路段的方式产生所述路线。

可以任何适合方式实施执行以上步骤(即，确定用户的当前位置是否可与特定路段匹配)。所述方法可包括将所述当前位置与第一决策点处的外出路段匹配，且将所述路段的身份与形成主要路线的延续的路段的身份及(视情况)包含于一或若干所存储替代路线中的一或若干路段的身份进行比较。

以此方式，可在通过第一决策点之后从用户的当前位置检测由用户在所述决策点处采取的路径，且确立在通过所述决策点之后的适当主要路线。如果用户选择采取不对应于现有主要路线或已产生替代路线的路线，那么可产生从已被采取的路段开始的新(替代)路线，且在通过第一决策点之后所述新(替代)路线变为新主要路线。在无需用户提供指示既定路线的输入的情况下推断由用户在第一决策点处采取的路线。

所述方法可包括将导航指令提供给用户以用于在通过第一决策点之后沿着所确定的主要路线引导用户。因此，此可为现有主要路线的延续、先前所存储替代路线或新替代路线。此可利用先前产生(例如，当视情况产生替代路线时)的导航指令。

优选地，所述方法包括在当前位置通过第一决策点之后删除指示第一决策点处的所述或每一预期替代路线的所存储路线池数据(即，指示所述决策点处的外出路段及相关联一或多个替代路线的数据)。一旦已确立在通过第一决策点之后的用户的路线，便不再需要此数据，且可由关于新即将到来的决策点的对应数据来替换所述数据。换句话说，可刷新路线池数据。

将了解，可在通过第一决策点之后针对沿着所确定的主要路线的一或多个后续决策点重复本发明的第三方面及第四方面以及相关实施例的方法。此(些)决策点可能并非下一(且如果适用，连续)其它决策点。如较早所描述，所述技术可仅应用于沿着路线的选定决策点。在一些实施例中，关于沿着主要路线的至少下一决策点(其为可导航网络的子网络的决策点)而执行所述方法。可关于沿着主要路线的子网络的每一连续即将到来的决策点而执行所述方法直到到达目的地为止。关于任何后续决策点而执行的步骤可根据关于第一决策点所描述的实施例中的任一者来执行。

在优选实施例中，所述方法进一步包括(且所述系统包括用于进行以下操作的构件)：在通过第一决策点之后识别沿着所确定将由用户行进的主要路线的即将到来的第二决策点；及产生介于第二决策点与目的地之间的一或多个替代路线，其中每一替代路线沿着第二决策点处的外出路段中的不同于提供主要路线的延续的外出路段的一者通过；以及将指示第二决策点处的每一所产生替代路线的数据(其与指示包含于所述路线中的第二决策点处的外出路段的数据相关联)存储于至少一个数据库(例如，路线池)中。

当用户的当前位置通过第二决策点时，所述方法可包括确定用户的当前位置是否可与第二决策点处的提供主要路线的延续的外出路段匹配，且如果所述当前位置可与所述外出路段匹配，那么维持现有主要路线作为到目的地的主要路线，且如果所述当前位置无法与所述外出路段匹配，那么确定用户的当前位置是否可和第二决策点处的与针对所述第二决策点的所存储替代路线中的一者相关联的外出路段匹配，其中，当所述当前位置可和第二决策点处的与所存储路线中的一者相关联的外出路段匹配时，所述方法包括获得所存储替代路线，并采取所述替代路线作为从第二决策点到目的地的新主要路线，且当所述当前位置无法和决策点处的与针对所述第二决策点的所存储替代路线中的一者相关联的外出路段匹配时，识别当前位置可与其匹配的外出路段、产生沿着所识别路段的从第二决策点到目的地的另一路线且使用所产生路线作为到目的地的新主要路线。

所述方法可包括使用存储于路线池中的关于第二决策点处的可能替代路线的数据(即，指示每一所产生替代路线的数据，及指示包含于每一路线中的第二决策点处的外出路段的数据)来替换关于第一决策点而获得的对应数据。

可在通过第二决策点之后接着针对沿着所确定的主要路线的即将到来的第三决策点重复所述方法，以此类推。针对每一后续决策点获得的路线数据可用于更新路线池数据，例如替换针对先前决策点获得的对应数据。如上文所概述，第一决策点、第二决策点等无需为沿着主要路线遇到的连续决策点。然而，优选地网络包括预定义子网络(例如，如上文所描述)，且优选地关于沿着主要路线的子网络的连续决策点而执行所述方法。第一决策点及第二决策点以及在适用的情况下第三决策点等优选地为沿着主要路线的子网络的连续决策点。

所述方法可包括关于给定决策点产生导航指令以用于沿着所产生的每一替代路线或所述路线中的至少一些路线引导用户，且可包括存储此数据，如关于第一决策点所描述。

所述方法可包括获得并存储指示关于决策点(无论是第一决策点还是后续决策点)获得的所述或每一替代路线及任选地主要路线的一或多个性质的数据。可将所述数据存储于路线池中。当采取到目的地的路线时，所述性质可包含以下各项中的一或多者：沿着所述路线到达目的地处的所估计时间、沿着所述路线到目的地的距离、所述路线上的交通状况及燃料消耗量。所述性质优选地包含一或多个动态改变的性质，例如(当采取到目的地的路线时)以下各项中的一或多者：沿着所述路线到达目的地处的所估计时间、所述路线上的交通状况及燃料消耗量。所述方法可包括在沿着主要路线行进期间动态地更新指示一或多个动态改变的性质的所存储数据。举例来说，可在用户沿着主要路线行进时以给定时间间隔来更新指示动态改变的性质的数据。所述方法可包括将所存储数据或从其导出的数据提供给用户。举例来说，导航装置的显示器上的路线的指示可包括表示在所述路线上存在交通的图标。

在一些实施例中，每一替代路线是从决策点到目的地的为关于给定性质的最优替代路线的替代路线。所述性质可为所估计到达时间、距离或燃料消耗量。不同路线可关于不同性质而被优化。此可使得能够向用户呈现关于可为所关注的多个不同性质中的一者而被优化的路线。所述方法可包括基于性质数据及优选地指示路线的一或若干动态改变的性质的数据而从路线池选择决策点处的一或多个替代路线以供对用户进行建议。举例来说，可建议关于至少一个性质(例如，时间、距离或燃料消耗量)而在存储于路线池中的多个替代路线当中为最优的替代路线。

在一些实施例中，所述方法可包括确定指示介于决策点(无论是第一决策点还是任何后续决策点)与目的地之间的替代路线的动态改变的性质的参数何时改变达大于预定阈值量(即，在沿着主要路线行进期间)，且当确定此改变时，重复以下步骤：获得从决策点到目的地的一或多个替代路线，其中每一替代路线沿着决策点处的外出路段中的不同于提供主要路线的延续的外出路段的相应一者通过；及将指示所述或每一替代路线的数据与指示包含于路线中的决策点处的外出路段的数据相关联地存储于路线池中。举例来说，所述改变与其相关的参数可为当采取所述路线时的所估计到达时间、所述路线的燃料消耗量等。指示一或多个新产生的替代路线的数据优选地用于替换存储于路线池中的关于现有所产生替代路线中的一或多者及优选地每一者的对应数据。因此，所述方法优选地包括使用新替代路线数据来替换路线池中的对应现有数据。优选地删除现有替代路线数据。换句话说，除在已通过决策点时刷新路线池之外，还可在路线的动态改变的性质改变达大于给定量的情况下更新路线池。此可表明，(例如)由于当前交通状况，因此所述路线不再为最优的(例如，关于持续时间)，且需要基于当前状况产生一组新的替代路线。此可帮助确保路线池总是含有指示可被认为是关于一或若干给定性质最优的替代路线的数据。

将了解，通过提供并更新包括可由用户在即将到来的决策点处采取的可能路线的路线池(如关于本发明的第三方面及第四方面所描述)，所述系统将总是具有指示从即将到来的决策点到目的地的可能替代路线且可被呈现给用户的数据。尽管对此路线池数据的存储在提供使得能够自动推断用户在决策点处采取的路径的数据时尤其有用，但在其它背景中路线池的形成是有利的，例如提供关于即将到来的决策点的路线选择，所述路线选择可被呈现给用户以用于由所述用户手动选择既定路线。

根据本发明的第五方面，提供一种将指示路线选项的数据提供给行进穿过可导航网络的用户的方法，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述方法包括：

识别沿着由用户在起点与目的地之间行进的主要路线的即将到来的决策点，在所述决策点处存在多个外出路段，且产生介于第一决策点与所述目的地之间的至少一个替代路线；

将指示决策点处的到所述目的地的至少一个所产生替代路线的数据存储于至少一个数据库中；

将主要路线的至少一部分的示意性表示显示给用户，所述表示包括指示沿着主要路线的用户的当前位置的图标、指示沿着主要路线的决策点的位置的图标及指示至少一个所产生替代路线的存在的可选择图标；及

当检测到由用户对图标的选择时，在地图上显示从决策点延伸到目的地的主要路线及替代路线的至少部分的表示，其中主要路线及替代路线的表示可各自由用户选择以提供对打算在决策点处采取的路线的指示；

其中，当确定用户已选择主要路线的表示时，继续将导航指令提供给用户以沿着现有主要路线引导用户，且

其中，当确定用户已选择替代路线的表示时，采取替代路线作为从决策点到目的地的新主要路线，并将导航指令提供给用户以沿着新主要路线引导用户。

本发明扩展到一种用于执行根据本文中所描述的本发明的各方面或实施例中的任一者的方法的系统。

根据本发明的第六方面，提供一种用于将指示路线选项的数据提供给行进穿过可导航网络的用户的系统，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述系统包括：

用于识别沿着由用户在起点与目的地之间行进的主要路线的即将到来的决策点并产生介于第一决策点与所述目的地之间的至少一个替代路线的构件，在所述决策点处存在多个外出路段；

用于将指示决策点处的到所述目的地的至少一个所产生替代路线的数据存储于至少一个数据库中的构件；

用于将主要路线的至少一部分的示意性表示显示给用户的构件，所述表示包括指示沿着主要路线的用户的当前位置的图标、指示沿着主要路线的决策点的位置的图标及指示至少一个所产生替代路线的存在的可选择图标；及

用于当检测到由用户对图标的选择时在地图上显示从决策点延伸到目的地的主要路线及替代路线的至少部分的表示的构件，其中主要路线及替代路线的表示可各自由用户选择以提供对打算在决策点处采取的路线的指示；

其中，当确定用户已选择主要路线的表示时，继续将导航指令提供给用户以沿着现有主要路线引导用户，且

其中，当确定用户已选择替代路线的表示时，采取替代路线作为从决策点到目的地的新主要路线，并将导航指令提供给用户以沿着新主要路线引导用户。

本发明在这些其它方面中是一种计算机实施的发明，且关于本发明的各方面或实施例中的任一者所描述的步骤中的任一者可在一组一或多个处理器的控制下执行。用于执行关于所述系统所描述的步骤中的任一者的构件可为一组一或多个处理器。

如所属领域的技术人员将了解，本发明的这些其它方面可以且优选地确实视情况包含本文中关于本发明的其它方面中的任一者所描述的本发明的优选及选用特征中的任何一或多者或者所有特征。特定来说，可关于主要路线及替代路线来实施本发明的第五方面及第六方面的步骤，所述主要路线及替代路线是根据本发明的实施例中的任一者中的其第一方面或第二方面中的本发明而在具有子网络的主要路线的任何决策点处确定的。此外，根据本发明的实施例中的任一者中的其第五方面及第六方面的本发明可利用决策点处的主要路线及替代路线，所述决策点是子网络的决策点，其中所述主要路线及替代路线是根据本发明的实施例中的任一者中的其第一方面及第二方面而获得的。另外，可使用关于本发明的第三方面及第四方面所描述的方法中的任一者来获得路线池。

可以任何适合装置(例如导航装置)来实施这些其它方面及实施例中的本发明。本发明的系统可为此装置。一般来说，本发明的系统可为至少一个处理装置。所述处理装置或处理装置可为移动装置的装置(例如导航装置，无论是便携式(例如，手持式)导航装置还是集成式装置)或可为服务器的装置。

本发明根据第五方面及第六方面的方法优选地实施于导航操作的背景中。因此，所述方法优选地由具有导航功能性的装置或系统的一组一或多个处理器执行。在优选实施例中，本发明根据在其各实施例中的任一者中的第五方面及第六方面的方法是使用导航装置执行，且本发明扩展到经布置以执行本发明的第五方面及第六方面或实施例中的任一者的方法的步骤的导航装置。导航装置可为移动装置且可为PND或集成式(例如，交通工具内)装置。导航装置可包括用于将电子地图显示给用户的显示器、经配置以存取数字地图数据且致使电子地图经由显示器被显示给用户的一组一或多个处理器及可由用户操作以使得用户能够与装置交互的用户接口。因此，本发明在这些其它方面中的系统可为例如导航装置的处理装置的系统。

根据第五方面及第六方面的本发明涉及获得指示沿着当前行进的主要路线的即将到来的第一决策点的一或多个替代路线的所存储数据。第一决策点是沿着主要路线的即将到来(即，在当前位置前面)的决策点。

在用户沿着主要路线行进期间执行获得替代路线并存储指示所述路线的数据的步骤。当用户的当前位置在第一决策点的预定距离内时，可触发所述步骤。当所述当前位置在第一决策点的预定距离内时，可触发显示指示第一决策点处的一或若干替代路线的图标的步骤。

主要路线可为介于起点与目的地之间的当前正行进的任何路线，且可为介于起点与目的地之间的任何适合路线(例如，最小成本路线)。所述方法可扩展到产生主要路线的步骤。可以任何适合方式产生所述或每一替代路线。可以关于本发明的较早方面所描述的方式(例如，通过参考穿越可导航网络的路段的成本)产生主要路线及每一替代路线。优选地，当产生主要路线及/或每一替代路线时，将实况数据(例如，针对路段的实况穿越时间或速度数据)考虑在内。

与本发明的第三方面及第四方面一样，将了解，可并不关于沿着主要路线的每个即将到来的决策点而执行本发明在其第五方面及第六方面中的方法。举例来说，可仅关于在其处期望向用户呈现替代路线选项的决策点(例如，显著决策点)而执行所述方法。因此，第一决策点可能并非沿着主要路线的下一决策点。在一些优选实施例中，可导航网络包括预定义子网络，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点。所述决策点优选地为子网络的决策点，且优选地为沿着主要路线的子网络的下一决策点。

无论所述决策点是否为子网络的决策点，在优选实施例中，可导航网络包括预定义子网络，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由所述电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点，且使用偏向子网络的路段的路线产生过程来产生所述或每一替代路线及任选地主要路线。此可根据较早关于第一方面及第二方面所描述的实施例中的任一者来执行。

如在本发明的第三方面及第四方面中，所述方法可包括识别决策点处的对应于主要路线的延续的外出路段。存在决策点处的一或多个额外外出路段。每一外出路段是从所述决策点发出的路段。产生到目的地的一或多个替代路线，所述路线中的每一者沿着决策点处的外出路段中的不同于形成主要路线的延续的外出路段的相应一者(即，沿着额外外出路段)通过。每一替代路线沿着不同相应外出路段通过。在一些实施例中，仅产生一个替代路线。产生每一替代路线的步骤可包括阻断从决策点的主要路线的外出路段及(在适用的情况下)决策点处的形成已产生替代路线的部分的所述或每一外出路段。此将产生沿着决策点处的不同外出路段通过的替代路线。在其它布置中，设想可首先识别不同于提供主要路线的延续的外出路段的一或多个外出路段，且接着产生沿着所述路段的到目的地的替代路线。

不管其如何获得，一旦已产生每一替代路线，便将指示每一替代路线的数据存储于至少一个数据库或“路线池”中。优选地，产生多个替代路线。可与指示包含于路线中的决策点处的外出路段的数据相关联地存储所述数据，如在本发明的第三方面及第四方面中。类似地，可(任选地)与指示形成主要路线的部分的外出路段的数据相关联地存储指示那一路线的从决策点到目的地的延续的数据。可将此数据存储于路线池中或别处。

将了解，存储于路线池中的沿着特定外出路段的替代路线可为沿着所述路段产生的多个替代路线中的一者。所存储的替代路线可为关于给定性质(例如，所估计到达时间、长度或燃料消耗量)而被优化的替代路线。

所述方法可包括产生导航指令以用于沿着在决策点处所产生的每一替代路线或所述路线中的至少一些路线引导用户。此可针对第一决策点或任何后续决策点而执行。所述方法可包括将数据存储于(例如)路线池中。此可使得能够将路线指令容易地提供给用户，倘若所述用户采取替代路线中的一者的话。

可以任何方式存储路线池数据，从而使得能够在所述方法的其余部分中对所述路线池数据进行存取及使用。在各实施例中，获得主要路线及替代路线数据的步骤由移动装置(例如，导航装置)执行。可将所述数据存储于所述装置的存储器中。所述装置优选地为执行在其第五方面及第六方面中的方法的其余部分的装置。

路线池包括指示预期在未来(即，在第一决策点处)将被采取的替代路线的数据。所存储数据可起始路线池，或在已先前起始路线池(例如，关于较早决策点)的情况下更新路线池。路线池是动态改变的路线池，其在任何时间均包括指示可在沿着当前行进的主要路线的即将到来的决策点处采取的一或多个替代路线的数据。此数据将随着即将到来的决策点的身份改变而自然地改变。因此，路线池包括在沿着路线行进到目的地期间的不同时间为不同(例如，在当接近第一决策点时的第一时间不同于在通过第一决策点之后且当接近后续决策点时的后续时间)的路线数据。优选地，路线池包括仅关于在给定时间的一个即将到来的决策点的此数据。所述决策点可为将遇到的下一决策点，或至少为关于其而期望能够提供替代路线信息的下一显著决策点。在一些实施例中，第一决策点是将遇到的子网络的下一决策点，如先前所描述。一旦已通过第一决策点，且确定在通过决策点之后的用户的主要路线，便不再需要且可删除针对第一决策点的路线池数据。优选地，路线池不包括关于任何先前所通过决策点的数据。将由路线池提供的动态替代路线数据与可由根据本发明的特定实施例所使用的替代路线的子网络提供的静态替代路线数据进行对比。

所述方法可涉及在沿着主要路线从起点行进到目的地期间将用户的当前位置与主要路线的路段匹配，所述路段是到第一决策点的进入路段。

优选地，所述方法包括在当前位置通过第一决策点之后删除指示第一决策点处的预期路线的所存储路线池数据(即，指示所述决策点处的外出路段及其相关联路线的数据)。一旦已确立在通过第一决策点之后的用户的路线，便不再需要此数据，且可由关于在通过第一决策点之后沿着所确定的主要路线的新即将到来的决策点的对应数据来替换所述数据。换句话说，可刷新路线池数据。

所述方法可包括获得并存储指示关于决策点(无论是第一决策点还是后续决策点)获得的所述或每一替代路线的一或多个性质的数据。可将所述数据存储于路线池中。当采取路线时，所述性质可包含以下各项中的一或多者：沿着所述路线到达目的地处的所估计时间、所述路线上的交通状况及燃料消耗量。所述性质优选地包含一或多个动态改变的性质。当采取到目的地的路线时，此类性质可包含以下各项中的一或多者：沿着所述路线到达目的地处的所估计时间、所述路线上的交通状况及燃料消耗量。所述方法可包括在沿着主要路线行进期间动态地更新指示一或多个动态改变的性质的所存储数据。举例来说，可在用户沿着主要路线行进时以给定时间间隔来更新指示动态改变的性质的数据。如果出于建议而选择路线或所述路线变为主要路线，那么此可使得能够在适当时间将指示给定性质的数据输出给用户。所述方法可包括将所存储数据或从其导出的数据提供给用户。举例来说，可将针对替代路线的所存储数据的指示与主要路线的示意性表示上的可选择图标相关联地提供给用户。

在一些实施例中，所述方法可包括确定指示介于决策点(无论是第一决策点还是任何后续决策点)与目的地之间的替代路线的动态改变的性质的参数何时改变达大于预定阈值量(即，在沿着主要路线行进期间)，且当确定此改变时，重复以下步骤：获得从决策点到目的地的一或多个替代路线；及将指示路线中的所述或每一替代路线的数据存储于路线池中。可以关于所述组原始一或多个替代路线所描述的方式中的任一者来获得所述替代路线。据信，此类实施例本身为有利的。

根据本发明的第七方面，提供一种将指示路线选项的数据提供给行进穿过可导航网络的用户的方法，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述方法包括：

识别沿着由用户在起点与目的地之间行进的主要路线的即将到来的决策点，在所述决策点处存在多个外出路段，且产生介于所述决策点与所述目的地之间的至少一个替代路线；

将指示决策点处的到所述目的地的至少一个所产生替代路线的数据存储于至少一个数据库中；

获得并存储指示至少一个替代路线的至少一个动态改变的性质的数据；

在沿着主要路线行进期间针对所述至少一个替代路线更新所存储数据；及

确定所述至少一个替代路线的所述至少一个性质何时改变达大于预定量，且当确定此改变时，重复以下步骤：产生介于决策点与目的地之间的至少一个路线；及将指示至少一个所产生替代路线的数据存储于至少一个数据库中。

本发明扩展到一种用于执行根据本文中所描述的本发明的各方面或实施例中的任一者的方法的系统。

根据本发明的第八方面，提供一种用于将指示路线选项的数据提供给行进穿过可导航网络的用户的系统，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述系统包括：

用于识别沿着由用户在起点与目的地之间行进的主要路线的即将到来的决策点并产生介于所述决策点与所述目的地之间的至少一个替代路线的构件，在所述决策点处存在多个外出路段；

用于将指示决策点处的到所述目的地的至少一个所产生替代路线的数据存储于至少一个数据库中的构件；

用于获得并存储指示至少一个替代路线的至少一个动态改变的性质的数据的构件；

用于在沿着主要路线行进期间针对所述至少一个替代路线更新所存储数据的构件；及

用于进行以下操作的构件：确定所述至少一个替代路线的所述至少一个性质何时改变达大于预定量，且当确定此改变时，重复以下步骤：产生介于决策点与目的地之间的至少一个路线；及将指示至少一个所产生替代路线的数据存储于至少一个数据库中。

根据这些其它方面的本发明可包括关于本发明的其它方面中的任一者所描述的特征中的任一者，只要其不相互矛盾即可。

根据在其涉及确定替代路线的动态改变的性质的改变的各方面或实施例中的任一者中的本发明，所述改变的性质可为(举例来说)当采取所述路线时的所估计到达时间或燃料消耗量。

指示一或多个新产生的替代路线的数据优选地用于替换存储于至少一个数据库或“路线池”中的关于现有所产生替代路线中的一或多者及优选地每一者的对应数据。因此，所述方法优选地包括使用新替代路线数据来替换路线池中的对应现有数据。优选地删除现有替代路线数据。换句话说，除在已通过决策点时刷新路线池之外，还可在路线的动态改变的性质改变达大于给定量的情况下更新路线池。此可表明，(举例来说)由于当前交通状况，因此所述路线不再为最优的(例如，关于持续时间、预期燃料消耗量等)，且需要基于当前状况产生一组新的替代路线。此可帮助确保路线池总是含有指示可被认为是关于一或若干给定性质最优的替代路线的数据。

第五方面及第六方面的方法包括在用户接近第一决策点时将主要路线的至少一部分的示意性表示显示给用户的步骤，所述表示包括指示沿着主要路线的用户的当前位置的图标、指示沿着主要路线的第一决策点的位置的图标及(针对所述所产生替代路线中的一或多者或者每一者)指示所产生替代路线的存在的图标。优选地，提供指示决策点处的仅一个替代路线的存在的图标。本文中所使用的图标可为任何适合图形图标。图标可包括单个元素或一组元素。当所述当前位置在第一决策点的预定距离内时，可显示指示第一决策点处的所述或每一替代路线的存在的图标。因此，可因当前位置进入所述预定距离内而触发对图标的显示。将了解，将被指示给用户的替代路线可以任何适合方式(例如，基于路线的计时、是否已产生导航指令等)从针对第一决策点产生的多个替代路线中进行选择。

在一些实施例中，存储于路线池中的所述或每一替代路线是从决策点到目的地的为关于给定性质的最优替代路线的替代路线。所述性质可为所估计到达时间、距离或燃料消耗量不同路线可关于不同性质而被优化。此可使得能够向用户呈现关于可为所关注的多个不同性质中的一者而被优化的路线。所述方法可包括基于性质数据及优选地指示路线的一或若干动态改变的性质的数据而从路线池选择一或多个替代路线(将关于其的图标显示给用户)。举例来说，可建议关于至少一个性质(例如，时间、距离或燃料消耗量)而在存储于路线池中的多个替代路线当中为最优的替代路线。

所述方法可包括将所述或每一替代路线(任选地相对于主要路线)的性质的指示提供(例如，显示)给用户。所述性质可为路线的或与所述路线相关联的计时、长度、交通状况或燃料消耗量。可与主要路线的示意性表示相关联地显示所述指示。所述指示可与指示替代路线(所述指示与其相关)的存在的图标相关联。所述指示可包括指示性质的绝对值或者性质的值或状态(相对于主要路线)的数据。在一些实施例中，所述指示可仅为对相对于主要路线的差异的存在以及差异的性质的指示。举例来说，可提供路线比主要路线快或慢的指示(例如，通过对指示替代路线的图标进行适当着色)。此信息可不断地或间歇地显示。在一些实施例中，所述性质是动态改变的性质，且所述指示是基于所述性质的当前值或状态。

在一些实施例中，所述方法可包括显示指示所述或每一替代路线的性质的图标。此图标可与主要路线的示意性表示相关联。所述性质可从路线的计时、长度或燃料消耗量中进行选择。在一些实施例中，所述性质为动态改变的性质，例如当采取所述路线时的所估计到达时间或燃料消耗量或者沿着所述路线的交通状况。所述性质可为路线关于其而被优化的性质，例如所述路线关于所述性质而为最小成本路线。举例来说，所述路线可为与主要路线相比的较快路线、较短路线或较经济路线。所述性质可帮助用户理解为何所述路线引起其注意。指示交通状况的图标可展示替代路线受交通影响。

如上文所论述，在优选实施例中，所述方法包括存储指示关于决策点所获得且包含于路线池中的所述或每一替代路线的一或多个性质的数据。可将此数据存储于路线池中。所述数据可接着用于使得能够将指示路线的性质的数据提供给用户。如上文所论述，所述方法优选地包括在沿着主要路线行进期间动态地更新指示一或多个动态改变的性质的所存储数据。此可使得性质指示能够基于性质的当前状态或值及/或将被选择以供输出给用户的路线基于所述性质的所述当前状态或值。指示决策点处的替代路线的存在的所述或每一图标可由用户选择。当检测到由用户对替代路线图标的选择时，所述方法包括在地图上显示从第一决策点延伸到目的地的主要路线及替代路线的至少那些部分的表示。同时显示主要路线及替代路线的部分的表示。所述方法可另外包括显示从当前位置到第一决策点且(在一些实施例中)从起点到第一决策点的主要路线的一部分的表示。所述表示可包括指示当前位置的图标、指示第一决策点的位置的图标及指示目的地的位置的图标。

设想，在将指示多个替代路线的图标提供于主要路线的示意性表示上的情况下，用户可能够选择图标中的多个图标以导致连同主要路线一起在地图视图上将多个替代路线的可选择表示同时显示给用户。

在优选实施例中，所述方法可包括在地图上显示针对主要路线及所述或每一替代路线的比较数据。所述数据可包含指示针对所述路线的比较计时(例如，所估计到达时间)的数据。此可使用与可适用路线的表示相关联的图标(例如，举例来说指示与所述路线相关联的时间节省的图标)来实现。所述方法可包括显示指示一个或两个(或每一)路线的持续时间的数据。在一些实施例中，所述方法包括显示指示一个(例如，主要)路线的持续时间的数据，及指示相对于所述一个路线的所述或每一其它(例如，替代)路线的持续时间的数据。替代地或另外，可以类似于计时数据的方式显示关于路线的长度或燃料消耗量的比较数据。

主要路线及替代路线中的每一者的表示可由用户(例如，手动地)选择。举例来说，所述表示可由用户轻敲相关表示而选择。

当检测到用户已选择主要路线的表示时，此指示所述用户希望继续所述主要路线。所述方法可包括继续提供用于沿着现有路线引导用户的导航指令。因此，将导航指令输出给用户以用于在通过第一决策点之后沿着现有主要路线的延续引导用户。

当从用户接收到此指示时，所述方法可包括识别沿着主要路线的在其处存在多个外出路段的后续决策点、产生介于所述后续决策点与目的地之间的一或多个替代路线且将指示所述后续决策点处的到所述目的地的每一所产生替代路线的数据存储于路线池中。换句话说，可重复关于沿着主要路线的第一决策点所执行的步骤，此次是关于后续决策点。当所述当前位置在后续决策点的预定距离内时，可执行这些步骤。所述方法可包括使用指示后续决策点处的到目的地的每一所产生替代路线的所述所存储数据来替换路线池中针对沿着主要路线的第一决策点所确定的对应数据。

当确定用户已选择替代路线的表示从而指示所述用户希望采取替代路线时，所述方法包括采取替代路线作为新主要路线。所述方法包括将导航指令输出给用户以用于在通过第一决策点之后沿着新主要路线(即，先前替代路线)引导用户。所述方法可接着包括识别沿着新主要路线的在其处存在多个外出路段的即将到来的决策点、产生介于所述决策点与目的地之间的一或多个替代路线且将指示所述即将到来的决策点处的到所述目的地的每一所产生替代路线的数据存储于路线池中。当所述当前位置在即将到来的决策点的预定距离内时，可执行这些步骤。所述方法可包括使用指示沿着新主要路线的即将到来的决策点处的到目的地的每一所产生替代路线的所述所存储数据来替换路线池中针对沿着先前主要路线的第一决策点所确定的对应数据。

如上文所描述，且关于本发明的第三方面及第四方面，如果与针对第一决策点或任何后续决策点所确定的替代路线中的一者的动态改变的性质相关联的参数改变达大于预定阈值量，那么可另外刷新路线池数据。

在这些实施例中，在通过第一决策点之后沿着为现有主要路线的延续的主要路线的后续决策点或沿着新主要路线的即将到来的决策点可未必是下一决策点。如较早所描述，所述技术可仅应用于沿着路线的选定决策点。在一些实施例中，关于沿着(新)主要路线的至少下一决策点(其为在通过第一决策点之后的可导航网络的子网络的决策点，所述第一决策点为所述子网络的决策点)而执行所述方法。

将了解，可针对在通过先前决策点之后沿着所确定的主要路线的任何所要数目个其它后续决策点而重复本发明的第五方面及第六方面以及相关实施例的方法直到到达目的地为止。此(些)决策点可或可不为下一(且如果适用，连续)其它决策点。在其中可导航网络包括预定义子网络的一些实施例中，关于沿着主要路线的子网络的每一连续即将到来的决策点而执行所述方法直到到达目的地为止。针对每一后续决策点所获得的路线数据可用于更新路线池数据，例如替换针对先前决策点所获得的对应路线数据。

在未从用户接收到对主要路线或替代路线的任何选择的情况下，所述方法可包括再次将主要路线的至少一部分的示意性(例如，线性)表示连同当前位置图标及替代路线图标的表示一起显示给用户。根据本发明的较早所描述方面，所述系统可接着在无需由用户输入的情况下确定在用户通过决策点之后所采取的路径(例如，基于考虑路线池数据)。

如将根据本发明的第五方面及第六方面，所述系统将总是具有关于沿着当前主要路线的即将到来的决策点而可被呈现给用户的主要路线及至少一个替代路线。这给用户提供更充分参与路线选择过程的能力。

将了解，本文中根据本发明的方面中的任一者所产生及使用的替代路线可能并非比主要路线快或有利。本发明涉及给用户提供沿着主要路线的决策点处的至少一个替代路线以提供用户可能希望考虑的额外选项(无论其是否必要，举例来说，是否较快)。

根据本发明的方法中的任一者可至少部分地使用软件(例如，计算机程序)实施。本发明因此还扩展到包括计算机可读指令的计算机程序，所述计算机可读指令可执行以执行或致使导航装置及/或服务器执行根据本发明的各方面或实施例中的任一者的方法。

相应地，本发明扩展到一种包括此类软件的计算机软件载体，所述软件在用以操作包括数据处理构件的系统或设备时致使所述设备或系统连同所述数据处理构件一起执行本发明的方法的步骤。此类计算机软件载体可为非暂时性物理存储媒体(例如ROM芯片、CD ROM或磁盘)，或可为信号(例如经由电线的电子信号、光学信号或无线电信号(例如去往卫星)等等)。本发明提供一种机器可读媒体，其含有指令，所述指令在由机器读取时致使所述机器根据本发明的各方面或实施例中的任一者的方法操作。

不管其实施方案如何，根据本发明所使用的导航设备可包括处理器、存储器及存储于所述存储器内的数字地图数据。所述处理器与存储器协作以提供可在其中建立软件操作系统的执行环境。可提供一或多个额外软件程序以使得能够控制设备的功能性，且提供各种其它功能。本发明的导航设备可优选地包含导航卫星(例如，GPS(全球定位系统)或GLONASS)、信号接收及处理功能性。所述设备可包括可借以将信息中继到用户的一或多个输出接口。除了视觉显示器之外，所述输出接口还可包含用于可听输出的扬声器。所述设备可包括输入接口，所述输入接口包含一或多个物理按钮以控制所述设备的开/关操作或其它特征。

在其它实施例中，可至少部分地借助应用不形成特定导航装置的部分的处理装置来实施所述导航设备。举例来说，可使用经布置以执行导航软件的适合计算机系统来实施本发明。所述系统可为移动或便携式计算机系统(例如，移动电话或膝上型计算机)或可为桌上型系统。

在未明确陈述的情况下，将了解，本发明在其各方面中的任一者中可包含关于本发明的其它方面或实施例所描述的特征中的任何或所有特征，只要其不相互排斥即可。特定来说，尽管已描述可在所述方法中且由所述设备执行的操作的各种实施例，但将了解，可视需要且视情况在所述方法中且由所述设备以任何组合执行这些操作中的任何一或多者或者所有操作。

应注意，关于一或多个路段的短语“与……相关联”不应解释为要求对数据存储位置的任何特定限制。所述短语仅要求特征可关于路段被识别。因此，举例来说，关联可借助于参考潜在定位于远程服务器中的副文件而实现。

下文中陈述这些实施例的优点，且这些实施例中的每一者的其它细节及特征定义于所附独立权利要求书中且另外在以下详细描述中。

附图说明

现在将参考附图仅以实例方式描述本发明的实施例，其中：

图1是对可供导航装置使用的全球定位系统(GPS)的示范性部分的示意性图解说明；

图2是用于导航装置与服务器之间的通信的通信系统的示意图；

图3是对图2的导航装置或任何其它适合导航装置的电子组件的示意性图解说明；

图4是安装及/或对接导航装置的布置的示意图；

图5图解说明根据本发明的一个示范性实施例的用于产生决策点处的替代路线的方法；

图6及7图解说明分别使用常规及经改进电子罗盘技术而在起点与目的地之间获得的替代路线组；

图8图解说明根据本发明的一个示范性实施例的用于确定由用户在决策点处采取的路径的方法；

图9图解说明根据本发明的一个示范性实施例的用于给用户提供替代路线选项的方法；

图10a到10d图解说明可在图9的方法中的不同阶段处被输出给用户的示范性显示；且

图11a及11b图解说明可根据图9的实施例而被提供于主要路线的线性表示上的一些额外特征，而图11c及11d图解说明显示器可如何对较接近于其的决策点进行放大。

具体实施方式

现在将特定参考便携式导航装置(PND)来描述本发明的实施例。然而应记住，本发明的教示不限于PND而是替代性地普遍适用于经配置而以便携式方式执行导航软件以便提供路线计划及导航功能性的任何类型的处理装置。因此，由此得出，在本申请案的上下文中，导航装置打算包含(不限于)任何类型的路线计划与导航装置，而无论所述装置是体现为PND、交通工具(例如汽车)还是实际上为便携式计算资源(举例来说，便携式个人计算机(PC)、移动电话或执行路线计划与导航软件的个人数字助理(PDA))。

此外，参考道路路段描述本发明的实施例。应意识到，本发明还可适用于其它可导航路段，例如路径、河流、水道、自行车道、纤道、铁路线等等的路段。为便于参考，通常将这些路段称为道路路段。

从下文还将明了，本发明的教示甚至在用户不寻求关于如何从一点导航到另一点的指令而是仅希望被提供给定位置的视图的情况中具有效用。在此类情况中，由用户选择的“目的地”位置不需要具有用户希望从其开始导航的对应开始位置，且因此本文中对“目的地”位置或甚至对“目的地”视图的提及不应解释为意指路线的产生是必不可少的、必须发生到“目的地”的行进或甚至目的地的存在需要对应开始位置的指定。

记住以上附带条件，图1的全球定位系统(GPS)等等用于各种目的。一般来说，GPS是能够确定连续位置、速度、时间且在一些实例中能够确定无限数目个用户的方向信息的基于卫星无线电的导航系统。以前称作NAVSTAR，GPS并入以极精确的轨道绕地球轨道运行的多个卫星。基于这些精确轨道，GPS卫星可将其位置作为GPS数据中继到任何数目个接收单元。然而，将理解，可使用例如GLOSNASS、欧洲伽利略定位系统、罗盘定位系统或IRNSS(印度区域导航卫星系统)的全球定位系统。

当专门经装备以接收GPS数据的装置开始扫描GPS卫星信号的射频时实施GPS系统。在从GPS卫星接收到无线电信号之后，所述装置即刻经由多种不同常规方法中的一者来确定所述卫星的精确位置。在大多数实例中，所述装置将继续扫描信号直到其已获取至少三个不同的卫星信号(注意，使用其它三角测量技术仅借助两个信号是非正常确定所述位置，但可实现)为止。通过实施几何三角测量，接收器利用三个已知位置来确定其自身相对于卫星的二维位置。此可以已知方式完成。另外，获取第四卫星信号允许接收装置通过相同几何计算以已知方式来计算其三维位置。位置及速度数据可由无限数目个用户在连续基础上实时更新。

如图1中所展示，GPS系统100包括绕地球104轨道运行的多个卫星102。GPS接收器106从多个卫星102中的若干个卫星接收作为扩展频谱GPS卫星数据信号108的GPS数据。扩展频谱数据信号108连续从每一卫星102发射，所发射的扩展频谱数据信号108各自包括数据流，所述数据流包含识别所述数据流源自其的特定卫星102的信息。GPS接收器106通常需要来自至少三个卫星102的扩展频谱数据信号108以便能够计算二维位置。第四扩展频谱数据信号的接收使得GPS接收器106能够使用已知技术来计算三维位置。

转到图2，包括或耦合到GPS接收器装置106的导航装置200(即，PND)能够在需要的情况下经由移动装置(未展示)(举例来说，移动电话、PDA及/或具有移动电话技术的任何装置)建立与“移动”或电信网络的网络硬件的数据会话以便建立数字连接(举例来说，经由已知蓝牙技术的数字连接)。此后，通过其网络服务提供者，移动装置可建立与服务器150的网络连接(举例来说，通过因特网)。如此，可在导航装置200(在其单独行进及/或在交通工具中行进时，其可为且通常为移动的)与服务器150之间建立“移动”网络连接，以提供“实时”或至少非常“时新的”的信息网关。

使用(举例来说)因特网在移动装置(经由服务提供者)与另一装置(例如服务器150)之间建立网络连接可以已知方式完成。在此方面，可采用任何数目个适当数据通信协议，举例来说，TCP/IP分层协议。此外，移动装置可利用任何数目个通信标准，例如CDMA2000、GSM、IEEE 802.11a/b/c/g/n等。

因此，可看出，可利用可经由数据连接、经由(举例来说)导航装置200内的移动电话或移动电话技术而实现的因特网连接。

虽然未展示，但导航装置200当然可在导航装置200本身内包含其自身的移动电话技术(包含(举例来说)天线，或任选地使用导航装置200的内部天线)。导航装置200内的移动电话技术可包含内部组件，及/或可包含(举例来说)配备有必要的移动电话技术及/或天线的可插入卡(例如，订户身份模块(SIM)卡)。如此，导航装置200内的移动电话技术可(举例来说)经由因特网以类似于任何移动装置的方式的方式类似地在导航装置200与服务器150之间建立网络连接。

对于电话设置，可使用具有蓝牙能力的导航装置来与移动电话型号、制造商等的千变万化的频谱一起正确地工作，型号/制造商专用特定设置可存储于(举例来说)导航装置200上。可更新针对此信息所存储的数据。

在图2中，将导航装置200描绘为正经由可通过若干种不同布置中的任一者实施的类属通信信道152与服务器150通信。通信信道152类属地表示连接导航装置200与服务器150的传播媒体或路径。当在服务器150与导航装置200之间建立经由通信信道152的连接时，服务器150与导航装置200可进行通信(注意，此连接可为经由移动装置的数据连接、经由个人计算机的直接连接(经由因特网)等)。

通信信道152并不限于特定通信技术。另外，通信信道152并不限于单个通信技术；也就是说，信道152可包含使用多种技术的数个通信链路。举例来说，通信信道152可适于提供用于电、光学及/或电磁通信等的路径。如此，通信信道152包含但不限于以下各项中的一者或其组合：电路、例如电线及同轴电缆、光纤电缆等电导体、转换器、射频(RF)波、大气、自由空间等。此外，举例来说，通信信道152可包含例如路由器、中继器、缓冲器、发射器及接收器等中间装置。

在一个说明性布置中，通信信道152包含电话及计算机网络。此外，通信信道152可能够适应无线通信，举例来说，红外通信、射频通信(例如微波频率通信)等。另外，通信信道152可适应卫星通信。

通过通信信道152所发射的通信信号包含但不限于给定通信技术可需要或期望的信号。举例来说，所述信号可适于用于蜂窝式通信技术中，例如时分多址(TDMA)、频分多址(FDMA)、码分多址(CDMA)、全球移动通信系统(GSM)、通用包无线电服务(GPRS)等。数字及模拟信号两者可通过通信信道152而发射。这些信号可为通信技术可期望的经调制、经加密及/或经压缩的信号。

除可能未图解说明的其它组件之外，服务器150还包含操作地连接到存储器156且经由有线或无线连接158进一步操作地连接到大容量数据存储装置160的处理器154。大容量存储装置160含有大量导航数据及地图信息，且再者可为与服务器150分开的装置或可并入到服务器150中。处理器154进一步操作地连接到发射器162及接收器164以经由通信信道152向导航装置200发射信息及从导航装置200接收信息。所发送及接收的信号可包含数据、通信及/或其它所传播信号。可根据导航系统200的通信设计中所使用的通信要求及通信技术来选择或设计发射器162及接收器164。此外，应注意，发射器162与接收器164的功能可组合成单个收发器。

如上文所提及，导航装置200可经布置以使用发射器及接收器通过通信信道152发送及接收信号及/或数据而通过通信信道152与服务器150通信，注意这些装置可进一步用于与除了服务器150以外的装置通信。此外，根据导航装置200的通信设计中所使用的通信要求及通信技术来选择或设计发射器及接收器，且发射器与接收器的功能可组合成单个收发器，如上文关于图2所描述。当然，导航装置200包括本文中稍后将进一步详细描述的其它硬件及/或功能部件。

存储于服务器存储器156中的软件提供用于处理器154的指令且允许服务器150将服务提供给导航装置200。服务器150所提供的一个服务涉及处理来自导航装置200的请求及将导航数据从大容量数据存储装置160发射到导航装置200。服务器150可提供的另一服务包含使用针对所要应用的各种算法处理导航数据及将这些计算的结果发送到导航装置200。

服务器150构成导航装置200可经由无线信道存取的远程数据源。服务器150可包含定位于局域网(LAN)、广域网(WAN)、虚拟专用网络(VPN)等上的网络服务器。

服务器150可包含个人计算机(例如桌上型或膝上型计算机)，且通信信道152可为连接于个人计算机与导航装置200之间的电缆。替代地，个人计算机可连接于导航装置200与服务器150之间以在服务器150与导航装置200之间建立因特网连接。

导航装置200可具备经由信息下载而来自服务器150的信息，所述信息可不时地自动更新或在用户将导航装置200连接到服务器150时更新，及/或可在经由(举例来说)无线移动连接装置及TCP/IP连接在服务器150与导航装置200之间做出更恒定或更频繁连接时更动态。对于许多动态计算，服务器150中的处理器154可用于处置大部分处理需求，然而，导航装置200的处理器(图2中未展示)也可时常独立于到服务器150的连接而处置很多处理及计算。

参考图3，应注意，导航装置200的框图并不包含所述导航装置的所有组件，而是仅表示许多实例性组件。导航装置200定位于一外壳(未展示)内。导航装置200包含处理电路，所述处理电路包括(举例来说)上文所提及的处理器202，处理器202耦合到输入装置204及显示装置(举例来说，显示屏幕206)。虽然此处以单数参考输入装置204，但所属领域的技术人员应了解，输入装置204表示任何数目个输入装置，包含键盘装置、语言输入装置、触摸面板及/或用以输入信息的任何其它已知输入装置。同样，显示屏幕206可包含任何类型的显示屏幕，举例来说，液晶显示器(LCD)。

在一个布置中，将输入装置204的一个方面、触摸面板与显示屏幕206集成在一起以便提供集成式输入与显示装置，包含用以实现信息输入(经由直接输入、菜单选择等)及信息显示(通过触摸面板屏幕)两者的触摸垫或触摸屏输入250(图4)，使得用户仅需要触摸显示屏幕206的一部分来选择多个显示选择中的一者或者激活多个虚拟或“软”按钮中的一者。在此方面，处理器202支持连同触摸屏一起操作的图形用户接口(GUI)。

在导航装置200中，处理器202经由连接210操作地连接到输入装置204且能够从输入装置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可包含但不限于外部收听装置，举例来说耳塞式耳机。到I/O装置222的连接可进一步是到任何其它外部装置(例如用于免提操作及/或用于语音激活操作的汽车立体声单元)的有线或无线连接，(举例来说)用于连接到耳塞式耳机或头戴式耳机及/或(举例来说)用于连接到移动电话，其中所述移动电话连接可用于(举例来说)在导航装置200与因特网或任何其它网络之间建立数据连接，及/或经由(举例来说)因特网或某一其它网络建立到服务器的连接。

导航装置200的存储器214包括非易失性存储器的一部分(举例来说，以存储程序代码)及易失性存储器的一部分(举例来说，以在执行所述程序代码时存储数据)。所述导航装置还包括端口228，所述端口经由连接230与处理器202通信以允许向装置200添加可装卸式存储器卡(通常称为卡)。在正描述的实施例中，所述端口经布置以允许添加SD(安全数字)卡。在其它实施例中，所述端口可允许连接其它格式的存储器(例如紧凑式闪存(CF)卡、存储器棒、xD存储器卡、USB(通用串行总线)闪存驱动器、MMC(多媒体)卡、智能媒体卡、微驱动器等)。图3进一步图解说明处理器202与天线/接收器224之间经由连接226的操作连接，其中(举例来说)天线/接收器224可为GPS天线/接收器且如此将用作图1的GPS接收器106。应理解，由参考编号224标示的天线及接收器出于图解说明的目的示意性地组合，但天线及接收器可为分开定位的组件，且(举例来说)所述天线可为GPS贴片天线或螺旋形天线。

当然，所属领域的技术人员将理解，图3中所展示的电子组件是由一或多个电源(未展示)以常规方式供电。此类电源可包含内部电池及/或用于低电压DC供应器的输入或任何其它适合布置。如所属领域的技术人员将理解，预期图3中所展示的组件的不同配置。举例来说，图3中所展示的组件可经由有线及/或无线连接等等彼此通信。因此，本文中所描述的导航装置200可为便携式或手持式导航装置200。

另外，图3的便携式或手持式导航装置200可以已知方式连接或“对接”到例如自行车、摩托车、汽车或轮船(举例来说)等交通工具。接着，此导航装置200可从所对接的位置移除，以用于便携式或手持式导航用途。实际上，在其它实施例中，装置200可经布置以为手持式的从而允许用户进行导航。

参考图4，导航装置200可为包含集成式输入与显示装置206及图2的其它组件(包含但不限于内部GPS接收器224、处理器202、电力供应器(未展示)、存储器系统214等)的单元。

导航装置200可安放于臂252上，所述臂本身可使用吸盘254紧固到交通工具仪表板/窗/等。此臂252是导航装置200可对接到的对接站的一个实例。可通过(举例来说)将导航装置200搭锁连接到对接站的臂252而将导航装置200对接或以其它方式连接到臂252。接着，导航装置200可在臂252上旋转。为释放导航装置200与对接站之间的连接，(举例来说)可按下导航装置200上的按钮(未展示)。用于将导航装置200与对接站耦合及解耦的其它同样适合的布置为所属领域的技术人员众所周知的。

处理器202与存储器214协作以支持BIOS(基本输入/输出系统)，所述BIOS用作导航装置200的功能硬件组件与由所述装置执行的软件之间的接口。接着，处理器202从存储器214加载操作系统，所述操作系统提供其中可运行应用软件(实施所描述路线计划及导航功能性中的一些或全部)的环境。应用软件提供包含支持导航装置的核心功能(例如，地图查看、路线计划、导航功能及与其相关联的任何其它功能)的图形用户接口(GUI)的操作环境。在此方面，应用软件的部分包括视图产生模块。

在正描述的实施例中，导航装置的处理器202经编程以接收由天线224接收的GPS数据，并不时地，将所述GPS数据连同在接收所述GPS数据时的时间戳一起存储于存储器214内，以累积所述导航装置的位置的记录。可将如此存储的每一数据记录视为GPS方位；即，其为所述导航装置的位置的方位且包括纬度、经度、时间戳及准确度报告。

在一个实施例中，基本上在周期性基础上(举例来说，每5秒)存储数据。所属领域的技术人员将了解，其它周期将为可能的，且在数据分辨率与存储器容量之间存在平衡；即，当数据的分辨率因采取更多样本而增加时，需要更大存储量来保存数据。然而，在其它实施例中，所述分辨率可基本上为：每1秒、每10秒、每15秒、每20秒、每30秒、每45秒、每1分钟、每2.5分钟(或实际上，介于这些周期之间的任何周期)。因此，在装置的存储器内在各时间点处累积装置200的所在之处的记录。在一些实施例中，可发现，所捕获数据的质量在周期增加时降低，且尽管降级程度将至少部分地取决于导航装置200移动的速度，但大致15秒的周期可提供适合上限。尽管导航装置200通常经布置以累积其所在之处的记录，但在一些实施例中，其不记录行程的开始或结束时预定周期及/或距离的数据。此布置帮助保护导航装置200的用户的隐私，这是因为其可能保护他/她的家的位置及其它常去的目的地。举例来说，导航装置200可经布置以不存储行程的大致前5分钟及/或行程的大致前1英里的数据。

在其它实施例中，GPS可不在周期性基础上存储而是可在预定情况发生时存储于存储器内。举例来说，处理器202可经编程以在装置通过道路交叉点、道路路段改变或发生其它此情况时存储GPS数据。

此外，处理器202不时地经布置以将装置200的所在之处的记录(即，GPS数据及时间戳)上传到服务器150。在其中导航装置200具有将其连接到服务器150的永久或至少普遍存在的通信信道152的一些实施例中，数据的上传在周期性基础上发生(举例来说，其可为每24小时一次)。所属领域的技术人员将了解，其它周期是可能的，且可基本上为以下周期中的任一者：15分钟、30分钟、每小时、每2小时、每5小时、每12小时、每2天、每周或介于这些周期之间的任何时间。实际上，在此类实施例中，处理器202可经布置以在基本上实时基础上上传所在之处的记录，但此可必然意味着数据事实上以各发射之间的相对短的周期不时地发射且如此可更正确地被视为伪实时的。在此类伪实时实施例中，导航装置可经布置以在存储器214内及/或在插入于端口228中的卡上缓冲GPS方位且在已存储预定数目之后发射这些GPS方位。此预定数目可为大约20、36、100、200或介于其间的任何数目。所属领域的技术人员将了解，所述预定数目部分地由存储器214或端口228内的卡的大小支配。

在不具有普遍存在的通信信道152的其它实施例中，处理器202可经布置以在形成通信信道152时将记录上传到服务器152。举例来说，此可在导航装置200连接到用户的计算机时。再次，在此类实施例中，导航装置可经布置以在存储器214内或在插入于端口228中的卡上缓冲GPS方位。如果存储器214或插入于端口228中的卡变得充满GPS方位，那么导航装置可经布置以删除最旧GPS方位且如此其可被视为先进先出(FIFO)缓冲器。

在所描述的实施例中，所在之处的记录包括一或多个轨迹，其中每一轨迹表示在24小时周期内那一导航装置200的移动。每一24经布置以与日历天吻合，但在其它实施例中，情形不必如此。

通常，导航装置200的用户给出他/她对将装置所在之处的记录上传到服务器150的同意意见。如果不给出同意意见，那么不将记录上传到服务器150。导航装置本身及/或导航装置所连接到的计算机可经布置以向用户询问他/她对所在之处的记录的此使用的同意意见。

服务器150经布置以接收装置的所在之处的记录且将此记录存储于大容量数据存储装置160内以用于处理。因此，随着时间流逝，大容量数据存储装置160积累已上传数据的导航装置200的所在之处的多个记录。

如上文所论述，大容量数据存储装置160还含有地图数据。此地图数据提供关于道路路段的位置、所关注点的信息及通常在地图上找到的其它此信息。

现在将通过参考图5到11而描述本发明的实施例。

关于包括指示可导航网络(例如，道路网络)的路段的多个路段的电子地图数据而执行本发明的实施例。所述路段由节点连接。将方法描述为由与用户的交通工具相关联的便携式导航装置(PND)执行。然而，将了解，可使用其它形式的导航装置，例如集成式交通工具内装置。此外，导航装置可为具有导航功能性的任何移动装置。在其它实施例中，设想步骤中的至少一些步骤可由服务器执行，使得方法可由服务器单独地或与导航装置(例如，PND)组合地执行。

参考图5，根据步骤1，预定义可导航网络的子网络。此可通过列示网络的形成子网络的部分的路段的身份而执行。子网络由路段定义，所述路段形成介于网络的第一起点-目的地对之间的相交路线的网络的部分。

在步骤3中，在网络的第二起点-目的地对(其可或可不与第一起点-目的地对相同)之间产生主要路线。可紧接在从起点出发之前执行此步骤。主要路线的产生将实况数据(例如，基于当前交通状况的路段的当前穿越时间或速度)考虑在内。还产生第二起点-目的地对之间的替代路线，但此为选用步骤。

将了解，可以任一次序或甚至同时执行步骤1及3。现在将论述一些实例。

在一些实施例中，子网络为个人网络，所述个人网络由给定用户在起点与目的地之间先前行进穿过所述网络的路线的路段构成。这些路线可为用户在家与工作场所等之间频繁行进的路线。此类路线可由与用户的交通工具相关联的导航装置存储，所述导航装置在用户沿着起点与目的地之间的路线行进期间视情况记录位置数据，如此项技术中已知。

接着，主要路线可穿过介于与子网络的路线在其之间延伸的起点及目的地相同的起点与目的地之间的个人子网络而产生为最小成本路线(例如，关于时间、距离或燃料消耗量)。主要路线接着局限于子网络。在其它实施例中，可穿过介于与子网络的路线相同的起点-目的地对之间或替代地介于不同起点-目的地对之间的作为整体的可导航网络而产生主要路线。主要路线可为穿过作为整体的网络的最小成本路线。因此，可或可不接着通过参考子网络而确定主要路线。在一些实施例中，穿过作为整体的可导航网络但以偏向个人子网络的路段的方式确定主要路线。可以任何适合方式偏向子网络的路段。举例来说，此可通过将与包含于子网络中的每一路段相关联的成本操纵为相比于原本的情形较低而执行。在所产生主要路线并不局限于个人网络的情况下，可将所述路线添加到子网络以扩展子网络。

在其它实施例中，子网络由已在第一起点与目的地对之间计算的多个替代路线的路段构成。在一些实施例中，通过参考主要路线而产生替代路线。因此，第二起点-目的地对之间的主要路线产生(例如)为最小成本路线，且接着在第二起点-目的地对之间确定对主要路线的多个替代路线以提供其路段定义子网络的路线。第一起点-目的地对与第二起点-目的地对将接着为相同的。在其它实施例中，可在不参考主要路线的情况下产生子网络的替代路线，且反之亦然。

可通过参考穿越网络的路段的成本而计算替代路线。可通过参考所述路段的预期穿越时间而确定成本。如此项技术中已知，电子地图的每一路段与关于给定时间周期(例如，针对在一周的每一天的特定时间槽)的一或多个预期穿越时间或速度相关联。这些穿越时间是基于可适用时间周期的历史数据。这些穿越时间可用于产生将穿越时间考虑在内的多个路线。

在一些优选实施例中，使用开发为上文所描述电子罗盘项目的部分的技术来计算替代路线。根据电子罗盘技术，获得为起点与目的地之间的替代路径的汇总的“替代图”。方法涉及基于特定质量准则而对起点与目的地之间的所有替代路径进行过滤及评级。准则将替代图的路径之间的重叠的总距离考虑在内。期望路径不应在太大程度上重叠。因此，寻求使路径之间的重叠最小化。另外，寻求使与替代路径相关联的成本(相对于起点与目的地之间的最小成本路径)最小化。此通常涉及使路径的长度(相对于起点与目的地之间的最短路径)最小化。可将其它因素考虑在内以尝试限制由替代图表示的替代网络的复杂性，即路径及决策点的数目。

用于确定替代路线的电子罗盘技术中的主要改进涉及修改用于获得替代图的技术。特定来说，电子罗盘技术寻求改进用于确定替代图的所谓的“平线区(Plateau)”及“惩罚”方法。根据上文所提及的“经改进替代路线计划”出版物的第3章来描述这些方法。如根据“经改进替代路线计划”文件的第4章及“FP7—信息及通信技术：赠款协议号288094:D2.3.2—对用于环境友好型交通工具路线规划的算法的验证及实证评估：工作包WP2—用于交通工具路线规划的算法”文件的第5.3章所描述，在执行这些方法中的任一者之前引入修整(pruning)阶段以试图减小搜索空间，但是以限制对所得替代图的质量的任何负面影响的方式。另外，使用用以过滤平线区的新方法来获得提供最佳替代路径的平线区。通过对一组已计算路径选择惩罚因子而调谐惩罚方法，以便获得下一些最佳替代方案。

图6及7图解说明可由电子罗盘技术提供的改进。图6图解说明介于当前位置3与目的地5之间的主要路线1。还展示介于相同当前位置与目的地之间的若干个替代路线(以具有周期性点的较浅颜色来阴影化)。通过阻止主要路线的中心部分包含于替代路线中而获得这些替代路线。可看出，由于对与主要路线的重叠所加的约束，因此这些路线中的许多路线包含显著绕路。图7图解说明基于相同主要路线1在相同当前位置3与目的地5之间获得的替代路线的网络。可看出，这些替代路线为较用户友好的。图7因此提供起点目的地对之间的相交替代路线(其路段可提供本发明中所使用的子网络)的网络的实例。

将不进一步描述获得穿过网络的路线的子网络以供根据本发明使用的方式，这是因为可使用各种技术来获得路线，前提是定义可导航网络内的由属于起点与目的地之间的替代路线的路段构成的子网络。不管其如何获得，所述子网络均是在沿着路线行进期间不改变的预定静态网络。子网络包含在其处存在多个外出路段的若干个决策点。

在步骤5中，由导航装置将主要路线及替代路线的指示输出给用户以使得用户能够选择其所要路线。用户可手动地选择其所要路线，或此可在一旦用户开始从起点沿着路线行进时从所述用户的路径推断。可执行此的方式的细节将不进行描述，但可类似于用于确定用户在离开起点之后沿着路线在子网络的决策点处所采取的路径的技术(稍后所描述)。

在步骤7中，导航装置将导航指令输出给用户以沿着从起点采取的路线(“主要”路线)引导所述用户。假定用户采取主要路线，导航装置产生用于沿着原始主要路线引导用户的导航指令。如果用户采取替代路线，那么导航装置采取此路线作为新主要路线，且产生用于沿着那一路线引导用户的导航指令。将了解，不必要提供从起点的替代路线。

在步骤9中，导航装置确定沿着正行进的主要路线的将遇到的子网络的下一决策点。主要路线的从决策点到目的地的延续将已为已知的。导航装置现在产生从决策点到目的地的替代路线—步骤11。此替代路线是以偏向形成子网络的部分的路段的方式产生，且将关于网络上的状况的实况数据(例如，基于当前交通状况的路段的实况穿越时间或速度)考虑在内。此外，在产生替代路线时，沿着主要路线的从决策点到目的地的延续的第一路段被阻断，使得所述第一路段可不包含于所得所产生路线中。此帮助确保替代路线不同于主要路线、被迫在决策点处沿着不同外出路段。当用户的当前位置进入决策点的预定距离内时，可触发在决策点处产生替代路线的步骤。根据下文所描述的特定优选实施例，可将替代路线存储于导航装置的数据库(在本文中称为路线池)中。在这些布置中，可与从第一决策点外出的形成路线的部分的第一路段的指示相关联地存储替代路线。还可将主要路线的延续及形成路线的部分的第一决策点处的外出路段存储于路线池中或别处。

以此方式，提供从将遇到的子网络的下一决策点发出的主要路线及替代路线。由于替代路线已以偏向子网络的路段的方式产生，因此其将往往沿循子网络的路段，从而由形成子网络的到目的地的预定路线引导。此可帮助将路线朝向已被确定为有用或先前已行进的路线推进。然而，路线产生过程并不约束于仅沿循子网络的路段。因此，如果当前交通状况意味着沿着子网络的路段的流严重受影响，那么所产生的路线可绕过所述路段，但通常将在一旦已通过受影响区域时由于在路线产生过程期间偏向子网络的路段而朝向所述子网络移回。如果沿着子网络的路段的交通流严重受影响，那么此可使对路段的任何偏向失色，这是因为所述路段形成子网络的部分。在其中最初产生的从起点的主要路线及任选地替代路线是经产生以偏向子网络的实施例中，相同情形将适用于这些路线。

在步骤13中，导航装置将第一决策点处的替代路线的指示输出给用户以使得用户能够决定是采取替代路线，还是在主要路线上继续。如下文将更详细地描述，此可通过提供指示替代路线的存在的图标连同指示当前位置及在主要路线的线性表示上沿着主要路线的决策点的位置的图标而执行。主要路线的表示可呈路线栏或交通栏的形式，如下文所描述。当然，可使用引起用户对替代路线的存在的注意的任何其它方法。

确定用户在通过第一决策点之后是选择采取替代路线还是沿着原始主要路线继续—步骤14。此可以各种方式执行，且下文描述一些示范性方法。在一些实施例中，用户提供指示其所计划路线的输入。此可通常在用户到达第一决策点之前提供。在其它实施例中，导航装置通过在通过第一决策点之后考虑当前位置而推断由用户采取的路线。

如果用户已沿着原始主要路线继续，那么导航装置继续产生关于主要路线的导航指令。如果用户采取替代路线，那么在通过第一决策点之后导航装置将替代路线视为新主要路线，且提供关于新主要路线的导航指令。

在步骤15中，在通过第一决策点之后导航装置识别沿着主要路线的子网络的下一决策点。如果原始主要路线是用户在第一决策点处采取的路线，那么下一决策点可为在沿着原始主要路线行进时的子网络的下一决策点。然而，如果用户选择在第一决策点处采取替代路线，那么下一决策点将为沿着此新主要路线(即，对应于先前替代路线)将遇到的子网络的下一决策点。一旦当前位置在此下一决策点的预定距离内，导航装置便以与关于第一决策点相同的方式(视情况重复步骤11及13)来产生从决策点到目的地的替代路线。因此，偏向子网络的路段且以在决策点处阻断当前主要路线的外出路段的方式而产生替代路线。将替代路线的指示输出给用户。

再次，取决于由用户采取的路径，在通过决策点之后，现有主要路线在决策点处的延续或替代路线变为新主要路线，且输出关于主要路线的导航指令。识别沿着那一主要路线的子网络的下一决策点，且再次重复步骤11到15，以此类推直到子网络的下一决策点是目的地为止。如果无子网络的进一步决策点可在当前位置与目的地之间确定，那么视需要可使用较早所描述技术中的任一者来在当前位置与目的地之间定义替代路线的新子网络。可识别沿着主要路线的此子网络的第一决策点，且确定替代路线，以此类推重复步骤11到15，直到到达目的地或需要定义另一子网络为止。可定义新子网络，其中在当前位置与目的地之间存在某一距离，即，使得替代路线选项为期望的。此情形可在用户采取到城镇的环形道路上的转向的情况下出现，所述环形道路可不与在内城区中定义的介于起点与目的地之间的路线的原始子网络相交。

将了解，以此方式，关于子网络的决策点而产生替代路线，所述决策点可对应于其中有用替代方案可能存在的较显著决策点。对子网络的使用提供选择关于其而产生替代路线的决策点的方式，从而避免因过多信息而给用户增加负担。

主要路线的起点及目的地(即，第二起点目的地对)将通常对应于或接近于子网络替代路线的起点及目的地(即，第一起点目的地对)，例如在1km内。在沿着大致在第一起点目的地对之间延伸的路线行进时，子网络可提供适当引导。然而，不必要使起点目的地对与主要路线的起点目的地对重合，或不必要应使主要路线通过第一起点目的地对。举例来说，子网络可介于用户的家与工作场所位置之间。此网络仍可用于引导用户在家附近的位置到工作场所之间行进或从家行进到工作场所附近等，例如在家或工作场所附近的停车位置。

尽管上文已关于在每一决策点处产生单个替代路线而描述本发明的实施例，但将了解，可产生多个替代路线。此可通过在路线产生过程中在决策点处阻断现有主要路线的第一外出路段且还阻断任何已产生替代路线而实现。可接着向用户呈现多个替代路线，在子网络的下一决策点处从所述多个替代路线进行选择。

与一些已知技术相比，本发明可不总是在决策点处提供较快替代路线，而是提供使得能够视需要在沿着当前主要路线的子网络的每一即将到来的决策点处提供有用替代路线的方法，从而给用户提供较大选择以及控制其到目的地的路线的能力。

根据一些其它方面，本发明还提供用于自动确定由用户在决策点处采取的路径的方法。此类方法可连同较早所描述实施例一起使用，从而提供用以检测用户在第一决策点或后续决策点处是已在主要路径上继续还是已采取所述(或一)替代路径的方法。然而，还可独立于通过参考图5所描述的方法来使用所述方法。

将通过参考图8而描述本发明的此进一步方面。用户正沿着主要路线从起点行进到目的地。根据步骤20，导航装置检测沿着前面的主要路线在离开起点之后的即将到来的第一决策点。此决策点有利地为子网络的下一决策点，如关于图5的较早实施例所描述。然而，本发明的这些其它方面及实施例同样可适用于检测由用户穿过可导航路段的网络(关于其未预定义任何子网络)采取的路线。在那些情形中，决策点可为沿着主要路线的下一决策点，或至少为期望关于(举例来说)网络的较显著决策点而提供替代路线选项的决策点。

当用户的当前位置在所检测第一决策点的预定距离内时，导航装置形成可在决策点处采取的可能替代路线的路线池。导航装置识别决策点处的提供现有主要路线的延续的外出路段—步骤22。导航装置接着确定从第一决策点到目的地的至少一个替代路线—步骤24。理想地确定多个替代路线。每一替代路线是沿着第一决策点处的不同外出路段，且每一替代路线沿着不同于主要路线的延续沿着其通过的外出路段的外出路段通过。可使用关于通过参考图5所描述的本发明的较早方面而描述的方法来获得替代路线，所述方法涉及偏向子网络的路段及/或阻断决策点处的特定外出路段。然而，此并非必要的，且可独立于较早方面而执行本发明的此方面。在一些实施例中，每一替代路线是关于给定性质(例如所估计到达时间、长度或燃料消耗量)而被优化的路线。

导航装置将每一替代路线添加到路线池(即，将数据存储于所述路线池中)，所述替代路线与指示决策点处的形成路线的部分的外出路段的数据相关联—步骤26。因此，路线池将包括针对与每一替代路线相关联的路线的路段识别符，所述识别符可用于在路线池中查找可适用路线。针对所确定的每一替代路线产生导航指令。此使得能够在确定替代路线已由用户采取的情况下将所述替代路线立即用作新主要路线。

另外，可将指示路线的一或多个性质的数据确定并存储(任选地)于路线池中。所述性质可包含所估计到达时间、长度、交通状况或燃料消耗量。在用户沿着主要路线朝向目的地点行进时，更新此性质数据。以此方式，每一替代路线的任何动态改变的性质的当前值将为已知的。此类性质(例如，所估计到达时间、交通状况、燃料消耗量等)可用于将关于路线的当前信息显示给用户，或从所存储的多个替代路线选择路线以供输出给用户。

一旦用户的当前位置已通过第一决策点，导航装置便将当前位置与电子地图的路段匹配—步骤28。可使用此项技术中已知的任何地图匹配技术。导航装置获得路段的路段识别符，且确定路段识别符(ID)是否匹配第一决策点处的与主要路线的延续相关联的外出路段的路段识别符—步骤30。如果路段ID匹配与主要路线相关联的外出路段的路段ID，那么假定用户在通过第一决策点之后已沿着主要路线继续，且导航装置继续提供关于现有主要路线的导航指令—步骤31。如果路段ID不匹配与主要路线相关联的外出路段的路段ID，那么导航装置现在检查路段ID是否匹配与路线池中的替代路线相关联的外出路段中的任一者的路段ID—步骤32。如果路段ID确实匹配与替代路线相关联的外出路段中的一者的路段ID，那么导航装置在通过第一决策点之后采取那一路线作为新主要路线，且提供关于此路线的导航指令—步骤34。如果路段ID不匹配与包含于路线池中的替代路线相关联的外出路段中的任一者的路段ID，那么导航装置产生介于第一决策点与目的地之间的沿着当前位置已与其匹配的路段通过的新替代路线—步骤36。此可亦与产生从第一决策点的先前替代路线相同的方式来执行，且可涉及偏向子网络的路段。在通过第一决策点之后采取此新替代路线作为新主要路线，且产生并提供关于此新主要路线的导航指令。

以此方式，获得用于从第一决策点朝向目的地行进的新主要路线，所述新主要路线为原始主要路线的延续、所存储替代路线中的一者或新产生的替代路线。提供关于新主要路线的导航指令。

在通过第一决策点之后，导航装置接着识别沿着新主要路线的第二决策点。此可为子网络的下一决策点，或期望关于其而提供替代路线选项的任何其它即将到来的决策点(其可或可不为沿着路线的下一决策点)。接着视情况重复步骤22到36。识别提供从即将到来的第二决策点到目的地的主要路线的延续的路段。沿着第二决策点处的外出路段中的相应其它者产生一或多个替代路线，且与第二决策点处的路线沿着其通过的外出路段相关联地将指示每一路线的数据添加到路线池。此数据用于刷新关于第一决策点所存储的对应数据。产生关于每一替代路线的导航指令。将了解，一旦已通过第一决策点，便不再需要此数据，且路线池可被重新填充有关于将被考虑的下一决策点处(即，第二决策点)的可能路线的数据。通过考虑第二决策点处的包含当前位置的外出路段而识别在通过第二决策点之后的新主要路线，且产生关于此新主要路线的导航指令。再次，可识别沿着新主要路线的另一决策点，且以关于此决策点的路线数据来刷新路线池，并重复步骤22到36，以此类推直到到达目的地为止。以此方式，可给用户提供沿着路线所考虑的每一决策点(例如，子网络的每一决策点)处的至少一个替代路线选项。

在其中在沿着主要路线朝向决策点行进期间更新指示路线池中的替代路线的一或多个动态改变的性质的数据的一些实施例中，方法可涉及检测指示此性质的参数的改变何时超过给定阈值(例如，所估计到达时间推移达大于给定量或燃料消耗量增加达大于给定量)。此可接着触发对路线池的刷新，其中在决策点与目的地之间产生一组新的一或多个路线。指示每一路线及所述每一路线与其相关联的外出路段的数据将接着用于替换关于原始替代路线组的对应数据。每一路线可关于给定性质而被优化。以此方式，通过在当前状况已导致路线性质的显著改变的情况下更新路线池，维持包含在当前状况下为最优的一组替代路线的池可为可能的。此可关于在其处监视动态改变的路线性质的第一决策点或任何后续决策点而执行。

根据一些其它方面，本发明还提供用于给用户提供关于即将到来的决策点处的路线选项的信息使得用户能够手动地指示其计划在决策点处采取的路线的方法。再次，此类布置可利用使用关于图5所描述的方法(即，偏向子网络的路段)产生的主要路线及替代路线。然而，本发明的这些其它方面可(如关于图8所描述的方面)独立于较早方面而实施，且不需要待被预定义的子网络。

将通过参考图9、10a到10d及11a到11d而图解说明根据这些其它方面的本发明。这些方面涉及在沿着路线行进期间产生关于即将到来的决策点处的可能路线的路线池数据，如关于图8实施例所描述。

用户正沿着主要路线从起点行进到目的地。根据步骤40，导航装置检测沿着前面的主要路线在离开起点之后的即将到来的第一决策点。此决策点有利地为子网络的下一决策点，如关于图5的较早实施例所描述。然而，本发明的这些其它方面及实施例同样可适用于检测由用户穿过可导航路段的网络(关于其未预定义任何子网络)采取的路线。在那些情形中，决策点可为沿着主要路线的下一决策点，或至少为期望关于(举例来说)网络的较显著决策点而提供替代路线选项的决策点。

当用户的当前位置在所检测第一决策点的预定距离内时，导航装置形成可在决策点处采取的可能替代路线的路线池。导航装置识别决策点处的提供现有主要路线的延续的外出路段—步骤42。导航装置接着确定从第一决策点到目的地的至少一个替代路线—步骤44。可确定多个替代路线。每一替代路线是沿着第一决策点处的不同外出路段，且每一替代路线沿着不同于主要路线的延续沿着其通过的外出路段的外出路段通过。可使用关于通过参考图5所描述的本发明的较早方面而描述的方法来获得替代路线，所述方法涉及偏向子网络的路段及/或阻断决策点处的特定外出路段。然而，此并非必要的，且可独立于较早方面而执行本发明的此方面。导航装置将每一替代路线添加到路线池中。可使替代路线与指示决策点处的形成路线的部分的外出路段的数据相关联—步骤46。针对所确定的每一替代路线产生导航指令。此使得能够在替代路线由用户选择的情况下将所述替代路线立即用作新主要路线。

另外，可将指示路线的一或多个性质的数据确定并存储(任选地)于路线池中。所述性质可包含所估计到达时间、长度、交通状况或燃料消耗量。在用户沿着主要路线朝向目的地点行进时，更新此性质数据。以此方式，每一替代路线的任何动态改变的性质的当前值将为已知的。此类性质(例如，所估计到达时间、交通状况、燃料消耗量等)可用于将关于路线的当前信息显示给用户，或从所存储的多个替代路线选择路线以供输出给用户。在步骤48中，导航装置将下一决策点(即，第一决策点)处的替代路线的存在的指示显示给用户。所述指示是呈指示替代路线的存在的图标的形式。将关于指示决策点处的单个替代路线而图解说明本发明，其涉及沿着决策点处的外出路段的右转。设想可关于一决策点将多个替代路线呈现给用户。然而，可期望可能从针对所述决策点导出的多个替代路线选择单个替代路线以用于呈现给用户，以避免给用户增加负担。

在一些实施例中，呈现给用户的替代路线是基于路线的性质(例如燃料经济性、所估计到达时间或持续时间)而选择的。路线可为关于此性质而被优化的路线。路线池可包括多个替代路线，所述多个替代路线中的每一者关于不同给定性质而被优化。此可使得能够向用户呈现关于无论哪个所关注的性质(例如，燃料经济性或持续时间)而被优化的替代路线。

在一些实施例中，在沿着主要路线朝向决策点行进期间更新指示路线池中的替代路线的一或多个动态改变的性质的数据。此可执行为持续后台过程。方法可涉及检测指示此性质的参数的改变何时超过给定阈值(例如，所估计到达时间推移达大于给定量或燃料消耗量增加达大于给定量)。此可接着触发对路线池的刷新，其中在决策点与目的地之间产生一组新的一或多个路线。指示每一路线的数据将接着用于替换关于原始替代路线组的对应数据。每一路线可关于给定性质而被优化。以此方式，通过在当前状况已导致路线性质的显著改变的情况下更新路线池，维持包含在当前状况下为最优的一组替代路线的池可为可能的。此可关于在其处监视动态改变的路线性质的第一决策点或任何后续决策点而执行。在图10a中展示可根据本发明的实施例将替代路线呈现给用户的一种方式。导航装置显示2D导航地图50，从而图解说明前面的道路(当然，可替代地使用3D地图视图)。在显示器的右边，提供路线栏52，所述路线栏是从当前位置到超过第一决策点的点的前面的路线的线性表示。路线栏52包含当前位置图标54，及指示第一决策点56的图标。第一决策点56是沿着路线的下一决策点。还展示指示测速相机及加油站的位置的图标，但出于本发明的目的将不进一步描述这些。超过第一决策点，路线的区域58经阴影化且以图标60来注释，所述图标指示具有预期15分钟延迟的交通拥堵的存在。替代使用路线栏类型表示，路线的线性表示可展示从起点到目的地的整个主要路线。

在第一决策点56的位置处，提供图标，所述图标指示替代路线的存在。此图标呈指向右边的箭头的形式，其指示替代路线涉及右转。图标可经着色以指示替代路线是否比被沿循的主要路线快。将通过相对于主要路线采取所述路线而引发的时间节省(或时间惩罚)的指示可与所述箭头交替地显示。将了解，本发明寻求在沿着路线的每一决策点处或至少在于其处期望提供替代方案的每一决策点(例如，显著决策点、子网络的决策点等)处提供替代路线选项。因此，替代路线可能并非总是较快路线。目标是给用户提供较大选择，且对其所采取的路线进行控制。图标可经注释(例如使用红点或类似物)以展示存在影响路线的交通。

指示替代路线的图标可由用户(例如)通过触摸图标而选择。如果用户选择替代路线图标，那么方法涉及向用户呈现地图视图，所述地图视图图解说明主要路线及从第一决策点到目的地的替代路线连同路线的比较计时信息—步骤49。在图10b中展示一个此地图视图。地图包含从当前位置到目的地的主要路线的表示64、从第一决策点到目的地的替代路线的表示66、指示当前位置的图标68及指示目的地的图标70。替代路线表示及主要路线表示被不同地着色。图标74指示替代路线比主要路线快9分钟。与主要路线的表示相关联地提供图标76，所述图标指示存在具有预期15分钟的延迟的影响路线的一部分的交通拥堵。与主要路线的表示相关联地提供图标78，所述图标指示所述主要路线的持续时间(45分钟)。主要路线及替代路线的表示可由用户手动地选择以使得用户能够指示其希望采取哪一路线。

当检测到用户已选择主要路线的表示时，导航装置将忽略替代路线，且在用户通过第一决策点之后继续提供关于现有主要路线的导航指令—步骤50。显示器回复到具有相关联路线栏的2D地图视图，如图10c中所展示。路线栏不再展示第一决策点及其替代路线。当检测到用户已选择替代路线的表示时，导航装置将在通过第一决策点之后采取替代路线作为新主要路线，且将提供关于从那一点的替代路线的导航指令—步骤52。图10d图解说明可提供给用户的显示。2D地图视图现在将前面的路线展示为涉及在决策点处右转到替代路线上。

导航装置接着识别沿着新主要路线的下一决策点—步骤54。此将称为第二决策点。此可为子网络的下一决策点，或期望关于其而提供替代路线选项的任何其它即将到来的决策点(其可或可不为沿着路线的下一决策点)。视情况接着重复步骤42到54。识别提供从即将到来的第二决策点到目的地的主要路线的延续的路段。沿着第二决策点处的外出路段中的相应其它者产生一或多个替代路线，且将指示每一路线的数据添加到路线池。此数据用于刷新关于第一决策点所存储的对应数据。产生关于每一替代路线的导航指令。如果用户选择在主要路线上继续，那么新主要路线将为先前主要路线的从第一决策点的延续，或如果用户打算选择那一路线，那么新主要路线可为关于第一决策点所产生的替代路线。接着向用户呈现指示第二决策点处的替代路线的存在的图标(如图10a中)，所述图标可经选择以提供具有主要路线及替代路线的可选择表示的地图视图，如图10b中所展示。用户可接着视需要选择主要路线或替代路线的表示，从而针对路线的从第二决策点向前的部分而确定主要路线。再次，可识别沿着新主要路线的另一决策点，且针对新主要路线重新填充路线池以使得能够针对决策点将替代路线选项呈现给用户，以此类推。可重复此直到在目的地之前不存在其它决策点为止。

图11a及11b图解说明可用于在步骤48中在主要路线的线性表示上表示替代路线的一些替代特征。特定来说，这些其它实施例指示替代路线的已导致其被呈现给用户的性质(例如，所述路线是最快路线、最经济路线、最短路线等)。参考图11a，显示82展示当前位置图标84与目的地86之间的路线。图标指示决策点90处的替代路线的存在。所述图标指示路线比主要路线慢6分钟。图标80指示路线是可用的最具燃料效益路线。图11b是类似于图11a中所展示的视图的视图，然而，此次指示决策点92处的替代路线的图标89指示图标90，图标90告知用户所述替代路线是最快路线。

在一些实施例中，在当前位置进入即将到来的决策点的预定距离(例如，200m)内时，显示器可对决策点进行放大，且提供关于替代路线选项的一些额外细节。图11c图解说明在当前位置距决策点300m时的图11a与其相关的路线的此视图。此视图展示包含当前位置100及具有替代路线103的决策点的位置的指示的路线栏。决策点图标经着色以指示路线是较具燃料效益替代方案，且为此目的提供图标102。在右上角，提供关于路线相对于主要路线的计时及距离(即，展示所述路线慢6分钟，及短3.6km)的额外信息。图11d图解说明在距决策点310m处的图11b与其相关的路线的另一此视图。此视图展示包含当前位置104及具有替代路线108的决策点的位置的指示的路线栏。决策点图标经着色以指示路线是较快替代方案，且为此目的提供图标106。在右上角，提供关于路线相对于主要路线的计时及距离(即，展示所述路线快2.10分钟，及长2.9km)的额外信息。在缩放视图中，用户可不选择替代路线来获得地图视图，以避免接近于决策点的注意力分散。

在未明确陈述的情况下，将了解，本发明在其各方面中的任一者中可包含关于本发明的其它方面或实施例所描述的特征中的任何或所有特征，只要其不相互排斥即可。特定来说，尽管已描述可在所述方法中且由所述设备执行的操作的各种实施例，但将了解，可视需要且视情况在所述方法中且由所述设备以任何组合执行这些操作中的任何一或多者或者所有操作。

Claims (18)

1.一种穿过可导航网络产生路线的方法，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述方法包括：

定义所述可导航网络的子网络，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由所述电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点；

产生介于第二起点-目的地对的起点与目的地之间的主要路线；及

识别所述子网络的将沿着所述主要路线遇到的第一决策点，及使用路线产生过程来产生介于所述决策点与所述第二起点-目的地对的所述目的地之间的替代路线，在所述路线产生过程中，阻断所述主要路线的部分的从表示所述第一决策点的节点外出的至少第一路段且偏向表示所述子网络的路段的所述子集，并且其中所产生的所述替代路线不包含所偏向的表示所述子网络的路段的所述子集是可能的。

2.根据权利要求1所述的方法，其中所述子网络由介于所述第一起点-目的地对的所述起点与所述目的地之间的穿过所述可导航网络的一组先前所行进路线的路段表示。

3.根据权利要求1或2所述的方法，其包括定义所述可导航网络的所述子网络，且在路线产生过程中产生介于所述第二起点-目的地对之间的所述主要路线，所述路线产生过程偏向表示所述子网络的所述路段。

4.根据权利要求1所述的方法，其中所述子网络由在所述第一起点-目的地对的所述起点与所述目的地之间计算的一组多个替代路线的路段表示。

5.根据权利要求4所述的方法，其包括产生介于所述第二起点-目的地对的所述起点与所述目的地之间的所述主要路线，且将所述主要路线用于产生介于所述起点与所述目的地之间的所述组多个替代路线，所述主要路线及所述多个替代路线的路段表示所述子网络，其中所述第一起点-目的地对对应于第二起点-目的地对。

6.根据权利要求1或2所述的方法，其包括产生介于所述第二起点-目的地对的所述起点与所述目的地之间的至少一个替代路线。

7.根据权利要求6所述的方法，其中所述至少一个替代路线是使用偏向表示所述子网络的所述路段的路线产生过程而产生的。

8.根据权利要求1或2所述的方法，其包括当确定用户已选择在通过所述第一决策点之后在现有的所述主要路线上继续时，识别沿着所述主要路线的所述子网络的下一决策点，且使用路线规划过程来产生介于所述决策点与所述第二起点-目的地对的所述目的地之间的替代路线，在所述路线规划过程中，阻断所述主要路线的所述部分的从表示所述决策点的节点外出的至少第一路段且偏向表示所述子网络的路段的所述子集。

9.根据权利要求8所述的方法，其包括在用户选择采取从所述第二起点-目的地对的所述起点到所述目的地的所述替代路线而非所述主要路线时采取所述替代路线作为新主要路线、识别沿着所述新主要路线的所述子网络的所述下一决策点以及使用路线规划过程来产生介于所述决策点与所述第二起点-目的地对的所述目的地之间的替代路线，在所述路线规划过程中，阻断所述新主要路线的部分的从表示所述决策点的节点外出的至少第一路段且偏向表示所述子网络的路段的所述子集。

10.根据权利要求1或2所述的方法，其中在用户开始沿着所述主要路线行进之后执行产生介于所述子网络的沿着所述主要路线的决策点与所述第二起点-目的地对的所述目的地之间的替代路线。

11.根据权利要求10所述的方法，其中当所述用户的当前位置进入所述决策点的预定距离内时，执行所述产生替代路线。

12.根据权利要求1或2所述的方法，其中仅关于在沿着所述主要路线的当前位置前面的沿着所述主要路线的所述子网络的下一决策点而执行产生介于沿着所述主要路线的所述子网络的决策点与所述第二起点-目的地对的所述目的地之间的替代路线，且并非针对在用户的当前位置到达所述决策点之前在所述当前位置前面的任何后续决策点。

13.根据权利要求1或2所述的方法，其包括连同沿着所述主要路线的所述决策点的位置的指示及所述决策点处的所述替代路线的指示一起显示所述主要路线的示意性表示。

14.根据权利要求1或2所述的方法，其包括在用户选择采取从所述第二起点-目的地对的所述起点到所述目的地的所述替代路线而非所述主要路线时采取所述替代路线作为新主要路线，并且其进一步包括提供用于沿着所述主要路线及/或所述新主要路线引导用户的一组导航指令。

15.根据权利要求1或2所述的方法，其中所述方法是由便携式导航装置执行。

16.一种用于穿过可导航网络产生路线的系统，所述可导航网络由包括表示所述可导航网络的可导航元素的多个路段的电子地图表示，所述路段由节点连接，所述系统包括：

用于定义所述可导航网络的子网络的构件，所述子网络包括介于第一起点-目的地对的起点与目的地之间的穿过所述可导航网络的相交路线的网络，所述子网络由所述电子地图的路段的子集表示，且其中在其处存在路段的所述子集的两个或更多个外出路段的节点指示所述子网络的决策点；

用于产生介于第二起点-目的地对的起点与目的地之间的主要路线的构件；及

用于识别所述子网络的将沿着所述主要路线遇到的第一决策点及使用路线产生过程来产生介于所述决策点与所述第二起点-目的地对的所述目的地之间的替代路线的构件，在所述路线产生过程中，阻断所述主要路线的部分的从表示所述第一决策点的节点外出的至少第一路段且偏向表示所述子网络的路段的所述子集，并且其中所产生的所述替代路线不包含所偏向的表示所述子网络的路段的所述子集是可能的。

17.根据权利要求16所述的系统，其中所述系统是便携式导航装置。

18.一种非暂时性计算机可读介质，其存储有指令，所述指令在由导航装置的一或多个处理器执行时致使所述导航装置执行根据权利要求1到15中任一权利要求所述的方法。

Images