(57)【要約】【課題】データ構造およびデータ構造が有するデータを用いた経路探索装置において、設定されたエリア内の経路の探索を迅速に行なうことができる技術を提供する。【解決手段】２つ以上のノードと１つ以上のリンクとを含む第１のエリアに含まれる２つのノードを両端点とする２地点間経路を特定するエリア内経路データが記憶され、エリア内経路データによって特定された２地点間経路を経路探索に用いることで、ネットワーク上の任意の２つのノードを結ぶ経路を探索する。【選択図】図３
2015152383.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上の経路を探索するために用いられるデータ構造であって、
経路を構成する複数のノードおよび複数のリンクを特定するネットワークデータと、
２つ以上のノードと１つ以上のリンクとを含むエリアを特定するエリアデータと、
第１の前記エリアに含まれる２つのノードを両端点として結ぶ２地点間経路を特定するエリア内経路データと、を備える、データ構造。
【請求項２】
請求項１に記載のデータ構造であって、
前記両端点の２つのノードの内の少なくとも一方は、前記第１のエリアに含まれないノードにリンクを介して接続される境界ノードである、データ構造。
【請求項３】
請求項２に記載のデータ構造であって、
前記両端点の２つのノードは、異なる２つの前記境界ノードである、データ構造。
【請求項４】
請求項１から請求項３までのいずれか一項に記載のデータ構造であって、
前記エリア内経路データは、前記両端点の２つのノードと、前記２地点間経路を構成するリンクのリンクコストの累計値と、の組み合わせによって前記２地点間経路を特定する、データ構造。
【請求項５】
請求項１から請求項４までのいずれか一項に記載のデータ構造であって、
前記エリア内経路データは、前記２地点間経路を構成するリンクのリンクコストの累計値が最小となる前記２地点間経路である第１の経路と、前記第１の経路の前記リンクコストの累計値に許容コストを加えた値以下の前記リンクコストの累計値を有する１つ以上の前記第１の経路以外の前記２地点間経路である第２の経路と、を特定する、データ構造。
【請求項６】
請求項５に記載のデータ構造であって、
前記エリア内経路データは、
前記両端点の２つのノードの内の一方のノードである第１ノードと、前記第１の経路に含まれると共に前記両端点の２つのノードとは異なるノードである最適ノードと、を結ぶ２つ以上の中途経路の内、前記中途経路を構成する前記リンクコストの累計値が最小となる１つの最適経路と、前記最適経路以外の非最適経路と、を特定し、
前記中途経路のそれぞれについて、前記非最適経路と、前記最適ノードと前記両端点の２つのノードの内の前記第１ノードとは異なる第２ノードとを結ぶ経路において前記２地点間経路の前記第１の経路と重複する経路と、から構成される経路を前記第２の経路として特定する、データ構造。
【請求項７】
請求項１から請求項６までのいずれか一項に記載のデータ構造であって、
前記エリア内経路データは、前記第１のエリアに含まれる全てのノードの内から２つのノードが選択された全ての組み合わせのノードの前記２地点間経路のそれぞれを特定する、データ構造。
【請求項８】
請求項１から請求項７までのいずれか一項に記載のデータ構造が有するデータを用いて出発地ノードと目的地ノードとを結ぶ通行経路を探索する経路探索装置であって、
前記データ構造を記憶するデータ記憶部と、
前記出発地ノードと前記目的地ノードとを設定する条件設定部と、
前記データ記憶部に記憶された１つ以上の前記エリアを設定するエリア設定部と、
前記通行経路に含まれる前記エリア内の経路を、前記エリア内経路データを用いて探索する経路探索部と、を備える、経路探索装置。
【請求項９】
請求項１から請求項７までのいずれか一項に記載のデータ構造を記憶したデータ記憶装置を用いて出発地ノードと目的地ノードとを結ぶ通行経路を探索する経路探索方法であって、
前記出発地ノードと前記目的地ノードとを設定する工程と、
前記データ記憶装置に記憶された１つ以上の前記エリアを設定する工程と、
前記通行経路に含まれる前記エリア内の経路を、前記エリア内経路データを用いて探索する工程と、を備える、経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ構造、経路探索装置、および、経路探索方法に関する。
【背景技術】
【０００２】
現在位置から目的地までの経路を探索する経路探索装置として、自動車に搭載されたカーナビゲーションシステム、携帯電話機、携帯ゲーム機、ＰＮＤ（Personal Navigation Device）およびＰＤＡ（Personal Digital Assistant）が知られている。経路が探索されるときには、サーバ等に記憶されたネットワークを構成するノード情報およびリンク情報を特定するデータが用いられる。
【０００３】
従来のナビゲーション装置では、例えば、特許文献１に記載されているように、現在位置から目的地まで最も速く到着できる最適経路が探索された場合に、現在位置から目的地までの周辺が検索エリアとして設定され、ユーザによって指定された施設（例えば、ガソリンスタンド）が検索エリアの範囲内において検索される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−２３４９３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載された技術では、複数の検索エリアが設定されると共に異なる検索エリア内に指定された施設がある場合、最適経路から指定された施設のそれぞれまでの経路が探索されるため、指定された施設までの経路が探索されるのに多くの時間を要する場合があった。また、最適経路における右左折する交差点を中心とした検索エリアを探索する場合もあるため、右左折の数によって検索エリアが最適経路ごとに異なり、指定された施設を探索するのに多くの時間を要する場合があった。そのほか、従来の経路探索が行なわれるときに用いられるデータ構造として、使い勝手の向上等が望まれていた。
【課題を解決するための手段】
【０００６】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態として実現することが可能である。
【０００７】
（１）本発明の一形態によれば、ネットワーク上の経路を探索するために用いられるデータ構造が提供される。このデータ構造は、経路を構成する複数のノードおよび複数のリンクを特定するネットワークデータと；２つ以上のノードと１つ以上のリンクとを含むエリアを特定するエリアデータと；第１の前記エリアに含まれる２つのノードを両端点として結ぶ２地点間経路を特定するエリア内経路データと、を備える。この形態のデータ構造によれば、ネットワーク上の２つのノードを結ぶ経路が探索される場合に、エリア内の経路については、２地点間経路を用いた探索が行なわれるため、エリアを経由する２つのノードを結ぶ経路を迅速に探索できる。また、エリアデータによって特定されるエリアには、観光地等のエリアがあり、エリア内の経路探索の処理が集中するおそれがある。その場合に、本形態のデータ構造では、予めエリア内経路を特定するエリア内経路データを有することで、エリア内経路を探索するための処理時間を短縮できる。
【０００８】
（２）上記形態のデータ構造において、前記両端点の２つのノードの内の少なくとも一方は、前記第１のエリアに含まれないノードにリンクを介して接続される境界ノードであってもよい。この形態のデータ構造によれば、経路探索処理における両端点の２つのノードがエリア内のノードであっても、特定された２地点間経路によって、簡便にエリア内経路を探索でき、両端点の２つのノードを結ぶ経路を迅速に探索できる。
【０００９】
（３）上記形態のデータ構造において、前記両端点の２つのノードは、異なる２つの前記境界ノードであってもよい。この形態のデータ構造によれば、特定のエリアを経由するエリア外の両端点の２つのノードを結ぶ経路が探索される場合に、エリア内経路が迅速に探索される。
【００１０】
（４）上記形態のデータ構造において、前記エリア内経路データは、前記両端点の２つのノードと、前記２地点間経路を構成するリンクのリンクコストの累計値と、の組み合わせによって前記２地点間経路を特定してもよい。この形態のデータ構造によれば、エリア内経路が探索される場合に、エリア内経路を通過するためのリンクコストが算出されるため、エリア内経路を探索するユーザの利便性が向上する。
【００１１】
（５）上記形態のデータ構造において、前記エリア内経路データは、前記２地点間経路を構成するリンクのリンクコストの累計値が最小となる前記２地点間経路である第１の経路と、前記第１の経路の前記リンクコストの累計値に許容コストを加えた値以下の前記リンクコストの累計値を有する１つ以上の前記第１の経路以外の前記２地点間経路である第２の経路と、を特定してもよい。この形態のデータ構造によれば、エリア内を通過するのに予め定められた時間内にエリアを通過する複数の経路をユーザに提示でき、ユーザの利便性が向上する。
【００１２】
（６）上記形態のデータ構造において、前記エリア内経路データは；前記両端点の２つのノードの内の一方のノードである第１ノードと、前記第１の経路に含まれると共に前記両端点の２つのノードとは異なるノードである最適ノードと、結ぶ２つ以上の中途経路の内、前記中途経路を構成する前記リンクコストの累計値が最小となる１つの最適経路と、前記最適経路以外の非最適経路と、を特定し；前記中途経路のそれぞれについて、前記非最適経路と、前記最適ノードと前記両端点の２つのノードの内の前記第１ノードとは異なる第２ノードとを結ぶ経路において前記２地点間経路の前記第１の経路と重複する経路と、から構成される経路を前記第２の経路として特定してもよい。この形態のデータ構造によれば、エリア内の最適ノードに付与された経路が構成するリンクとリンクコストの累計値とに基づいて、エリア内の選択された２つのノードの組み合わせに対応して複数の類似経路を探索でき、必要最低限のデータによって、エリア内経路を探索でき、データを記憶する容量の増加を抑制できる。
【００１３】
（７）上記形態のデータ構造において、前記エリア内経路データは、前記第１のエリアに含まれる全てのノードの内から２つのノードが選択された全ての組み合わせのノードの前記２地点間経路のそれぞれを特定してもよい。この形態のデータ構造によれば、経路探索によって探索される２つの両端点のノードがエリア内の境界ノード以外のノードであっても、両端点のノードを基準とする２地点間経路が予め特定されているため、経路を迅速に探索できる。
【００１４】
（８）本発明の他の形態によれば、データ構造が有するデータを用いて出発地ノードと目的地ノードとを結ぶ通行経路を探索する経路探索装置が提供される。この経路探索装置は、前記データ構造を記憶するデータ記憶部と；前記出発地ノードと前記目的地ノードとを設定する条件設定部と；前記データ記憶部に記憶された１つ以上の前記エリアを設定するエリア設定部と；前記通行経路に含まれる前記エリア内の経路を、前記エリア内経路データを用いて探索する経路探索部と、を備える。この形態の経路探索装置によれば、ネットワーク上の２つのノードを結ぶ経路が探索される場合に、エリア内の経路については、２地点間経路を用いた探索が行なわれるため、エリアを経由する２つのノードを結ぶ経路を迅速に探索できる。
【００１５】
（９）本発明の他の形態によれば、データ構造を記憶したデータ記憶装置を用いて出発地ノードと目的地ノードとを結ぶ通行経路を探索する経路探索方法が提供される。この経路探索方法は、前記出発地ノードと前記目的地ノードとを設定する工程と；前記データ記憶装置に記憶された１つ以上の前記エリアを設定する工程と；前記通行経路に含まれる前記エリア内の経路を、前記エリア内経路データを用いて探索する工程と、を備える。この形態の経路探索方法によれば、ネットワーク上の出発地ノードと目的地ノードとの２つのノードを結ぶ経路が探索される場合に、エリア内の経路については、２地点間経路を用いた探索が行なわれるため、エリアを経由する２つのノードを結ぶ経路を迅速に探索できる。
【００１６】
例えば、本発明の一形態は、ネットワークデータと、エリアデータと、エリア内経路データと、の３つの要素の内の一部または全部の要素を備えたデータ構造として実現できる。すなわち、このデータ構造は、ネットワークデータを有していてもよく、有していなくてもよい。また、データ構造は、エリアデータを有していてもよく、有していなくてもよい。また、データ構造は、エリア内経路データを有していてもよく、有していなくてもよい。ネットワークデータは、例えば、経路を構成する複数のノードおよび複数のリンクを特定してもよい。エリアデータは、例えば、２つ以上のノードと１つ以上のリンクとを含む２つ以上のエリアを特定してもよい。エリア内経路データは、例えば、第１の前記エリアに含まれる２つのノードを両端点として結ぶ２地点間経路を特定してもよい。こうしたデータ構造は、データ構造以外の他のデータ構造を用いた装置としても実現できる。このような形態によれば、データ構造の利用性の向上および簡易化、データ構造の一体化や、データ構造を用いるユーザの利便性の向上、等の種々の課題の少なくとも１つを解決できる。前述したデータ構造の各形態の技術的特徴の一部または全部は、いずれもこのデータ構造に適用できる。
【００１７】
なお、本発明は、種々の態様で実現することが可能であり、例えば、データ構造、データ構造を用いた経路探索方法、データ構造を用いた経路探索装置および情報処理装置、情報端末装置、情報送信装置、情報送信方法、携帯端末装置、情報処理サーバ、経路探索サーバ、これらの装置、方法、システムを実現するためのコンピュータプログラム等の形態で実現できる。また、これらのコンピュータプログラムは、コンピュータが読取可能な記録媒体（例えば、フレキシブルディスクやＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、光磁気ディスク、メモリカード、ハードディスク等）に記録されていてもよい。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１実施形態における経路探索システム１０の概略構成を示す説明図である。
【図２】エリア内経路データの一例を示す説明図である。
【図３】エリア内経路データの一例を示す説明図である。
【図４】エリア内経路データの作成処理の流れを示す説明図である。
【図５】エリア内経路データの作成処理の流れを示す説明図である。
【図６】エリア内経路データの作成処理の流れを示す説明図である。
【図７】エリアＡ２内とエリアＡ２の周辺とにおける経路情報の一部を示す概略図である。
【図８】エリアＡ２内のノードｎ１２に確定ラベルが付与された状態を示す説明図である。
【図９】エリアＡ２の境界ノードの全てに確定ラベルが付与された状態を示す説明図である。
【図１０】エリアＡ２のノードＮ１２に付与された確定ラベルと負けラベルとを示す説明図である。
【図１１】ノードＮ１１とノードＮ１４とを結ぶ最適経路等同経路群を示す説明図である。
【図１２】経路探索処理の流れを示す説明図である。
【図１３】経路探索処理においてノードにラベルが順々に付与される状態を示す概略図である。
【図１４】境界ノードを基準とするラベル更新の処理の流れを示す説明図である。
【図１５】エリアＡ３の境界ノードのノードＮ２１に確定ラベルが付与された状態を示す概略図である。
【図１６】エリアＡ３の境界ノードであるノードＮ２３にも確定ラベルが付与された状態を示す概略図である。
【図１７】現在位置Ｓのノードを基準とするラベル更新の処理の流れを示す説明図である。
【図１８】エリアＡ４における現在位置Ｓ１のノードと境界ノードであるノードＮ３１とを結ぶ経路の一例を示す概略図である。
【図１９】逆方向に変換されたラベルの一例を示す概略図である。
【図２０】第２実施形態における現在位置Ｓと目的地Ｇとを結ぶ経路の概略図である。
【図２１】第２実施形態における現在位置Ｓと目的地Ｇとを結ぶ経路の概略図である。
【図２２】第２実施形態における現在位置Ｓと目的地Ｇとを結ぶ経路の概略図である。
【発明を実施するための形態】
【００１９】
次に、本発明の実施形態を以下の順序で説明する。
Ａ．第１実施形態：
Ａ−１．経路探索システムの構成：
Ａ−２．エリア内経路データ：
Ａ−３．エリア内経路データの作成：
Ａ−４．経路探索処理：
Ｂ．第１実施形態の変形例：
Ｃ．第２実施形態：
Ｄ．変形例：
【００２０】
Ａ．第１実施形態：
Ａ−１．経路探索システムの構成：
図１は、本発明の第１実施形態における経路探索システム１０の概略構成を示す説明図である。本実施形態の経路探索システム１０は、サーバ１００と携帯端末装置としての携帯電話機２００とを備えている。図１には、携帯電話機２００を１台のみ示しているが、経路探索システム１０には、複数の携帯電話機２００および携帯ゲーム機、ＰＮＤ（Personal Navigation Device）、ＰＤＡ（Personal Digital Assistant）といった様々な携帯端末装置が含まれ得る。
【００２１】
携帯電話機２００は、主制御部２１０と、ＧＰＳユニット２０１と、表示パネル２０２と、音声出力部２０３と、無線通信回路２０５と、操作部２０６と、通話制御部２２０と、を備えている。
【００２２】
主制御部２１０は、携帯電話機２００の各部を制御する。主制御部２１０は、ＣＰＵ２１１と、ＲＡＭ２１２と、ＲＯＭ２１３とを備えている。ＣＰＵ２１１は、ＲＯＭ２１３に記憶されたプログラムをＲＡＭ２１２にロードして実行することで、後述する種々の処理を実行するために機能する。
【００２３】
ＧＰＳユニット２０１は、ＧＰＳ（Global Positioning System／全地球測位システム）から人工衛星の位置を示す電波を受信する。主制御部２１０は、ＧＰＳユニット２０１が受信した人工衛星の位置を用いて、携帯電話機２００の現在位置（緯度、経度）を特定し、一定時間ごとに特定した携帯電話機２００の現在位置を示す位置情報を生成する。
【００２４】
表示パネル２０２は、液晶ディスプレイと液晶ディスプレイを駆動する駆動回路とを備えている。表示パネル２０２としては、液晶ディスプレイに限らず、有機ＥＬディスプレイなど、種々の表示デバイスを採用できる。主制御部２１０は、表示パネル２０２を制御することで、例えば、地図画像や推奨経路、現在位置などを表示する。音声出力部２０３は、音声を出力するためのスピーカーや、スピーカーを駆動する駆動回路などから構成される。
【００２５】
無線通信回路２０５は、基地局ＢＳとの間でデータ通信もしくは音声通信を無線によって行なう。主制御部２１０は、無線通信回路２０５を制御することで、基地局ＢＳを介して（より詳細には、送受信アンテナ、基地局ＢＳ、交換局を介して）、インターネットＩＮＴ上のサーバ１００と通信する。
【００２６】
操作部２０６は、テンキー２０６ａやカーソルキー２０６ｂやタッチパネルなどから構成される入力デバイスである。操作部２０６は、利用者による目的地の設定入力等を受け付ける。通話制御部２２０は、音声通話のための着信や呼出、音声信号と電気信号の変換などを行なう。
【００２７】
サーバ１００は、インターネットＩＮＴを介して携帯電話機２００との通信を行なう通信部１０２と、情報記憶部１１０と、経路探索部１２０と、を備えている。情報記憶部１１０は、ＣＰＵやＲＡＭ、ＲＯＭにより構成された制御部を有し、情報を記憶する記憶装置１１８と、を備えている。記憶装置１１８は、例えば、ハードディスク装置により構成されている。記憶装置１１８は、地図情報データベース（ＤＢ）１１４と、エリア情報データベース（ＤＢ）１１５と、エリア内経路情報データベース（ＤＢ）１１６と、を含んでいる。
【００２８】
地図情報ＤＢ１１４は、地図上のネットワークを構成するリンク情報およびノード情報である経路情報と、画像データとしての地図画像データと、を記憶している。エリア情報ＤＢ１１５は、地図情報ＤＢ１１４に記憶された２つ以上のノードと１つ以上のリンクとから構成されるエリアを特定するエリアデータを記憶している。なお、エリアデータによって特定されるデータとしては、例えば、観光地や商店街といったエリアがある。エリアデータの詳細については、後述する。エリア内経路情報ＤＢ１１６は、エリアデータによって特定されたエリアに含まれる２つのノードを結ぶエリア内経路を特定するエリア内経路データ３００を記憶している。本実施形態では、エリア内経路データは、接続されたリンクを介してエリア外のノードと接続する２つの異なる境界ノードを結ぶ経路を特定するために、エリア内の複数のノードに付与されたラベルを特定する。なお、ラベルおよびエリア内経路データ３００の詳細については、後述する。サーバ１００は、請求項における経路探索装置に相当し、情報記憶部１１０は、請求項におけるデータ記憶部に相当する。また、地図情報ＤＢ１１４に記憶された経路情報は、請求項におけるネットワークデータに相当する。
【００２９】
経路探索部１２０は、ＣＰＵやＲＡＭ、ＲＯＭにより構成された制御部を有する。経路探索部１２０は、ユーザによって携帯電話機２００に目的地と目的地に到着する到着時刻とが設定されると、到着時刻までに目的地に到着できる範囲で、携帯電話機２００の現在位置と設定された目的地とを結ぶ経路を探索する。経路探索部１２０は、エリアデータによって特定されたエリアも含めて、現在位置から目的地までの経路を探索する。経路探索の詳細については、後述する。
【００３０】
経路探索部１２０は、最適経路探索部１２３と、類似経路探索部１２４と、を備えている。最適経路探索部１２３は、地図情報ＤＢ１１４に記憶してある経路情報と受信した位置情報および目的地情報に基づいて、経路を構成する各リンクのリンクコストを足し合わせて、現在位置と目的地とを結ぶ経路のリンクコストの累計値が最小となる経路を探索する。なお、以下では、特定の経路を構成する各リンクのリンクコストの累計値を「経路コスト」とも呼び、特定の２つのノードを結ぶ経路の内、経路コストが最小の経路を最適経路と呼ぶ。すなわち、最適経路探索部１２３は、現在位置と目的地とを結ぶ最適経路を探索する。また、本実施形態では、リンクのリンクコストは、当該リンクを通過するための時間（分）として設定されている。
【００３１】
類似経路探索部１２４は、経路情報と最適経路の経路コストとに基づいて、設定された許容コストを最適経路の経路コストに加算した値以下の経路コストとなる現在位置と目的地とを結ぶ類似経路を探索する。なお、類似経路とは、特定の２つのノードを結ぶ経路における最適経路の経路コストに許容コストを加算した値以下の経路コストとなる経路全般をいう。経路探索部１２０は、通信部１０２を介して、携帯電話機２００に現在位置と目的地とを結ぶ最適経路と類似経路と示す経路情報を送信する。なお、最適経路と類似経路とを合わせて、最適経路同等経路群とも呼び、最適経路と類似経路との探索の詳細については、後述する。
【００３２】
Ａ−２．エリア内経路データ：
図２および図３は、エリア内経路データ３００の一例を示す説明図である。図２には、ネットワークデータ上のエリアＡ１の周辺の経路情報が示されている。また、図２には、エリアＡ１に含まれるノードのそれぞれに付与されたラベルが示されている。図２に示すように、エリアＡ１には、ノードＮ１からノードＮ６までの６つのノードが含まれている。これらの６つノードは、エリア内に含まれるリンクＬＮ１からＬＮ９までの９つのリンクのいずれかによって接続されている。また、６つのノードの内、ノードＮ１とノードＮ６とは、エリアＡ１に含まれないノードとリンクを介して接続されている境界ノードである。なお、図２では、エリアＡ１に含まれないノードを示すノードＩＤとリンクを示すリンクＩＤとの図示を省略している。
【００３３】
図２において、ノードＮ１からノードＮ６までのノードのそれぞれには、境界ノードであるノードＮ１と、境界ノードであるノードＮ６と、の２つのノードが両端点として設定された場合に、エリア内の各ノードに付与されたラベルが示されている。ノードに付与されるラベルには、確定ラベルと負けラベルとの２種類のラベルがある。確定ラベルとは経路を構成するリンクコストの累計値が最小であるラベルであり、負けラベルとは経路を構成するリンクコストの累計値が最小でないラベルである。ノードによって、確定ラベルおよび負けラベルが付与される場合と、確定ラベルのみが付与される場合と、ラベルが付与されない場合と、に分かれる。図２では、確定ラベルのラベルナンバー（ラベルＮｏ）が経路コストを含む四角で囲まれて示され、負けラベルのラベルＮｏが四角で囲われると共に四角の内部が斜線のハッチングで示されている。例えば、ノードＮ２には、確定ラベルと負けラベルとが付与され、ノードＮ４には、確定ラベルのみが付与されている。また、確定ラベルおよび負けラベルによって特定されるエリア内経路のそれぞれが線種の異なる矢印で示されている。なお、確定ラベルと負けラベルとの違いを含めたラベルの詳細と、ノードにラベルを付与するエリア内経路データ３００の作成と、の詳細については後述する。
【００３４】
図３には、エリア内経路データ３００が特定するエリアＡ１に含まれるノードのそれぞれに付与されたラベルの一覧が示されている。エリア内経路データ３００は、ラベルのそれぞれについて、経路コストと、ラベルが付与されたノードと、当該ラベルが付与される前のラベルと、確定ラベルと負けラベルとの別を示す確定フラグと、の組み合わせを特定する。図３における経路コストの欄に示す値は、出発地として設定されたノードＮ１からラベルが付与されたノードまでを通過した経路コストである。確定フラグは、当該ラベルが確定ラベルの場合には、値「１」とされ、当該ラベルが負けラベルの場合には、値「０」とされる。例えば、ラベルＬＢ０は、出発地であるノードＮ１に付与されているため、いずれのリンクも通過しておらず、経路コストが０であり、ラベルＬＢ０の前のラベルが存在せず、確定ラベルである。また、ラベルＬＢ１は、ノードＮ２に付与され、前のラベルがラベルＬＢ０であるため、リンクＬＮ３を通過しており、経路コストがリンクＬＮ３のリンクコストの５の確定ラベルである。すなわち、ノードＮ６に付与されたラベルＬＢ６に着目すると、エリア内経路データ３００によって、ラベルＬＢ６の前のラベルがラベルＬＢ２であり、ラベルＬＢ２の前のラベルがラベルＬＢ０であることがわかる。ラベルＬＢ０が付与されたノードはノードＮ１であるため、エリア内経路データ３００は、ノードＮ１とノードＮ６とを結ぶ経路を特定する。また、エリア内経路データ３００は、ラベルＬＢ６の経路コストが１２であるため、ノードＮ１とノードＮ６とを結ぶラベルＬＢ６によって特定される経路の経路コストを特定する。図２および図３に示す例では、ノードＮ１とノードＮ２とが請求項における両端点の２つのノードに相当し、ノードＮ１とノードＮ２とを結ぶ経路が２地点間経路に相当する。なお、請求項における両端点の２つのノードとしては、エリアＡ１内に含まれる任意の２つのノードが選択されてもよい。
【００３５】
Ａ−３．エリア内経路データの作成：
図４から図６までの各図は、エリア内経路データの作成処理の流れを示す説明図である。エリア内経路データの作成処理は、エリア内の複数のノードに確定ラベルや負けラベルが付与された後に、２つの境界ノードを結ぶ経路の最適経路と類似経路とを探索して、２つの境界ノードの組み合わせに対応付けた複数のラベルを特定する処理である。なお、本実施形態では、エリア内経路データの作成処理は、経路探索システム１０に含まれていないコンピュータによって行なわれる。
【００３６】
エリア内経路データの作成処理では、初めに、後述する類似経路の探索に用いられる許容コストが設定される（ステップＳ１０）。許容コストを用いた類似経路の探索の詳細については、後述するが、本実施形態では、許容コストが１０として設定される。次に、エリア内に含まれる１つ以上の境界ノードの内から、基準となる１つの基準の境界ノードが選択される（ステップＳ１２）。
【００３７】
図７は、エリアＡ２内とエリアＡ２の周辺とにおける経路情報の一部を示す概略図である。図７に示すように、エリアＡ２には、経路情報として、複数のノードおよび複数のリンクが含まれている。図７には、エリアＡ２に含まれるリンクのリンクコストが四角で囲われた数字で示されている。例えば、ノードＮ１１とノードＮ１２とを結ぶリンクＬＮ０１のリンクコストは、１０である。また、図７には、エリアＡ２のエリア外の複数のノードおよび複数のリンクの一部も示されている。なお、エリアＡ２外のリンクのリンクコストについては、図示を省略している。図７に示すように、エリアＡ２は、境界ノードとして、ノードＮ１１からノードＮ１４までの４つの境界ノードを含んでいる。
【００３８】
エリア内経路データの作成処理において、基準の境界ノードとしてノードＮ１１が選択され（図４のステップＳ１２）、選択された基準の境界ノードであるノードＮ１１に、確定ラベルまたは負けラベルの基となる候補ラベルが付与される（ステップＳ１４）。その後、エリアＡ２内のノードに付与された候補ラベルの内の経路コストが最小の候補ラベルが確定ラベルに変更される（ステップＳ１６）。図７では、ノードＮ１１に付与された候補ラベルが、エリア内のノードに付与された唯一の候補ラベルであるため、確定ラベルに変更される。変更されたノードＮ１１の確定ラベルは、いずれのリンクも通過していないため、経路コストが０のラベルである。
【００３９】
次に、エリアＡ２内の境界ノードの全てに確定ラベルが付与されているか否かが判定される（図４のステップＳ１８）。エリアＡ２内の境界ノードであるノードＮ１２からノードＮ１４までの３つのノードのそれぞれには、確定ラベルが付与されていないため（ステップＳ１８：ＮＯ）、確定ラベルが付与されたノードにリンクを介して接続する隣接ノードの全てに新しいラベルが付与される（ステップＳ２０）。図７に示すように、確定ラベルが付与されたノードＮ１１の隣接ノードであるノードｎ１１、ｎ１２、Ｎ１２に新しいラベルが付与される。
【００４０】
次に、新しいラベルが付与された隣接ノードの内の１つの着目ノードとして、ノードｎ１１が選択される（図５のステップＳ２２）。ノードｎ１１が着目ノードとして選択されると、着目ノードのノードｎ１１に付与された１つ以上の新しいラベルの内から、処理対象として１つの新しいラベルが選択される（ステップＳ２４）。なお、ノードｎ１１に付与された新しいラベルは１つであるため、当該新しいラベルが処理対象として選択される。次に、着目ノードに確定ラベルが既に付与されているか否かが判定される（ステップＳ２６）。着目ノードのノードｎ１１には確定ラベルが付与されていないため（ステップＳ２６：ＮＯ）、ノードｎ１１に既に候補ラベルが付与されているか否かが判定される（ステップＳ２８）。ノードｎ１１には候補ラベルが付与されていないため（ステップＳ２８：ＮＯ）、着目ノードのノードｎ１１に付与された新しいラベルがノードｎ１１の候補ラベルに変更される（ステップＳ３４）。
【００４１】
次に、着目ノードであるノードｎ１１に、候補ラベルとして設定された新しいラベル以外に選択されずに処理が行なわれていない新しいラベルがあるか否かが判定される（ステップＳ３８）。ノードｎ１１には、処理が行なわれていない新しいラベルが付与されていないため（ステップＳ３８：ＮＯ）、ネットワーク上における新しいラベルが付与されたノードの内、着目ノードとして選択されていないノードがあるか否かが判定される（ステップＳ４０）。ノードｎ１２とノードＮ１２とに新しいラベルが付与されており、これら２つのノードは着目ノードとして選択されていないため（ステップＳ４０：ＮＯ）、次に、ノードｎ１２が着目ノードとして選択され（ステップＳ２２）、ステップＳ２４以降の処理が行なわれる。ノードｎ１２に付与された新しいラベルは、以上に説明したノードｎ１１に付与された新しいラベルと同様の処理が行なわれ、ノードｎ１２における候補ラベルに変更される。その後、ノードＮ１２に付与された新しいラベルも、ノードＮ１２における候補ラベルに変更される。
【００４２】
その後、ステップＳ４０の処理において、新しいラベルが付与されると共に着目ノードとして選択されていないノードがないため（ステップＳ４０：ＮＯ）、エリアＡ２内のノードに付与された候補ラベルの内、経路コストが最小の５の候補ラベルであるノードｎ１２に付与された候補ラベルが確定ラベルに変更される（ステップＳ１６）。全ての境界ノードに確定ラベルが付与されていないため（ステップＳ１８：ＮＯ）、確定ラベルが付与されたノードｎ１２の隣接ノードであるノードｎ１１、ノードｎ１３、ノードＮ１２のそれぞれに新しいラベルが付与される（ステップＳ２０）。なお、１つのノードに付与されるラベルの数の最大は、当該ノードが接続するリンクの数であり、同じリンクを通過する２つのラベルの内の経路コストが最小のラベルのみが付与される。
【００４３】
図８は、エリアＡ２内のノードｎ１２に確定ラベルが付与された状態を示す説明図である。図８に示すように、ノードＮ１１に経路コストが０の確定ラベルＬＢ００と、ノードｎ１２に経路コストが５の確定ラベルＬＢ１１が付与されている。なお、図８では、エリアＡ２内の各リンクのリンクコストが示されていないが、各リンクのリンクコストは、図７に示すリンクコストと同じである。
【００４４】
ノードｎ１２の確定ラベルに基づいて、ノードｎ１２の隣接ノードに新しいラベルが付与され（図４のステップＳ２０）、１つの着目ノードとしてノードｎ１１が選択される（図５のステップＳ２２）。ノードｎ１２に基づいて付与された新しいラベルが選択され（ステップＳ２４）、着目ノードのノードｎ１１には確定ラベルがないため（ステップＳ２６：ＮＯ）、ノードｎ１１に候補ラベルがあるか否かが判定される（ステップＳ２８）。ノードｎ１１には、ノードＮ１１に基づく候補ラベルが付与されているため（ステップＳ２８：ＹＥＳ）、ノードｎ１１における候補ラベルの経路コストが新しいラベルの経路コストよりも大きいか否かが判定される（ステップＳ３０）。候補ラベルの経路コストは、５であり、新しいラベルの経路コストの５よりも大きくないため（ステップＳ３０：ＮＯ）、新しいラベルが負けラベルに変更され（ステップＳ３６）、ステップＳ３８以降の処理が行なわれる。なお、ステップＳ３０の処理において、候補ラベルの経路コストが新しいラベルの経路コストよりも大きいと判定された場合には（ステップＳ３０：ＹＥＳ）、候補ラベルが負けラベルに変更され（ステップＳ３２）、新しいラベルが候補ラベルに変更されて（ステップＳ３４）、ステップＳ３８以降の処理が行なわれる。以上のように、エリアＡ２の基準の境界ノードであるノードＮ１１以外の境界ノードであるノードＮ１２からノードＮ１４までのそれぞれに確定ラベルが付与されるまで、エリアＡ２に含まれるノードへのラベルの付与が行なわれる。
【００４５】
図９は、エリアＡ２の境界ノードの全てに確定ラベルが付与された状態を示す説明図である。図９には、エリアＡ２の境界ノードの全てに付与された確定ラベルの経路コストと、確定ラベルが付与されるまでに境界ノード以外のノードに付与された確定ラベルの経路コストと、が示されている。エリアＡ２の全ての境界ノードに確定ラベルが付与されると（図４のステップＳ１８：ＹＥＳ）、エリアＡ２の境界ノードの内から１つの境界ノードが選択される（図６のステップＳ４２）。なお、エリア内経路データの作成処理では、基準の境界ノードであるノードＮ１１に基づいて、その他の境界ノードに対して確定ラベルが付与されたが、ステップＳ４２では、基準の境界ノードであるノードＮ１１も境界ノードとして選択できる。
【００４６】
ステップＳ４２の処理において、例えば、ノードＮ１２の境界ノードが選択されると、基準の境界ノードであるノードＮ１１と選択された境界ノードであるノードＮ１２とを結ぶ最適経路が探索される（ステップＳ４４）。図９に示すように、ノードＮ１１とノードＮ１２とを結ぶ経路の経路コストの最小値は、ノードＮ１２に付与された確定ラベルの経路コストの１０である。ノードＮ１２に付与された確定ラベルの前のラベルは、ノードＮ１１に付与された確定ラベルである。そのため、ノードＮ１１とノードＮ１２とを結ぶ最適経路は、リンクＬＮ１２を介してノードＮ１１とノードＮ１２とを結ぶ経路である。ノードＮ１１とノードＮ１２とを結ぶ最適経路が探索されると、当該最適経路に基づいて、２つの境界ノードであるノードＮ１１とノードＮ１２とを結ぶ類似経路が探索される（図６のステップＳ４６）。類似経路は、最適経路に含まれるノードである最適ノードに付与された確定ラベルと負けラベルとに基づいて探索される。
【００４７】
図１０は、エリアＡ２のノードＮ１２に付与された確定ラベルと負けラベルとを示す説明図である。図１０には、ノードＮ１２に付与された確定ラベルの経路コストに加え、ノードＮ１２に付与された２つの負けラベルの経路コストが示されている。ノードＮ１２に付与された経路コストが１０の負けラベルは、リンクＬＮ１１とリンクＬＮ１６とを介して、ノードＮ１１とノードＮ１２とを結ぶ経路である。また、ノードＮ１２に付与された経路コストが２０の負けラベルは、リンクＬＮ１１、リンクＬＮ１３、リンクＬＮ１４、リンクＬＮ１５を介して、ノードＮ１１とノードＮ１２とを結ぶ経路である。
【００４８】
ノードＮ１１とノードＮ１２とを結ぶ類似経路は、最適ノードに付与された負けラベルの内の１つの経路コスト差と確定ラベルの経路コスト差を差し引いたラベルコスト差が設定された許容コストの１０以下の場合に、当該負けラベルに基づいて設定される。負けラベルに基づいて設定される類似経路は、負けラベルを構成する経路と、負けラベルが付与された最適ノードとエリア内目的地であるリンクＬＮ１２とを結ぶ最適経路を構成する経路と、を合わせた経路である。例えば、図１０では、リンクＬＮ１６を通過する負けラベルを構成する経路は、リンクＬＮ１１とリンクＬＮ１６とを通過する経路である。また、この経路では、ラベルコスト差が許容コスト以下であるため、当該経路が類似経路として設定される。同様に、リンクＬＮ１５を通過する負けラベルを構成する経路は、リンクＬＮ１１とリンクＬＮ１３とリンクＬＮ１４とリンクＬＮ１５とを通過する経路である。また、この経路では、ラベルコスト差が１０で許容コストの１０以下であるため、当該経路が類似経路として設定される。なお、図１０に示す例では、最適ノードがエリア内目的地のノードＮ１２であるため、負けラベルを構成する経路がそのまま類似経路になるが、最適ノードがエリア内目的地のノードＮ１２とは異なる場合には、負けラベルを構成する経路と、最適ノードとエリア内目的地とを結ぶ最適経路を構成する経路と、を合わせた経路が類似経路になる。
【００４９】
ノードＮ１１とノードＮ１２とを結ぶ最適経路に含まれる最適ノードのノードＮ１２において、類似経路が探索されると、同様に、もう１つの最適ノードであるノードＮ１１に付与された負けラベルに基づく類似経路が探索される。ノードＮ１１とノードＮ１２とを結ぶ経路に含まれる最適ノードにおける全ての類似経路が探索されると（図６のステップＳ４６）、探索された最適経路と類似経路とが合わせて最適経路同等経路群として記憶される（ステップＳ４８）。
【００５０】
図１１は、ノードＮ１１とノードＮ１４とを結ぶ最適経路等同経路群を示す説明図である。図１１には、２つの境界ノードであるノードＮ１１とノードＮ１４とを結ぶ経路において、経路コストが３０の最適経路Ｒ０１と、経路コストが４０の類似経路Ｒ０２と、が示されている。なお、最適経路と類似経路とは、線種が異なる矢印によって示されている。図１１に示すように、２つの境界ノードであるノードＮ１１とノードＮ１４とを結ぶ最適経路同等群として、最適経路Ｒ０１と類似経路Ｒ０２とが記憶される。
【００５１】
１つの基準の境界ノードともう１つの選択された境界ノードとを結ぶ最適経路同等経路群が記憶されると（図６のステップＳ４８）、エリアＡ２において、エリア内目的地として選択されていない境界ノードがあるか否かが判定される（ステップＳ５０）。この時点では、エリア内目的地として選択されていない境界ノードがあるため（ステップＳ５０：ＹＥＳ）、これらの境界ノードのそれぞれが選択されてステップＳ４２以降の処理が行なわれる。
【００５２】
境界ノードのそれぞれに対して、最適経路同等経路群が探索されると、基準の境界ノードであるノードＮ１１を出発地とするときに、エリア内目的地として選択されていない境界ノードがないため（ステップＳ５０：ＮＯ）、エリアＡ２において、基準の境界ノードとして全ての境界ノードが選択されたか否かが判定される（ステップＳ５２）。この時点では、基準の境界ノードとして、ノードＮ１１のみが選択され、ノードＮ１２、ノードＮ１３、ノードＮ１４は選択されていないため（ステップＳ５２：ＮＯ）、これらの境界ノードのそれぞれが基準の境界ノードとして選択されて（図４のステップＳ１２）、ステップＳ１４以降の処理が行なわれる。基準の境界ノードとして全ての境界ノードが選択されると（図６のステップＳ５２：ＹＥＳ）、エリア内経路データの作成処理が終了する。エリアＡ２においては、境界ノードが４つあるため、４つの基準の境界ノードのそれぞれに対応する最適経路同等経路群が探索されて記憶される。
【００５３】
Ａ−４．経路探索処理：
図１２は、経路探索処理の流れを示す説明図である。経路探索処理は、１つ以上のエリアを経由して現在位置と目的地とを結ぶ経路が探索される場合に、経由されるエリア内の経路探索にはエリア内経路データが用いられ、エリア外の経路探索には、ネットワークのノードに確定ラベルと負けラベルとが付与されることで、最適経路同等経路群が探索される処理である。
【００５４】
経路探索処理では、初めに、経路探索部１２０が閾値コストを設定する（ステップＳ１００）。閾値コストは、現在位置と目的地とを結ぶ最適経路の経路コストに加算される値である。閾値コストの詳細については後述するが、経路探索部１２０は、最適経路の経路コストに閾値コストを加算した値を超えるまで、ネットワーク上のノードに候補ラベル、確定ラベル、または負けラベルを付与する。
【００５５】
次に、経路探索部１２０は、現在位置のノードがエリアに含まれないエリア外のノードであるか否かを判定する（ステップＳ１０２）。出発地のノードがエリア外のノードであると判定された場合には（ステップＳ１０２：ＹＥＳ）、経路探索部１２０は、ネットワーク上のノードに候補ラベル、確定ラベル、または負けラベルを順々に付与する（ステップＳ１０４）。なお、ネットワーク上にラベルを付与するために、経路探索部１２０は、エリア内経路データの作成処理における図４のステップＳ１４において、基準の境界ノードの代わりに現在位置のノードに候補ラベルを付与し、ステップＳ１６から図５のステップＳ４０までの処理と同じ処理を繰り返す。なお、図１２のステップＳ１０２の処理において、現在位置のノードがエリア外のノードではないと判定された場合には（ステップＳ１４０：ＮＯ）、経路探索部１２０は、エリア内の現在位置のノードを基準として、現在位置をエリアに含むエリア内経路データによって特定されるラベルをエリア内のノードに付与してエリア内のラベルを更新する。なお、現在位置のノードがエリア内に含まれる場合については、後述する第１の変形例において説明する。
【００５６】
図１３は、経路探索処理においてノードにラベルが順々に付与される状態を示す概略図である。図１３には、現在位置Ｓと目的地ＧとエリアＡ３とを含むネットワークが示されている。エリアＡ３は、境界ノードとして、ノードＮ２１、ノードＮ２２、ノードＮ２３、ノードＮ２４の４つのノードを含んでいる。なお、図１３では、リンクが直線で示され、複数のリンクが交わっている交点がノードである。現在位置Ｓ付近の太い直線は、候補ラベル、確定ラベル、または負けラベルが付与されるときに、通過されたリンクである。
【００５７】
図１３に示すように、ラベルが順々にノードに付与されるごとに、経路探索部１２０は、エリアＡ３内の境界ノードに確定ラベルが付与されたか否かを判定する（図１２のステップＳ１０６）。境界ノードに確定ラベルが付与されたと判定された場合には（ステップＳ１０６：ＹＥＳ）、経路探索部１２０は、確定ラベルが付与された境界ノードを基準のノードとして、エリア内経路データによって特定されるラベルをエリアＡ３のノードに付与してエリアＡ３のラベルを更新する（ステップＳ１２０）。なお、境界ノードを基準とするラベル更新の処理については、後述する。
【００５８】
次に、経路探索部１２０の最適経路探索部１２３は、現在位置Ｓと目的地Ｇとを結ぶ最適経路が探索されたか否かを判定する（ステップＳ１０８）。現在位置Ｓと目的地Ｇとを結ぶ最適経路が探索されていないと判定された場合には（ステップＳ１０８：ＮＯ）、経路探索部１２０は、引き続き、ネットワーク上のノードに候補ラベル、確定ラベル、または負けラベルを付与し（ステップＳ１０４）、ステップＳ１０６以降の処理を行なう。
【００５９】
ステップＳ１０８の処理において、最適経路があると判定された場合には（ステップＳ１０８：ＹＥＳ）、経路探索部１２０は、ネットワーク上のノードに付与された全ての候補ラベルの経路コストが最適経路の経路コストに閾値コストを加えた所定の値を超えているか否かを判定する（ステップＳ１１０）。経路コストが所定の値を超えていない候補ラベルがあると判定された場合には（ステップＳ１１０：ＮＯ）、経路探索部１２０は、引き続き、ステップＳ１０４以降の処理を行なう。
【００６０】
ステップＳ１１０において、全ての候補ラベルの経路コストが所定の値を超えたと判定された場合には（ステップＳ１１０：ＹＥＳ）、経路探索部１２０は、ノードにラベルを付与する処理を終了し、経路探索部１２０の類似経路探索部１２４は、エリア内経路データの作成処理における図６のステップＳ４６およびステップＳ４８と同じ処理を行なって、現在位置Ｓと目的地Ｇとを結ぶ類似経路を探索する。その後、経路探索部１２０は、現在位置Ｓと目的地Ｇとを結ぶ最適経路および類似経路を最適経路同等経路群として設定し（図１２のステップＳ１１２）、経路探索処理を終了する。
【００６１】
図１４は、境界ノードを基準とするラベル更新の処理の流れを示す説明図である。境界ノードを基準とするラベル更新の処理は、境界ノードに確定ラベルが付与された場合に行なわれる処理である。図１５は、エリアＡ３の境界ノードのノードＮ２１に確定ラベルが付与された状態を示す概略図である。図１５では、図１３と同様に、現在位置Ｓと目的地ＧとエリアＡ３とを含むネットワークが示されている。エリアＡ３の境界ノードであるノードＮ２１に確定ラベルが付与されると、経路探索部１２０は、ノードＮ２１を基準としたエリア内経路データの内の１つのラベル情報を読み出す（図１４のステップＳ１２１）。
【００６２】
次に、経路探索部１２０は、読み出したラベル情報を付与すべきノードに既に他の境界ノードの確定ラベルに基づいて付与されたラベルである競合ラベルが付与されているか否かを判定する（ステップＳ１２３）。図１５に示すように、エリアＡ３外のリンクを介して、エリアＡ３の境界ノードに確定ラベルが付与されたのは、ノードＮ２１のみであるため、エリアＡ３内のノードに競合ラベルは付与されていないため（ステップＳ１２３：ＮＯ）、経路探索部１２０は、ノードＮ２１に基づいて読み出したラベル情報をノードに付与する（ステップＳ１２９）。なお、競合ラベルは、同じノードに同じリンクを介して到達すると共に、異なる境界ノードの確定ラベルに基づいて付与されるラベルであり、同じノードであっても異なるリンクを介して到達する場合には、既に付与されていたラベルは競合ラベルとして取り扱われない。次に、経路探索部１２０は、ノードＮ２１を基準としたエリア内経路データの内、読み出していない他のラベル情報があるか否かを判定する（ステップＳ１３１）。
【００６３】
図１６は、エリアＡ３の境界ノードであるノードＮ２３にも確定ラベルが付与された状態を示す概略図である。図１６には、エリアＡ３内の複数のノードに、ノードＮ２１の確定ラベルに基づくラベルが付与された後に、エリアＡ３外のリンクＬＮ２１を介して、境界ノードであるノードＮ２３に確定ラベルが付与された状態が示されている。エリアＡ３では、ノードＮ２１からノードＮ２４までの４つの境界ノードがあり、本実施形態では、４つの境界ノードのそれぞれに、エリアＡ３外のリンクを介して確定ラベルが付与される。そのため、境界ノードのノードＮ２１に付与された確定ラベルに基づいて、ラベルがエリアＡ３内のノードに付与されても、他の境界ノードであるノードＮ２３等に付与された確定ラベルに基づいてラベルを特定するラベル情報があるため（ステップＳ１３１：ＮＯ）、経路探索部１２０は、ノードＮ２１とは異なる境界ノードであるノードＮ２３に基づくラベル情報を読み出し、エリアＡ３内のノードに確定ラベルおよび負けラベルを付与する（ステップＳ１２１）。
【００６４】
図１６に示すように、ノードＮ２３の確定ラベルに基づくラベル情報が読み出されると、エリアＡ３内のノードＮ２３には、ノードＮ２１の確定ラベルに基づくラベルである経路コストが２０の競合ラベルＬＢ１２が付与されているため（ステップＳ１２３：ＹＥＳ）、経路探索部１２０は、ノードＮ２３の確定ラベルに基づいて付与したラベルＬＢ１３の経路コストが競合ラベルの経路コストよりも小さいか否かを判定する（ステップＳ１２５）。ラベルＬＢ１３の経路コストは、１５であり、競合ラベルＬＢ１２の経路コストの２０よりも小さいため（ステップＳ１２５：ＹＥＳ）、経路探索部１２０は、競合ラベルＬＢ１２を削除して、ラベルＬＢ１３を記憶する（ステップＳ１２９）。なお、ステップＳ１２５の処理において、ノードに新たに付与されたラベルの経路コストが同じノードに既に付与されている競合ラベルの経路コストよりも小さくないと判定された場合には（ステップＳ１２５：ＮＯ）、経路探索部１２０は、新たに付与されたラベルを削除して、引き続き、既に付与されていた競合ラベルを記憶する。以上のように、経路探索部１２０は、ステップＳ１３１の処理において、境界ノードに付与された確定ラベルに基づくラベル情報がなくなるまで、ステップＳ１２１以降の処理を繰り返す。境界ノードに付与された確定ラベルに基づくラベル情報がなくなったと判定された場合には（ステップＳ１３１：ＮＯ）、経路探索部１２０は、ラベル更新の処理を終了する。経路探索部１２０は、エリアＡ３内のエリア内経路データを用いて、エリアＡ３を経由する現在位置Ｓと目的地Ｇとを結ぶ経路を探索する。
【００６５】
以上説明したように、本実施形態におけるサーバ１００では、エリア内経路情報ＤＢ１１６は、エリアデータによって特定されるエリアに含まれる２つのノードを結ぶエリア内経路を特定する。そのため、本実施形態のサーバ１００では、現在位置と目的地とを結ぶ経路が探索される場合に、エリア内の経路については、エリア内経路を用いた探索が行なわれるため、エリアを経由する現在位置と目的地とを結ぶ経路を迅速に探索できる。また、エリアデータによって特定されるエリアには、観光地等のエリアがあり、エリア内の経路探索の処理が集中するおそれがある。その場合に、本実施形態のサーバ１００では、予めエリア内経路を特定するエリア内経路データを有することで、エリア内経路を探索するための処理時間を短縮できる。
【００６６】
また、本実施形態におけるサーバ１００では、エリア内経路情報ＤＢ１１６は、２つの境界ノードを結ぶエリア内経路を特定するエリア内経路データを記憶するため、特定のエリアを経由するエリア外の現在位置と目的地とを結ぶ経路が探索される場合に、エリア内経路が迅速に探索される。
【００６７】
また、本実施形態におけるサーバ１００では、エリア内経路は、エリア内の出発地およびエリア内目的地のノードと、エリア内経路の経路コストと、によって特定されるため、エリア内経路が探索される場合に、エリア内経路を通過するための時間が算出されるため、エリア内経路を探索するユーザの利便性が向上する。
【００６８】
また、本実施形態におけるサーバ１００では、エリア内経路は、エリア内の出発地とエリア内目的地とを結ぶ最適経路と、最適経路の経路コストに許容コストを加えた値以下の経路コストである類似経路と、を含む最適経路同等経路群である。そのため、本実施形態のサーバ１００では、エリア内を通過するのに予め定められた時間内にエリアを通過する複数の経路をユーザに提示でき、ユーザの利便性が向上する。
【００６９】
また、本実施形態におけるサーバ１００では、エリア内経路情報ＤＢ１１６に記憶されたエリア内経路データは、エリア内経路の最適経路に含まれる最適ノードに確定ラベルと負けラベルとを特定する。エリア内の出発地とエリア内目的地とを結ぶ類似経路は、エリア内の出発地のノードと最適ノードとを結ぶ負けラベルを構成するリンクと、当該最適ノードとエリア内のエリア内目的地のノードとを結ぶ最適経路と重複するリンクと、を組み合わせた経路である。そのため、本実施形態のサーバ１００では、エリア内の各ノードに付与された確定ラベルおよび負けラベルに基づいて、エリア内の出発地とエリア内目的地との組み合わせに対応して複数の類似経路を探索でき、必要最低限のデータによって、エリア内経路を探索でき、サーバ１００の容量の増加を抑制できる。
【００７０】
Ｂ．第１実施形態の変形例
Ｂ１．第１実施形態の第１の変形例：
上記第１実施形態では、経路探索処理において、現在位置ＳがエリアＡ３外のノードである場合について説明したが、第１実施形態の第１の変形例では、現在位置Ｓがエリア内のノードである場合（図１２のステップＳ１４０）について説明する。
【００７１】
図１２に示す経路探索処理において、現在位置Ｓがエリアの外のノードではないと判定された場合には（ステップＳ１０２：ＮＯ）、経路探索部１２０は、現在位置Ｓのノードを基準のノードとして、エリア内経路データによって特定されるラベルをエリア内のノードに付与してラベルを更新する（ステップＳ１４０）。
【００７２】
エリア内経路データは、上記第１実施形態では、エリア内の境界ノードの確定ラベルに基づいてノードに確定ラベルおよび負けラベルを付与したが、当該変形例では、エリア内の境界ノードと、境界ノードを含むエリア内の全ノードとを結ぶ経路のそれぞれに含まれるノードに確定ラベルおよび負けラベルを付与する。
【００７３】
図１７は、現在位置Ｓのノードを基準とするラベル更新の処理の流れを示す説明図である。このラベル更新の処理では、初めに、経路探索部１２０は、エリア内の現在位置Ｓのノードがエリア内の境界ノードであるか否かを判定する（ステップＳ１４１）。現在位置Ｓのノードが境界ノードであると判定された場合には（ステップＳ１４１：ＹＥＳ）、経路探索部１２０は、現在位置Ｓとエリア内の境界ノードのそれぞれとを結ぶ１つ以上のラベル情報を全て読み出して、エリア内のノードに確定ラベルおよび負けラベルを付与する（ステップＳ１４７）。
【００７４】
ステップＳ１４１の処理において、現在位置Ｓのノードが境界ノードではないと判定された場合には（ステップＳ１４１：ＮＯ）、経路探索部１２０は、全境界ノードに付与された確定ラベルに基づくラベル情報を呼び出し、現在位置Ｓのノードと境界ノードのそれぞれとを結ぶ経路に含まれるノードに確定ラベルおよび負けラベルを付与する（ステップＳ１４３）。
【００７５】
図１８は、エリアＡ４における現在位置Ｓ１のノードと境界ノードであるノードＮ３１とを結ぶ経路の一例を示す概略図である。図１８には、ノードＮ３１の確定ラベルに基づいて、エリアＡ４内のノードに付与されたラベルの一部が示されている。また、図１８には、現在位置Ｓ１と境界ノードとを結ぶ経路が矢印で示され、リンクＬＮ３１、リンクＬＮ３２、リンクＬＮ３３のそれぞれのリンクコストが四角で囲われた数字で示されている。また、ノードＮ３１の確定ラベルに基づいて、ノードｎ３２に経路コストが４の確定ラベルＬＢ２１と、ノードｎ３３に経路コストが９の確定ラベルＬＢ２２と、現在位置Ｓ１に経路コストが１４の確定ラベルＬＢ２３と、が示されている。図１７のステップＳ１４３が行なわれると、経路探索部１２０は、現在位置Ｓ１と境界ノードのそれぞれとを結ぶ経路に含まれるノードに付与されたラベル情報を逆方向に変換する（ステップＳ１４５）。
【００７６】
図１９は、逆方向に変換されたラベルの一例を示す概略図である。図１９には、図１８に示したノードＮ３１の確定ラベルに基づいて、ノードｎ３２、ノードｎ３３、現在位置Ｓ１に付与された確定ラベルが逆方向に変換された状態が示されている。この変形例では、経路探索部１２０は、エリアＡ４内の出発地のノードとエリア内目的地のノードとを、経路コストを含めて反対にすることで、ラベルを逆方向に変換する。図１９に示すように、各ノードに付与されたラベルが逆方向に変換されると、ノードＮ３１の確定ラベルに基づいて各ノードに付与されたラベルは、現在位置Ｓ１に付与された経路コストが０の確定ラベルＬＢ３０に基づいて各ノードに付与される。
【００７７】
以上のように、エリアＡ４内のノードに付与されたラベルが逆方向に変換された場合（図１７のステップＳ１４５）、または、ステップＳ１４７の処理が行なわれた場合には、経路探索部１２０は、第１実施形態の図１４に示すラベル更新の処理と同様の処理を行ない、現在位置のノードを基準とするラベル更新の処理を終了する。
【００７８】
以上説明したように、第１実施形態の第１の変形例では、エリア内経路データが特定するエリア内経路の出発地とエリア内目的地との一方が境界ノードである。そのため、この変形例では、経路探索処理における現在位置または目的地がエリア内のノードであっても、特定されたエリア内経路によって、簡便にエリア内経路を探索でき、現在位置と目的地とを結ぶ経路を迅速に探索できる。
【００７９】
Ｂ２．第１実施形態の第２の変形例：
エリア内経路データは、上記第１実施形態では、エリア内の境界ノードの確定ラベルに基づいてノードに確定ラベルおよび負けラベルを付与したが、この変形例では、エリア内の境界ノード以外の２つのノード結ぶ経路のそれぞれに含まれるノードに確定ラベルおよび負けラベルを付与する。
【００８０】
例えば、上記第１実施形態では、図２および図３に示すように、エリアＡ１のエリア内経路データは、境界ノードであるノードＮ１とノードＮ６とを両端点とする経路を特定するために、エリアＡ１内のノードに付与されたラベルを用いる。図２に示すように、エリアＡ１内の境界ノードは、ノードＮ１およびノードＮ６のみである。そのため、エリアＡ１内のノードに、図２に示す以外のラベルは付与されていない。それに対し、この変形例では、エリアＡ１内の境界ノードを含む全てノードの内の任意の２つのノードを結ぶ経路に基づいて、各ノードにラベルが付与される。例えば、境界ノードではないノードＮ２とノードＮ３とを結ぶ経路に基づいて、エリアＡ１内のノードに各ラベルが付与される。
【００８１】
上記第１実施形態の経路探索処理において、現在位置のノードがエリアに含まれるノードであると判定された場合に（図１２のステップＳ１０２：ＮＯ）、図１７に示すラベル更新の処理が行なわれる。この変形例の場合、現在位置のノードが境界ノードではないと判定された場合に（図１７のステップＳ１４１：ＮＯ）、経路探索部１２０は、ステップＳ１４３、ステップＳ１４５、ステップＳ１４９の処理に代えて、基準のノードを現在位置とするラベル情報を読み出し、エリア内経路データによって特定される確定ラベルおよび負けラベルをノードのそれぞれに付与する。その後、第１実施形態の第１の変形例と同じように、ステップＳ１５１以降の処理が行なわれる。
【００８２】
以上説明したように、この変形例では、エリア内の任意の２つのノードを結ぶ経路の全てに基づくラベル情報が記憶されているため、経路探索によって探索される現在位置及び目的地の両方がエリア内の境界ノード以外のノードであっても、当該ノードを基準とするエリア内経路が予め特定されているため、経路を迅速に探索できる。
【００８３】
Ｃ．第２実施形態：
経路探索処理において、エリア外の経路を探索する場合にも、上記実施形態では、ノードに確定ラベルおよび負けラベルが付与されて、現在位置と目的地とを結ぶ最適経路同等経路群が探索されたが、第２実施形態では、エリア外のノードに負けラベルが付与されずに、いわゆるダイクストラ法によってエリア外の経路が探索される。第２実施形態では、エリア外にある現在位置と、エリア外にある目的地と、のそれぞれのノードから探索枝を伸ばす双方向ダイクストラ法によって、経路探索が行なわれる。第２実施形態では、経路探索部１２０および最適経路探索部１２３は、現在位置と目的地とを結ぶ最適経路を探索した後に、全ての候補ラベルの経路コストが、最適経路の経路コストに対して１．２倍した値（１２０パーセント）を超えるまで、ダイクストラ法によって探索枝を伸ばす。
【００８４】
図２０から図２２までの各図は、第２実施形態における現在位置Ｓと目的地Ｇとを結ぶ経路の概略図である。図２０には、双方向ダイクストラ法によって、現在位置Ｓおよび目的地Ｇのそれぞれから探索枝が伸ばされ、エリアＡ３内の境界ノードに探索枝が到達した状態の一例が示されている。図２０に示すように、現在位置Ｓを起点とする探索枝は、エリアＡ３の境界ノードであるノードＮ２１に到達し、目的地Ｇを基点とする探索枝は、エリアＡ３の境界ノードであるノードＮ２４に到達している。
【００８５】
図２１には、エリアＡ３内の境界ノードであるノードＮ２１およびノードＮ２４に確定ラベルが付与された後に、ノードＮ２１とノードＮ２４とを結ぶエリア内経路が探索された状態が示されている。図２１に示すように、エリア内経路データによって、エリアＡ３内のノードＮ２１とノードＮ２４とを結ぶ最適経路同等経路群として、最適経路Ｒ１１と類似経路Ｒ１２と類似経路Ｒ１３とが特定される。第２実施形態では、エリアＡ３内の境界ノードに確定ラベルが付与されると、経路探索部１２０は、境界ノードに付与された確定ラベルに基づいて、エリアＡ３外のノードにはラベルを付与するが、エリアＡ３内のノードにはラベルを付与しない。そのため、上記実施形態と同様に、エリアＡ３内のエリア内経路は、エリア内経路データによって特定される。
【００８６】
図２２には、現在位置Ｓと目的地Ｇとを結ぶ最適経路同等経路群が示されている。図２２に示すように、第２実施形態において探索された最適経路同等経路群は、エリアＡ３内のリンクを通過しない最適経路Ｒ３１と、エリアＡ３内にノードＮ２１から入ってノードＮ２４から出る経路Ｒ３２と、エリアＡ３内にノードＮ２３から入ってノードＮ２４から出る経路Ｒ３４と、である。また、経路Ｒ３２のエリアＡ３内における類似経路として経路Ｒ３３があり、経路Ｒ３４のエリアＡ３内における類似経路として経路Ｒ３５がある。
【００８７】
Ｄ．変形例：
なお、この発明は上記実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様において実施することが可能であり、例えば、次のような変形も可能である。
【００８８】
Ｄ１．変形例１：
上記実施形態では、特定されるエリア内経路の出発地とエリア内目的地との少なくとも一方がエリア内の境界ノードであったが、必ずしも、出発地またはエリア内目的地は、境界ノードである必要はなく、種々変形可能である。例えば、エリア内の境界ノード以外の２つのノードを結ぶ経路がエリア内経路として特定されてもよい。
【００８９】
上記実施形態では、エリア内経路を構成するリンクを特定するラベルと、エリア内経路の経路コストと、によってエリア内経路が特定されたが、エリア内経路を特定する方法については、これに限られず、種々変形可能である。例えば、エリア内の２つの境界ノードが選択されると、選択された２つの境界ノードの組み合わせに応じて、経路コスト等にかかわらず、２つの境界ノードを結ぶ複数のリンクから構成される経路が特定されてもよい。
【００９０】
上記実施形態では、エリア内経路データは、ノードに付与された確定ラベルおよび負けラベルに基づいて作成された最適経路同等経路群であったが、これに限られず、種々変形可能である。例えば、エリア内経路データは、ダイクストラ法によって特定されたエリア内経路を特定してもよい。
【００９１】
Ｄ２．変形例２：
上記第２実施形態では、エリア外の経路が双方向ダイクストラ法によって探索され、現在位置Ｓから伸ばした探索枝によって確定ラベルが付与された境界ノードと、目的地Ｇから伸ばした探索枝によって確定ラベルが付与された境界ノードと、を結ぶエリア内経路が探索されたが、エリア外の経路探索については、種々変形可能である。例えば、図２０に示すように、ノードＮ２１が目的地Ｇよりも現在位置Ｓに近い場合には、目的地Ｇから伸ばした探索枝によって確定ラベルが付与されない設定であってもよい。すなわち、エリアＡ３内の境界ノードは、現在位置Ｓと目的地Ｇとの内の近いノードからの探索枝のみによって確定ラベルが付与されてもよい。
【００９２】
また、エリア内の２つの境界ノードの組み合わせによってエリア内経路が特定されてもよい。具体的には、第２実施形態の場合には、ノードＮ２１からノードＮ２４へと向かうエリア内経路が特定されたが、その逆のノードＮ２４からノードＮ２１へと向かうエリア経路は特定されなくてもよい。すなわち、２つの境界ノードの組み合わせに対して、１つのエリア内経路が対応する態様であってもよい。
【００９３】
Ｄ３．変形例３：
上記実施形態では、リンクを通過する時間（分）とリンクコストとが同一であったが、リンクを通過する時間とリンクコストとの関係は、これに限られず、種々変形可能である。例えば、特定されたリンクコストに対して、携帯電話機２００を介して設定されたユーザの移動手段に応じて、リンクコストが時間（例えば、分単位）に換算されてもよい。また、リンクコストは、分単位ではなく、リンクを通過する秒単位の時間であってもよい。
【００９４】
上記実施形態では、各リンクについて、向きにかかわらず、リンクコストが同じである態様であったが、各リンクの設定については、種々変形可能である。例えば、ユーザが自動車に乗車している場合には、リンクは、一方通行や右折禁止と知った規制が反映されていてもよい。また、リンクのリンクコストについても、例えば、坂道のリンクであった場合には、通過する向きに応じてリンクコストが変更されてもよい。
【００９５】
上記実施形態では、エリア内経路データの作成処理は、経路探索システム１０に含まれていないコンピュータによって行なわれたが、エリア内経路データを作成するのは、コンピュータに限られず、種々変形可能である。例えば、サーバ１００に構成された経路探索部１２０等とは異なるエリア内経路データ作成部がエリア内経路データを作成してもよい。
【００９６】
上記実施形態では、携帯電話機２００のＧＰＳユニット２０１によって現在位置Ｓが設定されたが、経路探索処理における出発地点の設定の方法については、これらに限られず、種々変形可能である。例えば、現在位置Ｓは、操作部２０６がユーザに操作されることによって設定されてもよい。また、携帯電話機２００の通話制御部２２０による音声認識によって、現在位置Ｓや目的地Ｇ等が設定されてもよい。
【００９７】
また、上記実施形態では、図１に示すようにサーバ１００が情報記憶部１１０および経路探索部１２０を備える態様としたが、情報記憶部１１０および経路探索部１２０を備える装置はこの態様に限られず、種々変形可能である。例えば、情報記憶部１１０と経路探索部１２０とは異なるサーバに備えられていてもよいし、経路探索部１２０が携帯電話機２００に搭載されていてもよい。
【００９８】
本発明は、上述の実施形態や実施例、変形例に限られるものではなく、その趣旨を逸脱しない範囲において種々の構成で実現できる。例えば、発明の概要の欄に記載した角形態中の技術的特徴に対応する実施形態、実施例、変形例中の技術的特徴は、上述の課題の一部または全部を解決するために、あるいは、上述の効果の一部または全部を達成するために、適宜、差し替えや、組み合わせを行なうことができる。また、その技術的特徴が本明細書中に必須なものとして説明されていなければ、適宜、削除できる。
【符号の説明】
【００９９】
１０…経路探索システム
１００…サーバ
１０２…通信部
１１０…情報記憶部
１１４…地図情報ＤＢ
１１５…エリア情報ＤＢ
１１６…エリア内経路情報ＤＢ
１１８…記憶装置
１２０…経路探索部
１２３…最適経路探索部
１２４…類似経路探索部
２００…携帯電話機
２０１…ＧＰＳユニット
２０２…表示パネル
２０３…音声出力部
２０５…無線通信回路
２０６…操作部
２０６ａ…テンキー
２０６ｂ…カーソルキー
２１０…主制御部
２１１…ＣＰＵ
２２０…通話制御部
３００…エリア内経路データ
Ｓ，Ｓ１…現在位置
Ｇ…目的地
ＬＮ１，ＬＮ３，ＬＮ０１，ＬＮ１１，ＬＮ１２，ＬＮ１３，ＬＮ１４，ＬＮ１５，ＬＮ１６，ＬＮ２１，Ｌ３１，Ｌ３２，Ｌ３３…リンク
ＬＢ０，ＬＢ１，ＬＢ００，ＬＢ１１，ＬＢ２１，ＬＢ２２，ＬＢ２３，ＬＢ３０…確定ラベル
ＬＢ１２…競合ラベル
ＬＢ１３…ラベル
Ａ１，Ａ２，Ａ３，Ａ４…エリア
Ｎ１，Ｎ２，Ｎ４，Ｎ６，Ｎ１１，Ｎ１２，Ｎ１３，Ｎ１４，Ｎ２１、Ｎ２２，Ｎ２３，Ｎ２４，Ｎ３１，ｎ１１，ｎ１２，ｎ１３，ｎ３２…ノード
ＢＳ…基地局
Ｒ０１，Ｒ１１，Ｒ３１…最適経路
Ｒ０２，Ｒ１２，Ｒ１３…類似経路
Ｒ３２，Ｒ３３，Ｒ３４，Ｒ３５…経路
ＩＮＴ…インターネット
【図１】
2015152383.tif 000003
【図２】
2015152383.tif 000004
【図３】
2015152383.tif 000005
【図４】
2015152383.tif 000006
【図５】
2015152383.tif 000007
【図６】
2015152383.tif 000008
【図７】
2015152383.tif 000009
【図８】
2015152383.tif 000010
【図９】
2015152383.tif 000011
【図１０】
2015152383.tif 000012
【図１１】
2015152383.tif 000013
【図１２】
2015152383.tif 000014
【図１３】
2015152383.tif 000015
【図１４】
2015152383.tif 000016
【図１５】
2015152383.tif 000017
【図１６】
2015152383.tif 000018
【図１７】
2015152383.tif 000019
【図１８】
2015152383.tif 000020
【図１９】
2015152383.tif 000021
【図２０】
2015152383.tif 000022
【図２１】
2015152383.tif 000023
【図２２】
2015152383.tif 000024