JP2014071063A - 経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラム - Google Patents

Abstract

【課題】ユーザに対してより適切な経路を探索することを可能とした経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラムを提供する。
【解決手段】出発地から目的地までの経路を構成する複数のリンク毎に、リンクが含まれる地域を特定し、地域毎に探索コストに影響を与える要素と該要素を含むリンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得するとともに、車両のリンクへの到達時刻を予測し、探索コストに影響を与える要素として到達時刻におけるリンクの交通状況を取得し、特定された地域と該地域に対応付けられた地域コスト算出条件と交通状況等の要素に基づいて算出された探索コストを用いて、出発地から目的地までの適合経路を探索条件毎に特定するように構成する。
【選択図】図９

Description

本発明は、出発地から目的地へと至る経路を探索する経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラムに関する。

近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。更に、かかるナビゲーション装置には、所望する目的地を入力すると、自車位置から目的地までの最適経路を探索する経路探索機能を備えており、探索された最適経路を案内経路として設定し、ディスプレイ画面に案内経路を表示するとともに、交差点に接近した場合等には音声による案内をすることによって、ユーザを所望の目的地まで確実に案内するようになっている。また、近年は携帯電話機、スマートフォン、ＰＤＡ（Personal Digital Assistant）、パーソナルコンピュータ等においても上記ナビゲーション装置と同様の機能を有するものがある。

また、上記経路探索機能では、出発地から目的地までの経路を探索する経路探索方法として一般的にダイクストラ法が用いられる。ここで、ダイクストラ法では、経路に含まれる各リンクや交差点に対応する各ノードに対してそれぞれ探索コスト（リンクコスト、交差点コスト）を算出し、算出された探索コストの加算値に基づいて最適な経路を特定する。また、探索コストの算出には、渋滞等の交通状況についても考慮される。しかし、リンクの交通状況は時刻毎によって異なる（例えば、午前中のみ渋滞するリンクもあれば、深夜のみ渋滞するリンクもある）ので、そのリンクを走行する時刻を特定しなければ、正確な交通状況を考慮した探索コストを算出することができない。そこで、特開２０１１−５３２２１号公報には、自車の現在位置周辺のエリアをメッシュ単位で分割し、各エリアの平均車速から自車のエリア毎の到達予想時刻を算出し、到達予想時刻における交通状況を用いてエリア内にあるリンクの探索コストを算出する技術について提案されている。また、特開２０１０−２７６３９６号公報には、現在地から目的地のエリアを、自車を中心とした同心円状のエリアに分割し、各エリア毎に異なる交通情報を用いて最適なルートを探索する技術について提案されている。

特開２０１１−５３２２１号公報（第５−７頁、図１、図２） 特開２０１０−２７６３９６号公報（第８−９頁、図３−７）

しかしながら、上記特許文献１及び特許文献２の技術では、リンク単位ではなくメッシュ単位或いは現在地からの直線距離で到達時刻を予測しているので、リンクへの到達時刻を正確に予測できない問題があった。その結果、リンクの探索コストについても正確に算出できなかった。

また、上記特許文献１及び特許文献２に記載された技術では、交通状況に対する地域性を考慮して探索コストを算出することができなかった。ここで、ユーザにとって適切な経路を探索する為には、地域性を考慮して探索コストを算出することは重要である。例えば、渋滞の規模が大きい地域では、他の地域よりもユーザは渋滞を避けた経路を好む傾向がある。一方、渋滞の規模が小さい地域では、ユーザは渋滞よりも他の要素（道路種別や車線数）等を重視する。しかしながら、上記特許文献１及び特許文献２の記載の技術では、交通状況に対する地域性を考慮しておらず、ユーザにとって最適な経路を探索できない場合があった。

本発明は前記従来における問題点を解消するためになされたものであり、移動体のリンク到達時点での交通状況を考慮したより正確な探索コストを算出することが可能となるとともに、交通状況に対する地域性（道路事情、交通事情、住民性等）についても考慮し、ユーザに対してより適切な経路を探索することを可能とした経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラムを提供することを目的とする。

前記目的を達成するため本願の請求項１に係る経路探索システム（１）は、出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得手段（１３）と、前記リンク情報取得手段により取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測手段（１３）と、前記到達時刻予測手段により予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得手段（１３）と、前記候補リンクが含まれる地域を特定する地域特定手段（１３）と、地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得手段（１３）と、前記地域特定手段によって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得手段により取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索手段（１３）と、を有することを特徴とする。
尚、「移動体」としては、自動車や自転車等の車両以外にユーザ（人）も含む。

また、請求項２に係る経路探索システム（１）は、請求項１に記載の経路探索システムであって、前記交通情報は、センタから取得した現時点の交通状況を示す現在交通情報と、前記現在交通情報の履歴を統計した統計情報である統計交通情報と、前記現在交通情報と前記統計交通情報に基づいて所定時間経過後の交通状況を予測した予測交通情報とを含み、前記交通情報取得手段（１３）は、前記現在交通情報と前記統計交通情報と前記予測交通情報の少なくとも一以上を前記交通情報として取得することを特徴とする。

また、請求項３に係る経路探索システム（１）は、請求項２に記載の経路探索システムであって、前記到達時刻予測手段（１３）により予測された前記到達時刻に基づいて、前記候補リンク毎に前記現在交通情報と前記統計交通情報と前記予測交通情報の利用に係る優先順位を設定する優先順位設定手段（１３）を有し、前記経路探索手段（１３）は、前記交通情報取得手段（１３）により取得された前記交通情報の内、最も優先順位の高い前記交通情報を用いて前記探索コストを算出することを特徴とする。

また、請求項４に係る経路探索システム（１）は、請求項３に記載の経路探索システムであって、前記優先順位設定手段（１３）は、前記到達時刻予測手段（１３）により予測された前記到達時刻と現在時刻との差異に基づいて、前記優先順位を設定することを特徴とする。

また、請求項５に係る経路探索システム（１）は、請求項４に記載の経路探索システムであって、前記優先順位設定手段（１３）は、前記到達時刻予測手段（１３）により予測された前記到達時刻と現在時刻との差異が第１基準値未満である場合に、前記現在交通情報を最も高い優先順位に設定し、前記到達時刻予測手段により予測された前記到達時刻と現在時刻との差異が前記第１基準値以上で第２基準値未満である場合に、前記予測交通情報を最も高い優先順位に設定し、前記到達時刻予測手段により予測された前記到達時刻と現在時刻との差異が前記第２基準値以上である場合に、前記統計交通情報を最も高い優先順位に設定することを特徴とする。

また、請求項６に係る経路探索システム（１）は、請求項１乃至請求項５のいずれかに記載の経路探索システムであって、前記探索コストは、該候補リンクのリンク長に該候補リンクの交通状況に基づいた係数を乗じることによって算出され、前記探索コストの算出条件は、交通状況毎の前記係数の値を規定することを特徴とする。

また、請求項７に係る経路探索システム（１）は、請求項１乃至請求項６のいずれかに記載の経路探索システムであって、前記地域特定手段（１３）は、前記探索コストの算出対象となる前記候補リンクが複数の地域に跨る場合には、該候補リンクの開始点が含まれる地域を、該候補リンクが含まれる地域として特定することを特徴とする。
尚、「候補リンクの開始点」とは、出発地から出発した車両等が該候補リンクを走行する場合に、候補リンクの走行を開始する地点となる。

