导航装置和使用该导航装置确定最佳行进路线的方法

1.一种导航装置，包括：
当前位置检测单元，用于响应用户的到指定目的地的最佳行进路 线的请求，检测可移动物体的当前位置信息；
当前线路检测单元，用于从所述当前位置检测单元接收所述当前 位置信息，以及从所存储的地图数据检测与所述当前位置一致的当前 线路信息；
邻近线路检测单元，用于从所述当前线路检测单元接收所述当前 线路信息，以及从所述所存储的地图数据检测所述当前线路的邻近线 路的信息；
邻近线路信息存储单元，用于在此接收和存储来自所述当前线路 检测单元和所述邻近线路检测单元的检测结果；
选定线路信息存储单元，用于存储从所述邻近线路信息存储单元 中存储的邻近线路的信息选出的最佳邻近线路信息；
路线计算单元，用于从所述邻近线路信息存储单元接收当前线路 信息和所述邻近线路的信息，使用指定给所述当前线路信息和所述邻 近线路的信息的每一个的行进方向的预定加权值，计算从所述可移动 物体的当前位置到每个邻近线路的累积行进时间，选择最佳邻近线路 信息，并将所述选定的最佳邻近线路信息存储在选定线路信息存储单 元中，以及然后，从选定线路信息存储单元获得当前路线信息，在邻 近线路信息存储单元中存储邻近当前路线的路线信息，基于该当前路 线信息执行下一计算；以及
最佳路线检测单元，用于确定所述选定线路信息存储单元是否存 储包括目的地信息的所述线路信息，从所述选定线路信息存储单元检 测包括所述目的地信息的线路信息以及检测从包括所述目的地线路到 出发点的所述邻近线路的信息，并输出最佳行进路线。
2.如权利要求1所述的导航装置，其中，所述邻近线路检测单元 根据存储在所述地图数据中的每个线路的位置和方向信息，在所述目 的地方向中检测与所述当前线路相邻的所有线路的信息。
3.如权利要求1所述的导航装置，其中，所述路线计算单元使用 加权值计算从所述当前线路到相应的邻近线路的累积行进时间，该加 权值指定给所述出发点范围内的节点并且高于所述预定加权值。
4.如权利要求3所述的导航装置，其中，所述路线计算单元根据 所述加权值设定虚拟时间信息，该加权值指定给所述出发点范围内的 节点并高于所述预定加权值，并根据所述设定的虚拟时间信息，计算 从所述当前线路到所述相应的邻近线路的累积行进时间。
5.一种用于使用导航装置，确定最佳行进路线的方法，包括步骤：
a)响应用户的到指定目的地的最佳行进路线的请求，检测可移动 物体的当前位置信息；
b)从所存储的地图数据检测与所述可移动物体的当前位置一致的 当前线路信息；
c)从所述地图数据，检测在所述目的地方向中，与所述当前线路 的邻近线路的信息；
d)使用指定给所述当前线路信息和所述邻近线路的信息的每一个 的行进方向的预定加权值，计算从所述可移动物体的当前位置到每个 邻近线路的累积行进时间；
e)根据所计算的每个邻近线路的累积行进时间，从由所述地图数 据检测的所述邻近线路信息选择一个最佳邻近线路信息；以及
f)重复步骤c)至e)，顺序地从所述选定最佳邻近线路信息检测 所述最佳行进路线，直到最佳路线检测单元检测到包括目的地信息的 相邻线路信息，以及输出所检测的最佳行进路线。
6.如权利要求5所述的使用导航装置确定最佳行进路线的方法， 其中，在步骤c)，根据存储在所述地图数据中的每个线路的位置和方 向信息，在所述目的地方向中检测与所述当前线路相邻的所有线路的 信息。
7.如权利要求5所述的使用导航装置确定最佳行进路线的方法， 其中，在步骤d)，使用加权值计算从所述当前线路到相应的邻近线路 的累积行进时间，该加权值指定给所述出发点范围内的节点并高于所 述预定加权值。
8.如权利要求7所述的使用导航装置确定最佳行进路线的方法， 其中，在步骤d)，根据所述加权值设定虚拟时间信息，该加权值指定 给所述出发点范围内的节点并高于所述预定加权值，并根据所述设定 的虚拟时间信息，计算从所述当前线路到所述相应的邻近线路的累积 行进时间。

