导航系统、路径搜索服务器、路径搜索方法及程序

摘要

本发明提供存在多个目的地点或出发地点时，在1次路径搜索处理中能够搜索最佳路径的导航系统。导航系统(10)具备存储关注目标场所的属性信息的POI属性信息数据库(40)，网络数据编辑机构(38)，假想节点设定机构(39)。根据出发地及/或目的地，参照POI属性信息数据库(40)，判别出发地及/或目的地上是否存在多个POI。当存在多个POI时，假想节点设定机构(39)，设定用与多个POI的各节点具有相等链路成本值的链路连接的假想节点，网络数据编辑机构(38)在搜索用网络数据上暂时的追加假想节点，路径搜索机构(33)利用已追加该假想节点的搜索用网络数据(35)，进行路径搜索。

说明书

技术领域

本发明涉及搜索从出发地到目的地的最佳路径并进行向导的导航系统、路径搜索服务器、路径搜索方法及程序，特别涉及在存在多个目的地点或出发地点时，能够在一次的路径搜索处理中搜索到最佳路径的导航系统、路径搜索服务器、路径搜索方法及程序。

所谓存在多个目的地点、出发地点的路径搜索，是指想要搜索例如主题公园、活动会场、交通工具的车站等存在多个出入口的路径搜索、当前位置、到离目的地较近范围内的便利商店、汽油加油站等的关注目标场所(POI：Point of Interest)路径的情况等。

背景技术

以往，大家都知道利用地图数据、道路数据，搜索从期望的出发地到目的地的路径向导利用者的导航装置、导航系统。

作为这样的导航装置、导航系统，有已被实用化了的例如装载在汽车上、给司机向导路径的车辆导航装置，或以手机为导航终端加以利用，向路径搜索服务器发送路径搜索要求，接收其结果、接受路径向导的通信型的导航系统等。

特别是通信型导航系统，是以手机等便携式终端作为导航终端加以利用的系统，即使是作为步行者用导航系统，也可以使用。作为步行者用导航系统，最佳方式是附加包含交通工具的路径向导功能，加在利用道路网络数据的汽车、徒步路径的搜索和向导上，在路径搜索服务器上将交通工具的路线、运行时刻数据作为交通网络数据进行存储。

这样的步行者用导航系统，具有将从期望的出发站到期望的目的站的路径(乘车候补列车)，加在徒步路径的搜索和向导上进行向导的功能。另外，也存在不随着徒步路径的路径搜索，从信息分发服务器接受交通工具的路线、时刻表、可乘坐的列车等的信息的分发，进行显示的交通向导系统。

另外，大家也知道利用飞机、列车、电车、汽车等交通工具，搜索从出发地到目的地的路径进行向导的路径搜索系统。这样的路径搜索系统，一般根据用户指定的出发日期时间、出发地、目的地、到达时刻等的路径搜索条件，进行路径搜索。

也就是说，参照将各交通工具的路线数据、运行时刻数据进行数据库化的交通网络数据，连接包含换乘的出发地和目的地，以可利用的各交通工具为路径进行顺次搜索，提出1个或多个与路径搜索条件相符合的向导路径(列车等的交通工具)的候补。作为路径搜索条件，一般都进一步地可指定出所需时间、换乘次数、票价等的条件。

在利用上述那样的道路网络数据进行路径搜索得到的从出发地到目的地的路径中，以路径的累计成本(距离或时间)最小的路径作为最佳向导路径被决定，生成向导路径数据。在向导路径数据中，在最佳路径的数据之外，还包含地图数据、导航数据，向导路径数据是根据需要，从向导数据存储机构中被读出的，显示在显示机构上。

一般按照，在包含利用具有导航装置的GPS接收机进行测位的导航装置的当前位置的一定比例尺、一定范围的地图内，使向导路径和表示导航装置的当前位置的标记重合，该当前位置标记成为显示画面中心的方式来进行显示。

由于利用GPS接收机进行测位的位置信息上含有误差，所以当当前位置从向导路径上偏离时，要进行将当前位置修正到向导路径上的路线匹配处理和修正到地图上最近的道路上的地图匹配处理。

另外，在向导路径数据上设定交差点等导航点，作为其导航点处的导航，附加语音向导(例如，“前面300m是交差点，请左转”等语音信息)数据时，通过扬声器，再生输出语音信息，向导用户。

上述导航系统、路径搜索方法，例如在下述的专利文献1(特开2000-258184号公报)中，作为“交通网络路径搜索方法及装置”被本申请人公开。

上述路径搜索导航系统，将从出发地点到目的地点的路径作为以地点为节点、地点间为链路的道路网络、交通网络的数据进行表现，利用计算机，通过标签确定法搜索出在最短成本条件下的徒步区间、交通工具利用区间。

在此路径搜索方法中，利用经度纬度信息，求得从出发地点及目的地点到所利用的交通工具的车站的直线距离，作为从出发地点及目的地点到所利用交通工具的车站的路径，以该直线距离为变量算出平均成本。