また、請求項８に係る経路探索装置（１）は、出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得手段（１３）と、前記リンク情報取得手段により取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測手段（１３）と、前記到達時刻予測手段により予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得手段（１３）と、前記候補リンクが含まれる地域を特定する地域特定手段（１３）と、地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得手段（１３）と、前記地域特定手段によって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得手段により取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索手段（１３）と、を有することを特徴とする。

また、請求項９に係る経路探索方法は、出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得ステップと、前記リンク情報取得ステップにより取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測ステップと、前記到達時刻予測ステップにより予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得ステップと、前記候補リンクが含まれる地域を特定する地域特定ステップと、地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得ステップと、前記地域特定ステップによって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得ステップにより取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索ステップと、を有することを特徴とする。

更に、請求項１０に係るコンピュータプログラムは、コンピュータに、出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得機能と、前記リンク情報取得機能により取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測機能と、前記到達時刻予測機能により予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得機能と、前記候補リンクが含まれる地域を特定する地域特定機能と、地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得機能と、前記地域特定機能によって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得機能により取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索機能と、を実行させることを特徴とする。

前記構成を有する請求項１に記載の経路探索システムによれば、出発地から目的地までの経路の探索を行う際に、リンク単位で移動体の到達時刻を予測し、予測された到達時刻の交通状況を用いて探索コストを算出するので、リンク毎の到達時点の交通状況を考慮したより正確な探索コストを算出することが可能となる。また、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎に探索コストの算出条件を設定するので、地域性に沿ったユーザに対してより適切な経路を探索することが可能となる。

また、請求項２に記載の経路探索システムによれば、センタから取得した現時点の交通状況を示す現在交通情報と、現在交通情報の履歴を統計した統計情報である統計交通情報と、現在交通情報と統計交通情報に基づいて所定時間経過後の交通状況を予測した予測交通情報に基づいてリンクの交通状況を特定するので、現時点からの時間経過に関わらず所定時刻におけるリンクの交通状況を正確に特定することが可能となる。

また、請求項３に記載の経路探索システムによれば、候補リンクの到達時刻に基づいて、候補リンク毎に現在交通情報と統計交通情報と予測交通情報の利用に係る優先順位を設定し、取得された交通情報の内、最も優先順位の高い交通情報を用いて探索コストを算出するので、リンク毎の到達時刻に応じて交通状況を特定するのに適切な交通情報を選択することが可能であり、到達時刻におけるリンクの交通状況を正確に特定することが可能となる。

また、請求項４に記載の経路探索システムによれば、候補リンクへの到達時刻と現在時刻との差異に基づいて、優先順位を設定するので、リンク毎の到達時刻に応じて交通状況を特定するのに適切な交通情報を選択することが可能であり、到達時刻におけるリンクの交通状況を正確に特定することが可能となる。

また、請求項５に記載の経路探索システムによれば、候補リンクへの到達時刻と現在時刻との差異が第１基準値未満である場合に現在交通情報を最も高い優先順位に設定し、第１基準値以上で第２基準値未満である場合に予測交通情報を最も高い優先順位に設定し、第２基準値以上である場合に統計交通情報を最も高い優先順位に設定するので、リンク毎の到達時刻に応じて交通状況を特定するのに適切な交通情報を選択することが可能であり、到達時刻におけるリンクの交通状況を正確に特定することが可能となる。

また、請求項６に記載の経路探索システムによれば、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎にリンクコストを算出する際に用いる係数を設定するので、リンクの渋滞度等の交通状況に基づいて適切なリンクコストを算出することが可能となる。

また、請求項７に記載の経路探索システムによれば、探索コストの算出対象となるリンクが複数の地域に跨る場合には、該リンクの開始点が含まれる地域を、該リンクが含まれる地域として特定するので、探索コストの算出対象となるリンクに対して最も影響のある地域を適切に特定することが可能となる。

また、請求項８に記載の経路探索装置によれば、出発地から目的地までの経路の探索を行う際に、リンク単位で移動体の到達時刻を予測し、予測された到達時刻の交通状況を用いて探索コストを算出するので、リンク毎の到達時点の交通状況を考慮したより正確な探索コストを算出することが可能となる。また、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎に探索コストの算出条件を設定するので、地域性に沿ったユーザに対してより適切な経路を探索することが可能となる。

また、請求項９に記載の経路探索方法によれば、出発地から目的地までの経路の探索を行う際に、リンク単位で移動体の到達時刻を予測し、予測された到達時刻の交通状況を用いて探索コストを算出するので、リンク毎の到達時点の交通状況を考慮したより正確な探索コストを算出することが可能となる。また、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎に探索コストの算出条件を設定するので、地域性に沿ったユーザに対してより適切な経路を探索することが可能となる。

更に、請求項１０に記載のコンピュータプログラムによれば、出発地から目的地までの経路の探索を行わせる際に、リンク単位で移動体の到達時刻を予測させ、予測された到達時刻の交通状況を用いて探索コストを算出させるので、リンク毎の到達時点の交通状況を考慮したより正確な探索コストを算出させることが可能となる。また、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎に探索コストの算出条件を設定させるので、地域性に沿ったユーザに対してより適切な経路を探索させることが可能となる。

本実施形態に係るナビゲーション装置の構成を示したブロック図である。 『推奨』の探索条件におけるコスト係数の設定基準と実際に設定されるコスト係数の一例を示した図である。 『一般優先』の探索条件におけるコスト係数の設定基準と実際に設定されるコスト係数の一例を示した図である。 『距離優先』の探索条件におけるコスト係数の設定基準と実際に設定されるコスト係数の一例を示した図である。 現在交通情報の一例を示した図である。 統計交通情報の一例を示した図である。 予測交通情報の一例を示した図である。 本実施形態に係る経路探索処理プログラムのフローチャートである。 タイムスライスデータの一例を示した図である。 出発地交差点から目的地交差点までの適合経路の候補を示した図である。 交差点リストの一例を示した図である。 交差点リストに基づく適合経路の特定処理の具体例について説明した図である。 コスト算出処理のサブ処理プログラムのフローチャートである。 リンク毎の予測される到達時刻を示した図である。

以下、本発明に係る経路探索システム及び経路探索装置をナビゲーション装置に具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。

図１に示すように本実施形態に係るナビゲーション装置１は、ナビゲーション装置１が搭載された車両の現在位置を検出する現在位置検出部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ１３と、ユーザからの操作を受け付ける操作部１４と、ユーザに対して車両周辺の地図や後述の経路探索処理によって探索された経路に関する経路情報等を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、記憶媒体であるＤＶＤを読み取るＤＶＤドライブ１７と、プローブセンタやＶＩＣＳ（登録商標：Vehicle Information and Communication System）センタ等の情報センタとの間で通信を行う通信モジュール１８と、から構成されている。

以下に、ナビゲーション装置１を構成する各構成要素について順に説明する。
現在位置検出部１１は、ＧＰＳ２１、車速センサ２２、ステアリングセンサ２３、ジャイロセンサ２４等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ２２は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションＥＣＵ１３に出力する。そして、ナビゲーションＥＣＵ１３は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記４種類のセンサをナビゲーション装置１が全て備える必要はなく、これらの内の１又は複数種類のセンサのみをナビゲーション装置１が備える構成としても良い。

また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ３１や交通情報ＤＢ３２や所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、データ記録部１２をハードディスクの代わりにメモリーカードやＣＤやＤＶＤ等の光ディスクにより構成しても良い。

