(57)【要約】【課題】  経路探索において、ノードの位置や数が異なる複数のネットワーク地図や時間的に変化するコストを有するネットワーク地図を有効に利用する。【解決手段】  ナビゲーションシステム１は、ナビ付き自転車１００、ＧＰＳ衛星１０３および地図管理センタ２０３を含む。地図管理センタ２０３は、地図サーバ２０４および地図データベース２０５を含む。地図サーバ２０４は、ナビ付き自転車１００から経路探索の要求メッセージを受信する。そして、地図データベース２０５に格納されたネットワーク地図を使用して経路探索計算を実施し、その経路探索の結果情報を端末１０２に送信する。この場合、時間的に変化するコストを考慮して経路探索計算を行う。また、検索条件に係る複数のネットワーク地図間においてノードの個数や数が異なるときには、対応するノードのないネットワーク地図にダミーノードを設定することで、コストの加算を可能とする。【選択図】      図１
2006275922.tif 000002
【特許請求の範囲】
【請求項１】
移動体に設置されまたは人に所持され、少なくとも出発地点情報、目的地点情報および検索条件情報を含む経路探索の要求メッセージを送信し、その経路探索の結果情報を受信し、表示する端末と、
前記要求メッセージを受信し、その要求メッセージに含まれる出発地点情報、目的地点情報および検索条件情報に従って経路探索を行い、その経路探索の結果情報を前記端末に送信する地図管理サーバと、
がネットワークを介して接続されて構成されるナビゲーションシステムであって、
前記要求メッセージは、出発予定時刻を含み、
前記地図管理サーバは、
検索条件ごとに、その検索条件に係る評価値を示すコストを有する、ノードおよび２つのノード間の接続経路を示すリンクの少なくとも一方を含むネットワーク地図データであって、前記コストを時間帯に対応付けたものを有し、
前記検索条件情報に含まれる検索条件を満たす経路を探索するために、所定のネットワーク地図データ内のノードをリンクに従って出発地点から目的地点に辿る場合に、所定のノードから次のノードに進むのに通過するリンクを選択するときに、前記出発予定時刻に出発地点からの経過時間を加算した時刻を含む時間帯のコストを参照する
ことを特徴とするナビゲーションシステム。
【請求項２】
移動体に設置されまたは人に所持され、少なくとも出発地点情報、目的地点情報および検索条件情報を含む経路探索の要求メッセージを送信し、その経路探索の結果情報を受信し、表示する端末と、
前記要求メッセージを受信し、その要求メッセージに含まれる出発地点情報、目的地点情報および検索条件情報に従って経路探索を行い、その経路探索の結果情報を前記端末に送信する地図管理サーバと、
がネットワークを介して接続されて構成されるナビゲーションシステムであって、
前記地図管理サーバは、
検索条件ごとに、その検索条件に係る評価値を示すコストを有する、ノードおよび２つのノード間の接続経路を示すリンクの少なくとも一方を含むネットワーク地図データを有するとともに、
前記検索条件情報に含まれる複数の検索条件を満たす経路を探索するために、その検索条件に係る複数のネットワーク地図データ内のコストを加算する場合に、ネットワーク地図データ間のノードの位置または数が異なるときに、対応するノードのないネットワーク地図データにダミーノードを設定し、そのダミーノードのコスト、または、そのダミーノードと他のノードとの間のリンクのコストを生成する
ことを特徴とするナビゲーションシステム。
【請求項３】
少なくとも出発地点情報、目的地点情報および検索条件情報を含む経路探索の要求メッセージを受信し、その要求メッセージに含まれる各情報に従って経路探索を行い、その経路探索の結果情報を送信する地図管理サーバであって、
前記要求メッセージは、出発予定時刻を含み、
前記地図管理サーバは、
検索条件ごとに、その検索条件に係る評価値を示すコストを有する、ノードおよび２つのノード間の接続経路を示すリンクの少なくとも一方を含むネットワーク地図データであって、前記コストを時間帯に対応付けたものを有し、
前記検索条件情報に含まれる検索条件を満たす経路を探索するために、所定のネットワーク地図データ内のノードをリンクに従って出発地点から目的地点に辿る場合に、所定のノードから次のノードに進むのに通過するリンクを選択するときに、前記出発予定時刻に出発地点からの経過時間を加算した時刻を含む時間帯のコストを参照する
ことを特徴とする地図管理サーバ。
【請求項４】
少なくとも出発地点情報、目的地点情報および検索条件情報を含む経路探索の要求メッセージを受信し、その要求メッセージに含まれる各情報に従って経路探索を行い、その経路探索の結果情報を送信する地図管理サーバであって、
前記地図管理サーバは、
検索条件ごとに、その検索条件に係る評価値を示すコストを有する、ノードおよび２つのノード間の接続経路を示すリンクの少なくとも一方を含むネットワーク地図データを有するとともに、
前記検索条件情報に含まれる複数の検索条件を満たす経路を探索するために、その検索条件に係る複数のネットワーク地図データ内のコストを加算する場合に、ネットワーク地図データ間のノードの位置または数が異なるときに、対応するノードのないネットワーク地図データにダミーノードを設定し、そのダミーノードのコスト、または、そのダミーノードと他のノードとの間のリンクのコストを生成する
ことを特徴とする地図管理サーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、利用者に対して、その利用者が設定した条件に従って目的地までの最適経路を選択して提示するようにしたナビゲーションシステムおよび地図管理サーバに関する。
【背景技術】
【０００２】
従来、移動体が通過する経路を検索する装置としては、車載用の経路案内装置（以下、ナビゲーション装置という）がよく知られている。車載用のナビゲーション装置は、車両が通行する道路について、ダイクストラ法などを用いて、予め定められている条件を満たす最適な経路を探索し、その探索した経路に沿って車両が走行する際に誘導の案内や支援などを行うようになっている。
【０００３】
近年、コンピュータで利用可能に電子化された地図データ（以下、電子地図データという）を利用して、地図の表示や経路の探索などを行うナビゲーション装置が普及している。ナビゲーション装置は、車載用だけでなく携帯用などもあり、幅広く使用されている。電子地図データは、経路探索を行うための経路探索用データを備えている。経路探索用データは、道路（通路）を表すリンク、交差点や行き止まりなどの道路の端点を表すノード、ランドマーク情報などを備えている。２つのノード間の接続経路を示すリンクには、各道路を識別するためのリンクＩＤや、平均通行所要時間などの道路の評価値を表すリンクコストなどが含まれる。リンクコストは、道路の種別、通行料金の有無、時間帯、渋滞発生率など種々の要因に基づき、道路の管理者が決定しており、ナビゲーション装置は、一般的に、このようなリンクコストに基づき、経路探索を行っている（例えば、特許文献１参照）。
【特許文献１】特開２００２−９８５４７号公報（段落００３９〜００５０、図２）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の技術（特許文献１に記載の技術）では、目的地に至るまでの経路ごとに希望道路条件で特定される環境情報に対応する重み付け値の総和から最適経路を検索できるが、同じエリア（地理的範囲）の異なるノード数を有する複数のネットワーク地図を利用する場合にリンクの重み付けの加算ができないという問題がある。ここで、ネットワーク地図とは、ノードおよびリンクからなり、所定の要因についてリンクごとにリンクコストが決められたものである。従って、複数のネットワーク地図は、それぞれ異なる要因についてリンクコストが決められている。
【０００５】
具体的には、複数のネットワーク地図を利用したリンクコストの加減算を行うには、各ネットワーク地図のノードの位置や数が同じである必要があった。つまり、ネットワーク地図によってノードの密度が異なる場合、リンクコストを計算することができない。また、それに対応するために、ノードの位置や数が異なった場合であっても、検索条件を考慮しながら適切に経路探索する方法を提案する必要があった。さらに、時間の経過に伴って変化するリンクコストを最適経路探索手法に取り入れた場合に、検索開始時のリンクコストだけを適用しており、必ずしも有効な経路探索ができていなかった。
【０００６】
そこで、本発明は、前記問題に鑑み、経路探索において、ノードの位置や数が異なる複数のネットワーク地図や時間的に変化するコストを有するネットワーク地図を有効に利用する手段を提供することを課題とする。
【課題を解決するための手段】
【０００７】
前記課題を解決する本発明は、移動体に設置されまたは人に所持され、少なくとも出発地点情報、目的地点情報および検索条件情報を含む経路探索の要求メッセージを送信し、その経路探索の結果情報を受信し、表示する端末と、要求メッセージを受信し、その要求メッセージに含まれる出発地点情報、目的地点情報および検索条件情報に従って経路探索を行い、その経路探索の結果情報を前記端末に送信する地図管理サーバとがネットワークを介して接続されて構成されるナビゲーションシステムであって、要求メッセージが、出発予定時刻を含み、地図管理サーバが、検索条件ごとに、その検索条件に係る評価値を示すコストを有する、ノードおよび２つのノード間の接続経路を示すリンクの少なくとも一方を含むネットワーク地図データであって、コストを時間帯に対応付けたものを有し、検索条件情報に含まれる検索条件を満たす経路を探索するために、所定のネットワーク地図データ内のノードをリンクに従って出発地点から目的地点に辿る場合に、所定のノードから次のノードに進むのに通過するリンクを選択するときに、出発予定時刻に出発地点からの経過時間を加算した時刻を含む時間帯のコストを参照することを特徴とする。
【０００８】
また、本発明は、ナビゲーションシステムであって、地図管理サーバが、検索条件ごとに、その検索条件に係る評価値を示すコストを有する、ノードおよび２つのノード間の接続経路を示すリンクの少なくとも一方を含むネットワーク地図データを有するとともに、検索条件情報に含まれる複数の検索条件を満たす経路を探索するために、その検索条件に係る複数のネットワーク地図データ内のコストを加算する場合に、ネットワーク地図データ間のノードの位置または数が異なるときに、対応するノードのないネットワーク地図データにダミーノードを設定し、そのダミーノードのコスト、または、そのダミーノードと他のノードとの間のリンクのコストを生成することを特徴とする。なお、本発明は、地図管理サーバを含む。
【発明の効果】
【０００９】
本発明によれば、経路探索において、ノードの位置や数が異なる複数のネットワーク地図や時間的に変化するコストを有するネットワーク地図を有効に利用することができる。これによれば、時間的に変化する複数の検索条件を用いて経路探索を行うことができる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００１１】
≪第１の実施の形態≫
（システムの構成と概要）
まず、本発明の第１の実施の形態を説明する。図１は、第１の実施の形態に係るナビゲーションシステムの構成を示すブロック図である。ナビゲーションシステム１は、ナビゲーション機能付き自転車（以下、ナビ付き自転車）１００および地図管理センタ２０３を含んで構成される。ナビ付き自転車１００は、通常の自転車１０１に自転車用のナビゲーション機能を有する端末１０２が搭載された構成になっている。端末１０２は、ＧＰＳ（Global Positioning Systems）衛星１０３との通信を行うことによって自らの測位を可能とする。
【００１２】
また、端末１０２は、ネットワーク２０６を介して地図管理センタ２０３と接続され、地図管理センタ２０３に経路探索を要求し、その経路探索の結果を受け取る。ネットワーク２０６は、無線を含む専用回線または公衆回線により実現される。
【００１３】
地図管理センタ２０３は、地図サーバ２０４および地図データベース２０５を含んで構成される。地図サーバ２０４は、ナビ付き自転車１００からネットワーク２０６を介して経路探索の要求メッセージを受信する。そして、地図データベース２０５を使用して経路探索計算を実施し、その経路探索の結果情報をネットワーク２０６経由でナビ付き自転車１００の端末１０２に送信する。地図データベース２０５は、全国の地図データを格納するデータベースである。なお、地図サーバ２０４は、サーバ用コンピュータによって実現される。また、地図データベース２０５は、ハードディスク装置などの不揮発性記憶装置に構築される。
【００１４】
図２は、第１の実施の形態に係る端末の内部構成を示す図である。端末１０２は、表示部１１０、入力装置１１１、内部時計１１２、電子コンパス１１３、ＧＰＳ受信機１１４、ＧＰＳアンテナ１１５、制御部１１６、通信部１１７、通信アンテナ１１８、バッテリ１１９、地図データ記憶部１２０、ＲＡＭ（Random Access Memory）１２１、ＲＯＭ（Read Only Memory）１２２、ＩＣタグ１２３および電子鍵１２４を含んで構成される。
【００１５】
表示部１１０は、地図データや探索された経路などを表示する画面であり、液晶ディスプレイなどによって実現される。入力装置１１１は、経路探索表示の検索条件入力などを行う装置であり、キーボードやタッチパネルなどによって実現される。内部時計１１２は、現在の時刻を保持、更新しており、その時刻は、制御部１１６によって表示部１１０に表示される。電子コンパス１１３は、現在の端末１０２、ひいてはナビ付き自転車１００が向く方向を保持、更新しており、その方向は、制御部１１６によって表示部１１０に表示される。ＧＰＳ受信機１１４は、ＧＰＳアンテナ１１５と接続され、ＧＰＳアンテナ１１５を介してＧＰＳ衛星１１５からの電波信号を受信し、その電波信号に従って測位演算を行って、ナビ付き自転車１００の位置を特定する。
【００１６】
制御部１１６は、端末１０２内の各部と接続され、端末１０２全体を制御する。制御部１１６は、ＣＰＵ（Central Processing Unit）が所定のメモリにロードされたプログラムを実行することによって実現される。通信部１１７は、ネットワーク２０６（図１参照）に接続するための信号処理を行い、通信アンテナ１１８を介して地図サーバ２０４と通信することにより、経路探索の要求メッセージの送受信や地図データのダウンロードを行うことが可能になる。地図サーバ２０４から受信した経路探索の結果情報は、表示部１１０に地図データと重畳して表示される。
【００１７】
バッテリ１１９は、端末１０２の電源であり、ナビ付き自転車１００（図１参照）の車輪が回転することにより充電される。地図データ記憶部１２０は、経路探索の処理に利用される地図データを格納するものであり、具体的には、フラッシュメモリやハードディスク装置などの不揮発性記憶装置である。地図データ記憶部１２０は、地図サーバ２０４を介して地図データベース２０５からダウンロードした地図データを格納する。ＲＡＭ１２１は、制御部１１６のプログラムのワークエリアなどに使用される一時的な記憶領域である。ＲＯＭ１２２は、端末１０２の電源投入時にロードが必要なプログラムが格納される、書き換え不可の固定的な記憶領域である。ＩＣタグ１２３は、ナビ付き自転車１００の固有ＩＤを持つ。さらに、ナビ付き自転車１００ごとにそれぞれ電子鍵１２４が付属する。電子鍵１２４を端末１０２に挿入することによって、端末１０２の電子錠が解除され、端末１０２の機能が使用可能となる。なお、端末１０２は、自転車１０１本体から取り外しが可能で、歩行する場合でも使用することができる。
【００１８】
図３は、第１の実施の形態に係る液晶ディスプレイを説明する図である。ナビ付き自転車１００の端末１０２は、利用者がナビ付き自転車１００に乗ったときに端末１０２の液晶ディスプレイ３０１が見やすい位置に設置される。液晶ディスプレイ３０１は、表示部１１０（図２参照）の一例である。液晶ディスプレイ３０１に表示される地図画面３１０には、現在地３１１、建物３１２、道路３１３、方角３１４、縮尺３１５などが表示される。なお、地図画面３１０の地図データは、端末１０２の地図データ記憶部１２０に記憶されているものであり、必要に応じてさらに地図データベース２０５からダウンロードされるものとする。
【００１９】
現在地３１１は、ナビ付き自転車１００の現在の位置を示し、地図画面３１０の中心に表示される。換言すれば、現在地３１１が地図画面３１０の中心に位置付くように、周辺の地図の表示範囲が調整される。建物３１２は、ランドマーク情報（位置を知る目印）であり、必ずしも建物でなくてもよく、例えば公園や運動場などの施設であってもよい。建物３１２は、後記する検索条件入力画面４０１に出発地点や目的地点を入力する際に利用することができる。すなわち、建物３１２を選択することによって、出発地点や目的地点を特定することができる。道路３１３は、ナビ付き自転車１００が通行可能な道路である。方角３１４は、端末１０２の電子コンパス１１３から取得されたナビ付き自転車１００の向く方角である。縮尺３１５は、現在表示されている地図の縮尺である。この縮尺３１５は、その比率の切り替えが可能である。
【００２０】
図４は、第１の実施の形態に係る検索条件入力画面を示す図である。検索条件入力画面４０１は、端末１０２が所望の経路を検索する条件を入力するために液晶ディスプレイ３０１（図３参照）に表示する画面である。検索条件入力画面４０１には、出発地点入力欄４０２、目的地点入力欄４０３、検索条件入力欄４０４、検索設定値入力欄４０５、検索設定値単位表示欄４０６および出発予定時刻入力欄４０７がある。
【００２１】
出発地点入力欄４０２は、検索したい経路の出発地点の緯度、経度および高度を入力する欄である。目的地点入力欄４０３は、検索したい経路の目的地点の緯度、経度および高度を入力する欄である。出発地点や目的地点を入力する場合、例えば、検索条件入力画面４０１の「出発地点」のアイコンを選択すると、ランドマークの一覧や地図画面３１０（図３参照）が表示されて、その表示されたものを選択することによって、選択した地点の緯度、経度および高度が入力されるものとする。また、出発地点については、制御部１１６によって、ＧＰＳ受信機１１４が受信した測位信号から現在の位置を求め、その位置である緯度、経度および高度が入力されるようにしてもよい。なお、地点の位置として高度を含めることによって、地点間の勾配を算出することができるので、例えば、勾配の少ない経路を検索することができるようになる。
【００２２】
検索条件入力欄４０４は、経路の検索条件を選択する欄である。選択可能な検索条件には、最短距離、最短時間だけでなく、走行距離、走行時間、消費カロリ、交通量（履歴）、事故発生（履歴）、犯罪発生（履歴）、見通しのよいルート（カーブ、曲がるルートが少ない、電灯の設置状況など）、道路の幅、段差除外ルート情報などがある。走行距離、走行時間または消費カロリを選択した場合には、その単位を含めて指定する。なお、端末１０２には、移動体が自転車、歩行者、自動車のいずれかであるかが予め設定されており、その設定された移動体に合わせて選択可能な検索条件が検索条件入力欄４０４に表示される。例えば、移動体が自転車や歩行者である場合には、自動車ではほとんど問題にならない「消費カロリが少ない」や「上り坂がない」などの検索条件が表示される。また、検索条件入力欄４０４に検索条件が選択されない場合には、デフォルトとして最短距離または最短時間を検索条件とする。
【００２３】
検索設定値入力欄４０５は、検索条件入力欄４０４で選択した条件によって必要な設定値を入力する欄である。例えば、検索条件入力欄４０４で走行距離、走行時間または消費カロリを選択した場合には、検索設定値入力欄４０５に希望する値を設定する。検索設定値入力欄４０５に設定値が入力された場合には、検索結果の最小値ではなく、設定された値に最も近い条件のルートを検索する。検索設定値単位表示欄４０６は、検索設定値入力欄４０５に設定された値の単位を表示する欄である。この検索設定値単位表示欄４０６には、検索条件入力欄４０４で指定した単位が表示される。出発予定時刻入力欄４０７は、出発地点入力欄４０２に入力した地点から実際に出発する予定になっている時刻を入力する欄である。「出発予定時刻」は、後記するように、時間的に変化するリンクコストを有するネットワーク地図を有効に利用するために必要な情報である。逆に言えば、リンクコストが固定であるネットワーク地図だけを利用する場合には、不要な情報である。
【００２４】
これによれば、出発地点入力欄４０２からの目的地点入力欄４０３までの経路探索を、最短距離、最短時間を基本として行うとともに、最短距離、最短時間以外の検索条件を選択することによって多機能な検索を行うことができる。
【００２５】
（システムの処理）
次に、第１の実施の形態に係るナビゲーションシステムについて説明する（適宜図１ないし図４参照）。図５は、ナビゲーションシステムの経路探索処理を示すフローチャートである。地図サーバ２０４は、ダイクストラ法に代表される最適経路探索手法を実装する。利用者は、ナビ付き自転車１００の端末１０２を利用することで複数の条件を考慮した最適経路探索の結果を得ることができる。
【００２６】
経路探索を実行する場合、最初に、端末１０２は目的地点を設定する（ステップＳ５１０）。具体的には、端末１０２の制御部１１６が、まず、利用者の操作により入力装置１１１から経路探索を行いたい旨を入力し、その入力に対応して検索条件入力画面４０１を表示部１１０（液晶ディスプレイ３０１）に表示する。そして、利用者が検索条件入力画面４０１の目的地点入力欄４０３に入力した目的地点を、後で地図サーバ２０４に送信する目的地情報に設定する。
【００２７】
次に、端末１０２は検索条件を設定する（ステップＳ５１１）。具体的には、端末１０２の制御部１１６が、利用者が検索条件入力画面４０１の検索条件入力欄４０４に入力した検索条件および検索設定値入力欄４０５に設定した値を、後で地図サーバ２０４に送信する検索条件情報に設定する。
【００２８】
続いて、端末１０２は現在地点を設定する（ステップＳ５１２）。具体的には、まず、端末１０２のＧＰＳ受信機１１４が、ＧＰＳ衛星１０３からＧＰＳアンテナ１１５を介して測位信号を受信し、その測位信号を制御部１１６に送信する。そして、制御部１１６が、ＧＰＳ受信機１１４から受信した測位信号に基づいて端末１０２の現在地点（緯度、経度および高度）を算出し、その現在地点を、後で地図サーバ２０４に送信する出発地情報に設定する。なお、出発地情報は、必ずしも現在地点でなくてもよく、利用者が検索条件入力画面４０１の出発地点入力欄４０２に入力したものを設定してもよい。これは、現在地点ではない、任意の出発地点からの目的地点までの経路を検索したい場合に有効である。なお、出発予定時刻入力欄４０７に入力された出発予定時刻を出発地情報に含めることもできる。
【００２９】
端末１０２は、ステップＳ５１０ないしステップＳ５１２で設定した情報、すなわち、出発地情報、目的地情報および検索条件情報（以下、検索情報という）を含む経路探索の要求メッセージを地図サーバ２０４に送信する（ステップＳ５１３）。具体的には、端末１０２の制御部１１６が、要求メッセージを通信部１１７に送信する。そして、通信部１１７が、制御部１１６から受信した要求メッセージを通信アンテナ１１８から送信する。通信アンテナ１１８から送信された要求メッセージは、ネットワーク２０６を通じて地図サーバ２０４に到達する。
【００３０】
地図サーバ２０４は、端末１０２からネットワーク２０６経由で検索情報、すなわち、出発地情報、目的地情報および検索条件情報を含む経路探索の要求メッセージを受信する（ステップＳ５２１）。次に、その検索情報を元に最適経路探索を実施する（ステップＳ５２２）。続いて、その検索結果の経路情報に合う地図情報を検索する（ステップＳ５２３）。そして、経路情報および地図情報を端末１０２に送信する（ステップＳ５２４）。
【００３１】
端末１０２は、経路情報および地図情報を受信し（ステップＳ５１４）、それらを表示する（ステップＳ５１５）。具体的には、まず、端末１０２の通信部１１７が、地図サーバ２０４からネットワーク２０６および通信アンテナ１１８経由で経路情報および地図情報を受信し、それらの情報を制御部１１６に送信する。そして、制御部１１６が、通信部１１７から経路情報および地図情報を受信し、それらの情報を表示部１１０に表示する。また、受信した地図情報を地図データ記憶部１２０に記憶する。これによって、利用者は、先に端末１０２の検索条件入力画面４０１に入力した条件に合う経路を、その周辺の地図とともに参照することができる。
【００３２】
図６は、第１の実施の形態に係るネットワーク地図を説明する図である。地図管理センタ２０３の地図データベース２０５に格納される地図データには、ネットワーク地図が含まれている。ネットワーク地図は、ノード６００およびリンク６０１を有する。ノード６００のＡないしＩは、位置情報（緯度、経度および高度）というコスト（重み付け）を持つ。地図上では交差点や道路の行き止まりなどを表す。なお、ノード６００は、位置情報だけでなく、例えば、その地点における犯罪発生率や事故発生率などのコストを持つようにしてもよい。リンク６０１は、２つのノード６００の間を結ぶ線であり、地図上の道路を表す。リンクコスト６０２は、リンク６０１に関連付けられる数値であり、リンク６０１に対するコストを意味する。なお、ノード６００のコストおよびリンクコスト６０２は、最適経路探索を実施するときに利用され、各検索条件に対応するものである。
【００３３】
ネットワーク地図のリンクコスト６０２は、次に示す要素ごとに値を持つ。すなわち、距離、傾斜、移動体（歩行者、自転車、自動車など）、消費カロリ、明るい道路、犯罪発生率、道幅、渋滞状況、事故発生率、環境（川沿い、海岸、桜通りなど）などの要素である。また、複数のリンクやノードのコストから新たなコストが計算可能となる。例えば、２つのノードの緯度、経度および高度（ノードのコスト）から、そのノード間の距離、方角および傾斜（リンクコスト）を計算することができる。
【００３４】
図７は、第１の実施の形態に係るネットワーク地図のレイヤ構造を示す図である。ネットワーク地図は、レイヤ７０１、レイヤ７０２、・・・、レイヤ７０ｎのように複数のレイヤを持つ階層構造になっている。複数の条件を考慮した最適経路探索を実施する際は、複数のレイヤを持つネットワーク地図を利用して行う。図７に示すように、例えば、レイヤ７０１は渋滞状況を示す渋滞マップであり、レイヤ７０２は犯罪発生率を示す犯罪マップであり、レイヤ７０ｎは事故発生率を示す事故マップである。
【００３５】
図８は、第１の実施の形態に係るリンクコストが変化するネットワーク地図を示す図である。図８に示すように、ネットワーク地図８００および８０１において、リンクコストが時間の経過に伴って変化する。すなわち、時刻ｔ０におけるネットワーク地図８００と時刻ｔ１におけるネットワーク地図８０１とでリンクコストの値が異なる箇所（ネットワーク地図８０１で下線のある数値）がある。このように、所定のネットワーク地図において、一部のコストが変化してもよいし、全部のコストが変化してもよい。また、図８では、リンクコストが時間的に変化する例を示したが、ノードのコスト、または、リンクおよびノードのコストが時間的に変化するようなネットワーク地図であってもよい。
【００３６】
このようなネットワーク地図の例を以下に示す。例えば、渋滞マップでは、午前９時ないし１１時の時間帯（午前中）はリンクコストが１０であるのに対して、午前１時ないし４時の時間帯（夜半ないし明け方）はリンクコストが２であることが考えられる。また、犯罪マップでは、午前１０時ないし午後３時の時間帯（昼間）はリンクコストが２であるのに対して、午後９時ないし午後１２時の時間帯（夜間）はリンクコストが９であることが考えられる。
【００３７】
図９は、第１の実施の形態に係るリンクコストが変化するネットワーク地図に対して経路探索を行う処理を示すフローチャートである。すなわち、最適経路探索手法において、時間の経過に伴ってリンクコストが変化するネットワーク地図を適用可能な検索手法について示すものである。なお、図９のフローチャートは、図５のステップＳ５２２の処理を詳細化したものである。
【００３８】
地図サーバ２０４は、まず、ネットワーク地図中の出発点のノードに隣接するノードのうち、出発点ノードと隣接ノードとの間のリンクコストが最小の値を持つ隣接ノードにマークをつけて確定する（ステップＳ９０１）。このとき、最初は出発点ノードを基準として処理するが、２回目以降はステップＳ９０２でマークを付けたノードを基準とし、隣接ノードのうちマークの付いていないノードを選択する。また、参照するリンクコストは、最初は出発予定時刻に対応する値であるが、２回目以降はステップＳ９０３で更新された値である。
【００３９】
次に、マークの付いたノードからの隣接するノードまでのリンクコストを参照し、マークの付いていないノードのリンクコストが最小の値を持つノードをマークして確定する（ステップＳ９０２）。続いて、先のリンクコストに対応する時刻に経過時間を加算し、その加算した結果の時刻に対応した各リンクのリンクコストを更新する（ステップＳ９０３）。そして、目的点ノードにマークが付いているか否かを判断する（ステップＳ９０４）。付いていなければ（ステップＳ９０４のＮｏ）、ステップＳ９０１に戻ってステップＳ９０１ないしステップＳ９０３の処理を繰り返し実行する。付いていれば（ステップＳ９０４のＹｅｓ）、経路探索の処理を終了する。
【００４０】
次に、図９のフローチャートの処理を、図８のネットワーク地図に適用した場合について説明する。ネットワーク地図８００および８０１において、出発点ノードをノードＡとし、目的点ノードをノードＩとする。まず、地図サーバ２０４は、ネットワーク地図８００を参照して、ノードＡからの隣接するノードＢ、ＤおよびＥまでのリンクのリンクコストを比較して、最小値である１のリンクコストを持つノードＢにマークを付ける（ステップＳ９０１）。次に、マークの付いたノードＢからの、マークの付いていない隣接するノードＣ、ＥおよびＦまでのリンクのリンクコストを比較して、最小値である３のリンクコストを持つノードＥおよびＦにマークを付ける（ステップＳ９０２）。そして、ネットワーク地図８００の時刻ｔ０に、ノードＡからノードＢを経由してノードＥまたはＦに達したときの経過時間を加算して時刻ｔ１を求め、その求めた時刻ｔ１に対するネットワーク地図８０１を参照することとする。これが、リンクコストの更新（ステップＳ９０３）に相当する。続いて、目的点ノードであるノードＩにマークが付いているか否かをチェックする（ステップＳ９０４）。
【００４１】
ノードＩにはマークが付いていないので（ステップＳ９０４のＮｏ）、ステップＳ９０１に戻ってノードＥおよびＦについて経路探索を行う。ネットワーク地図８０１によれば、ノードＥについてはリンクコストが１であるノードＨをマークし、ノードＦについてはリンクコストが３であるノードＩをマークする（ステップＳ９０１）。この時点で、目的地Ｉに到達したことになる。さらに、ノードＨについてリンクコストが３であるノードＩをマークする（ステップＳ９０２）。ここでも、目的地Ｉに到達したことになる。続いて、リンクコストの更新を行い（ステップＳ９０３）、目的点ノードであるノードＩにマークが付いているか否かをチェックする（ステップＳ９０４）。マークが付いているので（ステップＳ９０４のＹｅｓ）、経路探索処理を終了する。
【００４２】
図９のフローチャートでは、ステップＳ９０１およびステップＳ９０２の２回の経路探索処理で所定の時刻における１組のリンクコストを参照したが、１回の経路探索処理ごとに１組のリンクコストを参照した後、すぐにリンクコストを経過時間に合わせて更新するようにしてもよい。また、所定のノードから次のノードを確定するために、所定のノードと隣接するノードとの間のリンクコストだけを参照したが、少なくとも出発点ノードからの目的点ノードまでの最小リンク数を有する複数の経路についてリンクコストの合計値を算出し、比較するとともに、その合計値の算出に時間的に変化するリンクコストを反映するようにしてもよい。これによれば、時間的に変化するリンクコストを、より精度よく経路探索に反映させることができるので、より精確な最適経路探索を実現することが可能になる。
【００４３】
続いて、図１０を参照して、ノードの位置や数が異なる複数のネットワーク地図間でコストの加算を行う処理について説明する。なお、この処理は、地図サーバ２０４において、端末１０２から受信した経路探索の要求メッセージに複数の検索条件が含まれる場合に行われる。
【００４４】
図１０（ａ）は、渋滞マップのノードが事故マップのノードに比べて少ない場合の処理を示す図である。渋滞マップＭ１は、車両の渋滞の程度をリンクのコストとするネットワーク地図である。一方、事故マップＭ２は、事故発生率（例えば、月あたりの事故発生回数）をノードのコストとするネットワーク地図である。渋滞マップＭ１と事故マップＭ２とを比較すると、事故マップＭ２にはノードＱがあるが、渋滞マップＭ１にはない。そこで、渋滞マップＭ１にダミーノードＱを設定する。この場合、ノードＰおよびダミーノードＱ、ならびに、ダミーノードＱおよびノードＲの間のリンクコストを特定する必要があるが、各ノードの位置情報は分かっているので、それぞれの距離を算出し、ノードＰとノードＲとの間のリンクコスト４を距離の比率に応じて分けることにする。渋滞マップＭ３では、ダミーノードＱは、ノードＰおよびノードＲの中間地点にあるものとして、リンクのコスト４を２分の１に分けている。そして、事故マップＭ２および渋滞マップＭ３のコストを加算（重畳）することによって、渋滞・事故マップＭ４が生成される。
【００４５】
図１０（ｂ）は、事故マップのノードが渋滞マップのノードに比べて少ない場合の処理を示す図である。事故マップＭ５と渋滞マップＭ６とを比較すると、渋滞マップＭ６にはノードＴがあるが、事故マップＭ５にはない。そこで、事故マップＭ５にダミーノードＴを設定する。この場合、ダミーノードＴのコストを特定する必要があるが、各ノードの位置情報は分かっているので、ダミーノードＴから所定の距離範囲内にある最寄りのノードのコストと同じ値を設定することにする。事故マップＭ７では、ノードＵがダミーノードＴに近く、所定の距離範囲内にあるものとして、ダミーノードＴのコストをノードＵのコスト４にしている。そして、渋滞マップＭ６および事故マップＭ７のコストを加算（重畳）することによって、渋滞・事故マップＭ８が生成される。
【００４６】
図１０（ａ）では渋滞マップＭ１のリンクコストを分けるのに距離の比率を用いたり、図１０（ｂ）では事故マップＭ５のダミーノードのコストを特定するのに最寄りのノードのコストを設定したりしたが、その他のコストの特定方法であってもよい。例えば、ダミーノードのコストを特定するのに、ダミーノードからの所定の距離範囲内にあるすべてのノードのコストの平均値を設定するようにしてもよい。これは、例えば、位置情報をノードのコストとし、ノード間の距離や勾配をリンクのコストとする基本マップ（基本的なネットワーク地図）において、所定のノードの緯度、経度は測定できたが、高度は測定できなかった場合（位置情報が不完全な場合）に、他のマップとコストの加算を行うときに、他のマップにあって基本マップにないノードの高度を推定するのに有効であると考えられる。
【００４７】
≪第２の実施の形態≫
次に、本発明の第２の実施の形態を説明する。なお、第１の実施の形態と重複する説明は省略する。
【００４８】
（システムの構成と概要）
図１１は、第２の実施の形態に係るナビゲーションシステムの構成を示すブロック図である。ナビゲーションシステム２は、ナビ付き自転車１００、ＧＰＳ機能付き携帯端末（以下、ＧＰＳ端末という）１１０４および管理センタ１１０５を含んで構成される。ナビ付き自転車１００と管理センタ１１０５とは、ネットワーク１１０８を介して接続される。ＧＰＳ端末１１０４と管理センタ１１０５とは、ネットワーク１１１１を介して接続される。なお、ネットワーク１１０８およびネットワーク１１１１は、それぞれ無線を含む専用回線および公衆回線によって実現される。
【００４９】
ナビ付き自転車１００およびＧＰＳ衛星１０３の構成は、第１の実施の形態と同様である。端末１０２は、ネットワーク１１０８を介して管理センタ１１０５と通信を行う。ここでは、特に、ＧＰＳ衛星１０３から受信した測位信号に基づいて、自らの位置を測定し、その測定した位置情報を定期的に管理センタ１１０５に通知する。ＧＰＳ端末１１０４は、ナビ付き自転車１１０１の場所をリモート検索可能とする端末である。また、ＧＰＳ衛星１０３から受信した測位信号に基づいて、自らの位置を測定することができる。ＧＰＳ端末１１０４は、ネットワーク１１１１を介して管理センタ１１０５と通信を行う。ここでは、特に、管理センタ１１０５に要求して、ナビ付き自転車１００（の端末１０２）の位置情報を受信する。なお、ＧＰＳ端末１１０４は、端末１０２と同様の構成（図２参照）を持つものとする。
【００５０】
管理センタ１１０５は、管理サーバ１１０６および利用者情報データベース１１０７からなる。管理サーバ１１０６は、ナビ付き自転車１００の端末１０２からその位置情報を定期的に受信し、利用者情報データベース１１０７に格納する。また、その格納された位置情報をＧＰＳ端末１１０４からの要求に応じて送信する。なお、管理サーバ１１０６は、サーバ用コンピュータによって実現される。また、利用者情報データベース１１０７は、ハードディスク装置などの不揮発性記憶装置に構築される。
【００５１】
この構成によれば、ＧＰＳ端末１１０４は、ネットワーク１１１１を介して管理センタ１１０５の管理サーバ１１０６にアクセスして、利用者情報データベース１１０７に格納されるナビ付き自転車１００の位置情報を入手できる。そして、ＧＰＳ端末１１０４は、ナビ付き自転車１００の端末１０２と同様の処理（図５に示す端末１０２の処理）をすることによって、自らの位置からのナビ付き自転車１００までの経路探索を行うことができる。
【００５２】
（システムの処理）
図１２は、第２の実施の形態に係るナビ付き自転車の登録処理を示すフローチャートである。この処理は、ナビ付き自転車１００を購入した場所において、端末１０２から管理センタ１１０５の管理サーバ１１０６に対して利用者情報の登録を行うものである。まず、利用者の操作により端末１０２の電源が投入され、端末１０２がメニュー画面（図示せず）を表示部１１０に表示し、さらに利用者の操作によりメニュー画面から「利用者情報の登録」が選択される（ステップＳ１２０１）。次に、端末１０２は、管理サーバ１１０６に登録する利用者情報（所有者の氏名、連絡先などの所有者情報、車種、購入日時、登録番号などの自転車情報）の入力を促す画面を表示部１１０に表示する（ステップＳ１２０２）。なお、ナビ付き自転車１００の登録番号は、予め端末１０２のＩＣタグ１２３（図２参照）に記録されているものとする。
【００５３】
利用者情報の入力が終了すると、端末１０２は、表示部１１０に「送信登録」ボタンを表示し、それが利用者の操作により選択されると、管理サーバ１１０６にアクセスして、入力した利用者情報の登録が行われる（ステップＳ１２０３）。このとき、管理センタ１１０５では、管理サーバ１１０６が、端末１０２からネットワーク１１０８を介して利用者情報を受信し、その受信した利用者情報を利用者情報データベース１１０７に格納する。利用者情報の登録が終了すると、端末１０２は、ナビ付き自転車１００の登録番号を表示部１１０に表示する（ステップＳ１２０４）。これによれば、利用者は、管理サーバ１１０６にナビ付き自転車１００を登録するとともに、登録番号を記憶することによって、ナビ付き自転車１００の盗難に備えることができる。
【００５４】
図１３は、第２の実施の形態に係るナビ付き自転車の盗難時における車両発見処理を示すフローチャートである。まず、要求者の操作により、ＧＰＳ端末１１０４は、盗難されたナビ付き自転車１００の登録番号、氏名などの情報を、管理サーバ１１０６に連絡し、ナビ付き自転車１００の位置検索を要求する（ステップＳ１３０１）。管理サーバ１１０６は、これらの情報から、要求者が所有者であるか否かを確認する（ステップＳ１３０２）。この確認は、登録番号や氏名などの組合せが、利用者情報データベース１１０７に格納されている利用者情報の中にあるか否かを検索することによって行われる。要求者が所有者であることが確認できたら、管理サーバ１１０６は、ナビ付き自転車１００の端末１０２から最後に受信した位置情報をＧＰＳ端末１１０４に送信する（ステップＳ１３０３）。
【００５５】
図１４は、第２の実施の形態に係るナビ付き自転車が放置車両となった場合の所有者特定処理を示すフローチャートである。まず、ナビ付き自転車１００の端末１０２に内蔵または付設されたＩＣタグ１２３に読み取り機（図示せず）をかざすことで、その読み取り機がＩＣタグに記録された登録番号を読み取る（ステップＳ１４０１）。なお、読み取り機は警察などが所有していることを想定する。そして、その読み取り機から管理サーバ１１０６に、読み取った登録番号で登録されている所有者を問い合わせる（ステップＳ１４０２）。これにより、ナビ付き自転車１００の所有者を特定することができる。このような問い合わせは、主に警察などによって行われることを想定する。
【００５６】
以上本発明の実施の形態について説明したが、図１に示す端末１０２および地図管理サーバ２０４、図１１に示す端末１０２、ＧＰＳ端末１１０４および管理サーバ１１０６のそれぞれで実行されるプログラムをコンピュータによる読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、本発明の実施の形態に係るナビゲーションシステムが実現されるものとする。なお、プログラムをインターネットなどのネットワーク経由でコンピュータシステムに提供するようにしてもよい。
【００５７】
≪その他の実施の形態≫
以上本発明について好適な実施の形態について一例を示したが、本発明は前記実施の形態に限定されず、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、以下のような実施の形態が考えられる。
（１）前記実施の形態では、自転車を対象としたナビゲーションシステムについて説明したが、その他の移動体であっても適用可能である。例えば、自動車などの車両であってもよいし、歩行者であってもよい。
（２）端末１０２の表示部１１０に、地図データの位置に対応するユーザレイヤを持つようにしてもよい。ユーザレイヤには、利用者がタッチパネルなどによって自由にアイコンや文字などを描画することができる。これによれば、地図の表示範囲が変わると同時に、表示されるユーザレイヤも変わるので、あたかも地図上に描画したように利用することができる。
【図面の簡単な説明】
【００５８】
【図１】第１の実施の形態に係るナビゲーションシステムの構成を示すブロック図である。
【図２】第１の実施の形態に係る端末の内部構成を示す図である。
【図３】第１の実施の形態に係る液晶ディスプレイを説明する図である。
【図４】第１の実施の形態に係る検索条件入力画面を示す図である。
【図５】第１の実施の形態に係るナビゲーションシステムの経路探索処理を示すフローチャートである。
【図６】第１の実施の形態に係るネットワーク地図を説明する図である。
【図７】第１の実施の形態に係るネットワーク地図のレイヤ構造を示す図である。
【図８】第１の実施の形態に係るリンクコストが変化するネットワーク地図を示す図である。
【図９】第１の実施の形態に係るリンクコストが変化するネットワーク地図に対して経路探索を行う処理を示すフローチャートである。
【図１０】第１の実施の形態に係るノードの位置や数が異なる複数のネットワーク地図間でコストの加算を行う処理を示す図であり、（ａ）は渋滞マップのノードが事故マップのノードに比べて少ない場合の処理を示し、（ｂ）は事故マップのノードが渋滞マップのノードに比べて少ない場合の処理を示す。
【図１１】第２の実施の形態に係るナビゲーションシステムの構成を示すブロック図である。
【図１２】第２の実施の形態に係るナビ付き自転車の登録処理を示すフローチャートである。
【図１３】第２の実施の形態に係るナビ付き自転車の盗難時における車両発見処理を示すフローチャートである。
【図１４】第２の実施の形態に係るナビ付き自転車が放置車両となった場合の所有者特定処理を示すフローチャートである。
【符号の説明】
【００５９】
１      ナビゲーションシステム
１０１  自転車（移動体）
１０２  端末
２０４  地図サーバ（地図管理サーバ）
２０６  ネットワーク
６００  ノード
６０１  リンク
６０２  リンクコスト
【図１】
2006275922.tif 000003
【図２】
2006275922.tif 000004
【図３】
2006275922.tif 000005
【図４】
2006275922.tif 000006
【図５】
2006275922.tif 000007
【図６】
2006275922.tif 000008
【図７】
2006275922.tif 000009
【図８】
2006275922.tif 000010
【図９】
2006275922.tif 000011
【図１０】
2006275922.tif 000012
【図１１】
2006275922.tif 000013
【図１２】
2006275922.tif 000014
【図１３】
2006275922.tif 000015
【図１４】
2006275922.tif 000016