而且，求得在上述平均成本指定的成本范围内所包含的全部的利用交通工具的车站，决定步行路径，通过将求得的步行路径插入到交通工具的交通网络路径中，表现综合交通网络，利用计算机，在通过标签确定法求得的成本条件下，进行搜索。

在利用徒步和交通工具的路径搜索的情况下，有车站内存在多个出入口的情况。大家也知道考虑多个出入口，从出发地到就近车站的各出入口的徒步路径或从就近车站的各出入口到目的地的徒步路径中，搜索路径最短路径的路径搜索方法。例如，在下述的专利文献2(特开2003-182578号公报)中，由本人公开的“最佳路径搜索装置、最佳路径搜索方法”。

此最佳路径搜索装置，当出发地、目的地、出发预定日期时间的搜索条件被指定、搜索被指示时，最佳路径搜索部，利用道路数据和交通工具的时刻表数据，决定出发地就近的1个或多个出发站候补和目的地就近的1个或多个目的站候补。而且，其构成为在各出发站候补和各目的站候补的组合中，通过徒步和交通工具的组合，按照指定搜索条件，搜索出最短时间内可从出发地移动到目的地的最佳路径。当出发站候补、目的站候补具有多个出入口时，其构成为以出发地周边的就近的1个出入口作为出发站候补、目的站候补的车站位置，搜索最佳路径。

图9及图10是表示公开于上述专利文献2的最佳路径搜索装置中的以往的路径搜索的概念的说明图。图9是表示从出发地(START)到就近车站及其出入口的路径搜索的概念的说明图，图10是表示从就近车站及其出入口到目的站(GOAL)的以往的路进搜索的概念的说明图。

通过利用交通工具的路径搜索，当搜索出从出发地到目的地的电车路径、就近车站时，最佳路径搜索装置如图9所示，顺次搜索从出发地(START)到就近车站ST1、ST2及其每个出入口A1～A4、A5、A6的各出入口最短的徒步路径RT1～RT4、RT5、RT6。因此，徒步路径的搜索次数变成相当于出入口数目的次数。

下面，如图10所示，顺序搜索从目的地侧的各就近车站ST3、ST4及其出入口B1、B2、B3、B4到目的地(GOAL)的最短徒步路径RP1、RP2、RF1、RF2。因此，徒步路径的搜索次数变为相当于出入口数目的次数。还有，在图9、图10中，L1～L4表示电车路线，R0表示从出发地(START)抽出就近车站ST1和ST2的范围，抽出目的地(GOAL)侧的就近车站ST3、ST4的范围的半径距离。

另外，在导航系统中，在以特定的目的地、出发地为路径搜索条件，向路径搜索服务器要求路径搜索的情况以外，也存在不以特定的场所为目的地，进行到达实现某条件的场所的路径搜索要求的情况。例如，在开车移动到以某设施为目的地的情况下，无论怎样都需要停车，所以有设施周边的停车场为实质目的地的情况。此时，周边的停车场在哪都可以，总之希望以停车场作为目的地。

能进行这样的路径搜索的导航系统也被公开过。例如，在下述的专利文献3(特开2003-057057)中，公开了“停车场信息检索方法、停车场信息检索系统及程序”。此停车场信息检索系统，其构成为根据终端装置来的路径搜索条件，网络导航中心进行路径检索时，网络导航中心检索目的地周边的多个停车场，在搜索出到各停车场的最短路径后，向导最近路径的停车场。

另外，也存在搜索要求去特定的主题公园、博览会会场等的特定区域的路径的情况。图11是表示这样特定区域的地图的图。如图11所示，在作为活动会场的特定区域上，设计了3个出入口G1～G3。这样的情况下，通常用户不认识特定区域的多个出入口，以认识该区域全部范围为目的地，在从其出入口中，要求进行从出发地到最近的出入口的路径向导。

即使在这样的路径搜索中，在以往的路径搜索服务器中，也可象上述专利文献3公开的停车场信息检索方法所示，抽出搜索要求的特定区域的出入口G1～G3，分别重复从出发地到各出入口G1～G3的路径搜索，向导最短的出入口或在距离较近顺序中向导几个推荐路径。

专利文献1：特开2000-258184号公报(图4)

专利文献2：特开2003-182578号公报(图9、图10)

专利文献3：特开2003-057057号公报(图3、图6、段落[0089]、[0090])

发明内容

发明预解决的问题

在导航系统中，有期望进行包含如前述那样的停车场的向导的情况，也有期望从就近车站的多个出入口中、进行徒步路径最短的出入口的向导的情况。在这样的路径搜索中，如根据上述专利文献3中公开的导航系统的搜索的构成，即在网络导航中心(路径搜索服务器)侧，抽出目的地周边的停车场、搜索到各停车场的路径，则具有如下步骤。

也就是说，重复从出发地到路径搜索服务器抽出的各停车场的路径搜索，分别搜索到各停车场的最短路径，当搜索出到各个停车场的最短路径时，路径搜索服务器以从出发地到最近停车场的路径或者离出发地最近顺序中的多个路径作为向导路径，分发给终端装置。

