(57)【要約】【課題】本発明の目的は、推奨経路をユーザーへ有用に提示することにある。【解決手段】経路探索は、目的地並びに局所的な地図情報及び交通情報を基に、局所的な経路探索を繰り返し、目的地に至る複数経路を並行して生成する。経路表示は、経路探索による局所的な経路探索結果を受けて、探索の終了した範囲の経路を順次表示する。従って、経路探索に必要な情報がネットワーク接続されたセンタ側からダウンロードされるものにおいても、かかる情報のダウンロードと並行して経路探索及び探索済み経路の表示を実行することが可能である。【選択図】  図１
2005017052.tif 000002
【特許請求の範囲】
【請求項１】
地図上に現在地，目的地、及び、推奨経路を表示し、自車を誘導するナビゲーションの表示方法に於いて、
現在地から目的地を目指して複数本の推奨経路を計算するに際し、前記推奨経路の部分である局所経路の経路探索を繰り返すことによって前記目的地に至る前記複数本の推奨経路を並行して計算し、
経路探索の終了した範囲の前記局所経路を順次表示することによって、その複数本の推奨経路が、前記目的地を目指して伸びていくように表示することを特徴とするナビゲーションの表示方法。
【請求項２】
請求項１に於いて、
前記局所経路を求めるための探索領域として局所経路探索領域を前記現在地の周囲に設定すると共に、交通状況を加味して当該局所経路探索領域内で前記局所経路を計算し、
当該計算された局所経路の終端の周囲に新たに局所経路探索領域を設定すると共に、当該新たに設定された局所経路探索領域内で交通状況を加味して新たに局所経路を計算し、
前記局所経路探索領域の新たな設定と当該領域内での交通状況を加味した局所経路の新たな計算を目的地に辿り着くまで繰り返し、
前記各局所経路が計算される毎に当該局所経路を表示することによって、前記推奨経路を生成し、
前記複数本の推奨経路について、前記設定，計算，表示を並行して行うことで、その複数本の推奨経路が、前記目的地を目指して伸びていくように表示することを特徴とするナビゲーションの表示方法。
【請求項３】
請求項２に於いて、
前記推奨経路の部分に高速道路または有料道路が含まれている場合、高速道路または有料道路以外の道路のときと比較して前記局所経路探索領域を広く設定することを特徴とするナビゲーションの表示方法。
【請求項４】
請求項２に於いて、
前記地図情報と前記交通情報に基づいて、前記局所経路の終端からの到達容易性と前記目的地までの到達容易性とを考慮した局所ポテンシャル場を生成すると共に、局所経路探索領域を設定し、
当該局所経路探索領域内に於いて前記局所ポテンシャル場の前記各到達容易性が高い方向の局所経路を局所経路として選択し、
前記局所経路探索領域の設定と当該領域内での局所経路の計算を目的地に辿り着くまで繰り返すことを特徴とするナビゲーションの表示方法。
【請求項５】
請求項２に於いて、
前記目的地を目指して伸びていくように段階的に表示されていく推奨経路に関する走行距離や所要時間などの評価情報を文字あるいはグラフで段階的に表示することを特徴とするナビゲーションの表示方法。
【請求項６】
請求項２に於いて、
前記自車の位置が前記推奨経路から外れたと判断された場合には、リルート処理を開始することを特徴とするナビゲーションの表示方法。
【請求項７】
請求項２に於いて、
前記推奨経路が複数表示され、前記自車が前記推奨経路のうちの一つに沿って走行した場合には、前記自車の走行経路から外れた他の推奨経路を消去することを特徴とするナビゲーションの表示方法。
【請求項８】
請求項２に於いて、
前記推奨経路が複数表示され、ユーザーが明示的に選択した以外の推奨経路を消去することを特徴とするナビゲーションの表示方法。
【請求項９】
請求項２に於いて、
前記地図が、三次元的に描かれた地図であることを特徴とするナビゲーションの表示方法。
【請求項１０】
目的地までの推奨経路であって、センタ側で交通情報を考慮して計算される推奨経路を通信により取得して記憶し、当該推奨経路を画面内の地図上に表示して自車を前記目的地まで誘導するナビゲーションの表示方法に於いて、
前記出発地から前記目的地に向かって計算される推奨経路の計算途中の情報を通信により取得し、
当該取得した前記推奨経路の情報を順次表示することによって、前記目的地を目指して伸びていくように推奨経路を表示するナビゲーションの表示方法。
【請求項１１】
請求項１０に於いて、
前記センタ側での推奨経路の計算方法は、
前記出発地周囲の所定の局所経路探索領域を設定すると共に、当該局所経路探索領域内で局所経路を計算し、
当該計算された局所経路の終端の周囲に新たに局所経路探索領域を設定すると共に、当該新たに設定された局所経路探索領域内で局所経路を計算し、
前記局所経路探索領域の設定と当該領域内での局所経路の計算を目的地に辿り着くまで繰り返すものであることを特徴とするナビゲーションの表示方法。
【請求項１２】
請求項１０に於いて、
前記推奨経路の計算途中の情報と共に前記地図情報および前記交通情報を通信により取得し、当該取得した情報を順次前記画面に表示することを特徴とするナビゲーションの表示方法。
【請求項１３】
請求項１０に於いて、
前記段階的に表示されていく推奨経路に関する走行距離や所要時間などの評価情報を文字あるいはグラフで段階的に表示していくことを特徴とするナビゲーションの表示方法。
【請求項１４】
現在地から目的地を目指して複数本の推奨経路を計算すると共に、その計算の途中経過として、途中までの計算が終わった前記複数の推奨経路を表示し、
その複数本の推奨経路が前記目的地を目指して伸びていくように表示する場合に於いて、
前記推奨経路の一部に高速道路または有料道路が含まれているとき、
当該高速道路または有料道路上の推奨経路の計算範囲を、高速道路または有料道路以外の道路上の推奨経路の計算範囲よりも広い範囲で計算することによって、
前記高速道路または有料道路上での推奨経路の伸び方を、高速道路または有料道路以外の道路上での推奨経路の伸び方よりも、速く伸びていくように表示することを特徴とするナビゲーションの表示方法。
【請求項１５】
複数車両の推奨経路を同時に計算する配車管理システムにおいて、その計算の途中経過として、途中までの計算が終わった前記複数車両の推奨経路を同時に表示する表示方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路探索手法に関わり、特に交通情報を加味した複数の経路を同時に探索してユーザーに提示するナビゲーション装置に関わる。
【０００２】
【従来の技術】
従来のナビゲーション装置における経路探索手法の主流であるダイクストラ法は、道路網を構成する交差点（ノード）間の道路切片（リンク）の移動コストについて、距離を優先させたり、所要時間を優先させたりして移動コストを変化させることで、距離についての最適な経路や所要時間についての最適な経路を得ることが可能である。しかし、目的地までの距離が長くなるに従って計算時間が指数関数的に増加するという欠点があり、また、目的地までの探索が終了するまで経路が確定しないため経路探索の計算処理が終了するまでは経路に関する情報を一切提示することができないという欠点がある。この欠点を改善するものとして、目的地に向かって経路を探索するに際し、探索の終了した範囲の経路から順次情報を提示する技術として特開平６−３４２４９８号公報が知られている。これは、道路上への代表的ノードへの到達容易度を各リンク毎に記録した静的なデータベース（以下、ＤＢとする）を参照して局所的な経路探索を繰り返すことにより行われる。また、先ず目的地に至る経路を計算し、其の中の一部の区間をリアルタイムに変化する動的交通情報を加味してダイクストラ法などにより計算した経路で置き換えることも開示されている。
【０００３】
【特許文献１】
特開平６−３４２４９８号公報
【０００４】
【発明が解決しようとする課題】
上記公報に示された経路探索手法では、リアルタイムに変化する動的交通情報の反映がされていないか、又は、経路の部分的な置き換えによるものであるため、部分的に渋滞を適切に回避できたとしても、必ずしも目的地までの推奨経路の全体が最適な推奨経路として探索されるものではない。
【０００５】
また、動的交通情報を加味して置き換えを行う方法では、探索の終了した範囲から経路を順次表示することはできない。敢えて斯様な表示を行ったとしても、目的地までの表示が完了した後に一部の経路の置き換えが行われるので、経路の置き換えが終わるまでは推奨経路を運転に役立てることは困難である。
【０００６】
本発明の目的は、推奨経路をユーザーへ有用に提示することにある。
【０００７】
【課題を解決するための手段】
本発明の目的は、目的地までの所要時間を優先した時間優先の推奨経路や、目的地までの走行距離を優先した距離優先の推奨経路など、目的地を目指して複数本の推奨経路を計算し、その複数本の推奨経路が、前記目的地を目指して伸びていくように表示することで達成される。
【０００８】
【発明の実施の形態】
図１は、本発明の一実施例であるナビゲーション装置の構成を示すブロック図である。経路探索装置１０１は、ユーザーインターフェース１０４の入力装置
１０５を介してユーザーが入力した出発地、又は、ＧＰＳ受信機１０８で測定された現在位置から経路探索を開始する処理を行う。このとき、局所ポテンシャル場を用いて、局所経路探索アルゴリズム１０３による局所経路探索を繰り返すことによって、上記入力装置を介してユーザーが入力した目的地に至る複数の経路を生成する。局所ポテンシャル場は、ポテンシャル場生成アルゴリズム１０２により交通情報を加味して生成される。
【０００９】
記憶装置１０７には、主に経路探索処理で用いられる交通情報と、出力装置
１０６への地図描画などに用いる地図情報が記憶されている。記憶装置１０７がＣＤ−ＲＯＭドライブあるいはＤＶＤ−ＲＯＭドライブである場合には上記地図情報および交通情報は固定的，静的なものであるが、記憶装置１０７がハードディスクドライブや半導体メモリで構成される場合には無線通信機１０９を介して無線接続された情報センタからダウンロード（以下、ＤＬという）した最新の地図情報および交通情報、即ち動的な情報に基づいて処理を行うことが可能である。
【００１０】
図８の概念図を用いて、情報の流れについて説明する。
【００１１】
８０１〜８０４の各箱を結ぶ矢印は情報の流れのみを表すものである。８０１〜８０４の全てが車側に存在すると考えることもできるし、通信型ナビゲーションのように８０２，８０３がセンタ側に存在し８０１，８０４が車側に存在すると考えることもできる。また、センタ側で推奨経路の探索を行うタイプのナビゲーションのように８０１〜８０３がセンタ側に存在し８０４のみが車側に存在すると考えることも、８０１のみがセンタ側に存在し８０２〜８０４が車側に存在すると考えることもできる。
【００１２】
経路探索装置８０１は、地図情報ＤＢ８０２に格納された地図情報と、交通情報ＤＢ８０３に格納された交通情報とを用いて複数経路の探索を並行して行う。経路探索装置８０１からは、経路探索の処理と並行して探索の終了した範囲の経路情報と、経路毎の評価情報が経路表示装置８０４に出力される。経路表示装置８０４を構成する地図表示部制御装置８０５では、地図情報ＤＢの地図情報を用いて地図の描画を行い、交通情報ＤＢの交通情報を用いて渋滞状況などの交通情報を示すマーキングの描画を行い、それらに重畳して探索された経路を描画する。また、経路表示装置８０４を構成する評価情報表示部制御装置８０６では、経路探索装置８０１から入力された評価情報に基づいて、文字あるいはグラフによる評価情報の提示を行う。なお、経路探索装置８０１から入力された経路情報と、地図情報ＤＢおよび交通情報ＤＢの各情報を用いて、評価情報を追加生成することも可能である。評価情報については後述する。
【００１３】
次に図１０，図１１を用いてポテンシャル場を用いた経路探索手法について説明する。図１０は、経路探索の過程を例示した概念図である。図１０（ａ）では、出発地１００１の周囲に局所経路探索領域１００２を設定する。領域としては、一方向にノードが５つ程度含まれるようなものを設定する。高速・有料道路上を探索する場合には、目的地までの距離を勘案し、目的地までの距離の半分というように距離として設定してもよい。何れにせよ高速道路などの場合には、分岐が殆ど無いので一般道に比べて広範囲の局所経路探索領域となる。この領域内で探索された局所経路が線１００３である。図１０（ｂ）では、図１０（ａ）の過程で探索された局所経路の終端ノード１００４の周囲に新たな局所経路探索領域１００５を設定する。この領域内で探索された新たな局所経路が線１００６である。以後、同様に図１０（ｂ）の過程を図１０（ｃ）（ｄ）のように繰り返し、最終的に図１０（ｅ）に例示したように局所経路１００７が目的地１００８に到達すれば、経路探索終了である。
【００１４】
図１１は、格子状の道路網を例に、図１０で示された局所経路探索領域の内部における局所経路探索の方法を示した概念図である。図１１では、格子状の直線群１１０１が道路を表し、その交点がノードである。円１１０２が図１０における局所経路探索領域に相当し、曲線群１１０３は局所経路探索領域内に形成されたポテンシャル場を仮想的に等高線で表現したものである。
【００１５】
局所経路探索領域のより外側にある円１１０４は、その内部に存在するリンクの幅員，規制情報，交通情報などのリンク情報が、上記ポテンシャル場の計算に反映されるリンク情報取得領域である。上記ポテンシャル場は、かかるリンク情報取得領域１１０４内部のリンク情報と、局所経路探索開始ノード１１０５に対する目的地の相対座標を加味してノード毎に計算される。ノード毎のポテンシャル値は、該当ノードから目的地への到達容易性と、局所経路探索開始ノードから該当ノードへの到達容易性を、適当な係数を介して合算した値に相当する。局所経路１１０６は、かかるポテンシャル場を用いて、局所経路探索開始ノードからポテンシャル値の最も低いノード１１０７に到達するように形成される。
【００１６】
図１１の例では、局所経路探索領域１１０２，リンク情報取得領域１１０４ともに円形としたが領域の形状と大きさは任意である。矩形とした場合には演算処理上の負荷が軽くなるというメリットがある。また、局所経路探索開始ノードと、局所経路探索領域内で最低ポテンシャルを与えるノードとの間の経路が高々１通りである場合は、局所経路は一意に定まるが、かかる経路が複数通りある場合には、局所経路探索開始ノードから当該ノードへの移動コストが最小になるように局所経路を決定する。従って、ａ，ｂ，ｃを通る３つの経路のうち、ａが局所経路として決定されている。例えば、Ｐをポテンシャル，ｓを移動変位ベクトルとして、移動コストＣｍを次のように定義し、
Ｃｍ≡∫∇Ｐ・ｄｓ
各経路のＣｍを比較し、Ｃｍが最小となった経路を局所経路として決定すればよい。
【００１７】
以下、局所経路探索の繰り返しによる経路探索の処理フローについて図１２を用いて説明する。図１２は、複数経路の並行探索を実施し、経路探索と共に経路を段階的に表示するための処理フローである。
【００１８】
Ｓ１２０１：経路探索条件を設定する処理であり、まず、同時探索を行う経路の数を設定する。続いて、同時探索を行う経路の数だけ、探索条件の設定を行う。例えば、同時探索を行う経路の数が３である場合、１番目の経路は距離優先探索、２番目の経路は時間優先探索、３番目の経路は一般道路優先探索をするといった条件を設定する。其の他にも高速・有料道路優先探索や、運転し易い・走り易い道路優先探索、即ち幅員の広い道路を優先して探索するという条件が考えられる。各経路の探索条件、必要なら並行探索を行う経路の数、はデフォルトで設定しておくようにするが、経路探索を行う都度ユーザーが設定することも可能であり、或いは過去の経路探索の設定を履歴として保存しておいて、かかる履歴に従って自動的に設定することも可能である。
【００１９】
Ｓ１２０２，Ｓ１２０３：経路探索の初期化処理であり、並行探索を行う経路の数だけループを回し、各経路に関する局所経路探索開始ノードを出発地に設定する。
【００２０】
Ｓ１２０４〜Ｓ１２０７：経路毎に局所経路探索と、探索済み経路の表示を行う処理であり、並行探索を行う経路の数だけループを回す。ループ内部のＳ１２０５では、処理対象の経路が目的地に到達しているか否かの判定を行い、当該経路が目的地に到達している場合にはＳ１２０６とＳ１２０７をスキップし、目的地に到達していない場合には、Ｓ１２０６に処理を進める。Ｓ１２０６ではサブルーチンＳ１２０９を呼び出し、局所経路探索を実施する。Ｓ１２０７では、探索された局所経路を経路表示装置に出力し、探索済み経路の表示を行う。
【００２１】
Ｓ１２０８：Ｓ１２０４のループ終了後、全経路が目的地に到達したか否かの判断を行い、目的地に到達していない経路があればＳ１２０４に処理を戻して、局所経路の探索と表示処理を継続し、全経路が目的地に到達していれば、経路探索及び表示の終了となる。
【００２２】
Ｓ１２０９〜Ｓ１２１２：局所経路探索Ｓ１２０６の呼び出すサブルーチンである。Ｓ１２０９では、局所経路探索開始ノードの周囲に、図１１に例示した局所経路探索に用いるポテンシャル場の形成領域である局所経路探索領域１１０２並びにリンク情報取得領域１１０４を切り出す。Ｓ１２１０では、Ｓ１２０９で切り出された局所経路探索領域内に、同じくＳ１２０９で切り出されたリンク情報取得領域内の地図情報および交通情報、そして経路毎の探索条件（Ｓ１２０１参照）に基づいてポテンシャル場を形成する。Ｓ１２１１では、かかるポテンシャル場に基づいて、上記局所経路探索領域内に局所経路を生成する。Ｓ１２１２では、生成された局所経路の終端ノードに局所経路探索開始ノードを設定し、処理をメインルーチンのＳ１２０７に戻す。
【００２３】
この処理フローでの経路探索手法は、経路探索と共に経路の表示を行うことが可能であり、ユーザーが探索の終了した範囲の経路を速やかに確認できるというメリットを持つ。また、局所経路の探索には局所的な地図情報と交通情報を用いるので、出発地周辺の地図情報と交通情報があれば直ちに経路探索を開始できるというメリットを持つ。
【００２４】
図１３は、ダイクストラ法を用いて、上記経路表示装置による段階的経路表示を実施するための処理フローである。以下、図１３の処理フローについて説明する。
【００２５】
Ｓ１３０１，Ｓ１３０２：同時表示を行う経路の数だけループを回し、ダイクストラ法による経路探索を実施する。
【００２６】
Ｓ１３０３，Ｓ１３０４：経路表示の初期化処理であり、同時表示を行う経路の数だけループを回し、各経路に関する表示開始ノードを出発地に設定する。
【００２７】
Ｓ１３０５〜Ｓ１３０８：Ｓ１３０２で探索された経路毎に段階的表示を行う処理であり、同時表示を行う経路の数だけループを回す。ループ内部のＳ１３０６では、処理対象の経路が目的地まで表示されているか否かの判定を行い、当該経路が目的地まで表示されている場合にはＳ１３０７とＳ１３０８をスキップし、目的地まで表示されていない場合には、Ｓ１３０７に処理を進める。Ｓ１３０７では表示開始ノードから一定長あるいは一定リンク数の経路表示を行い、Ｓ１３０８で表示開始ノードを表示済み経路の終端ノードに設定する。
【００２８】
Ｓ１３０９：Ｓ１３０５のループ終了後、全経路が目的地まで表示されているか否かの判断を行い、目的地まで表示されていない経路があればＳ１３０５に処理を戻して、経路の段階的表示処理を継続し、全経路が目的地まで表示されていれば、経路表示の終了となる。
【００２９】
かかる処理フローにより段階的経路表示は可能である。なお、ここではダイクストラ法を例にとったが、図１３に示す処理フローは、いかなる経路探索手法とも組み合わせて適用することができる。しかしながら、経路探索と共に表示を行うことができないため、図１２に示した処理フローと比較して、経路の表示開始までに要する待ち時間は長くなる。Ｓ１３０２のループで経路探索の終了まで待つ必要があるからである。
【００３０】
以下、図２〜図７，図９を参照して探索した経路の表示例について説明する。
【００３１】
図２は表示構成を示している。地図表示部２０１には、道路地図２０２，探索された経路２０３，経路に付された番号２０４，渋滞状況などの交通情報を表すマーキング２０５，現在地を表すマーク２０６，目的地を表すマーク２０７が重畳して表示されている。探索された経路２０３は図２では３本表示されており、経路に付された番号も▲１▼〜▲３▼と３つの番号が表示されている。２０８は評価情報表示部であって、表示された経路毎に番号を付して走行距離や所要時間などが評価された評価情報を表示している。評価情報表示部は地図表示部２０１と別ウィンドウとして示されているが、地図表示部２０１に重畳して表示しても構わない。また、評価情報は文字情報として表示されているが、図３のウィンドウ３０１のようにグラフで表示することもできる。
【００３２】
経路探索を行う際、ユーザーは先ず地図上で目的地２０７を設定する。設定の仕方は、目的地である文字情報の選択による設定が代表的である。発音された地名を音声認識等することによって行う設定，カーソルキー等のポインティングデバイスを用いて地図表示部２０１上で座標指定して行う設定もある。経路探索の出発地としては、ＧＰＳ受信機等で測定される現在位置を使用することが通常と考えられるが、そうでない場合は出発地２０６も目的地と併せて設定する。前記のように、並行して探索する経路の数は、経路探索を行う都度設定することも可能であり、予め設定した値を使用することも可能である。以上の設定を終えたら、経路探索の開始を指示する。これにより、経路探索が開始され、探索された経路は段階的に地図表示部２０１に表示され、評価情報も評価情報表示部２０８に表示される。図２のように全経路が目的地に到達した時点で、経路探索は完了である。図２の経路探索結果を得る過程における探索途中の経路情報の表示について、図４と図５を用いて説明する。図４と図５を構成する要素は図２と同一であるが、地図表示部２０１，４０１，５０１に表示された経路２０３，４０２，５０２の長さと、評価情報表示部２０８，４０３，５０３に提示された評価情報の内容が異なる。地図表示部に表示された経路は、経路探索の処理と並行して図４→図５→図２という順番で段階的に伸長して描画される。詳細には、▲１▼の局所経路が１つ表示されると、次に▲２▼の局所経路が１つ表示され、次に▲３▼の局所経路が１つ表示されて、▲１▼に戻る。以後、全ての推奨経路が目的地に辿り着くまで、この流れを繰り返すので、各推奨経路が少しずつ目的地を目指して伸びていくように表示される。
【００３３】
複数の経路探索を行い、此れらを同時に一画面に表示することで、ユーザーへの走行の選択肢を確保すると共に、ユーザーがリルートを行う負荷を低減させることができる。計算された複数の推奨経路に高速・有料道路と一般道とが含まれている場合には、高速・有料道路の推奨経路の方が一般道の推奨経路よりも速く伸びていくように表示される。前述したように、局所経路探索領域の広さが異なるためである。従って、高速道路などは一般道よりも速く走ることができるという直感的なイメージが画面上に表現され、ユーザーにとって使い勝手のよい推奨経路表示といえる。
【００３４】
図１３の計算では、計算と表示が分離されているため、経路の表示によって計算の途中経過を知ることは出来ない。しかし、図１２の計算によると、経路全体に対して何％くらいの部分が計算されたのか其の途中経過を知ることが出来る。これは例えばインターネットでファイルをＤＬする際に、数値やインジケーターバーを用いて現在何％ＤＬ完了といった内容を表示させることと類似である。ナビゲーションの画面上に、インターネットのように新たにウィンドウを表示させるとすると地図などや場合によっては自車位置が隠されるのでナビゲーションの機能を低下させることに繋がるし、地図情報と全く別個にインジケーターバーを表示させることはユーザーへの情報の提示という観点から考えると必要な情報がそれぞれ分離されることとなり好ましくない。従って、地図上の道路にインジケーターバーの機能として推奨経路を表示していくのでユーザーにとって違和感のない表示方法ということが出来る。
【００３５】
評価情報表示部に提示される評価情報は、探索済みの経路上の道路情報を反映して、やはり経路探索の処理と並行して図４→図５→図２という順番で段階的に更新される。地図表示部と評価情報表示部の更新については、同期・非同期を問わないが、評価情報までもが更新されると鬱陶しく感じられる場合もあることが予想されるので、経路表示が終了した後にのみ評価情報を表示するようにしてもよい。また、複数の経路の並行探索と共に表示を行う場合であっても、全経路の探索と表示が同時に終了しないことがあるのは前述の通りである。
【００３６】
経路探索の完了後、即ち図２のような表示がなされた後、探索した経路の中からユーザーがインターフェースを介して一の走行経路を選択することで、選択外の経路は地図上から消去される。または、何れかの経路に沿って走行することで一の経路を選択した場合には、選択外の経路は地図上から消去される。経路を逸脱した場合やユーザーからの指示が入力された場合のリルート処理は、経路からの逸脱が自動検知された時点かユーザーから指示が入力された時点から開始される。リルート処理における経路探索および探索された経路の表示の過程も図４→図５→図２に示した例と同様に段階的なものであり、目的地までの経路探索処理の終了を待たずとも、リルート後の探索した経路が直ちに表示され、運転に役立てることができる。
【００３７】
図６，図７は経路探索の結果を鳥瞰図のような三次元的に描画された地図上で表示した例であり、図２，図４，図５とは全く別の領域を表示している例である。地図表示部６０１を構成する要素は、図２と同様であり、地図６０２の上に、出発地６０３，目的地６０４，探索された経路６０５および各経路に付された番号６０６が重畳して表示されている。図６，図７は経路探索の過程を表す例であり、地図表示部６０１，７０１上に表示された経路６０５，７０２は経路探索の処理と並行して図６→図７という順番で段階的に更新される。評価情報表示部６０７，７０３に表示される評価情報も、探索済み経路上の道路情報を反映して、経路探索の処理と並行して図６→図７という順番で段階的に更新され得るのは前記と同様である。
【００３８】
図９は、通信型ナビゲーション装置における経路探索の表示例である。地図情報ＤＢと交通情報ＤＢがネットワーク接続されたセンタにある場合であって、各ＤＢからデータをナビゲーション装置にＤＬするものの場合の表示例である。
【００３９】
地図表示部９０１において、９０２は詳細地図がＤＬされた領域、９０３は詳細地図のＤＬが完了していない領域である。この経路探索手法は局所的な経路探索を繰り返すものであるため、経路探索対象範囲全体の地図情報および交通情報がない場合であっても経路探索を開始することができる。このため、詳細地図のＤＬと並行して経路探索を実行し、探索済みの経路９０４と其の評価情報を図９のように地図表示部９０１及び評価情報表示部９０５に表示することができる。
【００４０】
また、図示していないが、地図情報ＤＢ，交通情報ＤＢと経路探索装置が上記のセンタ側に備えられ、センタ側で推奨経路を計算するナビゲーションシステムが考えられる。このシステムでは、センタ側での経路探索処理と並行して探索済み局所経路のＤＬが可能となり、経路探索結果の取得に要する時間が短縮される。このとき、地図情報と交通情報が予めＤＬされている場合には、経路探索処理と並行してＤＬされる局所経路の表示過程は図４→図５→図２と同様に表示領域全体が詳細地図となる。一方、経路探索と並行して地図情報および交通情報のＤＬも実施する場合には、探索途中の経路とＤＬ途中の地図情報，交通情報が同時に描画されるため、その過程における経路情報の表示は図９のように詳細地図がＤＬされた領域９０２だけが詳細地図となる。
【００４１】
経路探索装置のみがネットワーク接続されたセンタにある場合には、詳細地図の描画が完了した上に、センタからＤＬされた経路情報が重畳して描画されるため、ＤＬの過程における経路情報の表示は図４，図５，図２に例示した過程のようになる。
【００４２】
以上では１台の車両を誘導するナビゲーション装置を対象として複数経路の同時探索と探索済み経路の表示を行う例を示したが、本願のナビゲーション装置によれば、複数台の車両誘導を同時に実施する配車管理システムにおける、複数車両の経路探索と探索済み経路の表示を、並行して実施することが可能である。例えば１０００台のトラックの配車管理における推奨経路を作成する際、ダイクストラ法では、１台分ずつ経路探索を行って、経路探索が終了した車両から順次結果を表示する。あるいは、複数車両の経路を並行して探索することも可能だが、個々の車両について、経路探索結果を表示できるのは、やはりそれぞれの経路が目的地まで到達してからである。これに対して、前記局所経路探索を用いた経路探索法によれば、複数の車両の経路探索を同時に実施しつつ、それと並行して全車両について探索途中の経路を表示することが可能である。配車管理の担当者は、その経過を見ながら探索条件を随時変更して経路探索をやり直すことも可能である。また、配車管理作業が大規模なものであり、全車両の推奨経路の探索に数時間を要するような場合であっても、経路探索の終了を待つことなく、途中まで探索された推奨経路の情報をもとに、各車両への指示を行うことが可能である。図１４はその表示画面の例であり、５台の車両について、地図１４０１上の車庫１４０２からそれぞれの目的地１４０３〜１４０７までの経路探索を実施しつつ、それと並行して経路１４０８〜１４１２の描画を行っている。図１４では車両の台数を５台としているが、これは１０００台などの大規模配車管理においても同様の表示処理が可能である。
【００４３】
以上によれば、交通情報などを加味した局所的な経路探索を繰り返すことで、複数の適切な経路を並行して探索し、探索の終了した範囲の経路から順次ユーザーに提示することが可能となる。即ち、複数の経路探索処理の開始と共に此れら経路の段階的表示を開始することが可能である。
【００４４】
【発明の効果】
推奨経路をユーザーへ有用に提示することができる。
【図面の簡単な説明】
【図１】一実施例であるナビゲーション装置の構成を示すブロック図。
【図２】探索経路の表示例。
【図３】経路評価情報のグラフによる表示例。
【図４】探索経路の表示例。
【図５】探索経路の表示例。
【図６】探索経路の表示例（鳥瞰図）。
【図７】探索経路の表示例（鳥瞰図）。
【図８】経路探索の手法及び表示に関する情報の流れを示す概念図。
【図９】通信型ナビゲーション装置の例。
【図１０】経路探索手法の概念図。
【図１１】ポテンシャル場を用いた局所経路探索の概念図。
【図１２】経路探索手法と、段階的経路表示の処理フローの例。
【図１３】ダイクストラ法などを用いた段階的経路表示の処理フローの例。
【図１４】配車管理システムにおける探索経路の表示例。
【図１】
2005017052.tif 000003
【図２】
2005017052.tif 000004
【図３】
2005017052.tif 000005
【図４】
2005017052.tif 000006
【図５】
2005017052.tif 000007
【図６】
2005017052.tif 000008
【図７】
2005017052.tif 000009
【図８】
2005017052.tif 000010
【図９】
2005017052.tif 000011
【図１０】
2005017052.tif 000012
【図１１】
2005017052.tif 000013
【図１２】
2005017052.tif 000014
【図１３】
2005017052.tif 000015
【図１４】
2005017052.tif 000016