(57)【特許請求の範囲】
【請求項１】
目的地を設定する目的地設定手段と、
道路に対応する複数のリンクのそれぞれについて通過時間としてのコストを含む地図データを格納する地図データ格納手段と、
前記地図データ格納手段に格納された地図データに基づいて前記目的地までの走行経路を探索する際に、一度通過した有料道路と同じ道路種別の有料道路に再度合流する際に再合流コストを加算して走行経路を探索し、前記目的地に至るまでの最もコスト合計が小さい走行経路を決定する経路探索手段と、
を備え、前記同じ道路種別の有料道路は、いずれも距離に比例した料金体系を有し、前記一度通過した有料道路から連続する有料道路であることを特徴とするナビゲーション装置。
【請求項２】
請求項１において、
交通情報を取得する交通情報取得手段と、
前記交通情報が対応づけられている前記リンクのコストを前記交通情報に基づいて修正するコスト修正手段と、
をさらに備え、前記経路探索手段は、前記コスト修正手段による修正後のコストを用いて前記目的地までの走行経路を探索する際に、前記再合流コストを用いた経路探索を行うことを特徴とするナビゲーション装置。
【請求項３】
請求項１または２において、
一度通過した前記有料道路の道路種別を特定する道路種別情報を格納する道路種別情報格納手段をさらに備え、
前記経路探索手段は、再度合流する前記有料道路の道路種別が、前記道路種別情報格納手段に格納された道路種別情報によって特定される道路種別と同じであるときに、前記再合流コストの加算を行うことを特徴とするナビゲーション装置。
【請求項４】
請求項３において、
前記道路種別情報によって、直近に走行した前記有料道路の道路種別が特定されることを特徴とするナビゲーション装置。
【請求項５】
請求項２において、
前記経路探索手段による前記再合流コストを考慮した走行経路の探索は、前記交通情報取得手段によって前記交通情報を取得した場合に行われることを特徴とするナビゲーション装置。
【請求項６】
目的地を目的地設定手段によって設定するステップと、
道路に対応する複数のリンクのそれぞれについて通過時間としてのコストを含む地図データに基づいて前記目的地までの走行経路を探索する際に、一度通過した有料道路と同じ道路種別の有料道路に再度合流する際に再合流コストを加算して走行経路を探索し、前記目的地に至るまでの最もコスト合計が小さい走行経路を経路探索手段によって決定するステップと、
を有し、前記同じ道路種別の有料道路は、いずれも距離に比例した料金体系を有し、前記一度通過した有料道路から連続する有料道路であることを特徴とする走行経路設定方法。
【請求項７】
コンピュータを、
目的地を設定する目的地設定手段と、
道路に対応する複数のリンクのそれぞれについて通過時間としてのコストを含む地図データを格納する地図データ格納手段と、
前記地図データ格納手段に格納された地図データに基づいて前記目的地までの走行経路を探索する際に、一度通過した有料道路と同じ道路種別の有料道路であって、いずれも距離に比例した料金体系を有し、前記一度通過した有料道路から連続する有料道路に再度合流する際に再合流コストを加算して走行経路を探索し、前記目的地に至るまでの最もコスト合計が小さい走行経路を決定する経路探索手段と、
して機能させるための走行経路設定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地まで車両の走行経路を設定するナビゲーション装置、走行経路設定方法およびプログラムに関する。
【背景技術】
【０００２】
従来から、走行中の有料道路上の前方に渋滞区間がある場合に、この渋滞区間をそのまま走行する現状経路の所要時間や通行料と、この渋滞区間を避けて一旦有料道路を降りて再び有料道路に戻る出戻り経路の所要時間や通行料とを比較して、車両の走行経路を決定するようにしたナビゲーション装置が知られている（例えば、特許文献１参照。）。具体的には、このナビゲーション装置では、（ケース１）出戻り経路の所要時間の方が現状経路の所要時間よりも時間差閾値よりも短い場合、（ケース２）出戻り経路の通行料の増加分が現状経路の通行料に対して料金差閾値よりも安い範囲で収まっている場合、（ケース３）ケース１とケース２の両方を満たす場合、のいずれかに該当する場合に出戻り経路が車両の走行経路として設定される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−５８０８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、特許文献１に開示されたナビゲーション装置では、現状経路と出戻り経路のそれぞれについて所要時間や通行料を別々に計算した後、これらの計算結果を比較する必要があるため、処理が複雑になるという問題があった。特に、有料道路上に複数の渋滞区間が含まれる場合などについては、目的地に到達するまでの走行経路に含まれる出戻り経路が複数になる場合も考えられるため、比較対象となる経路が増えて処理がさらに複雑になる。また、一度降りた有料道路に再度乗る経路が選択され、有料道路の通行料が増加するという問題があった。
【０００５】
本発明は、このような点に鑑みて創作されたものであり、その目的は、有料道路上の渋滞を考慮して目的地までの走行経路の設定を行う際に、通行料の増加を抑制するとともに処理を簡略化することができるナビゲーション装置、走行経路設定方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上述した課題を解決するために、本発明のナビゲーション装置は、目的地を設定する目的地設定手段と、道路に対応する複数のリンクのそれぞれについて通過時間としてのコストを含む地図データを格納する地図データ格納手段と、地図データ格納手段に格納された地図データに基づいて目的地までの走行経路を探索する際に、一度通過した有料道路と同じ道路種別の有料道路に再度合流する際に再合流コストを加算して走行経路を探索し、目的地に至るまでの最もコスト合計が小さい走行経路を決定する経路探索手段とを備え、同じ道路種別の有料道路は、いずれも距離に比例した料金体系を有し、一度通過した有料道路から連続する有料道路である。
【０００７】
また、本発明の走行経路設定方法は、目的地を目的地設定手段によって設定するステップと、道路に対応する複数のリンクのそれぞれについて通過時間としてのコストを含む地図データに基づいて目的地までの走行経路を探索する際に、一度通過した有料道路と同じ道路種別の有料道路に再度合流する際に再合流コストを加算して走行経路を探索し、目的
地に至るまでの最もコスト合計が小さい走行経路を経路探索手段によって決定するステップとを有し、同じ道路種別の有料道路は、いずれも距離に比例した料金体系を有し、一度通過した有料道路から連続する有料道路である。
【０００８】
また、本発明の走行経路設定プログラムは、コンピュータを、目的地を設定する目的地設定手段と、道路に対応する複数のリンクのそれぞれについて通過時間としてのコストを含む地図データを格納する地図データ格納手段と、地図データ格納手段に格納された地図データに基づいて目的地までの走行経路を探索する際に、一度通過した有料道路と同じ道路種別の有料道路であって、いずれも距離に比例した料金体系を有し、一度通過した有料道路から連続する有料道路に再度合流する際に再合流コストを加算して走行経路を探索し、目的地に至るまでの最もコスト合計が小さい走行経路を決定する経路探索手段として機能させる。
【０００９】
同じ道路種別を有する有料道路に再度合流する際に再合流コストが加算されるため、このような走行経路がコスト合計の小さい最適な走行経路として決定されにくくなり、１つの有料道路を一旦降りて再度乗ることによる通行料の増加を抑制することができる。また、目的地までの複数の経路を求めてそれぞれの通行料等を比較することなく、出発地と目的地との間で探索枝を延ばしていく従来と同等の経路探索処理を行うことができ、処理の簡略化が可能となる。
また、上述した同じ道路種別の有料道路を、いずれも距離に比例した料金体系を有し、一度通過した有料道路から連続する有料道路とすることにより、距離比例制の料金体系を有するひとつながりの有料道路に再合流することを抑制することが可能となる。
【００１０】
また、上述した交通情報を取得する交通情報取得手段と、交通情報が対応づけられているリンクのコストを交通情報に基づいて修正するコスト修正手段とをさらに備え、経路探索手段は、コスト修正手段による修正後のコストを用いて目的地までの走行経路を探索する際に、再合流コストを用いた経路探索を行うことが望ましい。これにより、有料道路上に一部区間に渋滞や混雑が発生している場合に、通行料の増加を伴うことなく、最適な走行経路を決定することが可能となる。
【００１１】
また、一度通過した有料道路の道路種別を特定する道路種別情報を格納する道路種別情報格納手段をさらに備え、経路探索手段は、再度合流する有料道路の道路種別が、道路種別情報格納手段に格納された道路種別情報によって特定される道路種別と同じであるときに、再合流コストの加算を行うことが望ましい。これにより、これから合流しようとしている有料道路が一度走行した有料道路と同じであるか否かを容易に知ることができる。
【００１２】
また、上述した道路種別情報によって、直近に走行した有料道路の道路種別が特定されることが望ましい。これにより、通行料の増加につながる有料道路に合流する場合について確実に再合流コストを加算することが可能となる。
【００１３】
また、上述した経路探索手段による再合流コストを考慮した走行経路の探索は、交通情報取得手段によって交通情報を取得した場合に行われることが望ましい。これにより、渋滞や混雑が発生した時点で最適な走行経路を、有料道路の通行料の増加を抑制しながら決定することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】一実施形態のナビゲーション装置の詳細構成を示す図である。
【図２】交通情報を取得してコスト修正を行った後に経路探索を行うナビゲーション装置の動作手順を示す流れ図である。
【図３】図２に示したステップ１０８の経路探索処理の詳細動作を示す流れ図である。
【図４】合流コストを考慮した走行経路の説明図である。
【図５】新たな交通情報を取得する毎に再合流コストを考慮した経路探索処理を行う変形例の動作手順を示す流れ図である。
【図６】２回目以降の経路探索処理で得られた走行経路に対応する通行料が前回の走行経路の通行料と同じ、あるいは、前回の走行経路の通行料よりも低額になった場合に走行経路の置き換えを行う変形例の動作手順を示す流れ図である。
【発明を実施するための形態】
【００２０】
以下、本発明を適用した一実施形態のナビゲーション装置について、図面を参照しながら説明する。図１は、一実施形態のナビゲーション装置の詳細構成を示す図である。図１に示すように、本実施形態のナビゲーション装置１００は、ナビゲーションコントローラ１、地図データ記憶装置２、操作部３、車両位置検出部４、表示装置５、オーディオ部６、ビーコン送受信機７、ＦＭ多重放送受信機８を含んで構成されている。このナビゲーション装置は、車両に搭載されている。
【００２１】
ナビゲーションコントローラ１は、ＣＰＵ、ＲＯＭ、ＲＡＭ等を用いて所定の動作プログラムを実行することにより、自車位置周辺の地図画像表示動作、出発地と目的地とを結ぶ走行経路を設定する経路探索処理やこの走行経路に沿って車両の走行を誘導する経路誘導動作、ＶＩＣＳ（登録商標）センタから送られてくる交通情報の受信動作などの各種機能を実現する。ナビゲーションコントローラ１の詳細構成については後述する。
【００２２】
地図データ記憶装置２は、地図表示や施設検索、経路探索などに必要な地図データが格納されている記憶媒体およびその読み取り装置である。この地図データ記憶装置２には、経度および緯度で適当な大きさに区切られた矩形形状の図葉を単位とした地図データが格納されている。各図葉の地図データは、図葉番号を指定することにより特定され、読み出すことが可能となる。
【００２３】
また、この地図データには、（１）地図表示に必要な各種のデータからなる描画ユニットと、（２）マップマッチングや経路探索、経路誘導等の各種の処理に必要なデータからなる道路ユニットと、（３）交差点の詳細データからなる交差点ユニットが含まれている。
【００２４】
また、上述した描画ユニットには、ＶＩＣＳセンタから送られてくる渋滞情報に基づいて対応する道路を特定するために必要なＶＩＣＳ変換レイヤのデータと、建物あるいは河川等を表示するために必要な背景レイヤのデータと、市町村名や道路名等を表示するために必要な文字レイヤのデータが含まれている。
【００２５】
上述した道路ユニットにおいて、道路上のある交差点と隣接する他の交差点とを結ぶ線をリンクといい、２本以上のリンクを結ぶ交差点をノードという。道路ユニットには、全ノードの詳細データを納めた接続ノードテーブルと、隣接する２つのノードによって特定されるリンクの詳細データを納めたリンクテーブルとが含まれている。リンクテーブルには、各リンクについて、このリンクの通過に要する時間であるコスト（静的コスト）が対応づけられている。
【００２６】
地図データ記憶装置２は、ハードディスク装置や半導体メモリによって、あるいは、ＤＶＤとその読み取り装置によって実現される。また、地図データ記憶装置２を通信装置（図示せず）に置き換えて、外部の地図配信サーバ（図示せず）から地図データを取得するようにしてもよい。
【００２７】
操作部３は、利用者の指示（操作）を受け付けるためのものであり、各種の操作ボタンや操作つまみ類を備えている。また、操作部３は、表示装置５の画面に取り付けられたタッチパネルを含んでおり、画面上の一部を直接利用者が指等で指し示すことにより、操作指示を行うことができるようになっている。車両位置検出部４は、例えば、ＧＰＳ受信機、方位センサ、距離センサなどを備えており、所定のタイミングで車両位置（経度、緯度）の検出を行い、検出結果を出力する。
【００２８】
表示装置５は、例えばＬＣＤ（液晶表示装置）によって構成されており、ナビゲーションコントローラ１から出力される映像信号に基づいて自車位置周辺の地図画像などを表示する。オーディオ部６は、ナビゲーションコントローラ１から入力される音声信号に基づいて生成した案内音声等を車室内に出力する。
【００２９】
ビーコン送受信機７は、主に高速道路上に設置された電波ビーコンとの間で電波を介して双方向通信を行うとともに、主に一般道路上に設置された光ビーコン送受信機との間で双方向通信を行うことにより、ＶＩＣＳセンタから送られてくる交通情報を受信する。ＦＭ多重放送受信機８は、一般のＦＭ放送に重畳された多重化データに含まれる交通情報を受信する。ビーコン送受信機７とＦＭ多重放送受信機８によって受信される交通情報には、道路上の特定区間がどの程度渋滞しているかを示す渋滞情報、事故や道路の凍結等を示す事象情報、通行止めや対面通行等の規制情報などが含まれている。
【００３０】
次に、ナビゲーションコントローラ１の詳細構成について説明する。図１に示すナビゲーションコントローラ１は、地図バッファ１０、地図読出制御部１２、地図描画部１４、車両位置計算部２０、施設検索部３０、目的地設定部３２、経路探索処理部３４、状態フラグ格納部３５、経路誘導処理部３６、ＶＩＣＳ情報取得部４０、ＶＩＣＳ情報描画部４２、コスト修正部５０、走行経路置換部５２、入力処理部６０、表示処理部７０を含んで構成されている。
【００３１】
地図バッファ１０は、地図データ記憶装置２から読み出された地図データを一時的に格納する。この地図データには、地図画像描画に必要なデータや検索条件を指定して施設を検索するために必要なデータ、経路探索や経路誘導を行うために必要なデータ、有料道路の道路種別や通行料に関するデータが少なくとも含まれる。地図読出制御部１２は、車両位置計算部２０により算出される車両位置や利用者が操作部３を操作して指定した位置に応じて、所定範囲の地図データの読み出し要求を地図データ記憶装置２に出力する。地図描画部１４は、地図バッファ１０に格納された地図データに基づいて、表示装置５に地図画像を表示するために必要な描画処理を行って地図画像描画データを作成する。
【００３２】
車両位置計算部２０は、車両位置検出部４から出力される検出データに基づいて自車位置を計算するとともに、計算した自車位置が地図データの道路上にない場合には、自車位置を修正するマップマッチング処理を行う。
【００３３】
施設検索部３０は、地図バッファ１０に格納された地図データに基づいて、操作部３を用いて設定された検索条件を満たす施設を検索する。例えば、検索条件として、施設のジャンルを指定して候補となる施設を絞り込む場合や、電話番号あるいは住所等を特定して施設を絞り込む場合などが考えられる。このようにして特定の施設が抽出された後、この施設を目的地として用いた経路探索処理や、この施設の周辺地図や詳細情報の表示などが行われる。
【００３４】
目的地設定部３２は、経路探索処理部３４によって行われる経路探索処理に必要な目的地を設定する。例えば、施設検索部３０による検索によって抽出された施設を目的地として設定する場合や、利用者が操作部３を操作して直接指定した地図画像上の地点を目的地として設定する場合などが考えられる。
【００３５】
経路探索処理部３４は、出発地と目的地（あるいは経由地）との間を所定の探索条件にしたがって結ぶ走行経路（誘導経路）を経路探索処理によって設定する。例えば、車両位置計算部２０によって計算された自車位置が出発地として設定される。また、目的地設定部３２によって設定された目的地が経路探索処理の目的地として設定される。なお、経路探索処理の具体的な内容については、ダイクストラ法や横形探索法などの各種の方法を用いることができる。
【００３６】
状態フラグ格納部３５は、経路探索処理によって目的地に到達する走行経路を求める際に有料道路を通過した場合に、この有料道路の道路種別を特定する道路種別情報としての状態フラグを格納する。経路探索処理の途中で、複数の走行経路の候補が存在する場合には、それぞれの走行経路毎にこの状態フラグがセットされて格納される。
【００３７】
経路誘導処理部３６は、経路探索処理部３４による経路探索処理によって得られた誘導経路を地図上に重ねて表示したり、右左折交差点の拡大図を表示するための誘導経路描画データを作成するとともに、誘導経路に沿って車両の走行を誘導するために必要な交差点案内等の音声信号を生成することにより経路誘導処理を行う。
【００３８】
ＶＩＣＳ情報取得部４０は、ＶＩＣＳセンタから送信されビーコン送受信機７およびＦＭ多重放送受信機８によって受信される交通情報（ＶＩＣＳ情報）の取得処理を行う。この交通情報に含まれる渋滞情報としては、渋滞度（渋滞、混雑の程度）のみが含まれる場合の他に、渋滞度とともにリンクの旅行時間（通過に要する時間）が含まれる場合が考えられる。
【００３９】
ＶＩＣＳ情報描画部４２は、ＶＩＣＳ情報取得部４０によって取得された交通情報に含まれる渋滞情報、事象情報、規制情報に対応する交通情報画像描画データを作成する描画処理を行う。例えば、渋滞情報で特定される区間についてその内容（順調、混雑、渋滞）に応じた色を有する補助画像としての矢印画像を描画したり、事象情報や規制情報で特定される場所についてその内容に応じた所定のアイコン画像を描画する処理が行われる。
【００４０】
コスト修正部５０は、交通情報（渋滞情報）が対応づけられているリンクのコストをこの渋滞情報に基づいて修正する。渋滞情報として渋滞度のみが含まれる場合には、この渋滞度（順調、混雑、渋滞）に応じた重み付け係数を元の静的コストに乗算することにより、各リンクに対応するコストの修正が行われる。例えば、「順調」の場合の重み付け係数が１、「混雑」の重み付け係数が２、「渋滞」の重み付け係数が４に設定されているものとすると、渋滞度の内容に応じたこれらの重み付け係数が元の静的コストに乗算される。また、渋滞情報として渋滞度と旅行時間の両方が含まれる場合には、この旅行時間に対応するコストとなるように、各リンクのコストの修正が行われる。なお、コスト修正部５０によるコストの修正は、従来から行われている渋滞情報に基づく修正方法をそのまま適用することができる。
【００４１】
走行経路置換部５２は、経路探索処理部３４によって時間をずらして複数回経路探索を行った結果、後の経路探索で得られた第２の走行経路に対応する通行料がそれ以前の経路探索で得られた第１の走行経路に対応する通行料と同じあるいは低額となる場合に、第２の走行経路を第１の走行経路に置き換える。以後、この置き換えられた第２の走行経路を誘導経路として経路誘導処理部３６による表示等の処理が行われる。
【００４２】
入力処理部６０は、操作部３から入力される各種の操作指示に対応する動作を行うための命令をナビゲーションコントローラ１内の各部に向けて出力する。表示処理部７０は、地図描画部１４によって作成される地図画像描画データと、ＶＩＣＳ情報描画部４２によって作成される交通情報画像描画データとが入力されており、地図画像に交通情報画像を重ねた画像を表示装置５の画面に表示する。
【００４３】
上述した目的地設定部３２が目的地設定手段に、地図バッファ１０が地図データ格納手段に、経路探索処理部３４が経路探索手段に、ＶＩＣＳ情報取得部４０が交通情報取得手段に、コスト修正部５０がコスト修正手段に、状態フラグ格納部３５が道路種別情報格納手段に、走行経路置換部５２が走行経路置換手段にそれぞれ対応する。
【００４４】
本実施形態のナビゲーション装置１００はこのような構成を有しており、次に、一部に有料道路が含まれる目的地までの走行経路を経路探索処理によって設定する動作を説明する。
【００４５】
図２は、交通情報を取得してコスト修正を行った後に経路探索を行うナビゲーション装置の動作手順を示す流れ図である。
【００４６】
経路探索処理部３４は、経路探索処理が利用者によって指示されたか否かを判定する（ステップ１００）。指示されない場合には否定判断が行われ、この判定が繰り返される。また、操作部３を用いて利用者によって経路探索処理が指示されるとステップ１００の判定において肯定判断が行われる。
【００４７】
次に、経路探索処理部３４は、車両位置計算部２０によって計算された自車位置を経路探索処理の出発地として設定するとともに、目的地設定部３２によって設定された目的地を経路探索処理の目的地として設定する（ステップ１０２）。また、ＶＩＣＳ情報取得部４０は、ＶＩＣＳセンタから交通情報を取得したか否かを判定する（ステップ１０４）。交通情報を取得した場合には肯定判断が行われ、コスト修正部５０は、交通情報（渋滞情報）が対応づけられているリンクのコストをこの渋滞情報に基づいて修正する（ステップ１０６）。
【００４８】
コスト修正の後、あるいは、交通情報を取得しない場合であってステップ１０４の判定において否定判断が行われた後、経路探索処理部３４は、経路探索処理を行って出発地から目的地までの最適な走行経路（誘導経路）を設定する（ステップ１０８）。このようにして設定された走行経路を用いて経路誘導処理部３６による所定の経路誘導処理が行われる。
【００４９】
図３は、図２に示したステップ１０８の経路探索処理の詳細動作を示す流れ図である。なお、図３に示す動作手順は、経路探索処理の一例を示すものであって、他のアルゴリズムを有する経路探索処理を行うようにしてもよい。
【００５０】
経路探索処理が開始されると、まず、経路探索処理部３４は、着目交差点に隣接する隣接交差点を検索する（ステップ２００）。この交差点には、２本以上の道路（リンク）が交差する交差点の他に、経路探索処理で設定された出発地や目的地、高速道路などの有料道路の入口や出口などが含まれる。経路探索開始時には、出発地を着目交差点としてこの出発地に隣接する隣接交差点が検索される。
【００５１】
次に、経路探索処理部３４は、検索した隣接交差点が有料道路の出口か否かを判定する（ステップ２０２）。隣接交差点が有料道路の出口の場合は肯定判断が行われ、経路探索処理部３４は、状態フラグ格納部３５にこの有料道路の道路種別を特定する道路種別情報としての状態フラグを格納する（ステップ２０４）。
【００５２】
次に、あるいは、隣接交差点が有料道路の出口でない場合にはステップ２０２の判定において否定判断が行われた後、経路探索処理部３４は、検索した隣接交差点が有料道路の入口か否かを判定する（ステップ２０６）。隣接交差点が有料道路の入口の場合には肯定判断が行われ、経路探索処理部３４は、これから進入しようとしている有料道路の道路種別が一度通過したことがある直近の有料道路と道路種別と同じであるか否かを判定する（ステップ２０８）。ここで、「道路種別が同じである」場合としては、（１）同じ名称が付されている、（２）同じ料金体系を有し、一度通過した有料道路から連続する有料道路である、（３）いずれも均一区間制（走行距離に関係なく所定区間内を走行した際の料金が一定）の料金体系を有し、一度通過した有料道路から連続する有料道路である、（４）いずれも距離に比例した料金体系を有し、一度通過した有料道路から連続する有料道路である、などのいずれかに該当する場合、あるいはこれらの組み合わせに該当する場合が考えられる。
【００５３】
進入しようとする有料道路の道路種別が一度通過したことがある直近の有料道路の道路種別と同じでない場合（有料道路に始めて進入する場合も含まれる）にはステップ２０８の判定において肯定判断が行われる。この場合には、経路探索処理部３４は、リンクコストを合計する際に加算する再合流コストを設定する（ステップ２１０）。有料道路の入口でない場合（ステップ２０６の判定において否定判断）や道路種別が異なる場合（ステップ２０８の判定において否定判断）には、この再合流コストは設定されない（あるいは、再合流コストの値として「０」が設定される）。
【００５４】
次に、経路探索処理部３４は、隣接交差点までのコスト合計を計算する（ステップ２１２）。このコスト合計の計算では、リンクに対応するリンクコストの他に、ノード通過に要する時間としてのノードコストが考慮されている場合にはこのノードコストも加算される。また、上述したステップ２１０において再合流コストが設定されている場合には、この再合流コストも加算対象となる。隣接交差点が複数ある場合には、このコスト合計の計算は、隣接交差点毎に別々に行われる。
【００５５】
次に、経路探索処理部３４は、共通の隣接交差点があるか否かを判定する（ステップ２１４）。共通の隣接交差点がある場合には肯定判断が行われ、経路探索処理部３４は、コスト合計の小さい方の経路を選択する（ステップ２１６）。
【００５６】
次に、あるいは、共通の隣接交差点がない場合にはステップ２１４の判定において否定判断が行われた後、経路探索処理部３４は、一つ前の隣接交差点を登録する（ステップ２１８）。また、経路探索処理部３４は、隣接交差点が目的地と一致するか否かを判定する（ステップ２２０）。目的地と一致しない場合には否定判断が行われ、ステップ２００に戻って、次の隣接交差点検索以降の処理が繰り返される。
【００５７】
また、隣接交差点が目的地と一致する場合にはステップ２２０の判定において肯定判断が行われる。この場合には、経路探索処理部３４は、それまで探索された他の経路を介して目的地までの走行経路（既存の走行経路）が存在する場合には、新たに探索された目的地までの走行経路のコスト合計と、既存の走行経路のコスト合計とを比較し、コスト合計の小さい走行経路を誘導経路として設定する（ステップ２２２）。
【００５８】
次に、経路探索処理部３４は、ステップ２１２で計算した各隣接交差点までのコスト合計の中で、ステップ２２２において設定されたその時点で最適な誘導経路のコスト合計より小さいものがあるか否かを判定する（ステップ２２４）。コスト合計が小さい隣接交差点がある場合には肯定判断が行われ、ステップ２００に戻って、次の隣接交差点検索以降の処理が繰り返される。一方、各隣接交差点までのコスト合計の全てが、その時点で既に見いだされている最適な誘導経理のコスト合計を超えた場合にはステップ２２４の判定において否定判断が行われ、一連の経路探索処理が終了する。
【００５９】
このように、本実施形態のナビゲーション装置１００では、同じ道路種別を有する有料道路に再度合流する際に再合流コストが加算されるため、このような走行経路がコスト合計の小さい最適な走行経路として決定されにくくなり、１つの有料道路を一旦降りて再度乗ることによる通行料の増加を抑制することができる。また、目的地までの複数の経路を求めてそれぞれの通行料等を比較することなく、出発地と目的地との間で探索枝を延ばしていく従来と同等の経路探索処理を行うことができ、処理の簡略化が可能となる。
【００６０】
また、取得した交通情報に基づく修正後のコストを用いて目的地までの走行経路を探索する際に、再合流コストを用いた経路探索を行うことにより、有料道路上に一部区間に渋滞や混雑が発生している場合に、通行料の増加を伴うことなく、最適な走行経路を決定することが可能となる。
【００６１】
また、一度通過した有料道路の道路種別を特定する道路種別情報としての状態フラグを格納する状態フラグ格納部３５を備えており、格納された状態フラグによって特定される道路種別と同じであるときに、再合流コストの加算を行うことにより、これから合流しようとしている有料道路が一度走行した有料道路と同じであるか否かを容易に知ることができる。
【００６２】
また、直近に走行した有料道路の道路種別を特定することにより、通行料の増加につながる有料道路に合流する場合について確実に再合流コストを加算することが可能となる。
【００６３】
また、同じ道路種別の有料道路を、同じ名称が付された有料道路とすることにより、確実に同一の有料道路に再合流することを抑制することが可能となる。あるいは、同じ道路種別の有料道路を、同じ料金体系を有し、一度通過した有料道路から連続する有料道路とすることにより、同一の料金体系を有するひとつながりの有料道路に再合流することを抑制することが可能となる。また、同じ道路種別の有料道路を、いずれも均一区間制の料金体系を有し、一度通過した有料道路から連続する有料道路とすることにより、均一区間制の料金体系を有するひとつながりの有料道路に再合流することを抑制することが可能となる。さらに、同じ道路種別の有料道路を、いずれも距離に比例した料金体系を有し、一度通過した有料道路から連続する有料道路とすることにより、距離比例制の料金体系を有するひとつながりの有料道路に再合流することを抑制することが可能となる。
【００６４】
図４は、合流コストを考慮した走行経路の説明図である。図４において、Ｓは出発地、Ｍ１は第１の有料道路（例えば、東京外環自動車道）、Ｍ２は第２の有料道路（例えば、首都高速道路）、ＪＣＴは第１の有料道路Ｍ１から第２の有料道路Ｍ２に分岐するジャンクション、Ｔは第２の有料道路Ｍ２上で発生している渋滞区間、ＩＣ１は第１の有料道路上の出口としてのインターチェンジ、ＩＣ２は第２の有料道路Ｍ２上の入口としてのインターチェンジ、ＩＣ３は第２の有料道路上の出口としてのインターチェンジである。
【００６５】
一旦走行している有料道路から降りにくくなっている従来の経路探索処理では、第１および第２の有料道路Ｍ１、Ｍ２を乗り継いで走行する場合には、渋滞区間Ｔがあっても、よほど渋滞区間Ｔが長くない限り、ジャンクションＪＣＴを経由した走行経路Ｒ１が設定されて目的地Ｇまで経路誘導が行われる。
【００６６】
これに対し、本実施形態の経路探索処理では、第１の有料道路Ｍ１上の出口ＩＣ１で降りて第２の有料道路Ｍ２上の入口ＩＣ２で再び有料道路Ｍ２に合流する場合であっても、これらの乗り降りに際しては特別なコスト加算が行わないため、単にリンクやノード毎のコスト合計に基づいて、一部に一般道路が含まれる最適な（コスト合計が最小の）走行経路Ｒ２が決定される。しかも、第１および第２の有料道路Ｍ１、Ｍ２の道路種別は互いに異なるため、途中に一般道路が含まれていても、途中に一般道路が含まれない走行経路Ｒ１に比べて通行料が増加することはない。
【００６７】
なお、本発明は上記実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形実施が可能である。例えば、上述した実施形態では、交通情報を取得（図２のステップ１０４）して、リンクコストの修正（図２のステップ１０６）を行った後に、再合流コストを考慮した経路探索処理（図２のステップ１０８）を行うようにしたが、交通情報の取得や交通情報に基づくリンクコストの修正の有無とは無関係に、再合流コストを考慮した経路探索処理を行うようにしてもよい。
【００６８】
また、新たな交通情報を取得する毎に、再合流コストを考慮した経路探索処理を行うようにしてもよい。図５は、新たな交通情報を取得する毎に再合流コストを考慮した経路探索処理を行う変形例の動作手順を示す流れ図である。図５に示す流れ図は、図２に示した流れ図に対して、ステップ１０８の経路探索処理が終了した後、ステップ１０４に戻って、交通情報の取得判定以降を繰り返す点が異なっている。このように、新たな交通情報を受信したときに、再合流コストを考慮した経路探索処理を再度繰り返すことにより、渋滞や混雑が発生した時点で最適な走行経路を、有料道路の通行料の増加を抑制しながら決定することが可能となる。
【００６９】
また、再合流コストを考慮した経路探索処理を時間をずらして複数回行った結果、後の経路探索で得られた第２の走行経路に対応する通行料がそれ以前の経路探索で得られた第１の走行経路に対応する通行料と同じあるいは低額となる場合に、第２の走行経路を第１の走行経路に置き換えるようにしてもよい。
【００７０】
例えば、図５に示した動作手順では、経路探索処理（ステップ１０８）が時間をずらして複数回行われている。また、単純に所定の時間が経過する毎に、あるいは、所定の距離走行する毎に、経路探索処理を行うようにしてもよい。
【００７１】
図６は、２回目以降の経路探索処理で得られた走行経路に対応する通行料が前回の走行経路の通行料と同じ、あるいは、前回の走行経路の通行料よりも低額になった場合に走行経路の置き換えを行う変形例の動作手順を示す流れ図である。図６に示した流れ図は、図３に示した流れ図に対して、ステップ２２６、２２８が追加された点が異なっている。以下では、これらの追加された点に着目して説明を行う。なお、１回目の経路探索処理は図３に示した流れ図に従って行われ、２回目以降の経路探索処理が図６に示した流れ図に従って行われる。
【００７２】
２回目以降の経路探索処理では、最適な走行経路が誘導経路として設定された後（ステップ２２４の判定において否定判断）、走行経路置換部５２は、ステップ２２２において今回新たに設定した誘導経路の通信料が前回設定した誘導経路の通信料と同じ、あるいは前回設定した誘導経路の通信料よりも定額か否かを判定する（ステップ２２６）。同じあるいは低額の場合には肯定判断が行われ、走行経路置換部５２は、新たな誘導経路を前回の誘導経路に置き換える（ステップ２２８）。
【００７３】
このように、時間をずらして経路探索処理を複数回行って通信料が同じか低額の誘導経路が見いだされたときにこの新たな誘導経路を採用することにより、道路状況の変化等に応じた最適な走行経路を、有料道路の通行料の増加を抑制しながら決定することが可能となる。
【００７４】
また、上述した実施形態では、車両に搭載されたナビゲーション装置１００について説明したが、携帯端末装置やパーソナルコンピュータなどで地図アプリケーションを実行して行う経路探索処理においても本発明を適用することができる。
【産業上の利用可能性】
【００７５】
上述したように、本発明によれば、同じ道路種別を有する有料道路に再度合流する際に再合流コストが加算されるため、このような走行経路がコスト合計の小さい最適な走行経路として決定されにくくなり、１つの有料道路を一旦降りて再度乗ることによる通行料の増加を抑制することができる。また、目的地までの複数の経路を求めてそれぞれの通行料等を比較することなく、出発地と目的地との間で探索枝を延ばしていく従来と同等の経路探索処理を行うことができ、処理の簡略化が可能となる。
【符号の説明】
【００７６】
１  ナビゲーションコントローラ
２  地図データ記憶装置
４  車両位置検出部
７  ビーコン送受信機
８  ＦＭ多重放送受信機
１０  地図バッファ
１２  地図読出制御部
１４  地図描画部
２０  車両位置計算部
３０  施設検索部
３２  目的地設定部
３４  経路探索処理部
３５  状態フラグ格納部
３６  経路誘導処理部
４０  ＶＩＣＳ情報取得部
４２  ＶＩＣＳ情報描画部
５０  コスト修正部
５２  走行経路置換部
１００  ナビゲーション装置
【図１】
0006478793.tif 000002
【図２】
0006478793.tif 000003
【図３】
0006478793.tif 000004
【図４】
0006478793.tif 000005
【図５】
0006478793.tif 000006
【図６】
0006478793.tif 000007