图12是表示搜索从出发地(START)到目的地周边的最近的POI路径的以往路径搜索概念的模式图。在图12中，在以往的路径搜索方法中，目的地附近的某区域(AR)内的关注目标场所(POI)、例如关注目标场所为停车场时，抽出停车场G1～G5。而且，路径搜索服务器搜索从出发地(START)到停车场G1的最佳路径。图中，由出发地(START)的箭头是概念的表示路径搜索方向。

接着，路径搜索服务器搜索从出发地(START)到停车场G2的最佳路径，同样搜索从出发地(START)到停车场G3、停车场G4、停车场G5的最佳路径。也就是说，此时路径搜索服务器对于各停车场G1～G5，进行5次的路径搜索。其结果向终端装置提供得到的从出发地(START)到最近的停车场及那里的路径，或从出发地(START)到停车场距离较近顺序中的2至3个路径候补。

也就是说，在专利文献3公开的导航系统中，路径搜索服务器要以抽出的停车场数目重复进行到各停车场的路径搜索，存在路径搜索服务器中的搜索处理的负载过大的问题。

在通信型的导航系统中，向路径搜索服务器的向导要求由各终端装置随机发出，所以如果向导要求一时集中、路径搜索服务器上路径搜索处理的负载集中时，存在产生服务器性能减退、终端装置侧的等待时间增大这些不适的问题。

即使从出发地徒步去就近车站时，如果车站有多个入口，和前述的停车场的情况相同，由于在路径搜索服务器侧，以车站入口的数目设定目的地，重复路径搜索，求得最近的入口，所以也存在和前述同样的问题。

作为上述的路径搜索要求有各种各样的情况，除了前述的车站出入口、停车场为搜索条件的情况以外，例如有用于具有多个出入场口的主题公园、万国博览会会场的访问、目的地周边的便利商店、汽油加油站或西餐馆、旅馆等的用户兴趣目标的场所(POI)的访问的路径搜索要求等。

本申请的发明者，为了解决上述问题，重复种种研究的结果，想到了如果从多个POI位置的节点，用链路成本0的链路连接的假想节点(不具有经度、纬度的位置信息)追加到搜索用网络数据上，用1次的路径搜索，搜索到该假想节点的路径时，能够向导从出发地利用最近路径到达的路径，以实现完成本发明。

也就是说，本发明以解决上述问题为课题，目的在于提供一种当存在多个目的地点或出发地点时，能够在1次的路径搜索处理中搜索出最佳路径的导航系统、路径搜索服务器、路径搜索方法及程序。

用于解决问题的手段

为了解决上述课题，关于本申请的权利要求1的发明涉及利用搜索用网络数据，搜索从出发节点到目的节点的路径的导航系统，其特征在于，

上述导航系统具备存储关注目标场所的属性信息的POI属性信息数据库、网络数据编辑机构和假想节点设定机构，并

根据出发地及/或目的地，参照POI属性信息数据库，判别出发地及/或目的地上是否存在多个POI，

当存在多个POI时，上述假想节点设定机构，设定用与各上述多个POI节点具有链路成本相等值的链路来连接的假想节点，

上述网络数据编辑机构在上述搜索用网络数据上追加上述假想节点，路径搜索机构利用已追加该假想节点的搜索用网络数据，进行路径搜索。

另外，关于本申请的权利要求2的发明为，在涉及权利要求1的发明的导航系统中，其特征在于，从上述POI到假想节点的链路成本的值为0。

另外，关于本申请的权利要求3的发明为，在涉及权利要求1或权利要求2的发明的导航系统中，其特征在于，上述导航系统，其构成上具备发送路径搜索条件的导航终端装置和通过网络与上述导航终端装置连接的路径搜索服务器。

关于本申请的权利要求4的发明涉及通过网络，与发送路径搜索条件的导航终端装置连接的路径搜索服务器，其特征在于，

上述路径搜索服务器具备存储关注目标场所的属性信息的POI属性信息数据库、网络数据编辑机构和假想节点设定机构，并

根据出发地及/或目的地，参照POI属性信息数据库，判别出发地及/或目的地上是否存在多个POI，

当存在多个POI时，上述假想节点设定机构，设定用与上述多个POI的各节点具有链路成本相等值的链路来连接的假想节点，

上述网络数据编辑机构，在上述搜索用网络数据上追加上述假想节点，路径搜索机构利用已追加该假想节点的搜索用网络数据，进行路径搜索。

另外，关于本申请的权利要求5的发明为，在涉及权利要求4的发明的路径搜索服务器中，其特征在于，从上述POI到假想节点的链路成本值为0。

关于本申请的权利要求6的发明涉及利用搜索用网络数据，搜索从出发节点到目的节点的路径的路径搜索方法，其特征在于，

上述导航系统具备存储关注目标场所的属性信息的POI属性信息数据库、网络数据编辑机构和假想节点设定机构，并含有

根据出发地及/或目的地，参照POI属性信息数据库，判别出发地及/或目的地上是否存在多个POI的步骤，