ここで、地図情報ＤＢ３１は、例えば、道路（リンク）に関するリンクデータ３３、ノード点に関するノードデータ３４、経路探索処理に用いられる探索データ３５、施設に関する施設データ、地図を表示するための地図表示データ、各交差点に関する交差点データ、地点を検索するための検索データ等が記憶された記憶手段である。

また、リンクデータ３３としては、道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。

また、ノードデータ３４としては、実際の道路の分岐点（交差点、Ｔ字路等も含む）や各道路に曲率半径等に応じて所定の距離毎に設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接するノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。

また、探索データ３５としては、後述のように出発地（例えば車両の現在位置）から設定された目的地までの経路を探索する経路探索処理に使用される各種データについて記録されている。具体的には、交差点に対する経路として適正の程度を数値化したコスト（以下、交差点コストという）や道路を構成するリンクに対する経路として適正の程度を数値化したコスト（以下、リンクコストという）等の探索コストを算出する為に使用するコスト算出データが記憶されている。

ここで、交差点コストは、探索コストの算出対象となる経路に含まれる交差点に対応するノード毎に設定され、信号機の有無、交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）等によってその値が算出される。
また、リンクコストは、探索コストの算出対象となる経路に含まれるリンク毎に設定され、リンク長を基本にして、該リンクの道路属性や道路種別、道路幅、車線数、交通状況等を考慮して算出される。

ここで、本実施形態に係るナビゲーション装置１では、複数の探索条件に基づいて探索条件毎に該探索条件に適合する経路（以下、適合経路という）をそれぞれ特定し、各探索条件で特定された複数本の適合経路から利用者の希望する一の経路を最終的に案内経路として設定する構成を有する。具体的な探索条件としては、目的地までの所要時間が短くなることを優先するとともに走行し易さや走行に係る費用等についても考慮した『推奨』と、目的地まで有料道路を走行することを優先する『有料道路優先』と、目的地まで一般道路を走行することを優先する『一般優先』と、目的地までの走行距離が短くなることを優先した『距離優先』の４種類の探索条件からなる。

また、探索条件毎且つ地域毎に上記リンクコスト及び交差点コストの算出条件（以下、コスト算出条件という）は異なっている。以下にリンクコスト及び交差点コストのコスト算出条件について説明する。尚、以下の説明では、特にリンクコストを例に挙げて説明することとする。

リンクコストは、算出対象となるリンクのリンク長に対して、該リンクが含む車線数、道路種別、交通状況（例えば渋滞度）等の探索コストに影響を与える様々な要素毎に設定された係数（以下、コスト係数という）を乗じることによって算出される。従って、リンクコストのコスト算出条件は、要素毎にどのようにコスト係数を設定するかを定める条件となる。そして、このコスト係数は、探索条件や地域性（より具体的には道路事情、交通事情、住民性等）を考慮して、探索条件毎且つ地域毎に設定される。例えば、『推奨』ではリンク長を基本として、車線数、道路種別、交通状況等の旅行時間に影響を与える要素を考慮し、より旅行時間が短くなるリンクが低いコストとなるようにコスト係数を設定する。更に、走行に係る費用や走行し易さ等についても考慮する。但し、地域によっては、費用が生じても有料道路を一般道路より優先した方が良い地域もあるし、渋滞区間を走行することを特にユーザが嫌う地域もある。ここで、図２は探索条件の一つである『推奨』におけるコスト係数の設定基準と実際に設定されるコスト係数（地域コスト算出条件）の一例を示した図である。

図２に示すように、探索条件『推奨』では、地図データに含まれる地域（本実施形態では日本）を所謂８地方区分により８つの地域に区分している。そして、８つの地域毎に地域性（より具体的には道路事情、交通事情、住民性等）を考慮してコスト係数の設定基準を設定し、その基準に基づきコスト係数を設定している。
例えば、北海道地区では、一般道が比較的空いていて走り易く、ユーザは一般道を好んで走行する傾向が高いので、有料道路のコスト係数は他の地域より高めに設定される。更に、北海道地区では、法定速度の速い（例えば５０ｋｍ／ｈ以上）の道路を好んで走行するユーザが多いので、法定速度が速い道路のコスト係数は他の地域より低めに設定し、法定速度が遅い道路のコスト係数は他の地域より高めに設定する。
また、東北地区では、短い区間であっても有料道路を利用しやすい環境にあることから、有料道路（特に３０ｋｍ未満の短い区間）のコスト係数は他の地域より低めに設定される。更に、東北地区では、車線数の多い大型道路を好んで走行するユーザが多いので、車線数の多い道路のコスト係数は他の地域より低めに設定し、車線数の少ない道路のコスト係数は他の地域より高めに設定する。
また、関東地区では、一般道が非常に混雑して走り難く、ユーザは有料道路を好んで走行する傾向が高いので、有料道路のコスト係数は他の地域より低めに設定される。更に、関東地区では、発生する渋滞の規模が大きく、渋滞を回避して走行するユーザが多いので、渋滞度が低い道路のコスト係数は他の地域より低めに設定し、渋滞度が高い道路のコスト係数は他の地域より高めに設定する。
尚、他の地区についても同様に、図２に示すコスト係数の設定基準に基づいてコスト係数が設定されている。

また、『一般優先』では上記『推奨』の算出方法に加えて有料道路の道路種別であるリンクのリンクコストを高くなるようにコスト係数を設定する。但し、地域によっては、有料道路を一切走行しない条件とすると目的地までの経路が探索できない地域もある。ここで、図３は探索条件の一つである『一般優先』におけるコスト係数の設定基準と実際に設定されるコスト係数（地域コスト算出条件）の一例を示した図である。

図３に示すように、探索条件『一般優先』では、地図データに含まれる地域（本実施形態では日本）を所謂８地方区分により８つの地域に区分している。そして、８つの地域毎に地域性（より具体的には道路事情、交通事情、住民性等）を考慮してコスト係数の設定基準を設定し、その基準に基づきコスト係数を設定している。
例えば、北海道地区では、有料道路を走行しないこととすると、離島や本州などを目的地とした場合に目的地に到達できない場合があるので、フェリーを利用する経路のみはコスト係数を設定する。更に、北海道地区では、法定速度の速い（例えば５０ｋｍ／ｈ以上）の道路を好んで走行するユーザが多いので、法定速度が速い道路のコスト係数は他の地域より低めに設定し、法定速度が遅い道路のコスト係数は他の地域より高めに設定する。
また、東北地区では、同じく有料道路を走行しないこととすると、北海道などを目的地とした場合に目的地に到達できない場合があるので、フェリーを利用する経路のみはコスト係数を設定する。更に、東北地区では、車線数の多い大型道路を好んで走行するユーザが多いので、車線数の多い道路のコスト係数は他の地域より低めに設定し、車線数の少ない道路のコスト係数は他の地域より高めに設定する。
また、関東地区では、フェリーを利用しなくでも目的地に到着することが可能であるので、フェリーを含めた有料道路は一切利用しないようにコスト係数が設定される。更に、関東地区では、発生する渋滞の規模が大きく、渋滞を回避して走行するユーザが多いので、渋滞度が低い道路のコスト係数は他の地域より低めに設定し、渋滞度が高い道路のコスト係数は他の地域より高めに設定する。
尚、他の地区についても同様に、図３に示すコスト係数の設定基準に基づいてコスト係数が設定されている。

