(57)【要約】【課題】他の装置に設定された出発地と目的地とに基づいて、ネットワーク上の状況をより正確に推定する技術を提供する。【解決手段】他の装置に設定された出発地と目的地とに基づいて、他の装置のユーザの移動経路として、出発地と目的地とを結ぶ１つの経路だけではなく、所定のリンクコストの累計値以下となる複数の経路を探索することで、他のユーザがネットワークに発生し得る渋滞等を回避した場合の他のユーザの通行するリンクを推定することで、より正確なネットワーク上の混雑度等の交通状態を推定する。【選択図】図１
2015165215.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上の２つのノードを結ぶ経路を探索する経路探索装置であって、
ネットワーク上の複数のノードと、複数のリンクと、前記複数のリンクのそれぞれに設定されたリンクコストと、を特定するネットワーク情報を記憶するデータ記憶部と、
少なくとも１つの他の装置に設定された出発地のノードと目的地のノードとを特定する情報を取得する情報取得部と、
前記他の装置に設定された出発地のノードと目的地のノードとを結ぶ複数の第１の移動経路の内、前記第１の移動経路を構成するリンクのリンクコストの累計値が最小である第１の最適経路の前記リンクコストの累計値と、前記第１の最適経路の前記リンクコストの累計値に第１の許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの第１の準最適経路の前記リンクコストの累計値と、に基づいて、前記データ記憶部に記憶された前記ネットワーク情報のリンクコストを調整するコスト調整部と、
出発地のノードと目的地のノードとを設定する地点設定部と、
リンクコストが調整された前記ネットワーク情報を用いて、前記地点設定部が設定した出発地のノードと目的地のノードとを結ぶ少なくとも１つの第２の移動経路を探索する経路探索部と、を備える、経路探索装置。
【請求項２】
請求項１に記載の経路探索装置であって、
前記コスト調整部は、前記第１の最適経路の前記リンクコストの累計値と前記第１の準最適経路の前記リンクコストの累計値とに基づいてリンク毎に設定される変動コストを、前記第１の最適経路と前記第１の準最適経路とを構成するリンクのリンクコストに加えることで、前記ネットワーク情報のリンクコストを調整する、経路探索装置。
【請求項３】
請求項２に記載の経路探索装置であって、
前記コスト調整部は、前記第１の準最適経路の前記リンクコストの累計値から前記第１の最適経路の前記リンクコストの累計値を差し引いた値が小さいほど前記変動コストを大きく設定する、経路探索装置。
【請求項４】
請求項１から請求項３までのいずれか一項に記載の経路探索装置であって、
前記コスト調整部は、
前記他の装置に設定された前記出発地のノードと、前記第１の最適経路に含まれるノードである第１の最適ノードと、を結ぶ第１の中途経路の内、前記第１の中途経路を構成する前記リンクコストの累計値が最小となる第１の最小コスト中途経路と、前記第１の最小コスト中途経路以外の少なくとも１つの第１の非最小コスト中途経路と、を特定し、
前記第１の中途経路のそれぞれについて、前記第１の非最小コスト中途経路と、前記第１の最適ノードと前記他の装置に設定された前記目的地のノードとを結ぶ経路において前記第１の最適経路と重複する経路と、から構成される経路を前記第１の準最適経路として設定する、経路探索装置。
【請求項５】
請求項１から請求項４までのいずれか一項に記載の経路探索装置であって、
経路探索部は、前記第２の移動経路の内、前記第２の移動経路を構成する前記リンクコストの累計値が最小である第２の最適経路と、前記第２の最適経路の前記リンクコストの累計値に第２の許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの第２の準最適経路と、を探索する、経路探索装置。
【請求項６】
請求項５に記載の経路探索装置であって、
経路探索部は、
前記地点設定部が設定した前記出発地のノードと、前記第２の最適経路に含まれるノードである第２の最適ノードと、を結ぶ第２の中途経路の内、前記第２の中途経路を構成する前記リンクコストの累計値が最小となる第２の最小コスト中途経路と、前記第２の最小コスト中途経路以外の少なくとも１つの第２の非最小コスト中途経路と、を特定し、
前記第２の中途経路のそれぞれについて、前記第２の非最小コスト中途経路と、前記第２の最適ノードと前記地点設定部が設定した目的地のノードとを結ぶ経路において前記第２の最適経路と重複する経路と、から構成される経路を前記第２の準最適経路として設定する、経路探索装置。
【請求項７】
情報処理装置であって、
ネットワーク上の複数のノードと、複数のリンクと、前記複数のリンクのそれぞれに設定されたリンクコストと、を特定するネットワーク情報を記憶するデータ記憶部と、
少なくとも１つの装置に設定された出発地のノードと目的地のノードとを特定する情報を取得する情報取得部と、
前記出発地のノードと目的地のノードとを結ぶ移動経路の内、前記移動経路を構成するリンクのリンクコストの累計値が最小である最適経路の前記リンクコストの累計値と、前記最適経路の前記リンクコストの累計値に許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの準最適経路の前記リンクコストの累計値と、に基づいて、前記データ記憶部に記憶された前記ネットワーク情報のリンクコストを調整するコスト調整部と、
リンクコストが調整された前記ネットワーク情報を表す調整経路情報を生成する調整情報生成部と、を備える、情報処理装置。
【請求項８】
請求項７に記載の情報処理装置であって、
前記調整情報生成部は、前記ネットワーク情報によって特定されるリンクコストと、調整されたリンクコストと、を区別して表すように前記調整経路情報を生成する、情報処理装置。
【請求項９】
ネットワーク上の複数のノードと、複数のリンクと、前記複数のリンクのそれぞれに設定されたリンクコストと、を特定するネットワーク情報を記憶するデータ記憶部を備える記憶装置を用いて、ネットワーク上の２つのノードを結ぶ経路を探索する経路探索方法であって、
少なくとも１つの他の装置に設定された出発地のノードと目的地のノードとを特定する情報を取得する工程と、
前記他の装置に設定された出発地のノードと目的地のノードとを結ぶ複数の第１の移動経路の内、前記第１の移動経路を構成するリンクのリンクコストの累計値が最小である第１の最適経路の前記リンクコストの累計値と、前記第１の最適経路の前記リンクコストの累計値に第１の許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの第１の準最適経路の前記リンクコストの累計値と、に基づいて、前記データ記憶部に記憶された前記ネットワーク情報のリンクコストを調整する工程と、
出発地のノードと目的地のノードとを設定する工程と、
リンクコストが調整された前記ネットワーク情報を用いて、設定された出発地のノードと目的地のノードとを結ぶ少なくとも１つの第２の移動経路を探索する工程と、を備える、経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置に関する。
【背景技術】
【０００２】
現在位置から目的地までの経路を探索する経路探索装置として、自動車に搭載されたカーナビゲーションシステム、携帯電話機、携帯ゲーム機、ＰＮＤ（Personal Navigation Device）およびＰＤＡ（Personal Digital Assistant）が知られている。
【０００３】
例えば、特許文献１に記載されているように、自動車の現在位置と目的地とを結ぶ経路が探索される際に、他の自動車が現時点で位置する道路としてのリンクや他の自動車における現在位置から目的地までの経路を構成するリンクなどの交通状況が考慮されることで、渋滞を緩和させる交通管理装置が知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２１０２８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載された技術では、経路案内によって探索された現在位置から出発地までの移動経路に沿って走行していた自動車が、次に進行予定のリンクが渋滞していたときに、次のリンクでの渋滞を回避するために、移動経路を構成するリンクとは異なるリンクに進行する場合がある。複数の自動車が、このように移動経路を構成するリンクとは異なるリンクを進行してしまうと、交通状況を正確に予測できず、自動車の渋滞を十分に緩和させることができないおそれがあった。また、これらの課題は、経路探索装置に限られず、交通状況を把握するための情報処理装置等にも共通する課題であった。そのほか、経路探索装置および情報処理装置では、交通状況を正確にユーザに把握させるために、ユーザにとっての利便性や使い勝手の向上が望まれていた。
【課題を解決するための手段】
【０００６】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態として実現できる。
【０００７】
（１）本発明の一形態によれば、ネットワーク上の２つのノードを結ぶ経路を探索する経路探索装置が提供される。この経路探索装置は、ネットワーク上の複数のノードと、複数のリンクと、前記複数のリンクのそれぞれに設定されたリンクコストと、を特定するネットワーク情報を記憶するデータ記憶部と；少なくとも１つの他の装置に設定された出発地のノードと目的地のノードとを特定する情報を取得する情報取得部と；前記他の装置に設定された出発地のノードと目的地のノードとを結ぶ複数の第１の移動経路の内、前記第１の移動経路を構成するリンクのリンクコストの累計値が最小である第１の最適経路の前記リンクコストの累計値と、前記第１の最適経路の前記リンクコストの累計値に第１の許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの第１の準最適経路の前記リンクコストの累計値と、に基づいて、前記データ記憶部に記憶された前記ネットワーク情報のリンクコストを調整するコスト調整部と；出発地のノードと目的地のノードとを設定する地点設定部と；リンクコストが調整された前記ネットワーク情報を用いて、前記地点設定部が設定した出発地のノードと目的地のノードとを結ぶ少なくとも１つの第２の移動経路を探索する経路探索部と、を備える。この形態の経路探索装置によれば、他の装置に設定された第１の移動経路の内の第１の最適経路以外の第１の準最適経路を他のユーザが通行した場合も加味した上で、出発地と目的地とを結ぶ第２の移動経路が探索される。そのため、経路探索装置のユーザは、他のユーザの通行するリンクを踏まえて、ネットワーク上に発生する渋滞を回避して目的地に到着できる。
【０００８】
（２）上記形態の経路探索装置において、前記コスト調整部は、前記第１の最適経路の前記リンクコストの累計値と前記第１の準最適経路の前記リンクコストの累計値とに基づいてリンク毎に設定される変動コストを、前記第１の最適経路と前記第１の準最適経路とを構成するリンクのリンクコストに加えることで、前記ネットワーク情報のリンクコストを調整してもよい。この形態の経路探索装置によれば、他の装置に設定された１つの第１の移動経路のみではなく、第１の最適経路の経路コストと第１の準最適経路とを踏まえて、変動コストが算出される。よって、他の装置のユーザが、次に通行予定のリンクの混雑度を見て、経路を変更した場合などの状況を予測した上で、経路探索装置のユーザの第２の移動経路が探索されるため、経路探索装置のユーザは、より迅速に目的地に到着でき、また、ユーザにとっての利便性が向上する。
【０００９】
（３）上記形態の経路探索装置において、前記コスト調整部は、前記第１の準最適経路の前記リンクコストの累計値から前記第１の最適経路の前記リンクコストの累計値を差し引いた値が小さいほど前記変動コストを大きく設定してもよい。この形態の経路探索装置によれば、他の装置のユーザが通行する可能性が高いと推定されるリンクほど変動コストが大きく算出されるため、実際の推定される混雑度により則した状況に基づいて、経路探索装置のユーザの第２の移動経路を探索できる。
【００１０】
（４）上記形態の経路探索装置において、前記コスト調整部は；前記他の装置に設定された前記出発地のノードと、前記第１の最適経路に含まれるノードである第１の最適ノードと、を結ぶ第１の中途経路の内、前記第１の中途経路を構成する前記リンクコストの累計値が最小となる第１の最小コスト中途経路と、前記第１の最小コスト中途経路以外の少なくとも１つの第１の非最小コスト中途経路と、を特定し；前記第１の中途経路のそれぞれについて、前記第１の非最小コスト中途経路と、前記第１の最適ノードと前記他の装置に設定された前記目的地のノードとを結ぶ経路において前記第１の最適経路と重複する経路と、から構成される経路を前記第１の準最適経路として設定してもよい。この形態の経路探索装置によれば、他の装置に設定された出発地と目的地とを特定する情報のみ取得されれば、第１の移動経路が推定でき、他の装置に設定されたより少ない経路情報であっても、第２の移動経路を探索できる。
【００１１】
（５）上記形態の経路探索装置において、経路探索部は、前記第２の移動経路の内、前記第１の移動経路を構成する前記リンクコストの累計値が最小である第２の最適経路と、前記第２の最適経路の前記リンクコストの累計値に第２の許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの第２の準最適経路と、を探索してもよい。この形態の経路探索装置によれば、所定のリンクコストの累計値以下の範囲で複数の第２の移動経路が探索されるため、経路探索装置のユーザは複数の第２の移動経路から好みの経路を選択でき、ユーザにとっての利便性が向上する。
【００１２】
（６）上記形態の経路探索装置において、経路探索部は；前記地点設定部が設定した前記出発地のノードと、前記第２の最適経路に含まれるノードである第２の最適ノードと、を結ぶ第２の中途経路の内、前記第２の中途経路を構成する前記リンクコストの累計値が最小となる第２の最小コスト中途経路と、前記第２の最小コスト中途経路以外の少なくとも１つの第２の非最小コスト中途経路と、を特定し；前記第２の中途経路のそれぞれについて、前記第２の非最小コスト中途経路と、前記第２の最適ノードと前記地点設定部が設定した目的地のノードとを結ぶ経路において前記第２の最適経路と重複する経路と、から構成される経路を前記第２の準最適経路として設定してもよい。この形態の経路探索装置によれば、第２の準最適経路を探索する場合に、出発地から目的地までの経路をいちいち探索せずに、第２の最適ノードにおける第２の最小コスト中途経路と第２の非最小コスト中途経路とに基づいて探索できるため、第２の移動経路の探索を迅速に行なうことができ、経路探索装置の処理の負荷を低減できる。
【００１３】
（７）本発明の他の形態によれば、情報処理装置が提供される。この情報処理装置は、ネットワーク上の複数のノードと、複数のリンクと、前記複数のリンクのそれぞれに設定されたリンクコストと、を特定するネットワーク情報を記憶するデータ記憶部と；少なくとも１つの装置に設定された出発地のノードと目的地のノードとを特定する情報を取得する情報取得部と；前記出発地のノードと目的地のノードとを結ぶ移動経路の内、前記移動経路を構成するリンクのリンクコストの累計値が最小である最適経路の前記リンクコストの累計値と、前記最適経路の前記リンクコストの累計値に許容コストを加えた値以下の前記リンクコストの累計値を有する少なくとも１つの準最適経路の前記リンクコストの累計値と、に基づいて、前記データ記憶部に記憶された前記ネットワーク情報のリンクコストを調整するコスト調整部と；リンクコストが調整された前記ネットワーク情報を表す調整経路情報を生成する調整情報生成部と、を備える。この形態の情報処理装置によれば、他の装置に設定された情報に基づく移動経路において、最適経路と準最適経路とが探索されてリンクコストが調整される。よって、調整されたリンクコストは、従来技術と比べて、局所的に高い値にはならず、局所的な渋滞の発生を抑制する。また、調整経路情報が生成されることで、ユーザは、一目してネットワーク上の混雑度を把握でき、渋滞等を回避した経路を通行でき、ユーザにとっての利便性が向上する。
【００１４】
（８）上記形態の情報処理装置において、前記調整情報生成部は、前記ネットワーク情報によって特定されるリンクコストと、調整されたリンクコストと、を区別して表すように前記調整経路情報を生成してもよい。この形態の情報処理装置によれば、ユーザは、混雑していない場合に比べて、リンクがどの程度混雑しているかを視認できるため、容易に交通状況を認識でき、ユーザにとっての利便性が向上する。
【００１５】
（９）上記形態の情報処理装置において、前記コスト調整部は、前記最適経路の前記リンクコストの累計値と前記準最適経路の前記リンクコストの累計値とに基づいてリンク毎に設定される変動コストを、前記最適経路と前記準最適経路とを構成するリンクのリンクコストに加えることで、前記ネットワーク情報のリンクコストを調整してもよい。この形態の情報処理装置によれば、少なくとも１つの装置に設定された１つの移動経路のみではなく、最適経路の経路コストと準最適経路とを踏まえて、変動コストが算出される。よって、出発地と目的地とを設定したユーザが、次に通行予定のリンクの混雑度を見て、経路を変更した場合などの状況を予測した上で、ネットワーク上の混雑度を考慮した調整経路情報が生成されるため、情報処理装置のユーザは、混雑度を回避した経路を選択することで迅速に目的地に到着でき、また、ユーザにとっての利便性が向上する。
【００１６】
（１０）上記形態の情報処理装置において、前記コスト調整部は、前記準最適経路の前記リンクコストの累計値から前記最適経路の前記リンクコストの累計値を差し引いた値が小さいほど前記変動コストを大きく設定してもよい。この形態の情報処理装置によれば、少なくとも１つの装置のユーザが通行する可能性が高いと推定されるリンクほど変動コストが大きく算出されるため、実際の推定される混雑度により則した状況に基づいて調整経路情報が生成されるため、情報処理装置のユーザは、混雑度を回避することでより迅速に目的地に到着でき、また、ユーザにとっての利便性がより向上する。
【００１７】
（１１）上記形態の情報処理装置において、前記調整情報生成部は、前記ネットワーク情報によって特定されるリンクコストと、前記変動コストと、を区別すると共に、前記変動コストを加えるリンクを特定して表すように前記調整経路情報を生成してもよい。この形態の情報処理装置によれば、ユーザは、どのリンクがどの程度の変動コストが加えられているかを視認できるため、より容易に交通状況を認識でき、ユーザにとっての利便性がより向上する。
【００１８】
（１２）上記形態の情報処理装置において、前記コスト調整部は；前記出発地のノードと、前記最適経路に含まれるノードである最適ノードと、を結ぶ中途経路の内、前記中途経路を構成する前記リンクコストの累計値が最小である１つの最小コス中途経路と、前記最小コスト中途経路以外の非最小コスト中途経路と、を特定し；前記中途経路のそれぞれについて、前記非最小コスト中途経路と、前記最適ノードと前記目的地のノードとを結ぶ経路において前記最適経路と重複する経路と、から構成される経路を前記準最適経路として設定してもよい。この形態の情報処理装置によれば、少なくとも１つの装置に設定された出発地と目的地とを特定する情報のみ取得されれば、移動経路が推定でき、より少ない経路情報によってネットワーク上の混雑度を推定できる。
【００１９】
なお、本発明は、種々の態様で実現することが可能であり、例えば、経路探索装置、経路探索方法、情報処理装置、情報端末装置、情報送信装置、情報送信方法、携帯端末装置、情報処理サーバ、経路探索サーバ、これらの装置、方法、システムを実現するためのコンピュータプログラム等の形態で実現できる。また、これらのコンピュータプログラムは、コンピュータが読取可能な記録媒体（例えば、フレキシブルディスクやＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、光磁気ディスク、メモリカード、ハードディスク等）に記録されていてもよい。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施形態における経路探索システムの概略構成を示す説明図である。
【図２】経路探索処理の流れを示す説明図である。
【図３】出発地と目的地とを結ぶ移動経路を示す説明図である。
【図４】リンクにおける変動コストと変動コストを算出するための各種指標値との関係を示す説明図である。
【図５】変動コストデータの作成処理の流れを示す説明図である。
【図６】出発地と目的地とを含むネットワーク情報の一部を示す説明図である。
【図７】他のユーザに設定された出発地と目的地とを結ぶ移動経路の一例を示す説明図である。
【図８】出発地と目的地とを結ぶ移動経路に含まれる対象リンクに加えられる変動コストの一例を示す説明図である。
【図９】他のユーザに設定された出発地と目的地とを結ぶ移動経路を示す説明図である。
【図１０】出発地と目的地とを結ぶ移動経路に含まれる対象リンクに加えられる変動コストの一例を示す説明図である。
【図１１】変動コストが加えられたリンクコストを示すネットワーク情報の一例を示す説明図である。
【図１２】出発地と目的地とを結ぶ移動経路に含まれる対象リンクに加えられる変動コストを示す説明図である。
【図１３】他のユーザに設定された出発地と目的地とを結ぶ移動経路の一例を示す説明図である。
【図１４】出発地と目的地とを結ぶ移動経路に含まれる対象リンクに加えられる変動コストの一例を示す説明図である。
【図１５】移動経路群の探索処理の流れを示す説明図である。
【図１６】ラベルの付与処理の流れを示す説明図である。
【図１７】ラベルの付与処理の流れを示す説明図である。
【図１８】出発地のノードに候補ラベルが付与された状態を示す説明図である。
【図１９】確定ラベルのラベルが付与された出発地の隣接ノードに新しいラベルが付与された状態を示す説明図である。
【図２０】確定ラベルのラベルが付与されたノードの隣接ノードに新しいラベルが付与された状態を示す説明図である。
【図２１】確定ラベルのラベルが付与されたノードの隣接ノードに新しいラベルが付与された状態を示す説明図である。
【図２２】目的地に付与された確定ラベルのラベルに基づいて目的地の隣接ノードに新しいラベルが付与された状態を示す説明図である。
【図２３】ネットワーク上のノードに付与された候補ラベルがなくなった状態の一例を示す説明図である。
【図２４】ネットワーク上のノードに付与された確定ラベルおよび負けラベルのそれぞれについての経路コストと直前ラベルとの関係を一覧で示す説明図である。
【図２５】ネットワーク上のノードに付与された確定ラベルおよび負けラベルのそれぞれについての経路コストと直前ラベルとの関係を一覧で示す説明図である。
【図２６】出発地と目的地とを結ぶ最適経路の一例を示す説明図である。
【図２７】類似経路群の探索処理の流れを示す説明図である。
【図２８】探索された類似経路群の一例を示す説明図である。
【図２９】第２実施形態におけるネットワーク上のリンクの推定される混雑度の一例を示す概略図である。
【図３０】比較例におけるネットワーク上のリンクの推定される混雑度の一例を示す説明図である。
【発明を実施するための形態】
【００２１】
次に、本発明の実施形態を以下の順序で説明する。
Ａ．第１実施形態：
Ａ−１．経路探索システムの構成：
Ａ−２．経路探索処理：
Ａ−３．変動コストデータの作成処理：
Ａ−４．移動経路群の探索処理：
Ｂ．第２実施形態：
Ｃ．変形例：
【００２２】
Ａ．第１実施形態：
Ａ−１．経路探索システムの構成：
図１は、本発明の実施形態における経路探索システム１０の概略構成を示す説明図である。本実施形態の経路探索システム１０は、サーバ１００と携帯端末装置としての携帯電話機２００とを備えている。図１には、携帯電話機２００を１台のみ示しているが、経路探索システム１０には、複数の携帯電話機２００および携帯ゲーム機、ＰＮＤ（Personal Navigation Device）、ＰＤＡ（Personal Digital Assistant）といった様々な携帯端末装置が含まれ得る。
【００２３】
携帯電話機２００は、主制御部２１０と、ＧＰＳユニット２０１と、表示パネル２０２と、音声出力部２０３と、無線通信回路２０５と、操作部２０６と、通話制御部２２０と、を備えている。
【００２４】
主制御部２１０は、携帯電話機２００の各部を制御する。主制御部２１０は、ＣＰＵ２１１と、ＲＡＭ２１２と、ＲＯＭ２１３とを備えている。ＣＰＵ２１１は、ＲＯＭ２１３に記憶されたプログラムをＲＡＭ２１２にロードして実行することで、後述する種々の処理を実行するために機能する。
【００２５】
ＧＰＳユニット２０１は、ＧＰＳ（Global Positioning System／全地球測位システム）から人工衛星の位置を示す電波を受信する。主制御部２１０は、ＧＰＳユニット２０１が受信した人工衛星の位置を用いて、携帯電話機２００の現在位置（緯度、経度）を特定し、一定時間ごとに特定した携帯電話機２００の現在位置を示す位置情報を生成する。
【００２６】
表示パネル２０２は、液晶ディスプレイと液晶ディスプレイを駆動する駆動回路とを備えている。表示パネル２０２としては、液晶ディスプレイに限らず、有機ＥＬディスプレイなど、種々の表示デバイスを採用できる。主制御部２１０は、表示パネル２０２を制御することで、例えば、地図画像や推奨経路、現在位置などを表示する。音声出力部２０３は、音声を出力するためのスピーカーや、スピーカーを駆動する駆動回路などから構成される。
【００２７】
無線通信回路２０５は、基地局ＢＳとの間でデータ通信もしくは音声通信を無線によって行なう。主制御部２１０は、無線通信回路２０５を制御することで、基地局ＢＳを介して（より詳細には、送受信アンテナ、基地局ＢＳ、交換局を介して）、インターネットＩＮＴ上のサーバ１００と通信する。
【００２８】
操作部２０６は、テンキー２０６ａやカーソルキー２０６ｂやタッチパネルなどから構成される入力デバイスである。操作部２０６は、ユーザによる目的地の設定入力等を受け付ける。操作部２０６が受け付けた目的地の設定やＧＰＳユニット２０１によって生成された位置情報は、インターネットＩＮＴを介して、サーバ１００に送信される。通話制御部２２０は、音声通話のための着信や呼出、音声信号と電気信号の変換などを行なう。
【００２９】
サーバ１００は、インターネットＩＮＴを介して携帯電話機２００との通信を行なう通信部１０２と、制御部１５０と、情報記憶部１１０と、を備えている。情報記憶部１１０は、情報を記憶する記憶装置であり、例えば、ハードディスク装置により構成されている。情報記憶部１１０は、地図情報データベース（ＤＢ）１１４と、交通情報データベース（ＤＢ）１１５と、を含んでいる。地図情報ＤＢ１１４は、地図上のネットワークを構成するリンク情報およびノード情報であるネットワーク情報と、画像データとしての地図画像データと、を記憶している。地図情報ＤＢ１１４は、リンク情報として、ユーザがリンクを通過する際に要する時間をリンクコストとして記憶している。なお、リンクのリンクコストは、当該リンクを通過するための時間（分）として設定されている。
【００３０】
交通情報ＤＢ１１５は、制御部１５０が通信部１０２を介して受信した複数の携帯電話機２００等のそれぞれから送信された携帯電話機２００に設定された出発地と目的地とを含む経路情報を記憶する。経路情報としては、出発地としての現在位置および目的地を特定する情報や、出発地と目的地とを結ぶ移動経路の情報を含む。また、経路情報は、現時点よりも未来の特定の時点（例えば、予定された旅行時）における情報を含む。交通情報ＤＢ１１５は、地図情報ＤＢ１１４のネットワーク情報と複数の携帯電話機２００の経路情報とに基づいて、いつの時点でどこのリンクにどの程度のユーザがいるかの交通情報を記憶する。すなわち、交通情報ＤＢ１１５に記憶された交通情報を用いることで、特定のリンクに存在するユーザの数を特定したり、設定された移動経路に基づいてユーザの未来の位置を推定することで、リンクの混雑度等を判定できる。なお、本実施形態におけるサーバ１００は、請求項における経路探索装置に相当し、情報記憶部１１０は、請求項におけるデータ記憶部に相当する。また、地図情報ＤＢ１１４に記憶されたネットワーク情報は、請求項におけるネットワーク情報に相当する。
【００３１】
制御部１５０は、ＣＰＵやＲＡＭ、ＲＯＭにより構成されており、通信部１０２と情報記憶部１１０とを制御する。制御部１５０は、経路探索部１２０と、コスト調整部１３０と、を備えている。経路探索部１２０は、ユーザによって携帯電話機２００に目的地と目的地に到着する到着時刻とが設定されると、到着時刻までに目的地に到着できる範囲で、携帯電話機２００の現在位置と設定された目的地とを結ぶ移動経路を探索する。経路探索の詳細については、後述する。なお、経路探索部１２０は、請求項における経路探索部および地点設定部に相当する。
【００３２】
図１に示すように、経路探索部１２０は、最適経路探索部１２３と、類似経路探索部１２４と、を備えている。最適経路探索部１２３は、地図情報ＤＢ１１４に記憶してあるネットワーク情報および後述するコスト調整部１３０が記憶するリンクコスト情報と、受信した位置情報および目的地情報と、に基づいて、最適経路を探索する。最適経路は、移動経路を構成する各リンクのリンクコストを足し合わせたリンクコストの累計値が最小となる経路である。なお、以下では、経路を構成するリンクのリンクコストの累計値を「経路コスト」とも呼ぶ。
【００３３】
類似経路探索部１２４は、ネットワーク情報とリンクコスト情報と最適経路の経路コストとに基づいて、設定された許容コストを最適経路の経路コストに加算した経路コスト以下となる移動経路である類似経路を探索する。許容コストは、到着時刻から現在時刻を差し引いた時間であったり、ユーザの操作によって設定される任意の値である。経路探索部１２０は、通信部１０２を介して、携帯電話機２００に最適経路と類似経路と示す経路情報を送信する。最適経路と類似経路との探索の詳細については、後述する。なお、経路探索部１２０によって探索される出発地と目的地とを結ぶ移動経路は、請求項における第２の移動経路に相当する。最適経路探索部１２３によって探索される最適経路は、請求項における第２の最適経路に相当する。類似経路探索部１２４によって探索される類似経路は、請求項における第２の準最適経路に相当する。また、ユーザの操作等によって設定される許容コストは、請求項における第２の許容コストに相当する。
【００３４】
コスト調整部１３０は、変動コスト算出部１３５と、リンクコスト情報データベース（ＤＢ）１３６と、を備えている。変動コスト算出部１３５は、交通情報ＤＢ１１５によって特定される交通情報に基づいて、地図情報ＤＢ１１４によって特定される一部のリンクのリンクコストに加える変動コストのそれぞれを算出する。リンクコスト情報ＤＢ１３６は、変動コスト算出部１３５によって算出された変動コストを、対応するリンクのリンクコストのそれぞれに加えることでリンクコストを調整し、地図情報ＤＢ１１４のネットワーク情報に基づいて、探索用ネットワーク情報を生成する。また、リンクコスト情報ＤＢ１３６は、インターネットＩＮＴを介して、生成した探索用ネットワーク情報を、ユーザに認識しやすい交通情報のデータに変換して携帯電話機２００に送信する。携帯電話機２００は、送信された探索用ネットワーク情報を表示パネル２０２や音声出力部２０３を用いて、ユーザに認識させる。なお、コスト調整部１３０は、請求項におけるコスト調整部および調整情報生成部に相当する。また、ユーザに認識させるための探索用ネットワーク情報の詳細については、第２実施形態で後述する。
【００３５】
Ａ−２．経路探索処理：
図２は、経路探索処理の流れを示す説明図である。経路探索処理は、複数の他のユーザの携帯電話機２００に設定された経路情報を用いて、設定された出発地のノードと目的地のノードとを結ぶ移動経路を探索する処理である。経路探索処理では、初めに、サーバ１００の経路探索部１２０は、携帯電話機２００によって設定された出発地および目的地を特定する情報を取得する（ステップＳ１０）。本実施形態では、ＧＰＳユニット２０１によって取得された携帯電話機２００の現在位置が出発地として設定され、操作部２０６がユーザによって操作されることで目的地が設定される。
【００３６】
次に、サーバ１００のコスト調整部１３０は、設定された出発地と目的地とに基づいて、変動コストを加える対象のリンクである対象リンクを選択し、対象リンクを移動経路に含む他のユーザの経路情報を取得する（ステップＳ１２）。本実施形態では、コスト調整部１３０は、設定された目的地から所定の距離に含まれるリンクを対象リンクとして設定し、移動経路に対象リンクを含む他のユーザの経路情報を交通情報ＤＢ１１５から取得する。
【００３７】
次に、コスト調整部１３０は、取得された他のユーザの経路情報を用いて、ネットワーク情報によって特定されたリンクのリンクコストに加える変動コストを特定する変動コストデータを作成する（ステップＳ２０）。変動コストデータの作成処理については、後述する。変動コストデータが作成されると、経路探索部１２０は、変動コストデータを用いて作成された探索用ネットワーク情報を用いて、１つ以上の経路である移動経路である移動経路群を探索する（ステップＳ４０）。移動経路群の探索処理については、後述する。
【００３８】
Ａ−３．変動コストデータの作成処理：
変動コストデータは、他のユーザの移動経路に基づいて、対象リンクのそれぞれのリンクコストに加えられる変動コストを特定するデータである。初めに、変動コストの算出方法について説明する。
【００３９】
図３は、出発地Ｓ１と目的地ＧＬとを結ぶ移動経路を示す説明図である。図３には、出発地Ｓ１と目的地ＧＬとを結ぶ３つの経路Ｒ１１、Ｒ１２、Ｒ１３が示されている。また、図３には、３つの経路を構成するリンクのリンクコストが四角で囲われた数値で示されている。ここでは、経路Ｒ１１および経路Ｒ１２を構成する出発地Ｓ１とノードＮ１１とを接続するリンクＬ０１に加える変動コストの算出方法について説明する。
【００４０】
図４は、リンクＬＮ０１における変動コストと変動コストを算出するための各種指標値との関係を示す説明図である。図４に示すように、１つのリンクに加えられる変動コストは、ネットワーク情報に記憶されたリンクのリンクコストと、リンクを通行する可能性を表す通行可能性の指標値と、リンクにおける混雑度を表す人数係数と、を乗じて算出される。すなわち、変動コストは、他のユーザが通行する可能性が低いリンクでは小さい値となり、リンクが混雑している場合には大きな値となる。このようにすれば、経路探索の際に、混雑しているリンクを回避した経路をユーザに提示できる。また、他のユーザが通行する可能性が低いリンクは、他のユーザが通行する可能性が高いリンクに比べて、移動経路を構成するリンクとして探索されやすくなる。通行可能性は、コスト差許容値から対象リンクを含む経路の経路コスト差を差し引いた値の二乗を、経路コスト差の二乗の和で序すことによって算出される。経路コスト差は、最適経路の経路コストから、対象リンクを含む経路の経路コストを差し引いた値である。
【００４１】
例えば、図３に示す例では、出発地Ｓ１と目的地ＧＬとを結ぶ経路の内、経路コストが最小となる最適経路は、経路コストが１５の経路Ｒ１１である。ここで、対象リンクをリンクＬＮ０１に設定すると、リンクＬＮ０１は、経路Ｒ１１および経路Ｒ１２を構成するリンクである。経路Ｒ１２は、出発地Ｓ１と目的地ＧＬとを結ぶ経路コストが１６の類似経路である。１つの対象リンクが２つの経路に含まれる場合には、経路コストが小さい方の経路に含まれるものとして変動コストが算出される。すなわち、対象リンクであるリンクＬＮ０１の変動コストは、最適経路の経路Ｒ１１を構成するリンクとして算出される。この場合に、図４に示すように、経路コスト差は、経路Ｒ１１の経路コストの１５から、最適経路である同じ経路Ｒ１１の経路コストの１５を差し引いた値の０となる。また、経路コスト差の二乗は、同じく０となる。
【００４２】
経路コスト差の二乗の和は、設定されたコスト差許容値以下の整数の二乗の和である。具体的には、図３および図４に示す例では、コスト差許容値が３に設定されている。そのため、コスト差許容値の３から経路コスト差の０を差し引いた値の二乗は、３の二乗の９である。次に、コスト差許容値が３の場合に、コスト差許容値以下の整数は、０、１、２、３の４つの数字を取り得る。そのため、経路コスト差の二乗の和は、０の二乗の０と、１の二乗の１と、２の二乗の４と、３の二乗の９と、を加えた１４である。そのため、リンクＬＮ０１の通行可能性は、９を１４で除した０．６４（６４パーセント（％））となる。なお、経路コスト差がコスト差許容値以下と設定されているため、変動コストは、経路コスト差が３以下の経路に含まれるリンクのみを対象リンクとして算出される。図３に示す例では、類似経路である経路Ｒ１２および経路Ｒ１３の経路コストは、１６であり、最適経路の経路Ｒ１１の経路コストの１５に対して、経路コスト差が１である。そのため、類似経路の経路Ｒ１２および経路Ｒ１３に含まれるリンクは、対象リンクとして、変動コストが算出される。
【００４３】
次に、人数係数の算出方法について説明する。人数係数は、取得された他のユーザの経路情報に基づき、対象リンクを通行する可能性のある人数を、予め設定された基準混雑度の指標値によって除した値である。本実施形態では、対象リンクを通行する可能性のある人数を一人と設定し、また、基準混雑度を２０と設定する。そのため、対象リンクのリンクＬＮ０１における人数係数は、１を２０で除した０．０５となる。図３に示すように、リンクＬＮ０１のリンクコストが５であるため、リンクＬＮ０１の変動コストは、リンクコストの５と、通行可能性の０．６４と、人数係数の０．０５と、を乗じた０．１６である。以上のようにして、対象リンクのそれぞれの変動コストが算出される。
【００４４】
図５は、変動コストデータの作成処理の流れを示す説明図である。変動コストデータの作成処理では、初めに、コスト調整部１３０の変動コスト算出部１３５が基準混雑度および通行許容値を設定する（ステップＳ２１）。通行許容値とは、リンクのそれぞれに対して、どこまでの混雑を許容するかを判定するための閾値である。本実施形態では、変動コスト算出部１３５は、基準混雑度を２０に設定し、リンクのそれぞれの通行許容値を、ネットワーク情報によって特定されるそれぞれのリンクコストの２倍の値に設定する。通行許容値がリンクコストの２倍に設定されると、詳細については後述するが、例えば、リンクコストが５のリンクにおいては、変動コストが加えられた後のリンクコストが５の２倍の１０までを許容し、１０よりも大きい場合には、通行許容値が再設定される。
【００４５】
基準混雑度および通行許容値が設定されると、変動コスト算出部１３５は、一人の他のユーザの経路情報ごとにコスト差許容値を設定する（ステップＳ２３）。変動コストデータの作成処理の初期段階では、目的地付近の交通状況をより詳しく把握するために、変動コスト算出部１３５は、コスト差許容値を小さい値に設定する。本実施形態では、変動コスト算出部１３５は、初めに、コスト差許容値を３に設定する。なお、他のユーザの経路情報における最適経路は、請求項における第１の最適経路に相当し、他のユーザの経路情報における類似経路は、請求項における第１の準最適経路に相当する。
【００４６】
コスト差許容値が設定されると、変動コスト算出部１３５は、取得した経路情報に含まれる他のユーザの移動経路を構成する全リンクに対して、コスト差許容値を用いて、通行可能性を算出する（ステップＳ２５）。なお、本実施形態では、通行可能性を算出する際に、小数点以下を四捨五入している。図３および図４で示したように、同じようにして通行可能性を算出すると、経路コスト差が１の類似経路を構成するリンクの通行可能性は、２の二乗の４を１４で割った２９％である。経路コスト差が２の類似経路の通行可能性は、７％であり、経路コスト差が３の類似経路の通行可能性は、０％である。
【００４７】
通行可能性が算出されると、変動コスト算出部１３５は、経路コスト差がコスト差許容値以下である移動経路を構成する全ての対象リンクに加える変動コストを算出する（ステップＳ２７）。図６は、出発地と目的地とを含むネットワーク情報の一部を示す説明図である。図６には、２人の他のユーザのそれぞれの出発地のノードである出発地Ｓ１および出発地Ｓ２と、２人の他のユーザの同一の目的地のノードである目的地ＧＬと、黒丸で示された複数のノードと、直線で示された２つのノードを接続する複数のリンクと、が示されている。また、図６では、変動コストが加えられる前のネットワーク情報によって特定される各リンクのリンクコストが数字で示されている。
【００４８】
図７は、他のユーザに設定された出発地Ｓ１と目的地ＧＬとを結ぶ移動経路の一例を示す説明図である。図７以降で後述する同一のネットワークを用いた各図では、各リンクのリンクコストは図６と同じである。図７には、他のユーザの経路情報として、出発地Ｓ１と目的地ＧＬとを結ぶ３つの経路Ｒ１１、Ｒ１２、Ｒ１３が示されている。図７に示すように、経路Ｒ１１は、出発地Ｓ１を出発して、ノードＮ１１とノードＮ１２とを通過して目的地ＧＬに到着する経路である。経路Ｒ１２は、出発地Ｓ１を出発して、ノードＮ１１とノードＮ１５とを通過して目的地ＧＬに到着する経路である。経路Ｒ１３は、出発地Ｓ１を出発して、ノードＮ１４とノードＮ１５とを通過して目的地ＧＬに到着する経路である。
【００４９】
図８は、出発地Ｓ１と目的地ＧＬとを結ぶ移動経路に含まれる対象リンクに加えられる変動コストの一例を示す説明図である。図８には、図７における経路Ｒ１１、Ｒ１２、Ｒ１３に含まれる対象リンクを一人の他のユーザが通行する場合に加えられる変動コストが示されている。本実施形態では、変動コストは、対象リンクのリンクコストに加える値であるため、必ずプラスの値となる。図８には、同じようにして算出された経路Ｒ１１、Ｒ１２、Ｒ１３に含まれる対象リンクに加える変動コストが示されている。なお、変動コストの小数点第３位以降は、以降も含め、四捨五入されている。
【００５０】
図９は、他のユーザに設定された出発地Ｓ２と目的地ＧＬとを結ぶ移動経路を示す説明図である。図９には、図７および図８に示されたユーザとは異なる他のユーザに設定された出発地Ｓ２と目的地ＧＬとを結ぶ移動経路としての経路Ｒ１４が示されている。図９に示すように、経路Ｒ１４は、出発地Ｓ２を出発して、ノードＮ１３、ノードＮ１４、ノードＮ１５を通過して目的地ＧＬに到着する経路である。経路Ｒ１４の経路コストは、３０である。図９に示すように、このユーザの経路情報では、経路Ｒ１４のみが対象リンクを含む移動経路として設定されている。当然、経路Ｒ１４は、出発地Ｓ２と目的地ＧＬとを結ぶ最適経路になる。
【００５１】
図１０は、出発地Ｓ２と目的地ＧＬとを結ぶ移動経路に含まれる対象リンクに加えられる変動コストの一例を示す説明図である。図１０には、図９における経路Ｒ１４に含まれる対象リンクを一人の他のユーザが通行する場合に加えられる変動コストが示されている。図８に示す例と同様に、図１０に示す例では、例えば、出発地Ｓ２とノードＮ１３とを接続するリンクＬＮ０２の変動コストは、ネットワーク情報によって特定されるリンクコストの３（図６）に、通行可能性の６４％（最適経路）と、人数係数の０．０５を乗じた０．１０となる。図１０には、同じようにして、算出された経路Ｒ１４に含まれる対象リンクに加えられる変動コストが示されている。
【００５２】
全ての対象リンクに加える変動コストが算出されると（図５のステップＳ２７）、変動コスト算出部１３５は、ネットワーク情報によって特定されるリンクのリンクコストに、算出された変動コストを加える（ステップＳ２９）。図１１は、変動コストが加えられたリンクコストを示すネットワーク情報の一例を示す説明図である。図１１には、出発地Ｓ１と目的地ＧＬとを結ぶ経路を移動経路とする一人の他のユーザの経路情報と、出発地Ｓ２と目的地ＧＬとを結ぶ経路を移動経路とする一人の他のユーザの経路情報と、に基づいて算出された変動コストが加えられたリンクコストが示されている。図１１に示すように、例えば、ノードＮ１５と目的地ＧＬとを接続するリンクＬ０３のリンクコストは、ネットワーク情報によって特定された６と異なり、出発地Ｓ１を出発する他のユーザの移動経路に基づいて算出された変動コストの０．０９と（図８）、出発地Ｓ２を出発する他のユーザの移動経路に基づいて算出された変動コストの０．１９と（図１０）と、が加えられた６．２８になる。
【００５３】
リンクコストに変動コストが加えられると（図５のステップＳ２９）、変動コスト算出部１３５は、ネットワーク情報に含まれるリンクに、設定された通行許容値を超えるリンクがあるか否かを判定する（ステップＳ３１）。図１１に示す例では、変動コストが加えられる前のリンクコストの２倍の値である通行許容値を超えるリンクコストがないため（ステップＳ３１：ＮＯ）、コスト調整部１３０のリンクコスト情報ＤＢ１３６が変動コストを加えたリンクコストを変動コストデータとして記憶し、コスト調整部１３０は、変動コストデータの作成処理を終了する。
【００５４】
図５のステップＳ３１の処理において、通行許容値を超えるリンクがあると判定された場合には（ステップＳ３１：ＹＥＳ）、変動コスト算出部１３５は、通行許容値を超えたリンクを含む経路情報を抽出する（ステップＳ３３）。図１２は、出発地Ｓ１と目的地ＧＬとを結ぶ移動経路に含まれる対象リンクに加えられる変動コストを示す説明図である。図１２には、出発地Ｓ１と目的地ＧＬとを結ぶ経路を移動経路として設定した４０人の他のユーザに基づいて、算出された変動コストが示されている。なお、図１２に示す変動コストは、図９と同じ基準混雑度と、通行可能性と、が用いられて算出されており、ユーザの数の違いによって、人数係数は、４０（人）を基準混雑度の２０で割った２を用いて算出されている。そのため、図１２に示す変動コストは、図８に示す変動コストの４０倍の値である。この場合に、例えば、変動コストを加える前のリンクＬＮ０１のリンクコストは、５であり、変動コストの６．４を加えると、１１．４となる。この変動コストの１１．４は、通行許容値として設定された変動コストを加える前のリンクコストの２倍の１０を超えるため（図５のステップＳ３１：ＹＥＳ）、変動コスト算出部１３５は、通行許容値を超えた出発地Ｓ１と目的地ＧＬとを結ぶ４０人のユーザの経路情報に基づいて算出された変動コストを削除する（ステップＳ３５）。
【００５５】
次に、変動コスト算出部１３５は、変動コストを削除する前の３の通行許容値よりも高い通行許容値として６を新たに設定して（ステップＳ３７）、ステップＳ２５以降の処理を繰り返す。図１３は、他のユーザに設定された出発地Ｓ１と目的地ＧＬとを結ぶ移動経路の一例を示す説明図である。図１３に示す経路Ｒ１５は、出発地Ｓ１を出発して、ノードＮ１１、ノードＮ１２、ノードＮ１６、ノードＮ１７を通過して、目的地ＧＬに到着する経路である。図６に示す各リンクのリンクコストを用いて算出すると、経路Ｒ１５の経路コストは、２０である。図７の場合と異なり、通行許容値が６に設定されているため、図１３に示す例では、図７に示した経路Ｒ１１、Ｒ１２、Ｒ１３に加えて、経路コスト差がコスト差許容値以下の類似経路として、経路Ｒ１５が対象リンクを含む移動経路として設定される。
【００５６】
次に、変動コスト算出部１３５は、新たに設定された通行許容値に基づいて、通行可能性を算出する（図５のステップＳ２５）。最適経路の経路Ｒ１１に対する経路Ｒ１５の経路コスト差は、２０から１５を差し引いた５である。そのため、通行可能性を求めるための経路コスト差の二乗の和は、０の二乗と、１の二乗と、２の二乗と、３の二乗と、４の二乗と、５の二乗と、６の二乗と、を足し合わせた９１である。よって、経路コスト差が０である経路Ｒ１１に含まれる対象リンクの通行可能性は、コスト差許容値から経路コスト差を差し引いた６の二乗の３６を９１で除した４０％である。同様に、経路コスト差が１である経路Ｒ１２および経路Ｒ１３に含まれる対象リンクの通行可能性は、コスト差許容値から経路コスト差を差し引いた二乗の２５を９１で除した２７％である。また、経路Ｒ１５に含まれる対象リンクの通行可能性は、コスト差許容値から経路コスト差を差し引いた１の二乗の１を９１で除した１％である。
【００５７】
通行可能性が算出されると、変動コスト算出部１３５は、算出された通行可能性を用いて、全ての対象リンクに加える変動コストを算出する（図５のステップＳ２７）。図１４は、出発地Ｓ１と目的地ＧＬとを結ぶ移動経路に含まれる対象リンクに加えられる変動コストの一例を示す説明図である。図１４には、新たに設定された通行許容値が６の場合に、出発地Ｓ１と目的地ＧＬとを結ぶ移動経路に含まれる対象リンクに加える変動コストが示されている。なお、図１４には、４０人のユーザの移動経路に基づいて算出された変動コストが示されている。例えば、リンクＬＮ０１に加えられる変動コストは、リンクコストの５（図６）に、通行可能性の４０％（最適経路の経路Ｒ１１）と、人数係数の２と、を乗じた４．０である。図１４には、同じようにして、算出された経路Ｒ１１、Ｒ１２、Ｒ１３、Ｒ１５に含まれる対象リンクに加えられる変動コストが示されている。
【００５８】
変動コストが算出されると、変動コスト算出部１３５は、対象リンクのリンクコストに変動コストを加え（図５のステップＳ２９）、通行許容値を超えるリンクがあるか否かを判定する（ステップＳ３１）。以上のように、コスト調整部１３０は、通行許容値を超えるリンクがなくなるまで、変動コストデータの作成処理を行なう。
【００５９】
Ａ−４．移動経路群の探索処理：
変動コストデータの作成処理が行なわれると（図２のステップＳ２０）、経路探索部１２０は、作成された変動コストデータを用いて、出発地と目的地とを結ぶユーザの移動経路を探索する（ステップＳ４０）。図１５は、移動経路群の探索処理の流れを示す説明図である。移動経路群の探索処理では、初めに、経路探索部１２０が最適経路の経路コストに加える経路探索コストを設定する（ステップＳ４１）。詳細については後述するが、経路探索部１２０は、最適経路の経路コストに経路探索コストを加えた値以下となる類似経路を探索する。本実施形態では、経路探索部１２０は、経路探索コストを３に設定する。次に、経路探索部１２０は、ネットワーク上のノードに各種ラベルを付与する処理を行なう（ステップＳ５０）。ラベルの付与処理の詳細については、後述する。次に、経路探索部１２０の最適経路探索部１２３は、ノードに付与されたラベルに基づいて、出発地と目的地とを結ぶ経路の経路コストが最小となる最適経路を探索する（ステップＳ４３）。次に、経路探索部１２０の類似経路探索部１２４は、探索された最適経路に含まれるノードに付与されたラベルと経路探索コストとに基づいて、類似経路群を探索する（ステップＳ９０）。なお、類似経路群の探索処理の詳細については、後述する。次に、経路探索部１２０は、探索された最適経路および類似経路群を合わせて移動経路群として設定する（ステップＳ４５）。
【００６０】
図１６および図１７は、ラベルの付与処理の流れを示す説明図である。ラベルの付与処理では、ネットワーク上のノードに、ラベルが付与されるノードの直前のラベルと、出発地のノードからラベルが付与されるノードまでを移動するための経路コストと、を特定するラベルを付与する処理である。ラベル付与処理では、初めに、出発地のノードに候補ラベルを付与する（ステップＳ５１）。
【００６１】
図１８は、出発地Ｓ２のノードに候補ラベルが付与された状態を示す説明図である。図１８には、候補ラベルのラベルＡ０が出発地Ｓ２のノードに付与された状態が示されている。なお、ノードに付与するラベルには、候補ラベルと、確定ラベルと、新しいラベルと、負けラベルと、の４種類があり、４種類のラベルを使い分けることで最適経路および類似経路が探索される。図１８に示すように、候補ラベルのラベルＡ０では、直前のラベルがないため、直前のラベルが「−」で示され、いずれのリンクも通行していないため、経路コストが「０」で示されている。また、図１８には、ノードを接続するリンクのリンクコストが数値で示されており、四角で囲われている数値は、変動コストが加算されたリンクコストである。なお、本実施形態では、携帯電話機２００のユーザは、出発地Ｓ２から目的地ＧＬまでの移動経路群を探索する。
【００６２】
出発地Ｓ１に候補ラベルが付与されると、経路探索部１２０は、ネットワーク上にノードに付与された候補ラベルがあるか否かを判定する（図１６のステップＳ５３）。ノードに付与されている候補ラベルがないと判定された場合には（ステップＳ５３：ＮＯ）、経路探索部１２０は、ラベルの付与処理を終了する。ステップＳ５３の処理において、図１８に示すように、出発地Ｓ１に候補ラベルのラベルＡ０が付与されているため（図１６のステップＳ５３：ＹＥＳ）、経路探索部１２０は、経路コストが最小の候補ラベルであるラベルＡ０を確定ラベルに変更する（ステップＳ５５）。
【００６３】
次に、経路探索部１２０は、目的地ＧＬのノードに確定ラベルが既に付与されているか否かを判定する（ステップＳ５７）。図１８に示すように、目的地ＧＬには確定ラベルが付与されていないので（ステップＳ５７：ＮＯ）、経路探索部１２０は、確定ラベルに変更したラベルＡ０が付与されたノードからリンクによって接続された通行可能な隣接ノードに新しいラベルを付与する（ステップＳ６１）。
【００６４】
図１９は、確定ラベルのラベルＡ０が付与された出発地Ｓ１の隣接ノードに新しいラベルが付与された状態を示す説明図である。図１９には、出発地Ｓ２に付与された確定ラベルのラベルＡ０に基づいて、出発地Ｓ２にリンクによって接続された３つの隣接ノードのノードＮ１３、Ｎ１６、Ｎ１８に新しいラベルが付与された状態が示されている。新しいラベルとして、ノードＮ１３にはラベルＡ１が付与され、ノードＮ１６にはラベルＡ２が付与され、ノードＮ１８にはラベルＡ３が付与されている。ラベルＡ１は、直前のラベル（以下、単に「直前ラベル」とも呼ぶ）がラベルＡ０であり、経路コストが通行したリンクＬＮ０２のリンクコストの５である。同様に、ラベルＡ２は、直前ラベルがラベルＡ０であり、経路コストが通行した出発地Ｓ２とノードＮ１６とを結ぶリンクＬＮ０４のリンクコストの５である。ラベルＡ３は、直前ラベルがラベルＡ０であり、経路コストが通行した出発地Ｓ２とノードＮ１８とを結ぶリンクＬＮ０５のリンクコストの１５である。
【００６５】
隣接ノードに新しいラベルが付与されると、経路探索部１２０は、新しいラベルを付与した１つ以上の隣接ノードから１つの着目ノードとして、ラベルＡ１が付与されたノードＮ１３を選択する（図１７のステップＳ６３）。次に、経路探索部１２０は、着目ノードであるノードＮ１３に確定ラベルが既に付与されているか否かを判定する（ステップＳ６５）。図１９に示すように、ノードＮ１３には、確定ラベルが付与されていないため（図１７のステップＳ６５：ＮＯ）、経路探索部１２０は、着目ノードのノードＮ１３に付与された１つ以上の新しいラベルから１つの処理対象ラベルとして、ラベルＡ１を選択する（ステップＳ６７）。次に、経路探索部１２０は、ノードＮ１３に候補ラベルが付与されているか否かを判定する（ステップＳ６９）。図１９に示すように、ノードＮ１３には、候補ラベルが付与されていないため（図１７のステップＳ６９：ＮＯ）、経路探索部１２０は、処理対象ラベルである新しいラベルのラベルＡ１を候補ラベルに変更する（ステップＳ７５）。次に、経路探索部１２０は、新しいラベルが付与された隣接ノードの内、着目ノードとして選択されていない隣接ノードがあるか否かを判定する（ステップＳ８１）。図１９に示すように、出発地Ｓ２の隣接ノードの内、ノードＮ１６とノードＮ１８とが着目ノードとして選択されていないため（図１７のステップＳ８１：ＹＥＳ）、経路探索部１２０は、ノードＮ１３を着目ノードとして選択したときと同様に、ノードＮ１６を着目ノードとして選択し（ステップＳ６３）、ステップＳ６５以降の処理を行なう。これにより、ノードＮ１６に付与されたラベルＡ２が候補ラベルに変更され、ノードＮ１８に付与されたラベルＡ３が候補ラベルに変更される。
【００６６】
出発地Ｓ２の隣接ノードの内、着目ノードとして選択されていないノードがなくなると（ステップＳ８１：ＮＯ）、経路探索部１２０は、ネットワーク上のノードに付与された候補ラベルがあるか否かを判定する（図１６のステップＳ５３）。ノードＮ１３、Ｎ１６、Ｎ１８には候補ラベルが付与されているため（ステップＳ５３：ＹＥＳ）、経路探索部１２０は、経路コストが最小の５であるラベルの内の１つのラベルＡ１を確定ラベルに変更する（ステップＳ５５）。目的地ＧＬには確定ラベルが付与されていないため（ステップＳ５７：ＮＯ）、経路探索部１２０は、確定ラベルのラベルＡ１が付与されたノードＮ１３の隣接ノードに新しいラベルを付与する（ステップＳ６１）。
【００６７】
図２０は、確定ラベルのラベルＡ１が付与されたノードＮ１３の隣接ノードに新しいラベルが付与された状態を示す説明図である。図２０には、ノードＮ１３に付与された確定ラベルのラベルＡ１に基づいて、ノードＮ１３の隣接ノードであるノードＮ１７、Ｎ１４、Ｎ１９および出発地Ｓ２に新しいラベルが付与された状態が示されている。新しいラベルとして、ノードＮ１７にはラベルＡ４が付与され、出発地Ｓ２にはラベルＡ５が付与され、ノードＮ１４にはラベルＡ６が付与され、ノードＮ１９にはラベルＡ７が付与されている。これら４つのラベルの直前ラベルと経路コストとについては、図２０に示す通りであり、例えば、ラベルＡ４は、直前ラベルがラベルＡ１で、経路コストがラベルＡ１のラベルの経路コストの５に、ノードＮ１３とノードＮ１７とを接続するリンクＬＮ０６のリンクコストの４が加えられた９である。
【００６８】
出発地Ｓ２に付与された確定ラベルのラベルＡ０に基づいて、候補ラベルのラベルＡ１、Ａ２、Ａ３が付与されたのと同様に、ノードＮ１７、Ｎ１４、Ｎ１９に付与された新しいラベルＡ４、Ａ６、Ａ７は、候補ラベルに変更される。ここで、出発地Ｓ２に付与されたラベルＡ５の処理について説明する。経路探索部１２０は、新しいラベルを付与した隣接ノードの内、１つの着目ノードとして出発地Ｓ２を選択する（図１７のステップＳ６３）。着目ノードである出発地Ｓ２には、確定ラベルのラベルＡ０があるため（ステップＳ６５：ＹＥＳ）、経路探索部１２０は、出発地Ｓ２に付与された新しいラベルのラベルＡ５を負けラベルに変更する（ステップＳ７７）。その後、経路探索部１２０は、ステップＳ８１以降の処理を行なう。
【００６９】
ノードＮ１３の隣接ノードの内、着目ノードとして選択されていないノードがなくなると（ステップＳ８１）、経路探索部１２０は、ネットワーク上のノードに付与された候補ラベルがあるか否かを判定する（図１６のステップＳ５３）。ノードＮ１６、Ｎ１８、Ｎ１７、Ｎ１４、Ｎ１９には候補ラベルが付与されているため（ステップＳ５３：ＹＥＳ）、経路探索部１２０は、経路コストが最小の５であるラベルＡ２を確定ラベルに変更する（ステップＳ５５）。目的地ＧＬには確定ラベルが付与されていないため（ステップＳ５７：ＮＯ）、経路探索部１２０は、確定ラベルのラベルＡ２が付与されたノードＮ１６の隣接ノードに新しいラベルを付与する（ステップＳ６１）。
【００７０】
図２１は、確定ラベルのラベルＡ２が付与されたノードＮ１６の隣接ノードに新しいラベルが付与された状態を示す説明図である。図２１には、ノードＮ１６に付与された確定ラベルのラベルＡ２に基づいて、ノードＮ１６の隣接ノードであるノードＮ１７と出発地Ｓ２とに新しいラベルが付与された状態が示されている。新しいラベルとして、ノードＮ１７にはラベルＡ８が付与され、出発地Ｓ２にはラベルＡ９が付与されている。ラベルＡ８は、直前ラベルがラベルＡ２で、経路コストが８である。ラベルＡ９は、直前ラベルがラベルＡ２で、経路コストが１０である。
【００７１】
ノードＮ１３に付与された確定ラベルのラベルＡ１に基づいて、出発地Ｓ２に負けラベルのラベルＡ５が付与されたのと同様に、出発地Ｓ２に付与された新しいラベルのラベルＡ９は、負けラベルに変更される。ここで、経路探索部１２０は、ノードＮ１６の隣接ノードの内から着目ノードとしてノードＮ１７を選択する（図１７のステップＳ６３）。ノードＮ１７には、確定ラベルが付与されていないため（ステップＳ６５：ＮＯ）、経路探索部１２０は、ノードＮ１７に付与された新しいラベルのラベルＡ８を処理対象ラベルとして選択する（ステップＳ６７）。次に、経路探索部１２０は、着目ノードであるノードＮ１７に候補ラベルが付与されているか否かを判定する（ステップＳ６９）。図２１に示すように、ノードＮ１７には候補ラベルとしてラベルＡ４が付与されているため（図１７のステップＳ６９：ＹＥＳ）、経路探索部１２０は、ノードＮ１７に付与された候補ラベルの経路コストがノードＮ１７に付与された新しいラベルの経路コストよりも大きいか否かを判定する（ステップＳ７１）。図２１に示すように、候補ラベルのラベルＡ４の経路コストは、９であり、新しいラベルのラベルＡ８の経路コストの８よりも大きいため（ステップＳ７１：ＹＥＳ）、経路探索部１２０は、候補ラベルのラベルＡ４を負けラベルに変更する（ステップＳ７３）。その後、経路探索部１２０は、新しいラベルのラベルＡ８を候補ラベルに変更し（ステップＳ７５）、ステップＳ８１以降の処理を行なう。なお、ステップＳ７１の処理において、候補ラベルの経路コストが新しいラベルの経路コストよりも大きくない場合には（ステップＳ７１：ＮＯ）、経路探索部１２０は、新しいラベルを負けラベルに変更する。
【００７２】
図２２は、目的地ＧＬに付与された確定ラベルのラベルＡ４８に基づいて目的地ＧＬの隣接ノードに新しいラベルが付与された状態を示す説明図である。図２２には、ネットワーク上のノードに対するラベルの付与処理が進み、目的地ＧＬに付与された候補ラベルのラベルＡ４８が確定ラベルに変更された後に、目的地ＧＬの隣接ノードであるノードＮ１５、Ｎ２１、Ｎ２０、Ｎ１２に新しいラベルが付与された状態が示されている。なお、図２２では、各ラベルのラベル名のみを示し、目的地ＧＬの隣接ノードに付与された新しいラベルのラベルＡ６０、Ａ６１、Ａ６２、Ａ６３に関連するラベルの経路コストが表に示されている。ノードＮ１５において、新しいラベルのラベルＡ６０の経路コストは、４６．４であり、確定ラベルのラベルＡ１５の経路コストの２４．４よりも大きいため、ラベルＡ６０は、負けラベルに変更される。同じように、ノードＮ２１に付与された新しいラベルのラベルＡ６１は、負けラベルに変更される。また、ノードＮ１２に付与された新しいラベルのラベルＡ６３は、負けラベルに変更される。ノード２０において、新しいラベルのラベルＡ６２の経路コストの３５．８は、候補ラベルのラベルＡ５６の経路コストの３５．４よりも大きいため、ラベルＡ６２は、負けラベルに変更される。
【００７３】
目的地ＧＬに確定ラベルのラベルＡ４８が付与されると、経路探索部１２０は、ネットワーク上のノードに付与された候補ラベルがあるか否かを判定する（図１６のステップＳ５３）。図２２に示すように、候補ラベルとして、ノードＮ２０に付与されたラベルＡ５６とノードＮ２２に付与されたラベルＡ５３とがあるため（図１６のステップＳ５３：ＹＥＳ）、経路探索部１２０は、経路コストが最小の３５．４のノードＮ２０に付与された候補ラベルのラベルＡ５６を確定ラベルに変更する（ステップＳ５５）。次に、目的地ＧＬには確定ラベルのラベルＡ４８が付与されているため（ステップＳ５７：ＹＥＳ）、経路探索部１２０は、変更した確定ラベルのラベルＡ５６の経路コストが目的地ＧＬの確定ラベルの経路コストと経路探索コストとを加えた値よりも大きいか否かを判定する（ステップＳ６１）。確定ラベルのラベルＡ５６の経路コストは、３５．４であり、目的地ＧＬの確定ラベルのラベルＡ４８の経路コストの３４．８に経路探索コストの３を加えた３７．８よりも大きくないため（ステップＳ５９：ＮＯ）、経路探索部１２０は、ステップＳ６１以降の処理を行なう。なお、変更された確定ラベルの経路コストが目的地ＧＬに付与された確定ラベルの経路コストと経路探索コストとを加えた値よりも大きい場合には（ステップＳ５９：ＹＥＳ）、経路探索部１２０は、ラベルの付与処理を終了する。
【００７４】
図２３は、ネットワーク上のノードに付与された候補ラベルがなくなった状態の一例を示す説明図である。図２４および図２５は、ネットワーク上のノードに付与された確定ラベルおよび負けラベルのそれぞれについての経路コストと直前ラベルとの関係を一覧で示す説明図である。図２３には、ネットワーク上のノードに付与された確定ラベルおよび負けラベルのラベル名のみが示されている。図２４および図２５には、図２３に示された各ラベルのそれぞれについての経路コストと、直前ラベルと、確定ラベルまたは負けラベルを示すラベルの種類とが示されている。例えば、ラベルＡ１０は、図２４に示すように、ノードＮ１６に付与されたラベルであり、経路コストが１１で、直前ラベルがラベルＡ８の負けラベルである。以上のように、ネットワーク上にノードに付与された候補ラベルがなくなると（図１６のステップＳ５３：ＮＯ）、経路探索部１２０は、ラベルの付与処理を終了する。
【００７５】
ラベルの付与処理が終了すると、経路探索部１２０の最適経路探索部１２３は、ノードに付与されたラベルに基づいて、最適経路を探索する（図１５のステップＳ４３）。ラベルの付与処理では、直前ラベルおよび経路コストを特定するラベルがノードに付与されているため、特定のノードに付与された１つのラベルは、出発地Ｓ２と特定のラベルとを結ぶ経路と、当該経路の経路コストとを特定できる。そのため、目的地ＧＬに付与された確定ラベルに基づく経路は、出発地Ｓ２と目的地ＧＬとを結ぶ経路コストが最小の経路であると特定され、最適経路探索部１２３は、探索された当該経路を最適経路として設定する。なお、以降では、特定のラベルによって特定される経路を、単に「特定のラベルに基づく経路」ともいう。
【００７６】
図２６は、出発地Ｓ２と目的地ＧＬとを結ぶ最適経路の一例を示す説明図である。図２６には、目的地ＧＬに付与された確定ラベルのラベルＡ４８に基づいて、図２３および図２５を用いて、探索された最適経路である経路Ｒ２１が示されている。
【００７７】
最適経路が探索されて設定されると、経路探索部１２０の類似経路探索部１２４は、ネットワーク上のノードに付与された確定ラベルと負けラベルとに基づいて、類似経路群の探索処理を行なう（図１５のステップＳ９０）。図２７は、類似経路群の探索処理の流れを示す説明図である。類似経路群の探索処理では、初めに、類似経路探索部１２４は、最適経路に含まれるノードである最適ノードに、負けラベルが付与されているノードがあるか否かを判定する（ステップＳ９１）。図２６に示すように、最適経路の経路Ｒ２１に含まれる最適ノードの全てに負けラベルが付与されているため（ステップＳ９１：ＹＥＳ）、類似経路探索部１２４は、負けラベルが付与された最適ノードから１つの判定対象ノードとして、目的地ＧＬを選択する（ステップＳ９３）。次に、類似経路探索部１２４は、目的地ＧＬに付与された負けラベルと確定ラベルとの経路コスト差が経路探索コスト以下であるか否かを判定する（ステップＳ９５）。経路コスト差が経路探索コスト以下であると判定された場合には（ステップＳ９５：ＹＥＳ）、類似経路探索部１２４は、当該負けラベルに基づく経路を１つの類似経路として設定する（ステップＳ９７）。類似経路が設定された場合、または、ステップ９５の処理において、経路コスト差が経路探索コスト以下ではないと判定された場合には（ステップＳ９５：ＮＯ）、類似経路探索部１２４は、判定対象ノードとして選択されていない最適ノードがあるか否かを判定する（ステップＳ９９）。判定対象ノードとして選択されていない最適ノードがある場合には（ステップＳ９９：ＹＥＳ）、類似経路探索部１２４は、新たな判定対象ノードを選択して（ステップＳ９３）、ステップＳ９５以降の処理を行なう。
【００７８】
図２８は、探索された類似経路群の一例を示す説明図である。図２８には、最適経路である経路Ｒ２１に加えて、探索された類似経路群に含まれる類似経路である経路Ｒ２２と経路Ｒ２３とが示されている。なお、図２８では、判定対象ノードとして選択された最適ノードである目的地ＧＬに付与された確定ラベルと類似経路の基となる負けラベルとについては、ラベル名に加えて、直前ラベルおよび経路コストが示されている。図２８に示すように、目的地ＧＬの負けラベルのラベルＡ４３の経路コストの３６から、目的地ＧＬの確定ラベルのラベルＡ４８の経路コストの３４．８を差し引いた値は、１．２であり、経路探索コストの３以下であるため、ラベルＡ４３に基づく経路は、類似経路として設定される。図２４および図２５により、ラベルＡ４３に基づく類似経路は、図２８に示す経路Ｒ２２である。また、同じように、目的地ＧＬの負けラベルであるラベルＡ６５の経路コストの３６．４から、目的地ＧＬのラベルＡ４８の経路コストの３４．８を差し引いた値は、１．６であり、経路探索コストの３以下であるため、ラベルＡ６５に基づく経路は、類似経路として設定される。ラベルＡ６５に基づく類似経路は、図２８に示す経路Ｒ２３である。なお、最適経路の経路Ｒ２１に含まれる最適ノードは、請求項における第２の最適ノードに相当する。また、出発地Ｓ２と特定の最適ノードとを結ぶ移動経路は、請求項における第２の中途経路に相当する。特定の最適ノードに付与された確定ラベルに基づく経路は、第２の最小コスト中途経路に相当し、特定の最適ノードに付与された負けラベルに基づく経路は、第２の非最小コスト中途経路に相当する。
【００７９】
図２７のステップＳ９９の処理において、判定対象ノードとして選択されていない最適ノードがないと判定された場合には（ステップＳ９９：ＮＯ）、類似経路探索部１２４は、設定された類似経路を一時的に最適経路として設定する（ステップＳ１０１）。次に、類似経路探索部１２４は、新たに一時的に設定した最適経路に含まれる最適ノードに付与された負けラベルを対象としてステップＳ９３以降の処理を行なう。すなわち、類似経路探索部１２４は、類似経路に含まれるノードに付与された負けラベルの全てについて、更なる類似経路を探索する。本実施形態では、図２４および図２５に示すように、類似経路群の経路Ｒ２２および経路Ｒ２３において、更なる類似経路として設定される経路がないため、類似経路探索部１２４は、類似経路群の探索処理を終了する。
【００８０】
類似経路群の探索処理が行なわれると、経路探索部１２０は、探索された最適経路および類似経路群を、移動経路群として設定する（図１５のステップＳ４５）。以上の通り、本実施形態では、最適経路の経路Ｒ２１と、類似経路の経路Ｒ２２および経路Ｒ２３と、が出発地Ｓ２と目的地ＧＬとを結ぶ移動経路として設定されて、携帯電話機２００を介して、ユーザに提示される。
【００８１】
以上説明したように、本実施形態におけるサーバ１００では、コスト調整部１３０は、複数の携帯電話機２００等のそれぞれから送信された経路情報に含まれる最適経路と類似経路とに基づいて、通行可能性等を用いることで、ネットワーク情報によって特定されるリンクのリンクコストを調整する。経路探索部１２０は、調整されたリンクコストを特定する探索用ネットワークを用いることで、出発地と目的地とを結ぶ少なくとも１つの移動経路群を探索する。そのため、本実施形態のサーバ１００では、他のユーザがネットワーク上の交通状況によって、探索された移動経路としての最適経路以外の類似経路を通行した場合でも、類似経路を通行する他のユーザの交通状況も加味した上で、出発地と目的地とを結ぶユーザの移動経路が探索される。よって、ユーザは、他のユーザが通行する可能性のある未来の交通状況を踏まえて、渋滞を回避して目的地に到着できる。
【００８２】
また、本実施形態におけるサーバ１００では、コスト調整部１３０は、他のユーザの経路情報に含まれる情報である最適経路の経路コストと類似経路の経路コストとによって算出される経路コスト差に基づいて、通行可能性等の指標値を用いて変動コストを算出する。そのため、本実施形態のサーバ１００では、他のユーザの１つの移動経路のみではなく、最適経路の経路コストと、所定のリンクコストの差の経路コストである類似経路と、の複数の移動経路を踏まえた混雑度に基づく変動コストが算出される。よって、次に通行予定のリンクの渋滞を見て他のユーザが経路を変更した場合などの状況を予測した上で、ユーザの移動経路が探索されるため、ユーザは、発生する可能性のある渋滞を回避して、より迅速に目的地ＧＬに到着でき、また、ユーザにとっての利便性が向上する。
【００８３】
また、本実施形態におけるサーバ１００では、コスト調整部１３０は、他のユーザの経路情報において、類似経路の経路コストから最適経路の経路コストを差し引いた経路コスト差が小さいほど、通行可能性を大きくして、変動コストを大きく算出する。そのため、本実施形態のサーバ１００では、他のユーザが通行する可能性が高いリンクほど変動コストが大きく算出されるため、実際の混雑度により則した交通状況に基づいてユーザの移動経路を探索できる。
【００８４】
また、本実施形態におけるサーバ１００では、経路探索部１２０の最適経路探索部１２３は、出発地Ｓ２と目的地ＧＬとを結ぶ移動経路の内、経路コストが最小である最適経路を探索する。経路探索部１２０の類似経路探索部１２４は、最適経路の経路コストに経路探索コストを加えた値以下の経路コストを有する少なくとも１つの類似経路を探索する。そのため、本実施形態のサーバ１００では、所定の経路コスト以下の範囲で複数の移動経路が探索されるため、ユーザは複数の移動経路から好みの経路を選択でき、ユーザにとっての利便性が向上する。
【００８５】
Ｂ．第２実施形態：
上記第１実施形態では、他のユーザの経路情報に基づいて、ユーザの出発地と目的地とを結ぶ移動経路が探索されたが、必ずしもユーザの移動経路が探索される必要はなく、他のユーザの経路情報の利用方法については、種々変形可能である。
【００８６】
図２９は、第２実施形態におけるネットワーク上のリンクの推定される混雑度の一例を示す概略図である。図２９には、上記第１実施形態の変動コストデータを用いて、コスト調整部１３０が生成した探索用ネットワーク情報が携帯電話機２００の表示パネル２０２に表示されたネットワーク上の推定される交通状況が示されている。図２９に示す例では、３つの出発地として、出発地Ｓ１、Ｓ２、Ｓ３を出発して、目的地ＧＬ２へと向かう複数のユーザの経路情報に基づいて、変動コストデータが作成されている。図２９には、変動コストデータに基づいて、各リンクのリンクコストに加えられる変動コストの大きさに応じた推定される混雑度が分布ＡＲ１と分布ＡＲ２とで示されている。図２９では、分布ＡＲ１に含まれるリンクのそれぞれの変動コストは、ネットワーク情報に記憶されたリンクコストの５０％である。また、分布ＡＲ２に含まれるリンクのそれぞれの変動コストは、ネットワーク情報に記憶されたリンクコストの７５％である。すなわち、変動コストが加えられた探索用ネットワーク情報において、分布ＡＲ１に含まれるリンクのリンクコストは、ネットワーク情報によって特定されるリンクコストの１５０％の値であり、分布ＡＲ２に含まれるリンクのリンクコストは、ネットワーク情報によって特定される１７５％の値である。なお、探索用ネットワーク情報は、請求項における調整経路情報に相当する。
【００８７】
図３０は、比較例におけるネットワーク上のリンクの推定される混雑度の一例を示す説明図である。図３０には、類似経路の変動コストデータを作成せずに、従来の他のユーザの１つの移動経路である最適経路のみに基づくネットワーク上の推定される交通状況が示されている。この比較例では、分布ＡＲ３に含まれるリンクのそれぞれの変動コストは、ネットワーク情報の記憶されたリンクコストの５０％である。また、分布ＡＲ４に含まれるリンクのそれぞれの変動コストは、ネットワーク情報に記憶されたリンクコストの７５％である。分布ＡＲ５に含まれるリンクのそれぞれの変動コストは、ネットワーク情報に記憶されたリンクコストの１００％である。すなわち、探索用ネットワーク情報において、分布ＡＲ３に含まれるリンクのリンクコストは、ネットワーク情報によって特定されるリンクコストの１５０％の値であり、分布ＡＲ４に含まれるリンクのリンクコストは、ネットワーク情報によって特定されるリンクコストの１７５％の値である。また、探索用ネットワーク情報において、分布ＡＲ５に含まれるリンクのリンクコストは、ネットワーク情報によって特定されるリンクコストの２００％の値である。
【００８８】
以上説明したように、第２実施形態におけるサーバ１００では、コスト調整部１３０は、リンクコストを調整した変動コストデータを用いて探索用ネットワーク情報を生成し、携帯電話機２００に探索用ネットワーク情報を送信する。そのため、第２実施形態のサーバ１００では、複数のユーザの移動経路において、最適経路と類似経路とが探索されてリンクコストが調整算出される。よって、調整されたリンクコストは、比較例と比べて、局所的に高い値にはならず、局所的な渋滞の発生を抑制する。また、ユーザは、一目で目的地ＧＬ２の周りの混雑度を把握でき、経路探索を行なわなくても、渋滞を回避した上で目的地ＧＬ２に向かうことができ、ユーザにとっての利便性が向上する。
【００８９】
また、第２実施形態におけるサーバ１００では、ネットワーク情報に記憶されたリンクコストに対して、変動コストデータによって加えられる変動コストを分布ＡＲ１および分布ＡＲ２で区別して表示している。そのため、第２実施形態のサーバ１００では、ユーザは、混雑していない場合に比べて、どの程度混雑しているかを視認できるため、容易に交通状況を認識でき、ユーザにとっての利便性が向上する。
【００９０】
また、第２実施形態におけるサーバ１００では、コスト調整部１３０は、分布ＡＲ１および分布ＡＲ２によって、変動コストが加えられるリンクを区別した探索用ネットワーク情報を生成する。そのため、第２実施形態のサーバ１００では、ユーザは、どのリンクがどの程度の変動コストが加えられているかを視認できるため、より容易に交通状況を認識でき、ユーザにとっての利便性がより向上する。
【００９１】
Ｃ．変形例：
なお、この発明は上記実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様において実施することが可能であり、例えば、次のような変形も可能である。
【００９２】
Ｃ１．変形例１:
上記実施形態では、サーバ１００は、他のユーザの経路情報として、他のユーザの移動経路も含めた情報を取得したが、必ずしも移動情報を含めた経路情報を取得する必要はなく、取得する経路情報については、種々変形可能である。例えば、サーバ１００は、他のユーザの経路情報として、他のユーザによって携帯電話機２００等に設定された出発地および目的地を取得し、移動経路については取得しなくてもよい。この場合に、サーバ１００のコスト調整部１３０は、他のユーザの移動経路として、経路探索部１２０によって行なわれたラベルの付与処理と同じように、ネットワーク上のノードに各種ラベルを付与することで、最適経路と類似経路とを探索してもよい。この変形例のサーバ１００では、他のユーザの出発地と目的地とを特定する情報のみ取得されれば、他のユーザの移動経路が推定できる。また、他のユーザの出発地が不明の場合であっても、他のユーザが携帯している携帯電話機２００等のＧＰＳユニット２０１によって他のユーザの現在位置を特定して、当該位置を出発地と設定されることで、他のユーザの移動経路を推定でき、より少ない他のユーザの経路情報であっても、混雑度を考慮した経路を探索できる。
【００９３】
Ｃ２．変形例２：
上記第１実施形態では、図２８に示すように、目的地ＧＬに付与された確定ラベルと負けラベルとの経路コスト差に基づいて、類似経路の経路Ｒ２２と経路Ｒ２３とが探索されたが、目的地ＧＬ以外の最適ノードに付与された確定ラベルと負けラベルとに基づいて、類似経路が探索されてもよい。例えば、第１実施形態の経路探索コストよりも大きな経路探索コストが設定された場合に、ノードＮ１４に付与された確定ラベルと負けラベルとに基づいて類似経路が探索される。この場合に、類似経路は、出発地Ｓ２からノードＮ１４までは、ノードＮ１４に付与された負けラベルに基づく経路であり、ノードＮ１４から目的地ＧＬまでは、最適経路と重複する経路である。そのため、この変形例では、類似経路を探索する場合に、出発地Ｓ２から目的地ＧＬまでの経路をいちいち探索せずに、ノードに付与された確定ラベルと負けラベルとに基づいて探索できるため、経路探索を迅速に行なうことができ、経路探索装置の処理の負荷を低減できる。
【００９４】
Ｃ３．変形例３：
上記実施形態では、ＧＰＳユニット２０１によって取得された現在位置が経路を探索する際の出発地として設定されたが、出発地や目的地の設定の方法について、種々変形可能である。例えば、出発地は、ユーザによって操作部２０６が操作されることにより設定されてもよいし、予定された旅行における未来の日時を指定して、出発地や目的地が設定されてもよい。また、出発地や目的地の入力の方法についても、種々変形可能である。例えば、携帯電話機２００の通話制御部２２０による音声認識によって、現在位置や目的地等が設定されてもよい。
【００９５】
また、上記実施形態では、設定された目的地から所定の距離に含まれるリンクが対象リンクとして設定されたが、対象リンクの選択の方法については、これに限られず、種々変形可能である。例えば、目的地ではなく、出発地から所定の距離に含まれるリンクが対象リンクとして設定されてもよい。また、ユーザの移動経路としての最適経路が探索された後に、探索された最適経路を構成するリンクを含む他のユーザの移動経路を構成するリンクが対象リンクとして設定されてもよい。また、ユーザが操作部２０６を操作することにより、特定のリンクが対象リンクとして設定されてもよい。
【００９６】
また、上記実施形態では、変動コストを算出するための指標値について、具体的な値を示して説明したが、これらの指標値のそれぞれについての値は、種々変形可能である。例えば、初めに設定されるコスト差許容値は３以外の値であってもよいし、基準混雑度についても、２０以外の値であってもよいし、小数点を用いた値であってもよい。また、通行可能性を算出する際に、コスト差許容値から経路コスト差を差し引いた値の二乗の値や、経路コスト差の二乗の総和が用いられたが、二乗に限られず、一乗の値であってもよいし、三乗以上の乗数が用いられてもよい。また、通行可能性は、その他の指数関数や二次関数等が用いられて算出されてもよい。また、小数点の処理についても、四捨五入に限られず、端数を切り捨ててもよいし、切り捨てる小数点の単位についても種々変形可能である。
【００９７】
また、上記実施形態では、変動コスト算出部１３５は、地図情報ＤＢ１１４に記憶されたリンクのリンクコストに算出された変動コストを加えたが、リンクコストの調整の方法については、これに限られず、種々変形可能である。例えば、変動コスト算出部１３５は、対象リンク以外のリンクに対して、変動コストを差し引くことで、リンクコストを調整してもよい。また、変動コスト算出部１３５は、変動コストをリンクコストに加減算せずに、変動コストの代わりに何らかの係数を算出して、地図情報ＤＢ１１４に記憶されたリンクコストに係数を乗じることで、リンクコストを調整してもよい。また、変動コストを加えるリンクを特定のリンクに指定してもよい。
【００９８】
Ｃ４．変形例４：
また、上記実施形態では、ノードに付与されたラベルを用いて、ユーザの移動経路としての最適経路および類似経路が探索されたが、移動経路を探索する方法については、これに限られず、種々変形可能である。例えば、経路探索部１２０は、ダイクストラ法によって、最適経路を探索した後に、最適経路に含まれるいくつかのリンクを除いたネットワーク情報を用いて、類似経路を探索してもよい。また、経路探索部１２０は、ダイクストラ法の代わりに、エースター（Ａ*）探索アルゴリズムを用いて、移動経路を探索してもよいし、その他の方法によって移動経路を探索してもよい。
【００９９】
また、上記実施形態では、経路探索コストとして、３の値が用いられて、類似経路が探索されたが、経路探索コストについては、種々変形可能である。例えば、３以外の値であってもよいし、経路探索部１２０は、最適経路の経路コストの何パーセントの値を経路探索コストとして設定してもよい。
【０１００】
また、上記実施形態では、類似経路が探索された後に、類似経路を最適経路として一時的に設定した後に、更なる類似経路が探索されたが、類似経路の探索処理については、これに限られず、種々変形可能である。例えば、経路探索部１２０は、探索された類似経路を最適経路として一時的に設定しなくてもよい。また、経路探索部１２０は、探索される類似経路の数の上限を予め設定しておいて、上限を超える類似経路については、探索しなくてもよい。
【０１０１】
また、上記実施形態では、経路コスト差が小さいほど、通行可能性の指標値が大きくなるため、変動コストが大きい値に算出されたが、経路コスト差と変動コストとの関係については、これに限られず、種々変形可能である。例えば、変動コストの値は、通行可能性等の指標値にかかわらず、一律で同じ値に設定されてもよい。また、最適経路と類似経路とで異なる２つの値のみが設定されてもよい。
【０１０２】
Ｃ５．変形例５：
上記第２実施形態では、図２９に示すように、変動コストが加えられるリンクと、変動コストが加えられないリンクと、を分布ＡＲ１および分布ＡＲ２といった分布によって区別して表示されているが、変動コストが加えられるか否かを区別するための表示の方法については、これに限られず、種々変形可能である。例えば、リンク自体の色を変化させることで、変動コストが加えられたリンクが区別されてもよい。また、表示されるリンクの上に、変動コストの値自体が表示されてもよい。
【０１０３】
Ｃ６．変形例６：
上記実施形態では、リンクコストがリンクを通過する時間（分）であったが、リンクを通過する時間とリンクコストとの関係は、これに限られず、種々変形可能である。例えば、特定されたリンクコストに対して、携帯電話機２００を介して設定されたユーザの移動手段に応じて、リンクコストが時間（例えば、分単位）に換算されてもよい。また、リンクコストは、分単位ではなく、リンクを通過する秒単位の時間であってもよい。
【０１０４】
上記実施形態では、各リンクについて、向きにかかわらず、リンクコストが同じである態様であったが、各リンクの設定については、種々変形可能である。例えば、ユーザが自動車に乗車している場合には、リンクは、一方通行や右折禁止と知った規制が反映されていてもよい。また、リンクのリンクコストについても、例えば、坂道のリンクであった場合には、通過する向きに応じてリンクコストが変更されてもよい。また、ユーザは自動車に乗車している場合に限られず、例えば、ユーザの移動手段が徒歩であったり、自転車であってもよく、その他の移動手段であってもよい。
【０１０５】
また、上記実施形態では、図１に示すようにサーバ１００が情報記憶部１１０および経路探索部１２０を備える態様としたが、情報記憶部１１０および経路探索部１２０を備える装置はこの態様に限られず、種々変形可能である。例えば、情報記憶部１１０と経路探索部１２０とは異なるサーバに備えられていてもよいし、経路探索部１２０が携帯電話機２００に搭載されていてもよい。
【０１０６】
本発明は、上述の実施形態や実施例、変形例に限られるものではなく、その趣旨を逸脱しない範囲において種々の構成で実現できる。例えば、発明の概要の欄に記載した角形態中の技術的特徴に対応する実施形態、実施例、変形例中の技術的特徴は、上述の課題の一部または全部を解決するために、あるいは、上述の効果の一部または全部を達成するために、適宜、差し替えや、組み合わせを行なうことができる。また、その技術的特徴が本明細書中に必須なものとして説明されていなければ、適宜、削除できる。
【符号の説明】
【０１０７】
１０…経路探索システム
２０…ノード
１００…サーバ
１０２…通信部
１１０…情報記憶部
１１４…地図情報ＤＢ
１１５…交通情報ＤＢ
１２０…経路探索部
１２３…最適経路探索部
１２４…類似経路探索部
１３０…コスト調整部
１３５…変動コスト算出部
１３６…リンクコスト情報ＤＢ
１５０…制御部
２００…携帯電話機
２０１…ＧＰＳユニット
２０２…表示パネル
２０３…音声出力部
２０５…無線通信回路
２０６…操作部
２０６ａ…テンキー
２０６ｂ…カーソルキー
２１０…主制御部
２１１…ＣＰＵ
２２０…通話制御部
Ｓ１，Ｓ２…出発地
ＧＬ，ＧＬ２…目的地
ＩＮＴ…インターネット
【図１】
2015165215.tif 000003
【図２】
2015165215.tif 000004
【図３】
2015165215.tif 000005
【図４】
2015165215.tif 000006
【図５】
2015165215.tif 000007
【図６】
2015165215.tif 000008
【図７】
2015165215.tif 000009
【図８】
2015165215.tif 000010
【図９】
2015165215.tif 000011
【図１０】
2015165215.tif 000012
【図１１】
2015165215.tif 000013
【図１２】
2015165215.tif 000014
【図１３】
2015165215.tif 000015
【図１４】
2015165215.tif 000016
【図１５】
2015165215.tif 000017
【図１６】
2015165215.tif 000018
【図１７】
2015165215.tif 000019
【図１８】
2015165215.tif 000020
【図１９】
2015165215.tif 000021
【図２０】
2015165215.tif 000022
【図２１】
2015165215.tif 000023
【図２２】
2015165215.tif 000024
【図２３】
2015165215.tif 000025
【図２４】
2015165215.tif 000026
【図２５】
2015165215.tif 000027
【図２６】
2015165215.tif 000028
【図２７】
2015165215.tif 000029
【図２８】
2015165215.tif 000030
【図２９】
2015165215.tif 000031
【図３０】
2015165215.tif 000032