(57)【要約】【課題】複数の探索条件毎に基づく経路探索処理に係る処理時間や処理負担を軽減することを可能とした経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラムを提供する。【解決手段】出発地交差点から目的地交差点まで至る適合経路の候補を接続する交差点のリストである交差点リストを作成し（Ｓ１）、ダイクストラ法による経路探索処理を実行し、中心交差点が目的地交差点となった場合に、交差点リストに含まれる交差点の内、過去に中心交差点に設定されておらず、且つ、算出された探索コストの加算値が目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定し（Ｓ１２）、処理対象交差点があると判定された場合に、該処理対象交差点を新たな中心交差点に設定してコスト算出の処理を継続して実行し（Ｓ１３）するように構成する。【選択図】図２
2014044156.tif 000002
【特許請求の範囲】
【請求項１】
出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定する経路探索システムであって、
前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成手段と、
前記出発地交差点を中心交差点に設定する初期中心交差点設定手段と、
前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出手段と、
前記コスト算出手段によって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新手段と、
前記中心交差点更新手段によって新たに設定された前記中心交差点を対象とする前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定手段と、
前記交差点一致判定手段によって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出手段により算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定手段と、
前記交差点判定手段によって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出手段及び前記中心交差点更新手段の処理を実行する補助処理手段と、
前記コスト算出手段により算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定手段と、を有することを特徴とする経路探索システム。
【請求項２】
前記補助処理手段は、前記交差点判定手段によって前記処理対象交差点が無いと判定されるまで、前記処理対象交差点を前記中心交差点とした前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し実行することを特徴とする請求項１に記載の経路探索システム。
【請求項３】
前記交差点リスト作成手段は、前記交差点リストを、前記複数の探索条件毎に区分した複数のリストにより作成することを特徴とする請求項１又は請求項２に記載の経路探索システム。
【請求項４】
前記交差点リスト作成手段は、前記交差点リストを、前記交差点リストに含まれる各交差点に対して前記複数の探索条件を対応付けた一のリストにより作成することを特徴とする請求項１又は請求項２に記載の経路探索システム。
【請求項５】
出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定する経路探索装置であって、
前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成手段と、
前記出発地交差点を中心交差点に設定する初期中心交差点設定手段と、
前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出手段と、
前記コスト算出手段によって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新手段と、
前記中心交差点更新手段によって新たに設定された前記中心交差点を対象とする前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定手段と、
前記交差点一致判定手段によって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、少なくとも一の探索条件で前記コスト算出手段により算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定手段と、
前記交差点判定手段によって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出手段及び前記中心交差点更新手段の処理を実行する補助処理手段と、
前記コスト算出手段により算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定手段と、を有することを特徴とする経路探索装置。
【請求項６】
出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定する経路探索方法であって、
前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成ステップと、
前記出発地交差点を中心交差点に設定する初期中心交差点設定ステップと、
前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出ステップと、
前記コスト算出ステップによって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新ステップと、
前記中心交差点更新ステップによって新たに設定された前記中心交差点を対象とする前記コスト算出ステップ及び前記中心交差点更新ステップの処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定ステップと、
前記交差点一致判定ステップによって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出ステップにより算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定ステップと、
前記交差点判定ステップによって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出ステップ及び前記中心交差点更新ステップの処理を実行する補助処理ステップと、
前記コスト算出ステップにより算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定ステップと、を有することを特徴とする経路探索方法。
【請求項７】
コンピュータに、
出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定させるコンピュータプログラムであって、
前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成機能と、
前記出発地交差点を中心交差点に設定する初期中心交差点設定機能と、
前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出機能と、
前記コスト算出機能によって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新機能と、
前記中心交差点更新機能によって新たに設定された前記中心交差点を対象とする前記コスト算出機能及び前記中心交差点更新機能の処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定機能と、
前記交差点一致判定機能によって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出機能により算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定機能と、
前記交差点判定機能によって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出機能及び前記中心交差点更新機能の処理を実行する補助処理機能と、
前記コスト算出機能により算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定機能と、
を実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地へと至る経路を探索する経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。更に、かかるナビゲーション装置には、所望する目的地を入力すると、自車位置から目的地までの最適経路を探索する経路探索機能を備えており、探索された最適経路を案内経路として設定し、ディスプレイ画面に案内経路を表示するとともに、交差点に接近した場合等には音声による案内をすることによって、ユーザを所望の目的地まで確実に案内するようになっている。また、近年は携帯電話機、スマートフォン、ＰＤＡ（Personal Digital Assistant）、パーソナルコンピュータ等においても上記ナビゲーション装置と同様の機能を有するものがある。
【０００３】
また、上記経路探索機能では、出発地から目的地までの経路を探索する経路探索方法として一般的にダイクストラ法が用いられる。また、出発地から目的地までの経路を探索する場合には、最適な一の経路のみを探索するのではなく、複数の探索条件に基づいて探索条件毎に適合する経路を探索することが行われている。例えば、特開２００８−２０９２０８号公報には、推奨ルート、有料道路優先ルート、一般道路優先ルート、距離優先ルート、別ルートの５つの探索条件に適合する計５つの経路をダイクストラ法により探索することについて記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２０９２０８号公報（第７−９頁、図１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、上記特許文献１に記載された技術のように複数の探索条件毎に経路を特定する場合には、探索条件毎にコスト算出条件を変えて、ダイクストラ法による経路探索処理を探索条件の数だけ繰り返し実行していた。即ち、特許文献１のように５つの探索条件がある場合には、先ず推奨ルートに基づく経路探索処理を実行して推奨ルートの探索条件に合う経路を特定し、その後に有料道路優先ルートに基づく経路探索処理を実行して有料道路優先ルートの探索条件に合う経路を特定し、同様にして一般道路優先ルート、距離優先ルート、別ルートについても経路探索処理を繰り返し実行し、計５回の経路探索処理を行うことによって５つの経路を特定していた。
【０００６】
しかしながら、従来のように探索条件毎に経路探索処理を実行する構成とすると、探索条件が増えるほど経路探索処理に係る処理時間が長くなり、処理負担も増加していた。また、繰り返し実行される経路探索処理は、重複する処理も多い為、ＣＰＵの作業効率が非常に悪かった。
【０００７】
本発明は前記従来における問題点を解消するためになされたものであり、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する際に、探索条件毎に同様の経路探索処理を一から繰り返し実行する必要が無く、経路探索処理に係る処理時間や処理負担を軽減することを可能とした経路探索システム、経路探索装置、経路探索方法及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記目的を達成するため本願の請求項１に係る経路探索システム（１）は、出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定する経路探索システムであって、前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成手段（１３）と、前記出発地交差点を中心交差点に設定する初期中心交差点設定手段（１３）と、前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出手段（１３）と、前記コスト算出手段によって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新手段（１３）と、前記中心交差点更新手段によって新たに設定された前記中心交差点を対象とする前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定手段（１３）と、前記交差点一致判定手段によって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出手段により算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定手段（１３）と、前記交差点判定手段によって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出手段及び前記中心交差点更新手段の処理を実行する補助処理手段（１３）と、前記コスト算出手段により算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定手段（１３）と、を有することを特徴とする。
【０００９】
また、請求項２に係る経路探索システム（１）は、請求項１に記載の経路探索システムであって、前記補助処理手段（１３）は、前記交差点判定手段（１３）によって前記処理対象交差点が無いと判定されるまで、前記処理対象交差点を前記中心交差点とした前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し実行することを特徴とする。
【００１０】
また、請求項３に係る経路探索システム（１）は、請求項１又は請求項２に記載の経路探索システムであって、前記交差点リスト作成手段（１３）は、前記交差点リストを、前記複数の探索条件毎に区分した複数のリストにより作成することを特徴とする。
【００１１】
また、請求項４に係る経路探索システム（１）は、請求項１又は請求項２に記載の経路探索システムであって、前記交差点リスト作成手段（１３）は、前記交差点リストを、前記交差点リストに含まれる各交差点に対して前記複数の探索条件を対応付けた一のリストにより作成することを特徴とする。
【００１２】
また、請求項５に係る経路探索装置（１）は、出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定する経路探索システムであって、前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成手段（１３）と、前記出発地交差点を中心交差点に設定する初期中心交差点設定手段（１３）と、前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出手段（１３）と、前記コスト算出手段によって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新手段（１３）と、前記中心交差点更新手段によって新たに設定された前記中心交差点を対象とする前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定手段（１３）と、前記交差点一致判定手段によって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出手段により算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定手段（１３）と、前記交差点判定手段によって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出手段及び前記中心交差点更新手段の処理を実行する補助処理手段（１３）と、前記コスト算出手段により算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定手段（１３）と、を有することを特徴とする。
【００１３】
また、請求項６に係る経路探索方法は、出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定する経路探索方法であって、前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成ステップと、前記出発地交差点を中心交差点に設定する初期中心交差点設定ステップと、前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出ステップと、前記コスト算出ステップによって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新ステップと、前記中心交差点更新ステップによって新たに設定された前記中心交差点を対象とする前記コスト算出ステップ及び前記中心交差点更新ステップの処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定ステップと、前記交差点一致判定ステップによって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出ステップにより算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定ステップと、前記交差点判定ステップによって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出ステップ及び前記中心交差点更新ステップの処理を実行する補助処理ステップと、前記コスト算出ステップにより算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定ステップと、を有することを特徴とする。
【００１４】
更に、請求項７に係るコンピュータプログラムは、コンピュータに、出発地から目的地まで至る経路として、複数の探索条件毎に該探索条件に適合する適合経路をそれぞれ特定させるコンピュータプログラムであって、前記出発地に対応する出発地交差点から前記目的地に対応する目的地交差点まで至る前記適合経路の候補を接続する交差点のリストである交差点リストを作成する交差点リスト作成機能と、前記出発地交差点を中心交差点に設定する初期中心交差点設定機能と、前記交差点リストに含まれる交差点であって且つ前記中心交差点に隣接する交差点である隣接交差点について、前記出発地交差点から該隣接交差点への探索コストの加算値を前記複数の探索条件毎且つ該隣接交差点毎に算出するコスト算出機能と、前記コスト算出機能によって算出された前記複数の探索条件毎の前記探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる前記隣接交差点を新たな中心交差点に設定する中心交差点更新機能と、前記中心交差点更新機能によって新たに設定された前記中心交差点を対象とする前記コスト算出機能及び前記中心交差点更新機能の処理を繰り返し行った結果、前記中心交差点が前記目的地交差点と一致したか否かを判定する交差点一致判定機能と、前記交差点一致判定機能によって前記中心交差点が前記目的地交差点に一致したと判定された場合に、前記交差点リストに含まれる交差点の内、過去に前記中心交差点に設定されておらず、且つ、前記コスト算出機能により算出された前記探索コストの加算値が前記目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する交差点判定機能と、前記交差点判定機能によって前記処理対象交差点があると判定された場合に、前記処理対象交差点を新たな中心交差点に設定し、前記コスト算出機能及び前記中心交差点更新機能の処理を実行する補助処理機能と、前記コスト算出機能により算出された前記探索コストの加算値に基づいて、前記出発地交差点から前記目的地交差点までの前記探索コストの加算値が最小となる経路を前記適合経路として前記探索条件毎に特定する経路特定機能と、を実行させることを特徴とする。
【発明の効果】
【００１５】
前記構成を有する請求項１に記載の経路探索システムによれば、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する際に、探索条件毎に同様の経路探索処理を一から繰り返し実行する必要が無く、経路探索処理に係る処理時間や処理負担を軽減することが可能となる。
【００１６】
また、請求項２に記載の経路探索システムによれば、交差点判定手段によって処理対象交差点が無いと判定されるまで、処理対象交差点を中心交差点としたコスト算出手段及び中心交差点更新手段の処理を繰り返し実行するので、複数の探索条件に対するコスト算出を同時に行う場合であっても、出発地交差点から交差点リストに含まれる各交差点に至る探索コストの最小加算値を正確に算出することが可能となる。その結果、出発地交差点から目的地交差点までの探索コストの加算値が最小となる経路を適合経路として適切に特定することが可能となる。
【００１７】
また、請求項３に記載の経路探索システムによれば、交差点リストを複数の探索条件毎に区分した複数のリストにより作成するので、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する場合であっても、複数の交差点リストを用いて探索条件毎の適合経路を従来に比べてより少ない処理工程で特定することが可能となる。
【００１８】
また、請求項４に記載の経路探索システムによれば、交差点リストを交差点リストに含まれる各交差点に対して複数の探索条件を対応付けた一のリストにより作成するので、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する場合であっても、一の交差点リストを用いて探索条件毎の適合経路を従来に比べてより少ない処理工程で特定することが可能となる。
【００１９】
また、請求項５に記載の経路探索装置によれば、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する際に、探索条件毎に同様の経路探索処理を一から繰り返し実行する必要が無く、経路探索処理に係る処理時間や処理負担を軽減することが可能となる。
【００２０】
また、請求項６に記載の経路探索方法によれば、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する際に、探索条件毎に同様の経路探索処理を一から繰り返し実行する必要が無く、経路探索処理に係る処理時間や処理負担を軽減することが可能となる。
【００２１】
更に、請求項７に記載のコンピュータプログラムによれば、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定させる際に、探索条件毎に同様の経路探索処理を一から繰り返し実行させる必要が無く、経路探索処理に係る処理時間や処理負担を軽減することが可能となる。
【図面の簡単な説明】
【００２２】
【図１】本実施形態に係るナビゲーション装置の構成を示したブロック図である。
【図２】本実施形態に係る経路探索処理プログラムのフローチャートである。
【図３】出発地交差点から目的地交差点までの適合経路の候補を示した図である。
【図４】交差点リストの一例を示した図である。
【図５】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図６】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図７】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図８】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図９】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図１０】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図１１】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図１２】交差点リストに基づく適合経路の特定処理の具体例について説明した図である。
【図１３】交差点リストの変形例について示した図である。
【発明を実施するための形態】
【００２３】
以下、本発明に係る経路探索システム及び経路探索装置をナビゲーション装置に具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。
【００２４】
図１に示すように本実施形態に係るナビゲーション装置１は、ナビゲーション装置１が搭載された車両の現在位置を検出する現在位置検出部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ１３と、ユーザからの操作を受け付ける操作部１４と、ユーザに対して車両周辺の地図や後述の経路探索処理によって探索された経路に関する経路情報等を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、記憶媒体であるＤＶＤを読み取るＤＶＤドライブ１７と、プローブセンタやＶＩＣＳ（登録商標：Vehicle Information and Communication System）センタ等の情報センタとの間で通信を行う通信モジュール１８と、から構成されている。
【００２５】
以下に、ナビゲーション装置１を構成する各構成要素について順に説明する。
現在位置検出部１１は、ＧＰＳ２１、車速センサ２２、ステアリングセンサ２３、ジャイロセンサ２４等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ２２は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションＥＣＵ１３に出力する。そして、ナビゲーションＥＣＵ１３は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記４種類のセンサをナビゲーション装置１が全て備える必要はなく、これらの内の１又は複数種類のセンサのみをナビゲーション装置１が備える構成としても良い。
【００２６】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ３１や所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、データ記録部１２をハードディスクの代わりにメモリーカードやＣＤやＤＶＤ等の光ディスクにより構成しても良い。
【００２７】
ここで、地図情報ＤＢ３１は、例えば、道路（リンク）に関するリンクデータ３３、ノード点に関するノードデータ３４、経路探索処理に用いられる探索データ３５、施設に関する施設データ、地図を表示するための地図表示データ、各交差点に関する交差点データ、地点を検索するための検索データ等が記憶された記憶手段である。
【００２８】
また、リンクデータ３３としては、道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。
【００２９】
また、ノードデータ３４としては、実際の道路の分岐点（交差点、Ｔ字路等も含む）や各道路に曲率半径等に応じて所定の距離毎に設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接するノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。
【００３０】
また、探索データ３５としては、後述のように出発地（例えば車両の現在位置）から設定された目的地までの経路を探索する経路探索処理に使用される各種データについて記録されている。具体的には、交差点に対する経路として適正の程度を数値化したコスト（以下、交差点コストという）や道路を構成するリンクに対する経路として適正の程度を数値化したコスト（以下、リンクコストという）等の探索コストを算出する為に使用するコスト算出データが記憶されている。
【００３１】
ここで、交差点コストは、探索コストの算出対象となる経路に含まれる交差点に対応するノード毎に設定され、信号機の有無、交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）等によってその値が算出される。
また、リンクコストは、探索コストの算出対象となる経路に含まれるリンク毎に設定され、リンク長を基本にして、該リンクの道路属性や道路種別、道路幅、車線数等を考慮して算出される。
【００３２】
ここで、本実施形態に係るナビゲーション装置１では、複数の探索条件に基づいて探索条件毎に該探索条件に適合する経路（以下、適合経路という）をそれぞれ特定し、各探索条件で特定された複数本の適合経路から利用者の希望する一の経路を最終的に案内経路として設定する構成を有する。具体的な探索条件としては、目的地までの所要時間が短くなることを優先するとともに走行し易さや走行に係る費用等についても考慮した『推奨』と、目的地まで有料道路を走行することを優先する『有料道路優先』と、目的地まで一般道路を走行することを優先する『一般優先』の３種類の探索条件からなる。
【００３３】
また、探索条件毎に上記リンクコストの算出条件は異なっている。例えば、『推奨』ではリンク長を基本として、車線数、道路種別、渋滞度等の旅行時間に影響を与える要素を考慮し、より旅行時間が短くなるリンクが低いコストとなるようにリンクコストを算出する。更に、走行に係る費用や走行し易さ等についても考慮する。また、『有料道路優先』では上記『推奨』の算出方法に加えて有料道路の道路種別であるリンク以外のリンクのリンクコストを高くなるようにして（例えば２倍にして）リンクコストを算出する。また、『一般優先』では上記『推奨』の算出方法に加えて有料道路の道路種別であるリンクのリンクコストを高くなるようにして（例えば２倍にして）リンクコストを算出する。即ち、同一のリンクであっても探索条件毎に算出されるリンクコストは異なる値となる。
そして、ナビゲーションＥＣＵ１３は、探索条件毎に算出された上記リンクコストや交差点コスト等の探索コストに基づき、ダイクストラ法を用いて経路探索を行う。尚、ダイクストラ法による経路探索処理の詳細については後述する。
【００３４】
一方、ナビゲーションＥＣＵ（エレクトロニック・コントロール・ユニット）１３は、ナビゲーション装置１の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ、交差点リスト等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の経路探索処理プログラム（図２参照）等が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置を備えている。尚、ナビゲーションＥＣＵ１３は、処理アルゴリズムとしての各種手段を構成する。例えば、交差点リスト作成手段は、出発地に対応する出発地交差点から目的地に対応する目的地交差点まで至る適合経路の候補を接続する交差点のリストである交差点リストを作成する。初期中心交差点設定手段は、出発地交差点を中心交差点に設定する。コスト算出手段は、交差点リストに含まれる交差点であって且つ中心交差点に隣接する交差点である隣接交差点について、出発地交差点から該隣接交差点への探索コストの加算値を複数の探索条件毎且つ該隣接交差点毎に算出する。中心交差点更新手段は、複数の探索条件毎の探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる隣接交差点を新たな中心交差点に設定する。交差点一致判定手段は、中心交差点更新手段によって新たに設定された中心交差点を対象とする前記コスト算出手段及び前記中心交差点更新手段の処理を繰り返し行った結果、中心交差点が目的地交差点と一致したか否かを判定する。交差点判定手段は、中心交差点が目的地交差点に一致したと判定された場合に、交差点リストに含まれる交差点の内、過去に中心交差点に設定されておらず、且つ、コスト算出手段により算出された探索コストの加算値が目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定する。補助処理手段は、交差点判定手段によって処理対象交差点があると判定された場合に、処理対象交差点を新たな中心交差点に設定し、コスト算出手段及び前記中心交差点更新手段の処理を実行する。経路特定手段は、コスト算出手段により算出された探索コストの加算値に基づいて、出発地交差点から目的地交差点までの探索コストの加算値が最小となる経路を適合経路として探索条件毎に特定する。
【００３５】
操作部１４は、走行開始地点としての出発地、走行終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーションＥＣＵ１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部１４は液晶ディスプレイ１５の前面に設けたタッチパネルによって構成することもできる。また、マイクと音声認識装置によって構成することもできる。
【００３６】
また、液晶ディスプレイ１５には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの案内経路、案内経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。
また、ナビゲーションＥＣＵ１３が後述の経路探索処理を行った場合には、探索結果に基づいて複数の探索条件毎に特定された適合経路について表示される。また、適合経路が高速道路などの有料道路を走行する場合には、走行に必要となる料金についても併せて表示される。そして、ユーザは表示された複数の適合経路の内から、案内経路とする経路を選択する。
【００３７】
また、スピーカ１６は、ナビゲーションＥＣＵ１３からの指示に基づいて案内経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。
【００３８】
また、ＤＶＤドライブ１７は、ＤＶＤやＣＤ等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、地図情報ＤＢ３１の更新等が行われる。
【００３９】
また、通信モジュール１８は、交通情報センタ、例えば、ＶＩＣＳセンタやプローブセンタ等から送信された渋滞情報、規制情報、交通事故情報等の各情報から成る交通情報を受信する為の通信装置であり、例えば携帯電話機やＤＣＭが該当する。
【００４０】
続いて、上記構成を有する本実施形態に係るナビゲーション装置１においてＣＰＵ４１が実行する経路探索処理プログラムについて図２に基づき説明する。図２は本実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムはナビゲーション装置１において経路探索を行う為の所定の操作（例えば、目的地の設定操作）を受け付けた際に実行され、複数の探索条件毎に出発地から目的地までの適合経路を、ダイクストラ法を用いて探索するプログラムである。また、以下の実施例の説明では、説明の簡略化の為に探索コストとしてリンクコストのみを考慮することとし、交差点コストやその他のコストについては考慮しないこととする。尚、以下の図２にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。
【００４１】
先ず、経路探索処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、出発地交差点、目的地交差点及び地図情報ＤＢ３１に記憶された地図情報に基づいて、交差点リストを作成し、作成された交差点リストをＲＡＭ４２等の記憶媒体に記憶する。更に、作成された交差点リストの初期化についても行う。尚、出発地交差点は出発地（例えば車両の現在位置）に対応する交差点（例えば出発地から最も近い位置にある交差点）であり、目的地交差点は設定された目的地に対応する交差点（例えば目的地から最も近い位置にある交差点）である。
【００４２】
ここで、交差点リストは、出発地交差点から目的地交差点まで至る適合経路の候補を接続する交差点（出発地交差点と目的地交差点を含む）のリストである。また、交差点リストには、リストアップされた交差点毎に、出発地交差点から該交差点までの探索コストの最小加算値を示すコスト値Ｔと、コスト値Ｔを実現する場合に直前に通過する交差点である直前交差点と、中心交差点の設定候補を示す候補フラグとが対応付けられている。
【００４３】
以下の説明では、図３に示す出発地交差点Ａから目的地交差点Ｉまでの経路探索処理を行う場合を具体例に挙げて説明することとする。図３に示す出発地交差点Ａから目的地交差点Ｉまでの経路探索処理を行う場合には、出発地交差点Ａから目的地交差点Ｉまでの適合経路を構成し得る各リンクを接続する９つの交差点Ａ〜Ｉがリストアップされた交差点リストが作成される（図４参照）。更に、交差点リストは、探索条件毎に区分した複数のリストにより作成される。即ち、本実施形態では目的地までの所要時間が短くなることを優先するとともに走行し易さや走行に係る費用等についても考慮した『推奨』と、目的地まで有料道路を走行することを優先する『有料道路優先』と、目的地まで一般道路を走行することを優先する『一般優先』の３種類の探索条件により経路探索を行うので、計３つの交差点リストが作成される。
【００４４】
また、前記Ｓ１で実行される交差点リストの初期化処理では、図４に示すようにリストアップされた全交差点に対応付けられたコスト値Ｔが無限大に設定され、直前交差点は対応付けず、候補フラグは“ＯＦＦ（０）”に設定される。
【００４５】
次に、Ｓ２においてＣＰＵ４１は、出発地交差点に対する初期化処理を行う。具体的には、図５に示すように交差点リストの出発地交差点Ａに対応付けられたコスト値Ｔを０に設定し、候補フラグを“ＯＮ（１）”に設定する。
【００４６】
続いて、Ｓ３においてＣＰＵ４１は、中心交差点を設定する。具体的には、候補フラグが“ＯＮ（１）”に設定された交差点の内で、探索条件に関わらず最小のコスト値Ｔが対応付けられた交差点が中心交差点に設定される。尚、経路探索処理プログラムの開始後に最初にＳ３の処理が実行される際には、出発地交差点のみ候補フラグが“ＯＮ（１）”に設定されているので、必ず出発地交差点が中心交差点に設定されることとなる。一方、次回以降にＳ３の処理が実行された際には、中心交差点に設定された交差点と隣接する隣接交差点（対応付けられた候補フラグが“ＯＮ（１）”であれば過去の隣接交差点も含む場合がある）の内、最小のコスト値Ｔが対応付けられた交差点が中心交差点に設定される。また、上記したように前記Ｓ３では、探索条件に関わらずコスト値Ｔが最小となる交差点が中心交差点として選択される。即ち、“推奨”の交差点リストでは他の交差点よりも大きいコスト値Ｔ（例えば１５）が対応付けられていた交差点であっても、他の探索条件の交差点リストにおいて該交差点に小さいコスト値Ｔ（例えば８）が対応付けられていれば、中心交差点に設定される場合がある。
【００４７】
その後、Ｓ４においてＣＰＵ４１は、前記Ｓ３で新たに中心交差点に設定された交差点が目的地交差点であるか否か判定する。
【００４８】
そして、前記Ｓ３で新たに中心交差点に設定された交差点が目的地交差点であると判定された場合（Ｓ４：ＹＥＳ）には、Ｓ１２へと移行する。それに対して、前記Ｓ３で新たに中心交差点に設定された交差点が目的地交差点でないと判定された場合（Ｓ４：ＮＯ）には、Ｓ５へと移行する。
【００４９】
その後、Ｓ５においてＣＰＵ４１は、前記Ｓ３で新たに中心交差点に設定された交差点に対応付けられた候補フラグを“ＯＦＦ（０）”に設定する。例えば、出発地交差点Ａが前記Ｓ３で中央交差点に設定された場合には、図６に示すように出発地交差点Ａに対応付けられた候補フラグが“ＯＦＦ（０）”に設定される。
【００５０】
以降のＳ６〜Ｓ１１の処理は、交差点リストにリストアップされた交差点の内、前記Ｓ３で中心交差点に設定された交差点に隣接する交差点（以下、隣接交差点という）毎、且つ探索条件毎に繰り返し実施される。
【００５１】
先ず、Ｓ６においてＣＰＵ４１は、交差点リストにおいて隣接交差点に現時点で対応づけられているコスト値Ｔを読み出す。
【００５２】
次に、Ｓ７においてＣＰＵ４１は、出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃを算出する。具体的には、中心交差点に対応付けられたコスト値Ｔに、中心交差点から隣接交差点までの探索コストを加算した値が加算値Ｃとなる。
【００５３】
その後、Ｓ８においてＣＰＵ４１は、前記Ｓ７で算出された出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃが、隣接交差点に現時点で対応づけられているコスト値Ｔよりも小さいか否か判定する。
【００５４】
そして、前記Ｓ７で算出された出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃが、隣接交差点に現時点で対応づけられているコスト値Ｔよりも小さいと判定された場合（Ｓ８：ＹＥＳ）には、該隣接交差点への最適経路は現在の中心交差点を経由した経路であると推定する。その後、Ｓ９へと移行する。それに対して、前記Ｓ７で算出された出発地交差点から中心交差点を経由して隣接交差点へと至る経路の探索コストの加算値Ｃが、隣接交差点に現時点で対応づけられているコスト値Ｔと同じ又はコスト値Ｔより大きいと判定された場合（Ｓ８：ＮＯ）には、該隣接交差点への最適経路は現在の中心交差点を経由した経路では無いと推定する。そして、該隣接交差点に対応付けられたコスト値Ｔ等を更新することなく、他の探索条件や他の隣接交差点に対する処理へと移行する。
【００５５】
Ｓ９においてＣＰＵ４１は、隣接交差点に現時点で対応づけられているコスト値Ｔを、前記Ｓ７で算出された加算値Ｃへと更新する。
【００５６】
また、Ｓ１０においてＣＰＵ４１は、隣接交差点に対応づけられている直前交差点を、現在の中心交差点へと更新する。
【００５７】
更に、Ｓ１１においてＣＰＵ４１は、隣接交差点に対応づけられている候補フラグを“ＯＮ（１）”に設定する。即ち、該隣接交差点は、新たな中心交差点の候補となる。
【００５８】
そして、交差点リストにリストアップされた交差点の内、中心交差点に隣接する全ての隣接交差点、且つ全ての探索条件に対して、前記Ｓ６〜Ｓ１１の処理が行われた後には、Ｓ３へと戻る。
【００５９】
例えば、出発地交差点Ａが前記Ｓ３で中央交差点に設定された場合には、図７に示すように出発地交差点Ａに隣接する交差点Ｂと交差点Ｃに対して前記Ｓ６〜Ｓ１１の処理が実行される。そして、探索条件毎に、図２に示すリンクコストに基づいて新たなコスト値Ｔが対応付けられ、直前交差点には交差点Ａが対応付けられ、候補フラグは“ＯＮ（１）”に設定される。その後、Ｓ３の処理が行われると、『一般優先』の交差点リストの交差点Ｂに対応付けられたコスト値Ｔが“８”で最も小さいことから、交差点Ｂが新たな中心交差点に設定されＳ４以降の処理が実行されることとなる。そして、先ず図８に示すように新たに中心交差点に設定された交差点Ｂの候補フラグが“ＯＦＦ（０）”に設定される（Ｓ５）。その後、図９に示すように新たに中心交差点に設定された交差点Ｂに隣接する交差点Ｃ、交差点Ｄ、交差点Ｅに対してＳ６〜Ｓ１１の処理が実行される。以下同様に、中心交差点が目的地交差点となるまで繰り返し処理を実行する。
【００６０】
そして、前記Ｓ４の判定処理において前記Ｓ３で新たに中心交差点に設定された交差点が目的地交差点であると判定された場合に実行されるＳ１２では、ＣＰＵ４１は、交差点リストに含まれる交差点の内、候補フラグが“ＯＮ（１）”であって（即ち、中心交差点の候補となりながら中心交差点に設定されなかった交差点であって）、且つ少なくとも一の探索条件で目的地交差点より小さいコスト値Ｔが対応付けられた交差点（以下、処理対象交差点という）があるか否か判定する。
【００６１】
そして、交差点リストに含まれる交差点の内、処理対象交差点があると判定された場合（Ｓ１２：ＹＥＳ）には、Ｓ１３へと移行する。一方、交差点リストに含まれる交差点の内、処理対象交差点が無いと判定された場合（Ｓ１２：ＮＯ）には、Ｓ１４へと移行する。
【００６２】
Ｓ１３においてＣＰＵ４１は、処理対象交差点を中心交差点に設定する。その後、前記Ｓ１３で新たに設定された中心交差点に基づいて、Ｓ５以降の処理を実行する。その後、Ｓ１２の判定処理で処理対象交差点が無いと判定されるまで、Ｓ１３以降の処理を繰り返し実行する。尚、Ｓ１３以降の処理は、処理対象交差点があると判定された探索条件（例えば、図１０に示す例では『推奨』と『有料道路優先』の２つ）の交差点リストのみを対象として実行しても良い。
【００６３】
例えば、図１０は中心交差点が交差点Ｇに設定された状態で前記Ｓ４〜Ｓ１１の処理が行われた後の交差点リストを示した図である。図１０に示す交差点リストでは、候補フラグが“ＯＮ（１）”に設定された交差点の内で、探索条件に関わらず最小のコスト値Ｔが対応付けられた交差点は目的地交差点Ｉとなるので、前記Ｓ３で目的地交差点Ｉが中心交差点に設定される。しかしながら、『推奨』と『有料道路優先』の交差点リストでは、候補フラグが“ＯＮ（１）”であって、且つ目的地交差点より小さいコスト値Ｔが対応付けられた交差点（処理対象交差点）Ｈが存在するので、次に、交差点Ｈを新たな中心交差点に設定し（Ｓ１３）、Ｓ５以降の処理が実行される。その結果、図１１に示すように交差点Ｈに隣接する交差点Ｇと交差点Ｉに対してＳ６〜Ｓ１１の処理が実行される。
その後、前記Ｓ１３以降の処理を実行した結果、再度Ｓ３において目的地交差点Ｉが中心交差点に設定され、Ｓ１２の判定処理へと移行することとなる。図１１に示す交差点リストでは、候補フラグが“ＯＮ（１）”であって、且つ目的地交差点より小さいコスト値Ｔが対応付けられた処理対象交差点が、何れの探索条件においても存在しないので、Ｓ１２の判定処理でＮＯと判定され、Ｓ１４へと移行する。
【００６４】
Ｓ１４においてＣＰＵ４１は、図１２に示すように中心交差点（目的地交差点）に対応付けられた候補フラグを“ＯＦＦ（０）”に設定する。
【００６５】
その後、Ｓ１５においてＣＰＵ４１は、最終的な交差点リストに基づいて、探索条件毎に、目的地交差点から出発地交差点まで直前交差点を結んだ経路を適合経路に特定する。その結果、出発地交差点から目的地交差点までの探索コストの加算値が最小となる経路が適合経路として探索条件毎に特定されることとなる。例えば、図１２に示す交差点リストが最終的に得られた場合には、『推奨』の探索条件の適合経路として、交差点Ａ→交差点Ｂ→交差点Ｅ→交差点Ｇ→交差点Ｉを結んだ経路が特定される。また、『有料道路優先』の探索条件の適合経路として、交差点Ａ→交差点Ｃ→交差点Ｆ→交差点Ｈ→交差点Ｉを結んだ経路が特定される。また、『一般優先』の探索条件の適合経路として、交差点Ａ→交差点Ｂ→交差点Ｃ→交差点Ｅ→交差点Ｄ→交差点Ｇ→交差点Ｉを結んだ経路が特定される。
【００６６】
尚、前記Ｓ１５で特定された探索条件毎の適合経路は、液晶ディスプレイ１５等を介してユーザに案内される。そして、その後のユーザの操作に基づいて選択された一の適合経路がナビゲーション装置１の案内経路として設定され、設定された案内経路に基づく走行案内が行われる。
【００６７】
以上詳細に説明した通り、本実施形態に係るナビゲーション装置１、ナビゲーション装置１による経路探索方法及びナビゲーション装置１で実行されるコンピュータプログラムでは、出発地交差点から目的地交差点まで至る適合経路の候補を接続する交差点のリストである交差点リストを作成し（Ｓ１）、出発地交差点を最初の中心交差点に設定し（Ｓ３）、交差点リストに含まれる交差点であって且つ中心交差点に隣接する交差点である隣接交差点について、出発地交差点から該隣接交差点への探索コストの加算値を複数の探索条件毎且つ該隣接交差点毎に算出し（Ｓ６〜Ｓ９）、算出された複数の探索条件毎の探索コストの加算値を比較し、探索条件に関わらず探索コストの加算値が最小となる隣接交差点を新たな中心交差点に設定し（Ｓ３）、新たに設定された中心交差点が目的地交差点となった場合に、交差点リストに含まれる交差点の内、過去に中心交差点に設定されておらず、且つ、算出された探索コストの加算値が目的地交差点よりも小さくなる交差点である処理対象交差点があるか否か判定し（Ｓ１２）、処理対象交差点があると判定された場合に、該処理対象交差点を新たな中心交差点に設定してコスト算出の処理を継続して実行し（Ｓ１３）、出発地交差点から目的地交差点までの探索コストの加算値が最小となる経路を適合経路として探索条件毎に特定する（Ｓ１５）ので、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する際に、探索条件毎に同様の経路探索処理を一から繰り返し実行する必要が無く、経路探索処理に係る処理時間や処理負担を軽減することが可能となる。
また、交差点判定手段によって処理対象交差点が無いと判定されるまで、処理対象交差点を中心交差点としたコスト算出の処理を繰り返し実行するので、複数の探索条件に対するコスト算出を同時に行う場合であっても、出発地交差点から交差点リストに含まれる各交差点に至る探索コストの最小加算値を正確に算出することが可能となる。その結果、出発地交差点から目的地交差点までの探索コストの加算値が最小となる経路を適合経路として適切に特定することが可能となる。
また、交差点リストを複数の探索条件毎に区分した複数のリストにより作成するので、複数の探索条件毎に該探索条件に適合する経路をそれぞれ特定する場合であっても、複数の交差点リストを用いて探索条件毎の適合経路を従来に比べてより少ない処理工程で特定することが可能となる。
【００６８】
尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では、３種類の探索条件毎に適合経路を特定する構成としているが、２種類又は４種類以上の探索条件毎に適合経路を特定する構成としても良い。尚、その場合には交差点リストを探索条件の数に対応させて作成する必要がある。
【００６９】
また、本実施形態では交差点リストを複数の探索条件毎に区分した複数のリストにより作成することとしているが、交差点リストを交差点リストに含まれる各交差点に対して複数の探索条件を対応付けた一のリストにより作成しても良い。例えば、図１３は図１２に示す交差点リストを一のリストで作成した例を示す。図１３に示す交差点リストを用いた場合であっても、上記本実施形態と同様に探索条件毎の適合経路を従来に比べてより少ない処理工程で特定することが可能となる。
【００７０】
また、本実施形態では、リンクを走行するのに必要なリンクコストのみを考慮して探索コストの加算値Ｃを算出する構成としているが、交差点を通過するのに必要な交差点コストやその他のコストについても考慮して探索コストの加算値Ｃを算出する構成としても良い。
【００７１】
また、本発明はナビゲーション装置以外に、経路探索機能を有する装置に対して適用することが可能である。例えば、携帯電話機やスマートフォン等の携帯端末、パーソナルコンピュータ等（以下、携帯端末等という）に適用することも可能である。また、サーバと携帯端末等から構成されるシステムに対しても適用することが可能となる。その場合には、上述した経路探索処理プログラム（図２）の各ステップは、サーバと携帯端末等のいずれが実施する構成としても良い。また、本発明を携帯端末等に適用する場合には、車両以外の移動体、例えば、携帯端末等のユーザや２輪車等に対する経路の探索にも本願発明を適用することが可能である。
【符号の説明】
【００７２】
１              ナビゲーション装置
１３            ナビゲーションＥＣＵ
４１            ＣＰＵ
４２            ＲＡＭ
４３            ＲＯＭ
【図１】
2014044156.tif 000003
【図２】
2014044156.tif 000004
【図３】
2014044156.tif 000005
【図４】
2014044156.tif 000006
【図５】
2014044156.tif 000007
【図６】
2014044156.tif 000008
【図７】
2014044156.tif 000009
【図８】
2014044156.tif 000010
【図９】
2014044156.tif 000011
【図１０】
2014044156.tif 000012
【図１１】
2014044156.tif 000013
【図１２】
2014044156.tif 000014
【図１３】
2014044156.tif 000015