更に、図４は探索条件の一つである『距離優先』におけるコスト係数の設定基準と実際に設定されるコスト係数（地域コスト算出条件）の一例を示した図である。

図４に示すように、探索条件『距離優先』では、地図データに含まれる地域（本実施形態では日本）を１の地域に区分している。即ち、『距離優先』では道路種別や有料か無料かに関わらず、目的地までの距離が最も短くなる経路を探索する必要があるので、地域毎の地域性（より具体的には道路事情、交通事情、住民性等）の違いを考慮する必要が無い。従って、コスト算出条件は、地図データに含まれる全ての地域で同一の条件を規定する。具体的には、リンクに含まれる要素に関わらず、コスト係数を“１”とし、リンク長のみに基づいてリンクコストが算出される。

尚、説明は省略するが『有料道路優先』の探索条件についても同様に、地域毎に地域性（より具体的には道路事情、交通事情、住民性等）を考慮してコスト係数の設定基準を設定し、その基準に基づきコスト係数を設定している。

そして、ナビゲーションＥＣＵ１３は、探索条件毎且つ地域毎に設定されたコスト係数（地域コスト算出条件）に基づいて算出されたリンクコストや交差点コスト等の探索コストに基づき、ダイクストラ法を用いて経路探索を行う。尚、ダイクストラ法による経路探索処理の詳細については後述する。

尚、本実施形態では地図データに含まれる地域（本実施形態では日本）を８地方区分により区分しているが、その区分単位は都道府県単位や市区町村単位やメッシュ単位で区分しても良い。また、探索条件毎に区分する基準を変更しても良い（例えば、『推奨』では８地方区分により区分し、『一般優先』では都道府県単位で区分する）。また、探索データ３５は、地図データの一部ではなく後述の経路探索処理プログラムのプログラム上で記憶させる構成としても良い。

一方、地図情報ＤＢ３１とともにデータ記録部１２に格納される交通情報ＤＢ３２は、外部のＶＩＣＳセンタやプローブセンタから取得した現時点の交通状況を示す現在交通情報３６、現在交通情報３６の履歴を統計した統計情報である統計交通情報３７、現在交通情報３６と統計交通情報３７に基づいて所定時間（例えば６０分）経過後の交通状況を予測した予測交通情報３８等が記憶された記憶手段である。

ここで、現在交通情報３６は、ＶＩＣＳセンタから通信により取得したＶＩＣＳ情報やプローブセンタから通信により取得したプローブ情報が該当し、図５に示すように情報を取得した現時点での渋滞が発生している区間や、事故、工事等が発生している区間を特定する情報である。ここで、現在交通情報３６は、現時点及び現時点から近い将来（例えば６０分以内）について、他の交通情報に比べて情報の信頼性が高い特徴がある。

また、統計交通情報３７は、ＶＩＣＳセンタ、プローブセンタ、その他の外部センタ又はナビゲーション装置１が、所定間隔（例えば１か月や１年）毎に格納された現在交通情報３６に対して統計処理を行うことにより、生成する交通情報である。具体的には、図６に示すようにリンク毎、日時（又は曜日）毎に想定される渋滞度を特定した情報である。渋滞度の特定方法としては、例えば、統計期間において『渋滞』と８０％以上判定された時間帯については渋滞度を『渋滞』と特定し、『渋滞』又は『混雑』と５０％以上判定された時間帯は渋滞度を『混雑』と特定し、それ以外の時間帯については『空き』と特定することができる。ここで、統計交通情報３７は、現時点から遠い将来（例えば１２０分以降）について、他の交通情報に比べて情報の信頼性が高い特徴がある。

また、予測交通情報３８は、ＶＩＣＳセンタ、プローブセンタ、その他の外部センタ又はナビゲーション装置１が、現在交通情報３６を統計交通情報３７に基づいて修正することにより生成する交通情報であり、現時点（例えば経路探索時点）から所定時間経過後（例えば０〜１８０分後）の交通状況（特にリンクの渋滞度）を、統計交通情報３７に比べてより正確に予測した情報である。具体的には、図７に示すようにリンク毎に、現時点から比較的短時間経過後までの渋滞度を一定時間毎に区切って特定した情報である。尚、予測交通情報は後述の経路探索処理プログラムの実行時又は所定間隔（例えば３時間）毎に生成される。ここで、予測交通情報３８は、現時点から一定期間経過した将来（例えば６０〜１２０分経過）について、他の交通情報に比べて情報の信頼性が高い特徴がある。

一方、ナビゲーションＥＣＵ（エレクトロニック・コントロール・ユニット）１３は、ナビゲーション装置１の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ、交差点リスト、タイムスライスデータ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の経路探索処理プログラム（図８参照）等が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置を備えている。尚、ナビゲーションＥＣＵ１３は、処理アルゴリズムとしての各種手段を構成する。例えば、リンク情報取得手段は、出発地から目的地まで移動体（例えば車両）が移動する為の経路の候補を構成するリンク（候補リンク）に関するリンク情報を取得する。到達時刻予測手段は、リンク情報取得手段により取得したリンク情報に基づいて、候補リンクへの移動体の到達時刻を予測する。交通情報取得手段は、到達時刻予測手段により予測された到達時刻に基づいて、該到達時刻における候補リンクの交通状況を示す交通情報を取得する。地域特定手段は、候補リンクが含まれる地域を特定する。算出条件取得手段は、地域毎に、探索コストに影響を与える交通状況と該交通状況にある候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する。経路探索手段は、地域特定手段によって特定された地域と該地域に対応付けられた地域コスト算出条件と交通情報取得手段により取得した交通情報とに基づいて算出された探索コストを用いて、出発地から目的地までの経路を探索する。優先順位設定手段は、到達時刻予測手段により予測された到達時刻に基づいて、候補リンク毎に現在交通情報と統計交通情報と予測交通情報の利用に係る優先順位を設定する。

操作部１４は、走行開始地点としての出発地、走行終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーションＥＣＵ１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部１４は液晶ディスプレイ１５の前面に設けたタッチパネルによって構成することもできる。また、マイクと音声認識装置によって構成することもできる。

また、液晶ディスプレイ１５には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの案内経路、案内経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。
また、ナビゲーションＥＣＵ１３が後述の経路探索処理を行った場合には、探索結果に基づいて複数の探索条件毎に特定された適合経路について表示される。また、適合経路が高速道路などの有料道路を走行する場合には、走行に必要となる料金についても併せて表示される。そして、ユーザは表示された複数の適合経路の内から、案内経路とする経路を選択する。

また、スピーカ１６は、ナビゲーションＥＣＵ１３からの指示に基づいて案内経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。

また、ＤＶＤドライブ１７は、ＤＶＤやＣＤ等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、地図情報ＤＢ３１の更新等が行われる。

また、通信モジュール１８は、交通情報センタ、例えば、ＶＩＣＳセンタやプローブセンタ等から送信された前述の現在交通情報３６、統計交通情報３７、予測交通情報３８等を受信する為の通信装置であり、例えば携帯電話機やＤＣＭが該当する。

