专利名称：用于车辆的路线规划系统的制作方法
技术领域：
本发明涉及车辆导航系统。
背景技术：
导航系 统配置成选择从起始位置到期望目的地的路线。导航系统通常选择针对行 驶时间、行驶距离或路线复杂性进行优化的路线。

发明内容
一种导航系统，包括配置成确定起始位置的位置检测装置和配置成接收期望目的 地的用户可操作的输入装置。存储介质存储地图数据库，所述地图数据库描述包括路线部 段的道路网络。每个路线部段由相应属性值和相应能量成本表征。处理器操作性地连接到所述位置检测装置以接收起始位置，操作性地连接到输入 装置以接收期望目的地，且操作性地连接到存储介质并配置成选择性地访问地图数据库。 处理器配置成根据预定优化算法来分析数据库中的路线部段，所述预定优化算法考虑路线 部段的属性值和能量成本两者以从数据库选择将起始位置和目的地互连的路线部段的组
I=I O因而，导航系统选择作为在行驶时间和燃料成本的竞争目标之间的平衡的路线。 也提供相应方法。所述方法包括接收起始位置；接收预定目的地；以及访问地图数据库。 所述地图数据库描述包括路线部段的道路网络。每个路线部段由相应属性值和相应能量成 本表征。所述方法还包括根据预定优化算法来分析数据库中的路线部段，所述预定优化 算法考虑路线部段的属性值和能量成本两者以从数据库选择将起始位置和目的地互连的 路线部段的组合。根据本发明的另一方面，一种修正导航系统的方法包括提供具有数据库和处理器 的现有导航系统。所述数据库描述具有路线部段的道路网络。路线部段具有相应属性值和 相应能量成本。所述处理器配置成执行属性值的优化分析以选择路线。所述方法还包括修 正处理器，使得优化分析包括属性值和能量成本。方案1. 一种用于选择从起始位置到目的地的路线的导航系统，所述系统包括用户可操作的输入装置，所述输入装置配置成接收目的地；存储介质，所述存储介质具有地图数据库，所述地图数据库描述包括路线部段的 道路网络；所述路线部段中的每个具有相应属性值和相应能量成本；处理器，所述处理器操作性地连接到输入装置以接收目的地，且操作性地连接到 存储介质并配置成选择性地访问地图数据库；所述处理器配置成根据预定优化算法来分析数据库中的路线部段，所述预定优化 算法考虑路线部段的属性值和能量成本两者以从数据库选择将起始位置和目的地互连的 路线部段的组合。
方案2.根据方案1所述的导航系统，其中，所述属性值是时间成本。方案3.根据方案1所述的导航系统，其中，所述优化算法求解将起始位置和目的 地互连的道路部段的可能组合中的具有最低数学表达式总和的道路部段的组合，所述数学 表达式包括属性值和能量成本。
方案4.根据方案3所述的导航系统，其中，所述数学表达式包括加权变量，属性值 和能量成本中的一个乘以所述加权变量。方案5.根据方案4所述的导航系统，其中，所述处理器配置成从输入装置接收加 权变量的值。方案6.根据方案1所述的导航系统，还包括输出装置；且其中，所述处理器配置成 将路线部段的组合传输给输出装置。方案7.根据方案1所述的导航系统，其中，数据库存储所述路线部段的属性值；且其中，所述处理器配置成从所存储的属性值确定道路部段的能量成本。方案8. —种确定从起始位置到预定目的地的优化路线的方法，所述方法包括接收起始位置；接收预定目的地；访问地图数据库，所述地图数据库描述包括路线部段的道路网络；对于每个路线 部段，所述地图数据库包括相应属性值和相应能量成本；以及根据预定优化算法来分析数据库中的路线部段，所述预定优化算法考虑路线部段 的属性值和能量成本两者以从数据库选择将起始位置和目的地互连的路线部段的组合。方案9.根据方案8所述的方法，其中，所述属性值是时间成本。方案10.根据方案8所述的方法，其中，所述优化算法求解将起始位置和目的地互 连的道路部段的可能组合中的具有最低数学表达式总和的道路部段的组合，所述数学表达 式包括属性值和能量成本。方案11.根据方案10所述的方法，其中，所述数学表达式包括加权变量，属性值和 能量成本中的一个乘以所述加权变量。方案12.根据方案11所述的方法，还包括从输入装置接收加权变量的值。方案13.根据方案8所述的方法，还包括将路线部段的组合传输给输出装置。方案14.根据方案8所述的方法，其中，数据库存储所述路线部段的属性值；且其中，所述方法还包括从所存储的属性值确定道路部段的能量成本。方案15. —种修正导航系统的方法，包括提供具有数据库和处理器的导航系统，所述数据库描述包括路线部段的道路网 络，路线部段具有相应属性值和相应能量成本，所述处理器配置成执行属性值的优化分析 以选择路线；以及修正处理器，使得优化分析包括属性值和能量成本。方案16.根据方案15所述的方法，其中，数据库存储属性值；且其中，所述方法还 包括修正处理器使得所述处理器从属性值确定能量成本。方案17.根据方案15所述的方法，其中，所述修正优化分析求解将起始位置和目 的地互连的道路部段的可能组合中的具有最低数学表达式总和的道路部段的组合，所述数 学表达式包括属性值和能量成本。
方案18.根据方案17所述的方法，其中，所述数学表达式包括加权变量，属性值和能量成本中的一个乘以所述加权变量。本发明的上述特征和益处、以及其它特征和益处从用于实现本发明的最佳模式的 以下详细描述结合附图显而易见。


