(57)【要約】　　　（修正有）【課題】地点設定操作を容易に、また確実に行えるようにすること。【解決手段】設定された開始地点と終了地点間の走行経路を探索し、探索された経路に基づき経路案内を行う経路探索装置において、経路探索中に、前記設定された終了地点（開始地点）の地名を表示する終了地点名表示手段（開始地点名表示手段）とを備えたことを特徴とする経路探索装置。また、例えば前記終了（開始）地点の地名は、終了（開始）地点に基づいて検索された終了（開始）地点の近接地点に付された地名であり、さらに終了（開始）地点の近接ノードのノード情報から地名を割り出す。【選択図】　図３
2004085558.tif 000002
【特許請求の範囲】
【請求項１】
設定された開始地点と終了地点間の走行経路を探索し、探索された経路に基づき経路案内を行う経路探索装置において、
経路探索中に、前記設定された終了地点の地名を表示する終了地点名表示手段とを備えたことを特徴とする経路探索装置。
【請求項２】
請求項１の経路探索装置において、
経路探索中に、前記設定された開始地点の地名を表示する開始地点名表示手段とを備えたことを特徴とする経路探索装置。
【請求項３】
請求項１、請求項２の経路探索装置において、
前記終了地点の地名は、終了地点に基づいて検索された終了地点の近接地点に付された地名であることを特徴とする経路探索装置。
【請求項４】
請求項３の経路探索装置において、終了地点名表示手段は、設定された地点に基づいて検索された終了地点の近接ノードのノード情報から地名を割り出すことを特徴とする経路探索装置。
【請求項５】
請求項２の経路探索装置において、
前記開始地点の地名は、開始地点に基づいて検索された開始地点の近接地点に付された地名であることを特徴とする経路探索装置。
【請求項６】
請求項５の経路探索装置において、開始地点名表示手段は、設定された地点に基づいて検索された開始地点の近接ノードのノード情報から地名を割り出すことを特徴とする経路探索装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、設定された開始地点と終了地点を結ぶ最適な走行経路を自動的に演算する経路探索装置に関する。
【０００２】
【従来の技術】
車輛位置のマークを画面の中心に置いた地図画像を液晶画面等に表示して、操作者に道案内を提供するナビゲーション装置が実用化されている。車載用ナビゲーション装置は、ＧＰＳ（Ｇｌｏｂａｌ　Ｐｏｓｉｔｉｏｎｉｎｇ　Ｓｙｓｔｅｍ　）装置、車速センサ、方位センサ等から現実の車輛位置を刻々と演算し、演算結果を地図画面に合成して表示する。
【０００３】
車載用ナビゲーション装置は、例えば、地図情報を記憶したＣＤ−ＲＯＭ装置を備え、ＣＤ−ＲＯＭ装置から必要な地図情報を呼び出して、車輛位置を中心に置いた所定範囲の地図画像を液晶画面に画像表示する。
【０００４】
地図情報を記憶したＣＤ−ＲＯＭには、地図画像とともに、地図上の多数の情報点（以下ノードと呼ぶ）のデータと、２つのノードを連結するリンクのデータが記録されている。道路の交差点、行き止まり、踏切、鉄道駅、インターチェンジ等がノードとして選択される。また、緯度、経度の座標情報、交差点名、進行方向案内、右左折の禁止等がノード情報として付加され、道幅、一方通行等がリンク情報として付加されている。
【０００５】
従って、走行中、運転者は、地図画面上で実際の車輛位置を確認するが、ナビゲーション装置に現在位置の座標や進行方向でＣＤ−ＲＯＭを検索する機能を備えることで、通過中のノード（接近する交差点）のデータをリアルタイムに利用できる。
【０００６】
例えば、交差点の手前数１００ｍで、次の交差点の進行方向や車線の案内、一方通行の有無等を地図画面の隅に重ねて表示する。また、地図上の道路を外れて移動する車輛マークを道路上に自動復帰させる。
【０００７】
ＣＤ−ＲＯＭに記録されたノード情報、リンク情報を利用したナビゲーション装置の附属機能として、経路探索機能が実用化されている。経路探索機能は、実際の走行の開始に先立って、ナビゲーション装置が最適な走行経路を演算する機能である。
【０００８】
運転者が開始地点と終了地点とを設定すれば、後は、ナビゲーション装置の演算部が、ＣＤ−ＲＯＭを自動検索し、必要なノード情報、リンク情報を呼び出して、最短距離、最短時間等の条件に適合した走行経路を演算する。
【０００９】
例えば、走行経路に沿って位置するノードの座標を連結してＣＡＤ画像を形成して、地図画像に合成して画像表示する。これにより、地図画像上に走行経路が太線で示される。
【００１０】
例えば、設定した走行経路を実際に走行している際に、交差点に接近するごとに、走行経路を実現するための右折、左折、直進の区別を地図画像の隅に合成して画像表示する。制限速度や車線案内等を併せて表示してもよい。ナビゲーション装置にスピーカを備え、音声でこれらの情報を伝達する場合もある。
【００１１】
走行経路の演算方法としては、従来、ダイクストラ法という演算手法が有名である。ダイクストラ法では、開始地点から外側に向かってリンク長さを順番に加算して、より外側のノードに到達する最短経路を順次確定し、最終的に終了地点に到達する最短距離の走行経路を確定する。
【００１２】
しかし、ダイクストラ法では、開始地点から外側に演算を進めるに従って、演算すべきノード数（計算に関与する範囲）が面積的に増加するから、長距離の走行距離を演算させると長時間を費やす、演算データを一時保存して、演算装置に次の演算を可能にするメモリ容量に大容量を要求される等の問題がある。
【００１３】
また、ダイクストラ法では、長さ的に最短の道のりを実現する走行経路が求まるに過ぎず、その走行経路を採用しても旅行時間が最短となる保証は無い。すなわち、細い道を選択して右左折を繰り返す等、実際の運転感覚や常識に照らして非効率的な走行経路が求まる可能性がある。
【００１４】
そこで、ＣＤ−ＲＯＭに記録されたノード情報、リンク情報をさらに有効活用して、ノード、リンクに重み付けを行い、種々の修正形式でダイクストラ法を使用する試みが提案されている。
【００１５】
例えば、本願出願人は、特願平４−３２９５６４号において、リンク長さをリンク旅行時間に換算して積算させ、「最短旅行時間を達成する走行経路」を演算させる手法を提案している。
【００１６】
【発明が解決しようとする課題】
ナビゲーション装置では、経路探索の終了地点等、利用者が地点を設定する機会が多々ある。このため、ナビゲーション装置では、地点設定操作を容易に、また確実に行えるようにすることが、大きな課題となっている。
【００１７】
本発明は、この課題を解決するもので、地点設定操作を容易に、また確実に行えるようにすること目的としている。
【００１８】
【課題を解決するための手段】
図１は、実施例の経路探索装置の説明図である。ここでは、図１（ａ）　のシステム構成に付した記号を参照して本発明に係る技術分野である経路探索装置を説明する。ただし、本発明の経路探索装置は、図１および実施例の記載に説明される態様には限定されない。
【００１９】
図１において、経路案内装置は、地図画像に組み合わせて、地図上の多数のノードとリンクの情報を記憶させた第１記憶手段１３と、求める走行経路の開始地点と終了地点を設定可能な操作手段１１と、第１記憶手段１３に記憶された前記ノードとリンクの情報を参照して、少なくとも前記開始地点と終了地点の一方から、確定された走行経路を順次延長する形式で走行経路を演算する演算手段１６と、確定された走行経路を順次記憶して、前記演算手段１６による走行経路の続き部分の演算を可能にする第２記憶手段１５と、を有する経路探索装置において、全体に対する部分の割合をほぼ連続的に表示可能な一対の表示手段１７Ａ、１７Ｂと、求める走行経路の全体に対する確定された走行経路の割合を検知して、一方の前記表示手段１７Ａに、前記割合にほぼ対応した表示を行わせる第１計測手段１６と、第２記憶手段１５の記憶容量の残量を検知して、他方の前記表示手段１７Ｂに、前記残量にほぼ対応した表示を行わせる第２計測手段１６と、を設けたものである。
【００２０】
請求項１の経路探索装置は、設定された開始地点と終了地点間の走行経路を探索し、探索された経路に基づき経路案内を行う経路探索装置において、経路探索中に、前記設定された終了地点の地名を表示する終了地点名表示手段とを備えたものである。
従って、経路探索中に、終了地点の地名が表示され、終了地点の確認が容易、かつ確実に行うことができる。
【００２１】
請求項２の経路探索装置は、請求項１の経路探索装置において、経路探索中に、前記設定された開始地点の地名を表示する開始地点名表示手段とを備えたものである。
従って、経路探索中に、開始地点の地名も表示され、開始地点の確認も容易、かつ確実に行うことができる。
【００２２】
請求項３の経路探索装置は、　請求項１、請求項２の経路探索装置において、前記終了地点の地名は、終了地点に基づいて検索された終了地点の近接地点に付された地名であることを特徴とするものである。
従って、経路探索中に、終了地点付近でデータの存在する地名が表示されることとなる。
【００２３】
請求項４の経路探索装置は、請求項３の経路探索装置において、終了地点名表示手段は、設定された地点に基づいて検索された終了地点の近接ノードのノード情報から地名を割り出すことを特徴とするものである。
従って、経路探索中に、終了地点付近のノード情報に基づく地名が表示されることとなる。
【００２４】
請求項５の経路探索装置は、請求項２の経路探索装置において、前記開始地点の地名は、開始地点に基づいて検索された開始地点の近接地点に付された地名であることを特徴とするものである。
従って、経路探索中に、開始地点付近でデータの存在する地名が表示されることとなる。
【００２５】
請求項６の経路探索装置は、請求項５の経路探索装置において、開始地点名表示手段は、設定された地点に基づいて検索された開始地点の近接ノードのノード情報から地名を割り出すことを特徴とするものである。
従って、経路探索中に、開始地点付近のノード情報に基づく地名が表示されることとなる。
【００２６】
【実施例】
図１は、本発明の実施の形態に係るナビゲーション装置の説明図、図２は処理プログラムの説明図、図３は表示内容の説明図である。図１中、（ａ）　はシステム構成、（ｂ）　は処理ブロック図を示す。図３中、（ａ）　は画面構成、（ｂ）　は距離計算を示す。
【００２７】
ここでは、車載用ナビゲーション装置の附属機能として、経路探索機能を設けている。操作者は、経路探索処理を選択し、車載用ナビゲーション装置の画面に地図を呼び出して開始地点と終了地点を入力する。すると、車載用ナビゲーション装置の地図画面は、経路探索処理中を示す画面に移行し、経路探索処理の進度とメモリ容量の使用度（全容量−残量）が棒グラフ表示される。
【００２８】
図１において、通常走行の場合、処理部１６は、位置センサー１４から得られる位置や速度の情報に基づいて刻々の車輛位置を演算する。そして、車輛位置を含む地図画面を地図データベース１３から呼び出して画像データを形成する。画像データは、表示部１７を通じて、車輛のマークを画面の中央に位置させた地図画面として運転者に表示される。
【００２９】
また、地図画面の下部には、交差点名、交差点の構造、車線案内、道路名、制限速度等の各種情報の有無が表示されており、運転者は、操作部１１を通じて必要な情報の種類を選択して利用できる。
【００３０】
地図データベース１３は、ＣＤ−ＲＯＭの再生装置で構成され、処理部１６からの検索指令に応じて、地図画像データ、ノード情報、リンク情報を検索し、処理部１６に送出する。メモリ１５は、処理部１６が各種の演算処理を実行する場合に処理データを一時保存する。
【００３１】
処理部１６は、運転者が操作部１１を通じて開始地点（自宅）と終了地点（目的地）を指定すると、地図データベース１３から、必要なノード情報、リンク情報を検索して最短旅行時間の走行経路を構成する。
【００３２】
経路探索機能を使用する場合、操作者は、入力部１１を通じて経路探索処理を選択する。操作者は、表示部１７の画面に表示された地図を、入力部１１を通じてスクロール操作し、必要な地図を選択して開始地点を入力する。操作者は、続いて、表示部１７の画面に表示された地図を、入力部１１を通じてスクロール操作し、必要な地図を選択して終了地点を入力する。そして、操作者は、経路探索処理の開始を指令する。
【００３３】
これにより、表示部１７の地図画面は、直ちに、経路探索処理中を示す画面に移行して、２本の棒グラフ１７Ａ、１７Ｂを表示する。棒グラフ１７Ａは、経路探索処理の進度を示す。棒グラフ１７Ｂは、メモリ１５における経路探索処理に割り当て可能な容量のうち、現時点で既に利用されている割合を表示する。
【００３４】
その後、数分間に渡って演算が継続され、途中で棒グラフ１７Ｂが１００％に達しなければ（メモリ１５がオーバーフローしなければ）、すべての演算処理が完了して棒グラフ１７Ａの演算進度が１００％に表示される。操作者は、表示部１７に図９（ｂ）　の記録操作画面を呼び出して、経路データ保存部１２のＩＣカードに経路探索結果を記録する。なお、演算完了と同時に経路探索結果を経路データ保存部１２に送出させ、自動的に記録操作を行わせてよい。
【００３５】
このようにして形成された走行経路データは、開始地点から終了地点までの走行経路を構成するノードのノード情報、リンクのリンク情報を含む。また、走行経路を構成するための右折、左折、直進等の案内データがノード情報に追加されている。
【００３６】
経路データ保存部１２は、データ処理部１６からの指令に応じて走行経路データをデータ処理部１６に送出する。また、経路データ保存部１２からＩＣカードを抜き出して、パソコン等を利用した室内システムとの間でも走行経路データを共有できる。
【００３７】
図１（ｂ）　において、図１（ａ）　の処理部１６では、通常の自動車位置検出処理２３と、上述の経路探索処理２１の他に、経路案内処理２２を実行できる。経路案内処理２２は、図１（ａ）　の経路データ保存部１２に記録された走行経路のデータに基づいて、走行中、操作者にリアルタイムの情報提供を行う処理である。
【００３８】
例えば、設定された走行経路に対して刻々の車輛位置を比較し、走行経路上の右折を要する交差点の手前で、右折を予告するメッセージを出力する。また、走行経路を外れた場合には警報を出力する。
【００３９】
経路探索処理２１は、操作者の指定に基づいて開始地点と終了地点を決定する地点設定２１Ａ、修正形式のダイクストラ法等によって実際に経路を演算する経路探索２１Ｃ、演算された探索結果２１Ｄを、必要なその他の選別情報と組合せた形式でＩＣカードに記録させる探索結果管理２１Ｂの各処理を含む。
【００４０】
図２において、経路探索処理中を通じて、図１の表示部１７の表示画面に棒グラフ１７Ａ、１７Ｂが表示される。棒グラフ１７Ａは経路探索処理の進度、棒グラフ１７Ｂはメモリ１５の使用割合を表示している。
【００４１】
フローチャート下部のステップ２５で演算された「開始地点から終了地点までの距離」に対して、ステップ２６で演算された「演算中の領域から終了地点までの距離」が比較される。そして、両者の割合が、ステップ２８で棒グラフ（以下インジケータと呼ぶ）表示される。確定した直線距離ｄと、終了地点までの残りの直線距離Ｄ−ｄも、併せて文字表示される。
【００４２】
ただし、ステップ２７の演算処理では、残りの直線距離Ｄ−ｄが０になっても９０％の扱いである。１００％のインジケータ表示は、すべての経路探索処理が完了して、演算結果を出力可能になる頃を見計らって、ステップ３０によって実現される。
【００４３】
同様にして、メモリ１５における経路探索処理に割り当て可能な最大容量Ｍに対して、実際に使用している（または、未だ空き状態）である容量ｍが比較される。そして、両者の割合がステップ２９でインジケータ表示される。使用中の容量ｍと残量Ｍ−ｍも併せて文字表示される。
【００４４】
図３（ａ）　において、経路探索処理中の表示画面には、開始地点と終了地点の地名が表示される。地名は、操作者が設定した開始地点、終了地点に基づいて検索された近接ノードのノード情報から割り出している。
【００４５】
図３（ｂ）　において、経路探索処理の進度を割り出すための直線距離ｄは、ノード情報に含まれるＸＹ座標値から演算される。また、地図のユニットごとに直線距離ｄを１回演算する。
【００４６】
道路地図データは、通常、図３（ｂ）　のようにユニット管理されている。今、検索している地点が左下（２０、２０）のユニットにあるとき、ゴールが存在するユニットまでの距離Ｌは、
Ｌ２　＝（６０−２０）２　＋（０−２０）２
で求められる。
【００４７】
探索点が探索中のユニットに存在する間は、距離計算は不要となり、処理の高速化が図れる。探索点が未探索ユニットに移動したとき、距離計算を行い、距離が前の値より大きくなったとき、その距離に基づきインジケータ量を算出すればよい。
【００４８】
ところで、探索点が探索中のユニットに長時間存在すると、インジケータが動かなくなる。そこで、１ユニット分、インジケータ量を一度に増加させず、探索点が同一ユニットに存在する期間は、インジケータの最小ステップごとに増加させている。
【００４９】
図４は、地点設定機能機能の説明図である。ここでは、地点設定の禁止チェック処理のフローチャートが示される。
【００５０】
図４において、図１（ｂ）　の地点設定２１の処理では、詳細地図以外を用いての開始地点、終了地点の設定を禁止する。ＣＤ−ＲＯＭに記録された地図は、縮尺の異なる複数の階層を持つ。縮尺の小さい詳細地図を用いることで、地点設定の位置精度が確保される。
【００５１】
操作者が選択して画像表示させた地図の表示地図スケールｓを粗さの許容レベルＳに比較する。表示地図スケールｓは、最初に地図を描くとき、表示地図を拡大、縮小した際に更新される。そして、詳細地図でない場合には、例えば、「詳細地図で設定して下さい」という警報が表示される。詳細地図の場合には、引き続いて実際の地点設定が可能になる。
【００５２】
図５はノードの親子関係データの作成の説明図、図６は階層的経路探索の説明図、図７は階層的経路探索結果の説明図である。図５中、（ａ）は処理フローチャート、（ｂ）　はデータ構造を示す。ここでは、階層的経路探索を行うために、演算処理に先立って使用する演算データが整理される。
【００５３】
図５（ａ）　において、経路探索処理の途中、図１（ａ）　のメモリ１５には、地図データベース１３から検索したノード情報、リンク情報が単位ブロックの地図ごとに一時記憶されて、処理部１６に順次提供される。このとき、上（下）の階層の地図のノード情報も併せて参照して、ノードの親子関係をノード情報に追加して記録する。すなわち、ノード情報のＸＹ座標の同一性を調べて、上位地図のノードに重複する下位地図のノードがすべて選びだされる。これにより、下位地図のノードで演算している際に、上位地図で演算を継続できるか否かが識別可能になる。
【００５４】
このとき、（１）　階層的データ構造を持つ地図データであること、（２）　階層間における地図同士で、ノードの親子関係を示すデータが付加されていないことが条件となる。
【００５５】
図５（ｂ）　において、地図データ４１のヘッダは、地図データ番号、地図縮尺、データサイズ、緯度経度情報等を格納する。ノードテーブルは、ノード座標、接続リンク情報、親子ノードの有無等を格納する。リンクテーブルは、始点ノード番号、終点ノード番号、種別、幅員、交通規制、リンク長、リンク方位等を格納する。
【００５６】
親（子）ノードテーブル４２は、親（子）データ１〜ｎを配列し、１個の親（子）データ４３は、親（子）データ番号と、接続ノード番号で構成される。
【００５７】
図６において、図５（ｂ）　の親子ノードの関係を用いて、探索の始点、終点から離れるに従い、上位階層の道路地図を対象に経路探索を行う。すなわち、開始地点が設定された最下層の詳細地図で探索を開始し、詳細地図の子ノードの座標値が上位地図の親ノードの座標値に一致して重複する子ノードまで、経路探索が進行すると、今度は、上位地図の親ノードによる経路探索を開始する。上位地図で経路探索が進行して、さらに上位の地図の親ノードに重複する親ノードに到達すると、今度は、さらに上位の地図の親ノードによる経路探索を開始する。
【００５８】
一方、終了地点側からも同様な手順で経路探索が進行される。最下層の詳細地図で探索を開始し、上位地図、さらに上位の地図と乗り換えて経路探索を進行させる。開始地点からの経路探索と、終了地点からの経路探索が始めて共通のノードに到達したとき、経路探索が完了する。
【００５９】
処理手順は次のとおりである。（１）　最下位階層で探索の始点、終点ノードを決定する。（２）　始点ノードから親ノードデータを使って、上位階層までの経路を確定する。（３）　終点ノードから親ノードデータを使って、上位階層までの経路を確定する。（４）　上位階層間での経路を確定する。（５）　経路の確認、すなわち、階層が変わる付近の経路探索を再度やり直し、最適化する。なお、（２）　、（３）　において、どの階層まで上昇するかは、始点、終点間の距離や道路（データ）密度に基づいて決定する。
【００６０】
図７（ａ）　において、同一階層での探索によれば、次のような問題がある。（１）　最上位階層を使用すると、スタート、ゴール周辺の詳細な経路が無い。（２）　最下位階層を使用すると、データサイズが大きいため、探索距離が短くなる。
【００６１】
図７（ｂ）　において、階層的探索では、スタート、ゴール周辺は最下位階層を使用する。スタート、ゴールから離れるに従い、上位階層を使用する。従って、スタート、ゴール周辺の詳細な経路がある。
【００６２】
図８は、探索における地図切り出し法の説明図である。図中、（ａ）　は終了点方位とリンク方位の関係、（ｂ）　は終了点に対するリンク重みを示す。
ここでは、リンクを進行方向別に重み付けして、演算終了点方向への演算進行を促進する。
【００６３】
図８（ａ）　において、次のような手順で経路探索は進行する。（１）　探索しているノードＮから探索終了点Ｇに対する方位Ｄｇを求める。（２）　ノードＮから接続する道路方位Ｄｌを求める。（３）　ＤｌとＤｇの差分Δｄを求める。Δｄから重みｗを算出する。（５）　（４）　で求めたｗを経路探索時のリンクへの重み付けに用いる。（６）　地図データの境界に探索点が到達したときに、隣接する地図データを読み取る。従って、探索前に予め、楕円切出し等で地図データを用意しない。
【００６４】
このような処理では、探索処理の一部でありながら、地図切り出し機能も兼ね備えている。何故なら、終了点に向かうリンク長さを短くすることにより、終了点方向に探索が進みやすくなるからである。
【００６５】
図８（ｂ）　において、Δｄが０、すなわち、リンク方位と終了点方位の一致度が高い程、重みは小さく割り当てられる。リンク方位と終了点方位の一致度が低くなると、次第に重みは増大し、反対方向（１８０度）で最大となる。
【００６６】
重み付け修正された重み付きリンク長さＬは、ｌ：リンク実長さ、Ｗ１：乗算重み、Ｗ２：加算重み、ｗ：探索終了点に対する重みとして、
Ｌ＝ｌ×Ｗ１×ｗ＋Ｗ２
と求められる。この重み付きリンク長さＬを順次積算する形式で、ダイクストラ法等を使用した経路探索処理が進行される。
【００６７】
次に、メモリ開放機能を説明する。ここでは、経路検索処理中、図１（ａ）　のメモリ１５の容量が節約される。
【００６８】
探索で用いる道路データが図３（ｂ）　のようにブロック分けされて区切られている場合、探索開始点から区画に存在する全てのノードまでの経路長が確定した区画の道路データ領域をメモリ１５上から開放する。これにより、メモリ消費量を削減する。
【００６９】
一度確定したノードを再び、参照する必要は無いので、１ブロックに存在する全ノードまでの経路長が確定した時点で、そのブロックの道路データを開放し、経路探索処理で使用できるメモリ容量を増加させる。これにより、同じ容量のメモリ１５を使用しても、経路探索できる距離が増加する。
【００７０】
次に、データの間引き機能を説明する。ここでは、経路探索処理中、直近の演算に使用するノード情報、リンク情報を、図１（ａ）　の地図データベース１３からメモリ１５に蓄積する際に、地図データをふるい分けする。
【００７１】
探索する直線距離がある規定値よりも長い場合、途中の道路データから特定の道路種別だけを抽出し、地図データとしてメモリ１５に保持させる。この抽出操作は、地図データベース１３からブロックごとのノード情報、リンク情報をメモリ１５に一旦蓄積して行い、抽出が完了したブロックのデータは、直ちにメモリ１５上から開放される。
【００７２】
そして、特定の道路種別に関するノード情報、リンク情報だけを使用して、開始地点を含むブロック（または近隣のブロック）から、終了地点を含むブロックまでの経路探索処理を実行させる。開始地点を含むブロック内、終了地点を含むブロック内の経路探索は別に行って結果を加算すればよい。これにより、探索対象のノード数が大幅に削減され、処理の高速化、メモリ消費量の削減が達成される。
【００７３】
例えば、高速道路のみを抽出して経路探索処理を行う。ただし、初期のデータ読取りは、全道路を読み取る。このとき、高速道路の途中経路上のインターチェンジは、元のデータでは分岐を形成するノードであるが、間引き後のデータでは接続関係の無い行き止まりである。従って、これらのノードを基点として、高速道路の外に演算範囲が広がる心配が無い。
【００７４】
例えば、（１）　高速道路のみを抽出し、不要な領域を完全に無くして、データを並び換えて間を詰める。この場合、無駄な領域が無くなるため、データサイズが最小になるが、ＣＤ−ＲＯＭに記録されたオリジナルデータとの互換性が失われる。
【００７５】
あるいは、（２）　ノード番号、リンク番号はオリジナルデータとの互換性を保ちながら、接続関係等のみを変更する。経路探索以外の処理（表示、経路案内等）との関係で互換性を保つ必要がある場合には、この方法でデータを間引く。この場合、全体のデータサイズはやや大きくなるが、ノード番号、リンク番号を通じてオリジナルデータとの互換性を確保できる。例えば、ノード番号＝ノードテーブルに格納されている順序で０、１、２、…ｎというフォーマットを採用すればノード数は減らない。リンクに関しても同様である。
【００７６】
この機能が有効に機能する判定条件は、高速道路が通っていない最も長い陸上での直線距離よりも、経路探索する距離が長いときである。また、この機能が開始される条件は、始点（または終点）から高速道路までの距離が確定したときである。従って、操作者が開始地点と終了地点を設定した段階で、これらの条件を判定し、合致する場合に、自動的にこの機能に切り換えさせてもよい。
【００７７】
次にある特定の道路種別までの経路探索機能を説明する。ある特定の道路種別を例えば、高速道路とすると、この機能は、「最寄りの高速道路までの経路探索機能」と同意である。
【００７８】
通常の経路探索処理では、探索開始ノード〜探索終了ノードまでの経路を求める。この場合、探索処理の終了判定は、探索終了ノードまでの経路長が確定したときである。
【００７９】
これに対して、この機能では、探索終了判定条件を、「ある特定の道路種別のリンクに接続するノードまでの経路長が最初に確定したとき」に変更する。これにより、その後の演算処理については、通常の経路探索処理の場合と同様の演算方式、演算手順で実行する。
【００８０】
また、通常の「高速道路を特別扱いしない経路探索処理」と、この機能による経路探索処理とを切り換えるスイッチを持ち、操作者の指令を待って、探索処理の終了条件を切り換えるようにしている。
【００８１】
図９は、探索結果の保存、更新機能の説明図である。図中、（ａ）　は記録方法、（ｂ）　は表示画面を示す。ここでは、図１（ａ）　の経路データ保存部で、経路探索結果をＩＣカードに記録する際の操作が説明される。
【００８２】
図９（ａ）　において、ＩＣカードのＳＲＡＭの記憶容量は、予め一定の格納スペースを区分しておかない不定型で使用される。一方、記録容量を予め一定の格納スペースで区分する固定型では、格納スペースを越える経路探索結果を格納できない、全体の格納効率が低い等の問題がある。
【００８３】
例えば、４０ＫバイトのＳＲＡＭ７１を４つの格納番地に予め区分した場合、１０Ｋバイト以上の経路探索結果を格納できず、格納番地ごとに空きスペースが発生しても後からこれを埋めることができない。
【００８４】
これに対して、４０ＫバイトのＳＲＡＭ７２を不定型で使用すると、過去の複数の経路探索結果が、途中に空きスペースを形成することなく頭詰めされ、格納効率が高まる。そして、空きスペース７２Ｂに対して、新規の経路探索結果を格納することができる。
【００８５】
図９（ｂ）　において、新規の経路探索結果を格納する際には、図１（ａ）　の表示部に操作画面７３が出力される。操作者は、操作画面７３を視認しながら、操作盤７４を操作する。これにより、新規の経路探索結果がＩＣカードに記録され、ＩＣカードの記録内容の編集も可能となる。
【００８６】
操作画面７３には、記録済みの経路探索結果の一覧表示７３Ａ、選択マーク７３Ｂ、新規の探索結果のデータ量表示７３Ｃ、保存可／不可表示７３Ｄ、保存可能な容量表示７３Ｅが表示される。一方、操作盤７４は、カーソル移動スイッチ７４Ａ、７４Ｂ、選択確定スイッチ７４Ｃ、保存スイッチ７４Ｄ、抹消スイッチ７４Ｅを配置する。
【００８７】
操作者が探索結果をＩＣカードのＳＲＡＭ７２上にランダム（不定型）に保存する場合、（１）　新規の経路探索結果を保持するだけの空き領域７２Ｂがメモリ上にある場合は、その空き領域７２Ｂに新規の経路探索結果を保持する。この場合は、表示画面７３の保存可／不可表示７３Ｄは保存可と表示され、操作者が保存スイッチ７４Ｄを操作すれば、直ちに記録が実行される。
【００８８】
しかし、（２）　新規の経路探索結果を保持するだけの空き領域７２ＢがＳＲＡＭ７２に無い場合、過去に記録した結果のうち、操作者が削除してもよいと指定した結果のサイズと空き容量を加算した数値が、保存可能な容量表示７３Ｅに出力される。これをサイズＡとする。また、新規の経路探索結果のサイズの数値を、新規の探索結果のデータ量表示７３Ｃに出力する。これをサイズＢとする。
【００８９】
さらに、上記のサイズＡ、Ｂの大小関係を調べて、保存可／不可表示７３Ｄに出力する。保持できるか否かは、「サイズＡ≦サイズＢ」で判定する。この関係が成り立つ場合には、保存可を表示する。
【００９０】
操作者による削除の指定は、表示画面７３の一覧表示７３Ａに基づいて操作者がカーソル移動スイッチ７３Ａ、７３Ｂを移動し、選択確定スイッチ７４Ｃを操作して行われる。指定された経路探索結果に対して、選択マーク７３Ｂが出力される。指定された経路探索結果（複数でもよい）の容量を空き領域７２Ｂの容量に加算した数値が容量表示７３Ｅに出力される。保存可／不可表示７３Ｄに保存可が表示された段階で、操作者が保存スイッチ７４Ｄを操作すれば、直ちに指定された経路探索結果が消去され、残りの経路探索結果がＳＲＡＭ７２に頭詰め記録され、形成された空きスペースに新規の経路探索結果が記録される。
【００９１】
結果の更新（入替え）を行う場合の処理手順は次のとおりである。（１）　操作者が指定したデータを削除する。（２）　削除した領域を埋めるように、結果の領域を移動（メモリコピー）する。連続した空き領域を確保するためである。（３）　空き領域に新しい結果を記録する。
【００９２】
ところで、新規の経路探索結果を保持するだけの空き領域７２ＢがＳＲＡＭ７２に無い場合、操作者の指定操作を待たずに、「サイズＡ≦サイズＢ」の関係を満たす経路探索結果の組合せを表示画面７３に表示させてもよい。
【００９３】
消去推薦リストに掲載される経路探索結果の選別方法には、以下の手法を採用できる。（１）　１つの経路探索結果を消去するだけで新規の経路探索結果を記録可能になる場合には、その１つの経路探索結果を選択する。（２）　複数の経路探索結果を消去しないと新規の経路探索結果を記録できない場合には、消去すべき経路探索結果の数が最小で、合計サイズが最小となる組合せを選択する。（３）　古い経路探索結果から順番に選択する。これらの自動選択機能は、操作者が任意に選択できるようにしてもよい。
【００９４】
【発明の効果】
請求項１の経路探索装置によれば、終了地点の地名が表示されるので、終了地点の設定確認もできる。
【００９５】
請求項２の経路探索装置では、開始地点の地名も表示されるので、更に開始地点の設定確認もできる。
【００９６】
請求項３の経路探索装置では、終了地点付近に存在する地名が検出され表示されるので、終了地点の設定確認が分かりやすくなる。
【００９７】
請求項４の経路探索装置では、終了地点付近に存在するリンク定法に基づく地名が検出され表示されるので、終了地点の設定確認も分かりやすくなる。
【００９８】
請求項５の経路探索装置では、開始地点付近に存在する地名が検出され表示されるので、開始地点の設定確認が分かりやすくなる。
【００９９】
請求項６の経路探索装置では、開始地点付近に存在するリンク定法に基づく地名が検出され表示されるので、開始地点の設定確認も分かりやすくなる。
【図面の簡単な説明】
【図１】実施例の経路探索装置の説明図である。
【図２】処理プログラムの説明図である。
【図３】表示内容の説明図である。
【図４】地点設定機能の説明図である。
【図５】ノードの親子関係データの作成の説明図である。
【図６】階層的経路探索の説明図である。
【図７】階層的経路探索結果の説明図である。
【図８】探索における地図切り出し法の説明図である。
【図９】探索結果の保存、更新機能の説明図である。
【符号の説明】
１１　入力部
１２　経路データ保存部（第３記憶手段）
１３　地図データベース（第１記憶手段）
１４　位置センサー
１５　メモリ（第２記憶手段）
１６　処理部（演算手段等）
１７　表示部
１７Ａ　棒グラフ（第１表示手段）
１７Ｂ　棒グラフ（第２表示手段）
【図１】
2004085558.tif 000003
【図２】
2004085558.tif 000004
【図３】
2004085558.tif 000005
【図４】
2004085558.tif 000006
【図５】
2004085558.tif 000007
【図６】
2004085558.tif 000008
【図７】
2004085558.tif 000009
【図８】
2004085558.tif 000010
【図９】
2004085558.tif 000011