提供出发地和目的地导航信息的系统和方法转让专利
申请号 : CN200580036184.6
文献号 : CN100593802C
文献日 : 2010-03-10
发明人 : 金度成 , 朴民熙 , 崔仁俊 , 朴镇璟
申请人 : SK营销咨询
摘要 :
一种用于提供出发地和目的地导航信息的系统，选择交通工具的出发地位置，并且在考虑交通工具所到达的目的地的位置和类型(十字路口、公寓、公园、高速公路)的情况下选择目的地连接，它是目的地附近的道路，根据所选择的出发地连接、目的地连接、实时交通信息(或地图连接信息)，生成从出发地连接到目的地连接的路径，生成导航信息，该导航信息包含所生成的路径的邻接图和语音信息，并且向所述交通工具终端提供所述导航信息。根据本发明，系统生成从当前位置到期望目的地的最佳路径并且将该最佳路径提供给用户。
权利要求 :
1.一种用于向通过无线网络连接的交通工具终端提供出发地和 目的地导航信息的系统，其包括：出发地选择器，用于根据所述交通工具的方向和当前位置选择出 发地连接，该出发地连接是与所述出发地相邻的道路；
目的地选择器，用于根据目的地的位置和类型选择目的地连接， 该目的地连接是与所述目的地相邻的道路；
路径生成器，用于根据所选择的出发地连接、所选择的目的地连 接、实时交通信息以及地图信息，生成从所述出发地连接到所述目的 地连接的路径；
导航信息生成器，用于生成导航信息，该导航信息包含所生成的 路径的邻接图和有关所述路径的语音信息中的至少一个；以及导航信息提供器，用于向所述交通工具终端提供所生成的导航信 息。
2.根据权利要求1所述的系统，其中，当所述交通工具在右侧 行使时，所述目的地选择器选择目的地连接，以使得所述目的地位于 所述交通工具的行进方向的右边，并且当所述交通工具在左侧行使 时，所述目的地选择器选择目的地连接，以使得所述目的地位于所述 交通工具的行进方向的左边。
3.根据权利要求1所述的系统，其中，所述目的地选择器选择 在目的地坐标的预定范围之内提供的至少一个目的地连接，以及所述路径生成器为所述至少一个目的地连接生成路径，并且从所 生成的路径中确定最佳的路径。
4.根据权利要求1所述的系统，其中，当所述目的地具有至少 两个通路时，所述目的地选择器选择所述至少两个通路作为目的地连 接，以及所述路径生成器为所述至少两个所选择的目的地连接生成路径， 并且从所生成的路径中确定最佳的路径。
5.根据权利要求2到4中任一项所述的系统，其中，当将被选 择的目的地连接是高速公路、城市快速路、立交桥和地道中之一时， 所述目的地选择器再次搜索目的地连接以选择想要的一个。
6.根据权利要求1所述的系统，其中，当在所述出发地的预定 范围内同时提供了高速公路、城市快速路、立交桥和地道中的至少两 种道路时，所述出发地选择器控制用户从所提供的道路中选择出发地 连接。
7.根据权利要求1所述的系统，其中，当在所述出发地的预定 范围内未发现道路时，所述出发地选择器从所述预定范围外选择除了 所述高速公路和所述城市快速路以外的道路作为出发地连接。
8.一种用于向通过无线网络连接的交通工具终端提供出发地和 目的地导航信息的方法，其包括：a)根据所述交通工具的方向和当前位置选择出发地连接，该出发 地连接是与所述出发地相邻的道路；
b)在考虑到所述目的地的位置和类型的情况下选择目的地连接， 该目的地连接是与所述目的地相邻的道路；
c)根据所选择的出发地连接、所选择的目的地连接、实时交通信 息以及地图连接信息，生成从所述出发地连接到所述目的地连接的路 径；以及d)生成导航信息，该导航信息包含所生成的路径的邻接图和语音 信息中的至少一个，以及向所述交通工具终端提供所生成的导航信 息。
9.根据权利要求8所述的方法，其中，所述b)包括：当所述交 通工具在右侧行使时，选择目的地连接以使得所述目的地的位置位于 所述交通工具的行进方向的右边，并且当所述交通工具在左侧行使 时，选择目的地连接以使得所述目的地的位置位于所述交通工具的行 进方向的左边。
10.根据权利要求8所述的方法，其中，所述b)包括：选择在目 的地坐标的预定范围之内提供的至少一个连接作为候选目的地连接， 以及所述c)包括：为所选择的至少一个候选目的地连接生成相应的路 径；并且从所生成的路径中确定最佳的路径。
11.根据权利要求8所述的方法，其中，所述b)包括：当所述目 的地包括至少一个通路时，选择将作为候选目的地连接的通路，以及所述c)包括：为所选择的至少一个候选目的地连接生成相应的路 径；并且从所生成的路径中确定最佳的路径。
12.根据权利要求9到11中任一项所述的方法，其中，所述b) 包括：当将被选择的目的地连接是高速公路、城市快速路、立交桥和 地道中之一时，再次搜索所述目的地连接以选择想要的一个。
13.根据权利要求8所述的方法，其中，所述a)包括：当在将被 选择的所述出发地的预定范围内同时提供了高速公路、城市快速路、 立交桥和地道中的至少两种道路时，控制用户选择所述出发地连接的 道路类型。
14.根据权利要求8所述的方法，其中，所述a)包括：当在所述 出发地的预定范围内未发现道路时，从所述预定范围外选择除了所述 高速公路和所述城市快速路以外的道路作为出发地连接。
说明书 :
技术领域
本发明涉及提供路径信息的系统和方法。更具体地说，本发明涉 及用于提供选择出发地和目的地连接的方案和路径导航信息的系统 和方法。
背景技术
目前，为了检测当前位置和速度或确定路径，例如船、飞机和汽 车等各种交通工具都已经使用了全球定位系统(GPS)。导航系统利用 GPS检测交通工具的位置，并且将其应用于地图匹配或者出发地位置 的选择。传统的导航系统选择最接近当前位置的路径作为出发地连 接。当与该交通工具的当前位置最近的路径被选为出发地连接时，在 靠近用户的高速公路和普通路径被提供给附近的用户的时候，可能选 择用户不容易从当前位置进入的路径，并且由此用户可能不能沿所指 定的路径行使。
传统的目的地选择方法还选择目的地坐标附近的路径作为目的 地连接，并且当一个十字路口被作为目的地时，各种到达目的地的方 法都是可用的。如果十字路口附近的一个连接被确定为目的地，则可 以提供引导到目的地的迂回的路线，或者可以在不可达到期望的目的 地的高速公路上或城市快速路上终止导航路径。现在将参考图1描述 根据传统的目的地选择方法，提供了不适当的路径的情况。
图1显示由传统的目的地选择方法提供的路径。
如图所示，出发地是Bangbae Office并且目的地是Sadang Station 十字路口，而Sadang立交桥位于东西方向上。当根据传统的目的地 选择方法，用户选择Sadang Station十字路口作为目的地时，Sadang 立交桥可能被错误地选择为目的地，并且据此提供通向Sadang立交 桥的路线10。结果，用户必须开上离Sadang Station十字路口的西边 较远的Sadang立交桥，然后进行U形的转弯，因此浪费了时间。
此外，用于选择临近的连接作为目的地连接，而不考虑到目的地 的通路方向的路径提供方法，终止了在不同于通向目的地的方向的方 向上的路径的提供，因此，当到达目的地时，用户不能直接开车到目 的地。
如上所述，根据传统的出发地或目的地选择方法的路径导航没有 考虑选择出发地或目的地连接所需的事项，以致用户会走迂回的路线 或者无法到达目的地。
传统的目的地选择方法还选择目的地坐标附近的路径作为目的 地连接，并且当一个十字路口被作为目的地时，各种到达目的地的方 法都是可用的。如果十字路口附近的一个连接被确定为目的地，则可 以提供引导到目的地的迂回的路线，或者可以在不可达到期望的目的 地的高速公路上或城市快速路上终止导航路径。现在将参考图1描述 根据传统的目的地选择方法，提供了不适当的路径的情况。
图1显示由传统的目的地选择方法提供的路径。
如图所示，出发地是Bangbae Office并且目的地是Sadang Station 十字路口，而Sadang立交桥位于东西方向上。当根据传统的目的地 选择方法，用户选择Sadang Station十字路口作为目的地时，Sadang 立交桥可能被错误地选择为目的地，并且据此提供通向Sadang立交 桥的路线10。结果，用户必须开上离Sadang Station十字路口的西边 较远的Sadang立交桥，然后进行U形的转弯，因此浪费了时间。
此外，用于选择临近的连接作为目的地连接，而不考虑到目的地 的通路方向的路径提供方法，终止了在不同于通向目的地的方向的方 向上的路径的提供，因此，当到达目的地时，用户不能直接开车到目 的地。
如上所述，根据传统的出发地或目的地选择方法的路径导航没有 考虑选择出发地或目的地连接所需的事项，以致用户会走迂回的路线 或者无法到达目的地。
发明内容
本发明的优点是提供用于提供出发地和目的地导航信息的系统 和方法，以防止由无法到达目的地所引起的时间和资源损失。
根据本发明的一个方面，一种用于向通过无线网络连接的交通工 具终端提供出发地和目的地导航信息的系统，其包括：出发地选择器， 用于根据所述交通工具的方向和当前位置选择出发地连接，该出发地 连接是与所述出发地相邻的道路；目的地选择器，用于根据目的地的 位置和类型选择目的地连接，该目的地连接是与所述目的地相邻的道 路；路径生成器，用于根据所选择的出发地连接、所选择的目的地连 接、实时交通信息以及地图信息，生成从所述出发地连接到所述目的 地连接的路径；导航信息生成器，用于生成导航信息，该导航信息包 含所生成的路径的邻接图和有关所述路径的语音信息中的至少一个； 以及导航信息提供器，用于向所述交通工具终端提供所生成的导航信 息。
当所述交通工具在右侧行使时，所述目的地选择器选择目的地连 接，以使得所述目的地可以位于所述交通工具的行进方向的右边，并 且当所述交通工具在左侧行使时，所述目的地选择器选择目的地连 接，以使得所述目的地可以位于所述交通工具的行进方向的左边。
根据本发明的另一个方面，一种用于向通过无线网络连接的交通 工具终端提供出发地和目的地导航信息的方法，其包括：a)根据所述 交通工具的方向和当前位置选择出发地连接，该出发地连接是与所述 出发地相邻的道路；b)在考虑到所述目的地的位置和类型的情况下选 择目的地连接，该目的地连接是与所述目的地相邻的道路；c)根据所 选择的出发地连接、所选择的目的地连接、实时交通信息以及地图连 接信息，生成从所述出发地连接到所述目的地连接的路径；以及d) 生成导航信息，该导航信息包含所生成的路径的邻接图和语音信息中 的至少一个，以及向所述交通工具终端提供所生成的导航信息。
根据本发明的一个方面，一种用于向通过无线网络连接的交通工 具终端提供出发地和目的地导航信息的系统，其包括：出发地选择器， 用于根据所述交通工具的方向和当前位置选择出发地连接，该出发地 连接是与所述出发地相邻的道路；目的地选择器，用于根据目的地的 位置和类型选择目的地连接，该目的地连接是与所述目的地相邻的道 路；路径生成器，用于根据所选择的出发地连接、所选择的目的地连 接、实时交通信息以及地图信息，生成从所述出发地连接到所述目的 地连接的路径；导航信息生成器，用于生成导航信息，该导航信息包 含所生成的路径的邻接图和有关所述路径的语音信息中的至少一个； 以及导航信息提供器，用于向所述交通工具终端提供所生成的导航信 息。
当所述交通工具在右侧行使时，所述目的地选择器选择目的地连 接，以使得所述目的地可以位于所述交通工具的行进方向的右边，并 且当所述交通工具在左侧行使时，所述目的地选择器选择目的地连 接，以使得所述目的地可以位于所述交通工具的行进方向的左边。
根据本发明的另一个方面，一种用于向通过无线网络连接的交通 工具终端提供出发地和目的地导航信息的方法，其包括：a)根据所述 交通工具的方向和当前位置选择出发地连接，该出发地连接是与所述 出发地相邻的道路；b)在考虑到所述目的地的位置和类型的情况下选 择目的地连接，该目的地连接是与所述目的地相邻的道路；c)根据所 选择的出发地连接、所选择的目的地连接、实时交通信息以及地图连 接信息，生成从所述出发地连接到所述目的地连接的路径；以及d) 生成导航信息，该导航信息包含所生成的路径的邻接图和语音信息中 的至少一个，以及向所述交通工具终端提供所生成的导航信息。
附图说明
图1显示由传统的目的地选择方法提供的路径；
图2显示根据本发明的典型实施例的、用于提供出发地和目的地 导航信息的系统的结构；
图3显示根据本发明的典型实施例的、用于提供出发地和目的地 导航信息的系统的详细结构；
图4显示根据本发明的典型实施例的、用于提供出发地和目的地 导航信息的系统的操作流程图；
图5显示根据本发明的典型实施例的，考虑到目的地的位置和交 通工具的前进方向的目的地连接；
图6显示根据本发明的典型实施例，当地铁站被作为目的地时所 选的目的地连接；
图7显示根据本发明的典型实施例，当公园被作为目的地时所选 的目的地连接；
图8显示当城市快速路被作为目的地连接时，通过普通路径搜索 而找到的路径；
图9显示当城市快速路被作为目的地连接时，通过根据本发明的 典型实施例的路径搜索而找到的路径；
图10显示根据本发明的典型实施例的，从最终出发地到目的地 的连接信息。
图2显示根据本发明的典型实施例的、用于提供出发地和目的地 导航信息的系统的结构；
图3显示根据本发明的典型实施例的、用于提供出发地和目的地 导航信息的系统的详细结构；
图4显示根据本发明的典型实施例的、用于提供出发地和目的地 导航信息的系统的操作流程图；
图5显示根据本发明的典型实施例的，考虑到目的地的位置和交 通工具的前进方向的目的地连接；
图6显示根据本发明的典型实施例，当地铁站被作为目的地时所 选的目的地连接；
图7显示根据本发明的典型实施例，当公园被作为目的地时所选 的目的地连接；
图8显示当城市快速路被作为目的地连接时，通过普通路径搜索 而找到的路径；
图9显示当城市快速路被作为目的地连接时，通过根据本发明的 典型实施例的路径搜索而找到的路径；
图10显示根据本发明的典型实施例的，从最终出发地到目的地 的连接信息。
具体实施方式
在以下的详细说明中，简单地通过说明实现本发明的发明者所考 虑的最佳模式来只显示和描述本发明的优选实施例。正如将要认识到 的，该发明能够在多个显而易见的方面上修改，而都不脱离本发明。 因此，认为附图和说明是在本质上是说明性的，而不是限制性的。为 了阐明本发明，省略了在说明书中未描述的部分，并且提供了相似的 说明的部分具有相同的参考标记。
为了便于描述，道路网络将被称为网络，其包括结点和连接。该 结点表示连接多条线的点，并且连接表示结点之间的线。
图2显示了根据本发明的典型实施例的，用于提供出发地和目的 地导航信息的系统的结构。
如图所示，提供出发地和目的地导航信息的系统100，通过无线 网络200连接到交通工具终端300，并且连接到交通信息提供中心400 其用于实时地提供各个位置的交通状况。在这种情况下，术语“交通 工具”一般指汽车，但并不局限于此。此外，交通工具终端300可以 利用笔记本电脑、PDA或者移动电话来实现。
用于提供出发地和目的地导航信息的如上连接的系统100从交 通工具终端300接收当前位置信息和移动方向信息，并且选择用户可 以容易地从其移动的出发地(称为“出发地连接”)。
在这种情况下，交通工具终端300计算交通工具的行进方向，并 且系统100在考虑所计算的行进方向的情况下选择一出发地连接，其 目的是消除当在交通工具行进的方向相反的方向上选择出发地连接 时，由于交通工具必须不情愿的转向而引起的不便。
即，用于提供出发地和目的地导航信息的系统100向用户提供道 路信息以选择出发地连接，以使得当在交通工具的行进方向上并且在 当前位置的预定范围之内(例如，半径100米的范围之内)提供了至少 两种道路(高速公路，城市快速路，立交桥，地下通道和普通道路)时， 用户可以通过使用交通工具终端300在当前位置建立道路类型。
当在交通工具的行进方向上并且在当前位置的预定范围之内未 提供两种道路时，系统100选择最接交通工具终端300的位置的连接 作为出发地连接。
此外，当在预定范围之内没有发现道路时，系统100在预定范围 之外的道路选择出发地连接。在这种情况下，出发地连接不包括高速 公路和城市快速路。
在大多数情况下，交通工具终端300一般位于除高速公路或者城 市快速路以外的普通道路，而且当高速公路或者城市快速路被选为出 发地连接时，用户不能根据导航路径行使。
当在移动时接收到路径请求时，系统100在考虑到由交通工具终 端300提供的、有关交通工具的行进方向的信息的情况下，选择一出 发地连接。在这种情况下，可以使用由安装在交通工具中的GPS提 供的各种位置信息来计算前进方向信息。
当不考虑交通工具的行进方向时，会在交通工具的行进方向的相 反方向上搜索路径，交通工具不能在所提供的路径上行使。
此外，系统100通过考虑用户期望的目的地的位置和类型来选择 目的地连接，详细地说，对目的地连接进行分类，并且根据依赖于目 的地的位置和类型的条件选择所期望的。
更具体地说，在考虑到在交通工具的行进方向的右边(或者在左 边行驶的情况下为左边)具有目的地(目的地坐标)的临近连接以及交 通工具的方向的情况下，系统100选择目的地连接，以防当用户在所 选的目的地连接和交通工具的行进方向与目的地的方向相反的情况 下而不能直接到达目的地时，终止路径导航。
当用户可以从任何方向到达目的地时(例如，十字路口或者地铁 站)，用于提供出发地和目的地导航信息的系统100选择在预定范围 内(例如，半径为300米的范围)提供的连接作为候选目的地连接，并 且在考虑到出发地连接的情况下，从选择的候选连接中确定最优化路 径的连接作为目的地连接。
此外，当提供到达目的地的多个通路时(例如，一个大公寓或公 园)，在大多数情况下，提供彼此相距较远的途径，因此，系统100 选择多个途径作为候选目的地连接，并且在考虑到出发地连接的情况 下，从所选的候选连接中确定最优化路径的连接作为目的地连接。
然而，因为当选择目的地连接时，在大多数情况下，交通工具不 能容易地进入高速公路，城市快速路，立交桥或者地道，所以系统 100再次搜索候选目的地连接，并且确定交通工具容易进入的普通道 路作为目的地连接。
高速公路休息点或加油站可以是用户实际想要去的目的地，因 此，高速公路和城市快速路上的可到达的目的地被处理为例外情况。
用于提供出发地和目的地导航信息的系统100根据所选的出发 地和目的地连接，在从出发地到目的地提供的多个路径中产生最佳的 路径，产生关于生成的路径的导航信息，把该导航信息转换为可由交 通工具终端300显示的形式，并且提供转换后的导航信息。
正如所描述的，系统100根据交通工具的位置和道路类型，以多 种方式选择出发地连接，并且根据目的地的位置和类型，通过应用不 同的方法选择目的地连接。
现在将描述用于提供出发地和目的地导航信息的系统100的详 细结构。
图3显示了根据本发明的典型实施例的，提供出发地和目的地导 航信息的系统的详细结构。
如图所示，用于提供出发地和目的地导航信息的系统100包括路 径请求接收器110，出发地选择器120，目的地选择器130，路径生 成器140，导航信息生成器150以及导航信息提供器160。
详细地说，路径请求接收器110从交通工具终端300接收包含交 通工具的当前位置(出发地位置)和目的地位置的路径请求。路径请求 可以进一步包括交通工具的移动方向。
出发地选择器120根据交通工具的当前位置控制用户选择出发 地连接，或者当在预定的范围之内未提供路径搜索网络时，从预定范 围之外选择除了高速公路和城市快速路以外的出发地连接。
目的地选择器130根据目的地的位置和类型，通过应用不同的方 法来选择目的地连接。
路径生成器140基于所选的出发地连接、目的地连接、实时的交 通信息以及地图连接信息，生成从出发地到目的地的路径。在这种情 况下，地图连接信息包括行车道的数量、速度和道路分类(例如，高 速公路、城市快速路、国道或者当地道路)中的至少一个。
导航信息生成器150通过邻接图和语音信息中的至少一个，生成 有关所生成的路径的导航信息。
导航信息提供器160把生成的导航信息转换为可由交通工具终 端300显示的形式，并且提供转换后的导航信息。
现在将描述用于提供出发地和目的地导航信息的系统100的操 作。
图4显示了根据本发明的典型实施例的，用于提供出发地和目的 地导航信息的系统的操作流程图。
如图所示，在步骤S401，路径请求接收器110从交通工具终端 300接收通过安装在交通工具中的GPS获得的，包含出发地位置信息 和目的地信息的路径请求。路径请求可以进一步包括交通工具的行进 方向。
在步骤S402，出发地选择器120根据接收的路径请求信息(交通 工具的当前位置和行进方向)选择出发地连接，并且检查在交通工具 的当前位置上，是否在预定范围(例如，半径100米的范围)之内，提 供了不同类型的道路(高速公路、城市快速路、立交桥和地道)。
当发现不同类型的道路时，在步骤S403，出发地选择器120控 制用户选择出发地连接的道路类型，并且当未同时发现不同类型的道 路时，出发地选择器120选择与交通工具最接近的连接作为出发地连 接。
当在交通工具移动的同时生成路径请求时，出发地选择器120可 以在考虑交通工具的行进方向的情况下选择出发地连接。
在这种情况下，当在范围内没有发现道路时，在步骤S404，出 发地选择器120从预定范围之外的道路中选择除高速公路和城市快 速路以外的连接。
目的地选择器130根据目的地的位置和类型选择目的地连接，详 细地说，当要选择的目的地连接是与目的地邻近的连接时，在步骤 S405，目的地选择器130通过考虑交通工具的行进方向来选择目的地 连接。
因为在多数情况下，根据具体实施例选择的目的地连接在目的地 附近，所以希望通过考虑交通工具的行进方向来选择目的地连接，如 图5所示。
图5显示了当在右边驾驶时，根据本发明的典型实施例的，在考 虑到目的地的位置和交通工具的行进方向的情况下的目的地连接。
如图所示，交通工具行进在七点钟的方向上(在西南偏南的方向 上)。目的地选择器130选择目的地连接20，以使得目的地(Lotte Department Store)可以位于交通工具的行进方向的右侧，这是因为当 在右边行使时，目的地必须位于交通工具的行进方向的右侧，以使得 交通工具能够抵达目的地。
当在左侧行使时，目的地选择器130选择目的地连接，以使得目 的地可以位于交通工具的行进方向的左边。因此，目的地选择器130 控制用户容易地到达期望的目的地。
当在步骤S407判断交通工具300想要到达的目的地不对应于进 入方向(即，交通工具的行进方向)时，例如十字路口或地铁站，那么 在步骤S408，目的地选择器130选择在关于对应的目的地坐标的预 定范围之内(例如，半径300米的范围)提供的连接，作为候选连接， 并且根据在步骤S413中的随后的最佳化路径，从所选的候选目的地 连接中选择单个连接作为最终的目的地连接，其在图6中说明。
图6显示了根据本发明的典型实施例的，当地铁站被作为目的地 时的所选的目的地连接。
如图所示，当目的地给定为Sadang station时，目的地选择器130 选择Sadang station附近的多个候选连接，并且确定最终的目的地连 接，由此防止移动终端的关于目的地的迂回路线。
在步骤S409，在大多数情况下，交通工具终端300想要到达的 公寓或者公园具有至少两条通路。
因此，在步骤S410，目的地选择器130根据多点POI(MPP)方案， 选择多个通路作为候选目的地连接，并且在步骤413根据最佳路径， 从候选连接中确定最终的目的地连接。在图7中说明了MPP方案的 一个例子。
图7显示了根据本发明的典型实施例的，当公园作为目的地时的 所选择的目的地连接。
如图所示，当目的地是Olympic Park时，目的地选择器130选择 三种通路的连接作为候选目的地连接，并且在步骤S413，根据随后 选择的最佳路径，确定最终的目的地连接。
当期望的目的地连接是高速公路、城市快速路、立交桥以及地道 中之一时，目的地选择器130再次搜索目的地连接，并且在步骤S412 中选择交通工具容易进入的普通道路，作为目的地连接。现在将参考 图8和图9描述当目的地连接是城市快速路时，选择目的地连接的方 法。
图8显示当城市快速路作为目的地连接时，通过普通路径搜索找 到的路径，图9显示当城市快速路作为目的地连接时，通过根据本发 明的典型实施例的路径搜索找到的路径。
如图8所示，当目的地连接是Sokkye Station的内部环路时，通 过普通路径搜索所得到的路径的目的地连接变为内部环路的连接，因 此，用户必须走迂回路线以到达目的地Sokkye Station。
然而，如图9所示，因为目的地连接是内部环路，所以目的地选 择器130再次搜索连接，并且确定位于内部环路之下的普通道路作为 最终的目的地道路，以使得用户可以容易地移动到期望的目的地。
在步骤S413，路径生成器140根据所选择的出发地连接、目的 地连接、由交通信息提供中心400提供的实时交通信息以及地图连接 信息，生成从出发地到目的地的路径。在这种情况下，当提供了多个 目的地连接时，路径生成器140为相应的目的地连接生成多个路径， 并且从这些路径中确定最佳路径，其在图10中说明。
图10显示了根据本发明的典型实施例的，从最终的出发地到目 的地的连接信息。
如图所示，路径生成器140选择从Jongroku(即出发地30)附近的 出发地连接40到目的地60附近的目的地连接50的单个最佳路径， 并且提供该最佳路径。
离出发地30最近的连接是内部环路，但是因为难以进入内部环 路，所以出发地选择器120选择在预定范围内提供的连接40作为出 发地连接。
在步骤S414，导航信息生成器150生成导航信息，其包含所生 成的路径的邻接图和语音信息中的至少一个，并且导航信息提供器 160把所生成的导航信息转换为可由交通工具终端300正常显示的形 式，并且在步骤S415提供转换后的导航信息。
因此，用于提供出发地和目的地导航信息的系统和方法对当选择 出发地连接时错误地选择了高速公路和城市快速路的情况进行了补 充，并且根据交通工具想要到达的目的地的位置和类型，使用不同的 方法来选择目的地连接。
因此，本发明允许用户通过增大选择出发地和目的地的准确度来 接收出发地附近的精确的导航，并且接收容易进入期望的目的地的路 径，并且增加对于服务的满意度，这是因为它未提供目的地附近的迂 回路径。
当选择出发地连接时，用于提供出发地和目的地导航信息的系统 和方法排除了交通工具难以进入的高速公路和城市快速路，并且根据 交通工具想要到达的目的地的位置和类型，通过使用不同的方法来选 择目的地连接。因此，预先防止了当用户无法找到出发地附近的正确 道路时产生的，或者当用户无法到达目的地时出现的时间和资源的浪 费，因而提高了服务的满意度。
虽然已结合当前被认为是最实用的和优选的实施例描述了本发 明，但是应该理解，本发明不局限于所公开的实施例，相反，其意图 是覆盖在所附权利要求的精神和范围之内包含的各种变形和等价设 置。
为了便于描述，道路网络将被称为网络，其包括结点和连接。该 结点表示连接多条线的点，并且连接表示结点之间的线。
图2显示了根据本发明的典型实施例的，用于提供出发地和目的 地导航信息的系统的结构。
如图所示，提供出发地和目的地导航信息的系统100，通过无线 网络200连接到交通工具终端300，并且连接到交通信息提供中心400 其用于实时地提供各个位置的交通状况。在这种情况下，术语“交通 工具”一般指汽车，但并不局限于此。此外，交通工具终端300可以 利用笔记本电脑、PDA或者移动电话来实现。
用于提供出发地和目的地导航信息的如上连接的系统100从交 通工具终端300接收当前位置信息和移动方向信息，并且选择用户可 以容易地从其移动的出发地(称为“出发地连接”)。
在这种情况下，交通工具终端300计算交通工具的行进方向，并 且系统100在考虑所计算的行进方向的情况下选择一出发地连接，其 目的是消除当在交通工具行进的方向相反的方向上选择出发地连接 时，由于交通工具必须不情愿的转向而引起的不便。
即，用于提供出发地和目的地导航信息的系统100向用户提供道 路信息以选择出发地连接，以使得当在交通工具的行进方向上并且在 当前位置的预定范围之内(例如，半径100米的范围之内)提供了至少 两种道路(高速公路，城市快速路，立交桥，地下通道和普通道路)时， 用户可以通过使用交通工具终端300在当前位置建立道路类型。
当在交通工具的行进方向上并且在当前位置的预定范围之内未 提供两种道路时，系统100选择最接交通工具终端300的位置的连接 作为出发地连接。
此外，当在预定范围之内没有发现道路时，系统100在预定范围 之外的道路选择出发地连接。在这种情况下，出发地连接不包括高速 公路和城市快速路。
在大多数情况下，交通工具终端300一般位于除高速公路或者城 市快速路以外的普通道路，而且当高速公路或者城市快速路被选为出 发地连接时，用户不能根据导航路径行使。
当在移动时接收到路径请求时，系统100在考虑到由交通工具终 端300提供的、有关交通工具的行进方向的信息的情况下，选择一出 发地连接。在这种情况下，可以使用由安装在交通工具中的GPS提 供的各种位置信息来计算前进方向信息。
当不考虑交通工具的行进方向时，会在交通工具的行进方向的相 反方向上搜索路径，交通工具不能在所提供的路径上行使。
此外，系统100通过考虑用户期望的目的地的位置和类型来选择 目的地连接，详细地说，对目的地连接进行分类，并且根据依赖于目 的地的位置和类型的条件选择所期望的。
更具体地说，在考虑到在交通工具的行进方向的右边(或者在左 边行驶的情况下为左边)具有目的地(目的地坐标)的临近连接以及交 通工具的方向的情况下，系统100选择目的地连接，以防当用户在所 选的目的地连接和交通工具的行进方向与目的地的方向相反的情况 下而不能直接到达目的地时，终止路径导航。
当用户可以从任何方向到达目的地时(例如，十字路口或者地铁 站)，用于提供出发地和目的地导航信息的系统100选择在预定范围 内(例如，半径为300米的范围)提供的连接作为候选目的地连接，并 且在考虑到出发地连接的情况下，从选择的候选连接中确定最优化路 径的连接作为目的地连接。
此外，当提供到达目的地的多个通路时(例如，一个大公寓或公 园)，在大多数情况下，提供彼此相距较远的途径，因此，系统100 选择多个途径作为候选目的地连接，并且在考虑到出发地连接的情况 下，从所选的候选连接中确定最优化路径的连接作为目的地连接。
然而，因为当选择目的地连接时，在大多数情况下，交通工具不 能容易地进入高速公路，城市快速路，立交桥或者地道，所以系统 100再次搜索候选目的地连接，并且确定交通工具容易进入的普通道 路作为目的地连接。
高速公路休息点或加油站可以是用户实际想要去的目的地，因 此，高速公路和城市快速路上的可到达的目的地被处理为例外情况。
用于提供出发地和目的地导航信息的系统100根据所选的出发 地和目的地连接，在从出发地到目的地提供的多个路径中产生最佳的 路径，产生关于生成的路径的导航信息，把该导航信息转换为可由交 通工具终端300显示的形式，并且提供转换后的导航信息。
正如所描述的，系统100根据交通工具的位置和道路类型，以多 种方式选择出发地连接，并且根据目的地的位置和类型，通过应用不 同的方法选择目的地连接。
现在将描述用于提供出发地和目的地导航信息的系统100的详 细结构。
图3显示了根据本发明的典型实施例的，提供出发地和目的地导 航信息的系统的详细结构。
如图所示，用于提供出发地和目的地导航信息的系统100包括路 径请求接收器110，出发地选择器120，目的地选择器130，路径生 成器140，导航信息生成器150以及导航信息提供器160。
详细地说，路径请求接收器110从交通工具终端300接收包含交 通工具的当前位置(出发地位置)和目的地位置的路径请求。路径请求 可以进一步包括交通工具的移动方向。
出发地选择器120根据交通工具的当前位置控制用户选择出发 地连接，或者当在预定的范围之内未提供路径搜索网络时，从预定范 围之外选择除了高速公路和城市快速路以外的出发地连接。
目的地选择器130根据目的地的位置和类型，通过应用不同的方 法来选择目的地连接。
路径生成器140基于所选的出发地连接、目的地连接、实时的交 通信息以及地图连接信息，生成从出发地到目的地的路径。在这种情 况下，地图连接信息包括行车道的数量、速度和道路分类(例如，高 速公路、城市快速路、国道或者当地道路)中的至少一个。
导航信息生成器150通过邻接图和语音信息中的至少一个，生成 有关所生成的路径的导航信息。
导航信息提供器160把生成的导航信息转换为可由交通工具终 端300显示的形式，并且提供转换后的导航信息。
现在将描述用于提供出发地和目的地导航信息的系统100的操 作。
图4显示了根据本发明的典型实施例的，用于提供出发地和目的 地导航信息的系统的操作流程图。
如图所示，在步骤S401，路径请求接收器110从交通工具终端 300接收通过安装在交通工具中的GPS获得的，包含出发地位置信息 和目的地信息的路径请求。路径请求可以进一步包括交通工具的行进 方向。
在步骤S402，出发地选择器120根据接收的路径请求信息(交通 工具的当前位置和行进方向)选择出发地连接，并且检查在交通工具 的当前位置上，是否在预定范围(例如，半径100米的范围)之内，提 供了不同类型的道路(高速公路、城市快速路、立交桥和地道)。
当发现不同类型的道路时，在步骤S403，出发地选择器120控 制用户选择出发地连接的道路类型，并且当未同时发现不同类型的道 路时，出发地选择器120选择与交通工具最接近的连接作为出发地连 接。
当在交通工具移动的同时生成路径请求时，出发地选择器120可 以在考虑交通工具的行进方向的情况下选择出发地连接。
在这种情况下，当在范围内没有发现道路时，在步骤S404，出 发地选择器120从预定范围之外的道路中选择除高速公路和城市快 速路以外的连接。
目的地选择器130根据目的地的位置和类型选择目的地连接，详 细地说，当要选择的目的地连接是与目的地邻近的连接时，在步骤 S405，目的地选择器130通过考虑交通工具的行进方向来选择目的地 连接。
因为在多数情况下，根据具体实施例选择的目的地连接在目的地 附近，所以希望通过考虑交通工具的行进方向来选择目的地连接，如 图5所示。
图5显示了当在右边驾驶时，根据本发明的典型实施例的，在考 虑到目的地的位置和交通工具的行进方向的情况下的目的地连接。
如图所示，交通工具行进在七点钟的方向上(在西南偏南的方向 上)。目的地选择器130选择目的地连接20，以使得目的地(Lotte Department Store)可以位于交通工具的行进方向的右侧，这是因为当 在右边行使时，目的地必须位于交通工具的行进方向的右侧，以使得 交通工具能够抵达目的地。
当在左侧行使时，目的地选择器130选择目的地连接，以使得目 的地可以位于交通工具的行进方向的左边。因此，目的地选择器130 控制用户容易地到达期望的目的地。
当在步骤S407判断交通工具300想要到达的目的地不对应于进 入方向(即，交通工具的行进方向)时，例如十字路口或地铁站，那么 在步骤S408，目的地选择器130选择在关于对应的目的地坐标的预 定范围之内(例如，半径300米的范围)提供的连接，作为候选连接， 并且根据在步骤S413中的随后的最佳化路径，从所选的候选目的地 连接中选择单个连接作为最终的目的地连接，其在图6中说明。
图6显示了根据本发明的典型实施例的，当地铁站被作为目的地 时的所选的目的地连接。
如图所示，当目的地给定为Sadang station时，目的地选择器130 选择Sadang station附近的多个候选连接，并且确定最终的目的地连 接，由此防止移动终端的关于目的地的迂回路线。
在步骤S409，在大多数情况下，交通工具终端300想要到达的 公寓或者公园具有至少两条通路。
因此，在步骤S410，目的地选择器130根据多点POI(MPP)方案， 选择多个通路作为候选目的地连接，并且在步骤413根据最佳路径， 从候选连接中确定最终的目的地连接。在图7中说明了MPP方案的 一个例子。
图7显示了根据本发明的典型实施例的，当公园作为目的地时的 所选择的目的地连接。
如图所示，当目的地是Olympic Park时，目的地选择器130选择 三种通路的连接作为候选目的地连接，并且在步骤S413，根据随后 选择的最佳路径，确定最终的目的地连接。
当期望的目的地连接是高速公路、城市快速路、立交桥以及地道 中之一时，目的地选择器130再次搜索目的地连接，并且在步骤S412 中选择交通工具容易进入的普通道路，作为目的地连接。现在将参考 图8和图9描述当目的地连接是城市快速路时，选择目的地连接的方 法。
图8显示当城市快速路作为目的地连接时，通过普通路径搜索找 到的路径，图9显示当城市快速路作为目的地连接时，通过根据本发 明的典型实施例的路径搜索找到的路径。
如图8所示，当目的地连接是Sokkye Station的内部环路时，通 过普通路径搜索所得到的路径的目的地连接变为内部环路的连接，因 此，用户必须走迂回路线以到达目的地Sokkye Station。
然而，如图9所示，因为目的地连接是内部环路，所以目的地选 择器130再次搜索连接，并且确定位于内部环路之下的普通道路作为 最终的目的地道路，以使得用户可以容易地移动到期望的目的地。
在步骤S413，路径生成器140根据所选择的出发地连接、目的 地连接、由交通信息提供中心400提供的实时交通信息以及地图连接 信息，生成从出发地到目的地的路径。在这种情况下，当提供了多个 目的地连接时，路径生成器140为相应的目的地连接生成多个路径， 并且从这些路径中确定最佳路径，其在图10中说明。
图10显示了根据本发明的典型实施例的，从最终的出发地到目 的地的连接信息。
如图所示，路径生成器140选择从Jongroku(即出发地30)附近的 出发地连接40到目的地60附近的目的地连接50的单个最佳路径， 并且提供该最佳路径。
离出发地30最近的连接是内部环路，但是因为难以进入内部环 路，所以出发地选择器120选择在预定范围内提供的连接40作为出 发地连接。
在步骤S414，导航信息生成器150生成导航信息，其包含所生 成的路径的邻接图和语音信息中的至少一个，并且导航信息提供器 160把所生成的导航信息转换为可由交通工具终端300正常显示的形 式，并且在步骤S415提供转换后的导航信息。
因此，用于提供出发地和目的地导航信息的系统和方法对当选择 出发地连接时错误地选择了高速公路和城市快速路的情况进行了补 充，并且根据交通工具想要到达的目的地的位置和类型，使用不同的 方法来选择目的地连接。
因此，本发明允许用户通过增大选择出发地和目的地的准确度来 接收出发地附近的精确的导航，并且接收容易进入期望的目的地的路 径，并且增加对于服务的满意度，这是因为它未提供目的地附近的迂 回路径。
当选择出发地连接时，用于提供出发地和目的地导航信息的系统 和方法排除了交通工具难以进入的高速公路和城市快速路，并且根据 交通工具想要到达的目的地的位置和类型，通过使用不同的方法来选 择目的地连接。因此，预先防止了当用户无法找到出发地附近的正确 道路时产生的，或者当用户无法到达目的地时出现的时间和资源的浪 费，因而提高了服务的满意度。
虽然已结合当前被认为是最实用的和优选的实施例描述了本发 明，但是应该理解，本发明不局限于所公开的实施例，相反，其意图 是覆盖在所附权利要求的精神和范围之内包含的各种变形和等价设 置。