(57)【特許請求の範囲】
【請求項１】
出発地から目的地までの経路コストを計算し、経路コストが最小となる経路を探索する経路探索装置において、
前記経路コストの計算は、ノード間を接続するリンクのリンクコストを計算することを含むものであって、前記リンクコストは、リンクの種別に応じた係数が掛け合わされて算出されるようになっており、
該当するリンクが均一料金の有料道路のリンクである場合には、距離に応じて料金が変わる有料道路のリンクに対する係数より小さい係数が、前記リンクの種別に応じた係数として用いられることを特徴とする経路探索装置。
【請求項２】
探索する経路に前記均一料金の有料道路の料金所がある場合には、均一料金所通過コストが前記経路コストに加算されることを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記均一料金所通過コストは、前記料金所で支払う料金に応じた値に設定されていることを特徴とする請求項２に記載の経路探索装置。
【請求項４】
該当するリンクが均一料金の有料道路のリンクである場合に、距離に応じて料金が変わる有料道路のリンクに対する係数より小さい係数が、前記リンクの種別に応じた係数として用いられるのは、時間優先ルートの探索の場合であることを特徴とする請求項１乃至３のいずれか１つに記載の経路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路コストの計算を行って出発地から目的地への経路を探索する経路探索装置に関する。
【０００２】
【従来の技術】
従来、車両用走行案内装置において、出発地（例えば、車両の現在位置）から目的地までの経路をダイクストラ法を用いて探索し、探索された目的地経路を道路地図上に強調表示したり、あるいはその目的地経路に従って車両の進行すべき方向を指示したりして、目的地に対する走行案内を行うようにしたものがある（例えば、特開平８−３２７３８１号公報、特開平２０００−２６６５５３号公報など参照）。
【０００３】
ダイクストラ法を用いて経路探索を行う場合、経路コスト（経路に対する評価値）が計算される。この経路コストは、ノード間を接続するリンク毎に付されたリンクコストとノード毎に付されたノードコストの和から算出される。そして、経路コストが最小となるリンクの接続によって出発地から目的地までの経路が設定される。
【０００４】
また、経路探索を行う場合、時間を優先した時間優先ルートの探索、一般道を優先した一般道優先ルートの探索、有料道路を優先した有料道路優先ルートの探索のいずれかが選択できるようになっている。
【０００５】
【発明が解決しようとする課題】
上記した経路探索において、時間優先ルートの探索の場合、目的地までの所要時間が短くなるような経路が探索される。このため、図４に示すように、わずかな区間だけ均一料金の有料道路を使用する経路を探索したり、均一料金の有料道路から一般道に降りて、再び同一の有料道路区間の有料道路に乗るといった乗り直しの経路を探索することがある。その結果、わずかな所要時間の差でユーザに通行料金の負担を負わせてしまうことになる。
【０００６】
特開平１１−８３５１４号公報には、地図データ内に均一料金の有料道路リンク毎にＩＤ等をふっておき、経路探索した結果、同一の均一料金区間への乗り直しを検出すると、乗り直しのある道路区間を、該当均一料金の有料道路だけを利用する経路に変更するものが記載されている。
【０００７】
しかしながら、このものでは、経路探索が一旦終了した後に、同一の均一料金区間の乗り直しを検出すると、同一の均一料金区間でつなぐように経路探索しているため、探索時間が掛かってしまう。また、その場合に、乗り直し区間が非常に長くても乗り直し区間を同一の均一料金区間でつなごうとするため、図５に示すように、実際には、別の路線の有料道路を使用した方がよかったり、一般道のみを使用した方がよい場合でも、そのような経路を算出することができない。
【０００８】
本発明は上記問題に鑑みたもので、経路探索時間を長くすることなく、わずかな区間だけ均一料金の有料道路を使用する経路の探索を少なくして適切な経路を探索できるようにすることを第１の目的とする。
【０００９】
また、同一路線である均一料金区間の乗り直しを少なくすることを第２の目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するため、請求項１に記載の発明では、出発地から目的地までの経路コストを計算し、経路コストが最小となる経路を探索する経路探索装置において、
前記経路コストの計算は、ノード間を接続するリンクのリンクコストを計算することを含むものであって、前記リンクコストは、リンクの種別に応じた係数が掛け合わされて算出されるようになっており、
該当するリンクが均一料金の有料道路のリンクである場合には、距離に応じて料金が変わる有料道路のリンクに対する係数より小さい係数が、前記リンクの種別に応じた係数として用いられることを特徴としている。
【００１１】
このことにより、わずかな区間だけ均一料金の有料道路を使用する経路を探索することが少なくなり、なるべく均一料金の有料道路でつなぐように経路を探索することができる。
【００１２】
請求項２に記載の発明では、探索する経路に前記均一料金の有料道路の料金所がある場合には、均一料金所通過コストが前記経路コストに加算されることを特徴としている。
【００１３】
このように均一料金所通過コストを経路コストに加算することによって、同一路線である均一料金区間の乗り直しを少なくするができる。
【００１４】
この場合、請求項３に記載の発明のように、前記均一料金所通過コストを、前記料金所で支払う料金に応じた値に設定すれば、ユーザにとってよりリーズナブルな経路を探索することができる。
【００１５】
【発明の実施の形態】
図１に、本発明の一実施形態に係る車両用ナビゲーション装置の全体構成を示す。
【００１６】
ナビゲーション装置は、車両の現在位置を検出するための位置検出器１を有している。この位置検出器１は、地磁気センサ２、ジャイロスコープ３、距離センサ４、ＧＰＳ受信機５から構成されている。また、ナビゲーション装置は、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の地図データ記憶媒体（地図データ記憶手段）６ａから地図データを読み取る地図データ入力器６と、ナビゲーションに必要な各種操作を行うための操作スイッチ群７と、ナビゲーションに必要な各種処理を実行する制御回路（制御手段）８と、地図等の表示を行う表示装置９と、音声を発生する音声発生装置１０と、リモコン１２からの信号を受信するリモコンセンサ１１などを備えている。
【００１７】
地図データ記憶媒体６ａには、地図表示に用いられる地図データ、マップマッチングに用いられる地図データ、および経路案内に用いられる地図データなどが記憶されている。経路案内に用いられる地図データは、道路ネットワークデータとして構成されており、以下に説明する経路探索を行うのに用いられる。
【００１８】
ユーザが、操作スイッチ群７あるいはリモコン１２を用いて、目的地の設定の設定およびルート探索指示を行うと、制御回路８は、道路ネットワークデータを用いて、出発地から目的地までの経路を探索する処理を行う。すなわち、制御回路８は、出発地（例えば、車両の現在位置）から設定された目的地までの経路コストをダイクストラ法などにより計算し、目的地までの全ての経路コストの計算が終了すると、経路コストが最小となるリンクを接続して出発地から目的地までの経路を設定する。
【００１９】
制御回路８は、このようにして設定された目的地経路に対し、表示装置９の道路地図に目的地経路を強調表示させたり、その目的地経路に従って車両の進行すべき方向の音声を音声発生装置１０から発生させるような経路案内制御を行う。
【００２０】
上記した経路コストは、ノード毎、リンク毎にコストを付けていくことによって計算される。リンクコストは、該当するリンクについて、リンク長、車線数、幅員などのコストパラメータが掛け合わされて算出される。また、ノードコストは、右左折や信号機の有無などによって設定される。
【００２１】
このように経路コストを計算して出発地から目的地までの経路を探索することは、従来周知である。この実施形態では、従来のものと異なり、リンクコストの計算において、リンク種別に応じた係数が掛け合わされる。リンク種別は、一般道のリンク、距離に応じて料金が変わる有料道路（以下、通常の有料道路という）のリンク、均一料金の有料道路のリンクである。リンク種別に応じた係数は、時間優先ルートの探索の場合、例えば、該当するリンクが一般道のとき１．０、通常の有料道路のとき０．６、均一料金の有料道路のとき０．３である。すなわち、時間優先ルートの探索の場合、均一料金の有料道路リンクの係数が、一般道リンクおよび通常の有料道路リンクの係数よりも小さい値に設定されている。
【００２２】
また、従来のものと異なる他の点は、ノードコストにおいて、探索する経路に均一料金区間の有料道路の料金所ノードがある場合には、均一料金所通過コストが経路コストに加算されることである。この均一料金所通過コストは、固定値としてもよいが、実際にその料金所で支払う料金に応じた（比例した）値とするのが好ましい。
【００２３】
次に、ユーザが時間優先ルートの探索指示を行なった場合に、制御回路８において実行される経路コストの計算処理について説明する。その処理を図２、図３に示す。
【００２４】
リンクコストの計算では、従来のものと同様、リンク長、車線数、幅員などのコストパラメータが掛け合わされてリンクコストが算出された後、図２に示す処理が実行される。まず、該当リンクが均一料金の有料道路リンクであるか否かの判定（ステップ１０１）、該当リンクが通常の有料道路リンクであるか否かの判定（ステップ１０２）が行われる。
【００２５】
該当リンクが均一料金の有料道路リンクで、ステップ１０１の判定がＹＥＳになると、先に計算された該当リンクコストに、均一料金の有料道路リンクの係数Ａが掛け合わされる（ステップ１０３）。
【００２６】
また、該当リンクが通常の有料道路リンクで、ステップ１０１の判定がＮＯ、ステップ１０２の判定がＹＥＳになると、先に計算された該当リンクコストに、通常の有料道路リンクの係数Ｂが掛け合わされる（ステップ１０４）。
【００２７】
また、該当リンクが一般道リンクで、ステップ１０１、１０２の判定がいずれもＮＯになると、先に計算された該当リンクコストに、一般道リンクの係数Ｃが掛け合わされる（ステップ１０５）。
【００２８】
ここで、時間優先ルートの探索の場合、均一料金の有料道路に対する係数Ａ、通常の有料道路の係数Ｂ、一般道の係数Ｃは、例えばＡ＝０．３、Ｂ＝０．６、Ｃ＝１．０のように、均一料金の有料道路の係数Ａが、通常の有料道路の係数Ｂ、一般道の係数Ｃより小さい値に設定されているので、均一料金の有料道路を探索した場合、該当リンクのリンクコストは小さな値になる。
【００２９】
従って、わずかな区間だけ均一料金の有料道路を使用する経路を探索することが少なくなり、なるべく均一料金の有料道路でつなぐように経路が探索される。
【００３０】
なお、上記した処理では、リンクコストを算出した後にリンク種別に応じた係数を掛け合わせるものとしたが、リンク種別に応じた係数を他のコストパラメータとともに掛け合わせて、リンクコストを算出するようにしてもよい。
【００３１】
また、図３に示す処理においては、探索する経路にある探索ノードが均一料金の有料道路の料金所ノードであるか否かが判定される（ステップ２０１）。そして、探索ノードが均一料金の有料道路の料金所ノードであることが判定されると、均一料金所通過コストが経路コストに加算される（ステップ２０２）。この均一料金所通過コストは、均一料金の有料道路の料金所で支払う料金に応じた値のものである。
【００３２】
このように時間優先ルートの探索の場合に、ノードコストとして均一料金所通過コストが経路コストに加算されるため、均一料金区間の乗り直しを少なくすることができる。また、その均一料金所通過コストを、実際にその料金所で支払う料金に応じた値のものとすることにより、ユーザにとってよりリーズナブルな経路を探索することができる。
【００３３】
なお、上記した実施形態において、時間優先ルートの探索の場合について説明したが、有料道路優先ルートの探索、一般道優先ルートの探索も行うことができる。有料道路優先ルートの探索の場合には、上記した係数を、例えばＡ＝０．６、Ｂ＝０．６、Ｃ＝１．０、のようにし、一般道優先ルートの探索の場合には、上記した係数を、例えばＡ＝１０、Ｂ＝１０、Ｃ＝１．０のようにして、それぞれの経路探索を行う。
【００３４】
また、上記した実施形態では、本発明の経路探索装置を車両用ナビゲーション装置に適用するものを示したが、本発明は、車両外の装置、例えば情報センタで経路探索する装置、あるいはインターネットで経路探索する場合のサーバにも同様に適用することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る車両用ナビゲーション装置の全体構成を示す図である。
【図２】図１中の制御回路によるリンク種別処理を示すフローチャートである。
【図３】図１中の制御回路による均一料金所通過処理を示すフローチャートである。
【図４】従来の問題を説明するための説明図である。
【図５】従来の他の問題を説明するための説明図である。
【符号の説明】
１…位置検出器、６ａ…地図記憶媒体、６…地図データ入力器、
７…操作スイッチ群、８…制御回路、９…表示装置、
１０…音声発生装置、１１…リモコンセンサ、１２…リモコン。
【図１】
0003633495.tif 000002
【図２】
0003633495.tif 000003
【図３】
0003633495.tif 000004
【図４】
0003633495.tif 000005
【図５】
0003633495.tif 000006