当存在多个POI时，上述假想节点设定机构，设定用与上述多个POI的各节点具有链路成本相等值的链路来连接的假想节点的步骤，

上述网络数据编辑机构在上述搜索用网络数据上追加上述假想节点，路径搜索机构利用已追加该假想节点的搜索用网络数据，进行路径搜索的步骤。

另外，关于权利要求7的发明为，在关于权利要求6发明的路径搜索方法中，其特征在于，含有使从上述POI到假想节点的链路成本值为0的步骤。

关于本申请的权利要求8的发明涉及于一种被构成具备发送路径搜索条件的导航终端装置和通过网络与上述导航终端装置连接的路径搜索服务器的导航系统中的路径搜索方法，其特征在于，

上述路径搜索服务器，具备存储关注目标场所的属性信息的POI属性信息数据库、网络数据编辑机构和假想节点设定机构，并含有

根据出发地及/或目的地，参照POI属性信息数据库，判别出发地及/或目的地上是否存在多个POI的步骤，

当存在多个POI时，上述假想节点设定机构，设定用与上述多个POI的各节点具有链路成本相等值的链路来连接的假想节点的步骤，

上述网络数据编辑机构在上述搜索用网络数据上追加上述假想节点，路径搜索机构利用已追加该假想节点的搜索用网络数据，进行路径搜索的步骤。

另外，关于本申请的权利要求9的发明为，在涉及权利要求8的路径搜索方法中，其特征在于，含有使从上述POI到假想节点的链路成本值为0的步骤。

关于本申请的权利要求10的发明涉及，

连接发送路径搜索条件的导航终端装置和通过网络与上述导航终端装置的路径搜索服务器中的一种程序，其特征在于该程序，

在具备存储关注目标场所的属性信息的POI属性信息数据库、网络数据编辑机构和假想节点设定机构、构成路径搜索服务器的计算机中，运行

根据出发地及/或目的地，参照POI属性信息数据库，实行判别出发地及/或目的地上是否存在多个POI的处理，

当存在多个POI时，上述假想节点设定机构，实行设定用与上述多个POI的各节点具有链路成本相等值的链路来连接的假想节点的处理，

上述网络数据编辑机构，实行在上述搜索用网络数据上追加上述假想节点，路径搜索机构利用已追加该假想节点的搜索用网络数据，进行路径搜索的处理。

另外，关于本申请的权利要求11的发明，其特征在于，

在关于权利要求10的发明的程序中，实行使从上述POI到假想节点的链路成本值为0的处理。

发明效果

在关于权利要求1的发明中，导航系统，具备存储关注目标场所的属性信息的POI属性信息数据库、网络数据编辑机构和假想节点设定机构，根据出发地及/或目的地，参照POI属性信息数据库，判别出发地及/或目的地上是否存在多个POI。

而且，当存在多个POI时，上述假想节点设定机构，设定用与上述多个POI的各节点具有链路成本相等值的链路来连接的假想节点，上述网络数据编辑机构，在上述搜索用网络数据上追加上述假想节点，路径搜索机构利用已追加该假想节点的搜索用网络数据，进行路径搜索。

由于从假想节点PN连接各停车场G1～G5的链路的链路成本不依据实际距离，而全是[0]，所以假想节点PN和各POI的距离是假想的等距离。因此，如果经由特定POI的路径是最短距离，则其路径变为从出发地(START)到各POI的路径中最短的路径，变得可在1次路径搜索中，从多个POI中提供最近的POI和到其最近POI的路径。

在关于权利要求2的发明中的涉及权利要求1的发明的导航系统中，从POI到假想节点的链路成本值为0，因此，在路径搜索中不会产生向周边的搜索的扩散，能够进行有效地路径搜索。

在关于权利要求3的发明中的关于权利要求1或权利要求2的发明的导航系统中，导航系统其构成上具备发送路径搜索条件的导航终端装置和通过网络与上述导航终端装置连接的路径搜索服务器。因此，变得能够提供通信型导航系统，另外，路径搜索服务器变得能够在1次路径搜索中，从多个POI中提供最近的POI和到其最近POI的路径。

在关于权利要求4、权利要求5的发明中，变得可提供分别构成关于权利要求1、权利要求2发明的导航系统的路径搜索服务器。路径搜索服务器，变得能够在1次路径搜索中，从多个POI中提供最近的POI和到其最近POI的路径。

在关于权利要求6、权利要求7的发明中，可提供分别关于权利要求1、权利要求2发明的导航系统中的路径搜索方法，它能够在1次路径搜索中，从多个POI中提供最近的POI和到其最近POI的路径。

在关于权利要求8、权利要求9的发明中，可提供分别关于权利要求4、权利要求5发明的路径搜索服务器中的路径搜索方法。路径搜索服务器，能够在1次路径搜索中，从多个POI中提供最近的POI和到其最近POI的路径。

在关于权利要求10、权利要求11的发明中，可提供分别用于实现关于权利要求4、权利要求5发明的路径搜索服务器的程序。路径搜索服务器，能够在1次路径搜索中，从多个POI中提供最近的POI和到其最近POI的路径。