图1是具有混合动力电动动力系和导航系统的车辆的示意性部分剖切正视图；图2是图1的导航系统的示意图；图3是道路网络的示意性描述；图4是显示描述图3的道路网络的数据的表格；图5是示出了图4的道路网络中的互连的表格；图6是显示描述图3的道路网络的数据的表格；图7是图1和2的导航系统的方法和示例性控制逻辑的流程图；和图8是示出了现有软件的修正以实现图7的方法的功能的数据流图。
具体实施例方式参考图1，机动车辆10包括车身14。多个车轮18相对于车身14旋转地安装且在 路面上支撑车身14，如本领域技术人员理解的那样。车辆10还包括动力系22。在所示实 施例中，动力系22包括电动马达26，电动马达26具有操作性地连接到至少一个车轮18的 转子(未示出)以将扭矩传输给车轮，以便推进车辆10。动力系22还包括蓄电池30，蓄电 池30操作性地连接到马达26且配置成将电能选择性地供应给马达26。在所示实施例中，动力系22还包括发动机34和发电机38。发动机34操作性地 连接到发电机38以驱动发电机38，这使得发电机38产生电能，如本领域技术人员理解的 那样。发电机38操作性地连接到蓄电池30以将电能供应给蓄电池，以便给蓄电池30再次 充电。发电机38还操作性地连接到马达26，以便将电能选择性地供应给马达。动力系控 制模块(未示出)根据驾驶员动力指令、蓄电池30的电荷状态等来控制发电机38、马达26 和蓄电池30之间的电能流。在所示实施例中，动力系22串联混合动力电动动力系。在示例性实施例中，动力 系22是插入式混合动力电动动力系，其中，蓄电池30可由车外电源(例如，电网)再次充 电。在本发明的范围内可采用其它动力系配置。例如，在本发明的范围内，动力系22可具 有并联混合动力配置，动力系22可具有蓄电池电动配置，动力系22可不包括任何电动马达 且使得发动机34经由多速变速器连接到车轮18，等等。车辆10还包括相对于车身14安装的导航系统42。参考图2，其中相同的附图标 记指代与图1相同的部件，导航系统42包括处理器44、位置检测装置(在所示实施例中是 全球定位系统(GPS)接收器50)、数据输入/输出装置52 (例如，触摸屏显示器)、以及数据 存储介质54。数据存储介质54存储描述道路网络的地图数据库。道路网络的示例性部分在图3 中以64示出。参考图3，道路网络64包括多条道路66A-Q，其中每条道路在两个节点附-ΝΙΟ 之间延伸。每个节点m-ΝΙΟ将至少三条道路66A-Q互连，因而表示路线可以变化的点。例如，在道路66M上行驶的车辆10继续在道路66M上行驶，直到车辆到达节点附或N4。在节点Ni，道路66M上的车辆10可采用道路66C或道路66A。示例性节点包括十字路口、交叉
路口等。地图数据库包括描述道路网络64及其属性的数据，所述属性包括地理属性，例如 道路66A-Q和节点m-ΝΙΟ的位置。道路名称和街道地址以及纬度和经度也被编码为地图数 据库的一部分。每条道路66A-Q的属性包括车辆10或车辆10的驾驶员在其上行驶招致的 成本。每条道路的成本包括时间(即，车辆10行驶节点之间的道路长度所花费的时间量) 和距离(即，车辆在节点之间从道路一端行驶到另一端的距离)。参考图4，对于每条道路 66A-Q，地图数据库还包括距离成本值和时间成本(本文也称为“估计行驶时间”)。每条道 路的估计行驶时间是车辆行驶道路长度所花费的时间量的估计值，且可基于各种因素，例 如道路的法定速度极限值、道路的平均交通堵塞程度等。地图数据库还包括在图5的矩阵中示出的信息。参考图5，矩阵示出了两个节点是 否由道路直接连接，如果是，由哪条道路直接连接。因而，例如，节点N4和节点mo由道路 66Q连接。参考图6，对于每条道路66A-Q，地图数据库还包括相应能量成本。每条道路的能 量成本是沿道路长度推进车辆10必须花费的能量的估计值，且可基于各种因素，例如道路 的法定速度极限值、道路的平均交通堵塞程度(例如，启动和停止操作的次数)、道路条件 (例如，铺路面的或未铺路面的)、道路地形(上坡、下坡等)。应当注意的是，道路的估计 行驶时间和道路的估计能量成本可随着在道路上的行驶方向变化。因而，在本发明的范围 内，对于每条道路，地图数据库可包括两个估计行驶时间和两个估计能量成本，一个估计行 驶时间和一个估计能量成本用于以一个方向行驶，另一个估计行驶时间和估计能量成本用 于以另一个方向行驶。在本发明的范围内可采用道路属性数据的其它变化。图7示意性地示出了确定路线的方法，且表示导航系统的处理器44的示例性控制 逻辑。参考图2和7，在步骤100，处理器44接收起始位置。如本领域技术人员理解的那样， GPS接收器50配置成基于卫星信号来确定车辆10的地理位置。GPS接收器50操作性地连 接到处理器44且配置成将车辆10的位置传输给处理器44。由GPS接收器50传输给处理 器44的车辆10的位置通常是在步骤100接收的起始位置。替代地，在本发明的范围内，处 理器44可经由输入装置52或用户接口从车辆操作者接收起始位置。在步骤104，处理器44从输入/输出装置52接收期望目的地。本领域技术人员将 认识到，在本发明的范围内可采用各种其它输入装置，例如麦克风(带有语音识别硬件和 软件)、键盘等。在步骤108，处理器经由输入/输出装置52从车辆用户接收加权变量值。道路网络64限定车辆10可从起始位置行驶到目的地的多个可能路线。例如，如果 车辆10处于节点m (S卩，如果在步骤100接收的起始位置是节点N1)且车辆10驾驶员期 望行驶到节点Nio (即，在步骤104接收的目的地是节点mo)，一个可能路线包括道路66C、 节点N5、道路66H、节点N8、道路66K、节点N9和道路66L。另一个可能路线包括道路66M、 节点N4、道路66P、节点N7和道路66J。可能路线是将起始位置和目的地互连的道路和/或其部分的组合，因而道路 66A-Q是路线部段。因而，路线的时间成本是构成路线的路线部段的时间成本的总和。例 如，由道路66C、66H、66K和66L构成的路线的估计行驶时间是道路66C、66H、66K和66L的估计行驶时间的总和，即4. 112秒。类似地，路线的能量成本是构成路线的路线部段的能量 成本的总和。在步骤112，处理器44访问由介质54存储的地图数据库且根据预定优化算法来分 析道路部段66A-Q，以选择将在步骤100接收的起始位置和在步骤104接收的目的地互连的 路线部段的组合。优化算法考虑道路部段66A-Q的时间成本和能量成本两者，从而得到的 路线部段的组合或路线具有所需的低总行驶成本和总能量成本。 在步骤112的分析可包括简约函数(parsimony function)，所述简约函数排除任 何可行路线不可能触及的节点。示例性简约函数估计包围围绕起始点、目的地和行程的沿 途点的凸包的圆的直径。去除在该圆之外且距选择用于该行程的任何点超过半径的引导图 中的任何节点。因而，例如，道路网络64可包括大地理区域中的所有公共道路，且简约函数 可将有关道路和节点缩减为如图3所示的道路和节点。在所示实施例中，优化算法求解将起始位置和目的地互连的道路部段的可能组合 中的具有最低数学表达式总和的道路部段的组合，所述数学表达式包括时间成本和能量成 本。该问题表示为 其中，c (x，u)是从节点χ行驶到节点u的估计时间成本，U (χ)是在给定当前节点 时包括可行的下一节点的集合，E(x，u)是从节点χ行驶到节点u的估计能量成本，λ是在 步骤108接收的加权变量。因而c(X，u)是从节点χ延伸到节点u的道路的估计时间成本， E (x, u)是从节点χ延伸到节点u的道路的估计能量成本。当λ等于0时，产生具有最低时间成本的路线。当λ大于0时，那么将产生将能 量使用相对于时间成本进行平衡的路线。因而，车辆操作者通过在步骤108分配加权变量 值来确定在选择路线时能量成本的重要性。替代方案是使用初始成本和能量成本之间的相 对加权 (表达式2)其中，α是在步骤108接收的加权变量，且在0和1之间。当α是1时，产生具 有最低时间成本的路线。当α是0时，那么将产生最小能量路线。在步骤116，处理器44将在步骤112确定的路线经由输出装置(例如，输入/输出 装置52)传输给车辆10的驾驶员。本领域技术人员将认识到在步骤116用于将路线传输 给车辆驾驶员的各种不同格式，例如，驾驶指令的列表、突出方案的地图等。在示例性实施 例中，所述方案随时间传输，其中，在车辆沿包括所述方案的路线前进时基于“路口转弯提 示(turn by turn) ”提供驾驶指令。处理器44还可以确定在步骤112确定的路线的总能量成本和总时间成本，并在步骤116将总能量成本和总时间成本传输给输出装置。在所示实施例中，导航系统42的输入装置和输出装置组合成单个装置52，可例如 是触摸屏显示器，用户可通过触摸屏显示器借助于触摸所述屏幕输入信息。然而，在本发明 的范围内，导航系统可包括独立的输入和输出装置。本领域技术人员将认识到在本发明的 范围内可采用的各种其它输入装置，例如麦克风(带有语音识别硬件和软件)、键盘等。本 领域技术人员将认识到在本发明的范围内可采用的各种其它输出装置，例如没有触摸屏功 能的液晶显示器(LCD)屏幕、音频扬声器等。扬声器可以与视觉显示器结合或者取代视觉 显示器使用。在所示实施例中，地图数据库存储用于每条道路的单个能量成本和单个行驶成 本；然而，在本发明的范围内，估计行驶时间和估计能量成本能以本发明范围内的任何格式 存储，例如查询表、公式等。例如，在本发明的范围内，能量成本可以是可应用于任何车辆的 无单位因子。能量成本可以从存储在数据库中的其它信息估计。例如，能量成本可以从道 路部段的速度极限值、道路部段的类别(例如，有铺筑面的、碎石路等)等。应当注意的是， 在本发明的上下文中，“处理器”可包括协作执行本文所述操作的多个处理器。
本领域技术人员将认识到在本发明范围内可采用的各种数据存储介质。例如，数 据存储介质54可以是硬盘驱动器、只读存储器、可写只读存储器、光学介质(例如，光盘) 等。应当注意的是，在本发明的上下文中，“数据存储介质”可包括多个存储介质。例如，在 本发明的范围内，地图数据库可以分配在两个或更多的数据存储介质上。参考图8，在示例性实施例中，导航系统42从现有导航系统140生成，导航系统 140具有地图数据库114，地图数据库114包括图4的时间成本和距离成本，但是不包括图6 的能量成本。此外，在现有导航系统140中，处理器(在图2中以44示出)用软件148编 程，软件148采用优化算法，所述优化算法根据以下表达式使用来自于数据库144的时间成 本或距离成本 (表达式3)因而，具有原始软件148的现有导航系统140产生具有最低时间成本或最低距离 成本的从起始位置到目的地的路线，但是不考虑与路线部段相关联的能量成本。修正现有 导航系统140的方法包括针对每个路线部段产生能量成本数据152 (例如，图6的数据)。 在所示实施例中，能量成本数据152由算法156使用道路数据库144和描述车辆(在图1 中以10示出)特性的数据160来产生。例如，车辆特性160可包括车辆10质量、车辆10的阻力系数等。来自于算法156 所采用以确定能量成本的道路数据库的数据可包括例如道路的法定速度极限值、道路的平 均交通堵塞程度(例如，启动和停止操作的次数)、道路条件(例如，铺路面的或未铺路面 的)、道路地形(上坡、下坡等)。类似地，在本发明的范围内，数据库144可包括无单位道 路类别，能量成本可从无单位道路类别估计或以其它方式确定。软件148的添加物164提供表达式1或2的道路成本函数，使得由系统42产生的路线168将能量成本与其它属性(例如时间成本)进行平衡。再次参考图2，应当注意的是，虽然导航系统42的所有部件显示在车辆10上，但 是在本发明的范围内，导航系统42的部件中的一些或全部可以在车辆之外。例如，在本发 明的范围内，处理器44和数据存储介质54可以在车辆10之外的远程位置；无线通信系统 (例如，卫星中继系统)能将处理器44操作性地连接到GPS、触摸屏显示器等。虽然导航系统42显示和描述为安装在车辆10中，但是应当注意的是，在本发明的 范围内，导航系统可以安装在车辆中，也可以不安装在车辆中。例如，在一个示例性实施例 中，导航系统42是基于互联网的。更具体地，处理器44经由互联网操作性地连接到输入和 输出装置52。在这种实施例中，起始位置从输入装置而不是GPS接收器接收。在导航系统42的基于互联网的型式时，描述车辆10特性的数据160可以由系统 用户经由输入装置输入，或者替代地，存储介质54可以代表用户存储数据160。由于导航系 统42的基于互联网的型式将可能具有带有不同车辆特性的多个用户，因而处理器44可以 被编程为基于独特识别符(例如，电子邮件地址和密码)检索具体用户的车辆数据160。虽然已经详细描述用于实施本发明的最佳模式，但是本发明所属领域技术人员将 认识到在所附权利要求范围内的用于实践本发明的各种替代设计和实施例。
权利要求
一种用于选择从起始位置到目的地的路线的导航系统，所述系统包括用户可操作的输入装置，所述输入装置配置成接收目的地；存储介质，所述存储介质具有地图数据库，所述地图数据库描述包括路线部段的道路网络；所述路线部段中的每个具有相应属性值和相应能量成本；处理器，所述处理器操作性地连接到输入装置以接收目的地，且操作性地连接到存储介质并配置成选择性地访问地图数据库；所述处理器配置成根据预定优化算法来分析数据库中的路线部段，所述预定优化算法考虑路线部段的属性值和能量成本两者以从数据库选择将起始位置和目的地互连的路线部段的组合。
2.根据权利要求1所述的导航系统，其中，所述属性值是时间成本。
3.根据权利要求1所述的导航系统，其中，所述优化算法求解将起始位置和目的地互 连的道路部段的可能组合中的具有最低数学表达式总和的道路部段的组合，所述数学表达 式包括属性值和能量成本。
4.根据权利要求3所述的导航系统，其中，所述数学表达式包括加权变量，属性值和能 量成本中的一个乘以所述加权变量。
5.根据权利要求4所述的导航系统，其中，所述处理器配置成从输入装置接收加权变 量的值。
6.根据权利要求1所述的导航系统，还包括输出装置；且其中，所述处理器配置成将路 线部段的组合传输给输出装置。
7.根据权利要求1所述的导航系统，其中，数据库存储所述路线部段的属性值；且其中，所述处理器配置成从所存储的属性值确定道路部段的能量成本。
8.一种确定从起始位置到预定目的地的优化路线的方法，所述方法包括接收起始位置；接收预定目的地；访问地图数据库，所述地图数据库描述包括路线部段的道路网络；对于每个路线部段， 所述地图数据库包括相应属性值和相应能量成本；以及根据预定优化算法来分析数据库中的路线部段，所述预定优化算法考虑路线部段的属 性值和能量成本两者以从数据库选择将起始位置和目的地互连的路线部段的组合。
9.根据权利要求8所述的方法，其中，所述属性值是时间成本。
10.一种修正导航系统的方法，包括提供具有数据库和处理器的导航系统，所述数据库描述包括路线部段的道路网络，路 线部段具有相应属性值和相应能量成本，所述处理器配置成执行属性值的优化分析以选择 路线；以及修正处理器，使得优化分析包括属性值和能量成本。
全文摘要
本发明涉及用于车辆的路线规划系统。一种导航系统，包括配置成接收期望目的地的用户可操作的输入装置。存储介质存储地图数据库，所述地图数据库描述包括路线部段的道路网络。对于每个路线部段，所述地图数据库包括相应属性值和相应能量成本。处理器配置成根据预定优化算法来分析数据库中的路线部段，所述预定优化算法考虑路线部段的属性值和能量成本两者以从数据库选择将起始位置和目的地互连的路线部段的组合。
文档编号G01C21/34GK101881624SQ20101017602
公开日2010年11月10日 申请日期2010年5月5日 优先权日2009年5月5日
发明者C·A·马索尔, E·D·小塔特 申请人:通用汽车环球科技运作公司