経路探索方法、及びナビゲーション装置
【課題】有料道路の利用により一般道路走行に対して発生する料金と短縮できる時間による費用対効果の上でお得感の高い経路を提供する経路探索方法、及びナビゲーション装置を提供する。
【解決手段】有料道路の期待平均速度と一般道路の期待平均速度から有料道路の時間に対する料金単価を算出する有料道路対時間単価算出手段と、料金算出ルールまたは有料道路料金テーブルの少なくとも一方に基づき有料道路のリンク費用コストを算出し、リンク旅行時間からリンク時給換算コストと、燃料費を算出し、リンク費用コストとリンク時給換算コストとリンク燃料費を合成してリンク料金コストを算出する複数料金コスト加算手段とを備えて、料金コストを考慮した経路探索手段を構成する。
【解決手段】有料道路の期待平均速度と一般道路の期待平均速度から有料道路の時間に対する料金単価を算出する有料道路対時間単価算出手段と、料金算出ルールまたは有料道路料金テーブルの少なくとも一方に基づき有料道路のリンク費用コストを算出し、リンク旅行時間からリンク時給換算コストと、燃料費を算出し、リンク費用コストとリンク時給換算コストとリンク燃料費を合成してリンク料金コストを算出する複数料金コスト加算手段とを備えて、料金コストを考慮した経路探索手段を構成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステムに係り、特に車載端末を用いて車両の経路探索を行うシステムに関する。
【背景技術】
【０００２】
ナビゲーション装置において、複数の探索条件を用いて経路探索をするものが広く知られており、特に有料道路料金や燃料費などの料金を考慮し、この料金を道路リンク（道路ネットワークを構成する区間を表す）の経路探索コスト（リンクを通過するのに必要とする数値であり、距離，時間，料金などが用いられ、その合計が最適解算出時の評価値となる）として用いて経路探索する方法が存在している。
【０００３】
このとき、料金を単純に最小化するような経路を算出すると有料道路を単純に回避するような経路が算出され、費用対効果の面から必ずしもユーザにとって望ましい経路になるとは限らない。これに対して、特開２００８−８２８８４号公報では、一般道路優先で探索した経路の走行時間及び有料道路料金の合計と、有料道路優先で探索した経路の走行時間及び有料道路料金の合計とから、有料道路利用時の短縮時間とその有料道路料金を短縮時間で割った単位時間当たりの料金を算出し、単位時間当たりの料金が予め設定しておいた単位時間当たりの料金の閾値を超えているか否かを判別して、単位時間当たりの料金がこの閾値より大きい場合は一般道路優先経路を表示し、小さい場合は有料道路優先経路を表示するナビゲーション装置を開示している。このように有料道路利用における対費用効果の良し悪しを判断する目安として予め閾値を設定させておくことで、費用対効果の面でユーザに望ましい経路が提示できるとしている。
【０００４】
また、走行に直接必要なコストとして燃料費があるが、この燃料費の計算式としては、大口らの燃料消費量モデルが知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−８２８８４号公報
【非特許文献】
【０００６】
【非特許文献１】大口 敬ほか：「都市部道路交通における自動車の二酸化炭素排出量モデル」、土木学会論文集、Ｎo.６９５／ＩＶ−５４ pp.１２５−１３６（２００２）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、ユーザにとって単位時間当たりの料金を設定することは煩雑であり、設定した値自体が適切か否かを走行前に判断することも困難である。例えば、遠隔地に行きたいときに有料道路を使う、といったケースにおいてユーザが単位時間当たりの料金閾値を適切に設定することは困難である。特開２００８−８２８８４号公報では過去の指定経路に基づきこの閾値を更新する方法を提示しているが、初期段階で適切な経路を選択できなければ、次回以降も適切な閾値を設定することは困難である。
【０００８】
また、閾値を用いて有料優先経路と一般優先経路を比較する場合に、既存のコスト計算方法によって算出したルートの評価をするのみであって、新しいコスト計算方法に基づいて経路探索をするわけではない。すなわち、有料優先経路，一般優先経路とも異なる別のルートを経路探索結果として提示することが困難である。
【０００９】
本発明はユーザによる適切な料金閾値設定の困難さと、有料優先経路，一般優先経路とも異なる費用対効果の面で望ましい経路探索結果を提示する課題を解決する経路探索方法、及びナビゲーション装置を提供するものである。
【課題を解決するための手段】
【００１０】
本発明では、有料道路の期待平均速度と一般道路の期待平均速度と有料道路料金対距離単価から有料道路利用時の有料道路料金対時間単価を算出し、有料道路対時間単価に対し所要時間に応じた時給として定まる料金単価として時給換算単価を算出し、料金算出ルールまたは有料道路料金ＤＢの少なくとも一方に基づき有料道路のリンク費用コストを算出し、リンク旅行時間と時給換算単価からリンク時給換算コストを計算し、少なくともリンク費用コストと時給換算コストとを加算したトータルのリンク料金コストを算出し、これを用いた経路探索を行う経路探索方法を提供する。
【００１１】
また、本発明では、外部からの情報により料金算出ルールを更新する料金ルールを更新し、更新された料金算出ルールに基づき有料道路のリンク費用コストを算出し、リアルタイム交通情報またはリンク速度データベースの少なくとも一方に基づきリンク旅行時間を算出し、リンク旅行時間と時給換算単価からリンク時給換算コストを計算し、リンク費用コストとリンク時給換算コストとリンクあたりの燃料費を加算したリンク料金コストを算出し、経路探索を行う経路探索方法を提供する。
【００１２】
さらに、本発明では、前記経路探索方法を用いて算出したリンク料金コストを利用して経路探索処理を行う経路探索手段を備えるナビゲーション装置を提供する。
【発明の効果】
【００１３】
ユーザに煩雑な設定を強いることなく、有料道路を走行することで一般道路走行に対して発生する料金と、有料道路，一般道路それぞれの期待平均速度から算出する期待短縮時間とから算出できる時給換算単価（所要時間に対して仮想的に発生する料金）を算出し、リンク旅行時間と時給換算単価から算出される一般道路と有料道路の時給換算コストの差に対して有料道路利用料金が安い場合を「お得」と定義し、「お得」な場合には有料道路を、「お得」でない場合には一般道路を区間ごとに利用する経路を提供する経路探索方法、及びナビゲーション装置が実現できる。また有料道路料金の料金体系が途中で変化し、割引率の高い区間の高速料金が「お得」であるが割引率の低い区間の高速料金が「お得」でない場合には、割引率の高い「お得」な区間のみ利用するような経路探索結果を提示することが可能となる。また、有料道路と一般道路とを組み合わせた経路を提示し、「お得」な区間を明示するナビゲーション装置を実現することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明を用いた経路探索部の構成図である。
【図２】本発明における経路探索コスト決定方法の原理説明図である。
【図３】距離・集金表の例を示す図である。
【図４】有料道路の対時間単価算出処理のフローチャートである。
【図５】時給換算単価算出処理のフローチャートである。
【図６】リンク料金コスト算出処理のフローチャートである。
【図７】本発明を用いた経路探索部の変形の構成図である。
【図８】料金ルール更新処理のフローチャートである。
【図９】リンク料金コスト算出処理のフローチャートである。
【図１０】時間帯別リンク速度ＤＢの例を示す図である。
【図１１】本発明を用いたナビゲーション装置の図である。
【図１２】経路探索時の画面遷移図である。
【図１３】設定変更画面である。
【図１４】料金割引があったときの経路探索コスト決定方法の原理説明図である。
【図１５】料金ルールプロファイルの例を示す図である。
【図１６】有料道路の対距離単価の算出処理のフローチャートである。
【図１７】有料道路の対時間単価の算出処理のフローチャートである。
【図１８】リンク料金コスト計算の例を示す図である。
【図１９】経路探索処理のフローチャートである。
【図２０】経路探索で用いるノード群を構成するノードデータのデータ構造を示す図である。
【図２１】本発明を用いたセンターに通信によって接続するナビゲーション装置と周辺システムを表す図である。
【発明を実施するための形態】
【００１５】
本発明による経路探索方法、及びナビゲーション装置の実施の形態を、図面を参照して説明する。
【実施例１】
【００１６】
図１は本発明を用いた経路探索装置における経路探索部１００の構成を示す図である。経路探索部１００では、出発地，目的地の入力を受け付けて、本発明による経路探索コスト決定方法を用いた経路探索結果を出力する。料金コスト利用経路探索手段１０４は、出発地と目的地の入力に対してネットワーク地図ＤＢ１１１（経路探索に用いるノードとリンクの接続関係，リンクの属性情報が含まれる）を用いて、所要時間の増加に伴い発生する仮想的な時給換算料金も経路探索のコストに反映されるように考慮した経路探索結果を求める手段である。
【００１７】
有料道路対時間単価算出手段１０１は、設定値記憶部１１０に格納されている、有料道路の走行に予想される平均速度，一般道路の走行に予想される平均速度、および有料道路料金の対距離単価から、有料道路の利用可否判断を行う際に用いる有料道路利用時の時間に対する料金単価を算出する。
【００１８】
ここで道路の走行に予想される平均速度のことを期待平均速度と呼ぶことにする。期待平均速度は、後に説明する設定入力部１１３による設定画面を介してユーザが指定した設定値，制限速度などの規制速度，走行実績、あるいは過去の交通情報から算出した、地域または道路ごとに異なる速度のいずれかを与える。期待平均速度は、実際の経路を探索する前に、全体の走行予定距離の概算に対して所要時間を見積もる際に用いるため、個々の道路リンクを参照しなくても済むように、ある程度一律の値として定めておいてもよい。例えば、一番粗く定める場合には有料道路と一般道路に分けて定め、細かく定める場合には、地図のメッシュ単位あるいは各地図メッシュにおける有料道路と一般道路ごとに定めればよい。期待平均速度として走行実績を用いる場合には、過去に有料道路や一般道路を走行したときのそれぞれの平均速度を用いる。この場合でも、細かく分類する場合には、地図のメッシュ単位（地図メッシュごとの道路リンクの平均速度）を用いる。本実施例では、道路を有料道路と一般道路に分けて、有料道路の走行に予想される平均速度（有料道路期待平均速度）と一般道路の走行に予想される平均速度（一般道路期待平均速度）を設定値記憶部１１０に記憶しておくものとする。
【００１９】
有料道路料金の対距離単価は、有料道路の走行距離に対応した利用料金を計算するための距離に対する料金単価である。この値としては、有料道路によって定められた料金ルールを用いるか、有料道路料金ＤＢ１０５に格納されている各有料道路の料金表情報に基づき、地域ごと、あるいは道路ごとに料金所間の料金から予め算出しておいてもよい。料金ルールとして距離逓減（距離に応じて料金単価が減少する）ルールがあるような場合は、距離逓減ルールを適用しない通常の対距離単価及び距離逓減が発生する閾値距離と逓減時の料金単価を対距離単価として持つようにする。
【００２０】
有料道路期待平均速度，一般道路期待平均速度，有料道路料金の対距離単価は、経路探索前に予め設定しておく値であり、本実施例では、これらの値はハードディスク装置や不揮発性メモリなどの書き換え可能な記憶媒体により構成される設定値記憶部１１０に格納されているものとする。
【００２１】
時給換算単価算出手段１０２は、有料道路対時間単価算出手段１０１で算出した有料道路料金の対時間単価を用いて、有料道路を走行した場合に比べて一般道路を走行した場合の所要時間の増加分を、走行に要した時間増加分に対する時給として仮想的な料金に換算するための、時間当たりの料金単価（以下では時給換算単価とする）を算出する。
【００２２】
リンク単位処理部１０６は、経路探索処理においてリンク単位の処理を行う所である。ここでは一般的な経路探索処理としてダイクストラ法などの最小コスト求解方法が利用され、入力された出発地−目的地間のリンクごとにリンク料金コストを加算していき、その合計が最小となるリンク列が探索結果として算出される。そして加算するリンク料金コストは、リンク費用コスト算出手段１０７，リンク時給換算コスト算出手段１０８，複数料金コスト加算手段１０３により計算される。
【００２３】
リンク費用コスト算出手段１０７は、有料道路料金ＤＢ１０５に格納されている割引率などの情報を含んだ有料道路の料金算出ルールに基づき、リンクごとの有料道路料金に相当するリンク費用コストを算出する。リンク時給換算コスト算出手段１０８は、リンク旅行時間と時給換算単価算出手段１０２で求めた時給換算単価からリンク時給換算コストを計算する。リンク旅行時間は、ネットワーク地図ＤＢに含まれる個々のリンクの所要時間コスト、又は車速の概算値として期待平均速度を用いリンク長から求めたリンクの所要時間、あるいは後述するように外部から配信された交通情報を用いてもよい。複数料金コスト加算手段１０３は、リンク費用コスト算出手段１０７で求めたリンク費用コストと、リンク時給換算コスト算出手段１０８で求めた当該リンクにおけるリンク時給換算コストと、車両走行のために消費する燃料費の３つの料金コストを合計してリンク料金コストを算出する。
【００２４】
探索結果出力手段１０９は、リンク料金コストを用いた経路探索によって求まる最小コスト経路のリンク列を経路探索結果として出力する。
【００２５】
図１の構成によって算出される最小料金コスト経路は、前述の時給換算単価に基づく実際には費用が発生しない仮想的な時給換算コストの概念を用いているため、算出された経路の実際の料金コストである有料道路料金と燃料費の合計値の最小解ではないが、走行に要した時間を金銭に換算して含めた最小解となる。よって料金と時間とを考慮した上でユーザに「お得」感のある経路（以下ではエコノミールートと表現）となる。
【００２６】
まず図１の構成によりエコノミールートを算出する処理の概略について図２及び図１４を用いて説明し、次に各処理の詳細については図３ないし図６を用いて説明する。
【００２７】
図２（ｂ）はある出発地から目的地までの全ての経路の時間に対する有料道路料金，時給換算コスト及び燃料費の変化を示したものである。図２（ｂ）において、縦軸は料金、横軸は出発地から目的地到着に要する走行時間（出発地から目的地までの所要時間に対応しており、信号停止など交通全体に及ぼす時間は含むが、休憩時間は含まない）、をとっている。図２及び図１４の説明では簡単のため、出発地から目的地までは図２（ａ）に示すように有料道路，一般道路は完全に並行し、乗降りは有料道路上の任意の地点で自由に行えるものと仮定したときの経路について考える。この図２（ｂ）の有料道路料金のグラフで最速となるのは全線有料道路を利用した場合に相当し、一般道最速は一般道のみの最適経路を全線利用した場合に相当する。なお、一般道最速の状態よりも走行時間が大きくなる状態は、一般道路を利用した遠回りとなる区間を走行する場合に相当する。
【００２８】
チャート２０１は有料道路料金，時給換算コスト及び燃料費それぞれの料金コストを個別に表現したものであり、ライン２０３は有料道路料金の時間に対する変化、ライン２０４は燃料費の時間に対する変化、ライン２０５は時給換算コストの累計値を表している。チャート２０１において、有料道路料金，燃料費及び時給換算コストの各料金コストを表すライン２０３，２０４，２０５で、料金が最小となっている箇所が各料金コストをそれぞれ個別で用いたときの最小料金コストとなり、最小空間を探索する方法によって料金を最小にする解が求まる。言い換えれば、チャート２０１で現した特性空間での最小料金の解は、実際の経路探索において用いられる最小コスト解探索アルゴリズムであるダイクストラ法などを用いることによって最小料金コスト経路として求めることができる。
【００２９】
次に、それぞれの料金コストについてチャート２０１上での特徴を説明する。有料道路料金２０３は、有料道路と一般道路利用区間の区間長に応じて定まる料金コストである。通常のケースでは有料道路利用区間が長ければ長いほど高速走行が可能となり走行時間が短縮できるため、チャート２０１上では負の傾きをもって現すことができる。その傾きの大きさは以下のように概算できる。出発地から目的地までの道のり距離（道路上を走行したときの距離）をＤとし、このとき有料道路の利用区間をＤ１、一般道路の利用区間をＤ２とする。このとき、図２（ａ）のように有料道路と一般道路は完全に並行するものと仮定していることから、
Ｄ＝Ｄ１＋Ｄ２ … （式１）
と置くことができる。ここで有料道路の走行速度はＶ１一定、一般道路の走行速度はＶ２一定であると仮定すると、その所要時間Ｔは以下の式で計算できる。
【００３０】
Ｔ＝Ｄ１／Ｖ１＋Ｄ２÷Ｖ２ … （式２）
【００３１】
式１，式２を変形し、有料道路の利用区間Ｄ１について解くと以下の式となる。
【００３２】
Ｄ１＝Ｖ１×Ｖ２÷（Ｖ１−Ｖ２）×（Ｄ÷Ｖ２−Ｔ） … （式３）
【００３３】
このとき有料道路料金は、実際には距離逓減制度などにより単純比例で距離に応じて料金が下がるとは限らないが、距離が長くなれば料金が増加する傾向は近似できる。そこで、有料道路の利用距離に対する単価で単純に現した場合、この有料道路の対距離単価をαとすると、有料道路料金の変化分はα＊Ｄ１で表現される。よって所要時間Ｔに対する料金の傾きＣｔは式３を利用して以下となる。
【００３４】
Ｃｔ＝−α×Ｖ１×Ｖ２÷（Ｖ１−Ｖ２） … （式４）
【００３５】
通常有料道路の走行速度Ｖ１＞一般道路の走行速度Ｖ２であるので、走行時間に対する料金の傾きＣｔは負となる。例としてＶ１＝９０［km／時］，Ｖ２＝３０［km／時］，α＝３０［円／km］（＝日本の高速道路料金の概算値）とすると、Ｃｔ＝−１３５０［円／時］となる。
【００３６】
式３の両辺にαを乗ずることによってチャート２０１の有料道路料金２０３は式４を用いて
有料道路料金の変化分＝α×Ｄ１＝Ｃｔ×Ｔ＋α×Ｖ１÷（Ｖ１−Ｖ２）×Ｄ
… （式５）
として表され、有料道路料金は走行時間Ｔに対して負の傾きをもつ一次関数として近似できる。図２（ａ）で示した仮定により、時間が最も小さい（＝最速）なのは全て有料道路を利用したときとなり、全て一般道を利用して目的地まで有料道路に並行して向かったとき（＝一般道最速）には、Ｄ１＝０となり、有料道路料金＝０となる。この仮定では有料道路に並行する以外の一般道路は存在しないが、実際には一般道路で遠回りする経路が考えられる。このとき、一般道路の速度はＶ２を一定と仮定していることから、遠回り経路は、一般道最速よりも走行時間が大きい走行時間の領域となる。このときの有料道路料金は０となる。
【００３７】
一方、燃料費２０４の時間に対する料金変化を考える。燃料費の計算式としては、大口らの燃料消費量モデルを用いると以下の式で表すことができる。
【００３８】
燃料消費量＝Ｆｃ×Ｔ＋Ｃｆ×Ｄ＋空気抵抗分＋高度変化分＋速度変化分
… （式６）
【００３９】
式６において、Ｆｃは時間当たりの燃料消費量、Ｃｆは摩擦などによる距離当たりの燃料消費係数を表す。式６で第一項は走行時間に比例する項、第二項は走行距離に比例する項、第三項は空気抵抗分、第四項は高度変化分、第五項は加減速に伴う速度変化分を表す。チャート２０１では燃料消費量の走行時間に対する関数として表しているので、式６の各項の特徴を述べる。第一項は走行時間に比例する項、第二項は図２（ａ）で示した仮定により距離は一定なので走行時間に対しては定数である。第三項は高速走行と一般走行とで差があるが、燃料消費量全体からみると空気抵抗の占める割合は小さい。第四項は高度差の項であるが、図２（ａ）のような仮定では出発地，目的地が同じく並行道路であることから走行時間からみると一定値、第五項は一定速度の仮定によりゼロとなる。すなわち走行時間に対する影響としては、第一項と第三項を考えればよい。また第三項の空気抵抗分は第一項に対して影響が小さいので、第一項のみ考慮すればよいが、第一項は走行時間に対して正の傾きをもつものの、有料道路利用に対する傾きに対して小さいと予想され、チャート２０１に示す程度となる。
【００４０】
例として、時間当たりの燃料消費量が０.５［cc／秒］であり、燃料単価を１５０［円／１,０００cc］とすると時間に対する変化量は、２７０［円／時］となる。よって有料道路料金のライン２０３と燃料費のライン２０４のみを加算した料金コストをチャート２０１上で考えても、有料道路料金のライン２０３の負の傾きが大きく、有料道路を利用しない一般道路優先が料金コスト最小解となる可能性が強くなる。また一般道路で最速となる走行時間よりも走行時間が長くなる場合は、前述のように一般道路を遠回りする経路にあたり、有料道路料金は０で一定、燃料費は単純増加となり合計の料金コストも時間に対して単純増加することになる。
【００４１】
本発明では、料金と時間とを考慮した上で「お得」感のある経路を求めるため、時給換算コストのライン２０５の概念を加えることにより、料金優先／時間優先以外に料金と時間をともに考慮した経路を求めることが可能となる。そして、時給換算コストのライン２０５の傾きが、想定した有料道路料金コストのライン２０３の傾きを相殺する傾きであれば、即ち時給換算コストのライン２０５の傾きＣを前述の有料道路料金のライン２０３の傾きＣｔを相殺するようにＣ＝−Ｃｔとすれば、ライン２０６に示した有料道路＋燃料費＋時給換算コストの概形のように、走行時間に対して料金が大きく変化しないような解空間を作成することができる。実際には式１や式２の仮定と異なり、有料道路料金の地域性や、有料道路利用時と一般道路利用時の距離は有料道路の利用出入り口によって変化すること、また走行速度の傾向が地域や交通状況によって変化する異などから、実際の有料道路料金，時給換算コスト及び燃料費の合計はライン２０７のように変化することが予想され、この料金変動の中でもっともエコノミーな解、即ち最小料金コストの解が求まることとなる。
【００４２】
図１４は、有料道路の料金割引制度が存在する場合の有料道路料金と、時給換算コスト及び燃料費の変化を示したものである。簡単のため図２（ａ）に示すように、出発地から目的地までは、有料道路，一般道路は完全に並行しており、有料道路への乗り降りは自由であるとしたときの経路について考える。チャート１４０１はそれぞれの料金コストを個別に表現したものであり、ライン１４０３は有料道路料金の走行時間に対する変化、ライン２０４は燃料費の走行時間に対する変化、ライン２０５は時給換算コストの走行時間の増加に伴う累計値を表し、縦軸に料金、横軸に走行時間をとっている。なお、ライン２０４，２０５に関しては、図２（ｂ）と同一である。有料道路の料金割引制度が、ある一定距離までは半額、それ以降（以遠）は通常料金といった離散的な料金体系（例としては、日本のＥＴＣ割引制度）となっている場合、料金割引が適用される距離の範囲内で有料道路を利用したとき、ライン１４０３のように割引範囲内を走行した時間に対して急激に料金が変化することとなる。ライン２０５のような料金割引が無い場合の有料道路利用料金の変化を相殺するような時給換算コストを適用することで、点線で示したライン２０３の通常の有料道路料金とライン１４０３に示す割引後の料金の差の分が、料金割引が適用された場合のコスト合計値を表すライン１４０４と料金割引が無い場合のコスト合計値を表すライン２０６の差となり、有料道路料金＋燃料費＋時給換算コストの概形１４０４はチャート１４０２に示すように料金が変化した点を最小解とするような特性を示しうる。すなわち、このことは料金割引区間において有料道路を利用し、その他の区間は一般道路を通るといったエコノミールートが算出しうることを示すものである。
【００４３】
以上で示した考え方に基づき、有料道路の利用時間に対する料金の変動を相殺するような時給換算コストを算出して利用する方法を、図３ないし図６を用いて説明する。
【００４４】
図４は、有料道路対時間単価算出手段１０１の処理を示したフローチャートである。フローチャートにおける各処理ステップ（ステップは図中ＳＸＸＸとして記載する）の内容は以下のようになる。
【００４５】
Ｓ４００：この処理ステップでは、経路探索エリアを算出する。経路探索エリアは、料金コスト利用経路探索手段１０４に予め入力された出発地と目的地を含むように決定し、例えば出発地，目的地を頂点とする長方形領域に出発地，目的地のお互いに離れる方向の後方エリアを含むような領域としてもよい。そして、探索対象となる地域のエリアのコードを出力し、後述する処理において地域の特定に利用する。
【００４６】
Ｓ４０１：この処理ステップでは、有料道路，一般道路それぞれの期待平均速度を設定値記憶部１１０から読み込む。各期待平均速度は前述のようにして予め定められ、例えば所要時間計算時に用いるために予めシステムが定める速度を用いてもよい。システムが定める速度として、規制速度を用いる場合、それぞれの道路の規制速度に対して一定割合を掛けた（たとえば８割）速度でもよい。
【００４７】
Ｓ４０２：この処理ステップでは、実際の経路探索の前に予め有料道路料金の概算値を求めておくための準備として、有料道路の予想走行距離を算出する。ここでは例えば、出発地と目的地の直線距離（経路探索前）、あるいはその一定倍率の距離、または出発地と目的地の緯度経度差を単純に加算した距離などにより、全体の走行予定距離を算出する。さらにネットワーク地図ＤＢで地図情報を矩形領域ごとに管理しておき、経路探索エリアに対応する各矩形領域内に有料道路を含むかどうか判定することで出発地，目的地間を結ぶ直線あるいはその周辺領域に有料道路が全く存在しない矩形領域が明らかにわかる場合には、その矩形領域の一辺の長さなどを元に領域の通過想定距離を求めて全体の予想走行距離から差し引いて、有料道路の予想走行距離を算出する。
【００４８】
Ｓ４０３：この処理ステップでは、有料道路の予想走行距離に対する料金単価を算出する。この料金単価は、設定値記憶部１１０に設定された有料道路料金の対距離単価の値の中から走行予定地域の代表値を読み出す。本処理で求める有料道路料金の対距離単価は、有料道路の走行料金に相当する時給換算コストを計算するためのものであり、道路区間ごとに正確である必要はなく、ここの有料道路区間の料金単価が時給換算コストに対して「お得」かどうかを判定するためのものである。
【００４９】
例えば日本の都市間高速道路のように、距離に対して一定と想定される場合には、予め指定した値を使えばよい。距離に応じて明らかに料金が異なるような場合、距離に対する料金ルールに応じて料金単価を設定する。たとえば１００km以上に距離逓減制度（ある距離を過ぎたら、それ以降の距離単価が割り引かれる制度）がある場合や、一定料金が加算されるような場合は、こうした要因を考慮して利用料金を積み上げ、それを予想走行距離で割ることにより、料金の対距離単価を設定してもよい。
【００５０】
地域によって異なる有料道路料金体系が存在する場合は、その地域内に存在する有料道路料金単価の最大値，平均値，最小値といった代表値を取得し、料金単価を計算してもよい。地域内の有料道路料金単価は、ネットワーク地図ＤＢ１１１に格納されている地図データ及び図３に示すような有料道路料金ＤＢ１０５の距離・料金表３０１から計算することもできるし、予め計算した値を地域ごとにネットワーク地図ＤＢ１１１の地図に含めておいてもよい。また、距離によらず区間一定の料金体系をとる有料道路区間が存在する場合には、地域内の有料区間の料金を平均し、それを区間距離合計で割ることによって距離に対する料金単価を計算できる。
【００５１】
本発明の有料道路には、都市中心部進入によって課金される渋滞課金の区間を含んでもよい。この場合、区間ごとに一定の料金が発生する料金ルールを適用することにより、渋滞課金が適用されるエリアの大きさを表す代表長（半径やエリアの一辺）の大きさを走行予定距離とし、課金料金をこの代表値で割ることにより料金の距離単価が計算できる。渋滞課金エリアを避ける経路は、この料金単価から算出される時給換算コストを後述する図６の処理により小さめにとることによって実現できる。
【００５２】
図１６に、距離逓減制度がある場合の距離に対する有料道路料金単価を算出する処理のフローチャートを示す。本処理はＳ４０３の処理の一つの例を示したものである。
【００５３】
Ｓ１６０１：この処理ステップでは、Ｓ４０２で求めた有料道路の走行予定距離（ｄ）と距離逓減制度により料金が変化する距離（ｄｓ）を比較する。走行予定距離入力（ｄ）が料金が変化する距離（ｄｓ）以下の場合（ＮＯの場合）Ｓ１６０３に、そうでなければ（ＹＥＳの場合）Ｓ１６０２に進む。
【００５４】
Ｓ１６０２：この処理ステップでは、式５を用いて、ｄｓまでの有料道路料金の対距離単価（αｓ）とｄから料金の増加分（Ｔｉ）を算出する。有料道路料金の対距離単価（αｓ）は設定値記憶部１１０から読み込む。この値は一定値でもよいし、外部媒体によって更新されてもよい。
【００５５】
Ｓ１６０３：この処理ステップでは、αｓとｄｓ，ｄｓ以降の有料道路料金の対距離単価（αｆ）とｄから走行予定距離（ｄ）に対する料金の増加分（Ｔｉ）を、料金が変化する距離（ｄｓ）までの料金とｄｓ以降の料金の和として式５を用いて算出する。ｄｓ以降の有料道路料金の対距離単価（αｆ）に関してもαｓと同様に設定値記憶部１１０から読み込む。
【００５６】
Ｓ１６０４：この処理ステップでは、料金の増加分（Ｔｉ）に有料道路料金のベースとなる一定料金を加算し、これに税率を掛けて距離ｄにおける予想料金（Ｔｏ）を算出する。
【００５７】
Ｓ１６０５：この処理ステップでは、全区間平均での料金単価（α）をＴｏとｄにより算出する。
【００５８】
例えば、ｄ＝１５０km，ｄｓ＝１００km，αｓ＝２４.６km／円，αｆ＝１８.４５km／円，一定料金＝１５０円，税率＝５％とすると、α＝２５.８km／円となる。
【００５９】
図４に示す処理フローの説明に戻る。
【００６０】
Ｓ４０４：この処理ステップでは、設定値記憶部１１０から読み出した有料道路，一般道路の期待平均速度Ｖａ，Ｖｔから有料道路の走行時間に対する料金を表す対時間単価Ｃｔを算出する。式４によって、有料道路，一般道路それぞれの平均速度Ｖ１，Ｖ２として有料道路期待平均速度Ｖｔ，一般道路期待平均速度Ｖａを代入し、Ｓ４０３で算出した対距離単価αを代入することで、有料道路料金の対時間単価Ｃｔ、すなわち時間に対する有料道路料金の傾きを算出することができる。Ｓ４０４で算出した有料道路料金の対時間単価Ｃｔは、有料道路対時間単価算出手段１０１の処理結果として図示されていない一時記憶の中に保持する。
【００６１】
図１７は、有料道路料金の対時間単価（Ｃｔ）を算出する処理の例であり、Ｓ１７００で有料道路料金の対距離単価（α），有料道路の期待平均速度（Ｖｔ），一般道路の期待平均速度（Ｖａ）を設定値記憶部１１０から読み込み、Ｓ１７０１に示すように、式４から有料道路料金の対時間単価Ｃｔが計算できる。一例として、Ｖｔ＝８０km／時，Ｖａ＝４０km／時，α＝２４.６km／円とすると、Ｃｔ＝−１９８４円／時となる。
【００６２】
図５は、時給換算単価算出手段１０２の処理を表したフローチャートである。
【００６３】
Ｓ５０１：この処理ステップでは、有料道路対時間単価算出手段１０１によって算出した有料道路料金の対時間単価Ｃｔを読み込み、符号を反転させた値を時給換算単価Ｃとする。この符号を反転させた時給換算単価Ｃを用いることにより、事前の想定に対して有料道路の平均速度が事前に設定された有料道路期待平均速度よりも速いまたは有料道路料金が通常よりも安い、即ち費用対効果の面で有料道路の利用が「お得」な区間については有料道路を優先し、有料道路の平均速度が有料道路期待平均速度よりも遅いあるいは一般道路の平均速度が一般道路期待平均速度よりも速い区間については一般道路が優先されることとなる。
【００６４】
図１８は上記それぞれのケースについて例示したものである。共通の条件としては、有料道路の期待平均速度を８０km／時、一般道路の期待平均速度を４０km／時とする。また、有料道路料金の対距離単価αは２４.６円／kmとしている。また、図２（ａ）の仮定の下で有料道路，一般道路ともに走行距離は２０kmとする。この時の時給換算単価Ｃは、図１７の説明で用いた例から、図１６で説明した一定料金は考慮せず税率を５％とした場合には２０６４円／時となる。ケース１は有料道路の走行速度が１００km／時と期待平均速度Ｖｔより早く、ケース３は、走行区間の有料道路料金が割引制度により半額となったケースであり、有料道路料金と時給換算コストを単純に加算した有料道路の総費用は一般道路のそれよりも小さく、単純に並行する区間であればコストが小さい区間が選ばれることとなる。逆にケース２は有料道路が６０km／時と想定より遅く、ケース４は一般道路が６０km／時と想定よりも速い場合であり、どちらのケースも一般道路の方が総費用が小さくなっている。すなわち時給換算コストによる期待平均速度における有料道路区間のキャンセル効果が得られている。
【００６５】
Ｓ５０２：この処理ステップでは、ユーザ設定により時給換算単価Ｃの調整を行う。ユーザ設定では、図１３に示すような画面を用いて時給換算単価Ｃを調整する。ユーザが時給換算単価を増やす方向に調整すれば、時間に対する重みが増えることとなり、経路探索結果は有料道路区間がより多く選択される傾向となる。逆にユーザが時給換算単価を減らす方向に調整すれば、時間に対する重みが減ることとなり、経路探索結果では一般道路区間がより多く選ばれる傾向となる。この調整処理を備えることにより、今までの基準よりも有料道路区間を増やしたりあるいは所要時間を遅くしたりといった設定が、基準の値からの増減といった形でユーザの好みにより設定できる。また設定値記憶部１１０に記憶している値を出発地，目的地と対応付けて別途不揮発性の記憶装置に格納しておき、経路探索時にこの値を呼び出した後、基準の値をＳ５０１までの処理によって設定しておくことで、過去の同一出発地，目的地を対象とした経路との有料道路区間の利用割合を比較できるため、ユーザは試行錯誤によって基準の値を設定する手間が省けることとなる。
【００６６】
図１３は、時給換算単価Ｃの調整を行うための画面を説明したものである。時給換算単価Ｃと、有料道路対時間単価Ｃｔの間は、Ｃ＝−Ｃｔという関係としているため、時給換算単価Ｃの調整は有料道路対時間単価Ｃｔを調整することによって実現できる。そしてこの有料道路料金の対時間単価Ｃｔの算出には、期待平均速度Ｖｔ，Ｖａが用いられるため、これらの期待平均速度Ｖｔ，Ｖａを変更すればよい。このため、図１３に示す画面を操作することで、期待平均速度Ｖｔ，Ｖａを変更する。１３０１は基本設定画面、１３０２は詳細設定画面、１３０３は有料道路料金の対時間単価Ｃｔの加算ボタン、１３０４は逆に有料道路料金の対時間単価Ｃｔの減算ボタン、１３０５は詳細設定画面への遷移ボタン、１３０６は有料道路の期待平均速度の設定値入力欄、１３０７は一般道路の期待平均速度の設定値入力欄、１３０８は設定変更に伴う状態変化を示すグラフ、１３０９は基本設定画面への遷移ボタンである。
【００６７】
ボタン１３０３は対時間単価の絶対値を所定の単位で増加させ、ボタン１３０４は対時間単価を所定の単位で減少させる。具体的には、式４とＣ及びＣｔの関係から、時給換算単価Ｃが常に正の値を取るようにして、Ｃ＝対時間単価の絶対値｜Ｃｔ｜＝α×Ｖｔ×Ｖａ÷（Ｖｔ−Ｖａ）に対して、増減幅をｄＣとして設定変更後の時給換算単価をＣ±ｄＣに再設定する。そして、有料道路の料金体系が頻繁に変わることが無ければ料金の対距離単価αが変わることも無く、統計交通情報を用いることで予め一般道路における平均速度をある程度正確に評価できることから一般道路期待平均速度も大きく変更する必要が無く、むしろ有料道路の利用でどれだけ所要時間が短縮され又料金が高くなるかに関心が高いものと仮定して、新たに設定した時給換算単価に対して、有料道路料金の対距離単価α，一般道路期待平均速度（Ｖａ）を固定すれば、新たに設定した時給換算単価に対応した対時間単価に対する有料道路期待平均速度（Ｖｔ）が求まる。対時間単価の絶対値を増加することにより、時給換算単価Ｃが有料道路料金に比べて増大するため、エコノミールートはより時間重視の経路探索結果を出力するようになる。逆に対時間単価を減少することにより、時給換算単価が有料道路料金に比べて減少するため、エコノミールートはより料金重視の経路探索結果を出力するようになる。ユーザにとっては、簡便な操作によってエコノミールートの設定変更が可能となる。
【００６８】
ボタン１３０５は画面を詳細設定画面１３０２に遷移させる。詳細設定画面１３０２では、有料道路及び一般道路の期待平均速度を直接設定し、有料道路を優先する目安となる速度を直接操作することができる。状態変化を表すグラフ１３０８では、横軸に有料道路の期待平均速度，縦軸に一般道路の期待平均速度を示しており、実線によって新しい設定における有料，一般利用の境界線を示し、有料道路利用となる速度領域を網掛けで示している。また、破線によって現在の設定における有料道路利用と一般道路利用の境界線を表し、設定変更による有料道路利用領域の変化を表示する。境界線はＣを一定としたときのＶｔ，Ｖａの関数関係を表した特性曲線である。前述の関係式Ｃ＝｜Ｃｔ｜＝α×Ｖｔ×Ｖａ÷（Ｖｔ−Ｖａ）をＶａに関して解くと、
Ｖａ＝１÷ｋ×（１−１／（ｋ×Ｖｔ＋１）） ただしｋ＝α÷Ｃ … （式７）
という曲線になる。この曲線はＶａ＞０，Ｖｔ＞０の範囲で単調増加、かつ上に凸の形状を示す。期待平均速度の組み合わせは点として１３０８中に表現し、現在値及び設定変更による推移した値を表示する。有料道路料金の所要時間に対する変化とバランスするように時給換算コストを設定していることから、Ｃを一定とした場合の式７による曲線は、有料道路利用のお得感がちょうど釣り合うような有料道路及び一般道路の期待平均速度の組み合わせ、つまりお得感が同じ期待平均速度の状態を表していると見ることができる。そこでこのグラフ１３０８により、ユーザは設定されている速度以外での有料道路，一般道路の期待平均速度の状態において、有料道路利用優先になる領域を把握することができる。すなわちユーザが普段居住している地域の有料道路利用，一般利用の期待平均速度を入力することによって、交通状況が異なり走行速度が変わる地域で「お得」なのは有料優先となるか一般優先となるかを判断することが可能となる。
【００６９】
本設定画面により、ユーザは簡便にパラメータ調整が可能となり、また、速度によって有料道路利用，一般利用を見通すことができるようになる。
【００７０】
以上、図３から図５の処理が最小料金コスト経路探索を行うための前処理である。以下では、料金コスト利用経路探索手段１０４における最小料金コスト経路探索について図１９，図２０を用いて説明する。
【００７１】
図１９は、最小料金コスト経路探索処理のフローチャートを表し、図２０は経路探索で用いるノード群を構成するノードデータのデータ構造を示している。図１９は経路探索の一般的手法として知られるダイクストラ法の処理フローを表したものであるが、図２０に示したようにノード到達時刻，有料道路入口ノードを持ち、これらのデータを更新することによって料金コスト計算を可能としている点が料金コスト探索を実現するための特徴である。以下図１９のフローチャートについて説明し、必要に応じて図２０のデータ構造について説明する。
【００７２】
Ｓ１９００：この処理ステップでは、経路探索部１００に入力された出発地，目的地を経路探索のために取り込み設定する。
【００７３】
Ｓ１９０１：この処理ステップでは、ネットワーク地図ＤＢ１１１からＳ４００ｄｅ算出された経路探索エリアに含まれるノード群を読み込む。ノード群は図２０のテーブル２０００に示すデータ構造で表現される。「ノード番号」はノードを一意に決定する番号、「確定フラグ」はノードにいたる最小コスト経路が確定したか否かを表すフラグ、「コスト」はノードに到達するまでに要したコストで、最小料金コスト経路探索では料金コストにあたる。「直前ノード番号」は、このノード番号で表される現在のノードに至った経路を表し、「ノード到達時刻」はリンク旅行時間の積算で計算された現在のノードの到着時刻、「有料入口ノード」は現ノードに至るまでに通過した最も近くの入口のノードを表すノード番号、「有料入口からの距離」はその「有料入口ノード」からの積算距離、「有料入口通過時刻」は有料入口ノードの通過時刻を表す。Ｓ１９０１の処理時点では経路探索範囲の全てのノードに関してノード番号のみが読み込まれ、他の値は不定となる。
【００７４】
Ｓ１９０２：この処理ステップでは、ノード群中から出発地のノードを検出し、そのノードの「コスト」を０にセットする。「コスト」に値が定まることによってそのノードは候補ノードとなり、最小コストを求める対象ノードとなる。また、本処理では出発時刻をこの出発地のノードの「ノード到達時刻」として代入する。
【００７５】
Ｓ１９０３：この処理ステップでは、候補ノード２００１で表されるような候補ノード群の中からコストが最小なものを取り出す。取り出されたノードはダイクストラ法の原理により、最小コスト経路が確定したノードとなるので、確定ノード２００２のように「確定フラグ」を有効にし、確定ノードの１つとして次回からのコスト算出候補の対象外となる。
【００７６】
Ｓ１９０４：この処理ステップでは、Ｓ１９０３で確定ノードとしたノードが目的地ノードかどうか判定する。この確定ノードが目的地ノードであれば目的地までの最小コスト経路が確定したことになるので、Ｓ１９０９の処理に進み探索処理を終了する。確定ノードが目的地ノードでなければ、Ｓ１９０５に進む。
【００７７】
Ｓ１９０５：この処理ステップでは、確定ノードに接続するリンク群を取り出す。このうちリンクの終端ノードすなわち次のノードが確定ノードでないリンク群について、Ｓ１９０６からのループ処理の対象とする。
【００７８】
Ｓ１９０６：この処理ステップでは、Ｓ１９０５で取り出した接続リンク数分のループ処理を行う。
【００７９】
Ｓ１９０７：この処理ステップでは、リンク単位処理部１０６において料金コストの計算を行う。これは、リンクの料金コストを計算してリンク終端ノードまでのコストを算出する処理である。
【００８０】
Ｓ１９０８：この処理ステップでは、リンクの終端ノードを候補ノードとしてその「コスト」を更新する。既に計算されているリンク料金コストが存在する場合は、この処理ステップで計算したコストの方が小さい場合のみ更新を行う。直前ノード番号にはリンクの始端ノード、すなわち確定ノードのノード番号を、「ノード到達時刻」は、確定ノードの到着時刻にリンク旅行時間を加算した値を設定して更新する。また、同時に終端ノードが有料道路の入口ノードであれば、新たに「有料入口ノード」に終端ノードを設定し、終端ノードの到着時刻を「有料入口通過時刻」に設定し、「有料入口からの走行距離」も“０”にリセットする。終端ノードが有料道路の入口ノードでなければ、リンクの始端ノード、すなわち確定ノードのノードデータにある「有料入口ノード」，「有料入口通過時刻」の値をそれぞれコピーし、「有料入口からの走行距離」へはリンク長を加算した値を設定して入口からの距離を更新する。これにより、全ての候補ノードにおいて対応する有料道路入口，有料道路入口からの距離，有料道路入口の通過時刻がわかるため、料金ルールあるいは有料道路料金ＤＢによって有料道路料金が計算可能となる。
【００８１】
全ての接続リンク群に対してループ処理を行ったのち、処理は再びＳ１９０３に進む。
【００８２】
Ｓ１９０９：この処理ステップでは、目的地から「直前ノード」を逐次たどり、出発地までの確定ノード列を経路探索結果として出力する。
【００８３】
図６は、リンク単位処理部１０６における個々のリンクに対する処理の詳細を表したフローチャートである。複数料金コスト加算手段１０３における処理はＳ６０１，Ｓ６０９の処理に、リンク費用コスト算出手段１０７における処理はＳ６０２からＳ６０６の処理に、リンク時給換算コスト算出手段１０８における処理はＳ６０８の処理に該当する。
【００８４】
Ｓ６０１：この処理ステップでは、処理対象とするリンクの「コスト」に値が設定されていなければリンク料金コストを初期化して“０”を設定する。ここでリンク料金コストとは、リンク（経路探索時に用いるネットワークを構成する単位で、具体的には交差点間で表現される区間を表す）ごとの料金コストを表す。特に断らない限り以下の処理ステップでは、
リンク料金コスト＝リンク費用コスト＋リンク時給換算コスト＋リンク燃料費
… （式８）
であるとする。
【００８５】
Ｓ６０２からＳ６０６はリンク費用コストを算出する処理ステップである。
【００８６】
Ｓ６０２：この処理ステップでは、該当リンク内、またはリンクの終端に料金所があるか否かの判断を行い、その結果で分岐処理を行う。これは、リンク費用コストは料金の支払いが発生する箇所で料金を加算するためである。ＹＥＳの場合はＳ６０３に進み、ＮＯの場合はリンク費用コスト＝０としてＳ６０８に進む。
【００８７】
Ｓ６０３：この処理ステップでは、リンクの始端ノードのノードデータにおける「有料入口ノード」情報から入口インターに対応するノード番号を読み出す。つまり経路探索の出発地点が一般道路上である場合、経路探索の仮定で必ず有料道路の入口を通過するので、直近の入口インターを予め記憶させておいた確定ノード（リンク始端側ノード）のノードデータ２００２の有料道路入口ノードを利用する。出発地点が既に有料道路上である場合、直近の入口インターが存在しない場合がある。このとき実際に通過した入口インターが、例えばＥＴＣ車載機との連動やユーザの入力によって取得できる場合には、この入口インターの情報を有料道路入口の情報として読み込むものとする。あるいは、ネットワーク地図ＤＢ１１１から出発地点の直前にあたるインターチェンジを探し、これを入口インターとして代用することも可能である。
【００８８】
Ｓ６０４：この処理ステップでは、有料道路料金ＤＢ１０５から入口インターからこのリンクまでの区間の有料道路料金情報を取り出す。有料道路料金ＤＢ１０５は、図３に示すような距離・料金表３０１を電子データとして保持したものである。距離・料金表３０１は料金体系の異なる車種ごとに保持しておき、車両の種類に応じて取り出してもよい。距離・料金表３０１は入口インター群３０２と出口インター群３０３との組み合わせによって、料金が一意に定まる構造である。インター間の料金とともに距離が保持されていてもよい。
【００８９】
Ｓ６０５：この処理ステップでは、割引ルールが適用されるか否かによって分岐処理を行う。ＹＥＳの場合Ｓ６０６に進み、ＮＯの場合Ｓ６０７に進む。割引ルールが適用されるかどうかは、図２０に示した確定ノード２００２のノードデータに含まれる「有料入口からの走行距離」及び「有料入口通過時刻」、及び「ノード到達時刻」に現リンクのリンク旅行時間を加算した出口インターの通過時刻を読み出し、割引ルールの適合条件を満たすかどうかで判断する。例えば、入口インターの通過時刻，出口インターの通過時刻によって割引適用を判断する場合には、ノードの到着時刻，入口インターの通過予想時刻，出口インターの通過予想時刻のいずれか一つを用いて判断する必要があり、どの時刻も割引条件を満たさないような場合は割引ルールを適用しない。特定の機器の利用、例えばＥＴＣ車載機の有無により割引適用条件が変わる場合には、ＥＴＣ機器との接続有無、あるいはユーザの接続設定によって判断する。距離や区間によって割引適用条件が異なる場合は、その条件にしたがって割引の有無を判断する。割引ルールは有料道路料金ＤＢ１０５に格納されているものとする。
【００９０】
Ｓ６０６：この処理ステップでは、割引ルールを適用し、有料道路料金を変更する。例えば、割引ルール条件を満たせば半額といったルールが存在すれば、距離・料金表３０１から求めた有料道路料金を半額にセットする。あるいは、割引後の有料道路料金を距離・料金表３０１に保持しておくようにしてもよい。
【００９１】
Ｓ６０８：この処理ステップでは、リンク時給換算コストを計算する。これは次の式９で求まる。
【００９２】
リンク時給換算コスト＝時給換算単価Ｃ×リンク旅行時間 … （式９）
【００９３】
時給換算単価Ｃは、時給換算単価算出手段１０２で算出した結果を用いる。リンク旅行時間はネットワーク地図ＤＢ１１１の道路ネットワークデータに含まれる一定値の他、外部から取得したリアルタイム交通情報を考慮した値や図１０に示す時間帯別リンク速度ＤＢ７０７を更に設け、この時間帯別リンク速度ＤＢ７０７から読み込んだリンク速度データに基づき算出した値を使ってもよい。この時間帯別リンク速度ＤＢ７０７は、図１０に示すように、メッシュ番号（緯度経度によって地図上の領域を表現した番号）１００１でエリアごとに管理し、各メッシュに含まれるリンクについて、時間帯別リンク速度１００２に示すように平日，休日といった日種、および時間帯ごとに変化するリンクの統計的な速度データを保持している。この場合、時間帯別リンク速度ＤＢ７０７の速度データを用いた有料道路期待平均速度、及び一般道路期待平均速度が設定値記憶部１１０に設定され、有料道路対時間単価算出手段１０１は、これらの有料道路期待平均速度、及び一般道路期待平均速度を用いて有料道路料金の対時間単価を算出することになる。
【００９４】
Ｓ６０９：この処理ステップでは、式８に従い、既に求めたリンク費用コストとリンク時給換算コストにリンク燃料費を加算し、ノードデータの「コスト」に設定する。すなわちＳ６０９の時点で、リンク料金コスト＝リンク費用コスト＋リンク時給換算コスト＋リンク燃料費となる。リンク燃料費の計算にあたっては、一般に知られる方法を用いるものとする。例えば式６を用いれば、
リンク燃料消費量＝Ｆｃ×リンク旅行時間＋Ｃｆ×リンク長＋空気抵抗分＋高度変化 分＋速度変化分
リンク燃料費＝燃料単価×リンク燃料消費量
として計算できる。空気抵抗分は走行速度によって定まるので、リンク長やリンク旅行時間で算出できるリンク速度を用いればよい。高度変化分には地図ネットワークＤＢ１１１にリンク単位の高度データが含まれているか、あるいは推定に必要な値が含まれていれば算出可能となる。また、速度変化分については、走行速度から加速頻度を推定するなどすればよい。燃料単価は、設定値記憶部１１０に予め定めておいた設定値を利用するか、外部情報にアクセスして取得してもよい。
【００９５】
以上、図３から図６に記載された本発明の経路探索コスト決定方法を用いて、料金コスト利用経路探索手段１０４によって最小料金コストによる経路探索を実行することによって、図２及び図１４に示したエコノミールートを算出することができる。これによってユーザは時間と料金の両方を考慮した「お得」な経路を、煩雑な設定を伴わずに取得することが可能となる。また、システムは、有料道路優先，一般道路優先とも異なる経路探索コスト決定方法を用いているために、ユーザはどちらとも異なる経路を取得することが可能となる。
【００９６】
また時間帯別リンク速度ＤＢ７０７を用いることにより、料金と時間とを考慮した上で、時間帯ごとに異なるエコノミールートを求めることができる。
【実施例２】
【００９７】
図７は本発明を用いた経路探索装置における経路探索部の変形を示す図である。図１の構成に対して、外部から取得する料金ルールプロファイル７０６に従い料金算出ルールを更新する料金ルール更新手段７０５を追加している。この追加に伴い、有料道路料金の対距離単価についても料金ルールプロファイル７０６を用いて算出する。また、リンク費用コスト算出手段７１７は、料金ルールプロファイル７０６に基づき有料道路のリンク費用コストを算出する。図７の構成によって算出される最小料金コスト経路は、料金ルール更新手段７０５により、有料道路対時間単価算出手段１０１における有料道路料金の対時間単価，複数料金コスト加算手段１０３におけるリンク料金コストが変更可能となり、有料道路料金体系の変更や割引ルールの変更に対してもエコノミールートを提供することができる。以下、図７の処理の詳細について図８ないし図１０、及び図１５を用いて説明する。
【００９８】
図８は料金ルール更新手段７０５の処理をフローチャートで表したものである。以下処理ステップに従い説明する。
【００９９】
Ｓ８０１：この処理ステップでは、料金ルールプロファイル７０６を読み込む。料金ルールプロファイル７０６は、経路探索装置の外部から入手する情報であり、例えば通信によって内容を更新する。あるいはユーザ設定によって更新してもよい。料金ルールプロファイル７０６に格納されるデータの一例を図１５に示す。料金ルールプロファイルに格納されるデータはデータ１５００のような形式で表現し、料金パラメータの変更，料金算出ルールの変更内容，割引ルールの変更内容をデータとして記述した形をとる。１５０１，１５０２は料金パラメータ変更、１５０３は料金算出ルール変更、１５０４は割引ルール変更の例である。料金パラメータ変更１５０１では、対象エリアとして全国の自動車道、対象期間は指定なしとして、距離に対する料金単価、即ち有料道路の対距離単価αの設定を変更する例である。料金ルールの変更があった場合、有料道路対時間単価算出手段１０１，リンク費用コスト算出手段７１７にて変更されたルールの記述を適用する。例えば、１５０１の変更については、有料道路対時間単価算出手段１０１では、対象エリアの有料道路料金の対距離単価αとして料金パラメータ変更１５０１の“［料金単価］”に記述された値を使用する。また、リンク費用コスト算出手段７１７での利用方法に関しては図９の説明にて後述する。
【０１００】
料金パラメータ変更１５０２は、対象エリアとして特定の有料道路，対象期間を指定して距離に対する料金単価の設定を変更する例である。ここで挙げた料金パラメータ変更は料金単価の変更を記載しているが、個々のインター間の有料道路の距離・料金表のデータを記述してもよい。また、料金パラメータ変更として、距離逓減制が変更となる距離長，割引率などの変更を記述してもよい。ルールを適用する際には、“［対象エリア］”と“［対象期間］”の記述に基づき場所と時間の条件を変更し、また逓減制度が変更となる場合には、距離長に関してもその計算パラメータを変更して利用する。
【０１０１】
料金算出ルール変更１５０３は、対象エリアを指定して料金制度を一律料金制度から距離従量制へと変更するためのデータである。料金算出ルール変更としては、“［料金制度］”に小区間単位の料金徴収制を記載してもよい。割引ルール変更１５０４は、対象エリア，対象期間，対象時間帯，対象車両，対象条件，割引率など割引に関するルールの変更を記載した例である。割引ルールの変更に関してはリンク費用コスト算出手段７１７にてルールを適用する。詳細は図９の説明にて後述する。
【０１０２】
Ｓ８０２：この処理ステップでは、料金パラメータの更新を行う。料金パラメータの更新処理により、有料道路対時間単価算出手段１０１で用いる対距離単価αや距離逓減の割引率に使用される各種料金パラメータが変更となる。また、リンク費用コスト算出手段７１７にて、リンク費用コストを算出する際に料金パラメータが変更となる。
【０１０３】
Ｓ８０３：この処理ステップでは、料金ルールの更新を行う。料金ルール自体は、有料道路対時間単価算出手段１０１，リンク費用コスト算出手段７１７にて利用されるが、予め処理プロセスに搭載された料金ルールを料金ルールプロファイル７０６にしたがって変更する処理となる。
【０１０４】
Ｓ８０４：この処理ステップでは、割引ルールの更新を行う。有料道路対時間単価算出手段１０１，リンク費用コスト算出手段７１７にて利用される割引ルールのパラメータ変更と割引ルール自体を変更する。割引ルールの変更も料金ルールの更新と同様、予め処理プロセスに搭載された割引ルールを料金ルールプロファイル７０６にしたがって変更する処理となる。
【０１０５】
図９は、リンク費用コスト算出手段７１７を含むリンク単位処理部７１６における処理のフローチャートを示したものである。
【０１０６】
本処理では有料道路料金ＤＢが存在しない場合でも、料金ルールによってのみ有料道路区間の料金を計算する方法について示した例である。料金コスト利用経路探索手段１０４の経路探索自体は、前述の実施例１と同様であるため、全ての候補ノードにおいて対応する有料道路入口，距離，通過時刻がわかり、料金ルールによって有料道路料金が計算可能となる。以下処理ステップに従い説明する。
【０１０７】
Ｓ９０１：図６のＳ６０１と同じ。
【０１０８】
Ｓ９０２：この処理ステップも、図６のＳ６０２と同様の分岐処理を行う。ＹＥＳの場合Ｓ９０３に進み、ＮＯの場合Ｓ９０８に進む。
【０１０９】
Ｓ９０３：図６のＳ６０３と同じ。
【０１１０】
Ｓ９０４：この処理ステップでは、料金ルールに基づき入口インターからこのリンクまでの区間の有料道路料金を算出する。図６のＳ６０４では有料道路料金ＤＢから予め計算された料金データを抽出したが、ここでは料金ルールに基づき有料道路料金を算出する。例えば、入口インターからの距離が距離逓減ルールの適用範囲であれば、その距離逓減ルールによって該当区間の対距離単価を算出し、対象リンクのリンク長合計に距離逓減ルールに基づく対距離単価を乗じて距離逓減ルール該当区間の有料道路料金が計算できる。また、リンク費用コスト計算の際には、入口，出口間の対距離単価によるリンク費用コストに対して、基本料金に相当する金額を有料道路料金に加えることで、予め計算された有料道路料金ＤＢの距離・料金表３０１と同じ値になるようにする。
【０１１１】
Ｓ９０５：図６のＳ６０５と同じ。
【０１１２】
Ｓ９０６：この処理ステップでは、割引ルールを適用する。割引ルールが複数存在し、適用区間が異なるような場合は、入口インターから該当する出口インターまでの区間を構成する有料道路の各リンクについて、最も値が小さくなる割引ルールを適用してリンク単位の有料道路料金を計算していき、割引ルールが変更となる地点、あるいは時間を通過した時点でそのリンクに累積で利いた割引分を元に戻す処理を行う。例えば、
割引ルール１：０：００−４：００をまたいで走行した場合、全区間４割引
割引ルール２：２２：００−６：００に入口、または出口を通過し、走行距離が１００km以内ならば、区間内５割引
といった二つの割引ルールが存在する場合は、割引率の高い割引ルール２を適用し、確定ノードのノードデータに含まれる有料道路入口インターから１００km以内の有料道路区間の料金は５割引で算出する。１００kmを超えた時点で割引ルール１適用となるが、その差額である過去１００km内の累積料金差を有料道路料金に加算する。さらに候補ノードが有料道路の出口インターに該当する出口ノードにおいて、割引ルール１の時間帯を満たさないことが判明した場合、割引なし時と割引ルール１適用時の有料道路区間分の累積料金差を有料道路料金に加算する。
【０１１３】
Ｓ９０７：この処理ステップでは、リンク速度を時間帯別リンク速度ＤＢ７０７から読み出す。または外部から取得したリアルタイム交通情報からリンク速度データを取得する。そして、リンク長と確定ノードの到着時刻に対応する時間帯のリンク速度からリンク旅行時間を計算する。また、リアルタイム交通情報からリンク旅行時間が入手可能な場合には、その値を利用する。
【０１１４】
Ｓ９０８：図６のＳ６０８と同じ。Ｓ９０７で読み込んだリンク旅行時間を用いる。
【０１１５】
Ｓ９０９：図６のＳ６０９と同じ。なお、燃料費の算出に旅行時間，速度が必要な場合にはＳ９０７で求めたリンク旅行時間を利用する。
【０１１６】
以上に示した経路探索コスト決定方法により、料金コスト利用経路探索手段１０４によって最小料金コストによる経路探索を実行して、時間帯や交通状況によって変化する図２及び図１４に示したエコノミールートを算出することができる。そして料金ルール更新手段を備えることにより、料金ルールの変更に際してもユーザはエコノミールートにより「お得」な経路を享受することができる。
【実施例３】
【０１１７】
図１１は本発明を用いたナビゲーション装置の全体構成を表した図である。図１１では自動車に装備したナビゲーション装置を記載しているが、携帯電話に搭載されたソフトウェアとしてもよい。また、ＧＰＳ受信機１１０７による位置検出手段の代わりに、出発地を入力する手段を備えていれば、通常のパソコン上で動作するソフトウェアとしてもよい。以下図１１に従いナビゲーション装置について説明する。
【０１１８】
１１０３はスピーカ、１１０４はナビゲーション装置、１１０５は表示ディスプレイ、１１０８はナビゲーション装置を搭載した車両である。また、１００，１１３，１１１０，１１１２はナビゲーション装置１１０４内部の図示されていないＣＰＵで動作するソフトウェアを示す。
【０１１９】
交通情報受信部１１１０は、交通情報受信器１１０６にて受信したリアルタイム交通情報を経路探索部１００で使える形でデータを解釈し、渡す処理を担う。
【０１２０】
経路探索部１００は、実施例１又は実施例２で説明したようにエコノミールート探索及び従来の有料優先，一般優先の経路探索処理を担う。
【０１２１】
比較提示部１１１２は、経路探索部１００から出力されるエコノミールートの経路探索結果を受け取り、画面表示または音声による経路案内を行う処理を担う。
【０１２２】
設定入力部１１３は、前述のようにユーザに設定変更画面を提示し、設定入力のためのインターフェースを備えて設定を保存し、各種変更を行う。
【０１２３】
図１１の例は、経路探索コスト決定方法をナビゲーション装置内部で行う構成であるが、ナビゲーション装置の外部に経路探索コスト決定を行うセンターを設置し、そこから通信によって求めたリンク料金コストをナビゲーション装置に取得するようにしてもよい。
【０１２４】
図１２は、比較提示部１１１２の画面案内と、経路探索時の画面遷移について示したものである。画面遷移は、図示されていない目的地設定画面で目的地を設定後、地図表示画面１２０１に遷移し自車位置マーク１２０５とともに目的地マーク１２０６を地図表示１２０４上に表示する。ここで、複数経路探索ボタン１２０３の押し下げにより経路探索中の状態に遷移し、経路探索終了後、比較表示画面１２０２に遷移する。そして比較表示画面１２０２にて選択した経路に基づいて経路誘導開始となる。図中１２０７ないし１２０９は、各種探索条件ごとに探索結果経路の距離，所要時間，全料金（有料道路料金＋燃料費）と有料道路料金を表したものであり、１２０７は有料優先ルート、１２０８はエコノミールート、１２０９は一般優先ルートを表す。１２１０ないし１２１２は地図上に示した各種探索条件による探索結果経路であり、１２１０は有料優先ルート、１２１１はエコノミールート、１２１２は一般優先ルートを表す。また、１２１３は有料道路入口インター、１２１４は有料優先経路における出口インター、１２１５はエコノミールートにおける出口インターを示す。本発明による経路探索コスト決定方法を用いることによって、１２０８に示す例にあるように有料優先，一般優先とも異なるエコノミールートが出力され得る。すなわち、有料優先の有料道路利用料金よりは料金が安いが時間はかかるようなエコノミールートが得られる。
【０１２５】
図１２のような比較提示により、ユーザはエコノミールートの従来ルートとの違いを定量的に理解することができる。また、表示だけでなく音声によって表現し、「エコノミールートは有料優先ルートに比べて２０分余計にかかりますが、料金は２２００円得します。」といった差を表現するような提示をしてもよい。
【実施例４】
【０１２６】
図２１は本発明による経路探索機能を備えたセンターと通信によって接続し、経路探索結果を取得するナビゲーション装置と周辺システムを表した図である。以下図１１に示した実施例３との相違点を中心に説明する。
【０１２７】
２１０４はナビゲーション装置、２１０６はセンターと接続するための通信装置である。また、１１３，１１１２，２１０７，２１０８はナビゲーション装置２１０４内部のソフトウェアを示す。２１１２は本発明による経路探索機能を備えたセンターであり、２１０９はナビゲーションからの通信を受信し応答する通信応答部、２１１０は交通情報センター１１０１と接続してリアルタイム交通情報を取得する交通情報受信部、２１１１は通信応答部２１０９によって受信したナビゲーション装置２１０４からの経路探索要求に対して交通情報受信部２１１０で取得したリアルタイム交通情報，時間帯別リンク速度ＤＢ７０７，有料道路料金ＤＢ１０５を用いて料金コストによる経路探索を行う、図１１の経路探索部１００に対応した経路探索部である。
【０１２８】
設定入力部１１３は、実施例３と同様、ユーザに設定変更画面を提示し、設定入力のためのインターフェースを備えて設定を保存し、各種変更を行う。
【０１２９】
出発・目的地設定部２１０７は、経路探索における出発地と目的地を設定する。出発地はＧＰＳ受信機１１０７によって取得した現在位置を用い、目的地はユーザの指定によって決定する。
【０１３０】
通信処理部２１０８は、センターへの料金コスト利用経路探索の要求とともに設定入力部１１３によって決定したリンク時給換算コスト算出に必要となる有料道路の期待平均速度及び一般道路の期待平均速度、あるいは時給換算単価を設定値としてセンターに送信する。また、経路探索のために必要な出発地，目的地の情報をセンターに送信する。出発地，目的地は緯度経度などの形式で送信する。センター側では経路探索部２１１１にて、通信応答部２１０９で受信したナビゲーション装置２１０４からの出発地，目的地，設定値に従い、図１１の経路探索部１００と同様に料金コスト利用経路探索を行い、経路探索結果をエコノミールートとして出力する。受信した設定値が、有料道路期待平均速度、及び一般道路期待平均速度の場合は有料道路対時間単価算出手段１０１の入力として利用する。受信した設定が、時給換算単価であった場合は、有料道路対時間単価算出手段１０１及び時給換算単価算出手段１０２の処理は行わず、与えられた時給換算単価を用いてリンク時給換算コストを算出する。また経路探索部２１１１は、エコノミールートの探索結果との比較のための経路探索も行う。比較経路としては、交通情報利用時の最短時間経路探索結果などを含めてもよい。
【０１３１】
通信処理部２１０８は、センター側から料金コストを利用したエコノミールートの経路探索結果、及び比較のための経路探索結果を受信する。経路探索結果は経路の所要時間，距離，料金，有料道路料金，燃料費を含める他、経路の形状がわかるフォーマット、例えば緯度経度列を含める。
【０１３２】
比較提示部１１１２は、実施例３と同様、エコノミールートの探索結果を画面表示、または音声による案内を行う処理を担う。
【０１３３】
図２１の構成によって、センター側で有料道路料金ＤＢを備えて料金コスト利用経路探索を行うことにより、最新の料金データや割引ルールを容易に反映することができる。
【産業上の利用可能性】
【０１３４】
本発明は、経路探索方法に関するものであり、主にソフトウェアの一部として利用されるものである。また、ナビゲーション装置としての利用も可能であり、経路探索による経路誘導機能として利用できる。
【符号の説明】
【０１３５】
１００ 経路探索部
１０１ 有料道路対時間単価算出手段
１０２ 時給換算単価算出手段
１０３ 複数料金コスト加算手段
７０５ 料金ルール更新手段
１０００ 時間帯別リンク速度ＤＢ
１１０４ ナビゲーション装置
【技術分野】
【０００１】
本発明は、ナビゲーションシステムに係り、特に車載端末を用いて車両の経路探索を行うシステムに関する。
【背景技術】
【０００２】
ナビゲーション装置において、複数の探索条件を用いて経路探索をするものが広く知られており、特に有料道路料金や燃料費などの料金を考慮し、この料金を道路リンク（道路ネットワークを構成する区間を表す）の経路探索コスト（リンクを通過するのに必要とする数値であり、距離，時間，料金などが用いられ、その合計が最適解算出時の評価値となる）として用いて経路探索する方法が存在している。
【０００３】
このとき、料金を単純に最小化するような経路を算出すると有料道路を単純に回避するような経路が算出され、費用対効果の面から必ずしもユーザにとって望ましい経路になるとは限らない。これに対して、特開２００８−８２８８４号公報では、一般道路優先で探索した経路の走行時間及び有料道路料金の合計と、有料道路優先で探索した経路の走行時間及び有料道路料金の合計とから、有料道路利用時の短縮時間とその有料道路料金を短縮時間で割った単位時間当たりの料金を算出し、単位時間当たりの料金が予め設定しておいた単位時間当たりの料金の閾値を超えているか否かを判別して、単位時間当たりの料金がこの閾値より大きい場合は一般道路優先経路を表示し、小さい場合は有料道路優先経路を表示するナビゲーション装置を開示している。このように有料道路利用における対費用効果の良し悪しを判断する目安として予め閾値を設定させておくことで、費用対効果の面でユーザに望ましい経路が提示できるとしている。
【０００４】
また、走行に直接必要なコストとして燃料費があるが、この燃料費の計算式としては、大口らの燃料消費量モデルが知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−８２８８４号公報
【非特許文献】
【０００６】
【非特許文献１】大口 敬ほか：「都市部道路交通における自動車の二酸化炭素排出量モデル」、土木学会論文集、Ｎo.６９５／ＩＶ−５４ pp.１２５−１３６（２００２）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、ユーザにとって単位時間当たりの料金を設定することは煩雑であり、設定した値自体が適切か否かを走行前に判断することも困難である。例えば、遠隔地に行きたいときに有料道路を使う、といったケースにおいてユーザが単位時間当たりの料金閾値を適切に設定することは困難である。特開２００８−８２８８４号公報では過去の指定経路に基づきこの閾値を更新する方法を提示しているが、初期段階で適切な経路を選択できなければ、次回以降も適切な閾値を設定することは困難である。
【０００８】
また、閾値を用いて有料優先経路と一般優先経路を比較する場合に、既存のコスト計算方法によって算出したルートの評価をするのみであって、新しいコスト計算方法に基づいて経路探索をするわけではない。すなわち、有料優先経路，一般優先経路とも異なる別のルートを経路探索結果として提示することが困難である。
【０００９】
本発明はユーザによる適切な料金閾値設定の困難さと、有料優先経路，一般優先経路とも異なる費用対効果の面で望ましい経路探索結果を提示する課題を解決する経路探索方法、及びナビゲーション装置を提供するものである。
【課題を解決するための手段】
【００１０】
本発明では、有料道路の期待平均速度と一般道路の期待平均速度と有料道路料金対距離単価から有料道路利用時の有料道路料金対時間単価を算出し、有料道路対時間単価に対し所要時間に応じた時給として定まる料金単価として時給換算単価を算出し、料金算出ルールまたは有料道路料金ＤＢの少なくとも一方に基づき有料道路のリンク費用コストを算出し、リンク旅行時間と時給換算単価からリンク時給換算コストを計算し、少なくともリンク費用コストと時給換算コストとを加算したトータルのリンク料金コストを算出し、これを用いた経路探索を行う経路探索方法を提供する。
【００１１】
また、本発明では、外部からの情報により料金算出ルールを更新する料金ルールを更新し、更新された料金算出ルールに基づき有料道路のリンク費用コストを算出し、リアルタイム交通情報またはリンク速度データベースの少なくとも一方に基づきリンク旅行時間を算出し、リンク旅行時間と時給換算単価からリンク時給換算コストを計算し、リンク費用コストとリンク時給換算コストとリンクあたりの燃料費を加算したリンク料金コストを算出し、経路探索を行う経路探索方法を提供する。
【００１２】
さらに、本発明では、前記経路探索方法を用いて算出したリンク料金コストを利用して経路探索処理を行う経路探索手段を備えるナビゲーション装置を提供する。
【発明の効果】
【００１３】
ユーザに煩雑な設定を強いることなく、有料道路を走行することで一般道路走行に対して発生する料金と、有料道路，一般道路それぞれの期待平均速度から算出する期待短縮時間とから算出できる時給換算単価（所要時間に対して仮想的に発生する料金）を算出し、リンク旅行時間と時給換算単価から算出される一般道路と有料道路の時給換算コストの差に対して有料道路利用料金が安い場合を「お得」と定義し、「お得」な場合には有料道路を、「お得」でない場合には一般道路を区間ごとに利用する経路を提供する経路探索方法、及びナビゲーション装置が実現できる。また有料道路料金の料金体系が途中で変化し、割引率の高い区間の高速料金が「お得」であるが割引率の低い区間の高速料金が「お得」でない場合には、割引率の高い「お得」な区間のみ利用するような経路探索結果を提示することが可能となる。また、有料道路と一般道路とを組み合わせた経路を提示し、「お得」な区間を明示するナビゲーション装置を実現することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明を用いた経路探索部の構成図である。
【図２】本発明における経路探索コスト決定方法の原理説明図である。
【図３】距離・集金表の例を示す図である。
【図４】有料道路の対時間単価算出処理のフローチャートである。
【図５】時給換算単価算出処理のフローチャートである。
【図６】リンク料金コスト算出処理のフローチャートである。
【図７】本発明を用いた経路探索部の変形の構成図である。
【図８】料金ルール更新処理のフローチャートである。
【図９】リンク料金コスト算出処理のフローチャートである。
【図１０】時間帯別リンク速度ＤＢの例を示す図である。
【図１１】本発明を用いたナビゲーション装置の図である。
【図１２】経路探索時の画面遷移図である。
【図１３】設定変更画面である。
【図１４】料金割引があったときの経路探索コスト決定方法の原理説明図である。
【図１５】料金ルールプロファイルの例を示す図である。
【図１６】有料道路の対距離単価の算出処理のフローチャートである。
【図１７】有料道路の対時間単価の算出処理のフローチャートである。
【図１８】リンク料金コスト計算の例を示す図である。
【図１９】経路探索処理のフローチャートである。
【図２０】経路探索で用いるノード群を構成するノードデータのデータ構造を示す図である。
【図２１】本発明を用いたセンターに通信によって接続するナビゲーション装置と周辺システムを表す図である。
【発明を実施するための形態】
【００１５】
本発明による経路探索方法、及びナビゲーション装置の実施の形態を、図面を参照して説明する。
【実施例１】
【００１６】
図１は本発明を用いた経路探索装置における経路探索部１００の構成を示す図である。経路探索部１００では、出発地，目的地の入力を受け付けて、本発明による経路探索コスト決定方法を用いた経路探索結果を出力する。料金コスト利用経路探索手段１０４は、出発地と目的地の入力に対してネットワーク地図ＤＢ１１１（経路探索に用いるノードとリンクの接続関係，リンクの属性情報が含まれる）を用いて、所要時間の増加に伴い発生する仮想的な時給換算料金も経路探索のコストに反映されるように考慮した経路探索結果を求める手段である。
【００１７】
有料道路対時間単価算出手段１０１は、設定値記憶部１１０に格納されている、有料道路の走行に予想される平均速度，一般道路の走行に予想される平均速度、および有料道路料金の対距離単価から、有料道路の利用可否判断を行う際に用いる有料道路利用時の時間に対する料金単価を算出する。
【００１８】
ここで道路の走行に予想される平均速度のことを期待平均速度と呼ぶことにする。期待平均速度は、後に説明する設定入力部１１３による設定画面を介してユーザが指定した設定値，制限速度などの規制速度，走行実績、あるいは過去の交通情報から算出した、地域または道路ごとに異なる速度のいずれかを与える。期待平均速度は、実際の経路を探索する前に、全体の走行予定距離の概算に対して所要時間を見積もる際に用いるため、個々の道路リンクを参照しなくても済むように、ある程度一律の値として定めておいてもよい。例えば、一番粗く定める場合には有料道路と一般道路に分けて定め、細かく定める場合には、地図のメッシュ単位あるいは各地図メッシュにおける有料道路と一般道路ごとに定めればよい。期待平均速度として走行実績を用いる場合には、過去に有料道路や一般道路を走行したときのそれぞれの平均速度を用いる。この場合でも、細かく分類する場合には、地図のメッシュ単位（地図メッシュごとの道路リンクの平均速度）を用いる。本実施例では、道路を有料道路と一般道路に分けて、有料道路の走行に予想される平均速度（有料道路期待平均速度）と一般道路の走行に予想される平均速度（一般道路期待平均速度）を設定値記憶部１１０に記憶しておくものとする。
【００１９】
有料道路料金の対距離単価は、有料道路の走行距離に対応した利用料金を計算するための距離に対する料金単価である。この値としては、有料道路によって定められた料金ルールを用いるか、有料道路料金ＤＢ１０５に格納されている各有料道路の料金表情報に基づき、地域ごと、あるいは道路ごとに料金所間の料金から予め算出しておいてもよい。料金ルールとして距離逓減（距離に応じて料金単価が減少する）ルールがあるような場合は、距離逓減ルールを適用しない通常の対距離単価及び距離逓減が発生する閾値距離と逓減時の料金単価を対距離単価として持つようにする。
【００２０】
有料道路期待平均速度，一般道路期待平均速度，有料道路料金の対距離単価は、経路探索前に予め設定しておく値であり、本実施例では、これらの値はハードディスク装置や不揮発性メモリなどの書き換え可能な記憶媒体により構成される設定値記憶部１１０に格納されているものとする。
【００２１】
時給換算単価算出手段１０２は、有料道路対時間単価算出手段１０１で算出した有料道路料金の対時間単価を用いて、有料道路を走行した場合に比べて一般道路を走行した場合の所要時間の増加分を、走行に要した時間増加分に対する時給として仮想的な料金に換算するための、時間当たりの料金単価（以下では時給換算単価とする）を算出する。
【００２２】
リンク単位処理部１０６は、経路探索処理においてリンク単位の処理を行う所である。ここでは一般的な経路探索処理としてダイクストラ法などの最小コスト求解方法が利用され、入力された出発地−目的地間のリンクごとにリンク料金コストを加算していき、その合計が最小となるリンク列が探索結果として算出される。そして加算するリンク料金コストは、リンク費用コスト算出手段１０７，リンク時給換算コスト算出手段１０８，複数料金コスト加算手段１０３により計算される。
【００２３】
リンク費用コスト算出手段１０７は、有料道路料金ＤＢ１０５に格納されている割引率などの情報を含んだ有料道路の料金算出ルールに基づき、リンクごとの有料道路料金に相当するリンク費用コストを算出する。リンク時給換算コスト算出手段１０８は、リンク旅行時間と時給換算単価算出手段１０２で求めた時給換算単価からリンク時給換算コストを計算する。リンク旅行時間は、ネットワーク地図ＤＢに含まれる個々のリンクの所要時間コスト、又は車速の概算値として期待平均速度を用いリンク長から求めたリンクの所要時間、あるいは後述するように外部から配信された交通情報を用いてもよい。複数料金コスト加算手段１０３は、リンク費用コスト算出手段１０７で求めたリンク費用コストと、リンク時給換算コスト算出手段１０８で求めた当該リンクにおけるリンク時給換算コストと、車両走行のために消費する燃料費の３つの料金コストを合計してリンク料金コストを算出する。
【００２４】
探索結果出力手段１０９は、リンク料金コストを用いた経路探索によって求まる最小コスト経路のリンク列を経路探索結果として出力する。
【００２５】
図１の構成によって算出される最小料金コスト経路は、前述の時給換算単価に基づく実際には費用が発生しない仮想的な時給換算コストの概念を用いているため、算出された経路の実際の料金コストである有料道路料金と燃料費の合計値の最小解ではないが、走行に要した時間を金銭に換算して含めた最小解となる。よって料金と時間とを考慮した上でユーザに「お得」感のある経路（以下ではエコノミールートと表現）となる。
【００２６】
まず図１の構成によりエコノミールートを算出する処理の概略について図２及び図１４を用いて説明し、次に各処理の詳細については図３ないし図６を用いて説明する。
【００２７】
図２（ｂ）はある出発地から目的地までの全ての経路の時間に対する有料道路料金，時給換算コスト及び燃料費の変化を示したものである。図２（ｂ）において、縦軸は料金、横軸は出発地から目的地到着に要する走行時間（出発地から目的地までの所要時間に対応しており、信号停止など交通全体に及ぼす時間は含むが、休憩時間は含まない）、をとっている。図２及び図１４の説明では簡単のため、出発地から目的地までは図２（ａ）に示すように有料道路，一般道路は完全に並行し、乗降りは有料道路上の任意の地点で自由に行えるものと仮定したときの経路について考える。この図２（ｂ）の有料道路料金のグラフで最速となるのは全線有料道路を利用した場合に相当し、一般道最速は一般道のみの最適経路を全線利用した場合に相当する。なお、一般道最速の状態よりも走行時間が大きくなる状態は、一般道路を利用した遠回りとなる区間を走行する場合に相当する。
【００２８】
チャート２０１は有料道路料金，時給換算コスト及び燃料費それぞれの料金コストを個別に表現したものであり、ライン２０３は有料道路料金の時間に対する変化、ライン２０４は燃料費の時間に対する変化、ライン２０５は時給換算コストの累計値を表している。チャート２０１において、有料道路料金，燃料費及び時給換算コストの各料金コストを表すライン２０３，２０４，２０５で、料金が最小となっている箇所が各料金コストをそれぞれ個別で用いたときの最小料金コストとなり、最小空間を探索する方法によって料金を最小にする解が求まる。言い換えれば、チャート２０１で現した特性空間での最小料金の解は、実際の経路探索において用いられる最小コスト解探索アルゴリズムであるダイクストラ法などを用いることによって最小料金コスト経路として求めることができる。
【００２９】
次に、それぞれの料金コストについてチャート２０１上での特徴を説明する。有料道路料金２０３は、有料道路と一般道路利用区間の区間長に応じて定まる料金コストである。通常のケースでは有料道路利用区間が長ければ長いほど高速走行が可能となり走行時間が短縮できるため、チャート２０１上では負の傾きをもって現すことができる。その傾きの大きさは以下のように概算できる。出発地から目的地までの道のり距離（道路上を走行したときの距離）をＤとし、このとき有料道路の利用区間をＤ１、一般道路の利用区間をＤ２とする。このとき、図２（ａ）のように有料道路と一般道路は完全に並行するものと仮定していることから、
Ｄ＝Ｄ１＋Ｄ２ … （式１）
と置くことができる。ここで有料道路の走行速度はＶ１一定、一般道路の走行速度はＶ２一定であると仮定すると、その所要時間Ｔは以下の式で計算できる。
【００３０】
Ｔ＝Ｄ１／Ｖ１＋Ｄ２÷Ｖ２ … （式２）
【００３１】
式１，式２を変形し、有料道路の利用区間Ｄ１について解くと以下の式となる。
【００３２】
Ｄ１＝Ｖ１×Ｖ２÷（Ｖ１−Ｖ２）×（Ｄ÷Ｖ２−Ｔ） … （式３）
【００３３】
このとき有料道路料金は、実際には距離逓減制度などにより単純比例で距離に応じて料金が下がるとは限らないが、距離が長くなれば料金が増加する傾向は近似できる。そこで、有料道路の利用距離に対する単価で単純に現した場合、この有料道路の対距離単価をαとすると、有料道路料金の変化分はα＊Ｄ１で表現される。よって所要時間Ｔに対する料金の傾きＣｔは式３を利用して以下となる。
【００３４】
Ｃｔ＝−α×Ｖ１×Ｖ２÷（Ｖ１−Ｖ２） … （式４）
【００３５】
通常有料道路の走行速度Ｖ１＞一般道路の走行速度Ｖ２であるので、走行時間に対する料金の傾きＣｔは負となる。例としてＶ１＝９０［km／時］，Ｖ２＝３０［km／時］，α＝３０［円／km］（＝日本の高速道路料金の概算値）とすると、Ｃｔ＝−１３５０［円／時］となる。
【００３６】
式３の両辺にαを乗ずることによってチャート２０１の有料道路料金２０３は式４を用いて
有料道路料金の変化分＝α×Ｄ１＝Ｃｔ×Ｔ＋α×Ｖ１÷（Ｖ１−Ｖ２）×Ｄ
… （式５）
として表され、有料道路料金は走行時間Ｔに対して負の傾きをもつ一次関数として近似できる。図２（ａ）で示した仮定により、時間が最も小さい（＝最速）なのは全て有料道路を利用したときとなり、全て一般道を利用して目的地まで有料道路に並行して向かったとき（＝一般道最速）には、Ｄ１＝０となり、有料道路料金＝０となる。この仮定では有料道路に並行する以外の一般道路は存在しないが、実際には一般道路で遠回りする経路が考えられる。このとき、一般道路の速度はＶ２を一定と仮定していることから、遠回り経路は、一般道最速よりも走行時間が大きい走行時間の領域となる。このときの有料道路料金は０となる。
【００３７】
一方、燃料費２０４の時間に対する料金変化を考える。燃料費の計算式としては、大口らの燃料消費量モデルを用いると以下の式で表すことができる。
【００３８】
燃料消費量＝Ｆｃ×Ｔ＋Ｃｆ×Ｄ＋空気抵抗分＋高度変化分＋速度変化分
… （式６）
【００３９】
式６において、Ｆｃは時間当たりの燃料消費量、Ｃｆは摩擦などによる距離当たりの燃料消費係数を表す。式６で第一項は走行時間に比例する項、第二項は走行距離に比例する項、第三項は空気抵抗分、第四項は高度変化分、第五項は加減速に伴う速度変化分を表す。チャート２０１では燃料消費量の走行時間に対する関数として表しているので、式６の各項の特徴を述べる。第一項は走行時間に比例する項、第二項は図２（ａ）で示した仮定により距離は一定なので走行時間に対しては定数である。第三項は高速走行と一般走行とで差があるが、燃料消費量全体からみると空気抵抗の占める割合は小さい。第四項は高度差の項であるが、図２（ａ）のような仮定では出発地，目的地が同じく並行道路であることから走行時間からみると一定値、第五項は一定速度の仮定によりゼロとなる。すなわち走行時間に対する影響としては、第一項と第三項を考えればよい。また第三項の空気抵抗分は第一項に対して影響が小さいので、第一項のみ考慮すればよいが、第一項は走行時間に対して正の傾きをもつものの、有料道路利用に対する傾きに対して小さいと予想され、チャート２０１に示す程度となる。
【００４０】
例として、時間当たりの燃料消費量が０.５［cc／秒］であり、燃料単価を１５０［円／１,０００cc］とすると時間に対する変化量は、２７０［円／時］となる。よって有料道路料金のライン２０３と燃料費のライン２０４のみを加算した料金コストをチャート２０１上で考えても、有料道路料金のライン２０３の負の傾きが大きく、有料道路を利用しない一般道路優先が料金コスト最小解となる可能性が強くなる。また一般道路で最速となる走行時間よりも走行時間が長くなる場合は、前述のように一般道路を遠回りする経路にあたり、有料道路料金は０で一定、燃料費は単純増加となり合計の料金コストも時間に対して単純増加することになる。
【００４１】
本発明では、料金と時間とを考慮した上で「お得」感のある経路を求めるため、時給換算コストのライン２０５の概念を加えることにより、料金優先／時間優先以外に料金と時間をともに考慮した経路を求めることが可能となる。そして、時給換算コストのライン２０５の傾きが、想定した有料道路料金コストのライン２０３の傾きを相殺する傾きであれば、即ち時給換算コストのライン２０５の傾きＣを前述の有料道路料金のライン２０３の傾きＣｔを相殺するようにＣ＝−Ｃｔとすれば、ライン２０６に示した有料道路＋燃料費＋時給換算コストの概形のように、走行時間に対して料金が大きく変化しないような解空間を作成することができる。実際には式１や式２の仮定と異なり、有料道路料金の地域性や、有料道路利用時と一般道路利用時の距離は有料道路の利用出入り口によって変化すること、また走行速度の傾向が地域や交通状況によって変化する異などから、実際の有料道路料金，時給換算コスト及び燃料費の合計はライン２０７のように変化することが予想され、この料金変動の中でもっともエコノミーな解、即ち最小料金コストの解が求まることとなる。
【００４２】
図１４は、有料道路の料金割引制度が存在する場合の有料道路料金と、時給換算コスト及び燃料費の変化を示したものである。簡単のため図２（ａ）に示すように、出発地から目的地までは、有料道路，一般道路は完全に並行しており、有料道路への乗り降りは自由であるとしたときの経路について考える。チャート１４０１はそれぞれの料金コストを個別に表現したものであり、ライン１４０３は有料道路料金の走行時間に対する変化、ライン２０４は燃料費の走行時間に対する変化、ライン２０５は時給換算コストの走行時間の増加に伴う累計値を表し、縦軸に料金、横軸に走行時間をとっている。なお、ライン２０４，２０５に関しては、図２（ｂ）と同一である。有料道路の料金割引制度が、ある一定距離までは半額、それ以降（以遠）は通常料金といった離散的な料金体系（例としては、日本のＥＴＣ割引制度）となっている場合、料金割引が適用される距離の範囲内で有料道路を利用したとき、ライン１４０３のように割引範囲内を走行した時間に対して急激に料金が変化することとなる。ライン２０５のような料金割引が無い場合の有料道路利用料金の変化を相殺するような時給換算コストを適用することで、点線で示したライン２０３の通常の有料道路料金とライン１４０３に示す割引後の料金の差の分が、料金割引が適用された場合のコスト合計値を表すライン１４０４と料金割引が無い場合のコスト合計値を表すライン２０６の差となり、有料道路料金＋燃料費＋時給換算コストの概形１４０４はチャート１４０２に示すように料金が変化した点を最小解とするような特性を示しうる。すなわち、このことは料金割引区間において有料道路を利用し、その他の区間は一般道路を通るといったエコノミールートが算出しうることを示すものである。
【００４３】
以上で示した考え方に基づき、有料道路の利用時間に対する料金の変動を相殺するような時給換算コストを算出して利用する方法を、図３ないし図６を用いて説明する。
【００４４】
図４は、有料道路対時間単価算出手段１０１の処理を示したフローチャートである。フローチャートにおける各処理ステップ（ステップは図中ＳＸＸＸとして記載する）の内容は以下のようになる。
【００４５】
Ｓ４００：この処理ステップでは、経路探索エリアを算出する。経路探索エリアは、料金コスト利用経路探索手段１０４に予め入力された出発地と目的地を含むように決定し、例えば出発地，目的地を頂点とする長方形領域に出発地，目的地のお互いに離れる方向の後方エリアを含むような領域としてもよい。そして、探索対象となる地域のエリアのコードを出力し、後述する処理において地域の特定に利用する。
【００４６】
Ｓ４０１：この処理ステップでは、有料道路，一般道路それぞれの期待平均速度を設定値記憶部１１０から読み込む。各期待平均速度は前述のようにして予め定められ、例えば所要時間計算時に用いるために予めシステムが定める速度を用いてもよい。システムが定める速度として、規制速度を用いる場合、それぞれの道路の規制速度に対して一定割合を掛けた（たとえば８割）速度でもよい。
【００４７】
Ｓ４０２：この処理ステップでは、実際の経路探索の前に予め有料道路料金の概算値を求めておくための準備として、有料道路の予想走行距離を算出する。ここでは例えば、出発地と目的地の直線距離（経路探索前）、あるいはその一定倍率の距離、または出発地と目的地の緯度経度差を単純に加算した距離などにより、全体の走行予定距離を算出する。さらにネットワーク地図ＤＢで地図情報を矩形領域ごとに管理しておき、経路探索エリアに対応する各矩形領域内に有料道路を含むかどうか判定することで出発地，目的地間を結ぶ直線あるいはその周辺領域に有料道路が全く存在しない矩形領域が明らかにわかる場合には、その矩形領域の一辺の長さなどを元に領域の通過想定距離を求めて全体の予想走行距離から差し引いて、有料道路の予想走行距離を算出する。
【００４８】
Ｓ４０３：この処理ステップでは、有料道路の予想走行距離に対する料金単価を算出する。この料金単価は、設定値記憶部１１０に設定された有料道路料金の対距離単価の値の中から走行予定地域の代表値を読み出す。本処理で求める有料道路料金の対距離単価は、有料道路の走行料金に相当する時給換算コストを計算するためのものであり、道路区間ごとに正確である必要はなく、ここの有料道路区間の料金単価が時給換算コストに対して「お得」かどうかを判定するためのものである。
【００４９】
例えば日本の都市間高速道路のように、距離に対して一定と想定される場合には、予め指定した値を使えばよい。距離に応じて明らかに料金が異なるような場合、距離に対する料金ルールに応じて料金単価を設定する。たとえば１００km以上に距離逓減制度（ある距離を過ぎたら、それ以降の距離単価が割り引かれる制度）がある場合や、一定料金が加算されるような場合は、こうした要因を考慮して利用料金を積み上げ、それを予想走行距離で割ることにより、料金の対距離単価を設定してもよい。
【００５０】
地域によって異なる有料道路料金体系が存在する場合は、その地域内に存在する有料道路料金単価の最大値，平均値，最小値といった代表値を取得し、料金単価を計算してもよい。地域内の有料道路料金単価は、ネットワーク地図ＤＢ１１１に格納されている地図データ及び図３に示すような有料道路料金ＤＢ１０５の距離・料金表３０１から計算することもできるし、予め計算した値を地域ごとにネットワーク地図ＤＢ１１１の地図に含めておいてもよい。また、距離によらず区間一定の料金体系をとる有料道路区間が存在する場合には、地域内の有料区間の料金を平均し、それを区間距離合計で割ることによって距離に対する料金単価を計算できる。
【００５１】
本発明の有料道路には、都市中心部進入によって課金される渋滞課金の区間を含んでもよい。この場合、区間ごとに一定の料金が発生する料金ルールを適用することにより、渋滞課金が適用されるエリアの大きさを表す代表長（半径やエリアの一辺）の大きさを走行予定距離とし、課金料金をこの代表値で割ることにより料金の距離単価が計算できる。渋滞課金エリアを避ける経路は、この料金単価から算出される時給換算コストを後述する図６の処理により小さめにとることによって実現できる。
【００５２】
図１６に、距離逓減制度がある場合の距離に対する有料道路料金単価を算出する処理のフローチャートを示す。本処理はＳ４０３の処理の一つの例を示したものである。
【００５３】
Ｓ１６０１：この処理ステップでは、Ｓ４０２で求めた有料道路の走行予定距離（ｄ）と距離逓減制度により料金が変化する距離（ｄｓ）を比較する。走行予定距離入力（ｄ）が料金が変化する距離（ｄｓ）以下の場合（ＮＯの場合）Ｓ１６０３に、そうでなければ（ＹＥＳの場合）Ｓ１６０２に進む。
【００５４】
Ｓ１６０２：この処理ステップでは、式５を用いて、ｄｓまでの有料道路料金の対距離単価（αｓ）とｄから料金の増加分（Ｔｉ）を算出する。有料道路料金の対距離単価（αｓ）は設定値記憶部１１０から読み込む。この値は一定値でもよいし、外部媒体によって更新されてもよい。
【００５５】
Ｓ１６０３：この処理ステップでは、αｓとｄｓ，ｄｓ以降の有料道路料金の対距離単価（αｆ）とｄから走行予定距離（ｄ）に対する料金の増加分（Ｔｉ）を、料金が変化する距離（ｄｓ）までの料金とｄｓ以降の料金の和として式５を用いて算出する。ｄｓ以降の有料道路料金の対距離単価（αｆ）に関してもαｓと同様に設定値記憶部１１０から読み込む。
【００５６】
Ｓ１６０４：この処理ステップでは、料金の増加分（Ｔｉ）に有料道路料金のベースとなる一定料金を加算し、これに税率を掛けて距離ｄにおける予想料金（Ｔｏ）を算出する。
【００５７】
Ｓ１６０５：この処理ステップでは、全区間平均での料金単価（α）をＴｏとｄにより算出する。
【００５８】
例えば、ｄ＝１５０km，ｄｓ＝１００km，αｓ＝２４.６km／円，αｆ＝１８.４５km／円，一定料金＝１５０円，税率＝５％とすると、α＝２５.８km／円となる。
【００５９】
図４に示す処理フローの説明に戻る。
【００６０】
Ｓ４０４：この処理ステップでは、設定値記憶部１１０から読み出した有料道路，一般道路の期待平均速度Ｖａ，Ｖｔから有料道路の走行時間に対する料金を表す対時間単価Ｃｔを算出する。式４によって、有料道路，一般道路それぞれの平均速度Ｖ１，Ｖ２として有料道路期待平均速度Ｖｔ，一般道路期待平均速度Ｖａを代入し、Ｓ４０３で算出した対距離単価αを代入することで、有料道路料金の対時間単価Ｃｔ、すなわち時間に対する有料道路料金の傾きを算出することができる。Ｓ４０４で算出した有料道路料金の対時間単価Ｃｔは、有料道路対時間単価算出手段１０１の処理結果として図示されていない一時記憶の中に保持する。
【００６１】
図１７は、有料道路料金の対時間単価（Ｃｔ）を算出する処理の例であり、Ｓ１７００で有料道路料金の対距離単価（α），有料道路の期待平均速度（Ｖｔ），一般道路の期待平均速度（Ｖａ）を設定値記憶部１１０から読み込み、Ｓ１７０１に示すように、式４から有料道路料金の対時間単価Ｃｔが計算できる。一例として、Ｖｔ＝８０km／時，Ｖａ＝４０km／時，α＝２４.６km／円とすると、Ｃｔ＝−１９８４円／時となる。
【００６２】
図５は、時給換算単価算出手段１０２の処理を表したフローチャートである。
【００６３】
Ｓ５０１：この処理ステップでは、有料道路対時間単価算出手段１０１によって算出した有料道路料金の対時間単価Ｃｔを読み込み、符号を反転させた値を時給換算単価Ｃとする。この符号を反転させた時給換算単価Ｃを用いることにより、事前の想定に対して有料道路の平均速度が事前に設定された有料道路期待平均速度よりも速いまたは有料道路料金が通常よりも安い、即ち費用対効果の面で有料道路の利用が「お得」な区間については有料道路を優先し、有料道路の平均速度が有料道路期待平均速度よりも遅いあるいは一般道路の平均速度が一般道路期待平均速度よりも速い区間については一般道路が優先されることとなる。
【００６４】
図１８は上記それぞれのケースについて例示したものである。共通の条件としては、有料道路の期待平均速度を８０km／時、一般道路の期待平均速度を４０km／時とする。また、有料道路料金の対距離単価αは２４.６円／kmとしている。また、図２（ａ）の仮定の下で有料道路，一般道路ともに走行距離は２０kmとする。この時の時給換算単価Ｃは、図１７の説明で用いた例から、図１６で説明した一定料金は考慮せず税率を５％とした場合には２０６４円／時となる。ケース１は有料道路の走行速度が１００km／時と期待平均速度Ｖｔより早く、ケース３は、走行区間の有料道路料金が割引制度により半額となったケースであり、有料道路料金と時給換算コストを単純に加算した有料道路の総費用は一般道路のそれよりも小さく、単純に並行する区間であればコストが小さい区間が選ばれることとなる。逆にケース２は有料道路が６０km／時と想定より遅く、ケース４は一般道路が６０km／時と想定よりも速い場合であり、どちらのケースも一般道路の方が総費用が小さくなっている。すなわち時給換算コストによる期待平均速度における有料道路区間のキャンセル効果が得られている。
【００６５】
Ｓ５０２：この処理ステップでは、ユーザ設定により時給換算単価Ｃの調整を行う。ユーザ設定では、図１３に示すような画面を用いて時給換算単価Ｃを調整する。ユーザが時給換算単価を増やす方向に調整すれば、時間に対する重みが増えることとなり、経路探索結果は有料道路区間がより多く選択される傾向となる。逆にユーザが時給換算単価を減らす方向に調整すれば、時間に対する重みが減ることとなり、経路探索結果では一般道路区間がより多く選ばれる傾向となる。この調整処理を備えることにより、今までの基準よりも有料道路区間を増やしたりあるいは所要時間を遅くしたりといった設定が、基準の値からの増減といった形でユーザの好みにより設定できる。また設定値記憶部１１０に記憶している値を出発地，目的地と対応付けて別途不揮発性の記憶装置に格納しておき、経路探索時にこの値を呼び出した後、基準の値をＳ５０１までの処理によって設定しておくことで、過去の同一出発地，目的地を対象とした経路との有料道路区間の利用割合を比較できるため、ユーザは試行錯誤によって基準の値を設定する手間が省けることとなる。
【００６６】
図１３は、時給換算単価Ｃの調整を行うための画面を説明したものである。時給換算単価Ｃと、有料道路対時間単価Ｃｔの間は、Ｃ＝−Ｃｔという関係としているため、時給換算単価Ｃの調整は有料道路対時間単価Ｃｔを調整することによって実現できる。そしてこの有料道路料金の対時間単価Ｃｔの算出には、期待平均速度Ｖｔ，Ｖａが用いられるため、これらの期待平均速度Ｖｔ，Ｖａを変更すればよい。このため、図１３に示す画面を操作することで、期待平均速度Ｖｔ，Ｖａを変更する。１３０１は基本設定画面、１３０２は詳細設定画面、１３０３は有料道路料金の対時間単価Ｃｔの加算ボタン、１３０４は逆に有料道路料金の対時間単価Ｃｔの減算ボタン、１３０５は詳細設定画面への遷移ボタン、１３０６は有料道路の期待平均速度の設定値入力欄、１３０７は一般道路の期待平均速度の設定値入力欄、１３０８は設定変更に伴う状態変化を示すグラフ、１３０９は基本設定画面への遷移ボタンである。
【００６７】
ボタン１３０３は対時間単価の絶対値を所定の単位で増加させ、ボタン１３０４は対時間単価を所定の単位で減少させる。具体的には、式４とＣ及びＣｔの関係から、時給換算単価Ｃが常に正の値を取るようにして、Ｃ＝対時間単価の絶対値｜Ｃｔ｜＝α×Ｖｔ×Ｖａ÷（Ｖｔ−Ｖａ）に対して、増減幅をｄＣとして設定変更後の時給換算単価をＣ±ｄＣに再設定する。そして、有料道路の料金体系が頻繁に変わることが無ければ料金の対距離単価αが変わることも無く、統計交通情報を用いることで予め一般道路における平均速度をある程度正確に評価できることから一般道路期待平均速度も大きく変更する必要が無く、むしろ有料道路の利用でどれだけ所要時間が短縮され又料金が高くなるかに関心が高いものと仮定して、新たに設定した時給換算単価に対して、有料道路料金の対距離単価α，一般道路期待平均速度（Ｖａ）を固定すれば、新たに設定した時給換算単価に対応した対時間単価に対する有料道路期待平均速度（Ｖｔ）が求まる。対時間単価の絶対値を増加することにより、時給換算単価Ｃが有料道路料金に比べて増大するため、エコノミールートはより時間重視の経路探索結果を出力するようになる。逆に対時間単価を減少することにより、時給換算単価が有料道路料金に比べて減少するため、エコノミールートはより料金重視の経路探索結果を出力するようになる。ユーザにとっては、簡便な操作によってエコノミールートの設定変更が可能となる。
【００６８】
ボタン１３０５は画面を詳細設定画面１３０２に遷移させる。詳細設定画面１３０２では、有料道路及び一般道路の期待平均速度を直接設定し、有料道路を優先する目安となる速度を直接操作することができる。状態変化を表すグラフ１３０８では、横軸に有料道路の期待平均速度，縦軸に一般道路の期待平均速度を示しており、実線によって新しい設定における有料，一般利用の境界線を示し、有料道路利用となる速度領域を網掛けで示している。また、破線によって現在の設定における有料道路利用と一般道路利用の境界線を表し、設定変更による有料道路利用領域の変化を表示する。境界線はＣを一定としたときのＶｔ，Ｖａの関数関係を表した特性曲線である。前述の関係式Ｃ＝｜Ｃｔ｜＝α×Ｖｔ×Ｖａ÷（Ｖｔ−Ｖａ）をＶａに関して解くと、
Ｖａ＝１÷ｋ×（１−１／（ｋ×Ｖｔ＋１）） ただしｋ＝α÷Ｃ … （式７）
という曲線になる。この曲線はＶａ＞０，Ｖｔ＞０の範囲で単調増加、かつ上に凸の形状を示す。期待平均速度の組み合わせは点として１３０８中に表現し、現在値及び設定変更による推移した値を表示する。有料道路料金の所要時間に対する変化とバランスするように時給換算コストを設定していることから、Ｃを一定とした場合の式７による曲線は、有料道路利用のお得感がちょうど釣り合うような有料道路及び一般道路の期待平均速度の組み合わせ、つまりお得感が同じ期待平均速度の状態を表していると見ることができる。そこでこのグラフ１３０８により、ユーザは設定されている速度以外での有料道路，一般道路の期待平均速度の状態において、有料道路利用優先になる領域を把握することができる。すなわちユーザが普段居住している地域の有料道路利用，一般利用の期待平均速度を入力することによって、交通状況が異なり走行速度が変わる地域で「お得」なのは有料優先となるか一般優先となるかを判断することが可能となる。
【００６９】
本設定画面により、ユーザは簡便にパラメータ調整が可能となり、また、速度によって有料道路利用，一般利用を見通すことができるようになる。
【００７０】
以上、図３から図５の処理が最小料金コスト経路探索を行うための前処理である。以下では、料金コスト利用経路探索手段１０４における最小料金コスト経路探索について図１９，図２０を用いて説明する。
【００７１】
図１９は、最小料金コスト経路探索処理のフローチャートを表し、図２０は経路探索で用いるノード群を構成するノードデータのデータ構造を示している。図１９は経路探索の一般的手法として知られるダイクストラ法の処理フローを表したものであるが、図２０に示したようにノード到達時刻，有料道路入口ノードを持ち、これらのデータを更新することによって料金コスト計算を可能としている点が料金コスト探索を実現するための特徴である。以下図１９のフローチャートについて説明し、必要に応じて図２０のデータ構造について説明する。
【００７２】
Ｓ１９００：この処理ステップでは、経路探索部１００に入力された出発地，目的地を経路探索のために取り込み設定する。
【００７３】
Ｓ１９０１：この処理ステップでは、ネットワーク地図ＤＢ１１１からＳ４００ｄｅ算出された経路探索エリアに含まれるノード群を読み込む。ノード群は図２０のテーブル２０００に示すデータ構造で表現される。「ノード番号」はノードを一意に決定する番号、「確定フラグ」はノードにいたる最小コスト経路が確定したか否かを表すフラグ、「コスト」はノードに到達するまでに要したコストで、最小料金コスト経路探索では料金コストにあたる。「直前ノード番号」は、このノード番号で表される現在のノードに至った経路を表し、「ノード到達時刻」はリンク旅行時間の積算で計算された現在のノードの到着時刻、「有料入口ノード」は現ノードに至るまでに通過した最も近くの入口のノードを表すノード番号、「有料入口からの距離」はその「有料入口ノード」からの積算距離、「有料入口通過時刻」は有料入口ノードの通過時刻を表す。Ｓ１９０１の処理時点では経路探索範囲の全てのノードに関してノード番号のみが読み込まれ、他の値は不定となる。
【００７４】
Ｓ１９０２：この処理ステップでは、ノード群中から出発地のノードを検出し、そのノードの「コスト」を０にセットする。「コスト」に値が定まることによってそのノードは候補ノードとなり、最小コストを求める対象ノードとなる。また、本処理では出発時刻をこの出発地のノードの「ノード到達時刻」として代入する。
【００７５】
Ｓ１９０３：この処理ステップでは、候補ノード２００１で表されるような候補ノード群の中からコストが最小なものを取り出す。取り出されたノードはダイクストラ法の原理により、最小コスト経路が確定したノードとなるので、確定ノード２００２のように「確定フラグ」を有効にし、確定ノードの１つとして次回からのコスト算出候補の対象外となる。
【００７６】
Ｓ１９０４：この処理ステップでは、Ｓ１９０３で確定ノードとしたノードが目的地ノードかどうか判定する。この確定ノードが目的地ノードであれば目的地までの最小コスト経路が確定したことになるので、Ｓ１９０９の処理に進み探索処理を終了する。確定ノードが目的地ノードでなければ、Ｓ１９０５に進む。
【００７７】
Ｓ１９０５：この処理ステップでは、確定ノードに接続するリンク群を取り出す。このうちリンクの終端ノードすなわち次のノードが確定ノードでないリンク群について、Ｓ１９０６からのループ処理の対象とする。
【００７８】
Ｓ１９０６：この処理ステップでは、Ｓ１９０５で取り出した接続リンク数分のループ処理を行う。
【００７９】
Ｓ１９０７：この処理ステップでは、リンク単位処理部１０６において料金コストの計算を行う。これは、リンクの料金コストを計算してリンク終端ノードまでのコストを算出する処理である。
【００８０】
Ｓ１９０８：この処理ステップでは、リンクの終端ノードを候補ノードとしてその「コスト」を更新する。既に計算されているリンク料金コストが存在する場合は、この処理ステップで計算したコストの方が小さい場合のみ更新を行う。直前ノード番号にはリンクの始端ノード、すなわち確定ノードのノード番号を、「ノード到達時刻」は、確定ノードの到着時刻にリンク旅行時間を加算した値を設定して更新する。また、同時に終端ノードが有料道路の入口ノードであれば、新たに「有料入口ノード」に終端ノードを設定し、終端ノードの到着時刻を「有料入口通過時刻」に設定し、「有料入口からの走行距離」も“０”にリセットする。終端ノードが有料道路の入口ノードでなければ、リンクの始端ノード、すなわち確定ノードのノードデータにある「有料入口ノード」，「有料入口通過時刻」の値をそれぞれコピーし、「有料入口からの走行距離」へはリンク長を加算した値を設定して入口からの距離を更新する。これにより、全ての候補ノードにおいて対応する有料道路入口，有料道路入口からの距離，有料道路入口の通過時刻がわかるため、料金ルールあるいは有料道路料金ＤＢによって有料道路料金が計算可能となる。
【００８１】
全ての接続リンク群に対してループ処理を行ったのち、処理は再びＳ１９０３に進む。
【００８２】
Ｓ１９０９：この処理ステップでは、目的地から「直前ノード」を逐次たどり、出発地までの確定ノード列を経路探索結果として出力する。
【００８３】
図６は、リンク単位処理部１０６における個々のリンクに対する処理の詳細を表したフローチャートである。複数料金コスト加算手段１０３における処理はＳ６０１，Ｓ６０９の処理に、リンク費用コスト算出手段１０７における処理はＳ６０２からＳ６０６の処理に、リンク時給換算コスト算出手段１０８における処理はＳ６０８の処理に該当する。
【００８４】
Ｓ６０１：この処理ステップでは、処理対象とするリンクの「コスト」に値が設定されていなければリンク料金コストを初期化して“０”を設定する。ここでリンク料金コストとは、リンク（経路探索時に用いるネットワークを構成する単位で、具体的には交差点間で表現される区間を表す）ごとの料金コストを表す。特に断らない限り以下の処理ステップでは、
リンク料金コスト＝リンク費用コスト＋リンク時給換算コスト＋リンク燃料費
… （式８）
であるとする。
【００８５】
Ｓ６０２からＳ６０６はリンク費用コストを算出する処理ステップである。
【００８６】
Ｓ６０２：この処理ステップでは、該当リンク内、またはリンクの終端に料金所があるか否かの判断を行い、その結果で分岐処理を行う。これは、リンク費用コストは料金の支払いが発生する箇所で料金を加算するためである。ＹＥＳの場合はＳ６０３に進み、ＮＯの場合はリンク費用コスト＝０としてＳ６０８に進む。
【００８７】
Ｓ６０３：この処理ステップでは、リンクの始端ノードのノードデータにおける「有料入口ノード」情報から入口インターに対応するノード番号を読み出す。つまり経路探索の出発地点が一般道路上である場合、経路探索の仮定で必ず有料道路の入口を通過するので、直近の入口インターを予め記憶させておいた確定ノード（リンク始端側ノード）のノードデータ２００２の有料道路入口ノードを利用する。出発地点が既に有料道路上である場合、直近の入口インターが存在しない場合がある。このとき実際に通過した入口インターが、例えばＥＴＣ車載機との連動やユーザの入力によって取得できる場合には、この入口インターの情報を有料道路入口の情報として読み込むものとする。あるいは、ネットワーク地図ＤＢ１１１から出発地点の直前にあたるインターチェンジを探し、これを入口インターとして代用することも可能である。
【００８８】
Ｓ６０４：この処理ステップでは、有料道路料金ＤＢ１０５から入口インターからこのリンクまでの区間の有料道路料金情報を取り出す。有料道路料金ＤＢ１０５は、図３に示すような距離・料金表３０１を電子データとして保持したものである。距離・料金表３０１は料金体系の異なる車種ごとに保持しておき、車両の種類に応じて取り出してもよい。距離・料金表３０１は入口インター群３０２と出口インター群３０３との組み合わせによって、料金が一意に定まる構造である。インター間の料金とともに距離が保持されていてもよい。
【００８９】
Ｓ６０５：この処理ステップでは、割引ルールが適用されるか否かによって分岐処理を行う。ＹＥＳの場合Ｓ６０６に進み、ＮＯの場合Ｓ６０７に進む。割引ルールが適用されるかどうかは、図２０に示した確定ノード２００２のノードデータに含まれる「有料入口からの走行距離」及び「有料入口通過時刻」、及び「ノード到達時刻」に現リンクのリンク旅行時間を加算した出口インターの通過時刻を読み出し、割引ルールの適合条件を満たすかどうかで判断する。例えば、入口インターの通過時刻，出口インターの通過時刻によって割引適用を判断する場合には、ノードの到着時刻，入口インターの通過予想時刻，出口インターの通過予想時刻のいずれか一つを用いて判断する必要があり、どの時刻も割引条件を満たさないような場合は割引ルールを適用しない。特定の機器の利用、例えばＥＴＣ車載機の有無により割引適用条件が変わる場合には、ＥＴＣ機器との接続有無、あるいはユーザの接続設定によって判断する。距離や区間によって割引適用条件が異なる場合は、その条件にしたがって割引の有無を判断する。割引ルールは有料道路料金ＤＢ１０５に格納されているものとする。
【００９０】
Ｓ６０６：この処理ステップでは、割引ルールを適用し、有料道路料金を変更する。例えば、割引ルール条件を満たせば半額といったルールが存在すれば、距離・料金表３０１から求めた有料道路料金を半額にセットする。あるいは、割引後の有料道路料金を距離・料金表３０１に保持しておくようにしてもよい。
【００９１】
Ｓ６０８：この処理ステップでは、リンク時給換算コストを計算する。これは次の式９で求まる。
【００９２】
リンク時給換算コスト＝時給換算単価Ｃ×リンク旅行時間 … （式９）
【００９３】
時給換算単価Ｃは、時給換算単価算出手段１０２で算出した結果を用いる。リンク旅行時間はネットワーク地図ＤＢ１１１の道路ネットワークデータに含まれる一定値の他、外部から取得したリアルタイム交通情報を考慮した値や図１０に示す時間帯別リンク速度ＤＢ７０７を更に設け、この時間帯別リンク速度ＤＢ７０７から読み込んだリンク速度データに基づき算出した値を使ってもよい。この時間帯別リンク速度ＤＢ７０７は、図１０に示すように、メッシュ番号（緯度経度によって地図上の領域を表現した番号）１００１でエリアごとに管理し、各メッシュに含まれるリンクについて、時間帯別リンク速度１００２に示すように平日，休日といった日種、および時間帯ごとに変化するリンクの統計的な速度データを保持している。この場合、時間帯別リンク速度ＤＢ７０７の速度データを用いた有料道路期待平均速度、及び一般道路期待平均速度が設定値記憶部１１０に設定され、有料道路対時間単価算出手段１０１は、これらの有料道路期待平均速度、及び一般道路期待平均速度を用いて有料道路料金の対時間単価を算出することになる。
【００９４】
Ｓ６０９：この処理ステップでは、式８に従い、既に求めたリンク費用コストとリンク時給換算コストにリンク燃料費を加算し、ノードデータの「コスト」に設定する。すなわちＳ６０９の時点で、リンク料金コスト＝リンク費用コスト＋リンク時給換算コスト＋リンク燃料費となる。リンク燃料費の計算にあたっては、一般に知られる方法を用いるものとする。例えば式６を用いれば、
リンク燃料消費量＝Ｆｃ×リンク旅行時間＋Ｃｆ×リンク長＋空気抵抗分＋高度変化 分＋速度変化分
リンク燃料費＝燃料単価×リンク燃料消費量
として計算できる。空気抵抗分は走行速度によって定まるので、リンク長やリンク旅行時間で算出できるリンク速度を用いればよい。高度変化分には地図ネットワークＤＢ１１１にリンク単位の高度データが含まれているか、あるいは推定に必要な値が含まれていれば算出可能となる。また、速度変化分については、走行速度から加速頻度を推定するなどすればよい。燃料単価は、設定値記憶部１１０に予め定めておいた設定値を利用するか、外部情報にアクセスして取得してもよい。
【００９５】
以上、図３から図６に記載された本発明の経路探索コスト決定方法を用いて、料金コスト利用経路探索手段１０４によって最小料金コストによる経路探索を実行することによって、図２及び図１４に示したエコノミールートを算出することができる。これによってユーザは時間と料金の両方を考慮した「お得」な経路を、煩雑な設定を伴わずに取得することが可能となる。また、システムは、有料道路優先，一般道路優先とも異なる経路探索コスト決定方法を用いているために、ユーザはどちらとも異なる経路を取得することが可能となる。
【００９６】
また時間帯別リンク速度ＤＢ７０７を用いることにより、料金と時間とを考慮した上で、時間帯ごとに異なるエコノミールートを求めることができる。
【実施例２】
【００９７】
図７は本発明を用いた経路探索装置における経路探索部の変形を示す図である。図１の構成に対して、外部から取得する料金ルールプロファイル７０６に従い料金算出ルールを更新する料金ルール更新手段７０５を追加している。この追加に伴い、有料道路料金の対距離単価についても料金ルールプロファイル７０６を用いて算出する。また、リンク費用コスト算出手段７１７は、料金ルールプロファイル７０６に基づき有料道路のリンク費用コストを算出する。図７の構成によって算出される最小料金コスト経路は、料金ルール更新手段７０５により、有料道路対時間単価算出手段１０１における有料道路料金の対時間単価，複数料金コスト加算手段１０３におけるリンク料金コストが変更可能となり、有料道路料金体系の変更や割引ルールの変更に対してもエコノミールートを提供することができる。以下、図７の処理の詳細について図８ないし図１０、及び図１５を用いて説明する。
【００９８】
図８は料金ルール更新手段７０５の処理をフローチャートで表したものである。以下処理ステップに従い説明する。
【００９９】
Ｓ８０１：この処理ステップでは、料金ルールプロファイル７０６を読み込む。料金ルールプロファイル７０６は、経路探索装置の外部から入手する情報であり、例えば通信によって内容を更新する。あるいはユーザ設定によって更新してもよい。料金ルールプロファイル７０６に格納されるデータの一例を図１５に示す。料金ルールプロファイルに格納されるデータはデータ１５００のような形式で表現し、料金パラメータの変更，料金算出ルールの変更内容，割引ルールの変更内容をデータとして記述した形をとる。１５０１，１５０２は料金パラメータ変更、１５０３は料金算出ルール変更、１５０４は割引ルール変更の例である。料金パラメータ変更１５０１では、対象エリアとして全国の自動車道、対象期間は指定なしとして、距離に対する料金単価、即ち有料道路の対距離単価αの設定を変更する例である。料金ルールの変更があった場合、有料道路対時間単価算出手段１０１，リンク費用コスト算出手段７１７にて変更されたルールの記述を適用する。例えば、１５０１の変更については、有料道路対時間単価算出手段１０１では、対象エリアの有料道路料金の対距離単価αとして料金パラメータ変更１５０１の“［料金単価］”に記述された値を使用する。また、リンク費用コスト算出手段７１７での利用方法に関しては図９の説明にて後述する。
【０１００】
料金パラメータ変更１５０２は、対象エリアとして特定の有料道路，対象期間を指定して距離に対する料金単価の設定を変更する例である。ここで挙げた料金パラメータ変更は料金単価の変更を記載しているが、個々のインター間の有料道路の距離・料金表のデータを記述してもよい。また、料金パラメータ変更として、距離逓減制が変更となる距離長，割引率などの変更を記述してもよい。ルールを適用する際には、“［対象エリア］”と“［対象期間］”の記述に基づき場所と時間の条件を変更し、また逓減制度が変更となる場合には、距離長に関してもその計算パラメータを変更して利用する。
【０１０１】
料金算出ルール変更１５０３は、対象エリアを指定して料金制度を一律料金制度から距離従量制へと変更するためのデータである。料金算出ルール変更としては、“［料金制度］”に小区間単位の料金徴収制を記載してもよい。割引ルール変更１５０４は、対象エリア，対象期間，対象時間帯，対象車両，対象条件，割引率など割引に関するルールの変更を記載した例である。割引ルールの変更に関してはリンク費用コスト算出手段７１７にてルールを適用する。詳細は図９の説明にて後述する。
【０１０２】
Ｓ８０２：この処理ステップでは、料金パラメータの更新を行う。料金パラメータの更新処理により、有料道路対時間単価算出手段１０１で用いる対距離単価αや距離逓減の割引率に使用される各種料金パラメータが変更となる。また、リンク費用コスト算出手段７１７にて、リンク費用コストを算出する際に料金パラメータが変更となる。
【０１０３】
Ｓ８０３：この処理ステップでは、料金ルールの更新を行う。料金ルール自体は、有料道路対時間単価算出手段１０１，リンク費用コスト算出手段７１７にて利用されるが、予め処理プロセスに搭載された料金ルールを料金ルールプロファイル７０６にしたがって変更する処理となる。
【０１０４】
Ｓ８０４：この処理ステップでは、割引ルールの更新を行う。有料道路対時間単価算出手段１０１，リンク費用コスト算出手段７１７にて利用される割引ルールのパラメータ変更と割引ルール自体を変更する。割引ルールの変更も料金ルールの更新と同様、予め処理プロセスに搭載された割引ルールを料金ルールプロファイル７０６にしたがって変更する処理となる。
【０１０５】
図９は、リンク費用コスト算出手段７１７を含むリンク単位処理部７１６における処理のフローチャートを示したものである。
【０１０６】
本処理では有料道路料金ＤＢが存在しない場合でも、料金ルールによってのみ有料道路区間の料金を計算する方法について示した例である。料金コスト利用経路探索手段１０４の経路探索自体は、前述の実施例１と同様であるため、全ての候補ノードにおいて対応する有料道路入口，距離，通過時刻がわかり、料金ルールによって有料道路料金が計算可能となる。以下処理ステップに従い説明する。
【０１０７】
Ｓ９０１：図６のＳ６０１と同じ。
【０１０８】
Ｓ９０２：この処理ステップも、図６のＳ６０２と同様の分岐処理を行う。ＹＥＳの場合Ｓ９０３に進み、ＮＯの場合Ｓ９０８に進む。
【０１０９】
Ｓ９０３：図６のＳ６０３と同じ。
【０１１０】
Ｓ９０４：この処理ステップでは、料金ルールに基づき入口インターからこのリンクまでの区間の有料道路料金を算出する。図６のＳ６０４では有料道路料金ＤＢから予め計算された料金データを抽出したが、ここでは料金ルールに基づき有料道路料金を算出する。例えば、入口インターからの距離が距離逓減ルールの適用範囲であれば、その距離逓減ルールによって該当区間の対距離単価を算出し、対象リンクのリンク長合計に距離逓減ルールに基づく対距離単価を乗じて距離逓減ルール該当区間の有料道路料金が計算できる。また、リンク費用コスト計算の際には、入口，出口間の対距離単価によるリンク費用コストに対して、基本料金に相当する金額を有料道路料金に加えることで、予め計算された有料道路料金ＤＢの距離・料金表３０１と同じ値になるようにする。
【０１１１】
Ｓ９０５：図６のＳ６０５と同じ。
【０１１２】
Ｓ９０６：この処理ステップでは、割引ルールを適用する。割引ルールが複数存在し、適用区間が異なるような場合は、入口インターから該当する出口インターまでの区間を構成する有料道路の各リンクについて、最も値が小さくなる割引ルールを適用してリンク単位の有料道路料金を計算していき、割引ルールが変更となる地点、あるいは時間を通過した時点でそのリンクに累積で利いた割引分を元に戻す処理を行う。例えば、
割引ルール１：０：００−４：００をまたいで走行した場合、全区間４割引
割引ルール２：２２：００−６：００に入口、または出口を通過し、走行距離が１００km以内ならば、区間内５割引
といった二つの割引ルールが存在する場合は、割引率の高い割引ルール２を適用し、確定ノードのノードデータに含まれる有料道路入口インターから１００km以内の有料道路区間の料金は５割引で算出する。１００kmを超えた時点で割引ルール１適用となるが、その差額である過去１００km内の累積料金差を有料道路料金に加算する。さらに候補ノードが有料道路の出口インターに該当する出口ノードにおいて、割引ルール１の時間帯を満たさないことが判明した場合、割引なし時と割引ルール１適用時の有料道路区間分の累積料金差を有料道路料金に加算する。
【０１１３】
Ｓ９０７：この処理ステップでは、リンク速度を時間帯別リンク速度ＤＢ７０７から読み出す。または外部から取得したリアルタイム交通情報からリンク速度データを取得する。そして、リンク長と確定ノードの到着時刻に対応する時間帯のリンク速度からリンク旅行時間を計算する。また、リアルタイム交通情報からリンク旅行時間が入手可能な場合には、その値を利用する。
【０１１４】
Ｓ９０８：図６のＳ６０８と同じ。Ｓ９０７で読み込んだリンク旅行時間を用いる。
【０１１５】
Ｓ９０９：図６のＳ６０９と同じ。なお、燃料費の算出に旅行時間，速度が必要な場合にはＳ９０７で求めたリンク旅行時間を利用する。
【０１１６】
以上に示した経路探索コスト決定方法により、料金コスト利用経路探索手段１０４によって最小料金コストによる経路探索を実行して、時間帯や交通状況によって変化する図２及び図１４に示したエコノミールートを算出することができる。そして料金ルール更新手段を備えることにより、料金ルールの変更に際してもユーザはエコノミールートにより「お得」な経路を享受することができる。
【実施例３】
【０１１７】
図１１は本発明を用いたナビゲーション装置の全体構成を表した図である。図１１では自動車に装備したナビゲーション装置を記載しているが、携帯電話に搭載されたソフトウェアとしてもよい。また、ＧＰＳ受信機１１０７による位置検出手段の代わりに、出発地を入力する手段を備えていれば、通常のパソコン上で動作するソフトウェアとしてもよい。以下図１１に従いナビゲーション装置について説明する。
【０１１８】
１１０３はスピーカ、１１０４はナビゲーション装置、１１０５は表示ディスプレイ、１１０８はナビゲーション装置を搭載した車両である。また、１００，１１３，１１１０，１１１２はナビゲーション装置１１０４内部の図示されていないＣＰＵで動作するソフトウェアを示す。
【０１１９】
交通情報受信部１１１０は、交通情報受信器１１０６にて受信したリアルタイム交通情報を経路探索部１００で使える形でデータを解釈し、渡す処理を担う。
【０１２０】
経路探索部１００は、実施例１又は実施例２で説明したようにエコノミールート探索及び従来の有料優先，一般優先の経路探索処理を担う。
【０１２１】
比較提示部１１１２は、経路探索部１００から出力されるエコノミールートの経路探索結果を受け取り、画面表示または音声による経路案内を行う処理を担う。
【０１２２】
設定入力部１１３は、前述のようにユーザに設定変更画面を提示し、設定入力のためのインターフェースを備えて設定を保存し、各種変更を行う。
【０１２３】
図１１の例は、経路探索コスト決定方法をナビゲーション装置内部で行う構成であるが、ナビゲーション装置の外部に経路探索コスト決定を行うセンターを設置し、そこから通信によって求めたリンク料金コストをナビゲーション装置に取得するようにしてもよい。
【０１２４】
図１２は、比較提示部１１１２の画面案内と、経路探索時の画面遷移について示したものである。画面遷移は、図示されていない目的地設定画面で目的地を設定後、地図表示画面１２０１に遷移し自車位置マーク１２０５とともに目的地マーク１２０６を地図表示１２０４上に表示する。ここで、複数経路探索ボタン１２０３の押し下げにより経路探索中の状態に遷移し、経路探索終了後、比較表示画面１２０２に遷移する。そして比較表示画面１２０２にて選択した経路に基づいて経路誘導開始となる。図中１２０７ないし１２０９は、各種探索条件ごとに探索結果経路の距離，所要時間，全料金（有料道路料金＋燃料費）と有料道路料金を表したものであり、１２０７は有料優先ルート、１２０８はエコノミールート、１２０９は一般優先ルートを表す。１２１０ないし１２１２は地図上に示した各種探索条件による探索結果経路であり、１２１０は有料優先ルート、１２１１はエコノミールート、１２１２は一般優先ルートを表す。また、１２１３は有料道路入口インター、１２１４は有料優先経路における出口インター、１２１５はエコノミールートにおける出口インターを示す。本発明による経路探索コスト決定方法を用いることによって、１２０８に示す例にあるように有料優先，一般優先とも異なるエコノミールートが出力され得る。すなわち、有料優先の有料道路利用料金よりは料金が安いが時間はかかるようなエコノミールートが得られる。
【０１２５】
図１２のような比較提示により、ユーザはエコノミールートの従来ルートとの違いを定量的に理解することができる。また、表示だけでなく音声によって表現し、「エコノミールートは有料優先ルートに比べて２０分余計にかかりますが、料金は２２００円得します。」といった差を表現するような提示をしてもよい。
【実施例４】
【０１２６】
図２１は本発明による経路探索機能を備えたセンターと通信によって接続し、経路探索結果を取得するナビゲーション装置と周辺システムを表した図である。以下図１１に示した実施例３との相違点を中心に説明する。
【０１２７】
２１０４はナビゲーション装置、２１０６はセンターと接続するための通信装置である。また、１１３，１１１２，２１０７，２１０８はナビゲーション装置２１０４内部のソフトウェアを示す。２１１２は本発明による経路探索機能を備えたセンターであり、２１０９はナビゲーションからの通信を受信し応答する通信応答部、２１１０は交通情報センター１１０１と接続してリアルタイム交通情報を取得する交通情報受信部、２１１１は通信応答部２１０９によって受信したナビゲーション装置２１０４からの経路探索要求に対して交通情報受信部２１１０で取得したリアルタイム交通情報，時間帯別リンク速度ＤＢ７０７，有料道路料金ＤＢ１０５を用いて料金コストによる経路探索を行う、図１１の経路探索部１００に対応した経路探索部である。
【０１２８】
設定入力部１１３は、実施例３と同様、ユーザに設定変更画面を提示し、設定入力のためのインターフェースを備えて設定を保存し、各種変更を行う。
【０１２９】
出発・目的地設定部２１０７は、経路探索における出発地と目的地を設定する。出発地はＧＰＳ受信機１１０７によって取得した現在位置を用い、目的地はユーザの指定によって決定する。
【０１３０】
通信処理部２１０８は、センターへの料金コスト利用経路探索の要求とともに設定入力部１１３によって決定したリンク時給換算コスト算出に必要となる有料道路の期待平均速度及び一般道路の期待平均速度、あるいは時給換算単価を設定値としてセンターに送信する。また、経路探索のために必要な出発地，目的地の情報をセンターに送信する。出発地，目的地は緯度経度などの形式で送信する。センター側では経路探索部２１１１にて、通信応答部２１０９で受信したナビゲーション装置２１０４からの出発地，目的地，設定値に従い、図１１の経路探索部１００と同様に料金コスト利用経路探索を行い、経路探索結果をエコノミールートとして出力する。受信した設定値が、有料道路期待平均速度、及び一般道路期待平均速度の場合は有料道路対時間単価算出手段１０１の入力として利用する。受信した設定が、時給換算単価であった場合は、有料道路対時間単価算出手段１０１及び時給換算単価算出手段１０２の処理は行わず、与えられた時給換算単価を用いてリンク時給換算コストを算出する。また経路探索部２１１１は、エコノミールートの探索結果との比較のための経路探索も行う。比較経路としては、交通情報利用時の最短時間経路探索結果などを含めてもよい。
【０１３１】
通信処理部２１０８は、センター側から料金コストを利用したエコノミールートの経路探索結果、及び比較のための経路探索結果を受信する。経路探索結果は経路の所要時間，距離，料金，有料道路料金，燃料費を含める他、経路の形状がわかるフォーマット、例えば緯度経度列を含める。
【０１３２】
比較提示部１１１２は、実施例３と同様、エコノミールートの探索結果を画面表示、または音声による案内を行う処理を担う。
【０１３３】
図２１の構成によって、センター側で有料道路料金ＤＢを備えて料金コスト利用経路探索を行うことにより、最新の料金データや割引ルールを容易に反映することができる。
【産業上の利用可能性】
【０１３４】
本発明は、経路探索方法に関するものであり、主にソフトウェアの一部として利用されるものである。また、ナビゲーション装置としての利用も可能であり、経路探索による経路誘導機能として利用できる。
【符号の説明】
【０１３５】
１００ 経路探索部
１０１ 有料道路対時間単価算出手段
１０２ 時給換算単価算出手段
１０３ 複数料金コスト加算手段
７０５ 料金ルール更新手段
１０００ 時間帯別リンク速度ＤＢ
１１０４ ナビゲーション装置
【特許請求の範囲】
【請求項１】
リンク料金コストを経路探索コストとして利用する経路探索方法において、
有料道路の期待平均速度と一般道路の期待平均速度と有料道路料金対距離単価から有料道路利用時の有料道路料金対時間単価を算出し、
前記有料道路料金対時間単価から所要時間に対する料金単価である時給換算単価を算出し、
料金算出ルールまたは有料道路料金テーブルの少なくとも一方に基づき有料道路のリンク費用コストを算出し、
リンク旅行時間と前記時給換算単価からリンク時給換算コストを計算し、
リンク費用コストと時給換算コストとを加算したリンク料金コストを算出し、当該リンク料金コストを最小とする経路探索を行うことを特徴とする経路探索方法。
【請求項２】
請求項１に記載の経路探索方法において、リンク旅行時間は、リアルタイム交通情報または時間帯別のリンク速度データベースの少なくとも一方に基づき算出することを特徴とする経路探索方法。
【請求項３】
請求項１に記載の経路探索方法において、リンク料金コストに対してさらにリンクあたりの燃料費を加算することを特徴とする経路探索方法。
【請求項４】
請求項１に記載の経路探索方法において、外部からの情報により料金算出ルールを更新する料金ルールを更新することを特徴とする経路探索方法。
【請求項５】
請求項１ないし請求項４に記載の経路探索方法を用いて算出したリンク料金コストを用いて経路探索処理を行う経路探索手段を備えることを特徴とするナビゲーション装置。
【請求項６】
請求項５に記載のナビゲーション装置において、
ユーザの設定により有料道路の期待走行速度及び一般道路の期待走行速度、あるいは時給換算単価を変更する設定入力手段とを備えるナビゲーション装置。
【請求項７】
請求項１から請求項４に記載の経路探索方法を用いて算出したリンク料金コストを用いて経路探索処理を行う経路探索手段を備えるセンターに対し、通信により接続し、前記センターから経路探索結果を取得することを特徴とするナビゲーション装置。
【請求項８】
請求項７に記載のナビゲーション装置において、
ユーザの設定により有料道路の期待走行速度及び一般道路の期待走行速度、あるいは時給換算単価を変更する設定入力手段を備え、変更された有料道路の期待走行速度及び一般道路の期待走行速度、あるいは時給換算単価を通信によって前記センターに送信することを特徴とするナビゲーション装置。
【請求項１】
リンク料金コストを経路探索コストとして利用する経路探索方法において、
有料道路の期待平均速度と一般道路の期待平均速度と有料道路料金対距離単価から有料道路利用時の有料道路料金対時間単価を算出し、
前記有料道路料金対時間単価から所要時間に対する料金単価である時給換算単価を算出し、
料金算出ルールまたは有料道路料金テーブルの少なくとも一方に基づき有料道路のリンク費用コストを算出し、
リンク旅行時間と前記時給換算単価からリンク時給換算コストを計算し、
リンク費用コストと時給換算コストとを加算したリンク料金コストを算出し、当該リンク料金コストを最小とする経路探索を行うことを特徴とする経路探索方法。
【請求項２】
請求項１に記載の経路探索方法において、リンク旅行時間は、リアルタイム交通情報または時間帯別のリンク速度データベースの少なくとも一方に基づき算出することを特徴とする経路探索方法。
【請求項３】
請求項１に記載の経路探索方法において、リンク料金コストに対してさらにリンクあたりの燃料費を加算することを特徴とする経路探索方法。
【請求項４】
請求項１に記載の経路探索方法において、外部からの情報により料金算出ルールを更新する料金ルールを更新することを特徴とする経路探索方法。
【請求項５】
請求項１ないし請求項４に記載の経路探索方法を用いて算出したリンク料金コストを用いて経路探索処理を行う経路探索手段を備えることを特徴とするナビゲーション装置。
【請求項６】
請求項５に記載のナビゲーション装置において、
ユーザの設定により有料道路の期待走行速度及び一般道路の期待走行速度、あるいは時給換算単価を変更する設定入力手段とを備えるナビゲーション装置。
【請求項７】
請求項１から請求項４に記載の経路探索方法を用いて算出したリンク料金コストを用いて経路探索処理を行う経路探索手段を備えるセンターに対し、通信により接続し、前記センターから経路探索結果を取得することを特徴とするナビゲーション装置。
【請求項８】
請求項７に記載のナビゲーション装置において、
ユーザの設定により有料道路の期待走行速度及び一般道路の期待走行速度、あるいは時給換算単価を変更する設定入力手段を備え、変更された有料道路の期待走行速度及び一般道路の期待走行速度、あるいは時給換算単価を通信によって前記センターに送信することを特徴とするナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１１−７７０６（Ｐ２０１１−７７０６Ａ）
【公開日】平成２３年１月１３日（２０１１．１．１３）
【国際特許分類】
【出願番号】特願２００９−１５３１８０（Ｐ２００９−１５３１８０）
【出願日】平成２１年６月２９日（２００９．６．２９）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２３年１月１３日（２０１１．１．１３）
【国際特許分類】
【出願日】平成２１年６月２９日（２００９．６．２９）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]