経路探索方法および装置
【課題】走行環境の評価を反映して、スムーズに走ることのできる経路を提供する。
【解決手段】経路探索システムは、経路の快適性を表す指標として、期待する走行時間からの遅れ時間を用い、ユーザが回避を望む状況として設定した、交通状況や歩行者などの要因を選択するユーザ入力受付部と、選択された要因による遅れがなるべく小さくなるように、地図情報，交通情報，走行環境に応じて期待する到着予想時刻からの遅れ時間を算出し、その遅れ時間を元にコストを算出する遅れ時間算出部と、遅れ時間から経路探索に用いるリンクのコストを算出し、算出されたコストを用いて経路探索を行う経路探索部と、を備える。
【解決手段】経路探索システムは、経路の快適性を表す指標として、期待する走行時間からの遅れ時間を用い、ユーザが回避を望む状況として設定した、交通状況や歩行者などの要因を選択するユーザ入力受付部と、選択された要因による遅れがなるべく小さくなるように、地図情報，交通情報，走行環境に応じて期待する到着予想時刻からの遅れ時間を算出し、その遅れ時間を元にコストを算出する遅れ時間算出部と、遅れ時間から経路探索に用いるリンクのコストを算出し、算出されたコストを用いて経路探索を行う経路探索部と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステムに関わり、特に経路探索を行うシステムに関わる。
【背景技術】
【０００２】
近年、ナビゲーションシステムを用いて現在地から目的地までの経路を誘導する際、時間優先，距離優先，一般道優先などの条件をユーザが選択することにより、ユーザにとって最適な経路を探索し、誘導・案内する技術が普及している。ユーザが時間優先経路を選択した場合、カーナビゲーション装置は現況交通情報および統計交通情報を用いて目的地までの所要時間が最短となる経路を探索する。さらに、ユーザの幅広いニーズに応えるため、上記の時間優先，距離優先，一般道優先以外に、快適性，安全性などの条件についても最適な経路を探索し、誘導・案内する技術が開発されている。
【０００３】
例えば、特許文献１に示されるように、任意の目的条件を選択することで、２地点間を結ぶ複数経路を目的条件に対応する重みデータで評価し、最も目的条件に適合した経路を提供する技術が存在する。目的条件に対応する重みデータの評価は、ノードの判断項目（信号の有無，道路交差数，見通し度，年間事故件数）およびリンクの判断項目（一方通行の有無，高速・一般道の区別，渋滞度，信号数，最大カーブ曲率，道幅，年間事故件数，最大勾配，平均勾配，路面の凹凸レベル）の内のいずれかに対して、目的条件毎に定められて重みテーブルデータベースに格納された重みテーブルにより重み付けして行う。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−７７２９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の方法により、様々な目的条件に適合した経路を探索し、ユーザに提供することができる。しかしながら、特許文献１には、実際の道路状況および交通状況と快適性の関係を反映した重みテーブルの設定法については考慮されていない。即ち、評価の項目と快適性の関わりについて考慮されていないため、評価により設定した重みに基づいて経路を計算しても、その結果が必ずしも快適な経路になるとは限らない。例えば、渋滞度と信号の有無の重みについて、どの程度の大小関係をもった重みを設定すれば、最もユーザにとって快適な経路を探索できるかは、一般に明らかではない。
【０００６】
また、実際の走行においては、都市部，郊外などの地域の違い、あるいは昼夜や平日／休日などの時間帯の違いにより項目間の重みの大小関係が異なる可能性がある。例えば、信号の数が同じであっても、交通量の多い国道を走行する場合と交通量の少ない脇道を走行する場合とでは、ユーザが運転の際に感じる快適性の度合いが異なる。
【０００７】
以上で述べたように、ユーザにとって快適な経路を提供するためには、地域・時間帯などのさまざまな状況を反映して快適性を表す指標を算出することが重要であり、特許文献１に記載の方法では十分にその目的を果たすことができない。快適な経路を提供するには、快適な経路とは何かということ、および走行環境の評価の項目と快適性との関係について指標を定義し、経路を計算する必要がある。
【０００８】
本発明の目的は、このような課題を解決し、快適性を表す指標を用いた経路探索により、ユーザがより快適に走行できる経路を提供することである。
【課題を解決するための手段】
【０００９】
この課題を解決するため、本発明における経路探索方法は、経路の快適性を表す指標として、期待する走行時間からの遅れ時間を用い、ユーザが回避を望む状況として設定した地点に関して、交通状況や歩行者などの要因から受ける遅れがなるべく小さくなるようにしてスムーズに走行できる経路をユーザに提供する。そのため、ユーザが回避を望む地点に関して地図情報，交通情報，走行環境に応じて期待する到着予想時刻からの遅れ時間を算出し、その遅れ時間から経路探索に用いるリンク毎の重みパラメータ（以下、コストと記載）を算出し、このコストを用いて出発地から目的地までのコスト最小経路を計算するステップを実行することを特徴とする。
【発明の効果】
【００１０】
ユーザが回避を望む１つ以上の状況毎に、その状況に遭遇した場合に発生するユーザの期待からの遅れ時間を算出して経路探索に用いるコストに反映させることにより、遅れ時間を考慮した経路の探索を行うことができ、ユーザが望むスムーズに走ることのできる経路を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】本願発明に関わる経路探索システムの構成図である。
【図２】本願発明に関わる経路探索システムの処理を示すフローチャートである。
【図３】地図情報，交通情報，走行環境情報のデータ構成を示す図である。
【図４】経路探索時に作成されるヒープデータの一例を示す図である。
【図５】コスト算出処理を示すフローチャートである。
【図６】道路種別による信号における停止確率を示す図である。
【図７】本願発明に関わる経路探索システムの他の構成図である。
【図８】本願発明に関わる経路探索システムの処理を示す他のフローチャートである。
【図９】センタ装置におけるコスト更新処理を示すフローチャートである。
【図１０】コストデータベースに蓄積されるコスト情報のデータ構成を示す図である。
【図１１】経路探索条件入力画面の一例を示す図である。
【図１２】探索結果表示画面の一例を示す図である。
【発明を実施するための形態】
【００１２】
本発明の実施形態について、図面を参照して説明する。
【実施例１】
【００１３】
図１は、本発明の一実施形態が適用された経路探索方法を実現するナビゲーション装置の構成図である。本発明は、交通状況や歩行者などから受ける影響がなるべく小さくなるようにした、スムーズに走行することのできる経路を快適ルートとして探索するため、走行時の遅れ時間の大きさが運転者の感じる不快度の大きさに大きな影響を与えるものとして、この遅れ時間を快適性の指標にした経路探索を行う。図１に示すように、本実施形態におけるナビゲーション装置は、記憶装置１１と、位置情報取得部１２と、入出力インターフェース部１３と、探索条件設定部１４と、経路探索部１５と、遅れ時間算出部１６と、表示部１７とを含んで構成される。
【００１４】
記憶装置１１は、図１に示すように、地図情報データベース１１１と、交通情報データベース１１２と、走行環境情報データベース１１３とを内部に備える。地図情報データベースに蓄積される地図情報の構成例として、図３（ａ）にはリンク情報、図３（ｂ）には施設情報を示す。また、図３（ｃ）に交通情報データベースに蓄積される交通情報の構成例を、図３（ｄ）に走行環境情報データベースに蓄積される走行環境情報の構成例を示す。これらのリンク情報，交通情報，走行環境情報は、メッシュＩＤで識別されるメッシュおよびリンクＩＤで識別されるリンクと関係付けて記憶される。ここで、メッシュとは、緯度経度に基づいて設定された矩形領域（例えば、緯度差４０分，経度差１度の領域）を表す。この時、メッシュの大きさは、ユーザの求める渋滞範囲の分解能，道路の構成などによって、適宜設定して良い。また、リンクは、道路を構成する部分であり、交差点や分岐などに指定されるノード間を結んだベクトルとして表される。この時、同じ道路の上り方向と下り方向とは、それぞれ別のリンクとして管理されるものとする。
【００１５】
リンク情報は、高速道路・一般国道などの分類を示す道路種別、リンクを走行する際の規制速度を示す規制速度、リンクの幅を示す道路幅員、リンクの代表点（例えば、リンクの中間点）の位置座標を示す緯度・経度、過去に該当リンク上で起きた事故数、リンク終端点における信号有無、リンク内の踏切有無、リンクを代表する地点名などの情報を含む。
【００１６】
施設情報は、施設名称と、デパート，学校といった施設種別と、施設の代表点の位置座標を表す緯度・経度などの情報を含む。
【００１７】
交通情報は、１つのリンクに対し、予測対象日の日種（曜日，平日／土曜／休日，五十日，天気等）および一定間隔の時間帯（例えば５分毎）に対応して作成された統計交通情報として、統計速度，統計旅行時間が含まれる。この場合、予測対象日の日種に該当する過去の日が複数日あったとして、それらの同一時間帯に関するリンク旅行速度の平均値や中央値等の統計値が、リンクの統計旅行速度に該当する。統計旅行時間は、上記旅行速度と同様、同一日種かつ同一時間帯のリンク旅行時間の統計値である。これらの他に、路上センサにおいて取得された情報、あるいはプローブカーより送信された情報から求めた現況交通情報を含んでも良い。また、本構成要素として図示しないが、携帯電話や無線通信，放送等を介して外部から交通情報を取得し、これを用いても良い。
【００１８】
走行環境情報は、該当リンクを通過する際の平均的な信号停止時間，天気情報センタなどから入手した走行予定時の天候，気温，風速などの気象情報、および路面温度や平均的に遭遇する歩行者数などの情報を含む。
【００１９】
位置情報取得部１２は、出発地の位置を算出し、また、現在時刻を取得する。この時、例えば、図中に表示しない車速センサ，ジャイロセンサ，ＧＰＳ受信装置などのうち少なくとも一つから取得した情報に基づき、位置の算出を行う。車速センサは、車輪の円周と計測される車輪の回転数の積から走行距離を測定し、さらに対となる車輪の回転数の差から曲がった角度を計測する。ジャイロセンサは、光ファイバファイロや振動ジャイロ等で構成され、センサが取り付けられた車両の回転した角度を検出する。ＧＰＳ受信装置は、ＧＰＳ衛星からの信号を受信し、装置とＧＰＳ衛星間の距離と距離の変化率を３基以上の衛星との間で測定する。
【００２０】
入出力インターフェース部１３は、出発地，目的地および、経路探索条件に関する情報を経路探索部に送る。出発地情報は、位置情報取得部により算出された、本システムが搭載された端末が存在する場所として計算される。目的地情報は、表示部に表示された地図上の地点をユーザが画面上の位置で選択する、あるいは緯度経度により指定する等の方法で設定される。この時、出発地情報を目的地情報の指定と同様の方法によりユーザが指定しても良い。
【００２１】
経路探索条件は、表示部の画面上に表示された選択肢から、ユーザが望む経路の条件を少なくとも一つ選択する形式で指定される。図１１（ａ）に、経路探索条件設定画面の一例を示す。ユーザは画面上に表示された、時間優先ルート，距離優先ルート，省燃費ルート，快適ルートなどの選択肢から一つを選ぶことで、自分の望む探索条件を指定する。
【００２２】
さらに、入出力インターフェース部１３は、経路探索部において算出された経路の情報を表示部に送る。
【００２３】
探索条件設定部１４は、入出力インターフェース部１３を介して送信された探索条件，目的地の情報や、位置取得部から送信された出発地情報を経路探索部に送信する。
【００２４】
経路探索部１５は、ユーザが経路探索条件として快適ルートを選択した場合に、この快適ルートをできるだけスムーズな走行が可能となる経路と定義し、（１）ユーザがスムーズな運転でないと感じるのは、走行中に累積されてゆく不快度が大きいため、であり（２）不快度の大小は、期待される理想的な走行からの遅れ時間により左右される、という２つの仮定から、この遅れ時間の累積をスムーズな運転の指標として求め、快適ルートを遅れ時間最小ルートとして求める。そして、この期待される理想的な走行からの遅れ時間を求めるため、運転者が期待する理想的な走行を実現するために回避を望む状況として選択された事象による遅れ時間を評価し、選択されない事象による遅れ時間は、運転者が気にしない、即ち運転の快・不快に寄与しないものとして遅れ時間の評価には含めないものとする。そこで、探索対象となるリンクのリンク情報およびユーザが走行時に回避することを望む項目の情報を遅れ時間算出部１６に送り、コスト情報を要求する、そして、遅れ時間算出部１６で算出された当該リンクのコストを用いて探索を行う。経路探索アルゴリズムは一般的に、ダイクストラ法などが用いられ、出発地から目的地までの最小コストの経路を算出する。
【００２５】
遅れ時間算出部１６は、記憶装置１１に記憶された道路情報，交通情報，走行環境情報を用いて、経路探索部１５から要求されたリンクのコストを算出する。
【００２６】
表示部１７は、探索条件設定時に探索条件の選択肢を表示し、ユーザが探索条件を選択できるようにする。また、地図情報を用い、指定された縮尺，描画方式（平面図，鳥瞰図など）で、道路、その他の地図構成物や、出発地を示すマーク，経路探索により算出された経路を描画する。
【００２７】
以上の構成により、出発地から目的地に向かう経路の中で最もスムーズに走行することのできる快適ルートを探索することができる。
【００２８】
次に、本実施形態におけるナビゲーション装置の快適ルート探索処理を、図２に示すフローチャートを用いて説明する。ナビゲーション装置では快適ルート探索処理に先立ち、まず、出発地，目的地、および出発時刻が設定される。この時、出発地および出発時刻は、位置情報取得部１２によって取得された端末の現在位置および現在時刻とする。目的地は、表示部１７に表示された地図上の位置、あるいは緯度経度の入力などの方法により、入出力インターフェース部１３を介してユーザが指定する。なお、出発地を目的地の指定と同様の方法で指定しても良い。また、出発時刻をユーザの入力により指定しても良い。
【００２９】
次に、ユーザは入出力インターフェース部１３を介して探索条件を入力する。この時ユーザは、図１１（ａ）に示す画面上で自分の望む経路を指定する。ここで、時間優先ルート１１０１は目的地までの総旅行時間が最も短くなる経路、距離優先ルート１１０２は目的地までの総走行距離が最も短いルート、消費燃料優先ルート１１０３は目的地までの消費燃料が最も少ない経路、快適ルート１１０４は目的地までの遅れ時間が最も少ない経路の探索をそれぞれ指示するための項目である。ユーザが図１１（ａ）に示す画面上で快適ルート１１０４を選択すると、快適ルート探索処理が開始される。
【００３０】
快適ルート探索処理ではまず、探索エリアが決定される（Ｓ２０２）。探索エリアは、出発地及び目的地が含まれるメッシュをそれぞれ特定し、２メッシュを結ぶ線分を対角線とする長方形あるいは２メッシュを内包する楕円などの領域として設定される。探索エリアは、後記する候補リンクが選ばれる範囲であり、経路はこの探索エリア内で探索されることになる。
【００３１】
次に、ユーザは入出力インターフェース部１３を介して快適ルート探索処理における回避したい条件項目を入力する（Ｓ２０３）。この時ユーザには、図１１（ｂ）に示す画面が提示され、ユーザはこの画面で、走行時に回避したい項目（以下、回避項目と記載）や回避したい地点（以下、回避地点と記載）の名称を選択して回避条件を設定する。ここで、回避項目とは、渋滞１１１１，信号１１１２，歩行者１１１３など、遭遇することにより走行のスムーズさが失われる可能性のある要因を含む。選択項目として提示される回避項目は、後述するヒープテーブルに遅れ時間として登録する項目に対応している。また、回避地点とは、Ｓ２０２で設定された探索エリア内において、走行中にその地点の近傍を通過することによってスムーズさが失われると予想される具体的な地点であり、図３（ａ）のリンク情報に含まれる地点名で表示される。
【００３２】
この回避地点は、予め、各リンクについて対応付けられた回避項目についての遅れ時間の和を求め、これをリンクＩＤと地点名とに対応付けた回避地点リスト１１４を予め記憶装置１１に格納しておくものとする。Ｓ２０３で条件項目を選択する際には、Ｓ２０２で決定された探索エリア内に属する道路リンクに対応した回避地点の内、遅れ時間の大きなものから順に所定個数選び、図１１（ｂ）のようにユーザに提示される。
【００３３】
ここで、ユーザが回避項目を１つも選択しない場合は、ユーザに少なくとも１つの回避項目を選択する旨のメッセージを表示部に表示して端末がユーザに指示するか、遅れ時間算出部１６において遅れ時間を算出可能な全項目についての遅れ時間を反映してコストを算出することになる。
【００３４】
また、選択された回避地点については、それぞれの回避地点について予め決められた回避項目について遅れ時間を計算する。この場合、各回避地点については、対応するリンクを調べて、リンク端に信号があれば、回避項目に信号と渋滞を含め、施設情報を検索してリンクから所定の距離内存在する各施設について、それぞれの施設の種別に応じて決められた回避項目を遅れ時間の計算対象に含めるようにする。例えば施設が学校であれば歩行者を、施設が駅であれば歩行者と渋滞を回避項目に含め、これらの回避項目について遅れ時間を計算する。
【００３５】
あるいは、１つでも回避項目を選択し更に回避地点を選択した場合には、選択された回避地点について選択された回避項目についての遅れ時間を計算するようにしても良い。
【００３６】
なお、図１１（ｂ）に示す回避条件は、事前に入力して記憶装置１１に記憶しておき（不図示）、この条件を使用しても良い。
【００３７】
次に、経路探索部１５はヒープテーブルを作成する（Ｓ２０５）。ここで、ヒープテーブルとは、探索の対象となる候補リンクのリンクデータを、出発地からその候補リンクまでの総コストとともに登録するためのテーブルである。図４は、ヒープテーブルのデータ構成を示す図である。図４に示すように、ヒープテーブルには、候補リンク毎にレコード（表の１行分に相当）が登録される。各レコードは、候補リンクが含まれるメッシュのメッシュＩＤが格納される「候補メッシュＩＤ」フィールド、候補リンクのリンクＩＤが格納される「候補リンクＩＤ」フィールド、その候補リンクのコストを格納する「コスト」フィールド、該当する候補リンクが接続するリンクのリンクＩＤを格納する「接続元リンクＩＤ」フィールド、出発地から該当する候補リンクまでの総コストを格納する「総コスト」フィールド、後述する図２のＳ２０９およびＳ２１５で確定リンクとして設定済みか否かを示す確定フラグを登録するための「確定フラグ」フィールド、ユーザが回避を望む渋滞，信号，歩行者などの項目毎の遅れ時間を格納するフィールド、の各フィールドから構成される。この確定フラグが登録された候補リンクは確定リンクとなる。ヒープテーブルは、Ｓ２０５において作成された時点では、候補リンクが何も登録されていない空の状態である。
【００３８】
そこでまず最初に、出発地が存在する又は出発地に近接する少なくとも１つのリンク（以降、出発地リンクと記載）を候補リンクとして、そのリンクデータを記憶装置１１に格納されている地図情報データベース１１１から取得する（Ｓ２０６）。そして、出発地リンクのメッシュＩＤ，リンクＩＤおよび探索条件を遅れ時間算出部１６に送信し、遅れ時間算出部１６では、記憶装置１１に格納される地図情報データベース１１１，交通情報データベース１１２，走行環境情報データベース１１３の情報を用いて、出発地リンクのコストを算出する（Ｓ２０７）。本ステップにおける詳細な処理については後述する。
【００３９】
それぞれ出発地リンクについて算出したコスト及び総コストがヒープテーブルに追加される（Ｓ２０８）。この時、総コストには、Ｓ２０７で算出した各出発地リンクのコストを入力する。なお、出発地リンクは、最初のリンクであるため、接続元リンクＩＤのフィールドは空欄にしておく。そして、出発地リンクの中で総コストが最小のものを確定リンクに決定する（Ｓ２０９）。ここで、確定リンクとは、候補リンクの中で推奨経路を構成することが決定したリンクであり、ヒープテーブルの確定フラグがフィールドに「確」と入力される。ヒープテーブルに含まれる確定リンク以外のリンクを未確定リンクと呼び、未確定リンクに対しては確定フラグのフィールドに「未」が入力される。
【００４０】
次に、一つ前のステップで決定された確定リンク（以下、末端リンクと記載）に接続する少なくとも１つのリンクを候補リンクとし、そのリンク情報を記憶装置１１から取得する（Ｓ２１０）。この、一つ前のステップで決定された確定リンクを末端リンクと呼ぶ。候補リンクとするのは、この時点でヒープテーブルに含まれていないリンクである。
【００４１】
そして、Ｓ２０７と同様にして、遅れ時間算出部１６が各候補リンクのコストを算出する（Ｓ２１１）。本ステップにおける詳細な処理については後述する。次に、遅れ時間算出部１６は、出発地リンクから各候補リンクまでの総コストを算出する（Ｓ２１２）。総コストは、末端リンクの総コストに、Ｓ２１１で算出した各候補リンクのコストを足した値である。そして、各候補リンクについて、接続元リンクＩＤ，Ｓ２１１，Ｓ２１２で算出した各候補リンクのコスト、および総コストを候補リンクのリンクＩＤと共にヒープテーブルに追加する（Ｓ２１３）。
【００４２】
次に、経路探索部１５は、現在候補リンクとなっているリンクに、目的地を含むリンク（以降、目的地リンクと記載）があるか否かを判定する（Ｓ２１４）。具体的には、候補リンクが含まれるメッシュコードを特定し、リンクの各地点の座標と、Ｓ２０１で設定した目的地の座標を比較し、これらの座標が一致又は所定範囲内で近接する箇所があるか否かを判定する。そして、現在候補リンクとなっているリンクに、目的地リンクがないと判定された場合（Ｓ２１４でＮｏ）、Ｓ２１５へ進む。Ｓ２１５では、ヒープテーブルに格納されている未確定リンクの総コストを検索し、総コストが最小となっている候補リンクを選択し、この候補リンクを新たな確定リンクとする。確定リンクにおけるヒープテーブルの確定フラグのフィールドには「確」と入力される。確定リンクとならなかったリンクは、「未」が入力される。
【００４３】
一方、ステップＳ２１４の処理で、現在候補リンクとなっているリンクに、目的地リンクがあると判定された場合（Ｓ２１４でＹｅｓ）、そのリンクを特定してステップＳ２１６の処理へ進む。Ｓ２１６では、Ｓ２１５で目的地リンクとして特定された候補リンクを確定リンクとする。確定リンクとなったリンクにおけるヒープテーブルの確定フラグには「確」と追加される。確定リンクとならなかった候補リンクは、「未」が追加される。
【００４４】
そして、経路探索部１５が、ヒープテーブルの接続元リンクＩＤフィールドが空欄となっており、かつ確定フラグが「確」となっているリンクを最初のリンクとし、ヒープテーブルの接続元リンクＩＤと確定フラグを参照することによって、順次リンクを取得し、これを取得順に経路の構成リンクとすることで快適ルートを決定する（Ｓ２１７）。さらに経路探索部１５は、決定した快適ルートの情報を表示部１７に送り、画面上に表示する。
【００４５】
以上のダイクストラ法に基づく最適経路探索処理を実行することにより、Ｓ２０７およびＳ２１１におけるコスト算出処理で予め設定した条件項目をコストに反映した快適ルートを探索することができる。
【００４６】
次に、図５を用いて、図２のＳ２０７およびＳ２１１におけるコスト算出処理の説明を行う。
【００４７】
まず、遅れ時間算出部１６は、コストを算出するリンクのメッシュＩＤ、リンクＩＤおよび回避条件を経路探索部１５から取得する（Ｓ５０１）。回避条件は、Ｓ２０３の処理で、図１１（ｂ）の画面により選択される、ユーザが回避したい条件項目の情報である。図１１（ｂ）の画面での選択を行わなかった場合は、遅れ時間算出部において全てのリンクに対して全回避項目が選択されたものとして遅れ時間を算出する。このため、回避条件として何らかの項目が選択されていたかどうかを調べ（Ｓ５０２）、回避条件が何も選択されていなかった場合には（Ｓ５０２：Ｙｅｓ）、図１１（ｂ）の画面で提示された全ての開示項目が選択されたものとして遅れ時間算出のために評価する評価回避項目に設定する（Ｓ５０３）。一方、何らかの回避条件が選択されていた場合には（Ｓ５０２：Ｎｏ）、図１１（ｂ）の画面により選択された回避項目をこの評価回避項目に設定する（Ｓ５０４）。この時、回避地点が選択され回避項目は選択されていない場合には、評価回避項目には評価する回避項目が何も設定されていない状態となる。
【００４８】
次に遅れ時間算出部１６は、Ｓ５０１で取得した回避条件に回避地点が含まれるか調べ（Ｓ５０５）、回避地点が選択されていた場合には（Ｓ５０５：Ｙｅｓ）、選択されていたそれぞれの回避地点に対応する位置情報を取得する（Ｓ５０６）。そして、Ｓ５０１で取得したメッシュＩＤとリンクＩＤからリンク情報を参照して求めた位置情報と一致するものが、その取得した各位置情報にあるか調べ（Ｓ５０７）、リンクＩＤに対応した位置情報と一致する回避地点があれば（Ｓ５０７：Ｙｅｓ）、回避地点に対して事前に設定されていた回避項目を取得して評価回避項目に設定する（Ｓ５０８）。
【００４９】
このようにして設定された評価回避項目について遅れ時間を算出する。そこで、Ｓ５０１で取得したメッシュＩＤ、およびリンクＩＤを用いて記憶装置１１内を検索し、コスト計算の対象となるリンクに対応する地図情報，交通情報，走行環境情報を地図情報データベース１１１，交通情報データベース１１２，走行環境情報データベース１１３からそれぞれ取得する（Ｓ５０９）。次に評価回避項目に設定されていた回避項目について算出する遅れ時間を、渋滞，信号，歩行者などの個々の回避項目について場合分けし、Ｓ５０９で取得した地図情報，交通情報，走行環境情報を用いて各回避項目の遅れ時間を算出する（Ｓ５１０）。以下では評価回避項目の設定に基づく遅れ時間として、それぞれ渋滞による遅れ時間Ｔd1，信号による遅れ時間Ｔd2，歩行者による遅れ時間Ｔd3の算出方法の詳細について説明する。
【００５０】
評価回避項目に渋滞が設定されていた場合、渋滞による遅れ時間Ｔd1は、渋滞が発生していない状態での走行と実際の走行の旅行時間の差とする。ここで、渋滞が発生していない場合は、車両が規制速度で走行するものとし、実際の走行時には、地図情報に含まれる統計旅行速度により走行するものとする。そして、ダイクストラ法では負のコストを扱えないため、Ｔd1は０以上の値となることから、渋滞による遅れ時間Ｔd1は、以下の（式１）より求められる。
【００５１】
【数１】
【００５２】
ここで、Ｌ：リンク長、Ｖstat：統計旅行速度、Ｖreg：規制速度、とする。
【００５３】
信号による遅れ時間Ｔd2は、信号で停止しない走行をユーザの期待する走行として、赤信号による停止時間の期待値とする。赤信号による停止時間の期待値Ｔd2は、飯田恭敬他「交通工学」国民科学社，pp.248-249,1992年にあるように以下の（式２）から算出される。
【００５４】
【数２】
【００５５】
ここで、ＴR：赤信号時間、ＴG：青信号時間、ｑ：流入交通量、Ｓ：飽和交通流率、とする。
【００５６】
（式２）において、飽和交通流率が流入交通量より十分大きいと仮定してＳ≫ｑとすれば、Ｓ／（Ｓ−ｑ）がほぼ１になることから、（式２）を変形すると以下に示す（式３）となる。
【００５７】
【数３】
【００５８】
ここで、（式２）右辺の（ＴR＋ＴG）は信号一周期の時間を示すサイクル長を表し、ＴR／（ＴR＋ＴG）は信号における停止確率を表す。ここで、サイクル長は一律の値とし（例えば１２０［sec］）、信号における停止確率は図６に示すように自車の走行している進行リンクと、この進行リンクと交差するリンクの道路種別の組み合わせから決定すれば、地図情報から停止時間の期待値Ｔd2を算出することができる。ここで、交差リンクの道路種別としては、進行リンクと交差するリンクの中で最も格の高いリンク（国道＞県道＞一般道…の順に格が高いとする）の影響が一番大きいものと仮定して、その道路種別を交差リンクの道路種別を用いる。この時、高速道路には信号が存在しないため停止確率は０、国道＞県道＞一般道…の順に交通量が多いと仮定して、進入リンクの交通量が多いほど停止確率は低いこと、交差リンクの交通量が多いほど停止確率が高いこと、などの条件を反映して、図６に示すように道路種別の組み合わせ毎に停止確率をそれぞれ定め、記憶装置１１に格納しておくものとする。
【００５９】
歩行者による遅れ時間Ｔd3は、歩行者の多く出入りすると考えられる施設の近辺で大きくなると考えられる。そこで、リンクを走行中に歩行者と遭遇した場合は徐行するものと考え、歩行者による遅れ時間Ｔd3は、以下の（式４）から算出する。
【００６０】
【数４】
【００６１】
ここで、ｊは施設の種別を示すインデックスである。また、ｌはリンクとそのリンクに最も近い施設との距離であり、リンクおよび施設の位置を表す緯度・経度から求める。この時、距離ｌを算出する施設は、歩行者が多いと考えられる種別（例えばデパート，学校など）に該当する施設とする。さらに、ｃは探索を行う日種を、ｔは時刻を表し、Ｖslowは徐行速度を（例えば、時速１０km）、Ｖstatは統計旅行速度を表す。
【００６２】
ここで、リンクと施設の距離ｌの関数であるＦは、そのリンクを走行中に歩行者に遭遇する確率を示し、例えば、以下の（式５）のように定める。
【００６３】
【数５】
【００６４】
この（式５）は、施設の種別に依存し、リンクと施設の距離が近くなるほど歩行者との遭遇確率が高まることを表す。
【００６５】
また、Ｇは時間関数であり、歩行者が多くなる時間帯に大きくなるよう、例えば以下の（式６）のように定める。
【００６６】
【数６】
【００６７】
（式６）に示すように、施設の種別の違いにより、関数Ｇの値を変えることが望ましい。
【００６８】
上記（式４）では、リンクと施設の距離ｌの関数であるＦおよび時間関数Ｇを定めて、歩行者による遅れ時間Ｔd3を算出している。ここで、走行環境情報に含まれるリンクにおける歩行者数の情報を利用できる場合は、以下の（式７）から遅れ時間Ｔd3を算出しても良い。
【００６９】
【数７】
【００７０】
ここで、ｎ：歩行者数、ｌslow：歩行者１人に対して減速する距離とする。
【００７１】
また、道路構造令の様な規則に基づきリンクの道路種別からそのリンクに歩道が存在するか否か推定し、あるいは、リンクの道幅などを考慮して歩道が存在すると判断される場合やリンク情報に歩道有無の項目が含まれていて歩道が存在するとされている場合、または道幅が広い場合は歩行者による遅れ時間を小さくするよう定めても良い。
【００７２】
図５の説明に戻る。リンクのリンクＩＤと、上記のようにして算出された各回避項目の遅れ時間を図４に示すヒープテーブルに入力する（Ｓ５１１）。こうして図４に示すように、各リンクにおける回避項目毎の遅れ時間を入力していく。
【００７３】
一方、Ｓ５０７の判定で、Ｓ５０１で取得したリンクＩＤが選択された回避地点と一致しない場合（Ｓ５０７：Ｎｏ）、Ｓ５０９の処理に移って遅れ時間が算出され、Ｓ５１１でヒープテーブルに入力される。ここで、Ｓ５１４の処理により、評価回避項目として設定された回避項目についてのみ遅れ時間を算出しても良いし、コストを算出するリンクの近傍に存在する施設から、更に遅れ時間を算出する回避項目を選択しても良い。例えば、リンクの終点に信号が存在する場合は、信号による遅れ時間を算出する。また、学校，店舗のように周辺に歩行者が多いと予測される道路外の施設については、その施設とリンクとの距離が一定の閾値（例えば５００ｍ）以内の距離にある場合、歩行者による遅れ時間を算出する。あるいは、１つの回避地点を複数のリンクの集合と考え、ある回避地点が選択された時、その回避地点に対応付けられるリンクについて遅れ時間を算出してコストに反映してもよい。この場合、回避地点に対応付けられたリンクの集合に属する各リンクの近くの信号，施設の有無から、コスト算出のときの遅れ時間を算出する項目（回避項目）の選択が決定される。なお、Ｓ５１４において回避地点による遅れ時間を算出する場合は、コストを求めるリンクの地点名を取得しておくものとする（Ｓ５０６）。
【００７４】
図１１（ｂ）に示す選択の例では、ドライバの、例えば、ある信号は経験上、待ち時間が長いなどの判断により回避したい回避地点として△△丁目の信号１１２２が選択されているものの、回避項目の信号１１１２は選択されていないことから、△△丁目の信号１１１２が端点に存在するリンクについては遅れ時間を算出することになる。このように、ドライバの判断で選択された特定の地点のみ遅れ時間をコストに反映し、回避することができる。
【００７５】
以上の処理により、ユーザが選択した全回避項目・回避地点についての遅れ時間の算出が完了したら、求めた遅れ時間を用いてコストを算出する（Ｓ５１２）。ここで、算出した遅れ時間Ｔd1，Ｔd2，…と探索条件の情報から、以下の（式８）に従ってこのリンクのコストＴdを算出する。
【００７６】
【数８】
【００７７】
このとき、各回避地点について、当該回避地点がユーザに選択された場合、前述のように、各回避地点に対してはコストに反映させる回避項目が指定され、記憶装置１１に記憶されているため、選択された回避地点についてはその回避項目について遅れ時間が算出されることになる。例えば、△△丁目信号が選択された場合は、渋滞および、信号による遅れ時間を考慮するということが予め定められているものとする。
【００７８】
この各回避地点に対する回避項目の対応は、回避地点を抽出して回避地点リスト１１４が作成される際に指定される。回避地点の抽出処理は、予め各リンクについて遅れ時間を評価しておき、その遅れ時間が大きい地点（リンク）を抽出する。この時、リンク毎に近くにある施設を施設情報から検索して、その施設の種別毎に算出すべき遅れ時間の項目、即ち回避項目を予め決めておき、その回避項目の和集合から回避項目をきめる。例えば、ある「リンクＡ」の近傍に存在する施設の種別として、「信号」「学校」「駅」があり、「信号」について算出すべき遅れ時間の項目が「信号」「渋滞」の２つの回避項目であるとする。同様に「学校」については「歩行者」が、「駅」については「歩行者」と「渋滞」が回避項目とされていたとする。この時、この「リンクＡ」の地点名が「○×」であるとすれば、回避地点「○×」については、回避項目の和集合である「信号」「渋滞」「歩行者」が対応付けられることになる。そしてこれらの回避項目について算出された遅れ時間の和が所定の閾値以上となるリンクを抽出して、回避地点の地点名とこれに対応付けられた回避項目と共に、回避地点リスト１１４へ記録される。
【００７９】
ここで、ユーザが図１１（ｂ）に示すように渋滞，歩行者という回避項目および△△丁目信号という回避地点を選択した場合、リンク終端に△△丁目信号があるリンクについては上記の指定に基づきＴd＝Ｔd1＋Ｔd2とするが、それ以外のリンクでは、他の信号を回避しない選択をするということは、どんな信号でも避けたいわけではなく他の信号についてはドライバの感じる不快度に関与しないと考えられるため、Ｔd＝Ｔd1＋Ｔd3としてコストを算出する。
【００８０】
以上のようにして、図２のＳ２０７あるいはＳ２１１において候補リンクとなったリンク毎に図５の処理を実行して、コストを算出する。
【００８１】
図１２に本ナビゲーション装置による探索結果の表示例を示す。図１２（ａ）では、探索結果である快適ルートを太線で示している。また、この時、自車の現在位置１２１１の周辺のリンクの中で、コストの大きなリンクについて色を通常と変えて表示したり、マークを付けて表示しても良い。図１２（ａ）では、コストが特に大きいリンクを太点線で、コストがやや大きいリンクについては中太点線で表わしている。このような表示により、ユーザは遅れ時間が大きくスムーズな走行ができないリンクを把握し、回避して走行することができる。
【００８２】
また、経路探索処理中に図４に示したヒープテーブルを作成する際、各回避項目について算出した遅れ時間の値が所定の閾値より大きいリンクを記憶しておき、コストを構成する各回避項目，回避地点の遅れ時間の値の大小から、遅れ時間が大きい主要因を表示するようにしても良い。例えば、図１２（ａ）のリンク１２１３において、信号による遅れ時間があらかじめ規定した閾値より大きい、あるいは周囲の信号による遅れ時間より大きいなどの場合に、リンク１２１３の終点に対して、信号待ちが長くなる旨のメッセージ１２１４を表示する。さらに、図１２（ａ）のリンク１２１５において、渋滞による遅れ時間が大きい場合には、そのリンク１２１５において渋滞が発生している旨のメッセージ１２１６を表示することで、統計的に渋滞が発生する箇所を明示することができる。このような表示により、ユーザはスムーズに走行できない道路において、遅れ時間が大きい理由についても把握することができる。
【００８３】
また、図１２（ｂ）には、出発地１２２１から目的地１２２２に至る経路として、快適ルートだけでなく、時間優先ルート，距離優先ルートなどの探索条件でも探索を行い、地図上に複数経路１２２３〜１２２５を同時に表示する例を示す。この時、それぞれの経路の総遅れ時間，旅行時間，走行距離，通行料金を表示することにより、ユーザが経路の複数要素を比較することができ、ユーザはより希望に沿った経路を選択することができる。
【実施例２】
【００８４】
図７に、本発明に係る経路探索システムを、車載端末およびセンタ装置により構成した実施例の構成図を示す。図７に示すように、本実施形態における経路探索システムは、センタ装置７１と、インターネットや公衆回線網などを含む通信ネットワーク７２と、携帯電話や無線ＬＡＮなどの基地局７３と、車両７４に搭載された車載端末７５と、外部情報センタ７６と、を含んで構成される。車載端末７５の構成を、目的地までの誘導機能を有する通常のナビゲーション装置に含めても良い。
【００８５】
以下、センタ装置７１および車載端末７５の構成および機能について説明する。センタ装置７１は、通信ネットワーク７２に接続される通信装置（図示せず）を備えたコンピュータによって構成される。そして、そのコンピュータには、通信インターフェース部７１１，外部情報取得部７１２，プローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３，遅れ時間算出部７１５，コストデータベース７１６，端末要求受付部７１７，情報提供部７１８，コスト更新部７１９などを含んで構成される。
【００８６】
なお、センタ装置７１を構成するコンピュータは、少なくとも演算装置と半導体メモリやハードディスク装置などからなる記憶装置とを備える。そして、センタ装置７１を構成する各機能ブロックからの機能は、その演算処理装置が記憶装置に格納された所定のプログラムを実行することによって実現される。
【００８７】
通信インターフェース部７１１は、通信ネットワーク７２に対する通信制御を行うとともに、通信ネットワーク７２を介して車載端末７５との間でデータの送受信を行う。
【００８８】
外部情報取得部７１２は、車載端末７５から送信されたプローブデータを、通信インターフェース部７１１を介して取得する。ここでプローブデータとは、車両の走行軌跡データであり、位置情報（緯度経度などの座標）や時刻情報の他、走行速度，移動方向，ブレーキ情報等の車両情報を含んだ点列データである。外部情報取得部７１２で、取得した点列のプローブデータをリンク列あるいはリンク毎の所要時間や速度，渋滞度に変換しプローブデータベース７１３に蓄積する。
【００８９】
外部情報取得部７１２は、予め道路リンク単位の所要時間，速度，渋滞度に変換されたプローブデータを、通信インターフェース部７１１を介して取得する。この場合、道路リンク単位の情報は、車載端末７５あるいは通信ネットワーク７２を介して接続された交通情報センタで生成され、センタ装置７１に送信される。
【００９０】
また、外部情報取得部７１２は、通信インターフェース部７１１を介して、交通情報センタからリンク旅行時間などの交通情報を受信し、また天気情報センタなどの外部情報センタ７６からリンクのある地域の天候，気温などの情報を受信し、それぞれ交通情報データベース７１４２，走行環境情報データベース７１４３に格納する。外部情報取得部７１２においてプローブデータ，地図情報，交通情報，走行環境情報を取得する方法として、通信ネットワーク７２以外に記録メディアを介すこともある。
【００９１】
地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に格納される情報については、図２に示した地図情報データベース１１１，交通情報データベース１１２，走行環境情報データベース１１３、に格納される情報と同じ構成を持つため、説明を省略する。
【００９２】
遅れ時間算出部７１５は、実施例１における遅れ時間算出部１６と同等の機能を持ち、地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３にそれぞれ含まれる地図情報，交通情報，走行環境情報を用いてコストを算出する。コスト算出は、コスト更新部７１９からのコスト更新要求を受け取った場合に実行される。また、プローブデータベース７１３に含まれるプローブデータを用いてコストを算出しても良い。プローブデータを用いたコスト算出の詳細については後記する。
【００９３】
遅れ時間算出部７１５において算出されたコストは、コストデータベース７１６に蓄積される。図１０に、コストデータベース７１６に蓄積されるコスト情報の構成例を示す。図１０に示されるように、各リンクを示すリンクＩＤに対し、日種・時間帯毎に、各回避項目に対する遅れ時間が記録される。この時、複数の遅れ時間を足し合わせたコスト情報を、リンク毎に記録しても良い。
【００９４】
端末要求受付部７１７は、通信インターフェース部７１１を介して車載端末７５から送信される要求情報を受信する。この要求情報は、車載端末７５がセンタ装置７１に対してコストの提供を要求した情報であり、本実施形態に関する経路探索システムでは車載端末７５におけるコスト情報の更新時に利用される。さらに、端末要求受付部７１７は、この要求情報をコスト更新部７１９に送信する。
【００９５】
情報提供部７１８は、端末要求受付部７１７で受信した要求情報に応じて情報を提供するように機能し、要求情報にコスト情報の更新要求が含まれる場合はコストデータベース７１６から要求情報に一致したそのときの最新のコストを読み込み、通信インターフェース部７１１を介して車載端末７５に提供する。
【００９６】
コスト更新部７１９は、外部情報取得部７１２から外部情報の取得状況を、また端末要求受付部７１７から要求情報をそれぞれ取得してコスト更新を行うかタイミングか判定し、コスト更新を行うと判定した場合は遅れ時間算出部７１５にコスト更新要求を出す。コスト更新処理は、１）一定期間毎、２）プローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に格納される情報に一定件数以上の変更があった場合、３）車載端末７５から要求を受信した場合、などのタイミングで実行される。このようにすることで、より最新の情報を反映したコストを用いて経路探索を行い、よりスムーズに走行することができる。
【００９７】
一方、車両７４に搭載される車載端末７５は、本体部７５１，表示部７５２，携帯電話７５３，ＧＰＳ（Global Positioning System）受信機７５４などを含んで構成される。
【００９８】
本体部７５１は、演算処理部（図示せず），記憶装置７５５などを含んで構成されたコンピュータである。ここで記憶装置７５５は、半導体メモリやハードディスク装置などによって構成される。また、本体部７５１は、このほかにも入力装置として、種々のスイッチやボタン，タッチパネル，リモコン装置，音声マイクなどを、また、出力装置として音声スピーカなどを備えてもよい。表示部７５２については、実施例１における表示部１７と同等の機能を持つため、説明を省略する。
【００９９】
携帯電話７５３は、基地局７３との間で無線通信を行い、基地局７３および通信ネットワーク７２を介して、車載端末７５をセンタ装置７１にデータ通信可能なように接続する。また、ＧＰＳ受信機７５４は、図示しないＧＰＳ衛星からの電波を受信して、車両７４の現在位置を検出する。
【０１００】
また、本体部７５１は、通信インターフェース部７５１１，情報取得部７５１２，コストデータベース７５１３，地図情報データベース７５１４，位置情報取得部７５１５，経路探索部７５１６，入出力インターフェース部７５１７，探索条件設定部７５１８，要求情報送信部７５１９などを含んで構成される。これら本体部７５１の機能ブロックは、図示しない演算処理装置が記憶装置７５５に格納されている所定のプログラムを実行することによって実現される。ここで、先の実施例では快適ルート探索のためのコスト計算を遅れ時間算出部１６により行っていたが、この実施例では、予め各リンク毎の遅れ時間をセンタ装置で算出してコストデータベース７１６に格納しておき、これを元に更新した車載端末７５のコストデータベース７５１３の遅れ時間を用いている。
【０１０１】
通信インターフェース部７５１１は、携帯電話７５３に対する通信制御を行うとともに、基地局７３および通信ネットワーク７２を介してセンタ装置７１との間でデータの送受信を行う。
【０１０２】
情報取得部７５１２は、通信インターフェース部７５１１を介してセンタ装置７１から送信されたコスト情報を取得し、コストデータベース７５１３に保存する。コストの更新を表示部７５２に出力してユーザに通知することもある。
【０１０３】
位置情報取得部７５１５は、ＧＰＳ受信機７５４で検出した緯度経度や高度，時刻情報などのＧＰＳ情報を取得し、経路探索部７５１６に送信する。
【０１０４】
経路探索部７５１６，入出力インターフェース部７５１７，探索条件設定部７５１８については、それぞれ実施例１における経路探索部１５，入出力インターフェース部１３，探索条件設定部１４と同等の機能を持つため、説明を省略する。
【０１０５】
要求情報送信部７５１９は、通信インターフェース部７５１１を介してセンタ装置７１にコストデータの更新を確認して更新されていればそのコストデータを送るように要求する要求情報を送信する。ユーザが入出力インターフェース部７５１７を介してコストを要求する場合と、経路探索時の要求により経路探索部７５１６がコストを要求する場合がある。要求情報には、入出力インターフェース部７５１７を介して指定されたエリアや日時などが含まれる。
【０１０６】
次に、本実施形態における経路探索システムの快適ルート探索処理を、図８に示すフローチャートを用いて説明する。なお、図２に示す処理と同じステップについては、図２と共通の符号を用いて表わしている。ここで、Ｓ２０２，Ｓ２０３，Ｓ２０８〜Ｓ２１０，Ｓ２１２〜Ｓ２１７の各ステップは、図２における同名のステップと同じ処理を行うため説明を省略し、以下では、Ｓ８０１〜Ｓ８０５，Ｓ８０７，Ｓ８１１の説明を行う。
【０１０７】
この第２の実施例が第１の実施例と大きく異なる点は、第１の実施例では遅れ時間の計算をナビゲーション装置に備えた遅れ時間算出部１６で行っていたのに対し、第２の実施例では、遅れ時間の算出をセンタ装置７１に備えた遅れ時間算出部７１５で行い、車載端末７５ではその計算結果を反映したコストデータベースを受信して、経路探索の際にはこのコストデータベース７５１３から遅れ時間を参照してリンクのコストを算出している点である。このため、車載端末７５からセンタ装置７１に経路探索を行う探索エリアを送信し、センタ装置７１からその探索エリアについてコストデータを受信して、コストデータベース７５１３としている。
【０１０８】
ユーザが探索条件として快適ルートを選択した場合、図８の処理が開始され、車載端末７５は通信ネットワーク７２を介して、Ｓ２０２で決定した探索エリアをセンタ装置７１に送信する（Ｓ８０１）。
【０１０９】
センタ装置７１は、車載端末７５から送信された探索エリアを受信し（Ｓ８０２）、探索エリア内に含まれる全リンクについて、コストデータベース７１６内を検索する（Ｓ８０３）。この時、情報提供部７１８は、まず探索エリアに含まれるメッシュＩＤを全て抽出し、図１０に示すコストデータベース内のコスト情報について、メッシュＩＤと一致する全リンクのコスト情報を読み出す。
【０１１０】
センタ装置７１は、コストデータベース７１６から読みだした全コスト情報を送信し（Ｓ８０３）、車載端末７５は通信ネットワーク７２を介してこのコスト情報を受信する（Ｓ８０４）。受信したコスト情報は、情報取得部７５１２によりコストデータベース７５１３に格納される。
【０１１１】
Ｓ８０７は、Ｓ２０６で取得した出発地リンクのリンクＩＤを用いてコストデータベース７５１３内を検索してその遅れ時間を取得し、出発地リンクのコストを算出する。同様に、Ｓ８１１は、Ｓ２１０で選択された各候補リンクの遅れ時間をコストデータベース７５１３から取得して、第１の実施例におけるＳ５１０の処理と同様にしてそのリンクのコストを算出する。
【０１１２】
次に、センタ装置７１におけるコストデータベース７１６のコスト情報更新処理について、図９のフローチャートを用いて説明する。コスト情報更新処理はある一定周期（例えば５分毎）で実行される。
【０１１３】
まず、コスト更新部７１９が、外部情報取得部７１２から外部情報の取得状況を取得し、またあるいは端末要求受付部７１７から要求情報を取得してコスト更新を行うか判定する（Ｓ９００）。この時、前回のコスト更新から規定の時間以上が経過したか、外部情報の取得によりプローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に格納される情報に一定件数以上の変更があったか、あるいは端末からコスト更新要求があったか、などの判定条件の内のどれか１つ、あるいはいくつかが同時に成立した場合、コスト更新を行うものと判定され、そうでない場合はコスト更新を行わないと判定される。Ｓ９００の処理においてコスト更新を行わないと判定された場合（Ｓ９００：Ｎｏ）には、図９の処理を終了する。
【０１１４】
一方、コスト更新を行うと判定された場合（Ｓ９００：Ｙｅｓ）、まずセンタ装置７１がコスト更新を行うエリアを決定する（Ｓ９０１）。この更新エリアは、各種のデータベースについて一定件数以上の変更が行われていた場合、それに対応した更新を行うリンクを含むメッシュのメッシュＩＤなどにより指定される。また、前回のコスト更新から規定の時間以上が経過していた場合には、データが更新されたリンクを含むメッシュのメッシュＩＤなどにより指定される。あるいは端末からコスト更新要求があった場合には、そこで指定されたメッシュが更新エリアとなる。
【０１１５】
次に、遅れ時間算出部７１５が、更新エリア内に含まれる全リンクについて（Ｓ９０２）、対応するプローブデータ，地図情報，交通情報，走行環境情報を取得する（Ｓ９０３）。この時、プローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に蓄積される情報を、更新リンクのリンクＩＤを用いて検索することにより、更新リンクに対応する情報を取得する。
【０１１６】
Ｓ９０３で取得した情報を用いて、各リンクにおける遅れ時間を算出する（Ｓ９０４）。このステップでは、図５のＳ５１０における処理と同様にして遅れ時間の算出処理をリンク毎に行う。ここでＳ９０４では、既に説明したように、Ｓ９０３でＳ５０９と同様にして取得した地図情報，交通情報，走行環境情報を用いて遅れ時間を算出して良いし、あるいはＳ９０３で取得したプローブデータを用いて遅れ時間を算出しても良い。プローブデータを用いた、渋滞，信号，歩行者による遅れ時間算出法を以下で説明する。
【０１１７】
渋滞による遅れ時間Ｔd1を求める場合は、実際の走行時間として、プローブデータより各リンクを通過するのに要した旅行時間Ｔprobeを用いて、以下の（式９）より算出する。
【０１１８】
【数９】
【０１１９】
信号による遅れ時間Ｔd2を求める場合は、信号の存在する交差点を含む道路区間（例えば、交差点の前後１００［ｍ］）を通過する際のプローブデータから、その交差点における平均停止時間を求め、信号による遅れ時間とする。
【０１２０】
歩行者による遅れ時間Ｔd3を求める場合は、歩行者が周囲に多いと考えられる施設の近辺を走行したプローブデータから、（式７）における、ｎ：歩行者数、ｌslow：歩行者１人に対して減速する距離、Ｖslow：徐行速度を推定し、（式７）に推定値を代入することにより歩行者による遅れ時間を算出する。
【０１２１】
このように、実際にリンクを走行したプローブデータを用いることにより、より正確な遅れ時間を算出することができ、より実状を反映した快適ルートを実現できる。
【０１２２】
図９の説明に戻る。遅れ時間算出部７１５によりＳ９０４で算出されたコストをコストデータベース７１６に保存する（Ｓ９０５）。またこの時、回避地点の抽出処理は，遅れ時間算出部７１５では算出した遅れ時間の和が閾値以上のリンクを抽出し、図示されていない回避地点リストを更新する。この回避地点リストはコストデータベース７１６に保存するようにしてもよい。更新エリア内に、上記処理を実行していない未更新のリンクが存在する場合は、上記処理をリンク毎に繰り返す（Ｓ９０６）。
【０１２３】
上記の実施形態では、遅れ時間情報をセンタ装置７１で算出し、車載端末７５に送信して経路探索を行うことにより快適ルートを算出する。ここで、上記車載端末７５に備わる経路探索部７５１６と同様の機能をセンタ装置７１に備え、センタ装置で探索した経路を車載端末７５に送信して表示しても良い。この時、探索した経路は、経路を構成するリンクのリンクＩＤの集合として送信される。
【符号の説明】
【０１２４】
１１ 記憶装置
１２，７５１５ 位置情報取得部
１３，７５１７ 入出力インターフェース部
１４，７５１８ 探索条件設定部
１５ 経路探索部
１６，７１５ 遅れ時間算出部
１７ 表示部
７１ センタ装置
７２ 通信ネットワーク
７３ 基地局
７５ 車載端末
７１１，７５１１ 通信インターフェース部
７１２ 外部情報取得部
７１３ プローブデータベース
７１６，７５１３ コストデータベース
７１７ 端末要求受付部
７１８ 情報提供部
７５１ 本体部
７５２ 表示部
７５４ ＧＰＳ受信機
７１４１，７５１４ 地図情報データベース
７１４２ 交通情報データベース
７１４３ 走行環境情報データベース
７５１２ 情報取得部
７５１６ 経路探索部
７５１９ 要求情報送信部
【技術分野】
【０００１】
本発明は、ナビゲーションシステムに関わり、特に経路探索を行うシステムに関わる。
【背景技術】
【０００２】
近年、ナビゲーションシステムを用いて現在地から目的地までの経路を誘導する際、時間優先，距離優先，一般道優先などの条件をユーザが選択することにより、ユーザにとって最適な経路を探索し、誘導・案内する技術が普及している。ユーザが時間優先経路を選択した場合、カーナビゲーション装置は現況交通情報および統計交通情報を用いて目的地までの所要時間が最短となる経路を探索する。さらに、ユーザの幅広いニーズに応えるため、上記の時間優先，距離優先，一般道優先以外に、快適性，安全性などの条件についても最適な経路を探索し、誘導・案内する技術が開発されている。
【０００３】
例えば、特許文献１に示されるように、任意の目的条件を選択することで、２地点間を結ぶ複数経路を目的条件に対応する重みデータで評価し、最も目的条件に適合した経路を提供する技術が存在する。目的条件に対応する重みデータの評価は、ノードの判断項目（信号の有無，道路交差数，見通し度，年間事故件数）およびリンクの判断項目（一方通行の有無，高速・一般道の区別，渋滞度，信号数，最大カーブ曲率，道幅，年間事故件数，最大勾配，平均勾配，路面の凹凸レベル）の内のいずれかに対して、目的条件毎に定められて重みテーブルデータベースに格納された重みテーブルにより重み付けして行う。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−７７２９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の方法により、様々な目的条件に適合した経路を探索し、ユーザに提供することができる。しかしながら、特許文献１には、実際の道路状況および交通状況と快適性の関係を反映した重みテーブルの設定法については考慮されていない。即ち、評価の項目と快適性の関わりについて考慮されていないため、評価により設定した重みに基づいて経路を計算しても、その結果が必ずしも快適な経路になるとは限らない。例えば、渋滞度と信号の有無の重みについて、どの程度の大小関係をもった重みを設定すれば、最もユーザにとって快適な経路を探索できるかは、一般に明らかではない。
【０００６】
また、実際の走行においては、都市部，郊外などの地域の違い、あるいは昼夜や平日／休日などの時間帯の違いにより項目間の重みの大小関係が異なる可能性がある。例えば、信号の数が同じであっても、交通量の多い国道を走行する場合と交通量の少ない脇道を走行する場合とでは、ユーザが運転の際に感じる快適性の度合いが異なる。
【０００７】
以上で述べたように、ユーザにとって快適な経路を提供するためには、地域・時間帯などのさまざまな状況を反映して快適性を表す指標を算出することが重要であり、特許文献１に記載の方法では十分にその目的を果たすことができない。快適な経路を提供するには、快適な経路とは何かということ、および走行環境の評価の項目と快適性との関係について指標を定義し、経路を計算する必要がある。
【０００８】
本発明の目的は、このような課題を解決し、快適性を表す指標を用いた経路探索により、ユーザがより快適に走行できる経路を提供することである。
【課題を解決するための手段】
【０００９】
この課題を解決するため、本発明における経路探索方法は、経路の快適性を表す指標として、期待する走行時間からの遅れ時間を用い、ユーザが回避を望む状況として設定した地点に関して、交通状況や歩行者などの要因から受ける遅れがなるべく小さくなるようにしてスムーズに走行できる経路をユーザに提供する。そのため、ユーザが回避を望む地点に関して地図情報，交通情報，走行環境に応じて期待する到着予想時刻からの遅れ時間を算出し、その遅れ時間から経路探索に用いるリンク毎の重みパラメータ（以下、コストと記載）を算出し、このコストを用いて出発地から目的地までのコスト最小経路を計算するステップを実行することを特徴とする。
【発明の効果】
【００１０】
ユーザが回避を望む１つ以上の状況毎に、その状況に遭遇した場合に発生するユーザの期待からの遅れ時間を算出して経路探索に用いるコストに反映させることにより、遅れ時間を考慮した経路の探索を行うことができ、ユーザが望むスムーズに走ることのできる経路を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】本願発明に関わる経路探索システムの構成図である。
【図２】本願発明に関わる経路探索システムの処理を示すフローチャートである。
【図３】地図情報，交通情報，走行環境情報のデータ構成を示す図である。
【図４】経路探索時に作成されるヒープデータの一例を示す図である。
【図５】コスト算出処理を示すフローチャートである。
【図６】道路種別による信号における停止確率を示す図である。
【図７】本願発明に関わる経路探索システムの他の構成図である。
【図８】本願発明に関わる経路探索システムの処理を示す他のフローチャートである。
【図９】センタ装置におけるコスト更新処理を示すフローチャートである。
【図１０】コストデータベースに蓄積されるコスト情報のデータ構成を示す図である。
【図１１】経路探索条件入力画面の一例を示す図である。
【図１２】探索結果表示画面の一例を示す図である。
【発明を実施するための形態】
【００１２】
本発明の実施形態について、図面を参照して説明する。
【実施例１】
【００１３】
図１は、本発明の一実施形態が適用された経路探索方法を実現するナビゲーション装置の構成図である。本発明は、交通状況や歩行者などから受ける影響がなるべく小さくなるようにした、スムーズに走行することのできる経路を快適ルートとして探索するため、走行時の遅れ時間の大きさが運転者の感じる不快度の大きさに大きな影響を与えるものとして、この遅れ時間を快適性の指標にした経路探索を行う。図１に示すように、本実施形態におけるナビゲーション装置は、記憶装置１１と、位置情報取得部１２と、入出力インターフェース部１３と、探索条件設定部１４と、経路探索部１５と、遅れ時間算出部１６と、表示部１７とを含んで構成される。
【００１４】
記憶装置１１は、図１に示すように、地図情報データベース１１１と、交通情報データベース１１２と、走行環境情報データベース１１３とを内部に備える。地図情報データベースに蓄積される地図情報の構成例として、図３（ａ）にはリンク情報、図３（ｂ）には施設情報を示す。また、図３（ｃ）に交通情報データベースに蓄積される交通情報の構成例を、図３（ｄ）に走行環境情報データベースに蓄積される走行環境情報の構成例を示す。これらのリンク情報，交通情報，走行環境情報は、メッシュＩＤで識別されるメッシュおよびリンクＩＤで識別されるリンクと関係付けて記憶される。ここで、メッシュとは、緯度経度に基づいて設定された矩形領域（例えば、緯度差４０分，経度差１度の領域）を表す。この時、メッシュの大きさは、ユーザの求める渋滞範囲の分解能，道路の構成などによって、適宜設定して良い。また、リンクは、道路を構成する部分であり、交差点や分岐などに指定されるノード間を結んだベクトルとして表される。この時、同じ道路の上り方向と下り方向とは、それぞれ別のリンクとして管理されるものとする。
【００１５】
リンク情報は、高速道路・一般国道などの分類を示す道路種別、リンクを走行する際の規制速度を示す規制速度、リンクの幅を示す道路幅員、リンクの代表点（例えば、リンクの中間点）の位置座標を示す緯度・経度、過去に該当リンク上で起きた事故数、リンク終端点における信号有無、リンク内の踏切有無、リンクを代表する地点名などの情報を含む。
【００１６】
施設情報は、施設名称と、デパート，学校といった施設種別と、施設の代表点の位置座標を表す緯度・経度などの情報を含む。
【００１７】
交通情報は、１つのリンクに対し、予測対象日の日種（曜日，平日／土曜／休日，五十日，天気等）および一定間隔の時間帯（例えば５分毎）に対応して作成された統計交通情報として、統計速度，統計旅行時間が含まれる。この場合、予測対象日の日種に該当する過去の日が複数日あったとして、それらの同一時間帯に関するリンク旅行速度の平均値や中央値等の統計値が、リンクの統計旅行速度に該当する。統計旅行時間は、上記旅行速度と同様、同一日種かつ同一時間帯のリンク旅行時間の統計値である。これらの他に、路上センサにおいて取得された情報、あるいはプローブカーより送信された情報から求めた現況交通情報を含んでも良い。また、本構成要素として図示しないが、携帯電話や無線通信，放送等を介して外部から交通情報を取得し、これを用いても良い。
【００１８】
走行環境情報は、該当リンクを通過する際の平均的な信号停止時間，天気情報センタなどから入手した走行予定時の天候，気温，風速などの気象情報、および路面温度や平均的に遭遇する歩行者数などの情報を含む。
【００１９】
位置情報取得部１２は、出発地の位置を算出し、また、現在時刻を取得する。この時、例えば、図中に表示しない車速センサ，ジャイロセンサ，ＧＰＳ受信装置などのうち少なくとも一つから取得した情報に基づき、位置の算出を行う。車速センサは、車輪の円周と計測される車輪の回転数の積から走行距離を測定し、さらに対となる車輪の回転数の差から曲がった角度を計測する。ジャイロセンサは、光ファイバファイロや振動ジャイロ等で構成され、センサが取り付けられた車両の回転した角度を検出する。ＧＰＳ受信装置は、ＧＰＳ衛星からの信号を受信し、装置とＧＰＳ衛星間の距離と距離の変化率を３基以上の衛星との間で測定する。
【００２０】
入出力インターフェース部１３は、出発地，目的地および、経路探索条件に関する情報を経路探索部に送る。出発地情報は、位置情報取得部により算出された、本システムが搭載された端末が存在する場所として計算される。目的地情報は、表示部に表示された地図上の地点をユーザが画面上の位置で選択する、あるいは緯度経度により指定する等の方法で設定される。この時、出発地情報を目的地情報の指定と同様の方法によりユーザが指定しても良い。
【００２１】
経路探索条件は、表示部の画面上に表示された選択肢から、ユーザが望む経路の条件を少なくとも一つ選択する形式で指定される。図１１（ａ）に、経路探索条件設定画面の一例を示す。ユーザは画面上に表示された、時間優先ルート，距離優先ルート，省燃費ルート，快適ルートなどの選択肢から一つを選ぶことで、自分の望む探索条件を指定する。
【００２２】
さらに、入出力インターフェース部１３は、経路探索部において算出された経路の情報を表示部に送る。
【００２３】
探索条件設定部１４は、入出力インターフェース部１３を介して送信された探索条件，目的地の情報や、位置取得部から送信された出発地情報を経路探索部に送信する。
【００２４】
経路探索部１５は、ユーザが経路探索条件として快適ルートを選択した場合に、この快適ルートをできるだけスムーズな走行が可能となる経路と定義し、（１）ユーザがスムーズな運転でないと感じるのは、走行中に累積されてゆく不快度が大きいため、であり（２）不快度の大小は、期待される理想的な走行からの遅れ時間により左右される、という２つの仮定から、この遅れ時間の累積をスムーズな運転の指標として求め、快適ルートを遅れ時間最小ルートとして求める。そして、この期待される理想的な走行からの遅れ時間を求めるため、運転者が期待する理想的な走行を実現するために回避を望む状況として選択された事象による遅れ時間を評価し、選択されない事象による遅れ時間は、運転者が気にしない、即ち運転の快・不快に寄与しないものとして遅れ時間の評価には含めないものとする。そこで、探索対象となるリンクのリンク情報およびユーザが走行時に回避することを望む項目の情報を遅れ時間算出部１６に送り、コスト情報を要求する、そして、遅れ時間算出部１６で算出された当該リンクのコストを用いて探索を行う。経路探索アルゴリズムは一般的に、ダイクストラ法などが用いられ、出発地から目的地までの最小コストの経路を算出する。
【００２５】
遅れ時間算出部１６は、記憶装置１１に記憶された道路情報，交通情報，走行環境情報を用いて、経路探索部１５から要求されたリンクのコストを算出する。
【００２６】
表示部１７は、探索条件設定時に探索条件の選択肢を表示し、ユーザが探索条件を選択できるようにする。また、地図情報を用い、指定された縮尺，描画方式（平面図，鳥瞰図など）で、道路、その他の地図構成物や、出発地を示すマーク，経路探索により算出された経路を描画する。
【００２７】
以上の構成により、出発地から目的地に向かう経路の中で最もスムーズに走行することのできる快適ルートを探索することができる。
【００２８】
次に、本実施形態におけるナビゲーション装置の快適ルート探索処理を、図２に示すフローチャートを用いて説明する。ナビゲーション装置では快適ルート探索処理に先立ち、まず、出発地，目的地、および出発時刻が設定される。この時、出発地および出発時刻は、位置情報取得部１２によって取得された端末の現在位置および現在時刻とする。目的地は、表示部１７に表示された地図上の位置、あるいは緯度経度の入力などの方法により、入出力インターフェース部１３を介してユーザが指定する。なお、出発地を目的地の指定と同様の方法で指定しても良い。また、出発時刻をユーザの入力により指定しても良い。
【００２９】
次に、ユーザは入出力インターフェース部１３を介して探索条件を入力する。この時ユーザは、図１１（ａ）に示す画面上で自分の望む経路を指定する。ここで、時間優先ルート１１０１は目的地までの総旅行時間が最も短くなる経路、距離優先ルート１１０２は目的地までの総走行距離が最も短いルート、消費燃料優先ルート１１０３は目的地までの消費燃料が最も少ない経路、快適ルート１１０４は目的地までの遅れ時間が最も少ない経路の探索をそれぞれ指示するための項目である。ユーザが図１１（ａ）に示す画面上で快適ルート１１０４を選択すると、快適ルート探索処理が開始される。
【００３０】
快適ルート探索処理ではまず、探索エリアが決定される（Ｓ２０２）。探索エリアは、出発地及び目的地が含まれるメッシュをそれぞれ特定し、２メッシュを結ぶ線分を対角線とする長方形あるいは２メッシュを内包する楕円などの領域として設定される。探索エリアは、後記する候補リンクが選ばれる範囲であり、経路はこの探索エリア内で探索されることになる。
【００３１】
次に、ユーザは入出力インターフェース部１３を介して快適ルート探索処理における回避したい条件項目を入力する（Ｓ２０３）。この時ユーザには、図１１（ｂ）に示す画面が提示され、ユーザはこの画面で、走行時に回避したい項目（以下、回避項目と記載）や回避したい地点（以下、回避地点と記載）の名称を選択して回避条件を設定する。ここで、回避項目とは、渋滞１１１１，信号１１１２，歩行者１１１３など、遭遇することにより走行のスムーズさが失われる可能性のある要因を含む。選択項目として提示される回避項目は、後述するヒープテーブルに遅れ時間として登録する項目に対応している。また、回避地点とは、Ｓ２０２で設定された探索エリア内において、走行中にその地点の近傍を通過することによってスムーズさが失われると予想される具体的な地点であり、図３（ａ）のリンク情報に含まれる地点名で表示される。
【００３２】
この回避地点は、予め、各リンクについて対応付けられた回避項目についての遅れ時間の和を求め、これをリンクＩＤと地点名とに対応付けた回避地点リスト１１４を予め記憶装置１１に格納しておくものとする。Ｓ２０３で条件項目を選択する際には、Ｓ２０２で決定された探索エリア内に属する道路リンクに対応した回避地点の内、遅れ時間の大きなものから順に所定個数選び、図１１（ｂ）のようにユーザに提示される。
【００３３】
ここで、ユーザが回避項目を１つも選択しない場合は、ユーザに少なくとも１つの回避項目を選択する旨のメッセージを表示部に表示して端末がユーザに指示するか、遅れ時間算出部１６において遅れ時間を算出可能な全項目についての遅れ時間を反映してコストを算出することになる。
【００３４】
また、選択された回避地点については、それぞれの回避地点について予め決められた回避項目について遅れ時間を計算する。この場合、各回避地点については、対応するリンクを調べて、リンク端に信号があれば、回避項目に信号と渋滞を含め、施設情報を検索してリンクから所定の距離内存在する各施設について、それぞれの施設の種別に応じて決められた回避項目を遅れ時間の計算対象に含めるようにする。例えば施設が学校であれば歩行者を、施設が駅であれば歩行者と渋滞を回避項目に含め、これらの回避項目について遅れ時間を計算する。
【００３５】
あるいは、１つでも回避項目を選択し更に回避地点を選択した場合には、選択された回避地点について選択された回避項目についての遅れ時間を計算するようにしても良い。
【００３６】
なお、図１１（ｂ）に示す回避条件は、事前に入力して記憶装置１１に記憶しておき（不図示）、この条件を使用しても良い。
【００３７】
次に、経路探索部１５はヒープテーブルを作成する（Ｓ２０５）。ここで、ヒープテーブルとは、探索の対象となる候補リンクのリンクデータを、出発地からその候補リンクまでの総コストとともに登録するためのテーブルである。図４は、ヒープテーブルのデータ構成を示す図である。図４に示すように、ヒープテーブルには、候補リンク毎にレコード（表の１行分に相当）が登録される。各レコードは、候補リンクが含まれるメッシュのメッシュＩＤが格納される「候補メッシュＩＤ」フィールド、候補リンクのリンクＩＤが格納される「候補リンクＩＤ」フィールド、その候補リンクのコストを格納する「コスト」フィールド、該当する候補リンクが接続するリンクのリンクＩＤを格納する「接続元リンクＩＤ」フィールド、出発地から該当する候補リンクまでの総コストを格納する「総コスト」フィールド、後述する図２のＳ２０９およびＳ２１５で確定リンクとして設定済みか否かを示す確定フラグを登録するための「確定フラグ」フィールド、ユーザが回避を望む渋滞，信号，歩行者などの項目毎の遅れ時間を格納するフィールド、の各フィールドから構成される。この確定フラグが登録された候補リンクは確定リンクとなる。ヒープテーブルは、Ｓ２０５において作成された時点では、候補リンクが何も登録されていない空の状態である。
【００３８】
そこでまず最初に、出発地が存在する又は出発地に近接する少なくとも１つのリンク（以降、出発地リンクと記載）を候補リンクとして、そのリンクデータを記憶装置１１に格納されている地図情報データベース１１１から取得する（Ｓ２０６）。そして、出発地リンクのメッシュＩＤ，リンクＩＤおよび探索条件を遅れ時間算出部１６に送信し、遅れ時間算出部１６では、記憶装置１１に格納される地図情報データベース１１１，交通情報データベース１１２，走行環境情報データベース１１３の情報を用いて、出発地リンクのコストを算出する（Ｓ２０７）。本ステップにおける詳細な処理については後述する。
【００３９】
それぞれ出発地リンクについて算出したコスト及び総コストがヒープテーブルに追加される（Ｓ２０８）。この時、総コストには、Ｓ２０７で算出した各出発地リンクのコストを入力する。なお、出発地リンクは、最初のリンクであるため、接続元リンクＩＤのフィールドは空欄にしておく。そして、出発地リンクの中で総コストが最小のものを確定リンクに決定する（Ｓ２０９）。ここで、確定リンクとは、候補リンクの中で推奨経路を構成することが決定したリンクであり、ヒープテーブルの確定フラグがフィールドに「確」と入力される。ヒープテーブルに含まれる確定リンク以外のリンクを未確定リンクと呼び、未確定リンクに対しては確定フラグのフィールドに「未」が入力される。
【００４０】
次に、一つ前のステップで決定された確定リンク（以下、末端リンクと記載）に接続する少なくとも１つのリンクを候補リンクとし、そのリンク情報を記憶装置１１から取得する（Ｓ２１０）。この、一つ前のステップで決定された確定リンクを末端リンクと呼ぶ。候補リンクとするのは、この時点でヒープテーブルに含まれていないリンクである。
【００４１】
そして、Ｓ２０７と同様にして、遅れ時間算出部１６が各候補リンクのコストを算出する（Ｓ２１１）。本ステップにおける詳細な処理については後述する。次に、遅れ時間算出部１６は、出発地リンクから各候補リンクまでの総コストを算出する（Ｓ２１２）。総コストは、末端リンクの総コストに、Ｓ２１１で算出した各候補リンクのコストを足した値である。そして、各候補リンクについて、接続元リンクＩＤ，Ｓ２１１，Ｓ２１２で算出した各候補リンクのコスト、および総コストを候補リンクのリンクＩＤと共にヒープテーブルに追加する（Ｓ２１３）。
【００４２】
次に、経路探索部１５は、現在候補リンクとなっているリンクに、目的地を含むリンク（以降、目的地リンクと記載）があるか否かを判定する（Ｓ２１４）。具体的には、候補リンクが含まれるメッシュコードを特定し、リンクの各地点の座標と、Ｓ２０１で設定した目的地の座標を比較し、これらの座標が一致又は所定範囲内で近接する箇所があるか否かを判定する。そして、現在候補リンクとなっているリンクに、目的地リンクがないと判定された場合（Ｓ２１４でＮｏ）、Ｓ２１５へ進む。Ｓ２１５では、ヒープテーブルに格納されている未確定リンクの総コストを検索し、総コストが最小となっている候補リンクを選択し、この候補リンクを新たな確定リンクとする。確定リンクにおけるヒープテーブルの確定フラグのフィールドには「確」と入力される。確定リンクとならなかったリンクは、「未」が入力される。
【００４３】
一方、ステップＳ２１４の処理で、現在候補リンクとなっているリンクに、目的地リンクがあると判定された場合（Ｓ２１４でＹｅｓ）、そのリンクを特定してステップＳ２１６の処理へ進む。Ｓ２１６では、Ｓ２１５で目的地リンクとして特定された候補リンクを確定リンクとする。確定リンクとなったリンクにおけるヒープテーブルの確定フラグには「確」と追加される。確定リンクとならなかった候補リンクは、「未」が追加される。
【００４４】
そして、経路探索部１５が、ヒープテーブルの接続元リンクＩＤフィールドが空欄となっており、かつ確定フラグが「確」となっているリンクを最初のリンクとし、ヒープテーブルの接続元リンクＩＤと確定フラグを参照することによって、順次リンクを取得し、これを取得順に経路の構成リンクとすることで快適ルートを決定する（Ｓ２１７）。さらに経路探索部１５は、決定した快適ルートの情報を表示部１７に送り、画面上に表示する。
【００４５】
以上のダイクストラ法に基づく最適経路探索処理を実行することにより、Ｓ２０７およびＳ２１１におけるコスト算出処理で予め設定した条件項目をコストに反映した快適ルートを探索することができる。
【００４６】
次に、図５を用いて、図２のＳ２０７およびＳ２１１におけるコスト算出処理の説明を行う。
【００４７】
まず、遅れ時間算出部１６は、コストを算出するリンクのメッシュＩＤ、リンクＩＤおよび回避条件を経路探索部１５から取得する（Ｓ５０１）。回避条件は、Ｓ２０３の処理で、図１１（ｂ）の画面により選択される、ユーザが回避したい条件項目の情報である。図１１（ｂ）の画面での選択を行わなかった場合は、遅れ時間算出部において全てのリンクに対して全回避項目が選択されたものとして遅れ時間を算出する。このため、回避条件として何らかの項目が選択されていたかどうかを調べ（Ｓ５０２）、回避条件が何も選択されていなかった場合には（Ｓ５０２：Ｙｅｓ）、図１１（ｂ）の画面で提示された全ての開示項目が選択されたものとして遅れ時間算出のために評価する評価回避項目に設定する（Ｓ５０３）。一方、何らかの回避条件が選択されていた場合には（Ｓ５０２：Ｎｏ）、図１１（ｂ）の画面により選択された回避項目をこの評価回避項目に設定する（Ｓ５０４）。この時、回避地点が選択され回避項目は選択されていない場合には、評価回避項目には評価する回避項目が何も設定されていない状態となる。
【００４８】
次に遅れ時間算出部１６は、Ｓ５０１で取得した回避条件に回避地点が含まれるか調べ（Ｓ５０５）、回避地点が選択されていた場合には（Ｓ５０５：Ｙｅｓ）、選択されていたそれぞれの回避地点に対応する位置情報を取得する（Ｓ５０６）。そして、Ｓ５０１で取得したメッシュＩＤとリンクＩＤからリンク情報を参照して求めた位置情報と一致するものが、その取得した各位置情報にあるか調べ（Ｓ５０７）、リンクＩＤに対応した位置情報と一致する回避地点があれば（Ｓ５０７：Ｙｅｓ）、回避地点に対して事前に設定されていた回避項目を取得して評価回避項目に設定する（Ｓ５０８）。
【００４９】
このようにして設定された評価回避項目について遅れ時間を算出する。そこで、Ｓ５０１で取得したメッシュＩＤ、およびリンクＩＤを用いて記憶装置１１内を検索し、コスト計算の対象となるリンクに対応する地図情報，交通情報，走行環境情報を地図情報データベース１１１，交通情報データベース１１２，走行環境情報データベース１１３からそれぞれ取得する（Ｓ５０９）。次に評価回避項目に設定されていた回避項目について算出する遅れ時間を、渋滞，信号，歩行者などの個々の回避項目について場合分けし、Ｓ５０９で取得した地図情報，交通情報，走行環境情報を用いて各回避項目の遅れ時間を算出する（Ｓ５１０）。以下では評価回避項目の設定に基づく遅れ時間として、それぞれ渋滞による遅れ時間Ｔd1，信号による遅れ時間Ｔd2，歩行者による遅れ時間Ｔd3の算出方法の詳細について説明する。
【００５０】
評価回避項目に渋滞が設定されていた場合、渋滞による遅れ時間Ｔd1は、渋滞が発生していない状態での走行と実際の走行の旅行時間の差とする。ここで、渋滞が発生していない場合は、車両が規制速度で走行するものとし、実際の走行時には、地図情報に含まれる統計旅行速度により走行するものとする。そして、ダイクストラ法では負のコストを扱えないため、Ｔd1は０以上の値となることから、渋滞による遅れ時間Ｔd1は、以下の（式１）より求められる。
【００５１】
【数１】
【００５２】
ここで、Ｌ：リンク長、Ｖstat：統計旅行速度、Ｖreg：規制速度、とする。
【００５３】
信号による遅れ時間Ｔd2は、信号で停止しない走行をユーザの期待する走行として、赤信号による停止時間の期待値とする。赤信号による停止時間の期待値Ｔd2は、飯田恭敬他「交通工学」国民科学社，pp.248-249,1992年にあるように以下の（式２）から算出される。
【００５４】
【数２】
【００５５】
ここで、ＴR：赤信号時間、ＴG：青信号時間、ｑ：流入交通量、Ｓ：飽和交通流率、とする。
【００５６】
（式２）において、飽和交通流率が流入交通量より十分大きいと仮定してＳ≫ｑとすれば、Ｓ／（Ｓ−ｑ）がほぼ１になることから、（式２）を変形すると以下に示す（式３）となる。
【００５７】
【数３】
【００５８】
ここで、（式２）右辺の（ＴR＋ＴG）は信号一周期の時間を示すサイクル長を表し、ＴR／（ＴR＋ＴG）は信号における停止確率を表す。ここで、サイクル長は一律の値とし（例えば１２０［sec］）、信号における停止確率は図６に示すように自車の走行している進行リンクと、この進行リンクと交差するリンクの道路種別の組み合わせから決定すれば、地図情報から停止時間の期待値Ｔd2を算出することができる。ここで、交差リンクの道路種別としては、進行リンクと交差するリンクの中で最も格の高いリンク（国道＞県道＞一般道…の順に格が高いとする）の影響が一番大きいものと仮定して、その道路種別を交差リンクの道路種別を用いる。この時、高速道路には信号が存在しないため停止確率は０、国道＞県道＞一般道…の順に交通量が多いと仮定して、進入リンクの交通量が多いほど停止確率は低いこと、交差リンクの交通量が多いほど停止確率が高いこと、などの条件を反映して、図６に示すように道路種別の組み合わせ毎に停止確率をそれぞれ定め、記憶装置１１に格納しておくものとする。
【００５９】
歩行者による遅れ時間Ｔd3は、歩行者の多く出入りすると考えられる施設の近辺で大きくなると考えられる。そこで、リンクを走行中に歩行者と遭遇した場合は徐行するものと考え、歩行者による遅れ時間Ｔd3は、以下の（式４）から算出する。
【００６０】
【数４】
【００６１】
ここで、ｊは施設の種別を示すインデックスである。また、ｌはリンクとそのリンクに最も近い施設との距離であり、リンクおよび施設の位置を表す緯度・経度から求める。この時、距離ｌを算出する施設は、歩行者が多いと考えられる種別（例えばデパート，学校など）に該当する施設とする。さらに、ｃは探索を行う日種を、ｔは時刻を表し、Ｖslowは徐行速度を（例えば、時速１０km）、Ｖstatは統計旅行速度を表す。
【００６２】
ここで、リンクと施設の距離ｌの関数であるＦは、そのリンクを走行中に歩行者に遭遇する確率を示し、例えば、以下の（式５）のように定める。
【００６３】
【数５】
【００６４】
この（式５）は、施設の種別に依存し、リンクと施設の距離が近くなるほど歩行者との遭遇確率が高まることを表す。
【００６５】
また、Ｇは時間関数であり、歩行者が多くなる時間帯に大きくなるよう、例えば以下の（式６）のように定める。
【００６６】
【数６】
【００６７】
（式６）に示すように、施設の種別の違いにより、関数Ｇの値を変えることが望ましい。
【００６８】
上記（式４）では、リンクと施設の距離ｌの関数であるＦおよび時間関数Ｇを定めて、歩行者による遅れ時間Ｔd3を算出している。ここで、走行環境情報に含まれるリンクにおける歩行者数の情報を利用できる場合は、以下の（式７）から遅れ時間Ｔd3を算出しても良い。
【００６９】
【数７】
【００７０】
ここで、ｎ：歩行者数、ｌslow：歩行者１人に対して減速する距離とする。
【００７１】
また、道路構造令の様な規則に基づきリンクの道路種別からそのリンクに歩道が存在するか否か推定し、あるいは、リンクの道幅などを考慮して歩道が存在すると判断される場合やリンク情報に歩道有無の項目が含まれていて歩道が存在するとされている場合、または道幅が広い場合は歩行者による遅れ時間を小さくするよう定めても良い。
【００７２】
図５の説明に戻る。リンクのリンクＩＤと、上記のようにして算出された各回避項目の遅れ時間を図４に示すヒープテーブルに入力する（Ｓ５１１）。こうして図４に示すように、各リンクにおける回避項目毎の遅れ時間を入力していく。
【００７３】
一方、Ｓ５０７の判定で、Ｓ５０１で取得したリンクＩＤが選択された回避地点と一致しない場合（Ｓ５０７：Ｎｏ）、Ｓ５０９の処理に移って遅れ時間が算出され、Ｓ５１１でヒープテーブルに入力される。ここで、Ｓ５１４の処理により、評価回避項目として設定された回避項目についてのみ遅れ時間を算出しても良いし、コストを算出するリンクの近傍に存在する施設から、更に遅れ時間を算出する回避項目を選択しても良い。例えば、リンクの終点に信号が存在する場合は、信号による遅れ時間を算出する。また、学校，店舗のように周辺に歩行者が多いと予測される道路外の施設については、その施設とリンクとの距離が一定の閾値（例えば５００ｍ）以内の距離にある場合、歩行者による遅れ時間を算出する。あるいは、１つの回避地点を複数のリンクの集合と考え、ある回避地点が選択された時、その回避地点に対応付けられるリンクについて遅れ時間を算出してコストに反映してもよい。この場合、回避地点に対応付けられたリンクの集合に属する各リンクの近くの信号，施設の有無から、コスト算出のときの遅れ時間を算出する項目（回避項目）の選択が決定される。なお、Ｓ５１４において回避地点による遅れ時間を算出する場合は、コストを求めるリンクの地点名を取得しておくものとする（Ｓ５０６）。
【００７４】
図１１（ｂ）に示す選択の例では、ドライバの、例えば、ある信号は経験上、待ち時間が長いなどの判断により回避したい回避地点として△△丁目の信号１１２２が選択されているものの、回避項目の信号１１１２は選択されていないことから、△△丁目の信号１１１２が端点に存在するリンクについては遅れ時間を算出することになる。このように、ドライバの判断で選択された特定の地点のみ遅れ時間をコストに反映し、回避することができる。
【００７５】
以上の処理により、ユーザが選択した全回避項目・回避地点についての遅れ時間の算出が完了したら、求めた遅れ時間を用いてコストを算出する（Ｓ５１２）。ここで、算出した遅れ時間Ｔd1，Ｔd2，…と探索条件の情報から、以下の（式８）に従ってこのリンクのコストＴdを算出する。
【００７６】
【数８】
【００７７】
このとき、各回避地点について、当該回避地点がユーザに選択された場合、前述のように、各回避地点に対してはコストに反映させる回避項目が指定され、記憶装置１１に記憶されているため、選択された回避地点についてはその回避項目について遅れ時間が算出されることになる。例えば、△△丁目信号が選択された場合は、渋滞および、信号による遅れ時間を考慮するということが予め定められているものとする。
【００７８】
この各回避地点に対する回避項目の対応は、回避地点を抽出して回避地点リスト１１４が作成される際に指定される。回避地点の抽出処理は、予め各リンクについて遅れ時間を評価しておき、その遅れ時間が大きい地点（リンク）を抽出する。この時、リンク毎に近くにある施設を施設情報から検索して、その施設の種別毎に算出すべき遅れ時間の項目、即ち回避項目を予め決めておき、その回避項目の和集合から回避項目をきめる。例えば、ある「リンクＡ」の近傍に存在する施設の種別として、「信号」「学校」「駅」があり、「信号」について算出すべき遅れ時間の項目が「信号」「渋滞」の２つの回避項目であるとする。同様に「学校」については「歩行者」が、「駅」については「歩行者」と「渋滞」が回避項目とされていたとする。この時、この「リンクＡ」の地点名が「○×」であるとすれば、回避地点「○×」については、回避項目の和集合である「信号」「渋滞」「歩行者」が対応付けられることになる。そしてこれらの回避項目について算出された遅れ時間の和が所定の閾値以上となるリンクを抽出して、回避地点の地点名とこれに対応付けられた回避項目と共に、回避地点リスト１１４へ記録される。
【００７９】
ここで、ユーザが図１１（ｂ）に示すように渋滞，歩行者という回避項目および△△丁目信号という回避地点を選択した場合、リンク終端に△△丁目信号があるリンクについては上記の指定に基づきＴd＝Ｔd1＋Ｔd2とするが、それ以外のリンクでは、他の信号を回避しない選択をするということは、どんな信号でも避けたいわけではなく他の信号についてはドライバの感じる不快度に関与しないと考えられるため、Ｔd＝Ｔd1＋Ｔd3としてコストを算出する。
【００８０】
以上のようにして、図２のＳ２０７あるいはＳ２１１において候補リンクとなったリンク毎に図５の処理を実行して、コストを算出する。
【００８１】
図１２に本ナビゲーション装置による探索結果の表示例を示す。図１２（ａ）では、探索結果である快適ルートを太線で示している。また、この時、自車の現在位置１２１１の周辺のリンクの中で、コストの大きなリンクについて色を通常と変えて表示したり、マークを付けて表示しても良い。図１２（ａ）では、コストが特に大きいリンクを太点線で、コストがやや大きいリンクについては中太点線で表わしている。このような表示により、ユーザは遅れ時間が大きくスムーズな走行ができないリンクを把握し、回避して走行することができる。
【００８２】
また、経路探索処理中に図４に示したヒープテーブルを作成する際、各回避項目について算出した遅れ時間の値が所定の閾値より大きいリンクを記憶しておき、コストを構成する各回避項目，回避地点の遅れ時間の値の大小から、遅れ時間が大きい主要因を表示するようにしても良い。例えば、図１２（ａ）のリンク１２１３において、信号による遅れ時間があらかじめ規定した閾値より大きい、あるいは周囲の信号による遅れ時間より大きいなどの場合に、リンク１２１３の終点に対して、信号待ちが長くなる旨のメッセージ１２１４を表示する。さらに、図１２（ａ）のリンク１２１５において、渋滞による遅れ時間が大きい場合には、そのリンク１２１５において渋滞が発生している旨のメッセージ１２１６を表示することで、統計的に渋滞が発生する箇所を明示することができる。このような表示により、ユーザはスムーズに走行できない道路において、遅れ時間が大きい理由についても把握することができる。
【００８３】
また、図１２（ｂ）には、出発地１２２１から目的地１２２２に至る経路として、快適ルートだけでなく、時間優先ルート，距離優先ルートなどの探索条件でも探索を行い、地図上に複数経路１２２３〜１２２５を同時に表示する例を示す。この時、それぞれの経路の総遅れ時間，旅行時間，走行距離，通行料金を表示することにより、ユーザが経路の複数要素を比較することができ、ユーザはより希望に沿った経路を選択することができる。
【実施例２】
【００８４】
図７に、本発明に係る経路探索システムを、車載端末およびセンタ装置により構成した実施例の構成図を示す。図７に示すように、本実施形態における経路探索システムは、センタ装置７１と、インターネットや公衆回線網などを含む通信ネットワーク７２と、携帯電話や無線ＬＡＮなどの基地局７３と、車両７４に搭載された車載端末７５と、外部情報センタ７６と、を含んで構成される。車載端末７５の構成を、目的地までの誘導機能を有する通常のナビゲーション装置に含めても良い。
【００８５】
以下、センタ装置７１および車載端末７５の構成および機能について説明する。センタ装置７１は、通信ネットワーク７２に接続される通信装置（図示せず）を備えたコンピュータによって構成される。そして、そのコンピュータには、通信インターフェース部７１１，外部情報取得部７１２，プローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３，遅れ時間算出部７１５，コストデータベース７１６，端末要求受付部７１７，情報提供部７１８，コスト更新部７１９などを含んで構成される。
【００８６】
なお、センタ装置７１を構成するコンピュータは、少なくとも演算装置と半導体メモリやハードディスク装置などからなる記憶装置とを備える。そして、センタ装置７１を構成する各機能ブロックからの機能は、その演算処理装置が記憶装置に格納された所定のプログラムを実行することによって実現される。
【００８７】
通信インターフェース部７１１は、通信ネットワーク７２に対する通信制御を行うとともに、通信ネットワーク７２を介して車載端末７５との間でデータの送受信を行う。
【００８８】
外部情報取得部７１２は、車載端末７５から送信されたプローブデータを、通信インターフェース部７１１を介して取得する。ここでプローブデータとは、車両の走行軌跡データであり、位置情報（緯度経度などの座標）や時刻情報の他、走行速度，移動方向，ブレーキ情報等の車両情報を含んだ点列データである。外部情報取得部７１２で、取得した点列のプローブデータをリンク列あるいはリンク毎の所要時間や速度，渋滞度に変換しプローブデータベース７１３に蓄積する。
【００８９】
外部情報取得部７１２は、予め道路リンク単位の所要時間，速度，渋滞度に変換されたプローブデータを、通信インターフェース部７１１を介して取得する。この場合、道路リンク単位の情報は、車載端末７５あるいは通信ネットワーク７２を介して接続された交通情報センタで生成され、センタ装置７１に送信される。
【００９０】
また、外部情報取得部７１２は、通信インターフェース部７１１を介して、交通情報センタからリンク旅行時間などの交通情報を受信し、また天気情報センタなどの外部情報センタ７６からリンクのある地域の天候，気温などの情報を受信し、それぞれ交通情報データベース７１４２，走行環境情報データベース７１４３に格納する。外部情報取得部７１２においてプローブデータ，地図情報，交通情報，走行環境情報を取得する方法として、通信ネットワーク７２以外に記録メディアを介すこともある。
【００９１】
地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に格納される情報については、図２に示した地図情報データベース１１１，交通情報データベース１１２，走行環境情報データベース１１３、に格納される情報と同じ構成を持つため、説明を省略する。
【００９２】
遅れ時間算出部７１５は、実施例１における遅れ時間算出部１６と同等の機能を持ち、地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３にそれぞれ含まれる地図情報，交通情報，走行環境情報を用いてコストを算出する。コスト算出は、コスト更新部７１９からのコスト更新要求を受け取った場合に実行される。また、プローブデータベース７１３に含まれるプローブデータを用いてコストを算出しても良い。プローブデータを用いたコスト算出の詳細については後記する。
【００９３】
遅れ時間算出部７１５において算出されたコストは、コストデータベース７１６に蓄積される。図１０に、コストデータベース７１６に蓄積されるコスト情報の構成例を示す。図１０に示されるように、各リンクを示すリンクＩＤに対し、日種・時間帯毎に、各回避項目に対する遅れ時間が記録される。この時、複数の遅れ時間を足し合わせたコスト情報を、リンク毎に記録しても良い。
【００９４】
端末要求受付部７１７は、通信インターフェース部７１１を介して車載端末７５から送信される要求情報を受信する。この要求情報は、車載端末７５がセンタ装置７１に対してコストの提供を要求した情報であり、本実施形態に関する経路探索システムでは車載端末７５におけるコスト情報の更新時に利用される。さらに、端末要求受付部７１７は、この要求情報をコスト更新部７１９に送信する。
【００９５】
情報提供部７１８は、端末要求受付部７１７で受信した要求情報に応じて情報を提供するように機能し、要求情報にコスト情報の更新要求が含まれる場合はコストデータベース７１６から要求情報に一致したそのときの最新のコストを読み込み、通信インターフェース部７１１を介して車載端末７５に提供する。
【００９６】
コスト更新部７１９は、外部情報取得部７１２から外部情報の取得状況を、また端末要求受付部７１７から要求情報をそれぞれ取得してコスト更新を行うかタイミングか判定し、コスト更新を行うと判定した場合は遅れ時間算出部７１５にコスト更新要求を出す。コスト更新処理は、１）一定期間毎、２）プローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に格納される情報に一定件数以上の変更があった場合、３）車載端末７５から要求を受信した場合、などのタイミングで実行される。このようにすることで、より最新の情報を反映したコストを用いて経路探索を行い、よりスムーズに走行することができる。
【００９７】
一方、車両７４に搭載される車載端末７５は、本体部７５１，表示部７５２，携帯電話７５３，ＧＰＳ（Global Positioning System）受信機７５４などを含んで構成される。
【００９８】
本体部７５１は、演算処理部（図示せず），記憶装置７５５などを含んで構成されたコンピュータである。ここで記憶装置７５５は、半導体メモリやハードディスク装置などによって構成される。また、本体部７５１は、このほかにも入力装置として、種々のスイッチやボタン，タッチパネル，リモコン装置，音声マイクなどを、また、出力装置として音声スピーカなどを備えてもよい。表示部７５２については、実施例１における表示部１７と同等の機能を持つため、説明を省略する。
【００９９】
携帯電話７５３は、基地局７３との間で無線通信を行い、基地局７３および通信ネットワーク７２を介して、車載端末７５をセンタ装置７１にデータ通信可能なように接続する。また、ＧＰＳ受信機７５４は、図示しないＧＰＳ衛星からの電波を受信して、車両７４の現在位置を検出する。
【０１００】
また、本体部７５１は、通信インターフェース部７５１１，情報取得部７５１２，コストデータベース７５１３，地図情報データベース７５１４，位置情報取得部７５１５，経路探索部７５１６，入出力インターフェース部７５１７，探索条件設定部７５１８，要求情報送信部７５１９などを含んで構成される。これら本体部７５１の機能ブロックは、図示しない演算処理装置が記憶装置７５５に格納されている所定のプログラムを実行することによって実現される。ここで、先の実施例では快適ルート探索のためのコスト計算を遅れ時間算出部１６により行っていたが、この実施例では、予め各リンク毎の遅れ時間をセンタ装置で算出してコストデータベース７１６に格納しておき、これを元に更新した車載端末７５のコストデータベース７５１３の遅れ時間を用いている。
【０１０１】
通信インターフェース部７５１１は、携帯電話７５３に対する通信制御を行うとともに、基地局７３および通信ネットワーク７２を介してセンタ装置７１との間でデータの送受信を行う。
【０１０２】
情報取得部７５１２は、通信インターフェース部７５１１を介してセンタ装置７１から送信されたコスト情報を取得し、コストデータベース７５１３に保存する。コストの更新を表示部７５２に出力してユーザに通知することもある。
【０１０３】
位置情報取得部７５１５は、ＧＰＳ受信機７５４で検出した緯度経度や高度，時刻情報などのＧＰＳ情報を取得し、経路探索部７５１６に送信する。
【０１０４】
経路探索部７５１６，入出力インターフェース部７５１７，探索条件設定部７５１８については、それぞれ実施例１における経路探索部１５，入出力インターフェース部１３，探索条件設定部１４と同等の機能を持つため、説明を省略する。
【０１０５】
要求情報送信部７５１９は、通信インターフェース部７５１１を介してセンタ装置７１にコストデータの更新を確認して更新されていればそのコストデータを送るように要求する要求情報を送信する。ユーザが入出力インターフェース部７５１７を介してコストを要求する場合と、経路探索時の要求により経路探索部７５１６がコストを要求する場合がある。要求情報には、入出力インターフェース部７５１７を介して指定されたエリアや日時などが含まれる。
【０１０６】
次に、本実施形態における経路探索システムの快適ルート探索処理を、図８に示すフローチャートを用いて説明する。なお、図２に示す処理と同じステップについては、図２と共通の符号を用いて表わしている。ここで、Ｓ２０２，Ｓ２０３，Ｓ２０８〜Ｓ２１０，Ｓ２１２〜Ｓ２１７の各ステップは、図２における同名のステップと同じ処理を行うため説明を省略し、以下では、Ｓ８０１〜Ｓ８０５，Ｓ８０７，Ｓ８１１の説明を行う。
【０１０７】
この第２の実施例が第１の実施例と大きく異なる点は、第１の実施例では遅れ時間の計算をナビゲーション装置に備えた遅れ時間算出部１６で行っていたのに対し、第２の実施例では、遅れ時間の算出をセンタ装置７１に備えた遅れ時間算出部７１５で行い、車載端末７５ではその計算結果を反映したコストデータベースを受信して、経路探索の際にはこのコストデータベース７５１３から遅れ時間を参照してリンクのコストを算出している点である。このため、車載端末７５からセンタ装置７１に経路探索を行う探索エリアを送信し、センタ装置７１からその探索エリアについてコストデータを受信して、コストデータベース７５１３としている。
【０１０８】
ユーザが探索条件として快適ルートを選択した場合、図８の処理が開始され、車載端末７５は通信ネットワーク７２を介して、Ｓ２０２で決定した探索エリアをセンタ装置７１に送信する（Ｓ８０１）。
【０１０９】
センタ装置７１は、車載端末７５から送信された探索エリアを受信し（Ｓ８０２）、探索エリア内に含まれる全リンクについて、コストデータベース７１６内を検索する（Ｓ８０３）。この時、情報提供部７１８は、まず探索エリアに含まれるメッシュＩＤを全て抽出し、図１０に示すコストデータベース内のコスト情報について、メッシュＩＤと一致する全リンクのコスト情報を読み出す。
【０１１０】
センタ装置７１は、コストデータベース７１６から読みだした全コスト情報を送信し（Ｓ８０３）、車載端末７５は通信ネットワーク７２を介してこのコスト情報を受信する（Ｓ８０４）。受信したコスト情報は、情報取得部７５１２によりコストデータベース７５１３に格納される。
【０１１１】
Ｓ８０７は、Ｓ２０６で取得した出発地リンクのリンクＩＤを用いてコストデータベース７５１３内を検索してその遅れ時間を取得し、出発地リンクのコストを算出する。同様に、Ｓ８１１は、Ｓ２１０で選択された各候補リンクの遅れ時間をコストデータベース７５１３から取得して、第１の実施例におけるＳ５１０の処理と同様にしてそのリンクのコストを算出する。
【０１１２】
次に、センタ装置７１におけるコストデータベース７１６のコスト情報更新処理について、図９のフローチャートを用いて説明する。コスト情報更新処理はある一定周期（例えば５分毎）で実行される。
【０１１３】
まず、コスト更新部７１９が、外部情報取得部７１２から外部情報の取得状況を取得し、またあるいは端末要求受付部７１７から要求情報を取得してコスト更新を行うか判定する（Ｓ９００）。この時、前回のコスト更新から規定の時間以上が経過したか、外部情報の取得によりプローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に格納される情報に一定件数以上の変更があったか、あるいは端末からコスト更新要求があったか、などの判定条件の内のどれか１つ、あるいはいくつかが同時に成立した場合、コスト更新を行うものと判定され、そうでない場合はコスト更新を行わないと判定される。Ｓ９００の処理においてコスト更新を行わないと判定された場合（Ｓ９００：Ｎｏ）には、図９の処理を終了する。
【０１１４】
一方、コスト更新を行うと判定された場合（Ｓ９００：Ｙｅｓ）、まずセンタ装置７１がコスト更新を行うエリアを決定する（Ｓ９０１）。この更新エリアは、各種のデータベースについて一定件数以上の変更が行われていた場合、それに対応した更新を行うリンクを含むメッシュのメッシュＩＤなどにより指定される。また、前回のコスト更新から規定の時間以上が経過していた場合には、データが更新されたリンクを含むメッシュのメッシュＩＤなどにより指定される。あるいは端末からコスト更新要求があった場合には、そこで指定されたメッシュが更新エリアとなる。
【０１１５】
次に、遅れ時間算出部７１５が、更新エリア内に含まれる全リンクについて（Ｓ９０２）、対応するプローブデータ，地図情報，交通情報，走行環境情報を取得する（Ｓ９０３）。この時、プローブデータベース７１３，地図情報データベース７１４１，交通情報データベース７１４２，走行環境情報データベース７１４３に蓄積される情報を、更新リンクのリンクＩＤを用いて検索することにより、更新リンクに対応する情報を取得する。
【０１１６】
Ｓ９０３で取得した情報を用いて、各リンクにおける遅れ時間を算出する（Ｓ９０４）。このステップでは、図５のＳ５１０における処理と同様にして遅れ時間の算出処理をリンク毎に行う。ここでＳ９０４では、既に説明したように、Ｓ９０３でＳ５０９と同様にして取得した地図情報，交通情報，走行環境情報を用いて遅れ時間を算出して良いし、あるいはＳ９０３で取得したプローブデータを用いて遅れ時間を算出しても良い。プローブデータを用いた、渋滞，信号，歩行者による遅れ時間算出法を以下で説明する。
【０１１７】
渋滞による遅れ時間Ｔd1を求める場合は、実際の走行時間として、プローブデータより各リンクを通過するのに要した旅行時間Ｔprobeを用いて、以下の（式９）より算出する。
【０１１８】
【数９】
【０１１９】
信号による遅れ時間Ｔd2を求める場合は、信号の存在する交差点を含む道路区間（例えば、交差点の前後１００［ｍ］）を通過する際のプローブデータから、その交差点における平均停止時間を求め、信号による遅れ時間とする。
【０１２０】
歩行者による遅れ時間Ｔd3を求める場合は、歩行者が周囲に多いと考えられる施設の近辺を走行したプローブデータから、（式７）における、ｎ：歩行者数、ｌslow：歩行者１人に対して減速する距離、Ｖslow：徐行速度を推定し、（式７）に推定値を代入することにより歩行者による遅れ時間を算出する。
【０１２１】
このように、実際にリンクを走行したプローブデータを用いることにより、より正確な遅れ時間を算出することができ、より実状を反映した快適ルートを実現できる。
【０１２２】
図９の説明に戻る。遅れ時間算出部７１５によりＳ９０４で算出されたコストをコストデータベース７１６に保存する（Ｓ９０５）。またこの時、回避地点の抽出処理は，遅れ時間算出部７１５では算出した遅れ時間の和が閾値以上のリンクを抽出し、図示されていない回避地点リストを更新する。この回避地点リストはコストデータベース７１６に保存するようにしてもよい。更新エリア内に、上記処理を実行していない未更新のリンクが存在する場合は、上記処理をリンク毎に繰り返す（Ｓ９０６）。
【０１２３】
上記の実施形態では、遅れ時間情報をセンタ装置７１で算出し、車載端末７５に送信して経路探索を行うことにより快適ルートを算出する。ここで、上記車載端末７５に備わる経路探索部７５１６と同様の機能をセンタ装置７１に備え、センタ装置で探索した経路を車載端末７５に送信して表示しても良い。この時、探索した経路は、経路を構成するリンクのリンクＩＤの集合として送信される。
【符号の説明】
【０１２４】
１１ 記憶装置
１２，７５１５ 位置情報取得部
１３，７５１７ 入出力インターフェース部
１４，７５１８ 探索条件設定部
１５ 経路探索部
１６，７１５ 遅れ時間算出部
１７ 表示部
７１ センタ装置
７２ 通信ネットワーク
７３ 基地局
７５ 車載端末
７１１，７５１１ 通信インターフェース部
７１２ 外部情報取得部
７１３ プローブデータベース
７１６，７５１３ コストデータベース
７１７ 端末要求受付部
７１８ 情報提供部
７５１ 本体部
７５２ 表示部
７５４ ＧＰＳ受信機
７１４１，７５１４ 地図情報データベース
７１４２ 交通情報データベース
７１４３ 走行環境情報データベース
７５１２ 情報取得部
７５１６ 経路探索部
７５１９ 要求情報送信部
【特許請求の範囲】
【請求項１】
出発地および目的地の位置情報を受け付けて、出発地から目的地までの経路を探索する経路探索方法であって、
探索する経路において回避したい地点の入力を受け付け、
この地点における回避条件項目によるリンク毎の遅れ時間を算出し、
出発地から目的地までの経路を計算する際には、算出されたリンク毎の遅れ時間を反映したコストによるコスト最小経路を求める、
ことを特徴とする経路探索方法。
【請求項２】
前記回避条件項目は、渋滞，信号，歩行者の何れかを少なくとも含む交通状況の項目であることを特徴とする請求項１に記載の経路探索方法。
【請求項３】
入力された前記地点に対応した回避条件項目によるリンク毎の遅れ時間を算出する際には、各地点について、地点に対する前記交通状況の項目を求め、地点に対応するリンクについて、該当する交通状況の項目毎に求めた遅れ時間の和を算出することを特徴とする請求項２に記載の経路探索方法。
【請求項４】
計算した前記経路を、当該経路に含まれるリンク毎に算出された遅れ時間の大きさを表すマーク又は色を用いて表示することを特徴とする請求項１乃至３に記載の経路探索方法。
【請求項５】
出発地から目的地までの経路探索を行うナビゲーション装置であって、
探索する経路において回避したい地点の入力を受け付けるユーザ入力受付部と、
入力された地点における回避条件項目によるリンク毎の遅れ時間を算出する遅れ時間算出部と、
算出されたリンク毎の遅れ時間を反映したコストを用いて出発地から目的地までのコスト最小経路を計算する経路探索部と、
を備えることを特徴とするナビゲーション装置。
【請求項６】
前記ユーザ入力受付部では、前記回避条件項目として、渋滞，信号，歩行者の何れかを少なくとも含む交通状況の項目を受け付けることを特徴とする請求項５に記載のナビゲーション装置。
【請求項７】
前記遅れ時間算出部は、入力された各地点について、地点に対する前記交通状況の項目を求め、地点に対応するリンクについて、該当する交通状況の項目毎に求めた遅れ時間の和を算出することを特徴とする請求項６に記載のナビゲーション装置。
【請求項８】
前記ナビゲーション装置は表示部を備え、前記経路探索部において算出された経路に含まれるリンク毎に、算出された遅れ時間の大きさを表すマーク又は色を用いて前記経路を前記表示部に表示することを特徴とする請求項５乃至７に記載のナビゲーション装置。
【請求項１】
出発地および目的地の位置情報を受け付けて、出発地から目的地までの経路を探索する経路探索方法であって、
探索する経路において回避したい地点の入力を受け付け、
この地点における回避条件項目によるリンク毎の遅れ時間を算出し、
出発地から目的地までの経路を計算する際には、算出されたリンク毎の遅れ時間を反映したコストによるコスト最小経路を求める、
ことを特徴とする経路探索方法。
【請求項２】
前記回避条件項目は、渋滞，信号，歩行者の何れかを少なくとも含む交通状況の項目であることを特徴とする請求項１に記載の経路探索方法。
【請求項３】
入力された前記地点に対応した回避条件項目によるリンク毎の遅れ時間を算出する際には、各地点について、地点に対する前記交通状況の項目を求め、地点に対応するリンクについて、該当する交通状況の項目毎に求めた遅れ時間の和を算出することを特徴とする請求項２に記載の経路探索方法。
【請求項４】
計算した前記経路を、当該経路に含まれるリンク毎に算出された遅れ時間の大きさを表すマーク又は色を用いて表示することを特徴とする請求項１乃至３に記載の経路探索方法。
【請求項５】
出発地から目的地までの経路探索を行うナビゲーション装置であって、
探索する経路において回避したい地点の入力を受け付けるユーザ入力受付部と、
入力された地点における回避条件項目によるリンク毎の遅れ時間を算出する遅れ時間算出部と、
算出されたリンク毎の遅れ時間を反映したコストを用いて出発地から目的地までのコスト最小経路を計算する経路探索部と、
を備えることを特徴とするナビゲーション装置。
【請求項６】
前記ユーザ入力受付部では、前記回避条件項目として、渋滞，信号，歩行者の何れかを少なくとも含む交通状況の項目を受け付けることを特徴とする請求項５に記載のナビゲーション装置。
【請求項７】
前記遅れ時間算出部は、入力された各地点について、地点に対する前記交通状況の項目を求め、地点に対応するリンクについて、該当する交通状況の項目毎に求めた遅れ時間の和を算出することを特徴とする請求項６に記載のナビゲーション装置。
【請求項８】
前記ナビゲーション装置は表示部を備え、前記経路探索部において算出された経路に含まれるリンク毎に、算出された遅れ時間の大きさを表すマーク又は色を用いて前記経路を前記表示部に表示することを特徴とする請求項５乃至７に記載のナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−１２７７７０（Ｐ２０１２−１２７７７０Ａ）
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１０−２７８７３８（Ｐ２０１０−２７８７３８）
【出願日】平成２２年１２月１５日（２０１０．１２．１５）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願日】平成２２年１２月１５日（２０１０．１２．１５）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]