(57)【要約】【課題】現在位置と経由地との間に突発的に事故傷害等が発生したとしても、いずれの経由地へも効率的に到達できる経路探索装置を提供する。【解決手段】車両の現在位置を示す位置データを取得し、車両が移動する予定の複数の経由地Ａ及び経由地Ｂを示す地点データをそれぞれ取得し、各位置データ及び地点データに基づいて、経由地Ａ及び経由地Ｂを経由して車両が移動可能な経路であって、各経由地を移動する順番が相互に異なる複数の経路を探索する。その後、探索された各経路に基づいて、現在位置と各経由地との間にある分岐点であって現在位置からその分岐点を通過していずれの経由地へも到達可能な分岐点Ｊ１を決定する。そして、現在位置と分岐点Ｊ１との間の距離が既定の閾値距離以下となったとき、分岐点Ｊ１を通って経由点Ａ及び経由点Ｂに到達するための経路を探索する。【選択図】図３
2016194430.tif 000002
【特許請求の範囲】
【請求項１】
移動体の現在位置を示す現在位置情報を取得する位置情報取得手段と、
複数の地点についての地点情報を取得する地点情報取得手段と、
前記現在位置情報及び前記地点情報に基づいて、前記複数の地点を通る複数の移動可能経路を探索する可能経路探索手段と、
前記複数の移動可能経路に基づいて、前記現在位置と前記複数の地点との間にあり、前記複数の地点のうちいずれの地点へも到達可能な分岐点を決定する決定手段と、
前記現在位置と前記決定された分岐点との間の距離が前記移動体の移動により予め設定された閾値距離以下となったとき、当該分岐点を通って各前記地点に到達するための分岐点通過経路を決定する分岐点経路決定手段と、
を備えること特徴とする経路探索装置。
【請求項２】
請求項１に記載の経路探索装置において、
結節点を含む経路データを取得するデータ取得手段と、
前記経路データ中の前記結節点から、前記分岐点の候補となる候補点を抽出する抽出手段と、
を更に備え、
前記決定手段は、一の前記候補点を通り且つ前記複数の地点への到達順が異なる複数の前記移動可能経路それぞれの間で、経路としての選択され難さを示す被選択指標の差が予め設定された閾値指標以下となる経路上の前記候補点のうち、当該候補点から前記複数の地点への到達順が異なる複数の経路の前記被選択指標の合計が最も小さくなる当該候補点を、前記分岐点として決定することを特徴とする経路探索装置。
【請求項３】
請求項２に記載の経路探索装置において、
前記抽出手段は、前記現在位置を基準として予め設定された地理的範囲内にある前記経路データ内の前記結節点を前記候補点として抽出することを特徴とする経路探索装置。
【請求項４】
請求項１から請求項３のいずれか一項に記載の経路探索装置において、
前記決定手段により決定された前記分岐点への到達予定時刻を示す到達予定時刻情報を取得する予定時刻情報取得手段と、
前記到達予定時刻以前に前記分岐点へ前記移動体が到達できるか否かを判定する判定手段と、
を更に備え、
前記分岐点経路決定手段は、前記判定手段による判定結果に応じて異なる前記分岐点通過経路を決定することを特徴とする経路探索装置。
【請求項５】
移動体が移動する経路を探索する経路探索装置において実行される経路探索方法において、
前記移動体の現在位置を示す現在位置情報を取得する位置情報取得工程と、
複数の地点についての地点情報を取得する地点情報取得工程と、
前記現在位置情報及び前記地点情報に基づいて、前記複数の地点を通る複数の移動可能経路を探索する可能経路探索工程と、
前記複数の移動可能経路に基づいて、前記現在位置と前記複数の地点との間にあり、前記複数の地点のうちいずれの地点へも到達可能な分岐点を決定する決定工程と、
前記現在位置と前記決定された分岐点との間の距離が前記移動体の移動により予め設定された閾値距離以下となったとき、当該分岐点を通って各前記地点に到達するための分岐点通過経路を決定する分岐点経路決定工程と、
を含むこと特徴とする経路探索方法。
【請求項６】
コンピュータを、請求項１から請求項４のいずれか一項に記載の経路探索装置として機能させることを特徴とする経路探索用プログラム。
【請求項７】
請求項６に記載の経路探索用プログラムが前記コンピュータで読み取り可能に記録されていることを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、経路探索装置、経路探索方法並びに経路探索用プログラム及び記録媒体の技術分野に属し、より詳細には、移動体の移動を案内する経路を探索する経路探索装置及び経路探索方法並びに当該経路探索装置用のプログラム及び当該プログラムが記録された記録媒体の技術分野に属する。
【背景技術】
【０００２】
近年、車両に搭載されて当該車両の移動を案内するナビゲーション装置が広く一般化している。そして当該案内に際しては、上記移動の目的地と出発地（又は現在地）が入力されると、当該出発地又は現在地から目的地までの案内経路が設定され、当該案内に用いられる。このような案内経路の設定についての先行技術文献としては例えば下記特許文献１及び下記特許文献２が挙げられる。
【０００３】
このとき下記特許文献１には、複数の経由地を指定し、経由順の異なる複数ルートを探索すること、探索したルートが予め設定してある条件に合致するかどうか判断し、更に当該条件に合うように修正すること、及び経由地を含む複数のルートを探索することが記載されている。また下記特許文献２に記載の技術では、現在地から目的地に至るまでにある経由地を、効率よく訪れることができるようなルートを探索する構成とされている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−２３３６３２号公報
【特許文献２】特開平９−１０１１６８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、上記特許文献１及び上記特許文献２にそれぞれ記載されている技術は、複数の経由地を含む経路を探索する技術であり、特に上記特許文献１には、経由地を巡る順番が異なる複数のルートを探索することが記載されている。
【０００６】
しかしながら上記特許文献１記載の技術では、例えば案内途中でユーザの予定が変更され、二番目の経由地に先に行く必要が出てきた場合や、最初の経由地と二番目の経由地のどちらから先に行くかをユーザが迷っている場合等には対応できないという問題点がある。
【０００７】
また上記特許文献２記載の技術では、案内中に突発的な渋滞等が発生した際に経路の再探索を行うと、反って効率の悪い経路となる可能性があるという問題点がある。このとき、いわゆる渋滞情報を加味して最適なルートを探索することも一般的な技術だが、渋滞の状況等は時々刻々と変わってしまうことが多いため、その時点で最適な案内経路を探索するのは難しい。
【０００８】
そこで本願は、上記の各問題点に鑑みて為されたもので、その課題の一例は、例えば現在位置と経由地との間に突発的に事故傷害等が発生したとしても、いずれの経由地へも効率的に到達でき、また各経由地への到達順が決まっていない場合でもいずれの経由地へも効率的に到達できる経路探索装置及び経路探索方法並びに当該経路探索装置用のプログラム及び当該プログラムが記録された記録媒体を提供することにある。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、請求項１に記載の発明は、移動体の現在位置を示す現在位置情報を取得する位置情報取得手段と、複数の地点についての地点情報を取得する地点情報取得手段と、前記現在位置情報及び前記地点情報に基づいて、前記複数の地点を通る複数の移動可能経路を探索する可能経路探索手段と、前記複数の移動可能経路に基づいて、前記現在位置と前記複数の地点との間にあり、前記複数の地点のうちいずれの地点へも到達可能な分岐点を決定する決定手段と、前記現在位置と前記決定された分岐点との間の距離が前記移動体の移動により予め設定された閾値距離以下となったとき、当該分岐点を通って各前記地点に到達するための分岐点通過経路を決定する分岐点経路決定手段と、を備える。
【００１０】
上記の課題を解決するために、請求項５に記載の発明は、移動体が移動する経路を探索する経路探索装置において実行される経路探索方法において、前記移動体の現在位置を示す現在位置情報を取得する位置情報取得工程と、複数の地点についての地点情報を取得する地点情報取得工程と、前記現在位置情報及び前記地点情報に基づいて、前記複数の地点を通る複数の移動可能経路を探索する可能経路探索工程と、前記複数の移動可能経路に基づいて、前記現在位置と前記複数の地点との間にあり、前記複数の地点のうちいずれの地点へも到達可能な分岐点を決定する決定工程と、前記現在位置と前記決定された分岐点との間の距離が前記移動体の移動により予め設定された閾値距離以下となったとき、当該分岐点を通って各前記地点に到達するための分岐点通過経路を決定する分岐点経路決定工程と、を含む。
【００１１】
上記の課題を解決するために、請求項６に記載の発明は、コンピュータを、請求項１から請求項４のいずれか一項に記載の経路探索装置として機能させる。
【００１２】
上記の課題を解決するために、請求項７に記載の発明は、請求項６に記載の経路探索用プログラムが前記コンピュータで読み取り可能に記録されている。
【図面の簡単な説明】
【００１３】
【図１】実施形態に係る経路探索装置の概要構成を示すブロック図である。
【図２】第１実施例に係るナビゲーション装置の概要構成を示すブロック図である。
【図３】第１実施例に係る経路探索の対象となる道路の一例を示す図である。
【図４】第１実施例に係る経路探索処理を示すフローチャートである。
【図５】第１実施例に係る分岐点決定処理を示すフローチャートである。
【図６】第１実施例に係る分岐点決定処理を説明する図であり、（ａ）は当該分岐点決定処理におけるノードの抽出を例示する図であり、（ｂ）は当該分岐点決定処理における分岐点候補の検索を例示する図であり、（ｃ）は当該分岐点候補の決定を例示する図である。
【図７】第２実施例に係る経路探索処理を示すフローチャートであり、（ａ）は当該経路探索処理の全体を示すフローチャートであり、（ｂ）は第２実施例に係る分岐点決定処理を示すフローチャートである。
【図８】第２実施例に係る分岐点決定処理を説明する図であり、（ａ）は当該分岐点決定処理の第１例を示す図であり、（ｂ）は当該分岐点決定処理の第２例を示す図であり、（ｃ）は当該分岐点候補の例を示す図である。
【図９】第３実施例に係る経路探索処理を示すフローチャートである。
【発明を実施するための形態】
【００１４】
次に、本願を実施するための形態について、図１を用いて説明する。なお図１は、実施形態に係る経路探索装置の概要構成を示すブロック図である。
【００１５】
図１に示すように、実施形態に係る経路探索装置Ｓは、位置情報取得手段１と、地点情報取得手段２と、可能経路探索手段３と、決定手段４と、分岐点経路決定手段５と、を備えて構成されている。
【００１６】
この構成において位置情報取得手段１は、移動体の現在位置を示す現在位置情報を取得する。
【００１７】
一方地点情報取得手段２は、複数の地点についての地点情報を取得する。
【００１８】
そして可能経路探索手段３は、上記現在位置情報及び上記地点情報に基づいて、複数の地点を通る複数の移動可能経路を探索する。
【００１９】
これにより決定手段４は、上記複数の移動可能経路に基づいて、上記現在位置と上記複数の地点との間にあり、上記複数の地点のうちいずれの地点へも到達可能な分岐点を決定する。
【００２０】
そして分岐点経路決定手段５は、上記現在位置と上記分岐点との間の距離が移動体の移動により予め設定された閾値距離以下となったとき、当該分岐点を通って各地点に到達するための分岐点通過経路を決定する。
【００２１】
以上説明したように、実施形態に係る経路探索装置Ｓの動作によれば、複数の移動可能経路に基づいて、移動体の現在位置から分岐点を通過していずれの地点へも到達可能な当該分岐点を決定し、現在位置と分岐点との間の距離が閾値距離以下となったとき、分岐点を通って各地点に到達するための分岐点通過経路を探索する。よって、いずれの地点へも到達可能な分岐点を決定し、その分岐点までの距離が閾値距離以下となったとき分岐点通過経路を探索するので、例えば現在位置と各地点との間に突発的に移動傷害が発生したとしても、いずれの地点へも効率的に到達できる。また、移動中における各地点への到達順が決まっていない場合でも、分岐点通過経路を通ることで、いずれの地点へも効率的に到達できる。
【実施例】
【００２２】
次に、上述した実施形態に対応する具体的な実施例について、図２乃至図９を用いて説明する。なお以下に説明する各実施例は、車両又は自転車等と共に移動するナビゲーション装置における経路探索処理に実施形態を適用した場合の実施例である。このとき、上記車両又は自転車等が実施形態に係る移動体の一例に相当する。
【００２３】
（１）第１実施例
始めに、実施形態に係る第１実施例について、図２乃至図６を用いて説明する。なお、図２は第１実施例に係るナビゲーション装置の概要構成を示すブロック図であり、図３は第１実施例に係る経路探索の対象となる道路の一例を示す図である。また、図４は第１実施例に係る経路探索処理を示すフローチャートであり、図５は第１実施例に係る分岐点決定処理を示すフローチャートであり、図６は第１実施例に係る分岐点決定処理を説明する図である。このとき図２では、図１に示した実施形態に係る経路探索装置Ｓにおける各構成部材に対応する実施例の構成部材それぞれについて、当該経路探索装置Ｓにおける各構成部材と同一の部材番号を用いている。
【００２４】
図２に示すように、第１実施例に係るナビゲーション装置ＮＶは、ＣＰＵ、ＲＡＭ（Random Access Memory）及びＲＯＭ（Read Only Memory）等からなり且つ実施形態に係る経路探索装置Ｓの一例並びに本願に係る「データ取得手段」の一例、本願に係る「判定手段」の一例及び本願に係る「抽出手段」の一例にそれぞれ相当する処理部Ｓと、ＨＤＤ（Hard Disc Drive）又はＳＳＤ（Solid State Drive）等からなる記録部１０と、ナビゲーション装置ＮＶと図示しないインターネット等のネットワークとを接続し相互のデータ授受を制御するインターフェース１１と、ナビゲーション装置ＮＶが搭載されている車両の現在位置を示す位置データ等を出力するセンサ１２と、操作ボタン及びリモコン並びにタッチパネル等からなり且つ本願に係る「予定時刻情報取得手段」の一例に相当する操作部１３と、液晶ディスプレイ等からなるディスプレイ１４と、により構成されている。
【００２５】
この構成において上記記録部１０には、ナビゲーション装置ＮＶにおける案内処理（後述する第１実施例に係る経路探索処理を含む）に用いられる地図データＤや音声データ等を含むナビゲーション用データと、当該案内処理を実行するためのプログラム等が不揮発性に記録されている。またセンサ１２は、例えば図示しないＧＰＳ（Global Positioning System）航法衛星からの航法電波を受信する方法や図示しない加速度センサ等からの出力を用いた自律的な方法を用いて上記現在位置を検出し、当該現在位置を示す上記位置データを生成して処理部Ｓに出力する。これにより処理部Ｓは、操作部１３において行われたユーザの操作に基づき、上記位置データ及び上記地図データＤ等、並びにインターフェース１１を介して外部から取得された渋滞の発生状況等を示す渋滞情報や道路情報等を用いて、第１実施例に係る案内処理を統括的に制御する。このとき当該案内処理において上記ユーザに提示すべき地図等は、処理部Ｓの制御の下、ディスプレイ１４に表示される。
【００２６】
次に、より具体的に処理部Ｓは、実施形態に係る位置情報取得手段１の一例に相当する位置情報取得部１と、実施形態に係る地点情報取得手段２の一例に相当する地点情報取得部２と、実施形態に係る可能経路探索手段３の一例に相当する可能経路探索部３と、実施形態に係る決定手段４の一例及び本願に係る「分岐点決定手段」の一例にそれぞれ相当する決定部４と、実施形態に係る分岐点経路決定手段５の一例に相当する分岐点経路決定部５と、により構成されている。このとき、上記位置情報取得部１、上記地点情報取得部２、上記可能経路探索部３、上記決定部４及び上記分岐点経路決定部５はそれぞれ、処理部Ｓを構成する上記ＣＰＵ等のハードウェアロジック回路により実現されていてもよいし、後述する第１実施例に係る経路探索処理に相当するプログラムを上記ＣＰＵ等が読み出して実行することにより、ソフトウェア的に実現されるものであってもよい。
【００２７】
そして、上記第１実施例に係る経路探索処理として位置情報取得部１は、センサ１２から上記位置データを取得する。一方地点情報取得部２は、ナビゲーション装置ＮＶが搭載されている上記車両が移動する予定の複数の経由地を示す経由地データを、例えば地図データＤから又は上記ネットワークを介して、それぞれ取得する。このとき当該経由地データは、操作部１３における上記ユーザによる経由地指定操作に対応して地図データＤ等から取得されるのが好適である。そして可能経路探索部３は、上記位置データ及び上記経由地データに基づいて、複数の上記経由地を経由して車両が移動する経路を複数探索する。このとき当該各経路については、上記各経由地を経由する順番を相互に異ならせる。
【００２８】
これらにより決定部４は、可能経路探索部３によりそれぞれ探索された経路に基づき、車両の現在位置と各経由地との間の経路上にある分岐点（交差点）であって現在位置から当該分岐点を通過していずれの経由地へも到達可能な分岐点を決定する。そして分岐点経路決定部５は、現在位置と上記決定された分岐点との間の距離が予め設定された閾値距離以下となったとき、当該分岐点を通って各経由地に到達するための経路を決定する。
【００２９】
次に、第１実施例に係る経路探索処理の原理について図３を用いて説明する。
【００３０】
即ち図３に例示するように、上向き三角形の現在位置マークにより示される現在位置Ｃに、ナビゲーション装置ＮＶを搭載した車両が存在するとする。また図３において、現在位置Ｃに存在する車両は事後の移動により経由地Ａと経由地Ｂとを経由する予定であるが、経由地Ａと経由地Ｂのいずれを先に経由するかは任意であるとする。そして、当該車両が事後に移動し得る道路としては、図３に例示する道路ＲＣＡ、道路ＲＣＢ、道路ＲＣＪ１、道路ＲＢＪ１、道路ＲＡＪ１及び道路ＲＡＢがある。このとき、道路ＲＣＡ、道路ＲＡＢ及び道路ＲＡＪ１が経由地Ａで交差しており、道路ＲＣＢ、道路ＲＢＪ１及び道路ＲＡＢが経由地Ｂで交差しており、更に道路ＲＣＪ１、道路ＲＡＪ１及び道路ＲＢＪ１が交差点Ｊ１で交差している。
【００３１】
このとき、図３に例示するように、経由地Ａ及び経由地Ｂに到達すべきではあるが、その到達順が任意である場合、車両が移動すべき経路は、経由地Ａ及び経由地Ｂを含んで複数が考えられる。このような場合、例えば全体としての移動距離又は移動時間を短くするため、経由地Ａ⇒経由地Ｂの順で経由するとして、最初の経由地Ａに向けて道路ＲＣＡ上を移動したとする。そして、道路ＲＣＡ上を経由地Ａに向けてある程度進んだ後に、その前方で事故等の移動障害が発生してそれ以上の道路ＲＣＡ上の移動ができなくなったとする。このような車両としては、一旦元の場所に戻って道路ＲＣＪ１又は道路ＲＣＢ上を進むしかなくなり、結果的に経由地Ａ又は経由地Ｂへの到達が遅くなってしまうといったことが生じる。
【００３２】
そこで第１実施例に係る経路探索処理では、図３に例示する経由地Ａ及び経由地Ｂを経由する場合に、移動の途中までは経由地Ａ及び経由地Ｂの双方に到達し得る道路を進み、途中の分岐点でその時点での道路状態や渋滞の発生状況等に基づいてその後の経路を探索する。より具体的に図３に例示する場合では、先ず経由地Ａ及び経由地Ｂへの分岐点である交差点Ｊ１まで現在位置Ｃから移動するように案内し、その後、上記道路状態等に応じて、道路ＲＡＪ１又は道路ＲＢＪ１のいずれか一方を進むように案内する。
【００３３】
次に、第１実施例に係る経路探索処理について、より具体的に図２乃至図６を用いて説明する。なお以下に説明する経路探索処理においてナビゲーション装置ＮＶが搭載された車両は、図６（ａ）左に例示する現在位置Ｃに存在しており、その後、当該図６（ａ）に例示する経由地Ａ及び経由地Ｂの双方を経由して移動するものとする。なおこの場合でも経由地Ａと経由地Ｂのいずれを先に経由するかは任意であるとする。
【００３４】
また図６に例示する場合の車両が移動し得る道路としては、図３に例示した場合と異なり、道路ＲＣＡ、道路ＲＣＢ、道路ＲＣＪ２、道路ＲＢＪ２、道路ＲＡＪ２、道路ＲＪ１Ｊ２、道路ＲＢＪ１、道路ＲＡＪ１及び道路ＲＡＢがある。また、道路ＲＣＡ、道路ＲＡＢ、道路ＲＡＪ１及び道路ＲＡＪ２が経由地Ａで交差しており、道路ＲＣＢ、道路ＲＡＢ、道路ＲＢＪ１及び道路ＲＢＪ２が経由地Ｂで交差しており、道路ＲＪ１Ｊ２、道路ＲＡＪ１及び道路ＲＢＪ１が交差点Ｊ１で交差しており、道路ＲＪ１Ｊ２、道路ＲＡＪ２、道路ＲＢＪ２及び道路ＲＣＪ２が交差点Ｊ２で交差している。
【００３５】
図４に対応するフローチャートを示すように、第１実施例に係る経路探索処理は、例えば操作部１３における指示操作に基づいて開始される。そして、当該経路探索処理が開始されると先ず処理部Ｓは、上記経由地Ａ及び上記経由地Ｂを、例えば各経由地の位置を示す位置情報等を取得することにより設定する（ステップＳ１）。このとき当該位置情報等は、地点情報取得部２により取得された後、記録部１０に一時的に記録される。次に処理部Ｓは当該車両の現在位置を取得する（ステップＳ２）。このときの当該現在位置を示す位置データは、上記位置情報取得部１によりセンサ１２から取得される。
【００３６】
次に処理部Ｓの上記可能経路探索部３及び上記決定部４は、経由地Ａ及び経由地Ｂの双方に到達し得る道路の上記分岐点を、上記地図データＤ等を用いて決定する（ステップＳ３）。当該決定された分岐点を示す分岐点データは記録部１０に一時的に記録される。このステップＳ３については、後ほど詳述する。
【００３７】
その後処理部Ｓは、当該決定された分岐点までの現在位置Ｃからの経路を探索する（ステップＳ４）。その後処理部Ｓは、予め設定された閾値距離まで当該決定された分岐点に近付いたか否かを監視する（ステップＳ５、ステップＳ５；ＮＯ）。ここで上記閾値距離について具体的には、例えば、各道路を構成する地図データＤとしてのノードデータに基づき、その分岐点に相当するノードの一つ前のノードと当該分岐点に相当するノードとの間の距離とするのが好適である。なお、分岐点までが例えば長い一本道であり、従って当該分岐点までの間にノードが存在しないような場合には、例えば、
（ア）「分岐点到達前２０秒の位置から分岐点までの距離」や「分岐点まで５００メートル」といった経験的な値を用いる、
（イ）ナビゲーション装置ＮＶのユーザが操作部１３を用いて、例えば「分岐点まで○秒の距離」或いは「分岐点まで○○メートル」といった任意の値を設定する、或いは、
（ウ）上記一本道中のカーブに差し掛かったら分岐点付近と判断する、
といった方法により上記閾値距離を設定することが考えられる。
【００３８】
そして、車両が当該閾値距離まで分岐点に近付いたことが検出されたら（ステップＳ５；ＹＥＳ）、処理部Ｓは例えばインターフェース１１を介して、その時点での渋滞状況を示す情報や道路情報等を取得する（ステップＳ６）。その後処理部Ｓの分岐点経路決定部５は、ステップＳ６で取得した渋滞状況を示す情報等及び地図データＤに基づき、前方の分岐点から経由地Ａ及び経由地Ｂを経由する経路を改めて一又は複数探索する（ステップＳ７）。その後処理部Ｓは、探索された新たな経路（分岐点を経由する経路）のそれぞれのうち、当該経由地Ａ等を経由して移動することについての移動コストが最も小さい経路を抽出し、当該抽出された経路を示す情報を例えばディスプレイ１４を用いて提示（出力）する（ステップＳ８）。その後処理部Ｓは、当該提示された経路を示す情報に基づいた操作部１３におけるユーザの操作により選択された経路を案内経路とする車両の案内を開始する。
【００３９】
ここで上記「移動コスト」とは、案内経路に沿った車両の案内をする場合に、その移動コストを有するとされる経路（道路）の、上記案内経路としての選択（採用）され難さを示す指標であり、移動コストが高いほど案内経路として選択され難い（換言すれば、移動コストが低いほど案内経路として選択され易い）経路であることになる。この移動コストは、具体的には例えば、到達すべき地点までの距離、所要時間及び通行料等をその経路について数値化し、それらを正規化した指標である。
【００４０】
次に上記ステップＳ３の分岐点決定処理について、具体的に図５及び図６を用いて説明する。
【００４１】
上記ステップＳ３の分岐点決定処理として具体的に処理部Ｓの決定部４は、図５に示すように、先ず上記地図データＤに含まれているノードについて、車両の現在位置Ｃに基づいて、予め設定された範囲内にある経路上の全てのノードを検出する（ステップＳ３０）。このステップＳ３０では例えば、到達予定の経由地Ａ及び経由地Ｂを含むと共に、車両の現在位置Ｃから最も近い経由地（例えば図６（ａ）左に例示する道路の場合、経由地Ａ）と当該現在位置Ｃとの間の直線距離を半径とし、当該現在位置Ｃをその中心とする円の内部を上記予め設定された範囲内とするのが好適である。なおこの他に上記予め設定された範囲としては、例えば、車両の進行方向を中心として左右に拡がる扇形で且つ上記直線距離を半径とする扇形の範囲とすることが考えられる。そして、図６（ａ）に例示する場合の上記ステップＳ３０により抽出されるノードとしては、例えば図６（ａ）右に例示するノードＮ１、ノードＮ２、ノードＮ５、ノードＮ３及びノードＮ４となる。この場合、ノードＮ１が経由地Ａに相当し、ノードＮ２が経由地Ｂに相当し、ノードＮ５が現在位置Ｃに相当し、ノードＮ３が交差点Ｊ１に相当し、ノードＮ４が交差点Ｊ２に相当する。
【００４２】
次に決定部４は、ノードＮの番号を示すパラメータｎを初期化する（ステップＳ３１）。なお当該パラメータｎの初期値は「１」であり、またその最大値は上記ステップＳ３０により抽出されたノードの数（図６に例示する場合は５）である。
【００４３】
そして決定部４は、ノードＮｎから経由地Ａ⇒経由地Ｂと移動する経路のうち移動コストが最小となる経路（例えば図６（ｂ）左に太い実線で示すノードＮ４を起点とした経路Ｒ１）と、ノードＮｎから経由地Ｂ⇒経由地Ａと移動する経路のうち移動コストが最小となる経路（例えば図６（ｂ）中に破線で示すノードＮ４を起点とした経路Ｒ２）と、を探索する（ステップＳ３２）。そして決定部４は、その時点で探索した二つの経路（図６（ｂ）に例示する場合は経路Ｒ１と経路Ｒ２）の間の移動コストの差が予め設定された閾値コスト以下であるか否かを判定する（ステップＳ３３）。このとき、当該閾値コストとして具体的には、例えば図６（ｂ）に示す例を引用すると、
（エ）０．５＜経路Ｒ１の移動コスト／経路Ｒ２の移動コスト＜２とする（即ち、経路Ｒ１と経路Ｒ２の移動コストの差が倍以上になってしまうノードについては、後述する分岐点の候補から除外する）、或いは、
（オ）移動コストとしての所要時間の差をユーザに手動で設定させ、経路Ｒ１と経路Ｒ２との間の移動コストとしての所要時間差の絶対値が上記ユーザにより設定された差以内であれば、後述する分岐点の候補とする、
といった方法が考えられる。ステップＳ３３の判定において、その時点で探索した二つの経路の間の移動コストの差が上記閾値コストより大きい場合（ステップＳ３３；ＮＯ）、決定部４は後述するステップＳ３６に移行する。一方ステップＳ３３の判定において、当該二つの経路の間の移動コストの差が上記閾値コスト以下である場合（ステップＳ３３；ＹＥＳ）、決定部４は、当該二つの経路それぞれについての移動コストを加算して当該ノードＮｎについての合計移動コストＣｎを算出し、その値を一時的に記録部１０に記録する（ステップＳ３４）。その後決定部４は、上記二つの経路の起点となっているノードＮｎを分岐点の候補として設定する（ステップＳ３５）。このステップＳ３５における分岐点の候補についての情報も記録部１０に一時的に記録される。また図６に例示する場合は、経路Ｒ１及び経路Ｒ２の起点となっているノードＮ４が分岐点の候補となっている（図６（ｂ）右ハッチング参照）。
【００４４】
次に決定部４は、その時点でのパラメータｎの値がその最大値になったか否かを判定し（ステップＳ３６）、当該最大値になっていない場合は（ステップＳ３６；ＮＯ）、パラメータｎの値を一だけインクリメントして（ステップＳ３８）、上記ステップＳ３２に戻って上述した処理を繰り返す。一方ステップＳ３６の判定において、その時点でのパラメータｎの値がその最大値になっている場合（ステップＳ３６；ＹＥＳ）、決定部４は、各ノードＮｎについての上記ステップＳ３４により算出されている合計移動コストＣｎのうち最小の合計移動コストＣｎのノードＮｎを抽出し、このノードＮｎを新たな分岐点とし（ステップＳ３７）、その後上記ステップＳ４に移行する。
【００４５】
以上の図５を用いて説明した分岐点決定処理により、図６に例示する場合は、合計移動コストＣ３が最小となったノードＮ３に相当する交差点Ｊ１が、分岐点として決定されている（図６（ｃ）●印参照）。
【００４６】
以上説明したように、第１実施例に係る経路探索処理によれば、経由地Ａ及び経由地Ｂを経由する順番が相互に異なる複数の経路（図６記載の経路Ｒ１及び経路Ｒ２参照）に基づいて、車両の現在位置Ｃから分岐点を通過して経由地Ａ及び経由地Ｂへ到達可能な当該分岐点を決定し、現在位置Ｃと分岐点との間の距離が上記閾値距離以下となったとき、分岐点を通って経由地Ａ及び経由地Ｂに到達するための経路を探索する。よって、経由地Ａ及び経由地Ｂへ到達可能な分岐点を決定し、その分岐点までの距離が閾値距離以下となったとき分岐点を通る経路を改めて探索するので、例えば現在位置Ｃの前方で突発的な事故等が発生したとしても、経由地Ａ及び経由地Ｂへ効率的に到達できる。また、経由地Ａ及び経由地Ｂの経由順が決まっていない場合でも、経由地Ａ及び経由地Ｂへ効率的に到達できる。
【００４７】
更に、現在位置Ｃを基準とした既定の範囲内にある各経路に相当するノードＮｎであって、そのノードＮｎを通って経由地Ａ及び経由地Ｂに至る経路それぞれについての移動コストの差が既定の閾値コスト以下であるノードＮｎを分岐点の候補として決定する。そして、当該候補が複数決定された場合において、合計移動コストＣｎが最も小さい候補を分岐点として決定する。よって、既定の範囲内にあるノードＮｎにつき、それを通る経路の移動コストを用いて分岐点を決定するので、適切な分岐点をより少ない処理量で決定することができる。
【００４８】
更にまた、分岐点を通る経路が複数探索された場合において、各経路それぞれについての移動コストが最も小さい経路を車両の案内経路として決定するので（図４ステップＳ７及び同ステップＳ８参照）、車両が実際に移動する場合に最も適切な案内経路を設定することができる。
【００４９】
なお当該最適な案内経路を設定するに際し、分岐点を通る複数の経路それぞれを示す経路情報等を例えばディスプレイ１４に表示してユーザに提示し、当該ユーザの選択操作により、以降の案内経路を選択するように構成してもよい。この場合には、提示された経路情報に基づいていずれかの経路を案内経路として選択させるので、ユーザの好みに応じて経由地Ａ及び経由地Ｂに到達する案内経路を選択することができる。
【００５０】
（２）第２実施例
次に、実施形態に係る他の実施例である第２実施例について、図７及び図８を用いて説明する。なお、図７は第２実施例に係る経路探索処理を示すフローチャートであり、図８は第２実施例に係る分岐点決定処理を説明する図である。
【００５１】
また、第２実施例に係るナビゲーション装置のハードウェア的な構成は、基本的には第１実施例に係るナビゲーション装置ＮＶのハードウェア的な構成と同一である。よって以下に説明する第２実施例では、第１実施例に係るナビゲーション装置ＮＶと同一の構成部材及び処理については、同一の部材番号及び同一のステップ番号を付して細部の説明は省略する。
【００５２】
以下に説明する第２実施例では、実施形態に係る経路探索処理における分岐点決定処理として、第１実施例に係る分岐点決定処理とは異なる方法で分岐点を決定する場合について説明する。
【００５３】
先ず、第２実施例に係る経路探索処理の全体について、図７（ａ）を用いて説明する。
【００５４】
図７（ａ）に対応するフローチャートを示すように、第２実施例に係る経路探索処理は、第１実施例に係る経路探索処理と同様に、例えば操作部１３における指示操作に基づいて開始される。そして、当該経路探索処理が開始されると先ず処理部Ｓは、第１実施例に係る経路探索処理と同様のステップＳ１及びステップＳ２を実行する。
【００５５】
次に処理部Ｓの可能経路探索部３及び決定部４は、第２実施例に係る経路探索処理独自の処理として、経由地Ａ及び経由地Ｂの双方に到達し得る道路の上記分岐点を、上記地図データＤ等を用いて決定する（ステップＳ３ー１）。当該決定された分岐点を示す分岐点データは記録部１０に一時的に記録される。このステップＳ３−１については、後ほど詳述する。
【００５６】
その後処理部Ｓは、第１実施例に係る経路探索処理と同様のステップＳ４乃至ステップＳ８を実行し、これらの処理により選択された経路を案内経路とする車両の案内を開始する。
【００５７】
次に上記ステップＳ３−１の分岐点決定処理について、具体的に図７（ｂ）及び図８を用いて説明する。
【００５８】
上記ステップＳ３−１の分岐点決定処理として具体的に処理部Ｓの可能経路探索部３は、図７（ｂ）に示すように、先ず現在の経由地Ａ及び経由地Ｂについて、現在位置Ｃ⇒経由地Ａ⇒経由地Ｂと経由する経路の全てと、現在位置Ｃ⇒経由地Ｂ⇒経由地Ａと経由する経路の全てを、上記地図データＤ等を用いてそれぞれ探索し（ステップＳ４０）、その探索結果を示すデータ等を記録部１０に一時的に記録する。次に処理部Ｓの決定部４は、第２実施例に係る分岐点決定処理に用いられる各パラメータを初期化する（ステップＳ４１）。
【００５９】
ここで、第２実施例に係る分岐点決定処理に用いられる上記パラメータとしては、先ず現在位置Ｃ⇒経由地Ａ⇒経由地Ｂと経由する経路（以下、この経路を適宜「経路Ｒａ」と称する）を示すパラメータＲａｍがある。このとき、「ｍ」は上記ステップＳ４０により探索された、経由地Ａ⇒経由地Ｂの部分以外が相互に異なる複数の経路Ｒａの番号を示し、その初期値は「１」、その最大値は現在位置Ｃ⇒経由地Ａ⇒経由地Ｂと経由するものとして探索された経路Ｒａの総数である。以下の説明ではその最大地を「Ｍ」とする。
【００６０】
次に他のパラメータとしては、現在位置Ｃ⇒経由地Ｂ⇒経由地Ａと経由する経路（以下、この経路を適宜「経路Ｒｂ」と称する）を示すパラメータＲｂｓがある。このとき、「ｓ」は上記ステップＳ４０により探索された、経由地Ｂ⇒経由地Ａの部分以外が相互に異なる複数の経路Ｒｂの番号を示し、その初期値は「１」、その最大値は現在位置Ｃ⇒経由地Ｂ⇒経由地Ａと経由するものとして探索された経路Ｒｂの総数である。以下の説明ではその最大地を「Ｓ」とする。
【００６１】
最後に、経路ａに相当する経路データ上のノードＮを示すパラメータＮｍｎがある。このとき、「ｍ」は上記経路ａに関連するものと同じ意味であり、また「ｎ」は上記ステップＳ４０により探索された経路ａ上の上記ノードＮの番号を示し、その初期値は「１」、その最大値は経路ａに対応する経路データ上のノードＮの総数である。以下の説明ではその最大地を「Ｎ」とする。
【００６２】
そして上記ステップＳ４１では、上記「ｍ」、「ｎ」及び「ｓ」をそれぞれ初期化する。
【００６３】
次に決定部４は、ｍ番目の経路Ｒａ上のノードＮｍｎに着目し（ステップＳ４２）、そのノードＮｍｎが他方の経路Ｒｂｓ上にもあるか否かを、地図データＤ等を用いて判定する（ステップＳ４３）。ステップＳ４３の判定において、ノードＮｍｎが他方の経路Ｒｂｓ上にない場合（ステップＳ４３；ＮＯ）、決定部４は後述するステップＳ４８に移行する。一方ステップＳ４３の判定において、ノードＮｍｎが他方の経路Ｒｂｓ上にもある場合（ステップＳ４３；ＹＥＳ）、決定部４は次に、経路Ｒａｍにおける現在位置からノードＮｍｎに至る経路と、経路Ｒｂｓにおける現在位置からノードＮｍｎに至る経路と、が一致するか否かを、地図データＤ等を用いて判定する（ステップＳ４４）。ステップＳ４４の判定において、現在位置からノードＮｍｎに至る経路が経路Ｒｂｓと経路Ｒａｍとで一致しない場合（ステップＳ４４；ＮＯ）、決定部４は後述するステップＳ４８に移行する。一方ステップＳ４４の判定において、現在位置からノードＮｍｎに至る経路が経路Ｒｂｓと経路Ｒａｍとで一致する場合（ステップＳ４４；ＹＥＳ）、決定部４は次に、ノードＮｍｎの位置から経由地Ａまでの経路Ｒａｍの移動コストと、当該ノードＮｍｎの位置から経由地Ｂまでの経路Ｒｂｓの移動コストと、の差が上記閾値コスト以下であるか否かを判定する（ステップＳ４５）。ステップＳ４５の判定において、当該経路Ｒａｍの移動コストと当該経路Ｒｂｓの移動コストとの差が上記閾値コストより大きい場合（ステップＳ４５；ＮＯ）、決定部４は後述するステップＳ４８に移行する。
【００６４】
一方ステップＳ４５の判定において、ノードＮｍｎの位置から経由地Ａまでの経路Ｒａｍの移動コストと、当該ノードＮｍｎの位置から経由地Ｂまでの経路Ｒｂｓの移動コストと、の差が上記閾値コスト以下である場合（ステップＳ４５；ＹＥＳ）、決定部４は次に、当該経路Ｒａｍ及び経路Ｒｂｓそれぞれについての移動コストを加算して当該ノードＮｍｎについての合計移動コストＣｍｎを算出し、その値を一時的に記録部１０に記録する（ステップＳ４６）。その後決定部４は、上記二つの経路の起点となっているノードＮｍｎに対して上記経路Ｒａｍ及び経路ｂｓを関連付け、当該ノードＮｍｎに相当する交差点等を分岐点の候補として設定する（ステップＳ４７）。このステップＳ４７における分岐点の候補についての情報も記録部１０に一時的に記録される。
【００６５】
その後決定部４は、上記「ｍ」、「ｎ」及び「ｓ」がそれぞれの最大値になったか否かを、上記「ｓ」、「ｎ」及び「ｍ」の順に確認する（ステップＳ４８乃至ステップＳ５０）。そして上記「ｓ」がその最大値Ｓになっていない場合（ステップＳ４８；ＮＯ）、決定部４は当該「ｓ」を一だけインクリメントし（ステップＳ５４）、上記ステップＳ４３に戻って以降の処理を繰り返す。また上記「ｎ」がその最大値Ｎになっていない場合（ステップＳ４９；ＮＯ）、決定部４は当該「ｎ」を一だけインクリメントすると共に上記「ｓ」を初期化し（ステップＳ５３）、上記ステップＳ４２に戻って以降の処理を繰り返す。更に上記「ｍ」がその最大値Ｍになっていない場合（ステップＳ５０；ＮＯ）、決定部４は当該「ｍ」を一だけインクリメントすると共に上記「ｓ」及び上記「ｎ」をそれぞれ初期化し（ステップＳ５２）、上記ステップＳ４２に戻って以降の処理を繰り返す。
【００６６】
以上のステップＳ４８乃至ステップＳ５０及びステップＳ５２乃至ステップＳ５４の繰り返しに処理より、一つの経路Ｒａｍ上の全てのノードＮｍｎについて、全ての経路Ｒｂｓを対象とした上記ステップＳ４２乃至ステップＳ４７が繰り返され、更に、上記一つの経路ＲａｍについてのステップＳ４２乃至ステップＳ４７の繰り返しが、全ての経路Ｒａｍについて更に繰り返されることになる。
【００６７】
他方、上記「ｍ」、「ｎ」及び「ｓ」の全てがそれぞれの最大値になっている場合（ステップＳ４８：ＹＥＳ、ステップＳ４９；ＹＥＳ及びステップＳ５０；ＹＥＳ）、決定部４は、各ノードＮｍｎについての上記ステップＳ４６により算出されている合計移動コストＣｍｎのうち最小の合計移動コストＣｍｎのノードＮｍｎを抽出し、このノードＮｍｎを新たな分岐点とし（ステップＳ５１）、その後第２実施例に係る上記ステップＳ４に移行する。
【００６８】
以上の図７（ｂ）を用いて説明した分岐点決定処理が実行された場合、先ず図８（ａ）に例示するように、現在位置Ｃ（上記ノードＮｍｎに相当する）から経由地Ａ及び経由地Ｂを経由するに当たって、ノードＮ１及びノードＮ２を含む各経路Ｒａｍ（図８において太い実線で示す）に着目して全ての経路Ｒｂｓ（図８において一点鎖線で示す）との間に一致する区間がない場合（図７（ｂ）ステップＳ４３；ＮＯ又は同ステップＳ４４；ＮＯ参照）、個分岐点は決定されない（図８（ａ）右端参照）。
【００６９】
これに対し図８（ｂ）に例示するように、いずれかの経路Ｒａｍといずれかの経路Ｒｂｓとの間で一致する区間が一つあった場合（図７（ｂ）ステップＳ４３；ＹＥＳ又は同ステップＳ４４；ＹＥＳ参照。図８（ｂ）において破線で示す。）、その区間に対応するノードＮ４に相当する交差点Ｊ２が、分岐点として決定される（図８（ｂ）右端●印参照）。
【００７０】
更に、図８（ｃ）に例示するように、いずれかの経路Ｒａｍといずれかの経路Ｒｂｓとの間で一致する区間が二以上あった場合（図７（ｂ）ステップＳ４３；ＹＥＳ又は同ステップＳ４４；ＹＥＳ参照。図８（ｃ）において破線で示す。）、それぞれの区間に対応するノードＮ４に相当する交差点Ｊ２及びノードＮ３に相当する交差点Ｊ１について、分岐点の候補判定がそれぞれ別個になされる（図８（ｃ）右端●印参照）。そして、合計移動コストＣｍｎが小さい方のノードＮが実際の分岐点として決定される。
【００７１】
以上説明したように、第２実施例に係る経路探索処理によれば、上記第１実施例に係る経路探索処理による作用効果と一部異なり、経路Ｒａｍと、他の経路Ｒｂｓとで共通のノードＮｍｎであって、現在位置Ｃから当該ノードＮｍｎに至る経路Ｒａｍの部分が他の経路Ｒｂｓと共通であるノードＮｍｎを分岐点の候補として決定する（図８●印参照）。そして、当該候補が複数決定された場合において、一の候補を通る経路Ｒａｍについての合計移動コストＣｍｎが最も小さい候補を分岐点として決定する。よって、経路Ｒａｍ等に相当するノードＮｍｎを逐一検討対象として分岐点を決定するので、分岐点を的確に決定することができる。
【００７２】
なお上記ステップＳ４０において、経路Ｒａの全てと経路Ｒｂの全てを検索するのではなく、例えば、それぞれの移動コストが予め設定された移動コスト以下の経路のみを抽出するように構成してもよいし、或いは、当該移動コストが小さい経路から順に予め設定された数の経路Ｒａ及び経路Ｒｂを抽出するように構成してもよい。このようにすれば、処理部Ｓとしての処理量を低減することができる。
【００７３】
（３）第３実施例
次に、実施形態に係る更に他の実施例である第３実施例について、図９を用いて説明する。なお、図９は第３実施例に係る経路探索処理を示すフローチャートである。
【００７４】
また、第３実施例に係るナビゲーション装置のハードウェア的な構成は、基本的には第１実施例に係るナビゲーション装置ＮＶのハードウェア的な構成と同一である。よって以下に説明する第３実施例では、第１実施例に係るナビゲーション装置ＮＶと同一の構成部材及び処理については、同一の部材番号及びステップ番号を付して細部の説明は省略する。
【００７５】
以下に説明する第３実施例では、実施形態に係る経路探索処理に対応する実施例として、経由地ではなく目的地が複数あり、そのどちらを目指すかが決定されていない段階で、どちらの目的地に向かうべきかを決定して経路を設定する場合について説明する。
【００７６】
即ち、上記第１実施例に相当する場合の第３実施例に係る経路探索処理は、図９に対応するフローチャートを示すように、第１実施例に係る経路探索処理と同様に、例えば操作部１３における指示操作に基づいて開始される。そして、当該経路探索処理が開始されると先ず処理部Ｓは、上記複数の目的地を、例えば各目的地の位置を示す位置情報等を取得することにより設定する（ステップＳ６０）。このとき当該位置情報等は、地点情報取得部２により取得された後、記録部１０に一時的に記録される。次に処理部Ｓは、第１実施例に係る経路探索処理と同様のステップＳ２乃至ステップＳ６を実行する。
【００７７】
その後処理部Ｓの分岐点経路決定部５は、ステップＳ６で取得した渋滞の発生状況を示す情報等及び地図データＤに基づき、前方の分岐点から各目的地それぞれに向かう経路を改めて一又は複数探索する（ステップＳ６１）。その後処理部Ｓは、探索された新たな経路（分岐点を経由する経路）のそれぞれのうち、各目的地に向けて移動することについての移動コストが最も小さい経路を抽出し、当該抽出された経路を示す情報を例えばディスプレイ１４を用いて提示（出力）する（ステップＳ８）。その後処理部Ｓは、当該提示された経路を示す情報に基づいた操作部１３における操作により選択された経路を案内経路とする車両の案内を開始する。
【００７８】
なお、上記第２実施例に相当する場合にも、図９に示す場合と同ようにして第３実施例に係る経路探索処理を適用することができる。
【００７９】
以上説明した第３実施形態に係る経路探索処理によれば、目的地が複数あり且ついずれの目的地に向かうかが決定されていない場合でも、最適な経路及び目的地を効率的に探索することができる。
（４）変形例
最後に、実施形態に係る変形例について説明する。
【００８０】
先ず第１変形例として、上記各実施例に係る経路探索処理において、決定された分岐点への到達予定時刻を例えば操作部１３における操作により指定させ、更に、当該指定された到達予定時刻以前にその分岐点へ車両が到達できるか否かを判定し、その判定結果に応じて異なる経路（分岐点を含む）を探索するように構成してもよい。この構成によれば、車両の移動状況に応じて臨機応変に且つ適切に分岐点までの経路を探索することができる。
【００８１】
また第２変形例として、図４、図５、図７及び図９にそれぞれ示したフローチャートに相当するプログラムを、光ディスク又はハードディスク等の記録媒体に記録しておき、或いはインターネット等のネットワークを介して取得しておき、これを汎用のマイクロコンピュータ等に読み出して実行することにより、当該マイクロコンピュータ等を実施例に係る処理部Ｓとして機能させることも可能である。
【符号の説明】
【００８２】
１    位置情報取得手段（位置情報取得部）
２    地点情報取得手段（地点情報取得部）
３    可能経路探索手段（可能経路探索部）
４    決定手段（決定部）
５    分岐点経路決定手段（分岐点経路決定部）
１０    記録部
Ｄ    地図データ
ＮＶ    ナビゲーション装置
Ｓ    経路探索装置（処理部）
Ａ、Ｂ    経由地
Ｃ    現在位置
Ｎ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５    ノード
Ｒ１、Ｒ２、Ｒａｍ、Ｒｂｓ    経路
【図１】
2016194430.tif 000003
【図２】
2016194430.tif 000004
【図３】
2016194430.tif 000005
【図４】
2016194430.tif 000006
【図５】
2016194430.tif 000007
【図６】
2016194430.tif 000008
【図７】
2016194430.tif 000009
【図９】
2016194430.tif 000010
【図８】
2016194430.tif 000011