続いて、上記構成を有する本実施形態に係るナビゲーション装置１においてＣＰＵ４１が実行する経路探索処理プログラムについて図８に基づき説明する。図８は本実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムはナビゲーション装置１において経路探索を行う為の所定の操作（例えば、目的地の設定操作）を受け付けた際に実行され、出発地から目的地までの適合経路を、ダイクストラ法を用いて探索するプログラムである。また、経路探索処理プログラムは探索条件毎に繰り返し実行され、探索条件毎に一の適合経路が特定される。即ち、本実施形態では『推奨』と『有料道路優先』と『一般優先』と『距離優先』の４種類の探索条件により経路探索を行うので、計４回実行されることとなる。また、以下の実施例の説明では、説明の簡略化の為に探索コストとしてリンクコストのみを考慮することとし、交差点コストやその他のコストについては考慮しないこととする。尚、以下の図８及び図１３にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。

先ず、経路探索処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、経路探索処理に用いるタイムスライスデータを取得する。ここで、タイムスライスデータは、現在時刻（即ち車両が出発地を出発する出発時刻）から所定時間（例えば３時間）経過後までの周辺エリアの交通状況を、所定時間毎（例えば１５分毎）に予測（特定）したデータである。そして、タイムスライスデータは経路探索処理の開始時点、又はＡＣＣがオンされている状態において所定間隔（例えば１５分毎）で作成される。尚、前記Ｓ１の処理については探索条件毎に行う必要はなく、一旦取得されたタイムスライスデータは全ての探索条件の経路探索処理に用いることが可能である。

以下に、図９を用いてタイムスライスデータの詳細について説明する。尚、図９は特に車両が９：００に出発地を出発する場合において取得されるタイムスライスデータを示した図である。図９に示すように、タイムスライスデータは、出発地から目的地までの経路探索の対象となるエリア（メッシュ単位で区分）を対象として作成される。そして、エリアに含まれる全てのリンクについての交通状況（より具体的には渋滞度）を、所定時間毎（例えば１５分毎）に予測（特定）する。例えば１５分毎の交通状況を予測（特定）するタイムスライスデータでは、図９に示すように９：００〜１２：００まで１５分毎に計１２個のデータが作成されることとなる。

また、タイムスライスデータにおいて予測（特定）される交通状況は、ナビゲーション装置１が有する、又はＶＩＣＳセンタ等の外部センタから取得された現在交通情報３６、統計交通情報３７、予測交通情報３８のいずれかの交通情報に基づいて予測（特定）される。そして、いずれの交通情報を用いるかは、出発時刻からの経過時間毎に設定された優先順位に基づいて、タイムスライスデータの作成対象となる時刻毎に決定される。具体的には、出発時刻（現在時刻）からの経過時間が６０分未満までは、現在交通情報３６が最も高く、予測交通情報３８、統計交通情報３７の順に優先順位が設定されている。即ち、現在交通情報３６が取得されたリンクでは現在交通情報３６に基づいて交通状況が特定される。また、現在交通情報３６の取得できないリンクについては、該当時間帯の予測交通情報３８（例えば９：１５〜９：３０のタイムスライスデータでは９：１５〜９：３０を含む時間帯の交通状況を予測した予測交通情報（図７））に基づいて交通状況が特定される。更に、現在交通情報３６も該当時間帯の予測交通情報３８も取得できないリンクについては、該当時間帯の統計交通情報３７（例えば９：１５〜９：３０のタイムスライスデータでは９：１５〜９：３０を含む時間帯の交通状況を予測した統計交通情報（図６））に基づいて交通状況が特定される。

同様にして、出発時刻（現在時刻）からの経過時間が６０分以上１２０分未満までは、予測交通情報３８が最も高く、統計交通情報３７、現在交通情報３６の順に優先順位が設定されている。即ち、該当時間帯の予測交通情報３８（例えば１０：１５〜１０：３０のタイムスライスデータでは１０：１５〜１０：３０を含む時間帯の交通状況を予測した予測交通情報（図７））が取得されたリンクでは予測交通情報３８に基づいて交通状況が特定される。また、該当時間帯の予測交通情報３８の取得できないリンクについては、該当時間帯の統計交通情報３７（例えば１０：１５〜１０：３０のタイムスライスデータでは１０：１５〜１０：３０を含む時間帯の交通状況を予測した統計交通情報（図６））に基づいて交通状況が特定される。更に、該当時間帯の統計交通情報３７も予測交通情報３８も取得できないリンクについては、現在交通情報３６に基づいて交通状況が特定される。

また、出発時刻（現在時刻）からの経過時間が１２０分以上では、統計交通情報３７が最も高く、現在交通情報３６、予測交通情報３８の順に優先順位が設定されている。即ち、該当時間帯の統計交通情報３７（例えば１１：１５〜１１：３０のタイムスライスデータでは１１：１５〜１１：３０を含む時間帯の交通状況を予測した統計交通情報（図６））が取得されたリンクでは統計交通情報３７に基づいて交通状況が特定される。また、該当時間帯の統計交通情報３７の取得できないリンクについては、現在交通情報３６に基づいて交通状況が特定される。更に、該当時間帯の統計交通情報３７も現在交通情報３６も取得できないリンクについては、該当時間帯の予測交通情報３８（例えば１１：１５〜１１：３０のタイムスライスデータでは１１：１５〜１１：３０を含む時間帯の交通状況を予測した予測交通情報（図７）に基づいて交通状況が特定される。

また、タイムスライスデータには、エリアに含まれる各リンクの旅行時間についても記憶される。具体的には、上述した各交通情報によって特定された交通状況や道路種別に基づいて、リンク走行時の車両の車速を推定し、推定された車速とリンク長とに基づいて旅行時間を算出する。尚、前記したようにタイムスライスデータは所定時間毎（例えば１５分毎）に区分されており、時刻毎に予測（特定）される交通状況が異なるので、リンクの旅行時間についても所定時間毎に区分されて異なる値が記憶される。

次に、Ｓ２においてＣＰＵ４１は、出発地交差点、目的地交差点及び地図情報ＤＢ３１に記憶された地図情報に基づいて、交差点リストを作成し、作成された交差点リストをＲＡＭ４２等の記憶媒体に記憶する。更に、作成された交差点リストの初期化についても行う。尚、出発地交差点は出発地（例えば車両の現在位置）に対応する交差点（例えば出発地から最も近い位置にある交差点）であり、目的地交差点は設定された目的地に対応する交差点（例えば目的地から最も近い位置にある交差点）である。

ここで、交差点リストは、出発地交差点から目的地交差点まで至る適合経路の候補を接続する交差点（出発地交差点と目的地交差点を含む）のリストである。また、交差点リストには、リストアップされた交差点毎に、出発地交差点から該交差点までの探索コストの最小加算値を示すコスト値Ｔと、コスト値Ｔを実現する場合に直前に通過する交差点である直前交差点と、中心交差点の設定候補を示す候補フラグとが対応付けられている。

以下の説明では、図１０に示す出発地交差点Ａから目的地交差点Ｉまでの経路探索処理を行う場合を具体例に挙げて説明することとする。図１０に示す出発地交差点Ａから目的地交差点Ｉまでの経路探索処理を行う場合には、出発地交差点Ａから目的地交差点Ｉまでの適合経路を構成し得る各リンクを接続する９つの交差点Ａ〜Ｉがリストアップされた交差点リストが作成される（図１１参照）。

また、前記Ｓ２で実行される交差点リストの初期化処理では、図１１に示すようにリストアップされた全交差点に対応付けられたコスト値Ｔが無限大に設定され、直前交差点は対応付けず、候補フラグは“ＯＦＦ（０）”に設定される。

