(57)【要約】  経路探索装置（１００）は、記録部（１１０）と、入力部（１２０）と、抽出部（１３０）と、探索部（１４０）とを備える。記録部（１１０）は、テーブル（１１１）とエリア内経路データ（１１２）とを有する。テーブル（１１１）は、出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたものである。エリア内経路データ（１１２）は、各エリア内にてエリアの境界に位置する境界ノード同士を結んだデータを含む。入力部（１２０）は、出発地点および目的地点の入力を受け付ける。抽出部（１３０）は、出発エリアおよび目的エリアの組合せに基づき、出発エリアから目的エリアまでの間に経由する経由エリアの列をテーブル（１１１）から抽出する。探索部（１４０）は、経由エリアのエリア内経路データ（１１２）を用いて、出発地点から目的地点までの経路を探索する。
2010013327.tif 000002
【特許請求の範囲】
【請求項１】
出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録手段と、
出発地点および目的地点の入力を受け付ける入力手段と、
前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出手段と、
前記経由エリアのエリア内経路データを用いて、前記出発地点から前記目的地点までの経路を探索する探索手段と、
を備えることを特徴とする経路探索装置。
【請求項２】
前記テーブルは、出発エリアおよび目的エリアの一の組合せに対して複数の経由エリアの列が対応付けられており、
前記抽出手段は、前記出発地点が属するエリアおよび前記目的地点が属するエリアに基づいて、一の経由エリアの列を抽出することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記記録手段は、探索条件ごとの前記テーブルを記録し、
前記入力手段は、前記出発地点および前記目的地点とともに探索条件の入力を受け付け、
前記抽出手段は、前記入力手段が受け付けた前記探索条件に対応した前記経由エリアの列を前記テーブルから抽出し、
前記探索手段は、前記経由エリアのエリア内経路データを用いて、前記探索条件を充足する前記出発地点から前記目的地点までの経路を探索することを特徴とする請求項１または２に記載の経路探索装置。
【請求項４】
前記テーブルの更新情報を取得する取得手段と、
前記更新情報に基づいて、前記記録手段に記録されている前記テーブルを更新する更新手段と、
を備えることを特徴とする請求項１〜３のいずれか一つに記載の経路探索装置。
【請求項５】
前記エリア内経路データの更新情報を取得する取得手段と、
前記更新情報に基づいて、前記記録手段に記録されている前記エリア内経路データをエリアごとに更新する更新手段と、
を備えることを特徴とする請求項１〜４のいずれか一つに記載の経路探索装置。
【請求項６】
出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録部を備えた経路探索装置の経路探索方法であって、
出発地点および目的地点の入力を受け付ける入力工程と、
前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出工程と、
前記経由エリアのエリア内経路データを用いて、前記出発地点から前記目的地点までの経路を探索する探索工程と、
を含むことを特徴とする経路探索方法。
【請求項７】
請求項６に記載の経路探索方法をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項８】
請求項７に記載の経路探索プログラムを記録したことを特徴とするコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、経路探索装置、経路探索方法、経路探索プログラム、および記録媒体に関する。
【背景技術】
【０００２】
近年、車両などの移動体には、目的地点を設定することにより、当該目的地点までの経路を誘導するナビゲーション装置が搭載されている。この種のナビゲーション装置は、目的地点までの経路を探索する経路探索機能を有している。【０００３】
経路探索をおこなうために、通常、ナビゲーション装置には、階層構造をなす経路計算用データが格納されている。遠距離の経路計算をおこなう場合、候補となる道路数が多く、経路計算に時間を要するため、遠距離用の上位階層の経路計算用データには、出発地点のエリアと目的地点のエリアとを組合せ、その間の経路計算に必要なリンクのデータを記録するようにした手法が採られている。【０００４】
図１０および図１１を用いて、従来の一般的な遠距離計算用のデータの詳細について説明しておく。図１０は、従来の遠距離用経路計算データの組合せの一例を示した説明図である。図１０において、組合せデータ１０００は、出発地点のエリアと目的地点のエリアの組合せを示したものである。各エリアの組合せごとに、それぞれ、経路計算に必要なリンクデータが記録されている。具体例として、符号１００１に示す南関東エリアと近畿エリアとの組合せにおけるリンクデータについて、図１１を用いて以下に説明する。なお、組合せデータのうち、網点に示す領域のリンクデータについては後述する。【０００５】
図１１は、従来の遠距離用経路計算データにおける、各エリアの組合せごとのリンクデータを示した説明図である。図１１において、リンクデータ１１００は、南関東エリアと近畿エリアとの間の経路計算に用いられるデータを示したものである。たとえば、東京駅１１０１を出発地点とした南関東エリアから、大阪駅１１０２を目的地点とした近畿エリアまでの経路として、東海地方（南側）を通るルートや甲信越地方（北側）を通るルートなど、候補となるルートが予め多数記録されている。東京駅１１０１を出発地点とし、大阪駅１１０２を目的地点とした経路探索処理を実行する場合は、この中から、探索条件等に合致する最適なルートを絞り込むことにより、経路が決定される。【０００６】
また、このような遠距離計算用のデータをもつ技術として、遠距離の計算を迅速化させるために、地図上の各地域を複数の区画に分割し、各区画内の高速道路などの主要道路、およびインターチェンジなどの当該主要道路への接続点を予め記録しておき、経路探索時には、始点を含む区画および終点を含む区画から主要道路を特定するとともに、始点を含む区画および終点を含む区画の各区画内の各地点からそれぞれ主要道路の接続点までの経路を特定するようにした技術が提案されている（たとえば、下記特許文献１参照。）。【０００７】
【特許文献１】特開平１１−６４０２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した従来技術では、経路計算用データのデータ量が膨大であるといった問題が一例として挙げられる。特に、更新時におけるデータ量が多いため、更新に時間がかかるといった問題もある。【０００９】
なお、ここで、図１０を用いて、更新時に更新するデータについて補足しておく。たとえば、南関東のエリアに属する厚木から、北関東のエリアに属する久喜までの間に新たに高速道路が開通したと想定した場合、図１０の網点に示す組合せのリンクデータを全て更新することになる。つまり、北陸エリア以西のエリア同士の組合せや、東北エリア以北のエリア同士の組合せを除き、南関東エリアと北関東エリアとを結ぶ経路をもつ各エリアの組合せについては、それぞれリンクデータを更新する必要がある。【００１０】
すなわち、南関東から北関東を跨ぐ主要道路が１本追加されただけで、組合せデータ１０００のうち、半分以上の組合せについて更新しなければならないという問題がある。したがって、利用者が特定のエリアのみの更新を所望する場合であっても、当該エリアのみを更新することができず、更新時におけるデータ量が膨大になるといった問題がある。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、請求項１の発明にかかる経路探索装置は、出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録手段と、出発地点および目的地点の入力を受け付ける入力手段と、前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出手段と、前記経由エリアのエリア内経路データを用いて、前記出発地点から前記目的地点までの経路を探索する探索手段と、を備えることを特徴とする。【００１２】
また、請求項６に記載の経路探索方法は、出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録部を備えた経路探索装置の経路探索方法であって、出発地点および目的地点の入力を受け付ける入力工程と、前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出工程と、前記経由エリアのエリア内経路データを用いて、前記出発地点から前記目的地点までの経路を探索する探索工程と、を含むことを特徴とする。【００１３】
また、請求項７に記載の経路探索プログラムは、請求項６に記載の経路探索方法をコンピュータに実行させることを特徴とする。【００１４】
また、請求項８に記載の記録媒体は、請求項７に記載の経路探索プログラムをコンピュータに読み取り可能に記録したことを特徴とする。
【図面の簡単な説明】
【００１５】
【図１】図１は、本実施の形態にかかる経路探索装置の機能的構成の一例を示すブロック図である。
【図２】図２は、本実施の形態にかかる経路探索装置の経路探索処理手順の一例を示すフローチャートである。
【図３】図３は、本実施例にかかるナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【図４】図４は、遠距離経路の一例を示す説明図である。
【図５】図５は、磁気ディスクに記録されている遠距離用経路計算データの一例を示す説明図である。
【図６】図６は、エリア内経路データの一例を示した説明図である。
【図７】図７は、エリアを細分化した場合のエリア内経路データの一例を示した説明図である。
【図８】図８は、ナビゲーション装置がおこなう経路探索処理の一例を示したフローチャートである。
【図９】図９は、ナビゲーション装置がおこなうデータ更新処理を示すフローチャートである。
【図１０】図１０は、従来の遠距離用経路計算データの組合せの一例を示した説明図である。
【図１１】図１１は、従来の遠距離用経路計算データにおける、各エリアの組合せごとのリンクデータを示した説明図である。
【符号の説明】
【００１６】
１００  経路探索装置
１１０  記録部
１１１  テーブル
１１２  エリア内経路データ
１２０  入力部
１３０  抽出部
１４０  探索部
１５０  出力部
１６０  取得部
１７０  更新部
３００  ナビゲーション装置
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明にかかる経路探索装置、経路探索方法、経路探索プログラム、および記録媒体の好適な実施の形態を詳細に説明する。【００１８】
（実施の形態）
（経路探索装置の機能的構成）
この発明の実施の形態にかかる経路探索装置の機能的構成について説明する。図１は、本実施の形態にかかる経路探索装置の機能的構成の一例を示すブロック図である。図１において、経路探索装置１００は、記録部１１０と、入力部１２０と、抽出部１３０と、探索部１４０と、出力部１５０と、取得部１６０と、更新部１７０とを備えて構成される。【００１９】
記録部１１０は、テーブル１１１とエリア内経路データ１１２とを記録する。なお、本実施の形態において、対象とするデータは、階層構造をなす経路計算用データのうち、たとえば、最上位の階層、またはそれに準ずる階層の遠距離用経路計算データである。出発エリアとは、出発地点が含まれるエリアである。なお、出発地点は、ユーザが任意に選択した地点や、目的地点を入力した際の現在地点などである。目的エリアは、目的地点が含まれるエリアである。【００２０】
テーブル１１１は、出発エリアおよび目的エリアの組合せと、当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたものである。テーブル１１１は、具体的には、たとえば、南関東エリアを出発エリアとし、中国エリアを目的エリアとした組合せに対して、静岡や愛知などの東海エリアと近畿エリアを経由する経由エリアの列を対応付けたものである。このテーブル１１１は、各エリアに付されたエリアＩＤなどのテキストデータを、各組合せごとに経由エリア順に列挙したものである。【００２１】
エリア内経路データ１１２は、各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだデータである。具体的には、エリア内経路データ１１２は、境界ノード同士を結ぶ経路に使用されるリンクのみを含むデータである。また、エリア内経路データ１１２は、隣接エリアの組合せに応じて異なるデータとしてもよいし、各リンクに隣接エリアの組合せごとに、使用する／しないのフラグを設け、同一のデータとしてもよい。たとえば、東海エリアのエリア内経路データ１１２を例に挙げると、エリア内経路データ１１２は、南関東エリアとの境界に位置する境界ノードと、近畿エリアとの境界に位置する境界ノードとを結んだ複数のリンク列のデータである。【００２２】
入力部１２０は、出発地点および目的地点の入力を受け付ける。入力部１２０による入力を受け付ける手法は、操作入力や音声入力などが挙げられる。【００２３】
抽出部１３０は、出発地点が属するエリアおよび目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列をテーブル１１１から抽出する。具体的には、抽出部１３０は、出発地点が属するエリアを決定するとともに、目的地点が属するエリアを決定し、各エリアの組合せに基づいて、経由エリアの列を抽出する。【００２４】
探索部１４０は、経由エリアのエリア内経路データ１１２を用いて、出発地点から目的地点までの経路を探索する。具体的には、探索部１４０は、抽出部１３０によって抽出された経由エリアの列に含まれる各経由エリアごとに、境界ノード間の経路を計算することにより出発地点から目的地点までの経路を探索する。また、探索部１４０は、複数の経路を探索してもよい。探索部１４０は、エリアごとに順番に経路を計算してもよいし、必要なエリアを同時に読み込んで、まとめて経路を計算してもよい。【００２５】
出力部１５０は、探索部１４０によって探索された経路の情報を出力する。出力部１５０は、探索された経路を、ユーザに選択させるために不図示の表示部や音声出力部などに出力するほか、経路誘導用のデータとしてＲＡＭなどに出力する。【００２６】
また、本実施の形態において、テーブル１１１は、出発エリアおよび目的エリアの一の組合せに対して複数の経由エリアの列を対応付けたものとしてもよい。具体的には、テーブル１１１は、たとえば、南関東エリアを出発エリアとし、中国エリアを目的エリアとした組合せに対して、東海エリアと近畿エリアを経由する経由エリアの列や、山梨や長野などの甲信越エリアと近畿エリアを経由する経由エリアの列など、複数の経由エリアの列を対応付けたものである。【００２７】
この場合、抽出部１３０は、出発地点が属するエリアおよび目的地点が属するエリアに基づいて、一の経由エリアの列を抽出する。具体的には、抽出部１３０は、たとえば、出発エリア内の出発地点や目的エリア内の目的地点の位置や、後述する探索条件などに応じてリンク列を選択して抽出する。【００２８】
また、本実施の形態において、記録部１１０は、探索条件ごとのテーブル１１１を記録してもよい。この場合、入力部１２０は、出発地点および目的地点とともに探索条件の入力を受け付ける。抽出部１３０は、入力部１２０が受け付けた探索条件に対応した経由エリアの列をテーブル１１１から抽出する。また、探索部１４０は、経由エリアのエリア内経路データ１１２を用いて、探索条件を充足する出発地点から目的地点までの経路を探索する。【００２９】
このようにテーブル１１１を探索条件ごとに区別していれば、エリア内経路データ１１２を、探索条件にかかわらず、共通のものを用いることも可能である。なお、この場合、探索条件ごとに、各リンクにフラグを設定すればよい。すなわち、時間優先や距離優先などの各探索条件に応じて、エリア内経路データ１１２内の各リンクのフラグをオンまたはオフに設定し、探索条件に対応した経路探索をおこなえるようにすればよい。なお、エリア内経路データ１１２を、探索条件ごとに異なるデータとして記録しておくようにしてもよい。【００３０】
また、本実施の形態において、取得部１６０と、更新部１７０とは、任意の構成要素である。取得部１６０は、テーブル１１１の更新情報を取得する。テーブル１１１の更新情報は、具体的には、たとえば、各組合せごとに経由エリア順に列挙したエリアＩＤなどのテキストデータである。【００３１】
更新部１７０は、取得部１６０によって取得されたテーブル１１１の更新情報に基づいて、記録部１１０に記録されているテーブル１１１を更新する。具体的には、更新情報がテーブルを書き換えるためのテキストデータを示すものである場合、更新部１７０はテーブル１１１のテキストデータのみを書き換えればよい。なお、更新部１７０は、出発エリアおよび目的エリアの組合せごとにテーブル１１１を更新してもよい。【００３２】
また、本実施の形態において、取得部１６０は、エリア内経路データ１１２の更新情報を取得してもよい。この場合、更新部１７０は、エリア内経路データ１１２の更新情報に基づいて、記録部１１０に記録されているエリア内経路データ１１２をエリアごとに更新する。すなわち、更新部１７０は、更新のあったエリア内経路データ１１２のみを差し替えればよい。なお、テーブル１１１ごとの更新、およびエリア内経路データ１１２ごとの更新をまとめて更新することも可能である。【００３３】
（経路探索装置の経路探索処理手順）
つぎに、図２を用いて、経路探索装置１００の経路探索処理手順について説明する。図２は、本実施の形態にかかる経路探索装置１００の経路探索処理手順の一例を示すフローチャートである。【００３４】
図２のフローチャートにおいて、経路探索装置１００は、入力部１２０が出発地点および目的地点の入力を受け付けたか否かを判断する（ステップＳ２０１）。入力部１２０が出発地点および目的地点の入力を受け付けるまで待機状態にあり（ステップＳ２０１：Ｎｏのループ）、当該入力を受け付けると（ステップＳ２０１：Ｙｅｓ）、抽出部１３０により、出発地点が属するエリアおよび目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列をテーブル１１１から抽出する（ステップＳ２０２）。【００３５】
そして、探索部１４０が経由エリアのエリア内経路データ１１２を用いて、出発地点から目的地点までの経路を探索する（ステップＳ２０３）。このあと、出力部１５０が経路の情報を出力し（ステップＳ２０４）、一連の処理を終了する。【００３６】
以上説明したように、本実施の形態にかかる経路探索装置１００によれば、出発地点が属するエリアから目的地点が属するエリアまでの間に経由する経由エリアの列をテーブル１１１から抽出し、経由エリアのエリア内経路データを用いて、出発地点から目的地点までの経路を探索するようにしたので、迅速な経路探索処理を可能としながら、遠距離用経路計算データのデータ容量を削減することができる。【００３７】
また、本実施の形態において、テーブル１１１を、出発エリアおよび目的エリアの一の組合せに対して複数の経由エリアの列を対応付けたものとし、当該テーブル１１１から一の経由エリアの列を抽出するようにすれば、遠距離用経路計算データのデータ容量を削減しながら、複数の経路の中から最適な経路を提示することができる。【００３８】
また、本実施の形態において、探索条件ごとのテーブル１１１を記録しておき、利用者から受け付けた探索条件に対応した経由エリアの列をテーブル１１１から抽出し、探索条件を充足する出発地点から目的地点までの経路を探索するようにすれば、遠距離用経路計算データのデータ容量を削減しながら、利用者の所望する探索条件に応じた最適な経路を提示することができる。【００３９】
また、本実施の形態において、テーブル１１１の更新情報を取得するようにし、当該更新情報に基づいて、テーブル１１１を更新するようにすれば、たとえば、テキストデータのみを書き換えることにより、更新するデータ量を削減することができる。したがって、更新に要するコストを抑えることができる。【００４０】
また、本実施の形態において、エリア内経路データ１１２の更新情報を取得するようにし、当該更新情報に基づいて、エリア内経路データ１１２をエリアごとに更新するようにすれば、エリア単位で更新をおこなうことができ、更新するデータ量を削減することができる。したがって、更新に要するコストを抑えることができる。
【実施例】
【００４１】
以下に、本発明の実施例について説明する。本実施例では、車両に搭載されるナビゲーション装置によって、本発明の経路探索装置１００を実施した場合の一例について説明する。【００４２】
（ナビゲーション装置のハードウェア構成）
図３を用いて、本実施例にかかるナビゲーション装置のハードウェア構成について説明する。図３は、本実施例にかかるナビゲーション装置のハードウェア構成の一例を示すブロック図である。【００４３】
図３において、ナビゲーション装置３００は、ＣＰＵ３０１と、ＲＯＭ３０２と、ＲＡＭ３０３と、磁気ディスクドライブ３０４と、磁気ディスク３０５と、光ディスクドライブ３０６と、光ディスク３０７と、音声Ｉ／Ｆ（インターフェース）３０８と、スピーカ３０９と、入力デバイス３１０と、映像Ｉ／Ｆ３１１と、ディスプレイ３１２と、通信Ｉ／Ｆ３１３と、ＧＰＳユニット３１４と、各種センサ３１５とを備えている。また、各構成部３０１〜３１５はバス３２０によってそれぞれ接続されている。【００４４】
ＣＰＵ３０１は、ナビゲーション装置３００の全体の制御を司る。ＲＯＭ３０２やフラッシュＲＯＭ等の書換え可能な不揮発性メモリは、ブートプログラム、現在地点算出プログラム、経路探索プログラム、経路誘導プログラム、更新プログラム、などの各種プログラムを記録している。また、ＲＡＭ３０３は、ＣＰＵ３０１のワークエリアとして使用される。【００４５】
現在地点算出プログラムは、たとえば、後述するＧＰＳユニット３１４の出力情報に基づいて、車両の現在地点（ナビゲーション装置３００の現在地点）を算出させる。【００４６】
経路探索プログラムは、磁気ディスク３０５に記録されている地図データや経路計算データなどを利用して、出発地点から目的地点までの最適な経路を探索させる。ここで、最適な経路とは、目的地点までの最短（または最速）経路やユーザが指定した条件に最も合致する経路などである。また、目的地点のみならず、立ち寄り地点や休憩地点までの経路を探索してもよい。探索された誘導経路は、ＣＰＵ３０１を介して音声Ｉ／Ｆ３０８や映像Ｉ／Ｆ３１１へ出力される。【００４７】
また、経路探索プログラムは、遠距離の経路計算においては、磁気ディスク３０５に記録されている後述するテーブルやエリア内経路データを用いて、出発地点から目的地点までの経路を探索するプログラムである。具体的には、出発地点が属するエリアおよび目的地点が属するエリアの組合せに基づき、出発地点が属するエリアから目的地点が属するエリアまでの間に経由する経由エリアの列をテーブルから抽出して、各エリア内経路データを用いて、出発地点から目的地点までの経路を探索するプログラムである。【００４８】
経路誘導プログラムは、経路探索プログラムを実行することによって探索された誘導経路情報、現在地点算出プログラムを実行することによって算出された車両の現在地点の情報、磁気ディスク３０５から読み出された地図データに基づいて、リアルタイムな経路誘導情報を生成させる。生成された経路誘導情報は、ＣＰＵ３０１を介して音声Ｉ／Ｆ３０８や映像Ｉ／Ｆ３１１へ出力される。【００４９】
更新プログラムは、通信Ｉ／Ｆ３１３により取得されたテーブルまたはエリア内経路データの更新情報に基づいて、磁気ディスク３０５に記録されているテーブルまたはエリア内経路データを更新するプログラムである。【００５０】
図１に示した、抽出部１３０と、探索部１４０と、更新部１７０とは、ＣＰＵ３０１によって実現される。すなわち、ＣＰＵ３０１が経路探索プログラムを実行することによって、抽出部１３０と探索部１４０の機能を実現する。また、ＣＰＵ３０１が更新プログラムを実行することにより更新部１７０の機能を実現する。【００５１】
磁気ディスクドライブ３０４は、ＣＰＵ３０１の制御にしたがって磁気ディスク３０５に対するデータの読み取り／書き込みを制御する。磁気ディスク３０５は、磁気ディスクドライブ３０４の制御で書き込まれたデータを記録する。磁気ディスク３０５としては、たとえば、ＨＤ（ハードディスク）やＦＤ（フレキシブルディスク）を用いることができる。磁気ディスク３０５には、地図データや経路計算データが記録される。【００５２】
経路計算データは、階層構造をなしており、上位階層に遠距離用のデータを有し、下位階層になるほど近距離用のデータを有している。この遠距離用の経路計算データは、出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する一または複数の経由エリアの列とが対応付けられたテーブルを有している。このテーブルには、探索条件ごとに経由エリアの列が記録されている。また、遠距離用経路計算データは、エリアごとに、各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを有している。【００５３】
また、磁気ディスクドライブ３０４を着脱自在な構成としてもよい。この場合、着脱可能な磁気ディスクドライブ３０４を、更新された経路計算データが記録されている図示しないＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）などに接続することにより、更新情報を読み込むようにしてもよい。【００５４】
光ディスクドライブ３０６は、ＣＰＵ３０１の制御にしたがって光ディスク３０７に対するデータの読み取り／書き込みを制御する。光ディスク３０７は、光ディスクドライブ３０６の制御にしたがってデータの読み出される着脱自在な記録媒体である。光ディスク３０７は、書き込み可能な記録媒体を利用することもできる。また、この着脱自在な記録媒体として、光ディスク３０７のほか、ＭＯ、メモリカードなどであってもよい。【００５５】
光ディスクドライブ３０６は、光ディスク３０７として、更新された経路計算データを記録したものが挿入されると、当該光ディスク３０７に記録されている更新された経路計算データ（更新情報）の読み込みをおこなう。なお、本実施例においては、更新情報は通信Ｉ／Ｆ３１３によって取得されるものとする。【００５６】
音声Ｉ／Ｆ３０８は、スピーカ３０９に接続される。スピーカ３０９からは、音声情報が出力される。入力デバイス３１０は、文字、数値、各種指示などの入力のための複数のキーを備えたリモコン、キーボード、マウス、タッチパネルなどが挙げられる。入力デバイス３１０は、リモコン、キーボード、マウス、タッチパネルのうち、いずれか一つの形態によって実現されてもよいし、複数の形態によって実現されてもよい。入力デバイス３１０は、出発地点および目的地点の入力を受け付ける。図１に示した、入力部１２０は、入力デバイス３１０によって実現される。【００５７】
映像Ｉ／Ｆ３１１は、ディスプレイ３１２と接続される。映像Ｉ／Ｆ３１１は、具体的には、たとえば、ディスプレイ３１２全体の制御をおこなうグラフィックコントローラと、即時表示可能な画像情報を一時的に記録するＶＲＡＭ（Ｖｉｄｅｏ  ＲＡＭ）などのバッファメモリと、グラフィックコントローラから出力される画像データに基づいて、ディスプレイ３１２を表示制御する制御ＩＣなどによって構成される。【００５８】
ディスプレイ３１２には、アイコン、カーソル、メニュー、ウインドウ、あるいは文字や画像などの各種データが表示される。このディスプレイ３１２は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。上述したナビゲーションプログラムを実行することにより、ディスプレイ３１２からは、探索された経路の情報が表示される。なお、図１に示した出力部１５０は、ディスプレイ３１２によって実現される。【００５９】
通信Ｉ／Ｆ３１３は、無線を介してインターネットなどの通信網に接続され、この通信網とＣＰＵ３０１とのインターフェースとして機能する。また、通信Ｉ／Ｆ３１３は、図示せぬ外部サーバから、更新された経路計算データ（更新情報）を受信する機能を有する。【００６０】
ＧＰＳユニット３１４は、ＧＰＳ衛星からの電波を受信し、車両の現在地点を示す情報を出力する。ＧＰＳユニット３１４の出力情報は、ＣＰＵ３０１による車両の現在地点の算出に際して利用される。現在地点を示す情報は、たとえば緯度・経度、高度などの、地図データ上の１点を特定する情報である。【００６１】
各種センサ３１５は、車速センサ、加速度センサ、角速度センサなどの、車両の位置や挙動を判断することが可能な情報を出力する。各種センサ３１５の出力値は、ＣＰＵ３０１による車両の現在地点の算出や、速度や方位の変化量の測定などに用いられる。【００６２】
図１に示した本実施の形態における経路探索装置１００が備える、記録部１１０と、入力部１２０と、抽出部１３０と、探索部１４０と、出力部１５０と、取得部１６０と、更新部１７０とは、図３に示したナビゲーション装置３００におけるＲＯＭ３０２やフラッシュＲＯＭ等の書換え可能な不揮発性メモリ、ＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などに記録されたプログラムやデータを用いて、ＣＰＵ３０１が所定のプログラムを実行し、ナビゲーション装置３００における各部を制御することによってその機能を実現する。【００６３】
すなわち、本実施例のナビゲーション装置３００は、ナビゲーション装置３００における記録媒体としてのＲＯＭ３０２やフラッシュＲＯＭ等の書換え可能な不揮発性メモリに記録されている経路探索プログラムをＣＰＵ３０１が実行することにより、図１に示した経路探索装置１００が備える機能を、図２に示した経路探索処理手順で実行することができる。【００６４】
（遠距離経路の一例）
つぎに、図４を用いて、遠距離経路の一例について説明する。図４は、遠距離経路の一例を示す説明図である。図４において、エリア４００は、都道府県ごとの区画を示している。遠距離経路４０１は、東京エリア４００ａを出発地点とし、大阪エリア４００ｂを目的地点とした場合の経路を示したものである。なお、大阪エリア４００ｂを出発地点とし、東京エリア４００ａを目的地点とした逆の経路の場合についても同様である。【００６５】
遠距離経路４０１ａは、神奈川エリア、静岡エリア、愛知エリア、岐阜エリア、滋賀エリア、京都エリア、を経由して大阪エリアに到達する経路である。遠距離経路４０１ｂは、神奈川エリア、山梨エリア、長野エリア、愛知エリア、岐阜エリア、滋賀エリア、京都エリア、を経由して大阪エリアに到達する経路である。なお、遠距離経路４０１は、ここでは２つのみを例示しているが、実際には多数存在する。このような遠距離経路４０１のデータの持ち方について、以下に説明する。【００６６】
（磁気ディスクに記録されている遠距離用経路計算データの一例）
つぎに、図５および図６を用いて、磁気ディスク３０５に記録されている遠距離用経路計算データの一例について説明する。図５は、磁気ディスク３０５に記録されている遠距離用経路計算データの一例を示す説明図である。【００６７】
図５において、遠距離用経路計算データは、テーブル５００からなる。テーブル５００は、出発エリア５０１と、目的エリア５０２と、探索条件５０３と、経路ナンバー５０４と、経由エリアの列５０５とを有している。出発エリア５０１は、出発地点が属するエリアである。目的エリア５０２は、目的地点が属するエリアである。【００６８】
探索条件５０３は、探索時における条件を示したものであり、具体的には、目的地点までの所要時間を優先する時間優先、目的地点までの最短距離を優先する距離優先、高速道路を迂回する一般道優先などがある。経由エリアの列５０５は、出発エリアおよび目的エリアの組合せに対応して設定される経由エリアを、テキストデータであるエリアの番号の順に列挙したものである。なお、このテーブル５００内に示す番号は、図４に示したエリア４００の各エリア番号を示したものである。【００６９】
すなわち、テーブル５００のうち、出発エリア５０１に示す番号１は東京エリアを示し、目的エリア５０２に示す番号１２は、大阪エリアを示している。また、経由エリアの列５０５のうち、符号５１０に示す経路は、図４に示した遠距離経路４０１ａを示しており、すなわち、２：神奈川エリア、４：静岡エリア、５：愛知エリア、７：岐阜エリア、９：滋賀エリア、１１：京都エリア、を経由して１２：大阪エリアに到達する経路である。【００７０】
また、経由エリアの列５０５のうち、符号５１１に示す経路は、図４に示した遠距離経路４０１ｂを示しており、すなわち、２：神奈川エリア、３：山梨エリア、６：長野エリア、５：愛知エリア、７：岐阜エリア、９：滋賀エリア、１１：京都エリア、を経由して１２：大阪エリアに到達する経路である。【００７１】
このようなテーブル５００を用いて、出発エリア５０１と目的エリア５０２とが決定されると、探索条件５０３に応じた経由エリアの列５０５を抽出することが可能になっている。なお、ここでは、都道府県単位にエリアを区切った場合を例に挙げたが、これに限られるものではなく、たとえば、都道府県をさらに細分化した地区単位、関東地方や近畿地方などの地方単位、国境のある地域においては国単位、などとすることも可能である。【００７２】
図６は、エリア内経路データの一例を示した説明図である。図６において、エリア内経路データ６００は、たとえば、滋賀エリアのデータを示している。境界ノード６０１は、エリアの境界に位置するノードを示している。リンク列６０２は、一方の境界ノード６０１ａから他方の境界ノード６０１ｂまでを結ぶリンクの繋がりを示したものである。このように、岐阜エリアから、滋賀エリアを経由した京都エリアまでの経路は、複数通りある。各リンクは、探索条件に応じて使用するリンクにオン／オフのフラグが設定されるようになっており、探索条件に応じた経路探索が可能になっている。【００７３】
なお、ここでは、各エリアを都道府県単位としているが、各エリアをさらに細分化することにより、エリア内経路データ６００の絞り込みを効率的におこなうことも可能である。以下に、各エリアを細分化した場合のエリア内経路データについて補足しておく。【００７４】
図７は、エリアを細分化した場合のエリア内経路データの一例を示した説明図である。図７において、各エリアは、都道府県単位に区画され、さらに、各都道府県を南北に分けたものである。たとえば、岐阜北エリアから、京都北エリアまでの経路は、図中太線で示した経路となる。すなわち、経路探索時において、岐阜北から京都南までの経路や、岐阜南から京都北または京都南までの経路は、経路探索の対象から除外される。したがって、エリア内経路データ６００の絞り込みを効率的におこなうことが可能になり、迅速な経路探索処理をおこなうことが可能になる。【００７５】
（ナビゲーション装置がおこなう経路探索処理の一例）
つぎに、図８を用いて、ナビゲーション装置３００がおこなう経路探索処理の一例について説明する。図８は、ナビゲーション装置３００がおこなう経路探索処理の一例を示したフローチャートである。【００７６】
図８において、ナビゲーション装置３００のＣＰＵ３０１は、利用者により、入力デバイス３１０から出発地点および目的地点の入力を受け付けたか否かを判断する（ステップＳ８０１）。なお、通常、利用者が出発地点を特に指定しない限り、出発地点は現在地点となる。【００７７】
ステップＳ８０１において、出発地点および目的地点の入力を受け付けるまで待機状態にあり（ステップＳ８０１：Ｎｏのループ）、当該入力を受け付けると（ステップＳ８０１：Ｙｅｓ）、図５に示したテーブル５００から、探索条件に対応した経由エリアの列を抽出する（ステップＳ８０２）。なお、たとえば、出発地点を東京駅とし、目的地点を大阪駅とすると、ステップＳ８０２においては、東京駅が属する東京エリアと、大阪駅が属する大阪エリアとの間の経由エリアの列（たとえば、図５の符号５１０に示した東海地方経由のエリアの列）を抽出する。【００７８】
このあと、経路計算をおこなうリンクのエリア番号から、次の経由エリアを特定する（ステップＳ８０３）。具体的には、たとえば、出発地点のエリア番号（１：東京エリア）から、次の経由エリア（２：神奈川エリア）を特定する。そして、経由エリアの列ごとに探索条件に応じてリンクに設定されるフラグを参照する（ステップＳ８０４）。具体的には、東京エリアから神奈川エリアまでのリンクに設定されるフラグを参照する。【００７９】
そして、リンクの絞り込みをおこなう（ステップＳ８０５）。すなわち、エリア内の複数のリンクのうち、最適なリンクを選択する。このあと、リンクを接続していき、目的地点に繋がったか否かを判断する（ステップＳ８０６）。目的地点に繋がっていないと判断した場合（ステップＳ８０６：Ｎｏ）、リージョン境界を越えたか否かを判断する（ステップＳ８０７）。リージョン境界を越えていないと判断した場合（ステップＳ８０７：Ｎｏ）、ステップＳ８０４に移行し、引き続き、リンクに設定されるフラグを参照し、リンクの絞り込みをおこなう。【００８０】
リージョン境界を越えたと判断した場合（ステップＳ８０７：Ｙｅｓ）、ステップＳ８０３に移行し、次の経由エリアの特定をおこなう。すなわち、東京を越え、神奈川のエリア内の経路計算をおこなう場合、次の経由エリアである静岡エリアの特定をおこなう。【００８１】
一方、ステップＳ８０６において、目的地点に繋がったと判断した場合（ステップＳ８０６：Ｙｅｓ）、ディスプレイ３１２などから探索した経路の情報を出力し（ステップＳ８０８）、一連の処理を終了する。【００８２】
なお、複数の経路を出力する場合、再度、ステップＳ８０１に移行し、経路探索処理を実行すればよい。この場合、既に出力した経路をなるべく通らないようにした経路を探索すればよく、たとえば、東京エリアと大阪エリアとの間の経路探索においては、最初の経路として東海地方を経由する経路を探索した場合、次の経路として甲信越地方を経由する経路を探索すればよい。すなわち、具体的には、図５の符号５１１に示した甲信越地方経由のエリアの列を抽出して、経路を探索すればよい。また、予め探索条件の入力がない場合には、次に探索する経路を、前に探索した経路と探索条件を異ならせて、経路探索をおこなってもよい。【００８３】
また、上述した処理では、出発地点側から目的地点側への経路探索として説明したが、目的地点側から出発地点側への経路探索とした場合も、同様の処理にて経路探索をおこなうことができる。また、出発地点側から目的地点側への経路探索と同時に、目的地点側から出発地点側への経路探索をおこなうことも可能である。このように、出発地点側からと目的地点側の双方から経路探索をおこなう場合、ある地点で双方からの経路が繋がった場合に経路探索が終了となる。なお、複数の経路を出力する場合、出発地点側および目的地点側の双方から同時に経路計算をおこない、経路が繋がった後に、再度双方から経路計算をおこなえばよい。【００８４】
図８に示した処理によれば、出発地点が属するエリアから目的地点が属するエリアまでの間に経由する経由エリアの列をテーブル５００から抽出し、経由エリアのエリア内経路データを用いて、出発地点から目的地点までの経路を探索するようにしたので、迅速な経路探索処理を可能としながら、遠距離用経路計算データのデータ容量を削減することができる。特に、従来では、出発エリア／目的エリアの組合せ数分のデータが必要であったが、本実施例では、エリア内経路はそのエリアに隣接するエリアの組合せ数のみのデータ量で済むため、データ量を大幅に削減することができる。【００８５】
また、テーブル５００を、出発エリアおよび目的エリアの一の組合せに対して複数の経由エリアの列を対応付けたものとし、当該テーブル５００から一の経由エリアの列を抽出するようにしたので、遠距離用経路計算データのデータ容量を削減しながら、複数の経路の中から最適な経路を提示することができる。【００８６】
また、探索条件ごとのテーブル５００を記録しておき、利用者から受け付けた探索条件に対応した経由エリアの列をテーブル５００から抽出し、探索条件を充足する出発地点から目的地点までの経路を探索するようにしたので、遠距離用経路計算データのデータ容量を削減しながら、利用者の所望する探索条件に応じた最適な経路を提示することができる。【００８７】
（ナビゲーション装置がおこなうデータ更新処理の一例）
つぎに、図９を用いて、ナビゲーション装置３００がおこなうデータ更新処理の一例について説明する。図９は、ナビゲーション装置３００がおこなうデータ更新処理を示すフローチャートである。【００８８】
図９において、ナビゲーション装置３００のＣＰＵ３０１は、経路計算データの更新情報を取得したか否かを判断する（ステップＳ９０１）。なお、更新情報を取得したか否かの判断は、具体的には、たとえば、通信Ｉ／Ｆ３１３が外部のサーバから更新情報を受信したか否かの判断である。【００８９】
ステップＳ９０１において、更新情報を取得するまで待機状態にあり（ステップＳ９０１：Ｎｏのループ）、更新情報を取得すると（ステップＳ９０１：Ｙｅｓ）、更新情報にテーブル５００の更新情報が含まれるか否かを判断する（ステップＳ９０２）。テーブル５００の更新情報が含まれると判断した場合（ステップＳ９０２：Ｙｅｓ）、テーブル５００を更新する（ステップＳ９０３）。すなわち、テーブル５００のテキストデータを書き換える。なお、この場合、出発エリアおよび目的エリアの組合せごとにテーブル５００を更新してもよい。【００９０】
このあと、更新情報にエリア内経路データの更新情報が含まれるか否かを判断する（ステップＳ９０４）。エリア内経路データの更新情報が含まれると判断した場合（ステップＳ９０４：Ｙｅｓ）、エリアごとにエリア内経路データを更新する（ステップＳ９０５）。すなわち、エリア単位でエリア内経路データを差し替える。このあと、更新したデータを保存し（ステップＳ９０６）、一連の処理を終了する。【００９１】
一方、ステップＳ９０２において、テーブル５００の更新情報が含まれないと判断した場合（ステップＳ９０２：Ｎｏ）、更新情報をエリア内経路データの更新情報と判定し（ステップＳ９０７）、ステップＳ９０５における更新処理をおこなう。また、ステップＳ９０４において、エリア内経路データの更新情報が含まれないと判断した場合（ステップＳ９０４：Ｎｏ）、ステップＳ９０６におけるデータの保存をおこなう。【００９２】
上述した処理によれば、テーブル５００の更新情報に基づいて、テーブル５００を更新するようにしたので、従来のように、たとえば、関東から北関東を跨ぐ主要道路が１本追加されただけで、組合せデータ１０００（図１０参照）のうち、半分以上のリンクデータを更新しなければならないといった不具合を防止することができる。また、テーブル５００のテキストデータのみを書き換えることが可能となり、更新するデータ量を削減することができ、更新に要するコストを抑えることができる。【００９３】
また、エリア内経路データ１１２の更新情報に基づいて、エリア内経路データ１１２をエリアごとに更新するようにしたので、更新するデータ量を削減することができる。このように、エリア単位で更新することができるので、更新に要するコストを抑えることができる。【００９４】
以上のように、本発明の経路探索装置、経路探索方法、経路探索プログラム、および記録媒体によれば、迅速な経路探索処理を可能としながら、遠距離用経路計算データのデータ容量を削減することができる。【００９５】
なお、本実施例で説明した経路探索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【図１】
2010013327.tif 000003
【図２】
2010013327.tif 000004
【図３】
2010013327.tif 000005
【図４】
2010013327.tif 000006
【図５】
2010013327.tif 000007
【図６】
2010013327.tif 000008
【図７】
2010013327.tif 000009
【図８】
2010013327.tif 000010
【図９】
2010013327.tif 000011
【図１０】
2010013327.tif 000012
【図１１】
2010013327.tif 000013
【手続補正書】
【提出日】平成23年1月12日(2011.1.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録手段と、
出発地点および目的地点の入力を受け付ける入力手段と、
前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出手段と、
前記出発エリア、前記目的エリア、前記経由エリア内における前記エリア内経路データを前記経由エリアの列の順序に繋いで、前記出発地点から前記目的地点までの経路を探索する探索手段と、
を備えることを特徴とする経路探索装置。
【請求項２】
前記テーブルは、出発エリアおよび目的エリアの一の組合せに対して複数の経由エリアの列が対応付けられており、
前記抽出手段は、前記出発地点が属するエリアおよび前記目的地点が属するエリアに基づいて、一の経由エリアの列を抽出することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記記録手段は、探索条件ごとの前記テーブルを記録し、
前記入力手段は、前記出発地点および前記目的地点とともに探索条件の入力を受け付け、
前記抽出手段は、前記入力手段が受け付けた前記探索条件に対応した前記経由エリアの列を前記テーブルから抽出し、
前記探索手段は、前記経由エリアのエリア内経路データを用いて、前記探索条件を充足する前記出発地点から前記目的地点までの経路を探索することを特徴とする請求項１または２に記載の経路探索装置。
【請求項４】
前記テーブルの更新情報を取得する取得手段と、
前記更新情報に基づいて、前記記録手段に記録されている前記テーブルを更新する更新手段と、
を備えることを特徴とする請求項１〜３のいずれか一つに記載の経路探索装置。
【請求項５】
前記エリア内経路データの更新情報を取得する取得手段と、
前記更新情報に基づいて、前記記録手段に記録されている前記エリア内経路データをエリアごとに更新する更新手段と、
を備えることを特徴とする請求項１〜４のいずれか一つに記載の経路探索装置。
【請求項６】
出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録部を備えた経路探索装置の経路探索方法であって、
出発地点および目的地点の入力を受け付ける入力工程と、
前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出工程と、
前記出発エリア、前記目的エリア、前記経由エリア内における前記エリア内経路データを前記経由エリアの列の順序に繋いで、前記出発地点から前記目的地点までの経路を探索する探索工程と、
を含むことを特徴とする経路探索方法。
【請求項７】
請求項６に記載の経路探索方法をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項８】
請求項７に記載の経路探索プログラムを記録したことを特徴とするコンピュータに読み取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
上述した課題を解決し、目的を達成するため、請求項１の発明にかかる経路探索装置は、出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録手段と、出発地点および目的地点の入力を受け付ける入力手段と、前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出手段と、前記出発エリア、前記目的エリア、前記経由エリア内における前記エリア内経路データを前記経由エリアの列の順序に繋いで、前記出発地点から前記目的地点までの経路を探索する探索手段と、を備えることを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
また、請求項６に記載の経路探索方法は、出発エリアおよび目的エリアの組合せと当該組合せごとにそれぞれ出発エリアから目的エリアまでの間に経由する経由エリアの列とが対応付けられたテーブルおよび各エリア内にて当該エリアの境界に位置する境界ノード同士を結んだエリア内経路データを記録する記録部を備えた経路探索装置の経路探索方法であって、出発地点および目的地点の入力を受け付ける入力工程と、前記出発地点が属するエリアおよび前記目的地点が属するエリアの組合せに基づき、当該出発地点が属するエリアから当該目的地点が属するエリアまでの間に経由する経由エリアの列を前記テーブルから抽出する抽出工程と、前記出発エリア、前記目的エリア、前記経由エリア内における前記エリア内経路データを前記経由エリアの列の順序に繋いで、前記出発地点から前記目的地点までの経路を探索する探索工程と、を含むことを特徴とする。
【国際調査報告】
2010013327.tif 000014
2010013327.tif 000015
2010013327.tif 000016
2010013327.tif 000017