技术领域
本发明涉及导航装置，并且更具体地说，涉及用于使用导航装置 确定最佳行进路线的方法。
背景技术
近来，已经将使用GPS(全球定位系统)的导航装置安装在可移 动物体，例如，各种交通工具，诸如飞船、飞机、汽车等等中。导航 装置从多个GPS卫星接收表示纬度、经度、海拔高度等等的无线电波， 从而计算可移动物体的当前位置。导航装置根据存储的地图数据显示 包括可移动物体的位置的地图信息。即，传统导航装置使用从GPS接 收的信息，向驾驶员提供经显示屏显示的各种必要信息，诸如可移动 物体的当前行进速度(traveling speed)、在行进前由驾驶员指定的行进 路线，以及到他/她的期望目的地的最佳行进路线。
图1是传统的导航装置100的功能框图。参考图1，当前位置检 测单元110包括当前位置计算单元111、GPS接收器113以及传感单元 (sensing unit)115。当前位置检测单元110检测可移动物体的当前位 置。GPS接收器113经天线接收从多个GPS卫星发射的无线电波，从 而计算可移动物体的虚拟坐标。传感单元115包括陀螺仪传感器和速 度传感器。当前位置计算单元111基于从传感单元115发射的交通工具 的转向角度(turning angle)和速度，计算交通工具的当前虚拟位置。 然后，当前位置计算单元111选择从GPS接收器113发射的交通工具 的当前位置的虚拟坐标，或计算的交通工具的虚拟位置。在这里，当 前位置计算单元111不仅计算交通工具的当前位置，而且计算交通工具 的行进信息，诸如行进速度和方向。将计算的交通工具的行进信息传 送到导航控制器120。地图信息存储器130存储地图信息和另外的信息。 操纵单元160包括多个按钮，并将由驾驶员输入的按钮命令提供给导 航控制器以便操作导航装置100。显示单元150显示由地图信息存储器 130读取的地图信息以及导航装置100的状态，同时执行各种功能。基 于由当前位置计算单元111获得的行进信息，导航控制器120从地图信 息存储器130读取附近区域的地图数据，然后在显示单元150上显示 所读数据。
当驾驶员指定期望目的地，并请求目的地的行进路线信息时，导 航控制器120由该驾驶员的交通工具的当前位置或由该驾驶员指定的 出发点计算到该目的地的最佳行进路线，即，最短行进路线，然后在 屏幕上显示最佳行进路线的计算结果。例如，在该屏幕的地图上显示 计算的最佳行进路线。
在行进期间，当驾驶员请求最佳行进路线信息时，安装在交通工 具内的传统导航装置将该交通工具的当前位置视为出发点。然后，传 统的导航装置从出发点计算到该目的地的最佳行进路线，并显示计算 结果。当传统的导航装置计算最佳行进路线时，不考虑在计算时间期 间改变的交通工具的位置信息。因此，在传统的导航装置提供最佳行 进路线的计算结果时的时间点，请求最佳行进路线的交通工具已经移 动到不同于最初出发点的位置。因此，请求最佳行进路线的交通工具 可能处于所计算的最佳行进路线之外。
为解决这种问题，传统的导航装置确定基于请求最佳行进路线的 交通工具的行进速度和方向信息，计算最佳行进路线所花费的时间后 预测的交通工具的虚拟位置。然后，传统的导航装置将上述确定的虚 拟位置视为出发点，从而计算从虚拟位置到目的地的最佳行进路线。 在这种情况下，传统导航装置不考虑道路特性，而仅考虑交通工具的 行进速度和方向，并且将交通工具的当前位置经过某一距离后的虚拟 位置视为出发点。因此，出发点可能实际上是不可用的。
如上所述，使用传统的导航装置，请求最佳行进路线的交通工具 可位于由安装在该交通工具内的导航装置获得的最佳行进路线之处。
当该交通工具移动到地图的下一线路(link)时，在其向右或左转 的情况下，该交通工具的实际行进时间长于存储在该地图数据中的平 均行进时间。然而，传统的导航装置不考虑这点，而仅使用在检测最 佳行进路线中，按行程距离计算的行进时间信息。因此，尽管所检测 的经由传统导航装置计算的最佳行进路线的行进时间比较短，但该交 通工具的实际行进时间可能长于所计算的行进时间。
发明内容
因此，本发明的目的是提供导航装置以及使用该导航装置，计算 最佳行进路线的方法，以便增加请求最佳行进路线的交通工具处于所 获得的最佳行进路线的范围内的可能性。
本发明的另一目的是提供导航装置以及使用该导航装置，计算最 佳行进路线的方法，以便最小化请求最佳行进路线的交通工具的出发 点偏离所获得的最佳行进路线的可能性。
本发明的另一目的是提供导航装置以及使用该导航装置，计算最 佳行进路线的方法，其中根据行进方向，使用指定给地图上的当前线 路和邻近线路的预定加权值，确定从交通工具的当前位置到期望目的 地的最佳行进路线。
根据本发明的一个方面，能通过提供导航装置来实现上述和其他 目的，该导航装置包括当前位置检测单元，用于响应用户的到指定目 的地的最佳行进路线的请求，检测可移动物体的当前位置信息；当前 线路检测单元，用于从所述当前位置检测单元接收所述当前位置信息， 以及从所存储的地图数据检测与所述当前位置一致的当前线路信息； 邻近线路检测单元，用于从所述当前线路检测单元接收所述当前线路 信息，以及从所述所存储的地图数据检测所述当前线路的邻近线路的 信息；邻近线路信息存储单元，用于在此接收和存储来自所述当前线 路检测单元和所述邻近线路检测单元的检测结果；选定线路信息存储 单元，用于存储从所述邻近线路信息存储单元中存储的邻近线路的信 息选出的最佳邻近线路信息；路线计算单元，用于从所述邻近线路信 息存储单元接收当前线路信息和所述邻近线路的信息，使用指定给所 述当前线路信息和所述邻近线路的信息的每一个的行进方向的预定加 权值，计算从所述可移动物体的当前位置到每个邻近线路的累积行进 时间，选择最佳邻近线路信息，并将所述选定的最佳邻近线路信息存 储在选定线路信息存储单元中，以及在邻近线路信息存储单元中存储 邻近当前路线的路线信息，并且基于所执行的下一计算，从选定线路 信息存储单元获得当前路线信息；以及最佳路线检测单元，用于确定 所述选定线路信息存储单元是否存储包括目的地信息的所述线路信 息，从所述选定线路信息存储单元检测包括所述目的地信息的线路信 息以及检测从包括所述目的地线路到出发点的所述邻近线路的信息， 并根据所述线路信息，输出最佳行进路线。
根据本发明的另一方面，提供一种用于使用导航装置，计算最佳 行进路线的方法，包括步骤a)响应用户的到指定目的地的最佳行进路 线的请求，检测可移动物体的当前位置信息；b)从所存储的地图数据 检测与所述可移动物体的当前位置一致的当前线路信息；c)从所述地 图数据，检测在所述目的地方向中，与所述当前线路的邻近线路的信 息；d)使用指定给所述当前线路信息和所述邻近线路的信息的每一个 的行进方向的预定加权值，计算从所述可移动物体的当前位置到每个 邻近线路的累积行进时间；e)根据所计算的每个邻近线路的累积行进 时间，从由所述地图数据检测的所述邻近线路信息选择一个最佳邻近 线路信息；以及f)当最终选定最佳邻近线路信息包括目的地信息时， 重复步骤c)至e)，顺序地从所述选定最佳邻近线路信息检测所述最佳 行进路线，直到最佳路线检测单元检测到包括目的地信息的相邻线路 信息，以及输出所检测的最佳行进路线。
附图说明
从下述结合附图的详细描述，将更容易理解本发明的上述和其他 目的、特征和其他优点，其中：
图1是传统导航装置的框图；
图2是根据本发明的一个实施例的导航装置的基本零件的框图；
图3a是根据本发明的一个实施例的地图信息管理的配置的示意 图；
图3b是根据本发明的一个实施例的邻近线路信息数据库的配置 的示意图；
图3c是根据本发明的一个实施例的选定线路信息数据库的配置的 示意图；
图4是用于使用根据本发明的一个实施例的导航装置，计算最佳 行进路线的方法的流程图；以及
图5至7示例说明用于根据本发明的一个实施例，计算最佳行进 路线的示例性过程，更具体地说，
图5是由根据本发明的一个实施例的导航装置检测的当前线路和 邻近线路的示意图；
图6示例说明在用于计算通过图5的范围内的线路的最佳路线的 每个步骤，存储在选定线路信息存储单元中的信息的例子；
图7示例说明在用于计算通过图5的范围内的线路的最佳路线的 每个步骤，存储在邻近线路信息存储单元中的信息的例子。
具体实施方式
现在，将参考附图，详细地描述本发明的优选实施例。在图中， 即使在不同图中描述，也由相同的标记表示相同或相似的元件。在下 述描述中，当其可能使本发明的主题不清楚时，将省略在此包含的已 经功能和结构的详细描述。
图2是根据本发明的一个实施例的导航装置的基本部分的框图。 即，图2是根据本发明的一个实施例的导航装置100的导航控制器120 的框图。
参考图1和2，导航控制器120包括当前线路检测单元121、邻近 线路检测单元123、邻近线路信息存储单元125、路线计算单元127、 选定线路信息存储单元128，以及最佳路线检测单元129。导航控制器 120使用当前位置检测单元110提供的当前位置信息和由地图信息存储 器130提供的地图数据，检测最佳行进路线。然后，导航控制器120 在显示单元150上显示检测的最佳行进路线。
首先，用户经操纵单元160输入对指定目的地的最佳行进路线的 请求。当前位置检测单元110响应最佳行进路线请求，检测用户的交 通工具的当前位置信息。当前位置检测单元110将检测的当前位置信 息传送给导航控制器120。
导航控制器120的当前线路检测单元121从当前位置检测单元110 接收当前位置信息。当前线路检测单元121从已经存储在地图信息存 储器130中的地图数据检测与可移动物体的当前位置一致的当前线路 信息。
邻近线路检测单元123从当前线路检测单元121接收当前线路信 息。然后，邻近线路检测单元123从存储在地图信息存储器130中的 地图数据检测与与当前线路相邻的线路一致的信息。邻近线路检测单 元123根据存储在地图数据中的线路的位置和方向信息，在目的地方 向中检测与当前线路相邻的所有线路的信息。
邻近线路信息存储单元125从每个当前线路检测单元121和邻近 线路检测单元123接收检测结果，以及在此存储接收的结果。选定线 路信息存储单元128在由路线计算单元127做出决定后，存储将从存 储在邻近线路信息存储单元125中的邻近线路的信息中，选择为最佳 邻近线路信息的一个邻近线路信息。
路线计算单元127从邻近线路信息存储单元125接收当前线路信 息和邻近线路信息。然后，路线计算单元127使用指定给每个当前线 路信息和邻近线路信息的可用行进方向的预定加权值，从而计算可移 动物体的累积行进时间。即，当根据预定线路信息和邻近线路的信息， 可移动物体从当前线路移向邻近线路时，路线计算单元127确定可移 动物体的行进方向是否改变。在已经改变可移动物体的行进方向的情 况下，累积行进时间包括根据指定给每个可能改变的行进方向的预定 加权值，单独指定的虚拟时间信息。例如，当可移动物体右转弯以致 从当前线路移入相邻线路，以及用于做右转弯的虚拟时间指定为1分 钟时，将虚拟时间(1分钟)增加到根据相应的邻近线路的距离和平均 行进速度而计算的行进时间上。将增加的总时间检测为相应的邻近线 路的累积行进时间。
在假定驾驶员喜欢依次直行、右转弯、左转弯以及U转弯的情况 下，最好，分别将直行、右转弯、左转弯和U转弯的弯曲时间预定为 0、1、2和3。这种预定包括驾驶员在通过行进路线的最佳方向中驾驶 他们的汽车。
路线计算单元127将累积行进时间相互比较，然后根据比较结果 选择最佳邻近线路。将选定的最佳邻近线路的信息存储在选定线路信 息存储单元128中。路线计算单元127计算从可移动位置的当前位置 行进到邻近线路所花的累积行进时间直到将包括目的地信息的邻近线 路信息存储在选定线路信息存储单元128中，从而重复执行用于选择 最佳邻近线路信息的过程。在这里，路线计算单元127将最终存储在 选定线路信息存储单元128中的邻近线路信息设置为当前线路信息。 在由路线计算单元127将与当前线路相邻的线路的信息存储在邻近线 路信息存储单元125中之后，路线计算单元127根据存储在邻近线路 信息存储单元125中的信息，计算累积行进时间。
为防止该交通工具偏离出发点的范围内的最佳行进路线，路线计 算单元127使用指定给在出发点的预定范围内的节点的、高于预定加 权值的加权值。
最佳路线检测单元129确定包括目的地信息的邻近线路信息是否 存储在选定线路信息存储单元128中。当包括目的地信息的邻近线路 信息存储在选定线路信息存储单元128中时，最佳路线检测单元129 从选定线路信息存储单元128检测从包括目的地的线路到出发点的所 有邻近线路的信息，然后，根据检测信息，将最佳行进路线输出到显 示单元150上。
图3a至3c示例说明使用根据本发明的一个实施例的导航装置， 计算最佳行进路线所需的信息。
图3a是根据本发明的一个实施例，地图信息管理数据库(DB) 10的配置的示意图。参考图1和3a，由地图信息存储器130管理的地 图数据包括线路ID11、距离12、平均行进速度13以及方向信息14。 距离12是相应线路的长度。平均行进速度13是相应线路的平均行进 速度。方向信息14是相应线路的行进方向信息。
图3b是根据本发明的一个实施例的邻近线路信息数据库的配置 的示意图。参考图2和3b，由邻近线路信息存储单元125管理的邻近 线路信息30包括线路ID31、在前线路ID32、行进时间信息33、虚拟 时间信息34、最终时间信息35以及累积时间信息36。
图3c是根据本发明的一个实施例的选定线路信息数据库的配置的 示意图。参考图2和3c，由选定线路信息存储单元128管理的选定线 路信息20包括线路ID21、在前线路ID22以及累积时间信息23。
图4是用于使用根据本发明的一个实施例的导航装置，计算最佳 行进路线的方法的流程图。参考图2和4，描述用于使用根据本发明的 一个实施例的导航装置，计算最佳行进路线的方法如下。
当具有本发明的导航装置的可移动物体(以下称为“交通工具”) 的驾驶员请求从当前位置到期望目的地的最佳行进路线时，导航装置 的当前位置检测单元110检测交通工具的当前位置信息。在步骤S110， 当前线路检测单元121从存储的地图数据检测与上述检测的当前位置 一致的当前线路信息。在步骤120，邻近线路检测单元123从当前线路 检测单元121接收当前线路信息，并从所存储的地图数据检测在目的 地方向中，与当前线路相邻的所有线路的信息。然后，邻近线路检测 单元123将检测的邻近线路信息存储在邻近线路信息存储单元125中。
在步骤S130，当计算从出发点到目的地的路线时，路线计算单元 127确定第一节点是否在指定出发点的范围内。当第一节点不在指定出 发点的范围内时，在步骤S150，根据使用加权值获得的行进时间信息， 选择最佳邻近线路。在这里，为使用加权值计算行进时间信息，使用 指定给每个加权值的虚拟时间信息。
当在步骤130中，第一节点位于指定出发点的范围内时，在步骤 140，根据使用高于上述预定加权值的加权值(启程加权值 (departure_weightedvalue))获得的行进时间信息，选择最佳邻近线路。 这防止该交通工具偏离出发点的范围内的最佳行进路线。
在步骤160，确定最终选定线路是否为包括目的地信息的线路。 在步骤S170，检测最终选定线路的相邻线路，直到最终选定线路包括 该目的地为止。然后，使用加权值，在步骤S150，重复从邻近线路选 择最佳邻近线路。当最终选定线路包括目的地时，在步骤S160，检测 来自邻近线路的最佳行进路线并在步骤S180输出。
即，最佳路线检测单元129确定存储在选定线路信息存储单元128 中的线路信息是否包括包含目的地的线路的信息。当所存储的线路信 息包括具有目的地信息的线路信息时，最佳路线检测单元129从包括 目的地到出发点的线路跟踪存储在选定线路信息存储单元128中的邻 近线路，从而检测最佳行进路线。
图5至7示例说明用于根据本发明的一个实施例，计算最佳行进 路线的示例性过程。
图5是由根据本发明的一个实施例的导航装置检测的当前线路和 邻近线路的示意图。在图5中，九个节点(·)将区域分成由导航装置 管理的线路(行进路线)，以及节点(·)间的箭头(→)表示行进方 向。在箭头上印的字母符号是相应线路的标识符，以及紧接标识符的 括号内的了阿拉伯数字表示相应的线路的行进时间信息。在图5的例 子中，线路的行进时间信息均表示为“1”。印在线路A上的大箭头() 表示交通工具的当前位置。
图6和7示例说明存储在用于计算通过图5的线路的最佳行进路 线的每个步骤的选定线路信息存储单元(图2的128)和邻近线路信息 存储单元(图2的125)中的信息的例子。
参考图6，在步骤1，将交通工具(线路A)的当前位置的线路信 息存储在选定线路信息存储单元(图2的128)中。线路A的存储信 息的内容如图6所示。参考图7，在步骤2，与存储在选定线路信息存 储单元(图2的128)的与线路A相邻的线路(线路B和N)的信息 存储在邻近线路信息存储单元(图2的125)中。线路B和N的信息 内容如图7所示。即，邻近线路信息存储单元(图2的125)存储相应 线路的ID、在前线路的ID、转向信息、实际行进时间信息、实际累积 时间信息、加权值、启程_加权值值、线路虚拟时间信息、累积虚拟时 间信息以及状态信息。
实际累积时间信息是通过将当前线路的行进时间与在前线路的行 进时间相加所获得的值，将加权值指定给每个可用进行方向，诸如左 转弯、右转弯、直行等等。在图7的例子中，指定给左转弯的加权值 用“L”表示，以及指定给右转弯的加权值用“R”表示。指定给直行 的加权值用“S”表示。在计算累积时间中，将上述加权值转换成数值。
启程加权值是仅指定给在预定出发点范围内的节点的值。启程 加权值防止该交通工具偏离该出发点范围内的最佳行进路线。
在图7中，如括号内所示的在每个步骤的累积虚拟时间信息是通 过计算累积虚拟时间所获得的结果，其中指定给左转弯的加权值(L) 为“2”、指定给右转弯(R)的加权值为“1”，指定给直行(S)的加 权值为“0”，指定给绕出发点左转弯(LP)的加权值为“4”，指定绕 出发点右转弯(RP)的加权值为“2”，指定绕出发点直行(SP)的加 权值为“0”。
在图7的步骤2，选择线路B。如图6的步骤3所示，将选定线路 B存储在选定线路信息存储单元中，在图7的步骤4，选定线路C。如 图6的步骤5所示，将选定线路C存储在选定线路信息存储单元中。 在图7的步骤6，选择线路R。如图6的步骤7所示，将选定线路R存 储在选定线路信息存储单元中。
如上所述，使用启程加权值和加权值，获得从出发点到所有邻近 线路的每一个的累积时间信息。根据累积时间作息，选择最佳线路， 然后存储在选定线路信息存储单元中。当最终存储在选定线路信息存 储单元中的线路包括目的地(图5中的线路L)时，跟踪从包括目的地 的最终存储线路到出发点的路线并检测为最佳行进路线。
从上述说明可以看出，本发明提供导航装置以及用于使用该导航 装置，计算最佳行进路线的方法，其中根据方向，使用指定给地图上 的当前线路和邻近线路的预定加权值，确定从交通工具的当前位置到 期望目的地的最佳行进路线，从而提高请求最佳行进路线的交通工具 位于由该导航装置提供的最佳行进路线的范围内的可能性。另外，本 发明的导航装置考虑实际行进时间和行程距离，从而提供可靠的最佳 行进路线。
尽管详细地描述了本发明的一些实施例，本领域的普通技术人员 将意识到，在不脱离由附加权利要求书公开的本发明的范围和精神的 情况下，可对特定部分做出各种改进、增加以及取代。