次に、Ｓ３においてＣＰＵ４１は、出発地交差点に対する初期化処理を行う。具体的には、交差点リストの出発地交差点Ａに対応付けられたコスト値Ｔを０に設定し、候補フラグを“ＯＮ（１）”に設定する。

続いて、Ｓ４においてＣＰＵ４１は、中心交差点を設定する。具体的には、候補フラグが“ＯＮ（１）”に設定された交差点の内で、最小のコスト値Ｔが対応付けられた交差点が中心交差点に設定される。尚、経路探索処理プログラムの開始後に最初にＳ４の処理が実行される際には、出発地交差点のみ候補フラグが“ＯＮ（１）”に設定されているので、必ず出発地交差点が中心交差点に設定されることとなる。一方、次回以降にＳ４の処理が実行された際には、中心交差点に設定された交差点と隣接する隣接交差点（対応付けられた候補フラグが“ＯＮ（１）”であれば過去の隣接交差点も含む場合がある）の内、最小のコスト値Ｔが対応付けられた交差点が中心交差点に設定される。

その後、Ｓ５においてＣＰＵ４１は、前記Ｓ４で新たに中心交差点に設定された交差点が目的地交差点であるか否か判定する。

そして、前記Ｓ４で新たに中心交差点に設定された交差点が目的地交差点であると判定された場合（Ｓ５：ＹＥＳ）には、Ｓ１３へと移行する。それに対して、前記Ｓ４で新たに中心交差点に設定された交差点が目的地交差点でないと判定された場合（Ｓ５：ＮＯ）には、Ｓ６へと移行する。

その後、Ｓ６においてＣＰＵ４１は、前記Ｓ４で新たに中心交差点に設定された交差点に対応付けられた候補フラグを“ＯＦＦ（０）”に設定する。

以降のＳ７〜Ｓ１２の処理は、交差点リストにリストアップされた交差点の内、前記Ｓ４で中心交差点に設定された交差点に隣接する交差点（以下、隣接交差点という）毎に繰り返し実施される。

先ず、Ｓ７においてＣＰＵ４１は、交差点リストにおいて隣接交差点に現時点で対応づけられているコスト値Ｔを読み出す。

次に、Ｓ８においてＣＰＵ４１は、後述のコスト算出処理（図１３）を実行する。コスト算出処理は、出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃを、探索条件毎且つ地域毎に設定されたコスト算出条件（図２〜図４）に基づいて算出する処理である。具体的には、中心交差点に対応付けられたコスト値Ｔに、中心交差点から隣接交差点までの探索コストを加算した値が加算値Ｃとなる。尚、探索コストの算出に用いるリンクの交通状況（渋滞度等）は、該リンクへの車両の到着予定時刻と前記Ｓ１で取得されたタイムスライスデータを用いて特定される。

その後、Ｓ９においてＣＰＵ４１は、前記Ｓ８で算出された出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃが、隣接交差点に現時点で対応づけられているコスト値Ｔよりも小さいか否か判定する。

そして、前記Ｓ８で算出された出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃが、隣接交差点に現時点で対応づけられているコスト値Ｔよりも小さいと判定された場合（Ｓ９：ＹＥＳ）には、該隣接交差点への最適経路は現在の中心交差点を経由した経路であると推定する。その後、Ｓ１０へと移行する。それに対して、前記Ｓ８で算出された出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃが、隣接交差点に現時点で対応づけられているコスト値Ｔと同じ又はコスト値Ｔより大きいと判定された場合（Ｓ９：ＮＯ）には、該隣接交差点への最適経路は現在の中心交差点を経由した経路では無いと推定する。そして、該隣接交差点に対応付けられたコスト値Ｔ等を更新することなく、他の隣接交差点に対する処理へと移行する。

Ｓ１０においてＣＰＵ４１は、隣接交差点に現時点で対応づけられているコスト値Ｔを、前記Ｓ８で算出された加算値Ｃへと更新する。

また、Ｓ１１においてＣＰＵ４１は、隣接交差点に対応づけられている直前交差点を、現在の中心交差点へと更新する。

更に、Ｓ１２においてＣＰＵ４１は、隣接交差点に対応づけられている候補フラグを“ＯＮ（１）”に設定する。即ち、該隣接交差点は、新たな中心交差点の候補となる。

そして、交差点リストにリストアップされた交差点の内、中心交差点に隣接する全ての隣接交差点に対して、前記Ｓ７〜Ｓ１２の処理が行われた後には、Ｓ４へと戻る。

そして、前記Ｓ５の判定処理において前記Ｓ４で新たに中心交差点に設定された交差点が目的地交差点であると判定された場合に実行されるＳ１３では、ＣＰＵ４１は、最終的な交差点リストに基づいて、目的地交差点から出発地交差点まで直前交差点を結んだ経路を適合経路に特定する。その結果、出発地交差点から目的地交差点までの探索コストの加算値が最小となる経路が適合経路として特定されることとなる。例えば、図１２に示す交差点リストが最終的に得られた場合には、交差点Ａ→交差点Ｂ→交差点Ｅ→交差点Ｇ→交差点Ｉを結んだ経路が特定される。

尚、前記Ｓ１３で特定された適合経路は、探索条件毎に液晶ディスプレイ１５等を介してユーザに案内される。そして、その後のユーザの操作に基づいて選択された一の適合経路がナビゲーション装置１の案内経路として設定され、設定された案内経路に基づく走行案内が行われる。

次に、前記Ｓ８において実行されるコスト算出処理のサブ処理について図１３に基づき説明する。図１３はコスト算出処理のサブ処理プログラムのフローチャートである。

先ず、Ｓ２１においてＣＰＵ４１は、地図情報ＤＢ３１に記憶された地図データに基づいて、中心交差点の座標を取得する。尚、中心交差点の座標は、中心交差点から隣接交差点までのリンクの開始点（出発地から出発した車両等がリンクの走行を開始する地点）となる。

次に、Ｓ２２においてＣＰＵ４１は、前記Ｓ２１で取得した中心交差点の座標に基づいて、中心交差点の座標が含まれる地域を特定する。具体的には、中心交差点の座標と、地域毎に区分された地図画像の背景ポリゴンとに基づいて特定する。尚、特定する地域はコスト算出条件の設定区分によって異なり、例えば図２及び図３に示すようにコスト算出条件を８地方区分毎に設定している場合には、８地方区分により区分された地域（例えば北海道地区や関東地区等）によって特定される。また、前記Ｓ２２で特定される地域は、中心交差点から隣接交差点までのリンクが含まれる地域にも相当する。但し、該リンクが複数の地域に跨る場合には、該リンクの開始点が含まれる地域が特定されることとなる。

続いて、前記Ｓ２３においてＣＰＵ４１は、前記Ｓ２２で特定された地域のコスト算出条件を取得する。前記したように、コスト算出条件は、同一区分に区分された地域内では、同一のコスト算出条件が規定されている。また、特にリンクコストのコスト算出条件は、車線数、道路種別、交通状況（例えば渋滞度）等の要素毎にどのようにコスト係数を設定するかを定める条件となる（図２〜図４参照）。

その後、Ｓ２４においてＣＰＵ４１は、地図情報ＤＢ３１に記憶されたリンクデータ３３等に基づいて、中心交差点から隣接交差点までのリンクのリンク長と、該リンクが含む要素（車線数、道路種別等）を取得する。尚、リンクが含む要素の内、特に時間経過によって変化する交通状況（渋滞度等）については前記Ｓ２４では取得せず、タイムスライスデータを用いて後述のＳ２６で取得する。

