(57)【要約】  本発明は、上位階層道路ネットワークを用いた経路探索においてリンク内の勾配などエネルギコストに影響を与える要因を考慮した探索を可能とし、始終点間が遠距離であってもエネルギコストが最小の経路の探索を高速に行うことが可能な経路探索装置を提供することを目的としている。そのために、一の遠距離探索用リンクに対応する複数の近距離探索用リンクについて、各近距離探索用リンクの登り標高差の和と、各近距離探索用リンクの降り標高差の和とを一の遠距離探索用リンクの属性として算出して、当該遠距離探索用リンクの属性と車両特性とから車両走行時のエネルギ消費量であるリンクコストを算出するようにしている。
2011111145.tif 000002
【特許請求の範囲】
【請求項１】
始点と終点とを結ぶ経路を探索する経路探索装置であって、  近距離探索に用いられる近距離探索用リンクを含む近距離探索用道路データと、遠距離探索に用いられる遠距離探索用リンクを含む遠距離探索用道路データとを有する地図データ部と、  一の前記遠距離探索用リンクに対応する複数の前記近距離探索用リンクについて、各前記近距離探索用リンクの登り標高差の和と、各前記近距離探索用リンクの降り標高差の和とを前記一の遠距離探索用リンクの属性として算出する遠距離探索用属性算出部と、  前記遠距離探索用リンクの前記属性と車両特性とに基づいて、前記遠距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストを算出するリンクコスト算出部と、  前記リンクコストに基づいて、エネルギ消費量が最小の経路を求める処理、または、所定の経路におけるエネルギ消費量を算出する処理を行う経路探索処理部と、を備える、経路探索装置。
【請求項２】
前記遠距離探索用属性算出部にて算出された前記遠距離探索用リンクの前記属性は、前記遠距離探索用道路データに保持されることを特徴とする、請求項１に記載の経路探索装置。
【請求項３】
前記所定の経路は、前記経路の走行距離が最短の経路、または前記経路の走行時間が最短の経路のうちのいずれかであることを特徴とする、請求項１または２に記載の経路探索装置。
【請求項４】
前記リンクコスト算出部は、走行に必要な消費量以外の基本消費量、路面摩擦に起因する消費量、位置エネルギに起因する消費量、空気抵抗に起因する消費量、または加減速に起因する消費量を前記リンクコストとして算出することを特徴とする、請求項１ないし３のいずれかに記載の経路探索装置。
【請求項５】
前記リンクコスト算出部は、二酸化炭素排出量、燃料消費量、または電力消費量を前記リンクコストとして算出することを特徴とする、請求項１ないし３のいずれかに記載の経路探索装置。
【請求項６】
前記リンクコスト算出部は、前記近距離探索用リンクの属性と前記車両特性とに基づいて、前記近距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストをも算出することを特徴とする、請求項１ないし５のいずれかに記載の経路探索装置。
【請求項７】
前記遠距離探索用属性算出部は、一の前記遠距離探索用リンクに対応する複数の前記近距離探索用リンク内における走行時間の和、距離の和、前記登り標高差の和、前記降り標高差の和、および停止回数の和を前記遠距離探索用リンクの属性として算出し、  前記リンクコスト算出部は、前記経路探索処理部からの要求に応じて、前記遠距離探索用リンクの前記属性と前記車両特性とに基づいて前記リンクコストを算出することを特徴とする、請求項１ないし５のいずれかに記載の経路探索装置。
【請求項８】
一の前記遠距離探索用リンクに対応する複数の前記近距離探索用リンクにおける各前記近距離探索用リンク内での停止回数を推定する停止回数推定部をさらに備え、  前記リンクコスト算出部は、前記遠距離探索用リンクの属性である前記停止回数の和に基づいて、前記停止回数の和が最大の場合における前記リンクコスト、および前記停止回数の和が最小の場合における前記リンクコストを算出し、  前記経路探索処理部は、前記停止回数の和が最大の場合に前記エネルギ消費量が最小となる経路と、前記停止回数の和が最小の場合に前記エネルギ消費量が最小となる経路とを算出することを特徴とする、請求項１ないし５のいずれかに記載の経路探索装置。
【請求項９】
前記リンクコスト算出部は、前記経路探索処理部にて算出された前記停止回数の和が最大の場合に前記エネルギ消費量が最小の経路に対して前記停止回数の和が最小の場合における前記リンクコスト、および前記停止回数の和が最小の場合に前記エネルギ消費量が最小の経路に対して前記停止回数の和が最大の場合における前記リンクコストを算出することを特徴とする、請求項８に記載の経路探索装置。
【請求項１０】
前記エネルギ消費量が最小の経路に替えて、前記経路の走行距離が最短の経路または前記経路の走行時間が最短の経路であることを特徴とする、請求項８または９に記載の経路探索装置。
【請求項１１】
前記経路探索処理部は、前記エネルギ消費量が最小の経路、前記経路の走行距離が最短の経路、および前記経路の走行時間が最短の経路を含む複数の経路の各々に対する前記エネルギ消費量を算出し、各経路における前記エネルギ消費量の比較を提示することを特徴とする、請求項３または１０に記載の経路探索装置。
【請求項１２】
前記遠距離探索用属性算出部は、地図作成システムまたはカーナビゲーションシステムに備えられることを特徴とする、請求項１ないし１１のいずれかに記載の経路探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、経路探索装置に関し、特に、カーナビゲーションシステムなどに用いられる始点（例えば、出発地）から終点（例えば、目的地）までのエネルギコスト（二酸化炭素排出量、燃料消費量、電力消費量など）が最小となる経路を探索する経路探索装置に関する。
【背景技術】
【０００２】  従来における二酸化炭素排出量が最小となる経路を探索する経路探索装置では、記憶媒体に記憶された各区間（以下、リンクとする）の両端の高低差に基づいて各区間の道路勾配状況に応じた係数を算出し、当該係数を区間毎の距離に乗算して区間毎の距離に応じて変化する二酸化炭素排出量を特定するとともに、区間毎の走行時間に応じて変化する二酸化炭素排出量および区間毎の停止回数に応じて変化する指標に基づく二酸化炭素排出量を個別に特定し、特定した各二酸化炭素排出量を合計して区間毎の二酸化炭素排出量を算出することを特徴とする経路探索装置がある（例えば、特許文献１参照）。【０００３】  特許文献１の経路探索装置では、各リンクの始点と終点との高低差を用いてリンクの高低差を求めるとともに（段落［００５２］参照）、「ｓｉｎθ＝（リンク両端の）高低差／（リンクの）距離」の関係を用いてリンクの勾配（θ：水平面とリンクとがなす角度）を表現することによって（段落［００４８］参照）、リンク両端の高低差に起因する位置エネルギに関する燃料消費量を求めている。段落［００４８］では勾配θの説明について記載されているが、最終的にはリンク両端の高低差に起因する位置エネルギ（ｍｇ×（リンク両端の）高低差）によって燃料消費量を算出するため、緩やかな登りなのか急な登りなのかといった勾配の程度による影響は考慮されない。従って、リンク内の勾配が一定の（リンク内の位置によって勾配が変化しない）リンクと、リンクにおける位置エネルギに関する燃料消費量を想定した技術である。【０００４】  一方、カーナビゲーションシステムなどにおける経路探索装置では、情報量の多い（詳細な情報を有する）下位階層道路ネットワークに加えて、情報量の少ない（抽象化された）上位階層道路ネットワークを地図データに保持することによって、出発地から目的地までの距離が長い場合であっても、経路探索に要する計算時間やメモリ容量の増加を抑制する技術が開示されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−７９９９５号公報
【特許文献２】特許第３２２３７８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】  通常、特許文献２に記載されるような上位階層道路ネットワークを利用した経路探索技術では、下位階層道路ネットワークのリンク（以下、近距離探索用リンクとする）を複数集約してなる上位階層道路ネットワークのリンク（以下、遠距離探索用リンクとする）に設定された属性やリンクコストに基づいて、上位階層道路ネットワークにおける経路探索を行う。一般的に、近距離探索用リンクの勾配が一定であったとしても、当該近距離探索用リンクを複数集約した遠距離探索用リンクは登り勾配や降り勾配の区間（登り勾配の近距離探索用リンクや降り勾配の近距離探索用リンク）を有するため、遠距離探索用リンク内の勾配が一定であるとは限らない。例えば、遠距離探索用リンクの両端では高低差が０であるにもかかわらず、当該遠距離探索用リンク内では登り勾配や降り勾配の区間が繰り返して存在する場合がある。【０００７】  しかし、特許文献１に記載の経路探索装置を上記の道路ネットワークを複数階層に分けて経路探索する技術に対して応用すると、リンクの両端の高低差に基づいてリンクコストに相当する二酸化炭素排出量を特定しているため、リンク内の勾配が一定であるとは限らない遠距離探索用リンクに対しては、リンク途中の登り降りが位置エネルギに与える影響を考慮できないため、走行時の位置エネルギの影響を正確に反映したリンクコストを算出することができないという問題がある。例えば、遠距離探索用リンクの両端では高低差が０であるがリンク内で登りや降りの勾配の区間が繰り返して存在する場合は、登りにおける位置エネルギの影響を反映したリンクコストの算出が必要になるが、リンクの両端の高低差のみを考慮すると登りにおける位置エネルギが０と判断されてしまう。【０００８】  また、特許文献１に記載の経路探索装置では、上記の道路ネットワークを複数階層に分けて経路探索する技術に対して応用しない場合は、始点と終点とが遠距離であると経路の探索に時間がかかるという問題があった。【０００９】  本発明は、上記の課題を解決するためになされたものであり、上位階層道路ネットワークを用いた経路探索においてリンク内の勾配などエネルギコストに影響を与える要因を考慮した探索を可能とし、始終点間が遠距離であってもエネルギコストが最小の経路の探索を高速に行うことが可能な経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】  上記の課題を解決するために、本発明による経路探索装置は、始点と終点とを結ぶ経路を探索する経路探索装置であって、近距離探索に用いられる近距離探索用リンクを含む近距離探索用道路データと、遠距離探索に用いられる遠距離探索用リンクを含む遠距離探索用道路データとを有する地図データ部と、一の遠距離探索用リンクに対応する複数の近距離探索用リンクについて、各近距離探索用リンクの登り標高差の和と、各近距離探索用リンクの降り標高差の和とを一の遠距離探索用リンクの属性として算出する遠距離探索用属性算出部と、遠距離探索用リンクの属性と車両特性とに基づいて、遠距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストを算出するリンクコスト算出部と、リンクコストに基づいて、エネルギ消費量が最小の経路を求める処理、または、所定の経路におけるエネルギ消費量を算出する処理を行う経路探索処理部とを備える。
【発明の効果】
【００１１】  本発明によると、一の遠距離探索用リンクに対応する複数の近距離探索用リンクについて、各近距離探索用リンクの登り標高差の和と、各近距離探索用リンクの降り標高差の和とを一の遠距離探索用リンクの属性として算出する遠距離探索用属性算出部と、遠距離探索用リンクの属性と車両特性とに基づいて、遠距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストを算出するリンクコスト算出部と、リンクコストに基づいて、エネルギ消費量が最小の経路を求める処理、または、所定の経路におけるエネルギ消費量を算出する処理を行う経路探索処理部とを備えるため、上位階層道路ネットワークを用いた経路探索においてリンク内の勾配などエネルギコストに影響を与える要因を考慮した探索を可能とし、始終点間が遠距離であってもエネルギコストが最小の経路の探索を高速に行うことが可能となる。【００１２】  この発明の目的、特徴、局面、および利点は、以下の詳細な説明と添付図面とによって、より明白となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態による経路探索装置の構成を示すブロック図である。
【図２】本発明の実施形態による経路探索装置の動作を示すフローチャートである。
【図３】本発明の実施形態による遠距離探索用リンクの距離と標高に関する属性の設定を説明するための概念図である。
【図４】本発明の実施形態による遠距離探索用リンクのリンクコストの算出の一例を示す図である。
【図５】本発明の実施形態による信号での停止回数を考慮した経路探索を説明するための概念図である。
【図６】本発明の実施形態によるエネルギ消費量指標を用いたユーザへのエネルギ削減効果とその変動幅の提示の一例を示した図である。
【発明を実施するための形態】
【００１４】  本発明の実施形態について、図面を用いて以下に説明する。
【００１５】  図１は、本発明の実施形態による経路探索装置１の構成を示すブロック図である。図１に示すように、本実施形態による経路探索装置１は、始点と終点とを結ぶ経路を探索し、遠距離探索用属性算出部２、地図データ３（地図データ部）、経路探索処理部６、リンクコスト算出部７、車両データ８とを備えている。また、地図データ３は、近距離探索に用いられる近距離探索用リンクを含む近距離探索用道路データ５と、遠距離探索に用いられる遠距離探索用リンクを含む遠距離探索用道路データ４とを有している。
【００１６】  前述では説明容易のために近距離探索用リンクにおける勾配が一定である場合を仮定したが、実際には近距離探索用リンクの勾配がリンク内で変化してもよい。すなわち、一本の近距離探索用リンク内に複数の登り区間（勾配が正の道路区間）、複数の降り区間（勾配が負の道路区間）が含まれてもよく、そのような場合と前記勾配が一定である場合とを総合して一般化すれば、近距離探索用リンクの登り標高差の和とは、近距離探索用リンクが対応する道路区間における登り道路区間の標高差の和を表し、近距離探索用リンクの降り標高差の和とは、近距離探索用リンクが対応する道路区間における降り道路区間の標高差の和を表す。勾配が変化する地点でリンクを分割すれば、ここで記載したような（近距離探索用リンクの勾配に関する制約をなくす）一般化は不要である。しかし、勾配の変化点は多数あるがリンク途中で分岐点（他のリンクへの接続点）がない場合などには、リンクを勾配の変化点で逐一分割すると地図データ（道路データ）のサイズが増えてしまうため、この一般化は有用である。
【００１７】  遠距離探索用属性算出部２は、遠距離探索用リンクに対応する複数の近距離探索用リンクの属性を用いて、遠距離探索用リンクを用いた経路探索に必要な遠距離探索用リンクの属性を算出し、地図データ３における遠距離探索用道路データ４に格納する。
【００１８】  なお、遠距離探索用属性算出部２における処理は、カーナビゲーションシステムのハードディスクに格納される地図データ３を作成する工程にて事前に実施してもよく、また、カーナビゲーションシステム内で動的に実施されてもよい。例えば、地図データ３が更新された時に近距離探索用リンクの属性情報のみを通信などによって外部から取得し、取得した近距離探索用リンクの属性情報を用いてカーナビゲーション内の遠距離探索用属性算出部２にて遠距離探索用リンクの属性を算出して更新するなどすれば、更新のために取得するデータ量を削減することができる。なお、上記の例では遠距離探索用属性算出部２をカーナビゲーションシステムに備えることを想定して説明したが、地図生成システムに遠距離探索用属性算出部２を備えても同様の効果を得ることができる。
【００１９】  遠距離探索用道路データ４および近距離探索用道路データ５は、交差点などに相当するノードに関するノードデータと、ノード間の道路区間（リンク）に関するリンクデータとを含んで構成される。道路データは、ノード間の接続情報を保持するように構成され、Ｄｉｊｋｓｔｒａ法などの探索アルゴリズムを用いることによって、指定した２点間のコスト（リンクコスト）を最小にする経路を算出することができる。接続情報としては、例えばノードを一意に特定するノード番号をノードデータに格納し、リンクデータにリンクの始点ノード番号と終点ノード番号とを格納すればよい。以下、各リンクを通過するために必要となるリンクコストに着目した経路探索について説明するが、直進や右左折などでノードにおける通過コストが異なる場合などは、ノードを通過するために必要となるノードコストを設定してもよい。
【００２０】  リンクにおけるリンクコストは、例えば、リンクの長さをリンクコストとすると距離優先の経路探索を行うことができ、リンクを通過するために要する時間をリンクコストとすると時間優先の経路探索を行うことができる。また、リンクを通過するために消費するエネルギ量をリンクコストとするとエネルギコストが最小となる経路探索を行うことができる。
【００２１】  リンクデータは、リンクコストの算出に必要となる、リンク長、道路種別、車線数、走行速度、規制速度、形状、標高差などの属性を保持している。
【００２２】  遠距離探索用道路データ４は、遠距離の探索で用いられない近距離探索用リンクを下位階層道路ネットワークから取り除くことによって（例えば、高速道路などの主要な道路のみを残すなどして）、上位階層道路ネットワークを構成するように別途定義される。さらに、分岐がない（すなわち、つながっているリンクが２本である）ノードを省略することによって、上位階層道路ネットワークにおけるリンク数およびノード数を削減するなどして遠距離探索用リンクが定義される。
【００２３】  なお、上位階層道路ネットワークは、道路の種別などを用いて高速道路などの主要な道路のみを残して構成してもよく、下位階層道路ネットワークにおける様々な始終点間の組み合わせ（例えば、特許第２６５３８４７号公報）や、様々なリンクコストの組み合わせ（時間優先、距離優先、エネルギコスト優先などの検索オプションに依存したリンクコストの組み合わせ）で経路探索することによって必要最小限の道路ネットワークを構成してもよい。また、本実施形態では、下位階層道路ネットワークが１層と上位階層道路ネットワークが１層の計２層の場合について説明するが、上位階層である遠距離探索用リンクが、当該遠距離探索用リンクよりも下位階層である近距離探索用リンクの複数から構成されていれば、道路ネットワークの大きさや求められる処理速度に応じて計３層以上の階層からなる道路ネットワークを用いてもよい。
【００２４】  経路探索処理部６は、経路の探索範囲に含まれる道路データを地図データ３の遠距離探索用道路データ４または近距離探索用道路データ５から読み込み、リンクコスト算出部７にて算出されたリンクコストの和が最小となる経路を求め、モニタ（図示せず）などに出力する。すなわち、経路探索処理部６は、リンクコスト算出部７にて算出されたリンクコストに基づいて、エネルギ消費量が最小の経路を求める処理、または、所定の経路（例えば、走行距離が最短の経路、走行時間が最短の経路）におけるエネルギ消費量を算出する処理を行う。
【００２５】  リンクコスト算出部７は、地図データ３の遠距離探索用道路データ４または近距離探索用道路データ５から取得した属性と、車両データ８から取得した車両特性などを用いてリンクコストを算出し、算出したリンクコストを経路探索処理部６に出力する。
【００２６】  図２は、本発明の実施形態による経路探索装置１の動作を示すフローチャートであり、始点（現在地）から終点（目的地または経由地）までの距離が長く、上位階層道路ネットワークを用いた経路探索時における経路探索処理部６の動作のフローチャートである。
【００２７】  図２に示すように、ステップＳ２０１において、経路探索処理部６では、現在地やユーザによって設定された目的地（経由地）の情報を用いて、経路探索を行う下位階層道路ネットワーク上における始点および終点の２点を決定する。
【００２８】  ステップＳ２０２において、ステップＳ２０１にて決定された始点および終点の各々の近傍における下位階層道路ネットワーク上の必要な道路データを地図データ３の近距離探索用道路データ５から読み込み、経路探索に必要なリンクコストをリンクコスト算出部７から取得しながら始点および終点の各々から経路探索し、上位階層道路ネットワークへ移行することができる地点を決定する（近距離探索）。なお、上位階層道路ネットワークへ移行することができる地点は複数候補あってもよい。
【００２９】  ステップＳ２０３において、ステップＳ２０２の近距離探索にて取得された地点間において、上位階層道路ネットワーク上の必要な道路データを地図データ３の遠距離探索用道路データ４から読み込み、経路探索に必要なリンクコストをリンクコスト算出部７から取得しながら前記地点間の経路を探索し、前記地点間におけるリンクコストの和が最小となる経路を算出する（遠距離探索）。
【００３０】  ステップＳ２０４において、ステップＳ２０２にて行った近距離探索と、ステップＳ２０３にて行った遠距離探索との各々の探索結果を合成し、始点から終点までのリンクコストの和が最小となる経路を決定して出力する。
【００３１】  また、上位階層道路ネットワークにおける探索結果（通過するノード（リンク）の集合）に対応する下位階層道路ネットワークのノード（リンク）のデータに基づいて、下位階層道路ネットワークを用いて交差点などの右左折案内などを上位階層道路ネットワークに対応付けることができる。
【００３２】  図３は、本発明の実施形態による遠距離探索用リンクの距離と標高に関する属性の設定を説明するための概念図である。図３では、４本の近距離探索用リンク（登り区間を持つ２本の近距離探索用リンク３１，３３と、降り区間を持つ２本の近距離探索用リンク３２，３４）を１本の遠距離探索用リンク３５に集約する場合を一例として示している。簡単のために、近距離探索用リンクにおける勾配は一定である場合を示している。
【００３３】  図３に示すように、近距離探索用リンク３１，３３の登り標高差の和（Ｈ１＋Ｈ３）と、近距離探索用リンク３２，３４の降り標高差の和（Ｈ２＋Ｈ４）とを、近距離探索用リンク３１〜３４に対応する遠距離探索用リンク３５の遠距離探索用道路データ４の属性（Ｈ＿ｕｐ，Ｈ＿ｄｏｗｎ）として設定する。すなわち、遠距離探索用属性算出部２は、一の遠距離探索用リンクに対応する複数の近距離探索用リンクについて、各近距離探索用リンクの登り標高差の和と、各近距離探索用リンクの降り標高差の和とを一の遠距離探索用リンクの属性として算出している。また、遠距離探索用属性算出部２は、算出した標高差の和がある閾値以上の場合にのみ標高差の和を算出してもよい。このようにすれば、標高差の和を地図データへ格納する場合に、エネルギ消費量に与える影響が小さい標高差の情報を省略することができ、地図データの容量を削減することができる。
【００３４】  また、近距離探索用リンク３１〜３４の距離の和（Ｄ１＋Ｄ２＋Ｄ３＋Ｄ４）も、遠距離探索用リンク３５の遠距離探索用道路データ４の属性（Ｄ）として設定される。すなわち、遠距離探索用属性算出部２にて算出された遠距離探索用リンクの属性は、遠距離探索用道路データ４に保持される。
【００３５】  なお、遠距離探索用リンク３５における走行時間や停止回数などに関する遠距離探索用道路データ４の属性については、上記と同様に近距離探索用リンク３１〜３４の各リンクにおける走行時間や停止回数などの和を遠距離探索用道路データ４の属性として設定すればよい。すなわち、遠距離探索用属性算出部２は、一の遠距離探索用リンクに対応する複数の近距離探索用リンク内における走行時間の和、距離の和、登り標高差の和、降り標高差の和、および停止回数の和を遠距離探索用リンクの属性として算出し、リンクコスト算出部７は、経路探索処理部６からの要求に応じて、遠距離探索用リンクの属性と車両特性とに基づいてリンクコストを算出する。
【００３６】  また、近距離探索用リンク３１〜３４の各リンクにおけるリンク距離（Ｄ１〜Ｄ４）、標高差（Ｈ１〜Ｈ４）は、近距離探索用リンク３１〜３４の各々の属性として地図データ３の近距離探索用道路データ５に設定されている。
【００３７】  図４は、本発明の実施形態による遠距離探索用リンクのリンクコストの算出の一例を示す図である。図４に示すように、１リンクあたりのエネルギ消費量（リンクコスト）は、アイドリングやエアコン動作などに起因する、走行以外で必要なエネルギに関する基本消費量（Ｃ＿１＊ｑ＿ｂａｓｅ＊Ｔ）と、路面摩擦に起因する消費量（Ｃ＿２＊μＭｇ＊Ｄ）と、位置エネルギに起因する消費量（Ｃ＿３＊Ｍｇ＊Ｈ＿ｕｐ（登り）＋Ｃ＿４＊Ｍｇ＊Ｈ＿ｄｏｗｍ（降り））と、空気抵抗に起因する消費量（Ｃ＿５＊κ＊ｖ3＊Ｔ）と、停止による加減速に起因する消費量（Ｃ＿６＊（Ｍ＋ｍ）／２＊ｖ2＊Ｎ＿ｓｔｏｐ）とに分けて算出される。
【００３８】  上記のように、リンクコスト算出部７では、エネルギ消費量をエネルギの消費要因（走行以外に要するエネルギ、路面摩擦によるエネルギ、位置エネルギ、速度（加減速）エネルギ）に分けて算出するため、遠距離探索用リンクにおける走行時のエネルギ消費量を正確に反映したリンクコストを算出することができる。また、車種（例えば、動力源の特性など）が変わった場合に変更するべき車両に関するパラメータと、車種によって変わらない道路に関するパラメータとを分けてモデル化して算出することによって、エンジン自動車からハイブリッド自動車や電気自動車まで幅広い車種に対して適用することが可能となる。
【００３９】  例えば、エンジン自動車やエンジンを有するハイブリッド自動車では、図４に示す数式のうちの車両の効率に関する係数Ｃ＿１〜Ｃ＿６を、エンジンの回転数や走行速度を考慮して算出してもよい。また、回生機構を有さないエンジン自動車では、降りの位置エネルギに関する車両の効率に関する係数Ｃ＿４を０に近い値とするのに対して、回生機構を有するハイブリッド自動車や電気自動車では、係数Ｃ＿４を大きい値（すなわち、降りの位置エネルギに起因する消費量は負の値となる）として、回生による回収エネルギを考慮してもよい。また、図４に示す消費要因の他に、例えば降りや減速時における回生による回収エネルギの項を加えて算出してもよい。
【００４０】  なお、二酸化炭素排出量、燃焼消費量、または電力消費量など、最小化したいエネルギ消費量が異なる場合（すなわち、リンクコスト算出部７にて算出しようとするリンクコストが異なる場合）には、車両の効率に関する係数Ｃ＿１〜Ｃ＿６を最小化したいエネルギ消費量に対応して変更すればよい。
【００４１】  従来（例えば、特許文献１）においても、図４に示すような数式（基本消費量、路面摩擦に起因する消費量、位置エネルギに起因する消費量、停止による加減速に起因する消費量）を用いてエネルギ消費量を算出していたが、本実施形態では図４の位置エネルギに起因する消費量の算出において、登り標高差に起因する消費量と降り標高差に起因する消費量とに分けて算出している点が従来とは異なる（従来（例えば、特許文献１）では、空気抵抗に起因する消費量について記載されていないが、一般的には空気抵抗に起因する消費量の影響があることが知られている（特に、高速走行時））。
【００４２】  上記のように、上位階層道路ネットワークを用いた経路探索において、遠距離探索用リンクの遠距離探索用道路データ４の属性である登り標高差の和および降り標高差の和を用いることによって、累積の標高差のみで決定される位置エネルギに起因するエネルギ消費量を正確に算出することができる。すなわち、登り標高差の和および降り標高差の和を用いることによって、近距離探索用リンクを複数集約した遠距離探索用リンクのリンク両端の高低差のみだけでは考慮することができない、遠距離探索用リンクの途中における登り降りの影響を考慮したエネルギ消費量を算出することが可能となる。
【００４３】  リンクコスト算出部７では、リンクに関する距離、走行速度、標高差、停止回数など道路の属性に関係するパラメータを、地図データ３の遠距離探索用道路データ４または近距離探索用道路データ５から取得し、また、基本消費量、摩擦係数、重量、効率などの車両特性に関係するパラメータを車両データ８から取得している。そして、取得した属性および車両特性に基づいて、図４に示す数式によって１リンクあたりのエネルギ消費量を、経路探索処理部６にて必要となるリンクに対するリンクコストとして算出する。このように、リンクコスト算出部７における処理は、近距離探索用リンクと遠距離探索用リンクとを区別することなく共通の計算式で算出することが可能である。図４に示す数式は、本実施形態では遠距離探索用リンクのリンクコストの算出について説明したが、近距離探索用リンクに対しても適用可能である。すなわち、リンクコスト算出部７は、近距離探索用リンクの属性と車両特性とに基づいて、近距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストをも算出することができる。なお、最も詳細な情報を有する近距離探索用リンクについては、一般的にリンク途中の登り降りは存在せず勾配が一定であると仮定されるため、図４の数式において、登り標高差の和または降り標高差の和のいずれかが有効な値を有することになる。
【００４４】  なお、上記の停止回数は、信号機や停止標識の数などをそのまま設定してもよく、停止確率を考慮した停止回数を設定してもよい。
【００４５】  また、本実施形態では、図４に示すように、信号機などで停止する場合のみを想定した停止による加減速に起因するエネルギ消費量を考慮した場合を一例として示したが、カーブなどでの速度の低下による加減速に起因するエネルギ消費量を別途考慮してもよい。例えば、走行速度の低下分をｖ＿ｄｅｌｔａ、加減速回数をＮ＿ｓｌｏｗとすれば、停止による加減速に起因するエネルギ消費量の算出と同様に、Ｃ＿７＊（Ｍ＋ｍ）／２＊ｖ＿ｄｅｌｔａ2＊Ｎ＿ｓｌｏｗとして算出することができる。
【００４６】  図５は、本発明の実施形態による信号での停止回数を考慮した経路探索を説明するための概念図である。図５では、信号機５１〜５５（または停止標識）の数などを道路データの属性として設定した場合を一例として示している。リンクにおけるエネルギコスト（リンクコスト）は、信号などによる停止によって大きく変動すると考えられており、信号スケジュールが与えられない状況においては、信号によって停止するか否かは確率的事象であり、これらを考慮した探索方法を確立する必要がある。ここでは、以下に示す地点Ａから地点Ｂまでの２つの経路を提示することによって、信号による影響度を的確にユーザに対して提示する例について説明する。  経路１：全ての信号機で停止する場合にエネルギコストが最小となる経路  経路２：全ての信号機で停止せずに通過できる場合にエネルギコストが最小となる経路
【００４７】  経路１は、図５の上側の経路を示しており、図４の数式において停止回数を最大（例えば、全ての信号機の数分）として探索した経路である。また、経路２は、図５の下側の経路を示しており、図４の数式において停止回数を最小（例えば、０回）として探索した経路である。このようにして得られた経路１および経路２をユーザに提示する。すなわち、本実施形態による経路探索装置１は、一の遠距離探索用リンクに対応する複数の近距離探索用リンクにおける各近距離探索用リンク内での停止回数を推定する停止回数推定部（図示せず）をさらに備え、リンクコスト算出部７は、遠距離探索用リンクの属性である停止回数の和に基づいて、停止回数の和が最大の場合におけるリンクコスト、および停止回数の和が最小の場合におけるリンクコストを算出し、経路探索処理部６は、停止回数の和が最大の場合にエネルギ消費量が最小となる経路と、停止回数の和が最小の場合にエネルギ消費量が最小となる経路とを算出する。
【００４８】  また、探索の結果得られた経路１および経路２について、経路１に対しては停止回数を最小に設定してエネルギコストを算出し、経路２に対しては停止回数を最大に設定してエネルギコストを算出することによって、各経路にエネルギコストの変動幅を持たせて提示してもよい。すなわち、リンクコスト算出部７は、経路探索処理部６にて算出された停止回数の和が最大の場合にエネルギ消費量が最小の経路に対して停止回数の和が最小の場合におけるリンクコスト、および停止回数の和が最小の場合にエネルギ消費量が最小の経路に対して停止回数の和が最大の場合におけるリンクコストを算出する。
【００４９】  なお、停止する場合のノードコストを進入リンクおよび流出リンクの勾配によって決定してもよく、信号機の赤信号の時間を学習することによって停止する場合のノードコストに反映させるなどしてもよい。また、エネルギ消費量が最小の経路に替えて、走行距離が最短の経路または走行時間が最短の経路について、上記の停止回数を加味したリンクコストを算出してもよい。
【００５０】  また、登り標高差の和および降り標高差の和に加えて、登り標高差の和に対応するリンク距離の和（すなわち、登りリンクの距離の和）、降り標高差の和に対応するリンク距離の和（すなわち、降りリンクの距離の和）を道路データの属性として設定してもよい。このように設定することによって、位置エネルギによる影響に加えて、勾配に応じた車両の効率の違いを考慮したリンクコストを算出することが可能となる。
【００５１】  また、遠距離探索用リンク内の区間（遠距離探索用リンクに対応する近距離探索用リンク）の連続性（すなわち、登り降りの区間が交互に連続するリンク、または、連続する登り区間と連続する降り区間とが各々まとまっているリンク）など、エネルギコストに影響するパラメータ（具体的には、勾配の変化点の数など）を道路データの属性として設定してもよい。
【００５２】  また、本実施形態では、位置エネルギなどの代表的なエネルギ消費量に着目して、近距離探索用リンクの属性である各近距離探索用リンクの登り標高差の和、降り標高差の和などとして（すなわち、近距離探索用リンクの属性を集約して）遠距離探索用リンクの属性として設定した場合について説明したが、より詳細にリンクコストの算出を行う場合には、近距離探索用リンクの属性を集約せずに各近距離探索用リンクの属性をそのまま遠距離探索用リンクの属性として設定してもよい。例えば、遠距離探索用リンクのリンクコストの算出において、ｐ個の近距離探索用リンクの標高差をそれぞれ考慮する場合には、ｐ個の標高差の全てを遠距離探索用リンクの属性として設定してもよい。しかし、各近距離探索用リンクの属性の全てを遠距離探索用リンクの属性として設定するよりも、上記のように近距離探索用リンクの登り標高差の和、降り標高差の和など近距離探索用リンクを集約して遠距離探索用リンクの属性として設定した方が、地図データ３のデータサイズを削減できる（例えば、ｐ個分から２個分へと削減できる）とともに、遠距離探索用リンクの属性を固定数個で地図データ３に格納できるため、可変個数の属性（近距離探索用リンクの個数によって属性の個数が変わる）を地図データ３に格納する場合に比べて、属性の個数を考慮せずにデータを読み込めるため、一般的にデータを取得する際に要する計算量を削減することができる。
【００５３】  また、本実施形態では、遠距離探索用リンクの属性として登り標高差の和、降り標高差の和を設定する例を示したが、「登り標高差の和」、「降り標高差の和」、および「リンクの始終点の標高差」の３つの値には、「登り標高差の和」＋「降り標高差の和」＝「リンクの始終点の標高差」の関係が成り立つため、本実施形態と同様の効果を得るためには、「登り標高差の和」、「降り標高差の和」、および「リンクの始終点の標高差」のうちのいずれか２つの情報を遠距離探索用リンクの属性として設定すればよい。例えば、「登り標高差の和」と「リンク始終点の標高差」との２つの情報を遠距離探索用リンクの属性として設定してもよい。
【００５４】  また、本実施形態では、遠距離探索用リンク内の勾配が一定とは限らない場合を一例として説明したが、例えばリンク内の勾配が一定ではない近距離探索用リンクに対しても、登り標高差の和、降り標高差の和を近距離探索用リンクの属性として設定することによって、リンク途中における勾配の変化点でリンクを分割することなく、リンク数（道路データ量）を抑制しながら走行時の位置エネルギに起因するエネルギ消費量を正確に求めることができる。
【００５５】  また、地図データ３には標高差や停止回数など道路に関するパラメータを格納し、経路探索処理部６にて行われる経路探索処理時に必要となるリンクコストを、リンクコスト算出部７にて適宜に（例えば、オンラインで）算出するようにしたため、リンクコストを算出するアルゴリズムやエネルギコストに影響を与える車両特性などのパラメータを、オフラインの計算結果（地図データ）を変更することなく柔軟に変更することができる。さらに、交通情報などを取得した場合には、リンクにおける走行速度や走行時間などのパラメータを柔軟に変更することができる。例えば、リンク内が渋滞している場合には、走行速度に関するパラメータを低く設定するとともに、走行時間を大きく設定すればよい。
【００５６】  また、例えば、特に降りにおいて回生エネルギを回収することができるハイブリッド自動車や電気自動車の場合は、図４に示すリンクコスト算出の数式において、登り標高差の和と降り標高差の和とを分けることによって、登りと降りとのエネルギ効率の違いを車両に関するパラメータであるＣ＿３やＣ＿４を車両の特性に応じて設定することによって、より正確なエネルギコストを反映したリンクコストを設定することが可能となる。また、信号などによる停止における減速時の回生やアイドリングストップの影響についても、それぞれ走行時間に関するＴやＣ＿６などのパラメータを車両の特性に応じて設定することによって、より正確なエネルギコストを反映したリンクコストを設定することが可能となる。例えば、加速によって生じた速度エネルギの３０％が回収可能な車両の場合は、Ｃ＿６の値を３０％小さい値に設定するなどすればよい。
【００５７】  また、道路に固有な物理パラメータ（距離、走行時間、標高差、停止回数）と、車両特性に固有な物理パラメータ（車両重量、エネルギ効率）とを分けて用いる（格納する）ことによって、これらを道路データの属性としてまとめて地図データ３に格納する場合と比較して、変更があった道路に関する物理パラメータのみを更新すればよいので、地図更新時のデータ更新量を削減することが可能となる。
【００５８】  また、上位階層道路ネットワークは、「遠距離探索用リンクのリンクコストは、必ず対応する近距離探索用リンクのリンクコストの和に等しいこと」という一般的な条件を満足する必要がある。この条件は、上位階層道路ネットワークを用いた探索結果と下位階層道路ネットワークを用いた探索結果とが同じになることを保証するために必要な条件である。もしも上位階層道路ネットワークにおける経路探索結果が下位階層道路ネットワークにおける経路探索結果と異なれば、上位階層道路ネットワークを用いた検索結果の最適性が保証できなくなってしまう。本実施形態では、近距離探索用リンクの登り標高差の和および降り標高差の和を遠距離探索用リンクの標高差に関する属性として設定し、また近距離探索用リンクの標高差とは異なる他の属性値の和を用いて遠距離探索用リンクの属性として設定し、経路探索処理時に近距離探索用リンクと遠距離探索用リンクとの両方において共通の数式（例えば、図４に示す数式）を用いてリンクコストを算出するようにしたため、上記の条件を満たすことができる。
【００５９】  上記条件について、図４に示す１リンクあたりのエネルギ消費量をリンクコストとする場合を一例として説明する。ｎ本の近距離探索用リンクを集約してなる遠距離探索用リンクに関するリンクコストは、以下の式（１）のように示される。ただし、Ｔ＿ｉ、Ｄ＿ｉ、Ｈ＿ｕｐ＿ｉ、Ｈ＿ｄｏｗｎ＿ｉ、Ｎ＿ｓｔｏｐ＿ｉの各々は、ｉ番目の近距離探索用リンクにおける走行時間、リンク距離、登り標高差の和、降り標高差の和、停止回数とする。
【００６０】
【数１】
2011111145.tif 000003
【００６１】  式（１）において、添え字ｉを付した変数以外の変数（例えば、走行速度ｖなど）を定数と仮定すると、以下の式（２）のように示すことができる。
【００６２】
【数２】
2011111145.tif 000004
【００６３】  式（２）において、Ｔ＿ｉ、Ｄ＿ｉ、Ｈ＿ｕｐ＿ｉ、Ｈ＿ｄｏｗｎ＿ｉ、Ｎ＿ｓｔｏｐ＿ｉの各々の和は、遠距離探索用リンクの属性として設定される値である。従って、遠距離探索用リンクの属性として設定される近距離探索用リンクの走行時間、リンク距離、登り標高差、降り標高差、停止回数の各々の和を用いて遠距離探索用リンクのリンクコストを算出すれば、遠距離探索用リンクのリンクコストを、当該遠距離探索用リンクに対応する近距離探索用リンクのリンクコストの和に必ず等しくすることができる。
【００６４】  なお、リンクコストを算出するアルゴリズムやエネルギコストに影響を与える車両特性のパラメータの変更に対する柔軟性が重要でない場合には、オフラインでの地図データの作成時に予めリンクコストを算出して道路データの属性として格納しておいてもよい。
【００６５】  また、エネルギコスト（リンクコスト）が最小となる経路探索を行う場合だけでなく、経路探索によって得られた探索結果（通過するノード（リンク）の集合）に対して各経路のエネルギ消費量の算出を行う場合においても、上位階層道路ネットワークの道路データの属性を用いることによって高速に算出することができる。すなわち、上位階層道路ネットワークを用いて経路探索を行った時に、算出された探索結果が上位階層道路ネットワークのノードやリンクを含む場合には、上位階層道路ネットワークの道路データの属性を用いてリンクあたりのエネルギ消費量を求めて全体の経路にわたって加算することによって、下位階層道路ネットワークの道路データのみを用いてリンクコストを算出する場合と比較して算出に必要なリンク数が減少するため（純粋な演算時間だけでなく、地図データへのアクセス回数も減少するため）、各経路のエネルギ消費量の演算を高速に行うことができる。
【００６６】  図６は、本発明の実施形態によるエネルギ消費量指標を用いたユーザへのエネルギ削減効果とその変動幅の提示の一例を示した図である。図６に示すように、時間を優先した場合の経路探索や距離を優先した場合の経路探索によって求められた各経路についてエネルギ消費量をそれぞれ算出することによって、エネルギコストが最小となる経路のエネルギ消費量が他の経路（例えば、図６に示すような、時間を優先した経路や距離を優先した経路）のエネルギ消費量に対してどれほど改善したかというエネルギ消費量の改善率（他の経路探索による経路のエネルギ消費量に対する改善率）を算出することができる。算出した改善率は、例えば、最もエネルギ消費量が多い経路のエネルギ消費量によって規格化されたエネルギ消費量の割合をエネルギ消費量指標として棒グラフなどで分かりやすくユーザに対して提示することによって、ユーザの環境への意識を高め、よりエネルギ消費量の少ない経路を選択させることが可能となる。
【００６７】  例えば、図６では、最もエネルギ消費量が多い経路（時間優先ルート）のエネルギ消費量指標を１００とし、時間優先ルートよりもエネルギ消費量が１０％少ない経路（距離優先ルート）のエネルギ消費量指標を９０とし、時間優先ルートよりもエネルギ消費量が２０％少ない経路（エネルギ優先ルート）のエネルギ消費量指標を８０として、ユーザが視認しやすいように提示する。
【００６８】  また、各経路のエネルギ消費量指標について、前述した信号での停止など不確定な要素による影響を考慮した変動幅を図６のようにグラフ上に示してもよい。このようにすることによって、ユーザは変動幅（リスク）を予め加味した状態で総合的に経路を選択することが可能となる。
【００６９】  以上のことから、上位階層道路ネットワークを用いた経路探索においてリンク内の勾配などエネルギコストに影響を与える要因を考慮した探索を可能とし、始終点間が遠距離であってもエネルギコストが最小の経路の探索を高速に行うことが可能となる。
【００７０】  この発明は詳細に説明されたが、上記した説明は、すべての局面において、例示であって、この発明がそれに限定されるものではない。例示されていない無数の変形例が、この発明の範囲から外れることなく想定され得るものと解される。
【符号の説明】
【００７１】  １  経路探索装置、２  遠距離探索用属性算出部、３  地図データ、４  遠距離探索用道路データ、５  近距離探索用道路データ、６  経路探索処理部、７  リンクコスト算出部、８  車両データ、３１〜３４  近距離探索用リンク、３５  遠距離探索用リンク、５１〜５５  信号機。
【図１】
2011111145.tif 000005
【図２】
2011111145.tif 000006
【図３】
2011111145.tif 000007
【図４】
2011111145.tif 000008
【図５】
2011111145.tif 000009
【図６】
2011111145.tif 000010
【手続補正書】
【提出日】平成24年4月4日(2012.4.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
始点と終点とを結ぶ経路を探索する経路探索装置であって、
近距離探索に用いられる近距離探索用リンクを含む近距離探索用道路データと、遠距離探索に用いられる遠距離探索用リンクを含む遠距離探索用道路データとを有する地図データ部と、
一の前記遠距離探索用リンクに対応する複数の前記近距離探索用リンクについて、各前記近距離探索用リンクの登り標高差の和と、各前記近距離探索用リンクの降り標高差の和とを前記一の遠距離探索用リンクの属性として算出する遠距離探索用属性算出部と、
前記遠距離探索用リンクの前記属性と車両特性とに基づいて、前記遠距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストを算出するリンクコスト算出部と、
前記リンクコストに基づいて、エネルギ消費量が最小の経路を求める処理、または、所定の経路におけるエネルギ消費量を算出する処理を行う経路探索処理部と、
を備える、経路探索装置。
【請求項２】
前記遠距離探索用属性算出部にて算出された前記遠距離探索用リンクの前記属性は、前記遠距離探索用道路データに保持されることを特徴とする、請求項１に記載の経路探索装置。
【請求項３】
前記所定の経路は、前記経路の走行距離が最短の経路、または前記経路の走行時間が最短の経路のうちのいずれかであることを特徴とする、請求項１または２に記載の経路探索装置。
【請求項４】
前記リンクコスト算出部は、走行に必要な消費量以外の基本消費量、路面摩擦に起因する消費量、位置エネルギに起因する消費量、空気抵抗に起因する消費量、または加減速に起因する消費量を前記リンクコストとして算出することを特徴とする、請求項１ないし３のいずれかに記載の経路探索装置。
【請求項５】
前記リンクコスト算出部は、二酸化炭素排出量、燃料消費量、または電力消費量を前記リンクコストとして算出することを特徴とする、請求項１ないし３のいずれかに記載の経路探索装置。
【請求項６】
前記リンクコスト算出部は、前記近距離探索用リンクの属性と前記車両特性とに基づいて、前記近距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストをも算出することを特徴とする、請求項１ないし５のいずれかに記載の経路探索装置。
【請求項７】
前記遠距離探索用属性算出部は、一の前記遠距離探索用リンクに対応する複数の前記近距離探索用リンク内における走行時間の和、距離の和、前記登り標高差の和、前記降り標高差の和、および停止回数の和を前記遠距離探索用リンクの属性として算出し、
前記リンクコスト算出部は、前記経路探索処理部からの要求に応じて、前記遠距離探索用リンクの前記属性と前記車両特性とに基づいて前記リンクコストを算出することを特徴とする、請求項１ないし５のいずれかに記載の経路探索装置。
【請求項８】
一の前記遠距離探索用リンクに対応する複数の前記近距離探索用リンクにおける各前記近距離探索用リンク内での停止回数を推定する停止回数推定部をさらに備え、
前記リンクコスト算出部は、前記遠距離探索用リンクの属性である前記停止回数の和に基づいて、前記停止回数の和が最大の場合における前記リンクコスト、および前記停止回数の和が最小の場合における前記リンクコストを算出し、
前記経路探索処理部は、前記停止回数の和が最大の場合に前記エネルギ消費量が最小となる経路と、前記停止回数の和が最小の場合に前記エネルギ消費量が最小となる経路とを算出することを特徴とする、請求項１ないし５のいずれかに記載の経路探索装置。
【請求項９】
前記リンクコスト算出部は、前記経路探索処理部にて算出された前記停止回数の和が最大の場合に前記エネルギ消費量が最小の経路に対して前記停止回数の和が最小の場合における前記リンクコスト、および前記停止回数の和が最小の場合に前記エネルギ消費量が最小の経路に対して前記停止回数の和が最大の場合における前記リンクコストを算出することを特徴とする、請求項８に記載の経路探索装置。
【請求項１０】
前記エネルギ消費量が最小の経路に替えて、前記経路の走行距離が最短の経路または前記経路の走行時間が最短の経路であることを特徴とする、請求項８または９に記載の経路探索装置。
【請求項１１】
前記経路探索処理部は、前記エネルギ消費量が最小の経路、前記経路の走行距離が最短の経路、および前記経路の走行時間が最短の経路を含む複数の経路の各々に対する前記エネルギ消費量を算出し、各経路における前記エネルギ消費量の比較を提示することを特徴とする、請求項３または１０に記載の経路探索装置。
【請求項１２】
前記遠距離探索用属性算出部は、地図作成システムまたはカーナビゲーションシステムに備えられることを特徴とする、請求項１ないし１１のいずれかに記載の経路探索装置。
【請求項１３】
始点と終点とを結ぶ経路を探索する経路探索装置であって、
近距離探索に用いられる近距離探索用リンクを含む近距離探索用道路データと、遠距離探索に用いられる遠距離探索用リンクを含む遠距離探索用道路データとを有する地図データ部と、
前記遠距離探索用リンクの属性と車両特性とに基づいて、前記遠距離探索用リンクにおける車両走行時のエネルギ消費量であるリンクコストを算出するリンクコスト算出部と、
前記リンクコストに基づいて、エネルギ消費量が最小の経路を求める処理、または、所定の経路におけるエネルギ消費量を算出する処理を行う経路探索処理部と、
を備え、
前記遠距離探索用道路データは、その属性として、前記遠距離探索用リンクに対応する複数の前記近距離探索用リンクについて、各前記近距離探索用リンクの登り標高差の和と、各前記近距離探索用リンクの降り標高差の和とを保持することを特徴とする、経路探索装置。
【国際調査報告】
2011111145.tif 000011
2011111145.tif 000012
2011111145.tif 000013
2011111145.tif 000014