附图说明

图1是表示搜索从出发地(START)到存在于目的地附近的某区域(AR)内的多个关注目标场所(POI)G1～G5中、最近的POI的路径的本发明的路径搜索概念的模式图。

图2是表示构成关于本发明的导航系统构成的模块图。

图3是表示存储关注目标场所等的POI属性信息的数据库中的数据构成的图。

图4是表示道路网络的数据概念的模式图。

图5是表示交通网络的数据概念的模式图。

图6是用于说明出发地侧存在多个出入口时的路径搜索概念的说明图。

图7是用于说明出发地侧、目的地侧双方存在多个出入口、POI时的路径搜索概念的说明图。

图8是表示本发明的导航系统的路径搜索步骤的流程图。

图9是用于说明搜索从出发地到具有多个出入口的就近车站的路径的以往路径搜索方法概念的说明图。

图10是用于说明搜索从具有多个出入口的就近车站到目的地的路径的以往路径搜索方法概念的说明图。

图11是用于说明到主题公园等、具有多个出入口的特定区域的路径搜索的概念的说明图。

图12是用于说明搜索到多个目的地点的以往路径搜索方法说明图。

图中符号说明

10-导航系统                 11、12-网络

20-导航终端装置             21-控制机构

22-通信机构                 23-测位机构

24-显示机构                 25-向导路径数据存储机构

26-分发要求编辑机构         27-操作·输入机构

30-路径搜索服务器           31-控制机构

32-路径向导机构             33-路径搜索机构

34-通信机构                 35-搜索用网络数据

36-道路网络数据             37-交通网络数据

38-网络数据编辑机构         39-假想节点设定机构

40-POI属性信息DB(数据库)    50-POI信息提供服务器

具体实施方式

下面，利用实施例及附图，详细地说明本发明的具体例。图1是表示搜索从出发地(START)到存在于目的地附近的某区域(AR)内的多个关注目标场所(POI)G1～G5中、最近的POI的路径的本发明的路径搜索概念的模式图。

实施例

还有，在以下的本发明的实施例的说明中，含有关注目标场所、多个出入口的车站等，包括存在多个地点的出发地点、目的地点，统称关注目标场所(POI)，在明确表示车站的出入口、特定主题公园等的出入口时，也有称为出入口的情况。

在图1中，当抽出目的地附近的停车场G1～G5时，路径搜索服务器，从各停车场G1～G5的节点位置，设定用链路成本为[0]值的链路连接的假想节点PN。此假想节点PN是为了路径搜索，假想连接到路径搜索网络上的，由于仅用于链路成本累计的运算，所以不需要像路径搜索网络的节点那样，要具有由纬度、经度组成的位置信息。另外，假想节点只在路径搜索上必需，所以也不必显示出来。因此，对假想节点设定位置信息的值的处理一概都不需要。

当假想节点PN被设定时，路径搜索服务器搜索从出发地(START)到假想节点PN的最佳路径GR。在此路径搜索中，由于从假想节点PN连接各停车场G1～G5的链路的链路成本不依据实际距离，全部为[0]，所以假想节点PN和各停车场G1～G5的距离是假想的等距离的。

因此，如果经由停车场G3的路径是最短路径，其路径就变成了从出发地(START)到各停车场G1～G5的路径中最短的路径，变得可在1次的路径搜索中，从多个停车场G1～G5中向导航终端装置20提供最近的停车场及到其最近停车场的路径。

这里，从各停车场G1～G5到假想节点PN的链路的链路成本，逻辑上其各个值相等即可，不需要值一定是[0]。然而，当链路成本为[0]以外的值时，路径搜索时迪杰斯特拉(Dijkstra)算法中的扩散，会有向周边延伸该值的部分，存在增大路径搜索处理时间的情况。

这点、如果链路成本的值为[0]，则在搜索到达假想节点PN上的时刻，结束路径搜索处理。也就是说，如果假想节点PN的链路成本的值为[0]，能够有效地进行路径搜索处理。

图2是表示关于本实施例的导航系统的构成的模块图。关于本实施例的导航系统10，如图2的模块图所示，其构成上具备通过因特网等的网络11，进行通信的导航终端20和路径搜索服务器30。

导航终端装置20，向路径搜索服务器30设定出发地和目的地等的路径搜索条件，发送路径搜索要求，路径搜索服务器30按照路径搜索条件，参照由道路网络数据、交通网络数据组成的搜索用网络数据，搜索出最佳路径，并将其最佳路径编辑到向导路径数据上，分发给导航终端装置20。

路径搜索服务器30具备，搜索用网络数据35(数据库)，其存储包含用于步行者导航系统、车辆导航系统中路径搜索的地图数据的道路网络数据36，和用于搜索利用交通工具的路径区间的交通网络数据37；和POI属性信息DB(数据库)40，其存储POI属性信息。

存储在POI属性信息DB40中的POI属性信息，如图3所示那样，存储了每个关注目标场所(POI)的位置坐标(纬度、经度)和属性信息，在属性信息上存储了到该POI的链路的端点的节点数和各节点的位置信息，另外还存储了各POI的类别。