次に、Ｓ２５においてＣＰＵ４１は、現在の時刻（出発時刻）と前記Ｓ１で取得したタイムスライスデータ（図９）に記憶された各リンクの旅行時間とに基づいて、中心交差点への車両の到達時刻を予測する。尚、前記Ｓ２５で予測される中心交差点への車両の到達時刻は、中心交差点から隣接交差点までのリンクへの車両の到達時刻にも相当する。

続いて、Ｓ２６においてＣＰＵ４１は、前記Ｓ２５で予測された中心交差点への車両の到達時刻と前記Ｓ１で取得されたタイムスライスデータに基づいて、中心交差点から隣接交差点までのリンクが含む要素の内、特に時間経過によって変化する要素である交通状況（渋滞度等）を取得する。尚、前記したようにタイムスライスデータは所定時間毎（例えば１５分毎）に区分されており（図９参照）、到達時刻に対応するタイムスライスデータを用いる。また、前記したようにタイムスライスデータは、時刻毎に現在交通情報３６と統計交通情報３７と予測交通情報３８の利用に係る優先順位が設定されている。即ち、中心交差点への到達時刻に基づいて、現在交通情報３６と統計交通情報３７と予測交通情報３８のいずれによって、中心交差点から隣接交差点までのリンクの交通状況を特定するかが決定されることとなる。

例えば、図１４に示すように出発地を９：００に出発する車両の各交差点Ｂ〜Ｈの到達時刻が予測された場合であって、中心交差点が交差点Ｂである場合には、９：００〜９：１５のタイムスライスデータ（主に現在交通情報に基づいて予測されたデータ）を用いて中心交差点Ｂから隣接交差点までのリンク（Ｂ−Ｃ、Ｂ−Ｄ、Ｂ−Ｅ）の交通状況が特定される。また、中心交差点が交差点Ｇである場合には、１０：００〜１０：１５のタイムスライスデータ（主に予測交通情報に基づいて予測されたデータ）を用いて中心交差点Ｇから隣接交差点までのリンク（Ｇ−Ｈ、Ｇ−Ｉ）の交通状況が特定される。

その後、Ｓ２６においてＣＰＵ４１は、前記Ｓ２３で取得したコスト算出条件と、前記Ｓ２４及びＳ２６で取得した中心交差点から隣接交差点までのリンクのリンク長と、該リンクが含む要素とに基づいて、中心交差点から隣接交差点までのリンクのリンクコストＮを算出する。具体的にリンクコストＮは、リンクのリンク長に対して、該リンクが含む要素毎に設定されたコスト係数を乗じることによって算出される。例えば、『推奨』の探索条件により経路探索を行う場合であって、中心交差点が関東地区にあり、中心交差点から隣接交差点までのリンクが、リンク長が“２０”で、３車線の国道で、６０ｋｍ／ｈの法制速度が規定され、渋滞度が“空き”であった場合には、図２に示すコスト算出条件に基づいて、以下の式（１）により中心交差点から隣接交差点までのリンクのリンクコストＮを算出する。
Ｎ＝２０（リンク長）×１．０（国道）×０．７（３車線）×０．８（法定速度“速い”）×０．５（渋滞度“空き”）＝５．６・・・・（１）

続いて、Ｓ２７においてＣＰＵ４１は、中心交差点に対応付けられたコスト値Ｔに、前記Ｓ２６で算出されたリンクコストＮを加算する。その結果算出された値が、出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃとなる。その後、Ｓ９の判定処理へと移行する。

以上詳細に説明した通り、本実施形態に係るナビゲーション装置１、ナビゲーション装置１による経路探索方法及びナビゲーション装置１で実行されるコンピュータプログラムでは、出発地から目的地までの経路を構成する複数のリンク毎に、リンクが含まれる地域を特定し（Ｓ２２）、地域毎に探索コストに影響を与える要素と該要素を含むリンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得するとともに（Ｓ２３）、車両のリンクへの到達時刻を予測し（Ｓ２５）、探索コストに影響を与える要素として到達時刻におけるリンクの交通状況を取得し（Ｓ２６）、特定された地域と該地域に対応付けられた地域コスト算出条件と交通状況等の要素に基づいて算出された探索コストを用いて、出発地から目的地までの適合経路を探索条件毎に特定する（Ｓ１〜Ｓ１３）ので、リンク毎の走行時点の交通状況を考慮したより正確な探索コストを算出することが可能となる。また、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎に探索コストの算出条件を設定するので、地域性に沿ったユーザに対してより適切な経路を探索することが可能となる。
また、センタから取得した現時点の交通状況を示す現在交通情報３６と、現在交通情報３６の履歴を統計した統計情報である統計交通情報３７と、現在交通情報と統計交通情報に基づいて所定時間経過後の交通状況を予測した予測交通情報３８に基づいてリンクの交通状況を特定するので、現時点からの時間経過に関わらず所定時刻におけるリンクの交通状況を正確に特定することが可能となる。
また、リンクの到達時刻に基づいて、リンク毎に現在交通情報３６と統計交通情報３７と予測交通情報３８の利用に係る優先順位を設定し、取得された交通情報の内、最も優先順位の高い交通情報を用いて探索コストを算出するので、リンク毎の到達時刻に応じて交通状況を特定するのに適切な交通情報を選択することが可能であり、到達時刻におけるリンクの交通状況を正確に特定することが可能となる。
また、リンクへの到達時刻と現在時刻との差異に基づいて、優先順位を設定するので、リンク毎の到達時刻に応じて交通状況を特定するのに適切な交通情報を選択することが可能であり、到達時刻におけるリンクの交通状況を正確に特定することが可能となる。
また、リンクへの到達時刻と現在時刻との差異が第１基準値（例えば６０分）未満である場合に現在交通情報を最も高い優先順位に設定し、第１基準値以上で第２基準値（例えば１２０分）未満である場合に予測交通情報を最も高い優先順位に設定し、第２基準値以上である場合に統計交通情報を最も高い優先順位に設定するので、リンク毎の到達時刻に応じて交通状況を特定するのに適切な交通情報を選択することが可能であり、到達時刻におけるリンクの交通状況を正確に特定することが可能となる。
また、交通状況に対する地域性（道路事情、交通事情、住民性等）を考慮して地域毎にリンクコストを算出する際に用いるコスト係数を設定するので、リンクが含む渋滞度等の交通状況に基づいて適切なリンクコストを算出することが可能となる。
また、探索コストの算出対象となるリンクが複数の地域に跨る場合には、該リンクの開始点が含まれる地域を、該リンクが含まれる地域として特定するので、探索コストの算出対象となるリンクに対して最も影響のある地域を適切に特定することが可能となる。

尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では、４種類の探索条件毎に適合経路を特定する構成としているが、２種類、３種類又は５種類以上の探索条件毎に適合経路を特定する構成としても良い。尚、その場合には地域コスト算出条件を探索条件の数に対応させて作成する必要がある。

また、本実施形態では、図２〜図４を用いて特にリンクコストのコスト算出条件を例に挙げて説明したが、交差点コストについてもリンクコストと同様に探索条件毎且つ地域毎にコスト算出条件が設定される。例えば、信号機の多い関東地区や近畿地区では信号機の設置された交差点の交差点コストを他の地区より小さくしたり、交通量の多い関東地区や近畿地区では右折交差点の交差点コストを他の地区より大きくするようにコスト算出条件を設定する。そして、ＣＰＵ４１は、コスト算出対象の交差点の含まれる地域を特定し、特定した地域のコスト算出条件を用いて該交差点の交差点コストを算出する。

