(57)【要約】【課題】第１地点から第２地点までの経路に関連付けられた施設の特性を経路ごとに特定する経路探索装置を提供する。 【解決手段】経路探索装置では、施設情報記憶部は、ノードおよびリンクに関連付けられた施設と、施設に設定されている指標値と、を特定する情報を記憶している。許容経路探索部は、取得した第２地点に到着したい到着時刻に基づいて移動上限時間を設定し、第１地点から第２地点までに移動する移動所要時間が上限時間以下である少なくとも１つの経路を許容経路として探索する。また、許容経路探索部は、許容経路のそれぞれに関連付けられた施設の指標値を、許容経路ごとに特定する。【選択図】図１５
2014190777.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索装置であって、
経路を構成するノードおよびリンクを特定するデータと、各リンクの通過に要する時間を表すリンクコストを特定するデータと、を記憶する経路情報記憶部と、
ノードまたはリンクの少なくとも一方に関連付けられた施設を特定するデータと、前記施設に設定された特性を特定するデータと、を記憶する施設情報記憶部と、
第１地点と第２地点とを特定するデータを取得する地点取得部と、
前記第１地点から前記第２地点までの経路を通過するのに要する時間の上限値である移動上限時間を設定する上限時間設定部と、
前記第１地点から前記第２地点までの経路の内、前記第１地点から前記第２地点まで移動するために要する時間である移動所要時間が前記移動上限時間以下である少なくとも１つの経路を許容経路として探索する許容経路探索部と、
それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設および前記施設に設定された前記特性を、前記許容経路ごとに特定する経路別特性特定部と、を備える、経路探索装置。
【請求項２】
請求項１に記載の経路探索装置であって、
前記許容経路探索部は、前記第１地点から特定のノードまでを結ぶ複数の経路の内、各リンクのリンクコストの累計値が最小となる最小コスト経路とそれ以外の非最小コスト経路とを探索し、前記特定のノードが前記第２地点である場合の前記最小コスト経路を最適経路として設定する最適経路探索部を有し、
前記経路情報記憶部は、前記第１地点から前記第２地点までの経路に含まれる複数の特定のノードのそれぞれについて、前記第１地点から前記特定のノードまでを結ぶ複数の経路の内、前記最小コスト経路および前記非最小コスト経路のリンクコストの累計値を記憶するノード別経路記憶部を有し、
前記許容経路探索部は、前記最適経路に含まれる複数の前記特定のノードを順に最適ノードとして選択し、前記最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記移動上限時間から前記最適経路のリンクコストの累計値を差し引いた許容タイム以下になる前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記最適ノードから前記第２地点までの経路が前記最適経路と同じ経路と、を組み合わせた経路を類似経路として設定する類似経路設定部を有し、
前記最適経路探索部は、前記最小コスト経路および非最小コスト経路のリンクコストの累計値が前記最適経路のリンクコスト累計値に前記許容コストを加算した値まで探索し、
前記許容経路は、前記最適経路および前記類似経路である、経路探索装置。
【請求項３】
請求項２に記載の経路探索装置であって、
前記類似経路設定部は、前記最適経路に含まれないと共に前記類似経路に含まれる前記特定のノードを順に準最適ノードとして選択し、前記準最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記許容タイムから前記最適経路と前記準最適ノードを含む前記類似経路とのリンクコストの累計値の差である経路別時間差以下である前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記準最適ノードから前記第２地点までの経路が前記類似経路と同じ経路と、を組み合わせた経路を準類似経路として設定し、さらに前記準類似経路を前記類似経路として設定した後に、設定された前記類似経路に含まれる前記準最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記許容タイムから前記最適経路のリンクコストの累計値と前記経路別時間差とを差し引いた値以下である前記非最小コスト経路がなくなるまで探索する、経路探索装置。
【請求項４】
請求項２または請求項３に記載の経路探索装置であって、
前記特性を特定するデータは、指標値であり、
前記経路探索装置は、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記経路別特性特定部は、それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の前記指標値を前記許容経路ごとに特定する、経路探索装置。
【請求項５】
請求項２から請求項４までのいずれか一項に記載の経路探索装置であって、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記経路別特性特定部は、同じノードにおいて、それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の組み合わせが同じであると共に、前記経路加算コストが異なる前記ラベル情報が付与されている場合には、前記経路加算コストが小さい方の前記ラベル情報のみを特定する、経路探索装置。
【請求項６】
請求項１から請求項５までのいずれか一項に記載の経路探索装置であって、
前記特性を特定するデータは、指標値であり、
前記経路探索装置は、さらに、
複数の前記施設から少なくとも１つの特定の施設を選択する特定施設選択部と、
前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の組み合わせの中に前記特定の施設が含まれる場合には、前記特定の施設に予め設定された指標加算値を前記許容経路の前記指標値の合計に加える指標値加算部と、を備える、経路探索装置。
【請求項７】
請求項１から請求項６までのいずれか一項に記載の経路探索装置であって、
前記施設情報記憶部は、前記施設の利用に要する時間を表す施設利用時間を記憶し、
前記特性を特定するデータは、指標値であり、
前記経路探索装置は、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられていた際に、同一の前記直前ラベルのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用された場合の前記ラベル情報には、前記経路加算コストの代わりに、前記経路加算コストと前記経路加算コストに利用された前記施設の前記施設利用時間とを足した時間を付与する、経路探索装置。
【請求項８】
請求項１から請求項７までのいずれか一項に記載の経路探索装置であって、
前記施設情報記憶部は、前記施設に設定された特定のイベントが開始するイベント開始時間と前記特定のイベントが終了するイベント終了時間とを記憶し、
前記経路探索装置は、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられている際に、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間である場合には、同一の前記直前ラベルのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間でない場合には、前記施設が利用されていない場合のみのラベル情報を付与する、経路探索装置。
【請求項９】
請求項１から請求項８までのいずれか一項に記載の経路探索装置であって、
前記許容経路探索部は、前記施設がリンクにおける任意の位置に関連付けられて記憶されている場合に、前記任意の位置を新たなノードである施設ノードとして設定すると共に、前記施設ノードに隣接する２つのノードのそれぞれを第１の隣接ノードと第２の隣接ノードとして設定し、前記施設ノードと前記第１の隣接ノードとを結ぶ第１のリンクと前記施設ノードと前記第２の隣接ノードとを結ぶ第２のリンクとのそれぞれのリンクコストを、前記第１の隣接ノードと前記第２の隣接ノードとを結ぶリンクのリンクコストの長さに対して前記第１のリンクの長さと前記第２のリンクの長さとで按分したリンクコストを設定し、新たに前記許容経路を探索する、経路探索装置。
【請求項１０】
請求項１から請求項９までのいずれか一項に記載の経路探索装置であって、さらに、
ぞれぞれの前記許容経路と、前記許容経路ごとに特定された前記施設および前記施設に設定された前記特性の内の少なくとも一方と、を関連付けて表示させる表示情報を送信する表示情報送信部を備える、経路探索装置。
【請求項１１】
ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索システムであって、
経路を構成するノードおよびリンクを特定するデータと、各リンクの通過に要する時間を表すリンクコストを特定するデータと、を記憶する経路情報記憶部と、
ノードまたはリンクの少なくとも一方に関連付けられた施設を特定するデータと、前記施設に設定された特性を特定するデータと、を記憶する施設情報記憶部と、
第１地点と第２地点とを特定するデータを設定する地点設定部と、
前記第１地点から前記第２地点までの経路を通過するのに要する時間の上限値である移動上限時間を設定する上限時間設定部と、
前記第１地点から前記第２地点までの経路の内、前記第１地点から前記第２地点まで移動するために要する時間である移動所要時間が前記移動上限時間以下である少なくとも１つの経路を許容経路として探索する許容経路探索部と、
それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設および前記施設に設定された前記特性を、前記許容経路ごとに特定する経路別特性特定部と、を備える、経路探索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置に関する。
【背景技術】
【０００２】
近年では、出発地点から到着地点までの経路を探索する経路探索装置として、自動車に搭載されたカーナビゲーションシステム、携帯電話機、携帯ゲーム機、ＰＮＤ（Personal Navigation Device）およびＰＤＡ（Personal Digital Assistant）が知られている。経路探索装置の中には、出発地点から到着地点までの経路として、利用者に複数の経路を提示するものもある。
【０００３】
例えば、特許文献１には、出発地点から到着地点までを最短時間で移動する最適経路において、任意の位置を設定して、任意の位置から一定距離の範囲内に存在する、または、任意の位置から一定時間で移動できる範囲内の施設を抽出し、抽出された施設を経由した出発地点から到着地点までの経路を探索する経路探索装置について開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２５７８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載された技術では、利用者が経由したい施設が多い場合には、その全ての施設を経由した出発地点から到着地点までの経路を探索して、探索された移動距離や所要時間を確認してから、利用者が経由したい施設を絞り込む必要があり、経由したい施設の絞り込みに時間がかかる場合があった。
【課題を解決するための手段】
【０００６】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態として実現することが可能である。
【０００７】
（１）本発明の一形態によれば、ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索装置が提供される。この経路探索装置は、経路を構成するノードおよびリンクを特定するデータと、各リンクの通過に要する時間を表すリンクコストを特定するデータと、を記憶する経路情報記憶部と；ノードまたはリンクの少なくとも一方に関連付けられた施設を特定するデータと、前記施設に設定された特性を特定するデータと、を記憶する施設情報記憶部と；第１地点と第２地点とを特定するデータを取得する地点取得部と；前記第１地点から前記第２地点までの経路を通過するのに要する時間の上限値である移動上限時間を設定する上限時間設定部と；前記第１地点から前記第２地点までの経路の内、前記第１地点から前記第２地点まで移動するために要する時間である移動所要時間が前記移動上限時間以下である少なくとも１つの経路を許容経路として探索する許容経路探索部と；それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設および前記施設に設定された前記特性を、前記許容経路ごとに特定する経路別特性特定部と、を備える。この形態の経路探索装置によれば、経路探索装置の利用者が第２地点に到着したい到着時刻までに到着できる許容経路の範囲において、施設を経由した第１地点から第２地点までの経路を利用者に提供できる。また、第１地点から第２地点までの経路探索において、移動所要時間が移動上限時間以下である許容経路のみを探索するため、移動上限時間以内に到着地点に到着できない無駄な経路が探索されない。また、許容経路に関連付けられた施設の範囲であれば、全ての施設のそれぞれについて経由する許容経路を利用者に提供できる。
【０００８】
（２）上記形態の経路探索装置において、前記許容経路探索部は、前記第１地点から特定のノードまでを結ぶ複数の経路の内、各リンクのリンクコストの累計値が最小となる最小コスト経路とそれ以外の非最小コスト経路とを探索し、前記特定のノードが前記第２地点である場合の前記最小コスト経路を最適経路として設定する最適経路探索部を有し；前記経路情報記憶部は、前記第１地点から前記第２地点までの経路に含まれる複数の特定のノードのそれぞれについて、前記第１地点から前記特定のノードまでを結ぶ複数の経路の内、前記最小コスト経路および前記非最小コスト経路のリンクコストの累計値を記憶するノード別経路記憶部を有し；前記許容経路探索部は、前記最適経路に含まれる複数の前記特定のノードを順に最適ノードとして選択し、前記最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記移動上限時間から前記最適経路のリンクコストの累計値を差し引いた許容タイム以下になる前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記最適ノードから前記第２地点までの経路が前記最適経路と同じ経路と、を組み合わせた経路を類似経路として設定する類似経路設定部を有し；前記最適経路探索部は、前記最小コスト経路および非最小コスト経路のリンクコストの累計値が前記最適経路のリンクコスト累計値に前記許容コストを加算した値まで探索し；前記許容経路は、前記最適経路および前記類似経路であってもよい。この形態の経路探索装置によれば、許容経路として、最適経路の探索および類似経路の設定を効率的に行なうことができ、第１地点から第２地点までの経路を効率的に設定できる。
【０００９】
（３）上記形態の経路探索装置において、前記類似経路設定部は、前記最適経路に含まれないと共に前記類似経路に含まれる前記特定のノードを順に準最適ノードとして選択し、前記準最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記許容タイムから前記最適経路と前記準最適ノードを含む前記類似経路とのリンクコストの累計値の差である経路別時間差以下である前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記準最適ノードから前記第２地点までの経路が前記類似経路と同じ経路と、を組み合わせた経路を準類似経路として設定し、さらに前記準類似経路を前記類似経路として設定した後に、設定された前記類似経路に含まれる前記準最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記許容タイムから前記最適経路のリンクコストの累計値と前記経路別時間差とを差し引いた値以下である前記非最小コスト経路がなくなるまで探索してもよい。この形態の経路探索装置によれば、許容経路として、最適経路の探索および類似経路の設定を効率的に行なうことができ、第１地点から第２地点までの経路を効率的に設定できる。
【００１０】
（４）上記形態の経路探索装置において、前記特性を特定するデータは、指標値であり；前記経路探索装置は、さらに；前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え；前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり；前記経路別特性特定部は、それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の前記指標値を前記許容経路ごとに特定してもよい。この形態の経路探索装置によれば、経路探索装置の利用者に複数の施設ごとの複雑な情報ではなく、１つの指標値を提供することで、第１地点から第２地点までの経路の内からいずれかの許容経路を簡単に選択させることができ、利用者の利便性が向上する。
【００１１】
（５）上記形態の経路探索装置において、さらに；前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え；前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり；前記経路別特性特定部は、同じノードにおいて、それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の組み合わせが同じであると共に、前記経路加算コストが異なる前記ラベル情報が付与されている場合には、前記経路加算コストが小さい方の前記ラベル情報のみを特定してもよい。この形態の経路探索装置によれば、許容経路に関連付けられた施設の組み合わせを算出する場合に、リンクコストの累計値の高いラベルに基づく組み合わせを算出する必要がなくなり、第１地点から第２地点までの経路を探索する時間を短くできる。
【００１２】
（６）上記形態の経路探索装置において、前記特性を特定するデータは、指標値であり；前記経路探索装置は、さらに；複数の前記施設から少なくとも１つの特定の施設を選択する特定施設選択部と；前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の組み合わせの中に前記特定の施設が含まれる場合には、前記特定の施設に予め設定された指標加算値を前記許容経路の前記指標値の合計に加える指標値加算部と、を備えていてもよい。この形態の経路探索装置によれば、経路探索装置の利用者が利用したい施設があった場合に、当該施設を利用できる許容経路を優先的に利用者に提供できるため、利用者が第１地点から第２地点までの経路を探索する場合の利便性が向上する。
【００１３】
（７）上記形態の経路探索装置において、前記施設情報記憶部は、前記施設の利用に要する時間を表す施設利用時間を記憶し；前記特性を特定するデータは、指標値であり；前記経路探索装置は、さらに；前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え；前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり；前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられていた際に、同一の前記直前ラベルのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用された場合の前記ラベル情報には、前記経路加算コストの代わりに、前記経路加算コストと前記経路加算コストに利用された前記施設の前記施設利用時間とを足した時間を付与してもよい。この形態の経路探索装置によれば、第１地点から第２地点までの経路の移動所要時間に、利用された施設の施設利用時間も加味されているため、実際の移動所要時間を踏まえて第２地点に到着する到着時刻を経路探索装置の利用者に提供でき、利用者の利便性が向上する。
【００１４】
（８）上記形態の経路探索装置において、前記施設情報記憶部は、前記施設に設定された特定のイベントが開始するイベント開始時間と前記特定のイベントが終了するイベント終了時間とを記憶し；前記経路探索装置は、さらに；前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え；前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり；前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられている際に、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間である場合には、同一の前記直前ラベルのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間でない場合には、前記施設が利用されていない場合のみのラベル情報を付与してもよい。この形態の経路探索装置によれば、許容経路に関連付けられた施設があっても、施設が利用できる時間外に当該施設と関連付けられたノードまたはリンクを経路探索装置の利用者が通過する場合には、施設が利用されないラベル情報のみが当該施設通過直後のノードに付与される。よって、実際の移動所要時間を踏まえて第２地点に到着する到着時刻を利用者に提供でき、利用者の利便性が向上する。
【００１５】
（９）上記形態の経路探索装置において、前記許容経路探索部は、前記施設がリンクにおける任意の位置に関連付けられて記憶されている場合に、前記任意の位置を新たなノードである施設ノードとして設定すると共に、前記施設ノードに隣接する２つのノードのそれぞれを第１の隣接ノードと第２の隣接ノードとして設定し、前記施設ノードと前記第１の隣接ノードとを結ぶ第１のリンクと前記施設ノードと前記第２の隣接ノードとを結ぶ第２のリンクとのそれぞれのリンクコストを、前記第１の隣接ノードと前記第２の隣接ノードとを結ぶリンクのリンクコストの長さに対して前記第１のリンクの長さと前記第２のリンクの長さとで按分したリンクコストを設定し、新たに前記許容経路を探索してもよい。この形態の経路探索装置によれば、リンクに関連付けられた施設における特定の位置を新たなノードである施設ノードとして設定される。よって、当該施設に関連付けられたリンクを通過するだけでなく、当該施設のみを経由する目的の施設ノードが追加されるため、経路探索装置の利用者に施設の特性を反映したより多くの経路が提供でき、利用者の利便性が向上する。
【００１６】
（１０）上記形態の経路探索装置において、さらに；ぞれぞれの前記許容経路と、前記許容経路ごとに特定された前記施設および前記施設に設定された前記特性の内の少なくとも一方と、を関連付けて表示させる表示情報を送信する表示情報送信部を備えていてもよい。この形態の経路探索装置によれば、経路探索装置の利用者は、許容経路ごとの施設および施設の特性を一覧の表示として認識でき、利用者の利便性が向上する。
【００１７】
なお、本発明は、種々の態様で実現することが可能であり、例えば、経路探索装置および方法、経路探索システムおよび方法、情報端末装置、情報送信装置および方法、携帯端末装置、情報処理サーバ、経路探索サーバ、これらの装置、方法、システムを実現するためのコンピュータプログラム等の形態で実現することができる。また、これらのコンピュータプログラムは、コンピュータが読取可能な記録媒体（例えば、フレキシブルディスクやＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、光磁気ディスク、メモリカード、ハードディスク等）に記録されていてもよい。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１実施形態における経路探索システム１０の概略構成を示す説明図である。
【図２】経路探索処理の流れを示す説明図である。
【図３】許容経路探索処理の流れを示す説明図である。
【図４】出発地点ＳＡから到着地点ＧＬまでの経路におけるノードとリンクとの一例を示す説明図である。
【図５】各ノードにおける各経路のコスト累計値算出の概略を示す説明図である。
【図６】各ノードにおける各経路のコスト累計値算出の概略を示す説明図である。
【図７】最適経路から類似経路を設定する処理の流れを示す説明図である。
【図８】各最適ノードにおける設定された類似経路の概略を示す説明図である。
【図９】各準最適ノードにおける設定された準類似経路の概略を示す説明図である。
【図１０】ノードおよびリンクに関連付けられた施設の各種情報を示す説明図である。
【図１１】ノードおよびリンクに関連付けられた施設の各種情報を示す説明図である。
【図１２】許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。
【図１３】許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。
【図１４】許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。
【図１５】許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。
【図１６】到着地点ＧＬに付与されたラベルの一覧を示す説明図である。
【図１７】携帯電話機２００に表示される許容経路別の満足度の一例を示す説明図である。
【図１８】許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。
【図１９】許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。
【図２０】携帯電話機２００に表示される許容経路別の満足度の一例を示す説明図である。
【図２１】出発地点ＳＡから到着地点ＧＬまでの経路におけるノードとリンクとの一例を示す説明図である。
【図２２】許容経路別の満足度の一例を示す説明図である。
【図２３】許容経路およびリンクに関連付けられた施設の情報を示す説明図である。
【図２４】許容経路のそれぞれにおける利用される施設を選択する流れの詳細を示す説明図である。
【図２５】許容経路のそれぞれにおいて利用される施設を示す説明図である。
【図２６】許容経路に関連付けられた施設の情報を示す説明図である。
【図２７】許容経路のそれぞれにおいて利用される施設を選択する流れの詳細を示す説明図である。
【図２８】許容経路のそれぞれにおいて利用される施設を示す説明図である。
【図２９】許容経路に関連付けられた施設の情報を示す説明図である。
【図３０】許容経路と許容経路に関連付けられた施設との関係の一例を示す説明図である。
【発明を実施するための形態】
【００１９】
次に、本発明の実施形態を以下の順序で説明する。
Ａ．第１実施形態：
Ａ−１．情報処理システムの構成：
Ａ−２．経路探索処理：
Ａ−３．許容経路探索処理：
Ａ−４．最適経路探索処理：
Ａ−５．類似経路設定処理：
Ａ−６．許容経路別の満足度算出処理：
Ｂ．第２実施形態：
Ｃ．第３実施形態：
Ｄ．第４実施形態：
Ｅ．第５実施形態：
Ｆ．第６実施形態：
Ｇ．変形例：
【００２０】
Ａ．第１実施形態：
Ａ−１．情報処理システムの構成：
図１は、本発明の第１実施形態における経路探索システム１０の概略構成を示す説明図である。本実施形態の経路探索システム１０は、サーバ１００と携帯端末装置としての携帯電話機２００とを備えている。図１には、携帯電話機２００を１台のみ示しているが、経路探索システム１０には、複数の携帯電話機２００および携帯ゲーム機、ＰＮＤ（Personal Navigation Device）、ＰＤＡ（Personal Digital Assistant）といった様々な携帯端末装置が含まれ得る。
【００２１】
携帯電話機２００は、ＧＰＳ受信機２０１と、表示パネル２０２と、音声出力部２０３と、無線通信回路２０５と、操作部２０６と、主制御部２１０と、通話制御部２２０と、を備えている。
【００２２】
ＧＰＳ受信機２０１は、ＧＰＳ（Global Positioning System／全地球測位システム）を構成する人工衛星を用いて測定した携帯電話機２００の現在位置（緯度、経度）を特定する出発地点情報を電波によって受信する。
【００２３】
表示パネル２０２は、液晶ディスプレイとこれを駆動する駆動回路とを備えている。表示パネル２０２としては、液晶ディスプレイに限らず、有機ＥＬディスプレイなど、種々の表示デバイスを採用することが可能である。音声出力部２０３は、音声を出力するためのスピーカや、これを駆動する駆動回路などから構成される。無線通信回路２０５は、基地局ＢＳとの間でデータ通信もしくは音声通信を無線によって行なう。操作部２０６は、テンキー２０６ａやカーソルキー２０６ｂやタッチパネルなどから構成される入力デバイスである。操作部２０６は、利用者による到着地点および到着地点に到着したい到着時刻や利用者が立ち寄りたい施設および施設に到着したい到着時刻の設定入力等を受け付ける。通話制御部２２０は、音声通話のための着信や呼出、音声信号と電気信号の変換などを行なう回路である。
【００２４】
主制御部２１０は、携帯電話機２００の各部を制御する。主制御部２１０は、ＣＰＵ２１１と、ＲＡＭ２１２と、ＲＯＭ２１３と、を備えている。ＣＰＵ２１１は、ＲＯＭ２１３に記憶されたプログラムをＲＡＭ２１２にロードして実行することで、後述する種々の処理を実行するための機能を実現する。例えば、主制御部２１０は、表示パネル２０２を制御することで、地図画像や推奨経路、現在位置などを表示する。また、主制御部２１０は、無線通信回路２０５を制御することで、基地局ＢＳを介して（より詳細には、送受信アンテナ、基地局ＢＳ、交換局を介して）、インターネットＩＮＴ上の情報記憶部１１０および経路探索部１２０と通信する。また、主制御部２１０は、一定時間ごとにＧＰＳ受信機２０１を介してＧＰＳを用いて測定された携帯電話機２００の現在位置情報を受信して、出発地点情報を生成する。
【００２５】
サーバ１００は、インターネットＩＮＴを介して携帯電話機２００との通信を行なう通信部１０２と、情報記憶部１１０と、経路探索部１２０と、を備えている。情報記憶部１１０は、ＣＰＵ、ＲＡＭ、ＲＯＭ、により構成された制御部を有し、情報を記憶する記憶装置１１８を備えている。記憶装置１１８は、例えば、ハードディスク装置により構成されている。記憶装置１１８には、地図情報データベース（ＤＢ）１１４と、ノード別経路情報データベース（ＤＢ）１１５と、ＰＯＩ情報データベース（ＤＢ）１１６と、が構築されている。地図情報ＤＢ１１４は、例えば、リンク情報およびノード情報、画像データとしての地図画像データを記憶している。ノード別経路情報ＤＢ１１５は、後述する経路探索を開始する出発地点から到着地点までの経路を探索する際に、出発地点から任意に選択されたノードである特定のノードまでの探索経路におけるリンクとノードとの組み合わせ（以下、「経路」とも呼ぶ）と当該経路におけるリンクコストの累計値（以下、「コスト累計値」とも呼ぶ）とを、特定のノードと関連付けてノード別経路情報として記憶している。ノード別経路情報では、ノードごとに、出発地点ＳＡからのコスト累計値が最小となる経路が最小コスト経路として記憶され、それ以外の経路が非最小コスト経路として、コスト累計値とノードとを関連付けて記憶される。なお、ノード別経路情報ＤＢ１１５に記憶されたリンクコストの数値は、時間を表している。本実施形態では、リンクコストは絶対的な時間である「分」を表す数値として記憶されているが、他の実施形態では、「分」以外の単位である「時間」や「秒」であってもよいし、相対的な時間を表す数値として記憶されていてもよい。
【００２６】
ＰＯＩ情報ＤＢ１１６は、地図情報ＤＢ１１４に記憶されたリンク情報やノード情報に関連付けられた施設の各種情報について記憶している。また、ＰＯＩ情報ＤＢ１１６は、探索された経路に関連付けられた施設に記憶された各種情報を、経路ごとに特定して記憶する。なお、ＰＯＩ情報ＤＢ１１６に記憶されている施設の各種情報の詳細については後述する。サーバ１００は、請求項における経路探索装置に相当し、情報記憶部１１０は、請求項における経路情報記憶部およびノード別経路記憶部に相当する。また、ＰＯＩ情報ＤＢ１１６は、請求項における施設情報記憶部および経路別特性特定部に相当する。
【００２７】
経路探索部１２０は、ＣＰＵ、ＲＡＭ、ＲＯＭ、により構成された制御部を有し、許容経路探索部１２１を備えている。また、許容経路探索部１２１は、最適経路探索部１２３と、類似経路設定部１２４と、を備えている。経路探索部１２０は、携帯電話機２００に到着地点が設定され、携帯電話機２００から出発地点情報が送信されると、通信部１０２を介して出発地点情報および到着地点情報を受信する。許容経路探索部１２１は、地図情報ＤＢ１１４に記憶してある経路情報と受信した出発地点情報および到着地点情報に基づいて、各リンクのリンクコストを算出して、到着地点までの後述する許容経路を探索する。
【００２８】
経路探索部１２０の最適経路探索部１２３は、地図情報ＤＢ１１４に記憶してある経路情報と受信した出発地点情報および到着地点情報に基づいて、各リンクのリンクコストを算出して、到着地点までの後述する最適経路を探索し、到着地点への到着時刻を計算する。経路探索部１２０の類似経路設定部１２４は、経路情報と最適経路とに基づいて後述する類似経路を設定する。経路探索部１２０は、到着地点までの最適経路と類似経路とを含む経路情報を通信部１０２を介して携帯電話機２００に送信する。
【００２９】
Ａ−２．経路探索処理：
図２は、経路探索処理の流れを示す説明図である。経路探索処理では、携帯電話機２００の利用者の出発地点から到着地点までの経路の内、到着したい時間までに到着地点に到着できる許容経路が探索されて、許容経路のそれぞれについて、到着地点に到着するまでに経由する施設に設定された満足度の合計が算出される。
【００３０】
初めに、サーバ１００の経路探索部１２０は、利用者が携帯する携帯電話機２００から、出発地点と、到着地点と、出発地点から到着地点までの経路を移動するために許容される上限時間と、を取得する（ステップＳ１１）。利用者が携帯電話機２００に到着地点と、到着地点に到着したい時間と、を入力すると、携帯電話機２００は、到着地点情報を生成する。また、ＧＰＳ受信機２０１は、携帯電話機２００の現在位置から出発地点情報を生成する。携帯電話機２００から到着地点情報および出発地点情報が送信されると、経路探索部１２０は、これらの情報を受信し、出発時刻および到着時刻から上限時間を算出する。なお、出発地点および到着地点のそれぞれは、請求項における第１地点および第２地点に相当し、上限時間は、請求項における移動上限時間に相当する。また、経路探索部１２０は、請求項における地点取得部および上限時間設定部に相当する。
【００３１】
次に、経路探索部１２０の許容経路探索部１２１は、許容経路を探索する（ステップＳ１２）。許容経路探索部１２１は、出発地点と到着地点と上限時間とに基づいて、上限時間以内で出発地点から到着地点まで到着できる少なくとも１つの経路である許容経路を探索する。なお、許容経路を探索する処理の詳細については後述する。
【００３２】
次に、経路探索部１２０は、探索された許容経路のそれぞれについて、許容経路ごとの満足度を算出する（ステップＳ１３）。経路探索部１２０は、ＰＯＩ情報ＤＢ１１６に記憶された施設ごとの満足度を用いて、許容経路ごとの満足度を算出する。なお、許容経路ごとの満足度の算出する処理の詳細については後述する。次に、経路探索部１２０が算出した許容経路別の満足度を表す情報である満足度表示情報を携帯電話機２００に送信し、携帯電話機２００は、送信された満足度表示情報を表示パネル２０２に表示させる（ステップＳ１４）。なお、満足度表示情報は、請求項における表示情報に相当し、経路探索部１２０は、請求項における表示情報送信部に相当する。
【００３３】
Ａ−３．許容経路探索処理：
図３は、許容経路探索処理の流れを示す説明図である。許容経路探索処理では、携帯電話機２００の利用者が出発地点から到着地点までを移動するのに必要な移動所要時間が上限時間以下となる少なくとも１つの経路を許容経路として探索する。初めに、経路探索部１２０の最適経路探索部１２３が出発地点から到着地点までの最短時間で移動できる経路である最適経路を探索する（ステップＳ２１）。最適経路の探索処理の詳細については後述する。最適経路が探索されると、経路探索部１２０は、上限時間以内に出発地点から到着できるノードまでの範囲において、各ノードにおける最小コスト経路および非最小コスト経路の探索する（ステップＳ２２）。本実施形態では、上限時間以内に到着できるノードまでの範囲において、最小コスト経路および非最小コスト経路の探索が行なわれるため、経路探索部１２０は、上限時間以内に到着地点へと到着できないノードについては、無駄な経路探索を行なわない。次に、経路探索部１２０の類似経路設定部１２４は、探索された最適経路に基づいて類似経路を設定する（ステップＳ２３）。類似経路とは、最適経路に基づいて設定される最適経路と異なる経路であると共に、上限時間以内に出発地点から到着地点へと到着できる経路である。類似経路の設定処理の詳細については後述する。次に、許容経路探索部１２１は、出発地点、到着地点、上限時間、に基づいて探索された最適経路および設定された類似経路を許容経路として設定する（ステップＳ２４）。
【００３４】
Ａ−４．最適経路探索処理：
本実施形態における最適経路処理では、出発地点から特定のノードまでの探索された経路の内、最適経路探索部１２３が最小コスト経路および非最小コスト経路を探索すると共に、情報記憶部１１０が最小コスト経路および非最小コスト経路を記憶する。最適経路探索部１２３は、特定のノードが到着地点である場合の最小コスト経路を最適経路として設定する。
【００３５】
最適経路探索部１２３は、携帯電話機２００から受信した到着地点情報および出発地点情報に基づいてダイクストラ法により最適経路を探索する。図４は、出発地点ＳＡから到着地点ＧＬまでの経路におけるノードとリンクとの一例を示す説明図である。図４には、ハッチングを施して表示された建物と、リンクおよびノードの各名称と、各リンクにおけるリンクコストと、が示されている。例えば、ノードＮ４１とノードＮ３１とはリンクＬ２で結ばれており、リンクＬ２のリンクコストは１０である。なお、本実施形態では、リンクコストが時間（分）と同じになるように設定されているため、ノードＮ４１からノードＮ３１まで携帯電話機２００の利用者が移動すると、リンクコストである１０分が移動に必要な時間として経過する。最適経路探索部１２３は、地図情報ＤＢ１１４に記憶されている図４に示す経路情報に基づいて、各ノードにおける最小コスト経路および非最小コスト経路と経路のそれぞれのコスト累計値とを算出する。
【００３６】
図５および図６は、各ノードにおける各経路のコスト累計値算出の概略を示す説明図である。初めに、図５（ａ）に示すように、出発地点ＳＡを出発点として各経路におけるコスト累計値を算出する。経路探索処理を始めた初期では、ノードである出発地点ＳＡにおけるコスト累計値は、まだどのリンクも通過していないためゼロである。また、この時点では、出発地点ＳＡに接続しているリンクから出発地点ＳＡへと入る経路のコスト累計値がないため、ゼロが出発地点ＳＡにおける最小コスト経路のコスト累計値（以下、「確定ラベル」とも呼ぶ）である。情報記憶部１１０のノード別経路情報ＤＢ１１５は、最小コスト経路と確定ラベルとを記憶する。なお、図５および図６では、確定ラベルが四角で囲まれて表示される。
【００３７】
次に、出発地点ＳＡからリンクＬ１を通過したノードＮ４１では、リンクＬ１からノードＮ４１へと入る経路のコスト累計値が１０となり、最小コスト経路の候補（以下、「仮ラベル」とも呼ぶ）としてノード別経路情報ＤＢ１１５に記憶される。なお、図５および図６では、仮ラベルは、ノードに入った方向を頂点とした五角形でコスト累計値が囲まれて表示される。同様に、出発地点ＳＡからリンクＬ３を通過したノードＮ３１では、リンクＬ３からノードＮ３１へと入る経路の仮ラベルが２１となり、ノード別経路情報ＤＢ１１５に記憶される。
【００３８】
次に、図５（ｂ）に示すように、ノードＮ４１において、全ての仮ラベルの中で最小のコスト累計値の１０を持つ仮ラベルが確定ラベルとなり、ノードＮ４１を出発点として各経路のコスト累計値が算出される。リンクＬ１を通過してノードＮ４１に入った後に、リンクＬ２を通過してノードＮ３１に入ると、当該経路の仮ラベルは、リンクＬ２のリンクコストが加算されて２０となる。ここで、出発地点ＳＡからノードＮ３１へと入る経路において、リンクＬ３を通過する経路は、リンクＬ１とリンクＬ２とを通過する経路の仮ラベルよりも大きいため、非最小コスト経路としてノード別経路情報ＤＢ１１５に記憶される。非最小コスト経路として記憶されると、ノードＮ３１を出発点とする経路を探索するときには、非最小コスト経路を通過した経路探索が行なわれず、最小コスト経路を基準として経路探索が行なわれる。なお、図５および図６では、非最小コスト経路のコスト累計値（以下、「負けラベル」とも呼ぶ）は、円でコスト累計値を囲まれて表示される。
【００３９】
次に、リンクＬ１を通過してノードＮ４１に入った後に、再びリンクＬ１を通過して出発地点ＳＡに戻ってきた経路の仮ラベルは、再びリンクＬ１のリンクコストが加算されて２０となる。当該経路の仮ラベルは、出発地点ＳＡにおける確定ラベルの０よりも大きいため、負けラベルとしてノード別経路情報ＤＢ１１５に記憶される。
【００４０】
次に、図５（ｃ）に示すように、最小コストの仮ラベルを持つノードＮ３１を出発点として各経路のコスト累計値が算出される。ノードＮ３１では、リンクＬ１とリンクＬ２とを通過した経路（ノードＮ３１における最小コスト経路）を基準として、経路探索が行なわれる。ノードＮ３１からリンクＬ４を通過してノードＮ２１に入ると、当該経路の仮ラベルは、リンクＬ４のリンクコストが加算されて２９となる。同様に、ノードＮ３１からリンクＬ５を通過してノードＮ３２に入ると、当該経路の仮ラベルは、リンクＬ５のリンクコストが加算されて３５となる。
【００４１】
ノードＮ３１から再びリンクＬ２を通過してノードＮ４１に戻ると、当該経路の仮ラベルは、リンクＬ２のリンクコストが加算されて３０となり、ノードＮ４１における確定ラベルの１０よりも大きいため、負けラベルとして記憶される。この場合に、ノードＮ４１において、ノードＮ４１に接続している全てのリンクからノードＮ４１へと入る経路のコスト累計値が記憶されたため、以降、最適経路探索部１２３は、ノードＮ４１へと入る経路を探索しない。同様に、ノードＮ３１からリンクＬ３を通過して出発地点ＳＡに入ると、当該経路の仮ラベルは、リンクＬ５のリンクコストが加算されて４１となり、出発地点ＳＡにおける確定ラベルのゼロよりも大きいため、負けラベルとして記憶される。以降、最適経路探索部１２３は、出発地点ＳＡへと入る経路と探索しない。本実施形態では、最適経路探索部１２３は、同一のリンクから特定のノードへと入る経路の内、コスト累計値が最小であるコスト累計値を記憶し、他の経路のコスト累計値を記憶しないので、サーバ１００の処理負担を軽減することができ、情報記憶部１１０の容量を軽減することができる。
【００４２】
次に、図５（ｄ）に示すように、ノードＮ２１を出発点として各経路のコスト累計値が算出される。ノードＮ２１が出発点として経路探索されると、リンクＬ１とリンクＬ２とリンクＬ４とを通過した経路（ノードＮ２１の最小コスト経路）のコスト累計値が、全ての仮ラベルの中で最小のコスト累計値を持つため、確定ラベルとして記憶される。ノードＮ２１からリンクＬ６を通過してノードＮ１１に入ると、当該経路の仮ラベルは、リンクＬ６のリンクコストが加算されて３８となる。同様に、ノードＮ２１からリンクＬ７を通過してノードＮ２２に入ると、当該経路の仮ラベルは、リンクＬ７のリンクコストが加算されて４４となる。ノードＮ２１から再びリンクＬ４を通過してノードＮ３１に戻ると、当該経路の仮ラベルは、リンクＬ４のリンクコストが加算されて３８となり、ノードＮ３１には既に確定ラベルが存在するため、負けラベルとして記憶される。また、ノードＮ３１からリンクＬ５を通過してノードＮ３２へと入った経路の仮ラベルは、全ての仮ラベルの中で最小のコスト累計地を持つため、次の確定ラベルとして記憶される。
【００４３】
次に、図６（ａ）に示すように、ノードＮ３２を出発点として各経路についてコスト累計値が算出される。ノードＮ３２からリンクＬ８を通過してノードＮ２２に入ると、当該経路の仮ラベルは、リンクＬ８のリンクコストが加算されて４５となり、ノードＮ２１における仮ラベルの４４よりも大きいため、負けラベルとして記憶される。
【００４４】
ノードＮ３２からリンクＬ９を通過してノードＮ３３に入ると、当該経路の仮ラベルは、リンクＬ９のリンクコストが加算されて４４となる。また、ノードＮ３２からリンクＬ１０を通過してノードＮ４３に入ると、当該経路の仮ラベルは、リンクＬ１０のリンクコストが加算されて５５となる。
【００４５】
また、ノードＮ３２から再びリンクＬ５を通過してノードＮ３１に戻ると、当該経路の仮ラベルは、リンクＬ５のリンクコストが加算されて５０となる。ノードＮ３１には既に確定ラベルが存在するため、負けラベルとして記憶される。ここで、ノードＮ３１に接続している全てのリンクからノードＮ３１へと入る経路のコスト累計値が記憶されたため、以降、最適経路探索部１２３は、ノードＮ３１へと入る経路を探索しない。ここで、ノードＮ３１に接続している全てのリンクからノードＮ３１へと入る経路のコスト累計値が記憶されたため、以降、最適経路探索部１２３は、ノードＮ３１へと入る経路を探索しない。ここで、ノードＮ１１の仮ラベルは全ての仮ラベルの中で最小のコスト累計値を持つため、確定ラベルとして記憶される。ノードＮ１１は、この時点で最もコスト累計値の低い仮ラベルを持つため、出発点として各経路についてコスト累計値が算出される。ノードＮ１１からリンクＬ１１を通過してノードＮ１３に入ると、リンクＬ１１のリンクコストが加算されてコスト累計値が６２となる。また、ノードＮ１１からリンクＬ６を通過してノードＮ２１に戻ると、当該経路の仮ラベルは、リンクＬ６のリンクコストが加算されて４７となり、ノードＮ２１には既に確定ラベルが存在するので、負けラベルとして記憶される。ここで、ノードＮ３２からリンクＬ９を通過してノードＮ３３へと入った経路の仮ラベルは、全ての仮ラベルの中で最小のコストを持つため、次の確定ラベルとして記憶される。同様にノードＮ２１からリンクＬ７を通過してノードＮ２２に入った経路の仮ラベルも確定ラベルとして記憶される。
【００４６】
図６（ｂ）には、上述のように、各ノードに接続するリンク全てからコスト累計値が算出されて、ノード別経路情報ＤＢ１１５に記憶された最小コスト経路および非最小コスト経路と、確定ラベルおよび負けラベルと、が示されている。最適経路探索部１２３は、ノード別経路情報ＤＢ１１５に記憶された各経路において、出発地点ＳＡから到着地点ＧＬまでの経路におけるコスト累計値が最小である最適経路を抽出して、決定する。図６（ｂ）には、最適経路として、出発地点ＳＡからリンクＬ１、ノードＮ４１、リンクＬ２、ノードＮ３１、リンクＬ４、ノードＮ２１、リンクＬ６、ノードＮ１１、リンクＬ１１、ノードＮ１３、リンクＬ１６を通過して到着地点ＧＬに入った経路が矢印で示されている。また、図６（ｂ）に示すノードＮ２３では、確定ラベルが５４の経路と、確定ラベルと同じコスト累計値が５４の負けラベルとが表示されている。経路が異なっていても、コスト累計値が同じである場合には、最適経路探索部１２３は、任意で片一方を確定ラベルとして設定する。本実施形態では、ノードＮ２３において先に探索されたリンクＬ１２からノードＮ２３へと入る経路のコスト累計値を確定ラベルとして設定している。
【００４７】
最適経路が決定されると、経路探索部１２０は、引き続き、出発地点ＳＡから到着地点ＧＬまでの経路において、最適経路のコスト累計値と設定された許容コストとを加えたコスト未満であるコスト累計値の仮ラベルを算出する。本実施形態では、最適経路のコスト累計値と許容コストとを加えたコスト以上の仮ラベルを算出しないため、出発地点ＳＡから到着地点ＧＬまで無限に経路を探索する必要がなく、効率的に経路探索を行なうことができる。
【００４８】
次に、経路探索部１２０の類似経路設定部１２４は、得られた最適経路と、各ノードにおける最小コスト経路および非最小コスト経路と、に基づいて出発地点ＳＡから到着地点ＧＬまでの類似経路を設定する。
【００４９】
Ａ−５．類似経路設定処理：
次に、類似経路設定部１２４は、探索された最適経路に基づいて類似経路を設定する（図３のステップＳ２３）。図７は、最適経路から類似経路を設定する処理の流れを示す説明図である。類似経路設定処理では、初めに、経路探索部１２０は、上限時間から最適経路のコスト累計値を差し引いた許容タイムを設定する（ステップＳ４１）。本実施形態では、上限時間は、予め７１分と設定されている。携帯電話機２００の利用者における出発地点ＳＡから到着地点ＧＬまでの最適経路のコスト累計値が６７であるため、許容タイムは４分間である。次に、類似経路設定部１２４は、最適経路に含まれるノードである各最適ノードにおいて、順番に確定ラベルと負けラベルとの差（以下、「経路別コスト差」とも呼ぶ）が許容タイム以下である非最小コスト経路があるか否かを判定する（ステップＳ４２）。経路別コスト差が許容タイム以下である非最小コスト経路を有する最適ノードがないと判定された場合（ステップＳ４２：ＮＯ）、類似経路設定部１２４は、類似経路がないと設定して、類似経路設定処理を終了する。ある最適ノードにおいて、経路別コスト差が許容タイム以下である非最小コスト経路があると判定された場合（ステップＳ４２：ＹＥＳ）、類似経路設定部１２４は、当該最適ノードにおける類似経路を設定する。
【００５０】
図８は、各最適ノードにおける設定された類似経路の概略を示す説明図である。図８（ａ）には、探索された最適経路および設定された類似経路と、各最適ノードにおける確定ラベルおよび負けラベルとが示されている。図８（ｂ）には、各最適ノードにおける確定ラベルと負けラベルと経路別コスト差とが示されている。図８（ｃ）には、図８（ｂ）と対応させて、各最適ノードと類似経路を選択した場合の経路別コスト差との概略が示されている。
【００５１】
類似経路設定部１２４は、経路別コスト差が５以下である非最小コスト経路を探索すると、図８（ａ）および（ｂ）に示すように、最適ノードの内、ノードＮ１３とノードＮ３１とにおいて、経路別コスト差が５以下である非最小コスト経路を抽出する。ノードＮ１３において経路別コスト差が２である非最小コスト経路は、出発地点ＳＡからノードＮ２１までは最適経路と同じ経路を通過し、ノードＮ２１からリンクＬ７、ノードＮ２２、リンクＬ１２、ノードＮ２３、リンクＬ１３を通過してノードＮ１３へと入り、ノードＮ１３から到着地点ＧＬまでは最適経路と同じ経路を通過する経路（以下、「第１類似経路」とも呼ぶ）である。
【００５２】
また、ノードＮ３１において経路別コスト差が１である非最小コスト経路は、出発地点ＳＡからリンクＬ３を通過してノードＮ３１へと入り、ノードＮ３１からは最適経路と同じ経路を通過する経路（以下、「第２類似経路」とも呼ぶ）である。類似経路設定部１２４は、第１類似経路および第２類似経路を類似経路として設定する（図７のステップＳ４３）。
【００５３】
次に、類似経路設定部１２４は、最適経路には含まれずに類似経路にのみ含まれる各準最適ノードにおいて、経路別コスト差が最適経路と類似経路とにおけるコスト累計値の差を許容タイムから差し引いた値（以下、「差分許容タイム」とも呼ぶ）以下である非最小コスト経路があるか否かを判定する（ステップＳ４４）。準最適ノードにおいて、経路別コスト差が差分許容タイム以下である非最小コスト経路がないと判定された場合（ステップＳ４４：ＮＯ）、類似経路設定部１２４は、類似経路設定処理を終了する。ある準最適ノードにおいて、経路別コスト差が差分許容タイム以下である非最小コスト経路があると判定された場合（ステップＳ４２：ＹＥＳ）、類似経路設定部１２４は、当該準最適ノードにおいて準類似経路を設定する。
【００５４】
図９は、各準最適ノードにおける設定された準類似経路の概略を示す説明図である。図９（ａ）には、探索された最適経路と、設定された類似経路および準類似経路と、各準最適ノードにおける確定ラベルおよび負けラベルとが示されている。図９（ｂ）には図８（ｂ）と同様に、各準最適ノードにおける確定ラベルと負けラベルと経路別コスト差と、が示されている。また、図９（ｂ）には、準類似経路に含まれる準最適ノードにおける経路別コスト差と、準類似経路を含む類似経路と最適経路とのコスト累計値との差とを加えた値（以下、「経路加算コスト」とも呼ぶ）が示されている。図９（ｃ）には、図９（ｂ）と対応させて、各準最適ノードと準類似経路を選択した場合の経路別コスト差および経路加算コストとの概略が示されている。
【００５５】
図９（ａ）および（ｂ）に示すように、類似経路設定部１２４は、第１類似経路における準最適ノードの内、ノードＮ２３とノードＮ２２とにおいて、経路別コスト差が差分許容タイム以下である非最小コスト経路を抽出する。ノードＮ２３において経路別コスト差がゼロである非最小コスト経路は、出発地点ＳＡからノードＮ３１までは第１類似経路と同じ経路を通過し、ノードＮ３１からリンクＬ５、ノードＮ３２、リンクＬ９、ノードＮ３３、リンクＬ１４を通過してノードＮ２３へと入り、ノードＮ２３からは第１類似経路と同じ経路を通過する経路（以下、「第１準類似経路」とも呼ぶ）である。また、図９（ｂ）に示すように、第１準類似経路は、最適経路との経路別コスト差が２である第１類似経路に対し、ノードＮ２３における経路別コスト差が０であるため、最適経路よりもコスト累計値が２大きい経路である。
【００５６】
ノードＮ２２において経路別コスト差が１である最小コスト経路は、出発地点ＳＡからノードＮ３１までは第１類似経路と同じ経路を通過し、ノードＮ３１からリンクＬ５、ノードＮ３２、リンクＬ８、を通過してノードＮ２２へと入り、ノードＮ２２からは第１類似経路と同じ経路を通過する経路（以下、「第２準類似経路」とも呼ぶ）である。また、図９（ｂ）に示すように、第２準類似経路は、最適経路との経路別コスト差が２である第１類似経路に対し、ノードＮ２２における経路別コスト差が１であるため、最適経路よりもコスト累計値が３大きい経路である。類似経路設定部１２４は、第１準類似経路および第２準類似経路を準類似経路として設定する（図７のステップＳ４５）。
【００５７】
次に、類似経路設定部１２４は、準類似経路を類似経路として設定し（ステップＳ４６）、新たに設定された類似経路における準最適ノードにおいて、上述したステップＳ４４の処理を準類似経路がないと判定されるまで繰り返す。経路別コスト差が差分許容タイム以下である非最小コスト経路を有する準最適ノードがないと判定されると（ステップＳ４４：ＮＯ）、類似経路設定部１２４は、準類似経路がないと設定して、類似経路設定処理を終了する。許容経路探索部１２１は、最適経路および類似経路を許容経路として設定する（図３のステップＳ２４）。
【００５８】
Ａ−６．許容経路別の満足度算出処理：
許容経路別の満足度算出処理では、探索された許容経路のそれぞれについて、許容経路に含まれるノードおよびリンクに関連付けられた施設を特定すると共に、関連付けられた施設を経由した場合に得られる満足度の合計を算出する。
【００５９】
図１０および図１１は、ノードおよびリンクに関連付けられた施設の各種情報を示す説明図である。図１０に示すように、ＰＯＩ情報ＤＢ１１６は、ノードおよびリンクに関連付けられた施設の名称と、施設が関連付けられているノードまたはリンクと、施設に設定されている満足度と、が示されている。なお、満足度は、請求項における指標値に相当する。図１１には、探索された許容経路と施設との関係が示されている。例えば、図１０および図１１に示すように、施設ＡＡは、リンクＬ７とリンクＬ１２に関連付けられており、経由されると満足度として２０が許容経路に加算される施設である。
【００６０】
図１２から図１５までは、許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。図１２から図１５までに示す処理では、許容経路に含まれるノードの内、隣接するノードに移動した場合に経路加算コストが異なるノードのそれぞれについて、満足度を含むラベルが付与されて、付与されたラベルを用いて許容経路のそれぞれの満足度が算出される流れが示されている。各ノードに付与されるラベルには、満足度と、当該ラベルまでの経路のコスト累計値が最適経路のコスト累計値よりもどれだけ大きいか示す経路加算コストと、当該ラベルを付与する１つ前のラベル（以下、「直前ラベル」とも呼ぶ）と、が含まれる。なお、他の実施形態では、許容経路に含まれる全てのノードにおいて、ラベルが付与されてもよい。
【００６１】
許容経路別の満足度算出処理では、図１２（ａ）に示すように、初めに、経路探索部１２０は、許容経路に含まれる最初のノードとして、出発地点ＳＡを選択する。次に、経路探索部１２０は、出発地点ＳＡにおけるラベルＡ０を付与する。ラベルＡ０は、出発地点ＳＡが初めのノードであるため、ラベルＡ０の直前ラベルが存在せず、また、いずれの施設も経由していない。そのため、経路探索部１２０は、出発地点ＳＡにおいて、満足度を０、経路加算コストを０、直前ラベルを「−」とするラベルＡ０を付与する。ＰＯＩ情報ＤＢ１１６は、付与されたラベルをノードごとに記憶する。
【００６２】
次に、経路探索部１２０は、出発地点ＳＡにおけるラベルＡ０を確定ラベルとして記憶し、直前ラベルをラベルＡ０として、出発地点ＳＡに隣接するノードにおけるラベルを付与する。ただし、ノードＮ４１は、出発地点ＳＡに隣接するノードであるものの、リンクＬ１からノードＮ４１へと入って、リンクＬ２を通過する許容経路では、ノードＮ４１における経路の分岐がなく、経路加算コストが変化しない。そのため、経路探索部１２０は、ノードＮ４１では、ラベルを付与しない。なお、図１２から図１５まででは、確定ラベルを四角で囲んで表示している。
【００６３】
図１２（ｂ）に示すように、経路探索部１２０は、ノードＮ３１において、リンクＬ１、ノードＮ４１、リンクＬ２を通過したラベルＡ１とリンクＬ３を通過したラベルＡ２を付与する。ラベルＡ１では、いずれの施設も経由していないため、満足度が０であり、リンクＬ１とノードＮ４１とリンクＬ２とは最適経路に含まれる経路であるため、経路加算コストが０であり、直前ラベルがラベルＡ０である。また、ラベルＡ２では、いずれの施設も経由していないため、満足度が０であり、最適経路に対して経路加算コストが１であり、直前ラベルがラベルＡ０である。なお、この時点では、ノードＮ３１を直前ノードとするラベルが付与されていないため、ラベルＡ１およびラベルＡ２は、ノードＮ３１における仮ラベルとして付与される。仮ラベルは、図１２から図１５まででは、リンクからノードへと入った向きを頂点とする５角形で囲まれて表示される。
【００６４】
次に、図１３（ａ）に示すように、経路探索部１２０は、ノードＮ３１におけるラベルＡ１を確定ラベルとして記憶し、ラベルＡ１を直前ラベルとして、ノードＮ２１におけるラベルＡ３と、ノードＮ３２におけるラベルＡ４と、を付与する。ラベルＡ３では、いずれの施設も経由していないため、満足度が０であり、リンクＬ４が最適経路に含まれる経路であるため、経路加算コストがラベルＡ１と同じく０であり、直前ラベルがラベルＡ１である。また、ラベルＡ４では、リンクＬ５に関連付けられた施設ＤＤを経由するため、満足度が１０であり、最適経路に対して経路加算コストが２であり、直前ラベルがラベルＡ１である。
【００６５】
次に、図１３（ｂ）に示すように、経路探索部１２０は、ノードＮ３１におけるラベルＡ２を確定ラベルとして記憶し、ラベルＡ２を直前ラベルとして、ノードＮ２１におけるラベルＡ５と、ノードＮ３２におけるラベルＡ６と、を付与する。ラベルＡ５では、いずれの施設も経由していないため、満足度が０であり、リンクＬ４が最適経路に含まれる経路であるため、経路加算コストがラベルＡ２と同じく１であり、直前ラベルがラベルＡ２である。また、ラベルＡ６では、リンクＬ５に関連付けられた施設ＤＤを経由するため、満足度が１０であり、リンクＬ５が最適経路に対して経路加算コストが２である経路のため、経路加算コストがラベルＡ２の経路加算コストの１に加えた３であり、直前ラベルがラベルＡ２である。
【００６６】
図１４（ａ）には、図１３（ｂ）の状態からラベルＡ７からラベルＡ１２までの仮ラベルが付与された状態が示されている。ラベルＡ７およびラベルＡ８は、ラベルＡ３を直前ラベルとする仮ラベルであり、ラベルＡ９およびラベルＡ１０は、ラベルＡ４を直前ラベルとする仮ラベルであり、ラベルＡ１１およびラベルＡ１２は、ラベルＡ５を直前ラベルとする仮ラベルである。
【００６７】
図１４（ｂ）には、図１４（ａ）に示すラベルが付与された状態から、ノードＮ３２におけるラベルＡ６を直前ラベルとしてノードＮ２３におけるラベルＡ１３が付与された状態が示されている。なお、図１４（ｂ）に示すように、経路探索部１２０は、ノードＮ２３におけるラベルＡ１３を付与する前に、ラベルＡ６を直前ノードとしてリンクＬ８を通過してノードＮ２２へと入る経路のラベルをラベルＡ１３として付与する。しかし、ノードＮ２２におけるラベルＡ１３では、経路加算コストが５となり、許容タイムの４分を超えてしまう。そのため、直前ラベルがラベルＡ６であり、リンクＬ８およびノードＮ２２を通過する経路は、許容経路ではないため、このラベルＡ１３は付与されない。その結果、ノードＮ２２におけるラベルＡ１３は付与されずに、ノードＮ２３におけるラベルＡ１３が付与されて、ＰＯＩ情報ＤＢ１１６に記憶される。以上のように、経路探索部１２０は、許容経路に含まれるノードにラベルを付与する。図１５には、許容経路に含まれるノードのそれぞれに付与された確定ラベルが示されている。ＰＯＩ情報ＤＢ１１６は、全ての確定ラベルを許容経路別およびノード別に記憶する。
【００６８】
図１６は、到着地点ＧＬに付与されたラベルの一覧を示す説明図である。図１６に示すように、経路探索部１２０は、許容経路ごとに関連付けられた施設の満足度および許容経路に含まれるノードにおける各ラベルが示されている。例えば、ラベルＡ２３の許容経路の満足度は１０であり、ラベルＡ２３のラベルの推移は、ラベルＡ０、ラベルＡ１、ラベルＡ４、ラベルＡ１０、ラベルＡ１７、ラベルＡ２３である。ラベルＡ２３の経路は、携帯電話機２００の表示パネル２０２において、実線で表示される。本実施形態では、経路探索部１２０は、満足度が０となるラベルＡ１４およびラベルＡ１８を構成する許容経路を携帯電話機２００の利用者に出発地点ＳＡから到着地点ＧＬまでの経路として提供しない。なお、他の実施形態では、ラベルＡ１４およびラベルＡ１８を構成する許容経路を携帯電話機２００の利用者に提供してもよい。
【００６９】
次に、経路探索部１２０は、許容経路別の満足度を携帯電話機２００に表示させる（図２のステップＳ１４）。経路探索部１２０は、探索した許容経路および許容経路における満足度を表す満足度表示情報を携帯電話機２００に送信する。図１７は、携帯電話機２００に表示される許容経路別の満足度の一例を示す説明図である。図１７には、図１６に示す満足度が１０以上の許容経路が示されている。本実施形態では、図１７に示すように、許容経路の線種および太さが異なるように携帯電話機２００に表示され、許容経路の線の太さが太いほど満足度が高いことが示されている。
【００７０】
以上説明したように、本実施形態におけるサーバ１００では、ＰＯＩ情報ＤＢ１１６は、ノードおよびリンクに関連付けられた施設と、施設に設定されている満足度と、を特定する情報を記憶している。経路探索部１２０は、取得した到着地点に到着したい到着時刻に基づいて上限時間を設定し、許容経路探索部１２１は、出発地点ＳＡから到着地点ＧＬまでに移動する移動所要時間が上限時間以下である少なくとも１つの経路を許容経路として探索する。経路探索部１２０は、許容経路のそれぞれに関連付けられた施設の満足度を、許容経路ごとに特定する。そのため、本実施形態におけるサーバ１００では、利用者が到着地点ＧＬの到着したい到着時刻までに到着できる許容経路の範囲において、利用者が経由できる施設を経由した出発地点ＳＡから到着地点ＧＬまでの経路を利用者に提供できる。また、出発地点ＳＡから到着地点ＧＬまでの経路探索において、移動所要時間が上限時間以下である許容経路のみを探索するため、上限時間以内に到着地点ＧＬに到着できない無駄な経路が探索されない。また、本実施形態では、許容経路に関連付けられた施設の範囲であれば、全ての施設のそれぞれについて経由する許容経路を利用者に提供できる。
【００７１】
また、本実施形態におけるサーバ１００では、許容経路探索部１２１は、最適経路探索部１２３と類似経路設定部１２４とを有している。最適経路探索部１２３は、出発地点ＳＡから到着地点ＧＬまでの経路の内、リンクコストのコスト累計値が最小となる最適経路を設定する。ノード別経路情報ＤＢ１１５は、各ノードにおける確定ラベルと負けラベルとを記憶する。類似経路設定部１２４は、設定された最適経路と、上限時間と最適経路のリンクコストのコスト累計地との差である許容タイムと、に基づいて類似経路を設定する。許容経路は、最適経路および類似経路である。また、本実施形態のサーバ１００では、類似経路設定部１２４は、類似経路に基づいて準類似経路を設定し、設定された準類似経路を新たな類似経路として設定した後に、準類似経路が設定されなくなるまで、準類似経路の設定を繰り返す。そのため、本実施形態のサーバ１００では、許容経路として、最適経路の探索および類似経路の設定を効率的に行なうことができ、第１地点から第２地点までの経路を効率的に設定できる。
【００７２】
また、本実施形態におけるサーバ１００では、ＰＯＩ情報ＤＢ１１６は、施設に設定されている満足度を記憶しており、経路探索部１２０は、許容経路に含まれるノードにラベルを付与する。ラベルには、出発地点ＳＡから当該ラベルが付与されているノードまでの満足度の合計と、当該ラベルまでの経路のコスト累計値が最適経路のコスト累計値よりもどれだけ大きいか示す経路加算コストと、直前ラベルと、が含まれている。経路探索部１２０は、それぞれの許容経路に関連付けられた施設の満足度を許容経路ごとに特定する。そのため、本実施形態におけるサーバ１００では、利用者に複数の施設ごとの複雑な情報ではなく、満足度といった１つの指標値を提供することで、出発地点ＳＡから到着地点ＧＬまでの経路の内からいずれかの許容経路を簡単に選択させることができ、利用者の利便性が向上する。
【００７３】
また、本実施形態におけるサーバ１００では、経路探索部１２０は、許容経路と、許容経路ごとに関連付けられた施設の満足度と、を関連付けて表示する情報である満足度表示情報を携帯電話機２００に送信する。そのため、本実施形態におけるサーバ１００では、携帯電話機２００の利用者は、許容経路ごとの満足度を一覧の表示として認識でき、利用者の利便性が向上する。
【００７４】
Ｂ．第２実施形態：
第２実施形態では、出発地点ＳＡから到着地点ＧＬまでのノードおよびリンクの設定と、探索された許容経路に含まれるノードに対して確定ラベルを付与する方法と、ラベルを付与する順序が上記実施形態とは異なる。図１８および図１９は、許容経路のそれぞれにおける満足度を算出する流れの詳細を示す説明図である。図１８および図１９に示す満足度の合計の算出では、同じノードにおける確定ラベルの内、満足度が同じで、経路加算コストが大きいラベルは、直前ラベルとして隣接するノードに新たなラベルを付与しない。経路加算コストを比較する対象は、施設に設定されている満足度の合計が同じラベルであると共に、施設への立寄順序も同じラベルとする。
【００７５】
図１８（ａ）に示すように、第２実施形態では、第１実施形態とリンクおよびノードの設定が異なるため、例えば、出発地点ＳＡからノードＮ５１を通過して、再び出発地点ＳＡに入る経路も許容経路として探索されている。許容経路ごとの満足度の合計を算出する処理では、第１実施形態と同じように、図１８（ａ）に示すように、ラベルＡ０が付与される。ここでラベルを付与する順序は第１実施形態とは異なり、経路加算コストが小さいラベルから隣接するノードにラベルを付与していく。図１８（ｂ）には、ラベルＡ０を直前ラベルとして、ノードＮ７１におけるラベルＡ１およびノードＮ５１におけるラベルＡ２が付与された状態が示されている。図１８（ｃ）には、直前ラベルをラベルＡ２として、ノードＮ５０におけるラベルＡ３、ノードＮ６１におけるラベルＡ４、出発地点ＳＡにおけるラベルＡ５、が仮ラベルとして付与された状態が示されている。図１８（ｄ）において、出発地点ＳＡに付与されたラベルＡ５は、同じ出発地点ＳＡに付与された確定ラベルであるラベルＡ０と満足度が同じで、経路加算コストが２であり、ラベルＡ０の経路加算コスト０よりも大きいため、ラベルとしてＰＯＩ情報ＤＢ１１６に記憶されない。
【００７６】
ラベルＡ５が直前ノードとしてラベルが付与されないので、図１９（ａ）に示すノードＮ５１におけるラベルＡ７およびノードＮ７１におけるラベルＡ８は、新たなラベルとして付与されない。また、図１９（ｂ）に示すノードＮ７１におけるラベルＡ１３は、ノードＮ７１における確定ラベルのラベルＡ１と同じ満足度の１０であり、経路加算コストがラベルＡ１の経路加算コストよりも２大きい４であるので、新たなラベルとして付与されない。なお、図１９（ａ）および図１９（ｂ）に示すように、簡略化のため、いくつかの確定ラベルでは、ラベルの名称のみが示されている。
【００７７】
図２０は、携帯電話機２００に表示される許容経路別の満足度の一例を示す説明図である。図２０（ａ）には、許容経路である経路Ｒ１から経路Ｒ４までの各経路が異なる線種で表示されている。図２０（ｂ）には、図２０（ａ）に示す許容経路別の満足度、経由する経由施設、出発地点ＳＡから到着地点ＧＬまで移動するのに必要な移動所要時間、が示されている。例えば、経路Ｒ３は、満足度が４０であり、経由する施設が施設Ａ、施設Ｂ、施設Ｅ、であり、出発地点ＳＡを出発してから到着地点ＧＬに到着するのに必要な移動所要時間が４０分である。
【００７８】
以上説明したように、第２実施形態におけるサーバ１００では、ラベルには、出発地点ＳＡから当該ラベルが付与されているノードまでの経路に関連付けられた施設の組み合わせが含まれている。経路探索部１２０は、同じノードにおける確定ラベルの内、満足度が同じで、経路加算コストが小さい方のラベルを確定ラベルとして特定する。そのため、本実施形態におけるサーバ１００では、許容経路に関連付けられた施設の満足度または施設の組み合わせを算出する場合に、コスト累計値の高い無駄なラベルに基づく満足度や組み合わせを算出する必要がなくなり、出発地点ＳＡから到着地点ＧＬまでの経路を探索する時間を短くできる。
【００７９】
Ｃ．第３実施形態：
第３実施形態では、経路探索部１２０が施設とリンクとが関連付けられているリンクにおける特定の位置を新たなノードである施設ノードとして設定すると共に、施設ノードを他のノードと同様に扱って許容経路を探索する点が上記実施形態と異なる。図２１は、出発地点ＳＡから到着地点ＧＬまでの経路におけるノードとリンクとの一例を示す説明図である。図２１（ａ）および（ｂ）には、ノードおよびリンクと、経路探索部１２０が新たに設定した施設ノードと、施設ノードに関連付けられた施設と、が示されている。例えば、施設ノードＳＰ３は、施設Ｃおよび施設Ｄに関連付けられた位置である。ノードＮ５１から施設ノードＳＰ３までを結ぶリンクがリンクＬ６１ａであり、施設ノードＳＰ３からノードＮ６１までを結ぶリンクがリンクＬ６１ｂである。なお、許容経路は、図２１に示された矢印の向きに進む経路である。なお、リンクＬ６１ａおよびリンクＬ６１ｂのそれぞれのリンクコストは、経路探索部１２０によって、施設ノードＳＰ３で分割される前のリンクＬ６１ａとリンクＬ６１ｂとで構成されるリンクのリンクコストを、リンクＬ６１ａおよびリンクＬ６１ｂのそれぞれのリンクの長さの比に基づいて設定される。第３実施形態では、リンクＬ６１ａとリンクＬ６１ｂとのリンクの長さの比が３：２であるため、リンクＬ６１ａのリンクコストは分割される前のリンクコストの５分の３であり、リンクＬ６１ｂのリンクコストは分割される前のリンクコストの５分の２である。なお、ノードＮ５１およびノードＮ６１のそれぞれは、請求項における第１の隣接ノードおよび第２の隣接ノードに相当する。他の実施形態では、必ずしも施設ノードで分割されたリンクのリンクコストは、上述のように、分割後のリンクの長さに按分される必要はなく、単に２分割であれば、分割する前のリンクコストの半分のリンクコストに設定されていてもよい。
【００８０】
図２１（ｂ）には、施設ノードを含む許容経路に含まれるノードへのラベルを付与する方法について示されている。上記実施形態と同様に、経路探索部１２０は、出発地点ＳＡにおけるラベルＡ０を直前ラベルとして、施設ノードＳＰ４におけるラベルＡ１と、ノードＮ５１におけるラベルＡ２と、のラベルを付与する。次に、経路探索部１２０は、施設ノードＳＰ４におけるラベルＡ１を直前ノードとして、ノードＮ７１におけるラベルを付与する。
【００８１】
施設ノードＳＰ１から施設ノードＳＰ４までが他のノードと同様に扱われて、許容経路に含まれるノードにおける確定ラベルがＰＯＩ情報ＤＢ１１６に記憶される。図２２は、許容経路別の満足度の一例を示す説明図である。図２２（ａ）には、満足度が１０以上の許容経路である経路Ｒ１１から経路Ｒ１６までの各経路が線種の異なる矢印で示されている。図２２（ｂ）には、経路Ｒ１１から経路Ｒ１６まで経路のそれぞれにおいて、満足度の合計と、経由する施設である経由施設と、当該経路を通過した場合の出発地点ＳＡから到着地点ＧＬまでに到着するのに必要な移動所要時間と、が示されている。例えば、経路Ｒ１３は、一点鎖線の矢印で示される経路であり、満足度が４０で、施設Ａと施設Ｂと施設Ｅとを経由し、出発地点ＳＡから到着地点ＧＬまで到着するのに４０分の移動所要時間を要する経路である。なお、図２２（ｂ）において、点線で囲まれて示された経路Ｒ１２および経路Ｒ１６は、施設ノードを新たに設定することで探索された許容経路であることを示している。なお、携帯電話機２００には、経路Ｒ１２および経路Ｒ１６のそれぞれを囲んでいる点線は表示されない。
【００８２】
以上説明したように、第３実施形態におけるサーバ１００では、経路探索部１２０は、施設とリンクとが関連付けられているリンクにおける特定の位置を新たなノードである施設ノードとして設定する。また、経路探索部１２０は、リンクＬ６１ａおよびリンクＬ６１ｂのそれぞれのリンクコストを、施設ノードＳＰ３で分割される前のリンクＬ６１ａとリンクＬ６１ｂとで構成されるリンクのリンクコストをリンクＬ６１ａおよびリンクＬ６１ｂのそれぞれのリンクの長さの比で按分して設定する。そのため、第３実施形態におけるサーバ１００では、リンクに関連付けられた施設における特定の位置を新たなノードとして設定される。よって、当該施設に関連付けられたリンクを通過するだけでなく、当該施設のみを経由する目的のノードが追加されるため、利用者に施設の満足度を反映したより多くの経路が提供でき、利用者の利便性が向上する。
【００８３】
Ｄ．第４実施形態：
第４実施形態では、上記実施形態と異なり、経路探索部１２０は、施設を経由した場合に予め設定された施設を利用するのに必要な時間である施設利用時間を経路加算コストに加算して、出発地点ＳＡから到着地点ＧＬまでに要する移動所要時間を算出する。図２３は、許容経路およびリンクに関連付けられた施設の情報を示す説明図である。図２３（ａ）には、第４実施形態における許容経路が線種の異なる矢印で示されており、リンクに関連付けられた施設Ｆから施設Ｊまでが示されている。ＰＯＩ情報ＤＢ１１６は、特定の施設を利用した場合に必要とされる施設利用時間を記憶している。図２３（ａ）において、最適経路は、出発地点ＳＡを出発して、リンクＬ９１、ノードＮ８１、リンクＬ９２、ノードＮ８２、リンクＬ９５、ノードＮ８７、を通過して、到着地点ＧＬに到着する経路である。第４実施形態では、最適経路のコスト累計値が１０であり、出発地点ＳＡから到着地点ＧＬまで到着するまでの上限時間は７０分に設定されているため、許容タイムは６０分である。図２３（ｂ）には、各施設の分類と、施設が提供するサービスの内容と、施設を利用した場合に要する施設利用時間と、が一覧で示されている。例えば、図２３（ｂ）に示すように、施設Ｆは、衣服を販売する服飾に分類される店舗であり、販売する衣服が婦人服に限られ、利用されると３０分が施設利用時間として必要な施設である。
【００８４】
図２４は、許容経路のそれぞれにおける利用される施設を選択する流れの詳細を示す説明図である。図２４に示すラベルを付与する処理では、上記実施形態と異なり、経路探索部１２０は、満足度の代わりに利用された施設と、経路加算コストと、直前ラベルと、をラベルとして付与する。図２４（ａ）には、出発地点ＳＡに付与された確定ラベルであるラベルＡ０を直前ノードとして、ノードＮ８３におけるラベルＡ１およびラベルＡ２と、ノードＮ８１におけるラベルＡ３と、が付与された状態が示されている。出発地点ＳＡとノードＮ８３とを結ぶリンクＬ９３は、施設Ｉに関連付けられている。そのため、ノードＮ８３において、経路探索部１２０は、施設Ｉが利用されない場合のラベルＡ１と、施設Ｉが利用された場合のラベルＡ２と、の２つのラベルを付与する。ラベルＡ１は、いずれの施設も利用されておらず、経路加算コストが２であり、直前ラベルがラベルＡ０であることを示している。ラベルＡ２は、施設Ｉが利用され、経路加算コストがリンクＬ９３を利用者が通過した場合の経路加算コストの２と施設Ｉの施設利用時間である２５とを足した２７であり、直前ラベルがラベルＡ０であることを示している。ラベルＡ３は、施設が利用されておらず、経路加算コストが０であり、直前ラベルがラベルＡ０であることを示している。
【００８５】
図２４（ｂ）には、ノードＮ８３に付与されたラベルＡ１を直前ノードとして、ノードＮ８６におけるラベルＡ４と、ノードＮ８４におけるラベルＡ５およびラベルＡ６と、が付与された状態が示されている。ラベルＡ４は、施設が利用されておらず、経路加算コストが２であり、直前ラベルがラベルＡ１であることを示している。リンクＬ９６は、施設Ｈに関連付けられているため、ノードＮ８４において、経路探索部１２０は、施設Ｈが利用されない場合のラベルＡ５と、施設Ｈが利用された場合のラベルＡ６と、の２つのラベルを付与する。ラベルＡ５は、いずれの施設も利用されておらず、経路加算コストの新たに２が加えられた４であり、直前ラベルがラベルＡ１であることを示している。ラベルＡ６は、施設Ｈが利用され、経路加算コストがリンクＬ９６を利用者が通過した場合の経路加算コストの２と施設Ｉの施設利用時間である４５とを足した４９であり、直前ラベルがラベルＡ１であることを示している。
【００８６】
図２４（ｃ）には、ノードＮ８３に付与されたラベルＡ２を直前ノードとして、ノードＮ８６におけるラベルＡ７と、ノードＮ８４におけるラベルＡ８と、が付与された状態が示されている。ラベルＡ７は、施設Ｉが利用されており、経路加算コストが２７であり、直前ラベルがラベルＡ２であることを示している。ノードＮ８４において、経路探索部１２０は、施設Ｈが利用されない場合のラベルＡ８を付与する。ラベルＡ８は、施設Ｉが利用されており、経路加算コストの新たに２が加えられた２９であり、直前ラベルがラベルＡ２であることを示している。なお、ノードＮ８４において、経路探索部１２０は、施設Ｈが利用されたラベルＡ９を付与しようとするものの、この場合には、経路加算コストが７４となり、上限時間を超えてしまうため、ラベルＡ９を付与できない。
【００８７】
図２４（ｄ）には、ノードＮ８１に付与されたラベルＡ３を直前ノードとして、ノードＮ８７におけるラベルＡ９と、ノードＮ８４におけるラベルＡ１０からラベルＡ１３までと、が付与された状態が示されている。ノードＮ８４では、施設Ｇおよび施設Ｊが利用された場合の組み合わせについてラベルＡ１０からラベルＡ１３までが付与されている。以上のように、図２４（ａ）から（ｄ）までに示された方法によって許容経路に含まれるノードにラベルが付与される。
【００８８】
図２５は、許容経路のそれぞれにおいて利用される施設を示す説明図である。図２５（ａ）には、許容経路が経路加算コストに応じて線種の異なる矢印で示されている。図２５（ｂ）には、経路Ｒ２１から経路Ｒ２４までの許容経路のそれぞれにおいて、出発地点ＳＡから到着地点ＧＬまで移動するのに要する移動所要時間と、利用される利用施設と、が示されている。例えば、経路Ｒ２３は、一点鎖線の矢印で示される経路であり、いずれの施設も利用されないで出発地点ＳＡから到着地点ＧＬまで１２分で移動できる経路と、施設Ｉが利用されて出発地点ＳＡから到着地点ＧＬまで３７分で移動できる経路と、の２種類の経路である。
【００８９】
以上説明したように、第４実施形態におけるサーバ１００では、経路探索部１２０は、ノードＮ８３において、リンクＬ９３に関連付けられた施設Ｉが利用されない場合のラベルＡ１と、施設Ｉが利用された場合のラベルＡ２と、の２つのラベルを付与する。ラベルＡ１は、いずれの施設も利用されておらず、経路加算コストが２であり、直前ラベルがラベルＡ０である。ラベルＡ２は、施設Ｉが利用され、経路加算コストがリンクＬ９３を通過した場合の経路加算コストの２と施設Ｉの施設利用時間である２５とを足した２７であり、直前ラベルがラベルＡ０である。そのため、第４実施形態におけるサーバ１００では、出発地点ＳＡから到着地点ＧＬまでの経路の移動所要時間に、利用された施設の施設利用時間も加味されているため、実際の移動所要時間を踏まえて到着地点ＧＬに到着する到着時刻を利用者に提供でき、利用者の利便性が向上する。
【００９０】
Ｅ．第５実施形態：
第５実施形態では、上記実施形態と異なり、ＰＯＩ情報ＤＢ１１６は、施設の各種情報として、特定の施設で予め定められた時間に行なわれるイベントと、イベントが行なわれる開始時間および終了時間と、を記憶しており、経路探索部１２０は、イベントの開始時刻および終了時刻に基づいてラベルを付与する方法を変更する。
【００９１】
図２６は、許容経路に関連付けられた施設の情報を示す説明図である。図２６（ａ）には、第５実施形態における許容経路が線種の異なる矢印で示されており、リンクに関連付けられた施設Ｋから施設Ｏまでの各施設が示されている。ＰＯＩ情報ＤＢ１１６は、特定の施設におけるイベントに参加した場合に要されるイベント所要時間を記憶している。図２６（ａ）において、最適経路は、出発地点ＳＡを出発して、リンクＬ１１１、ノードＮ９１、リンクＬ１１２、ノードＮ９２、リンクＬ１１６、を通過して、到着地点ＧＬに到着する経路である。第５実施形態では、最適経路のコスト累計値が１０であり、出発地点ＳＡから到着地点ＧＬまで到着するまでの上限時間は１３０分に設定されているため、許容タイムは１２０分である。また、携帯電話機２００の利用者が出発地点ＳＡを出発する時刻は９時である。
【００９２】
図２６（ｂ）には、ＰＯＩ情報ＤＢ１１６が記憶している各施設の分類と、施設が提供するサービスの内容と、イベントフラグと、早めフラグと、イベントに参加した場合に要するイベント所要時間と、イベント開始時刻と、イベント終了時刻と、が示されている。イベントフラグは、施設に予め設定されたイベントの有無を表している。早めフラグは、施設のイベントに参加する場合にイベント開始時刻までに施設に到着する必要の有無と、イベント開始時刻までに到着する必要がある場合にはイベントの内容と、を表している。例えば、図２６（ｂ）に示すように、施設Ｍは、人形焼を作っている飲食店であり、１０時３０分から１２時までに特売のイベントがあり、このイベントには早めフラグが設定されていない。そのため、利用者が施設Ｍのイベントに参加するためには、１０時３０分から１１時４５分（イベント終了の１２時からイベント所要時間の１５分を差し引いた時刻）に施設Ｍに到着する必要がある。
【００９３】
図２７は、許容経路のそれぞれにおいて利用される施設を選択する流れの詳細を示す説明図である。図２７（ａ）には、出発地点ＳＡに付与された確定ラベルであるラベルＡ０を直前ノードとして、ノードＮ９４におけるラベルＡ１およびラベルＡ２と、ノードＮ９１におけるラベルＡ３と、が付与された状態が示されている。ラベルＡ１は、施設Ｏが利用されていないラベルであり、ラベルＡ２は、施設Ｏが利用されたラベルである。ノードＮ９１におけるラベルＡ３は、いずれの施設も利用されていないラベルである。
【００９４】
図２７（ｂ）には、ノードＮ９４に付与されたラベルＡ２を直前ノードとして、ノードＮ９５におけるラベルＡ４とラベルＡ５とラベルＡ６とが付与された状態が示されている。なお、ノードＮ９７に付与されるラベルは、リンクＬ１１８およびリンクＬ１２０においていずれの施設も利用されず、ラベルの付与方法が上記実施形態と同じであるため、説明を省略する。ラベルＡ４は、施設Ｍが利用されていないラベルである。ラベルＡ５は、施設Ｍが利用されるラベルである。ラベルＡ６は、施設Ｍが利用されて、さらに、施設Ｍにおける１０時３０分からの特売のイベントに利用者が参加するラベルである。なお、ラベルＡ６には、１０時３０分までの待ち時間が経路加算コストとして加えられる。
【００９５】
図２７（ｃ）には、ノードＮ９１に付与されたラベルＡ３を直前ノードとして、ノードＮ９３におけるラベルＡ７およびラベルＡ８が付与された後に、ラベルＡ８を直前ノードとして、ノードＮ９５におけるラベルＡ９およびラベルＡ１０が付与された状態が示されている。ラベルＡ７は、施設Ｌが利用されていないラベルであり、ラベルＡ８は、施設Ｌが利用されているラベルである。ラベルＡ８の経路加算コストには、施設Ｌのイベント開始時刻が１０時であるため、待ち時間が含まれている。ラベルＡ９は、直前ラベルがラベルＡ８で、施設Ｎが利用されないラベルである。ラベルＡ１０は、直前ラベルがラベルＡ８で、施設Ｎが利用されるものの、施設Ｎのイベントには利用者が参加しないラベルである。なお、ノードＮ９５において、施設Ｎのイベント開始時刻である９時３０分以降に施設Ｎに到着すると共に、施設Ｎには早めフラグが設定されているため、経路探索部１２０は、直前ラベルがラベルＡ８の場合には、利用者が施設Ｎのイベントに参加するラベルＡ１１を付与しない。
【００９６】
図２８は、許容経路のそれぞれにおいて利用される施設を示す説明図である。図２８（ａ）には、許容経路が経路加算コストに応じて線種の異なる矢印で示されている。図２８（ｂ）には、経路Ｒ３１から経路Ｒ３５までの許容経路のそれぞれにおいて、出発地点ＳＡから到着地点ＧＬまで移動するのに要する移動所要時間と、いずれかの施設におけるイベントの参加の有無と、イベントに参加する場合の待ち時間と、が示されている。例えば、経路Ｒ３２は、破線の矢印で示される経路であり、いずれの施設も利用されないで移動所要時間が２０分である経路と、施設Ｎが利用されて移動所要時間が４５分である経路と、を含む経路である。
【００９７】
以上説明したように、第５実施形態におけるサーバ１００では、ＰＯＩ情報ＤＢ１１６は、施設の各種情報として、特定の施設で予め定められた時間に行なわれるイベントと、イベントが行なわれる開始時間および終了時間と、を記憶している。経路探索部１２０は、イベント開始時刻からイベント終了時刻までの間に利用できる施設がある場合には、施設が利用された場合と利用されていない場合との２つのラベルを付与する。一方で、経路探索部１２０は、イベント開始時刻からイベント終了時刻までの間に利用できる施設がない場合には、施設が利用されていない場合のラベルのみを付与する。そのため、第５実施形態におけるサーバ１００では、許容経路に関連付けられた施設があっても、施設が利用できる時間外に当該施設と関連付けられたノードまたはリンクを通過する場合には、施設が利用されないラベルのみが当該施設通過直後のノードに付与される。よって、実際の移動所要時間を踏まえて到着地点ＧＬに到着する到着時刻を利用者に提供でき、利用者の利便性が向上する。
【００９８】
Ｆ．第６実施形態：
第６実施形態では、上記実施形態と異なり、経路探索部１２０は、携帯電話機２００の利用者による入力によって利用者が利用したい特定の施設を取得し、探索された許容経路の内から特定の施設を含む少なくとも１つの許容経路における満足度の合計に、新たに加算する満足度加算値を加える。図２９は、許容経路に関連付けられた施設の情報を示す説明図である。図２９（ａ）には、第６実施形態における出発地点ＳＡ、到着地点ＧＬ、施設Ｐ、施設Ｑ、施設Ｒ、施設Ｓ、施設Ｔ、の位置関係が示されている。なお、図２９（ａ）に示す地図では、リンクおよびノードと、各リンクのリンクコストと、の表示を省略しているが、出発地点ＳＡから到着地点ＧＬまでの許容経路の探索処理については上記実施形態と同じである。図２９（ｂ）には、施設Ｐから施設Ｔまでのそれぞれの施設について、施設の分類および内容と、施設を利用した場合に要される施設利用時間と、施設を利用できる施設利用可能時間と、が示されている。例えば、施設Ｑは、仏堂の施設であり、利用された場合に要される施設利用時間が２０分であり、施設利用可能時間が１０時から１４時までの間である。
【００９９】
図３０は、許容経路と許容経路に関連付けられた施設との関係の一例を示す説明図である。図３０（ａ）には、許容経路のそれぞれについて、出発地点ＳＡから到着地点ＧＬまでに移動するのに要する移動所要時間と、利用される施設の順序である施設利用順序と、が示されている。なお、第６実施形態では、上限時間が１２０分に設定されている。例えば、経路Ｒ４１は、出発地点ＳＡから到着地点ＧＬまでの移動所要時間が１１５分であり、施設Ｐ、施設Ｑ、施設Ｒ、施設Ｔ、の順に各施設が利用される経路である。
【０１００】
図３０（ｂ）に示すように、利用者の入力の内容に基づいて、許容経路に関連付けられた施設の中に利用者が入力した施設が含まれる場合には、経路探索部１２０が各許容経路の満足度（図示しない）に満足度加算値を加えて、許容経路における満足度の高い経路を携帯電話機２００に表示されて利用者に提供する。例えば、入力ＳＬ１では、最も多くの施設が利用される経路に満足度加算値が加えられて、最多施設利用経路としての経路が提供される。最多施設利用経路として、図３０（ａ）に示す４つの施設が利用される経路Ｒ４１から経路Ｒ５１までの経路が提供される。なお、経路探索部１２０は、請求項における特定施設選択部および指標値加算部に相当する。
【０１０１】
入力ＳＬ２では、施設の利用順路を施設Ｐ、施設Ｑ、施設Ｒ、施設Ｓ、施設Ｔの順に満たした上で、最も多くの施設が利用される経路が提供されるため、施設Ｓ以外が利用されている経路Ｒ４１が提供される。入力ＳＬ３では、最も多くの施設が利用されると共に最短時間で到着地点ＧＬへと到着できる経路が提供されるため、利用施設が４つであると共に移動所要時間が１１０分である経路Ｒ４８および経路Ｒ５１が提供される。入力ＳＬ４では、神社の施設である施設Ｓおよび施設Ｔが優先的に利用される経路が提供されるため、施設Ｓおよび施設Ｔが利用される経路Ｒ５６が提供される。入力ＳＬ５では、施設Ｂが利用される経路が提供されるため、施設Ｂを含む経路である経路Ｒ４１から経路Ｒ４４までの各経路、経路Ｒ４６から経路Ｒ５１までの各経路、経路Ｒ５３、経路Ｒ５７、経路Ｒ５８、が提供される。
【０１０２】
以上説明したように、第６実施形態におけるサーバ１００では、経路探索部１２０は、許容経路に関連付けられた施設の中に利用者が入力した施設が含まれる場合には、各許容経路の満足度に満足度加算値を加える。そのため、第６実施形態におけるサーバ１００では、利用者が利用したい施設があった場合に、当該施設を利用できる許容経路を優先的に利用者に提供できるため、利用者が出発地点ＳＡから到着地点ＧＬまでの経路を探索する場合の利便性が向上する。
【０１０３】
Ｇ．変形例：
なお、この発明は上記の実施例や実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様において実施することが可能であり、例えば次のような変形も可能である。
【０１０４】
Ｇ１．変形例１：
上記実施形態では、許容経路は、最適経路と、最適経路と上限時間に基づいて設定される類似経路と、で構成される態様としたが、探索される許容経路については、種々変形可能である。例えば、上限時間のみに基づいて出発地点から到着地点ＧＬまでの許容経路が探索されてもよい。このサーバ１００では、上記実施形態の許容経路の探索と比較して、余分に時間がかかるものの、より多くの許容経路を探索できる場合があり、利用者の自由度が向上する場合がある。
【０１０５】
また、上記実施形態では、各施設に設定された指標値として満足度を例に挙げたが、指標値はこれに限られず、種々変形可能である。例えば、利用者が飲食店を探している場合に、飲食店の指標値を１と（例えば、「ＯＮ」と設定）して、飲食店以外の店舗の指標値を０と（例えば、「ＯＦＦ」と設定）することで、利用者は目的にあった施設のみを探索することができる。
【０１０６】
また、上記実施形態では、利用者が入力した特定の施設が含まれる許容経路に満足度加算値が加えられる態様としたが、他の態様であってもよい。例えば、２つの特定の施設同士が関連するイベントがあった場合に、単純に２つの施設が含まれる許容経路ではなく、１つの施設を利用した後にもう１つの施設を利用する許容経路にのみ、満足度加算値が加えられる態様であってもよい。
【０１０７】
上記実施形態では、出発地点ＳＡと到着地点ＧＬとが異なる地点であったが、出発地点ＳＡと到着地点ＧＬとが同じ地点であってもよい。例えば、利用者Ａが自宅を出発地点ＳＡをとし、色々な施設を利用した後に、到着地点ＧＬが出発地点ＳＡと同じである自宅に戻ってくる態様であってもよい。
【０１０８】
Ｇ２．変形例２：
また、上記実施形態では、利用者が携帯電話機２００の操作部２０６を操作することにより、到着地点ＧＬを設定したが、到着地点ＧＬおよび各種設定の入力手段はこれに限られず、種々変形可能である。例えば、携帯電話機２００が利用者の音声入力を受け付ける音声入力部を備えており、音声によって到着地点ＧＬの設定等、各種設定が行なわれてもよい。
【０１０９】
また、上記実施形態では、図１に示すようにサーバ１００が情報記憶部１１０および経路探索部１２０を備える態様としたが、情報記憶部１１０および経路探索部１２０を備える装置はこの態様に限られず、種々変形可能である。例えば、情報記憶部１１０と経路探索部１２０とは異なるサーバに備えられていてもよいし、経路探索部１２０が携帯電話機２００に搭載されていてもよい。また、経路探索部１２０における最適経路探索部１２３および類似経路設定部１２４は、それぞれ異なるサーバ１００に備えられていてもよい。また、地図情報ＤＢ１１４とノード別経路情報ＤＢ１１５とが同じデータベースに記憶されていてもよい。
【０１１０】
本発明は、上記実施形態や変形例に限られるものではなく、その趣旨を逸脱しない範囲において種々の構成で実現することができる。例えば、発明の概要の欄に記載した各形態中の技術的特徴に対応する実施形態、変形例中の技術的特徴は、上述の課題の一部または全部を解決するために、あるいは、上述の効果の一部または全部を達成するために、適宜、差し替えや、組み合わせを行なうことが可能である。また、その技術的特徴が本明細書中に必須なものとして説明されていなければ、適宜、削除することが可能である。
【符号の説明】
【０１１１】
１０…経路探索システム
１００…サーバ
１０２…通信部
１１０…情報記憶部
１１６…ＰＯＩ情報ＤＢ
１１８…記憶装置
１２０…経路探索部
１２１…許容経路探索部
１２３…最適経路探索部
１２４…類似経路設定部
２００…携帯電話機
２０１…ＧＰＳ受信機
２０２…表示パネル
２０３…音声出力部
２０５…無線通信回路
２０６…操作部
２０６ａ…テンキー
２０６ｂ…カーソルキー
２１０…主制御部
２１１…ＣＰＵ
２２０…通話制御部
ＳＡ…出発地点
ＧＬ…到着地点
ＢＳ…基地局
ＳＰ１，ＳＰ２，ＳＰ３，ＳＰ４…施設ノード
ＩＮＴ…インターネット
【図１】
2014190777.tif 000003
【図２】
2014190777.tif 000004
【図３】
2014190777.tif 000005
【図４】
2014190777.tif 000006
【図５】
2014190777.tif 000007
【図６】
2014190777.tif 000008
【図７】
2014190777.tif 000009
【図８】
2014190777.tif 000010
【図９】
2014190777.tif 000011
【図１０】
2014190777.tif 000012
【図１１】
2014190777.tif 000013
【図１２】
2014190777.tif 000014
【図１３】
2014190777.tif 000015
【図１４】
2014190777.tif 000016
【図１５】
2014190777.tif 000017
【図１６】
2014190777.tif 000018
【図１７】
2014190777.tif 000019
【図１８】
2014190777.tif 000020
【図１９】
2014190777.tif 000021
【図２０】
2014190777.tif 000022
【図２１】
2014190777.tif 000023
【図２２】
2014190777.tif 000024
【図２３】
2014190777.tif 000025
【図２４】
2014190777.tif 000026
【図２５】
2014190777.tif 000027
【図２６】
2014190777.tif 000028
【図２７】
2014190777.tif 000029
【図２８】
2014190777.tif 000030
【図２９】
2014190777.tif 000031
【図３０】
2014190777.tif 000032