例如，POI的A是主题公园A，连接到该主题公园的链路、即出入口链路有3个，存储了其3个链路端点节点的位置。万国博览会等的活动会场、主题公园、交通工具的各车站的出入口也是同样的。这些POI及其属性信息，路径搜索服务器30通过网络12，可从POI信息提供服务器50上收集(参照图2)。

当导航终端装置20进行以特定的主题公园、活动会场为目的地的路径搜索要求时，路径搜索服务器30参照POI属性信息DB40，判定该主题公园、活动会场是否有多个出入口。在利用交通工具的路径搜索中，在搜索目的地或出发地的就近车站时，在搜索出到该就近车站的徒步路径区间时，同样也参照POI属性信息DB40，判断就近车站是否有多个出入口。当有多个出入口时，路径搜索服务器30设定上述的假想节点，进行路径搜索。

另外，对于停车场、汽油加油站、便利商店、旅馆等的POI，其类别信息作为属性信息被存储。作为路径搜索条件，当有从导航终端装置20来的到目的地、出发地附近的特定的POI，例如到达汽油加油站中、最近的汽油加油站的路径搜索要求时，路径搜索服务器30参照POI属性信息DB40，抽出目的地、出发地附近的该POI。而且，路径搜索服务器30，以被抽出的POI作为多个目的地，设定前述的假想节点进行路径搜索。

假想节点设定机构39(参照图2)，路径搜索多个POI时，或者进行包含具有多个出入口的目的地、出发地的路径搜索时，像在图1中说明的那样，从被抽出的各POI或从出入口的节点，设定用链路成本为[0]连接的假想节点PN。网络数据编辑机构38，实行将假想节点设定机构39设定的假想节点PN暂时的追加到搜索用网络数据35的数据上的处理。

而且，路径搜索机构33，进行以通过网络数据编辑机构38追加到搜索用网络数据35上的假想节点PN为目的地或出发地的路径搜索。在从导航终端装置20来的路径搜索条件要求从特定的出发地到目的地的路径搜索的通常情况下，当然利用不追加假想节点PN的搜索用网络数据35，进行路径搜索。

路径向导机构32，用于编辑路径搜索机构33搜索的最佳路径或多个推荐向导路径的数据，分发给导航终端装置20。通信机构34，用于接收从导航终端装置20来的各种要求，或分发给导航终端装置20各种信息。

用于步行者导航系统、车辆导航系统中的路径搜索的道路网络数据36，构成如下。例如，当道路如图4所示，由道路A、B、C组成时，以道路A、B、C的端点、交差点、转弯点等为节点，用有向性的链路表示连接各节点的道路，其通过节点数据(节点的纬度、经度)，和以链路数据(链路编号)与各链路的链路成本(行走链路的距离或链路所必需的时间)为数据的链路成本数据构成。

也就是说，在图4中○符号、◎符号表示节点，◎符号表示道路的交差点。连接各节点的有向性的链路用箭头线(实线、虚线、2点点划线)表示。链路上存在道路的上行、下行、朝向各个方向的链路，而图4中为了简略化图示，只图示了箭头方向的链路。

以这样的道路网络数据作为路径搜索用的数据库，进行路径搜索时，沿着被连接的从出发地的节点到目的地的节点的链路，累积其链路成本，搜索出累积链路成本最小的路径进行向导。也就是说，在图4中，当以出发地为节点AX、目的地为节点CY，进行路径搜索时，顺次沿着从节点AX、行走道路A、在第2个交差点右转、进入道路C到达节点CY的链路，累积链路成本，搜索出链路成本的累积值最少的路径进行向导。

在图4中未图示从节点AX到节点CY的其他的路径，但实际上由于也存在其他那样的路径，所以同样也搜索可从节点AX到节点CY的其他路径，再决定那些路径中链路成本最少的路径作为最佳路径。这种方法通过被称为迪杰斯特拉(Dijkstra)算法的周知的方法进行。

与此相对，用于交通工具的路径搜索的交通网络数据37，按照以下方式构成。例如图5所示，当由交通路线A、B、C组成时，以设计在各交通路线A、B、C上的各车站(飞机路线上为各机场)为节点，用有向性链路表示连接各节点间的区间，以节点数据(纬度、经度)、链路数据(链路编号)作为网络数据。在图5中，○符号、◎符号表示节点，◎符号表示交通路线的换乘点(乘换站等)，用箭头线(实线、虚线、2点点划线)表示连接各节点间的有向性的链路。链路上存在朝向着交通路线的各个上行、下行方向的链路，而图5中为了简略化图示，只图示了箭头方向的链路。

然而，交通网络和道路网络相比，链路成本基本上不同。也就是说，在道路网络中，链路成本是固定的，静止的，而在交通网络中，如图5所示，运行交通路线的列车、飞机(以下各个列车、飞机等的各路径称为交通工具)有多个。从每个各交通工具的所在节点出发的时刻和到达下一个节点的时刻固定(在时刻表数据、运行数据中被规定)，而且有各个路径未必都链接邻接的节点的情况。例如，快速列车车和各站停车的列车的情况。此种情况下，变成了在相同交通路线上存在不同的多个链路，另外也有节点间的所需时间由于交通工具而不同的情况。