また、交差点コストのコスト算出条件は、探索条件に関わらず同じ条件（即ち地域毎のみで異なる条件）としても良い。また、リンクコストと交差点コストのいずれか一方のコスト算出条件のみを地域毎に変更する構成としても良い。

また、リンクやノードが位置する地域では無く、ユーザの居住する地域に基づいてコスト算出条件を設定しても良い。更に、リンクやノードが位置する地域に基づくコストの算出条件と、ユーザの居住する地域に基づくコスト算出条件の両方を適用する構成としても良い。その際には、道路事情に基づく地域性と住民性に基づく地域性を考慮することとする。例えば、北海道地区の住民が関東へ旅行した場合には、渋滞度は関東地区のコスト係数を採用し（道路事情による要因）、有料道路は北海道地区のコスト係数を採用する（通行料金に抵抗があるなど住民性の思考）。

また、本実施形態では、リンクを走行するのに必要なリンクコストのみを考慮して探索コストの加算値Ｃを算出する構成としているが、交差点を通過するのに必要な交差点コストやその他のコストについても考慮して探索コストの加算値Ｃを算出する構成としても良い。

また、本実施形態では、探索コストの算出対象となるリンクが複数の地域に跨る場合には、該リンクの開始点が含まれる地域を、該リンクが含まれる地域として特定するが、該リンクの終了点が含まれる地域を、該リンクが含まれる地域として特定しても良い。また、リンクが各地域に含まれる長さの割合を比較し、割合が高い地域を該リンクが含まれる地域として特定しても良い。

また、本実施形態では、タイムスライスデータを作成する際の交通情報として現在交通情報３６、統計交通情報３７、予測交通情報３８の内のいずれかを用いているが、上記３種類以外の交通情報を用いても良い。また、タイムスライスデータを作成する際の交通情報の優先順位は、図９に示す順位に限られることは無い。例えば、出発時刻から１２０分以降の時間帯において、統計交通情報３７、予測交通情報３８、現在交通情報３６の順に優先順位を設定しても良い。

また、本発明はナビゲーション装置以外に、経路探索機能を有する装置に対して適用することが可能である。例えば、携帯電話機やスマートフォン等の携帯端末、パーソナルコンピュータ等（以下、携帯端末等という）に適用することも可能である。また、サーバと携帯端末等から構成されるシステムに対しても適用することが可能となる。その場合には、上述した経路探索処理プログラム（図８、図１３）の各ステップは、サーバと携帯端末等のいずれが実施する構成としても良い。また、本発明を携帯端末等に適用する場合には、車両以外の移動体、例えば、携帯端末等のユーザや２輪車等に対する経路の探索にも本願発明を適用することが可能である。

１ ナビゲーション装置
１３ ナビゲーションＥＣＵ
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ

Claims (10)

1. 出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得手段と、
   前記リンク情報取得手段により取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測手段と、
   前記到達時刻予測手段により予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得手段と、
   前記候補リンクが含まれる地域を特定する地域特定手段と、
   地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得手段と、
   前記地域特定手段によって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得手段により取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索手段と、を有することを特徴とする経路探索システム。
2. 前記交通情報は、センタから取得した現時点の交通状況を示す現在交通情報と、前記現在交通情報の履歴を統計した統計情報である統計交通情報と、前記現在交通情報と前記統計交通情報に基づいて所定時間経過後の交通状況を予測した予測交通情報とを含み、
   前記交通情報取得手段は、前記現在交通情報と前記統計交通情報と前記予測交通情報の少なくとも一以上を前記交通情報として取得することを特徴とする請求項１に記載の経路探索システム。
3. 前記到達時刻予測手段により予測された前記到達時刻に基づいて、前記候補リンク毎に前記現在交通情報と前記統計交通情報と前記予測交通情報の利用に係る優先順位を設定する優先順位設定手段を有し、
   前記経路探索手段は、前記交通情報取得手段により取得された前記交通情報の内、最も優先順位の高い前記交通情報を用いて前記探索コストを算出することを特徴とする請求項２に記載の経路探索システム。
4. 前記優先順位設定手段は、前記到達時刻予測手段により予測された前記到達時刻と現在時刻との差異に基づいて、前記優先順位を設定することを特徴とする請求項３に記載の経路探索システム。
5. 前記優先順位設定手段は、
   前記到達時刻予測手段により予測された前記到達時刻と現在時刻との差異が第１基準値未満である場合に、前記現在交通情報を最も高い優先順位に設定し、
   前記到達時刻予測手段により予測された前記到達時刻と現在時刻との差異が前記第１基準値以上で第２基準値未満である場合に、前記予測交通情報を最も高い優先順位に設定し、
   前記到達時刻予測手段により予測された前記到達時刻と現在時刻との差異が前記第２基準値以上である場合に、前記統計交通情報を最も高い優先順位に設定することを特徴とする請求項４に記載の経路探索システム。
6. 前記探索コストは、該候補リンクのリンク長に該候補リンクの交通状況に基づいた係数を乗じることによって算出され、
   前記探索コストの算出条件は、交通状況毎の前記係数の値を規定することを特徴とする請求項１乃至請求項５のいずれかに記載の経路探索システム。
7. 前記地域特定手段は、前記探索コストの算出対象となる前記候補リンクが複数の地域に跨る場合には、該候補リンクの開始点が含まれる地域を、該候補リンクが含まれる地域として特定することを特徴とする請求項１乃至請求項６のいずれかに記載の経路探索システム。
8. 出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得手段と、
   前記リンク情報取得手段により取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測手段と、
   前記到達時刻予測手段により予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得手段と、
   前記候補リンクが含まれる地域を特定する地域特定手段と、
   地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得手段と、
   前記地域特定手段によって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得手段により取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索手段と、を有することを特徴とする経路探索装置。
9. 出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得ステップと、
   前記リンク情報取得ステップにより取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測ステップと、
   前記到達時刻予測ステップにより予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得ステップと、
   前記候補リンクが含まれる地域を特定する地域特定ステップと、
   地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得ステップと、
   前記地域特定ステップによって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得ステップにより取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索ステップと、を有することを特徴とする経路探索方法。
10. コンピュータに、
    出発地から目的地まで移動体が移動する為の経路の候補を構成するリンクである候補リンクに関するリンク情報を取得するリンク情報取得機能と、
    前記リンク情報取得機能により取得した前記リンク情報に基づいて、前記候補リンクへの前記移動体の到達時刻を予測する到達時刻予測機能と、
    前記到達時刻予測機能により予測された前記到達時刻に基づいて、該到達時刻における前記候補リンクの交通状況を示す交通情報を取得する交通情報取得機能と、
    前記候補リンクが含まれる地域を特定する地域特定機能と、
    地域毎に、探索コストに影響を与える交通状況と該交通状況にある前記候補リンクに対する探索コストの算出条件とを対応付けた地域コスト算出条件を取得する算出条件取得機能と、
    前記地域特定機能によって特定された地域と該地域に対応付けられた前記地域コスト算出条件と前記交通情報取得機能により取得した前記交通情報とに基づいて算出された前記探索コストを用いて、前記出発地から前記目的地までの前記経路を探索する経路探索機能と、
    を実行させることを特徴とするコンピュータプログラム。

Images