在如图5例示的交通网络中，在交通路线A的同一链路上存在多个交通机构(路径)Aa～Ac…、在交通路线C上存在多个交通机构(路径)Ca～Cc…。因此，交通工具的运行网络和单纯的道路网络不同，节点、链路、链路成本的各数据，变成与交通机构(各个飞机、列车等的路径)的总数成比例的数据量。由此，交通网络的数据和道路网络的数据量相比，变成了庞大的数据量。因此，与其相对应，路径搜索所需的时间变得也需要更多的时间。

为了利用这样的交通网络数据，搜索从某出发地到某目的地的路径时，需要搜索从出发地到达目的地时所能够使用(乘坐)的全部的交通机构，特定出符合搜索条件的交通机构。

例如，在图5中，指定以出发地为交通路线A的节点AX的某特定出发时刻，进行以交通路线C的节点CY为目的地的路径搜索时，在运行交通路线A上的交通机构Aa～Ac…中，以出发时刻以后的全部的交通机构顺次作为出发时的路径进行选择。而且，根据去交通路线C的乘换节点的到达时刻，在运行交通路线C上的各交通机构Ca～Cc…中，搜索出在乘换节点中、可乘坐的时刻以后的交通机构的全部的组合，累计各路径的所需时间、乘换次数等，进行向导。

另一方面，导航终端装置20，其构成具备控制机构21、通信机构22、测位机构23、显示机构24、向导路径数据存储机构25、分发要求编辑机构26、操作·输入机构27。测位机构23具备GPS接收机，接收、处理GPS卫星信号，测位导航终端装置20的当前位置(纬度、经度)。

通信机构22包含无线通信单元，用于与路径搜索服务器30进行通信。操作·输入机构27由按键、刻度盘等组成，作为用于操作导航终端装置20的输入、出发地、目的地等的输入功能使用。显示机构24由液晶显示面板等组成，被用于路径搜索服务器30分发的向导路径数据的向导路径、地图的显示。另外，显示机构24，显示菜单画面，功能上也作为用于操作导航终端装置20的输入机构。分发要求编辑机构26，以使用操作·输入机构27输入的出发地、目的地或利用测位机构23测位的导航终端装置20的当前位置为出发地，根据这些信息，生成向路径搜索服务器30发送的路径搜索要求。

向导路径数据存储机构25，存储路径搜索服务器30分发的作为路径搜索结果的向导路径数据、地图数据、导航数据等。这些数据根据需要，由向导路径数据存储机构25读出，显示在显示机构24中。一般的，在包含利用测位机构23测位的导航终端装置20的当前位置的一定比例尺、一定范围的地图内，按照使向导路径和标示导航终端装置20的当前位置的标记相重叠，使该当前位置标记成为显示画面的中心的方式来显示。

由于通过测位机构23接收GPS卫星信号，在测位的当前位置信息(纬度、经度的信息)上包含误差，所以当当前位置从向导路径上偏移时，要进行修正当前位置到向导路径上的路线匹配处理。另外，在路径搜索服务器30分发的向导路径数据上附加语音向导(例如，“前方300m是交差点，请左转”的语音信息)数据时，通过扬声器，再生输出语音信息，向导用户。

下面，针对关于以上说明的本发明的实施例的导航系统10中的路径搜索方法进行说明。对于目的地侧存在多个出入口或POI时的由本发明组成的路经搜索的概念，是按照参照图1进行说明的。同样的路径搜索也可能在出发地侧。图6表示对于目的地(GOAL)、出发地侧的车站ST1存在多个出入口A1～A5时的图。

当搜索出发地的就近车站ST1时，路径搜索服务器参照车站ST1的POI属性信息DB40，判别是否有多个出入口。如图6所示，当车站ST1有多个出入口A1～A5时，设定从出入口A1～A5的节点位置以具有链路成本为0的链路连接的假想节点PN。此假想节点PN是为了路径搜索而被假想连接到路径搜索网络上的，不需要具有纬度、经度组成的位置信息。

当假想节点PN被设定时，路径搜索服务器搜索从假想节点PN到目的地(GOAL)的最佳路径GR。在此路径搜索中，由于从假想节点PN连接各出入口A1～A5的链路的链路成本不依据实际距离、全部为0，所以假想节点PN和各出入口A1～A5的距离是假想的等距离。

因此，如果经由出入口A3的路径RT1是最短距离，就变成了其路径是出发地侧的出入口A1～A5路径中的最短路径。因此，能够在1次路径搜索中，向导航终端装置20提供从多个出入口A1～A5到目的地(GOAL)的最近的出入口和到目的地(GOAL)的路径。

同样地，出发地侧、目的地侧同时具有多个出入口、POI时的路径搜索也是可能的。图7是用于说明这样的路径搜索概念的说明图。图7是表示在从导航终端装置20来的路径搜索要求中，出发地侧的就近车站等的POI处存在多个出入口A1～A5，目的地侧的主题公园等的POI处存在多个出入口G1～G5的情况。

当这样的路径搜索要求从导航终端装置20向路径搜索服务器30要求时，路径搜索服务器30首先参照POI属性信息DB40，判别各个出发地侧、目的地侧是否存在多个出入口。当存在多个出入口时，抽出各出入口A1～A5、G1～G5。接着，假想节点设定机构39，从出发地侧的各个出入口A1～A5，设定用链路成本为0的链路连接的假想节点PN1，从目的地侧的各个出入口G1～G5，设定用链路成本为0的链路连接的假想节点PN2。

接着，在路径搜索服务器30中，网络数据编辑机构38，将假想节点PN1、PN2暂时的追加到搜索用网络数据35上。在图7中，虚线模式地表示搜索用的网络，已追加了假想节点PN1、PN2。路径搜索机构33，利用此搜索用网络数据35，搜索从假想节点PN1到假想节点PN2的最佳路径。

此搜索可在迪杰斯特拉(Dijkstra)算法等、一般的路径搜索中使用的方法下进行。即实际进行路径搜索的范围变成在实际的搜索用网络上，通过设置假想节点PN1(出发地侧)和假想节点PN2(目的地侧)，在此间求得的最佳路径在同时特定了出发地、目的地这一点上具有特征。

由于假想节点PN1和各出入口A1～A5间的链路成本全部相等为0，假想节点PN2和各出入口G1～G5间的链路成本全部相等为0，所以路径搜索的结果、可得到从假想节点PN1到假想节点PN2的最短路径RT1，此最短路径RT1经由的出发地侧的出入口A5和目的地侧的出入口G1分别变成出发地侧、目的地侧的最佳出入口。

还有，图7的情况，由于出发地侧是从出发地一定范围内的交通工具的车站，所以路径RT1以交通工具的路线路径为中心。另外，搜索包含目的地侧主题公园的出入口G1的就近车站的向导路径，搜索从就近车站到出入口G1的徒步路径，搜索出综合的向导路径RT1。从出发地到出发地侧的就近车站出入口，此时为A5间的路径作为徒步区间被路径搜索。

以上，参照图8所示的流程图，针对说明的本发明的导航系统的路径搜索步骤，进行说明。在步骤S10的处理中，路径搜索服务器30，从导航终端装置20接收路径搜索条件。

路径搜索服务器30接收路径搜索条件时，首先在步骤S11的处理中调查出发地侧的条件，在步骤S12的处理中，参照POI属性信息DB40，判断出发地侧是否存在多个POI。如果出发地侧不存在多个POI，进入步骤S14的处理，决定以出发地作为出发地节点。

在步骤S12的处理中，当出发地侧存在多个POI时，假想节点设定机构39，从多个POI的各个节点，设定用链路成本[0]的链路连接的假想节点(出发地侧)，进入步骤S15的处理。在步骤S15的处理中，路径搜索服务器30调查目的地侧的条件，在步骤S16的处理中，参照POI属性信息DB40，判断目的地侧是否存在多个POI。如果目的地侧不存在多个POI，进入步骤S17的处理，决定以目的地作为目的地节点。

在步骤S16的处理中，当目的地侧存在多个POI时，在步骤S18中，假想节点设定机构39，从多个POI的各个节点设定用链路成本[0]的链路连接的假想节点(目的地侧)，进入步骤S19的处理。在步骤S19的处理中，网络数据编辑机构38，在搜索用网络数据上暂时的追加假想节点设定机构39设定的出发地侧的假想节点和目的地侧的假想节点，路径搜索机构33，利用已追加假想节点的搜索用网络数据，搜索从出发地侧的假想节点到目的地侧的假想节点的最佳路径。

还有，当出发地侧或目的地侧不存在多个POI、在步骤S14或步骤S17的处理中，出发地或目的地作为出发地节点或目的地节点被决定时，步骤S19的处理中的节点当然不是假想节点，而是使用出发地节点或目的地节点。

在步骤S19的处理中，当通过路径搜索机构33搜索处最佳路径时，路径搜索服务器30，在步骤S20的处理中，将搜索的向导路径数据分发给导航终端装置20，结束处理。接收了向导路径数据的导航终端装置20，在向导路径数据存储机构25上暂时的存储向导路径数据，在显示机构24上显示地图、向导路径等。

还有，在上述的实施例中，在具有多个出入口的主题公园中，参照POI属性信息DB40，说明了设定假想节点的构成，在POI属性信息DB40中存储假想节点的数据，也可以是假想节点设定机构39，从POI属性信息DB40取得假想节点的数据的构成。

产业上的可用性

以上说明的关于本发明的路径搜索方法，可在假设多个目的地或多个出发地的各种搜索中使用。对于在车辆导航中搜索汽油加油站的场合、步行导航中搜索便利商店的场合等也是有效的。由于搜索自身可使用以往的算法，所以即使在车辆导航等的独立装置中，也不必大幅地修正，可以实施。