経路探索装置、経路探索方法及びコンピュータプログラム
【課題】 料金面で割安となる割安ルートを事前に自動的に探索できるようにして、ユーザに対して経済的なルート案内を行う。
【解決手段】 本発明は、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索する経路探索装置である。この経路探索装置は、車両３が有料道路を途中で降りない基準ルートと、車両が有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するルート取得手段１８と、基準ルートを走行するのに必要な基準料金と、複数の乗り直しルートを走行するのにそれぞれ必要な乗り直し料金とを算出する算出手段１９と、両料金に基づいて、基準ルート及び複数の乗り直しルートの中から少なくとも１つの割安ルートを判定する判定手段２０と、を備えている。
【解決手段】 本発明は、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索する経路探索装置である。この経路探索装置は、車両３が有料道路を途中で降りない基準ルートと、車両が有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するルート取得手段１８と、基準ルートを走行するのに必要な基準料金と、複数の乗り直しルートを走行するのにそれぞれ必要な乗り直し料金とを算出する算出手段１９と、両料金に基づいて、基準ルート及び複数の乗り直しルートの中から少なくとも１つの割安ルートを判定する判定手段２０と、を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索するための経路探索装置、経路探索方法及びこれらを実行するためのコンピュータプログラムに関する。
【背景技術】
【０００２】
自車両を出発地点から目的地点まで誘導する経路探索装置（例えば、車載ナビゲーション装置）は既に周知である。この経路探索装置は、出発地点から目的地点までの最適経路を所定の経路探索ロジックを用いて演算し、この演算結果である最適経路を、ディスプレイやスピーカ等の出力装置を介して画像や音声で搭乗者に案内するものである。
かかる最適経路の探索手法は、例えば、リンクコストが最小となる最適経路を特定の経路探索ロジックによって算出するのが一般的であり、この経路探索ロジックとしては、例えばダイクストラ法やポテンシャル法が利用される（特許文献１参照）。
【０００３】
【特許文献１】特開平７−１０３７７７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、高速道路等の有料道路では、料金所での渋滞緩和を主目的として、ＥＴＣシステム（Electronic Toll Collection System ）の整備が進展している。
かかるＥＴＣシステムを採用した有料道路では、車両の走行時間帯、走行距離及び走行区間等の観点から設定された種々の条件を満たす場合に通行料金の割引が適用される、ＥＴＣ割引が既に実施されている。このＥＴＣ割引の代表例としては、深夜割引、通勤割引及び早朝夜間割引といった時間帯割引がある（図９参照）。
【０００５】
上記ＥＴＣ割引の割引率は、大きい場合で５０％という大幅なものであるから、この割引制度を上手く活用すれば、有料道路を含む経路を走行する場合の通行料金を大幅に削減することができる。
しかし、上記の通り、ＥＴＣ割引は、有料道路に対する車両の走行時間帯、走行距離及び走行区間等といった種々の観点からの条件が設定されているので、いかなる経路でいかなる時刻に有料道路を通行すれば割引が受けられるのかを、走行中の車両の搭乗者が即座に判断するのは非常に困難である。
【０００６】
例えば、前記通勤割引の場合には、有料道路の入口インターチェンジ（以下、ＩＣと略記することがある。）と出口ＩＣを所定の時間帯に通過するという時間帯条件に加え、入口ＩＣから出口ＩＣまでの走行距離が１００ｋｍ以内であるという走行距離条件が加重されている。
このため、車載のナビゲーション装置による指示通りに途中のＩＣで降りないで走行を継続した場合には、上記走行距離条件に適合しないが、敢えて途中のＩＣで有料道路を降りていったん一般道路を走行し、その途中のＩＣで当該有料道路に復帰する乗り直しルートを採用すれば、上記走行距離条件に適合することがある。
【０００７】
また、例えば、午後の通勤割引と早朝夜間割引とは、適用される時間帯条件が互いに近接している。
このため、車載のナビゲーション装置による指示通りに途中のＩＣで降りないで走行を継続した場合には、前半の通勤割引しか適用されないが、敢えて途中のＩＣで有料道路を降りて暫く一般道路を走行し、その途中のＩＣで当該有料道路に復帰する乗り直しルートを採用すれば、通勤割引と早朝夜間割引の双方が適用され、より割安となる場合もあり得る。
【０００８】
しかし、上記のような割安となる乗り直しルートを車両の搭乗者が走行中に察知するのは至難であり、かかる乗り直しルートで実際に走行するためには、搭乗者自身がＥＴＣ割引の適用条件を熟知した上で、予め周到な走行計画を立てておく必要がある。
そこで、ＥＴＣ割引の適用条件をコストとして想定し、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索する機能を有する経路探索装置があれば至便であるが、かかる経路探索装置は未だ実現されていない。
【０００９】
本発明は、このような問題点に鑑み、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを事前に自動的に探索できるようにして、ユーザに対して経済的なルート案内を行える経路探索装置等を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の経路探索装置（請求項１）は、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索するための経路探索装置であって、車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するルート取得手段と、取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートを走行するのにそれぞれ必要な乗り直し料金とを算出する算出手段と、算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定する判定手段と、を備えていることを特徴とする。
【００１１】
本発明の経路探索装置によれば、前記算出手段が、基準ルートを走行するのに必要な基準料金と、複数の乗り直しルートを走行するのに必要な乗り直し料金とを算出する。
この乗り直し料金には、有料道路を途中で降りて再度その降りた地点で当該有料道路に復帰する乗り直すルートを敢えて採ったことが原因で、有料道路の割引制度が適用され、基準料金よりも割安になっているものが含まれている場合がある。
【００１２】
そこで、本発明の経路探索装置では、判定手段が、算出された上記両料金に基づいて、基準ルート及び乗り直しルートの中から少なくとも１つの割安ルートを判定する。これにより、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを自動的に探索することができる。
このため、探索された割安ルートを、例えば車載のディスプレイやスピーカ等の出力装置を通じてユーザ（車両の搭乗者）に提供するようにすれば、そのユーザに対して経済的なルート案内を事前に行うことができる。
【００１３】
また、本発明の経路探索装置によれば、１つの乗り直しルートだけではなく、複数の乗り直しルートを走行するのにそれぞれ必要な乗り直し料金を算出し、この複数の乗り直し料金に基づいて割安ルートを判定するので、１つの有料道路区間に対して、乗り直しを行うインターチェンジの場所や乗り直しの回数が異なる複数の乗り直しルートの中から、料金面で最も有利な割安ルートを探索することができる。
【００１４】
例えば、前記ルート取得手段が取得する複数の前記乗り直しルートの中に、複数のインターチェンジで乗り直しをする乗り直しルートが含まれている場合には（請求項３）、それぞれの乗り直しによって割引適用が複数回受けられ、１つのＩＣだけで乗り直しを行う場合に比べて料金面でより有利な割安ルートとなることがある（後述の図１０参照）。
本発明の経路探索装置では、このような複数種類の乗り直しルートを走行するのにそれぞれ必要な乗り直し料金に基づいて割安ルートを判定するので、その中から料金面で最も有利な割安ルートを探索することができる。
【００１５】
上記の通り、出発地点から目的地点までの経路に含まれる１つの有料道路の途中には、乗り直し可能なインターチェンジ（ＩＣ）が１つだけの場合に限らず、複数箇所あることも考えられる。
この場合、どこの途中ＩＣで乗り直しを行うか、及び、乗り直しを何回行うかの組み合わせによって料金が異なる複数の乗り直しルートを想定することができるので、このうちのどの乗り直しルートが料金面で最も有利となるかの判定ロジックが必要になる。
【００１６】
そこで、本発明の経路探索装置において、前記ルート取得手段は、前記有料道路の途中に位置する乗り直し可能なすべてのインターチェンジの中から選択し得る１又は複数の当該インターチェンジの組み合わせに基づいて、前記有料道路に関して採り得るすべての前記乗り直しルートを総当たり的に生成し、前記算出手段は、生成されたすべての前記乗り直しルートに対してそれぞれ前記乗り直し料金を算出することが好ましい（請求項２）。
【００１７】
この場合、ルート取得手段が、有料道路に関して採り得る乗り直しルートを総当たり的に生成し、算出手段が、そのように総当たり的に生成されたすべての乗り直しルートに対してそれぞれ乗り直し料金を算出するので、例えば料金が最小となる乗り直しルートを割安ルートとして選択するという比較的簡単な判定ロジックを採用することができ、料金面で有利となる割安ルートを簡単に判定できるようになる。
【００１８】
また、上記のように、すべての乗り直しルートを総当たり的に生成し、その各乗り直しルートに対して乗り直し料金を算出するようにすれば、割引制度の適用条件の変更にも柔軟に対応できるという利点がある。
すなわち、有料道路の事業主体が、割引制度の適用条件を将来的に任意に変更することも考えられるが、総当たり的に求めた各乗り直しルートに対してそれぞれ乗り直し料金を算出し、算出されたすべての乗り直し料金に基づいて割安ルートを判定する判定ロジックを採用すれば、正しい料金を算出するために割引適用条件を更新するだけで、同じ判定ロジックで正しい割安ルートを判定することができ、割安ルートの判定ロジック自体を変更する必要がない。
【００１９】
一方、基準ルートと複数の乗り直しルートの中から少なくとも１つの割安ルートを判定する場合において、料金面で優劣がつかない複数の割安ルートが見つかる場合がある。
この場合、有料道路への乗り直しの予測時刻と実際に有料道路に乗り直した時刻との差（以下、「時刻ずれ」という。）について考えると、この時刻ずれは、乗り直し地点までの渋滞や混雑等の交通状況によって大きく変化する。そして、乗り直し地点が異なる複数の乗り直しルートを想定すると、有料道路に対する乗り直しの実行時期が遅いほど、交通状況の変動による時刻ずれが発生し易いために割引適用が受けられなくなる可能性が高くなり、逆に、乗り直しの実行時期が早いほど、交通状況の変動による時刻ずれが発生し難くいために割引適用を受けられる可能性が高くなると考えられる。
【００２０】
そこで、前記判定手段は、料金面では優劣のつかない複数の前記割安ルートが複数ある場合には、前記出発地点により近い乗り直し地点を有する当該乗り直しルートを他よりも有利なルートとして判定を優先させることが好ましい（請求項４）。
なお、料金面で優劣がつかない複数の割安ルートがある場合には、更に乗り直し回数がより少ない乗り直しルートを、他よりも有利なルートとして判定を優先させることにしてもよい。その理由は、有料道路から一旦降りて一般道路を走行し、再び有料道路に乗るという乗り直し自体が煩雑な行為なので、乗り直し回数が少ないほど、ドライバーの負担がより小さくなるからである。
【００２１】
本発明の経路探索装置において、前記ルート取得手段は、前記出発地点から前記目的地点までの経路を探索する経路探索ロジック（例えば、ダイクストラ法やポテンシャル法等）を実行可能なものを採用することができる。
もっとも、かかる経路探索ロジックを実行可能であっても、当該ルート取得手段において、その経路探索ロジックにより前記基準ルートのみを生成し、前記乗り直しルートについては前記基準ルートと同じものを援用することが好ましい（請求項５）。
【００２２】
その理由は、乗り直し地点を経由地に設定して経路探索ロジックを実行すれば、複数の乗り直しルート（有料道路からいったん外れるループ経路を含む。）を個別に生成することもできるが、このような乗り直しルートの生成のための経路探索ロジックを逐一実行すると、演算量が大きくなってユーザに対する情報提供が遅れる恐れがあるからである。
特に、前記した通り、すべての乗り直しルートの組み合わせを総当たり的に生成する場合には、乗り直し可能な途中のインターチェンジが多数ある場合には、経路探索ロジックを実行すべき乗り直しルートの数が膨大になるので、これら膨大数の乗り直しルートについて単純に経路探索ロジックを実行してしまうと、演算量が膨大になる恐れがある。
【００２３】
一方、乗り直しルートについては基準ルートと同じものを援用する場合には、そのループ経路の通行時間（すなわち、乗り直しに必要な時間）を考慮しないと、乗り直し地点以降の車両の到着予定時刻（乗り直し地点において有料道路に復帰する予定時刻を含む。）がずれてしまい、算出手段が算出する乗り直し料金に誤差が生じ、ユーザに対して誤った割安ルートの情報を提供してしまう恐れがある。
そこで、本発明の経路探索装置において、前記ルート取得手段は、前記乗り直しルートにおける乗り直し地点以降の前記車両の到着予定時刻については、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行し、前記算出手段は、時刻補正された前記到着予定時刻に基づいて前記乗り直し料金を算出することが好ましい（請求項６）。
上記「乗り直しに必要な所定時間」は、全ＩＣ共通又は各ＩＣ個別の固定時間であってもよいし、曜日や時間帯等に応じて変動させる可変の設定時間であってもよい。
【００２４】
なお、本発明において、「料金面で割安となる割安ルート」とは、必ずしも単純に最低料金のルートのだけを意味するものではなく、乗り直しに伴うタイムロスとの関係を比較考量した綜合的な判定によって定まるルートも、これに含まれる。
例えば、本発明の経路探索手段において、前記算出手段は、前記有料道路に対する乗り直しのために生じるタイムロスを料金に換算し、換算された当該料金を前記乗り直し料金の算出に反映させるようにしてもよい。
この場合、乗り直しに伴うタイムロスが料金に換算されるので、単純な料金面だけで割安ルートを選択する場合に比べて、実態に即した有意義な判定を行うことができる。
【００２５】
本発明のコンピュータプログラム（請求項７）は、本発明の経路探索装置（請求項１）が行う探索処理をコンピュータに実行させるためのコンピュータプログラムであって、当該経路探索装置（請求項１）と同様の作用効果を奏する。
また、本発明の経路探索方法（請求項８）は、本発明の経路探索装置（請求項１）が行う探索方法であって、当該経路探索装置（請求項１）と同様の作用効果を奏する。
【発明の効果】
【００２６】
以上の通り、本発明によれば、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを事前に自動的に探索することができるので、ユーザに対して経済的なルート案内を行うことができる。
【発明を実施するための最良の形態】
【００２７】
〔システムの全体構成〕
図１は、本発明の経路検索装置を有するナビゲーションシステムの全体構成を示す概略構成図であり、図２は、同システムの機能ブロック図である。
図１及び図２に示すように、本実施形態のナビゲーションシステム１は、サーバ装置２と、複数の車両３にそれぞれ搭載された車載装置４とから構成されている。
なお、本明細書において、「車両」とは、自動車、原動機付き自転車、軽車両及びトロリーバス等のことをいう。また、「車載装置」とは、車両に搭載されており、その搭乗者に対して目的地までの経路を案内するいわゆるナビゲーション装置のことをいう。
【００２８】
このナビゲーションシステム１は、予め入会登録された会員（ユーザ）の車両３自体をセンサーとして、各車両３からサーバ装置２が情報収集し、メンバー間で相互に情報提供し合って運用することにより、サーバ装置２が各会員に対して有用な交通情報を提供するようにしたものである。
従って、本システム１によれば、通常のＶＩＣＳ（登録商標：Vehicle Information and Communication System）情報とともに、このＶＩＣＳ情報に含まれていないより詳細かつ動的な交通情報を、各会員の車両３に提供することができる。
【００２９】
本システム１のサーバ装置２は、専用の通信回線を介して交通情報センタ５に接続されており、必要に応じてＶＩＣＳ情報を交通情報センタ５から入手している。また、サーバ装置２は、インターネット網６を通じて携帯電話機８の無線基地局７と双方向で通信可能である。
各車両３の車両装置４は、搭乗者の携帯端末である携帯電話機８を介して、無線基地局７と双方向で通信可能であり、無線基地局７は上記インターネット網８に接続されている。このため、各車両３の車両装置４は、ほぼリアルタイムでサーバ装置２に対して情報を送受信可能となっている。
【００３０】
各車両３の車載装置４は、ＧＰＳ（Global Positioning System ）アンテナと、ＧＰＳ受信機と、道路地図データベースと、入力デバイスと、ディスプレイ及びスピーカ等よりなる出力装置とを備えており、ＧＰＳ受信機で検出した現在位置をディスプレイの画面上に表示できるようになっている。
また、車載装置４は、入力デバイスで入力された所定の旅行条件に基づいて、旅行ルートを演算可能なルート演算装置（図示せず）を備えている。
【００３１】
車載装置４に入力可能な旅行条件としては、出発地点（現在地点を含む。）や目的地点のほか、経由地や優先経路（ 一般道路優先又は有料道路優先や、距離優先又は道幅優先）等がある。ルート演算装置のメモリには、入力される情報や自身で演算した旅行ルートに加えて、サーバ装置２から提供されたルート探索情報を保存することもできる。
なお、本実施形態の車載装置４は、ＥＴＣ対応であり、有料道路の料金所等に設置されたＥＴＣ路側処理装置と無線による路車間通信を行うことができる。
【００３２】
〔サーバ装置の内部構成〕
図２に示すように、サーバ装置２は、ワークステーション等よりなる処理コンピュータ１１と、この処理コンピュータ１２に接続された通信インターフェースよりなる第１及び第２通信部１２，１３と、各種データベース１４〜１６とから構成されている。
第１通信部１２は、専用回線で交通情報センタ５に接続されている。また、第２通信部１３は、インターネット網６を介して前記無線基地局７に接続され、この無線基地局７と車両３の搭乗者の携帯電話機８との間の無線通信を通じて、車載装置４との間で情報の送受信を行う。
【００３３】
各データベース１４〜１６のうち、会員データベース１４には、当該システム１に参加する登録会員の識別情報が保存されている。処理コンピュータ１１は、会員データベース１４に記録されている特定の登録会員から受信した入力情報（出発地点及び目的地点等）に基づいて、後述する割安ルートの経路探索処理を実行する。
交通情報データベース１５には、第１通信部１２が受信した交通情報センタ５からのＶＩＣＳ情報が保存される。このＶＩＣＳ情報は、処理コンピュータ１１がセンタ５からのＶＩＣＳ情報を抽出するごとに更新され、ほぼ最新の情報が保持される。
【００３４】
また、交通情報データベース１５には、特定の登録会員から受信したリンク番号、リンク進入時刻、リンク退出時刻、リンク旅行時間等よりなる交通情報も保存される。
この場合、車載装置４は、所定時間毎（例えば、０．１秒毎）又は所定距離毎（例えば、５ｍ毎）に位置を検出しており、各リンクについて、検出位置がリンクの始端の位置を通過（一致）した時刻をリンク進入時刻とし、検出位置がリンクの終端の位置を通過（一致）した時刻をリンク退出時刻とし、リンク退出時刻とリンク進入時刻との差をリンク旅行時間として算出する。
【００３５】
更に、交通情報データベース１５には、ＥＴＣ割引に代表される有料道路の割引情報１７が含まれている。
この割引情報１７は、例えばＮＥＸＣＯが公表している各ＩＣ間の通行料金テーブルよりなり、この通行料金テーブルは、深夜割引、通勤割引及び早朝夜間割等の割引制度ごとに定められた複数のテーブルよりなる。なお、この割引情報１７の基礎となる各種ＥＴＣ割引の詳細については後述する。
【００３６】
地図データベース１６には道路地図データが記録されており、この道路地図データには交差点データとリンクデータとが含まれている。
交差点データは、交差点ＩＤと交差点位置とを対応付けたデータである。また、リンクデータは、特定リンクのリンクＩＤに対して、特定リンクの始点・終点・補間点の位置、特定リンクの始点に接続するリンクＩＤ、特定リンクの終点に接続するリンクＩＤ、及び、特定リンクのリンクコストを対応付けたデータよりなる。
【００３７】
リンクコストは、例えば、特定リンクとその終点に接続するリンクの組み合わせの数だけ用意されており、特定リンクの始点に進入してから当該特定リンクの終点を退出し、次に接続するリンクの始点に進入するまでに要する時間として設定されている。
すなわち、リンクコストには、特定リンクの始点から終点までを走行するのに要するコスト（時間）と、その特定リンクの終点から次のリンクの始点までを走行するのに要するコスト（時間）、つまり、交差点通過に要するコストが含まれている。
【００３８】
リンクコストは、平日、土曜、日曜及び祝日といった日種別ごとに、現時点から１日先までの５分毎のデータ（すなわち、現時点のリンクコスト、５分先のリンクコスト、１０分先のリンクコスト、… …、２３時間５５分先のリンクコスト、２４時間先のリンクコスト）が用意されており、これらのデータは、交通情報データベース１５のＶＩＣＳ情報や、特定会員から受信した交通情報に基づいて作成される。
【００３９】
また、地図データベース１６には、地図上の各道路が一般道路か有料道路かの区別情報と、有料道路のインターチェンジ（ＩＣ）の位置情報と、当該ＩＣが乗り直し可能か否かを判断するための種別情報が含まれている。図４は、有料道路のインターチェンジの種別を示す説明図である。
図４に示すように、有料道路のインターチェンジには、「入口のみ」のＩＣと、「出口のみ」のＩＣと、同じ場所に同方向の入口と出口の両方がある「両方あり」のＩＣと、同じ場所に入口と出口があるがその方向が異なる「異方向の出入口」のＩＣとがある。
【００４０】
このうち、「両方あり」のＩＣのみが乗り直し可能なＩＣ（以下、乗り直しＩＣということがある。）として記憶され、「入口のみ」のＩＣ、「出口のみ」のＩＣ及び「異方向の出入口」のＩＣは、乗り直し不能なＩＣとして記憶されている。
なお、本明細書において、「乗り直し」とは、車両３が有料道路を途中のＩＣで降り、その降りたＩＣで当該有料道路に再び復帰することを意味する。
【００４１】
〔処理コンピュータの構成及び機能〕
処理コンピュータ１１は、ＨＤＤやメモリ等よりなる記憶装置と、この記憶装置から各種のコンピュータプログラムを読み出して実行する演算装置とを含んでいる。
上記各コンピュータプログラムのうちの１つは、車両３が有料道路を含む経路を走行する場合の割安ルートを探索する処理を行うものであり、この探索処理用のプログラムの機能定義として、ルート取得手段１８、算出手段１９及び判定手段２０を含んでいる。
【００４２】
このうち、ルート取得手段１８は、出発地点から目的地点までの最小のリンクコストとなる最適経路を探索する、例えば、ダイクストラ法又はポテンシャル法を利用した経路探索ロジックを実行可能である。
例えば、ルート取得手段１８は、各リンクへの進入予測時刻を算出し、その進入予測時刻に該当するリンクコストを用いて経路を探索する。具体的には、出発地点が含まれるリンク（出発リンク）の現時点のリンクコストを用いて、出発リンクの退出予測時刻を算出する。
【００４３】
これがそのまま出発リンクに接続するリンク（一次接続リンク）の進入予測時刻となるため、一次接続リンクについては、この進入予測時刻に該当する時点のリンクコストを用いる（例えば、一次接続リンクの進入予測時刻が５分先までなら現時点のリンクコストを用い、一次接続リンクの進入予測時刻が５分先以上１０分先までなら５分先のリンクコストを用いる）。
【００４４】
そして、このリンクコストを用いて、一次接続リンクの退出予測時刻を算出する。これがそのまま一次接続リンクに接続するリンク（二次接続リンク）の進入予測時刻となるため、二次接続リンクについては、この進入予測時刻に該当する時点のリンクコストを用いる。以降、同様にこれを繰り返す。
また、ルート取得手段１８は、上記経路探索ロジックで得られた最適経路に有料道路が含まれている場合には、以下の（ａ）及び（ｂ）でそれぞれ定義される「第１ルート群」と「第２ルート群」を生成する、ルート生成処理を行う。
【００４５】
（ａ） 第１ルート群（予定時刻ルート）
第１ルート群は、次の「基準ルート」と「乗り直しルート」とからなる。
「基準ルート」：最適経路に含まれる有料道路を、途中のＩＣで乗り直しを行わないでそのまま走行するルート。
「乗り直しルート」：有料道路の途中にある乗り直しＩＣで乗り直しを行うルート。１つの有料道路区間の中に乗り直しＩＣが複数ある場合には、乗り直しＩＣの数と場所が異なるすべての組み合わせからなる。
【００４６】
なお、第１ルート群の基準ルートと乗り直しルートは、有料道路への流入を予定時刻通りに行うものであり、流入時刻を敢えてずらす後述の第２ルート群を構成する「仮想時刻ルート」と対比して、「予定時刻ルート」と呼ぶ。
（ｂ） 第２ルート群
第２ルート群は、次の「仮想時刻ルート」からなる。
「仮想時刻ルート」：「基準ルート」及び「乗り直しルート」のそれぞれについて、予定時刻から所定時間（例えば、３０分）内に含まれる範囲で、予定時刻から敢えて一定の時間間隔（例えば、１０分）ずつずらした仮想時刻に、有料道路に流入するルート。
【００４７】
なお、上記第２ルート群の定義において、「予定時刻」とは、車両３が現在時刻に出発地点を出発して目的地点に向かって経路に沿って走行した場合に、その車両３が有料道路の各ＩＣに流入する時刻のことを意味する。従って、例えば、予定時刻から１０分ずらした仮想時刻ルートは、有料道路の各ＩＣに対応するリンクへの流入予測時刻をそれぞれ１０分ずつずらして生成される。
【００４８】
算出手段１９は、有料道路の割引情報１７と車両３がＩＣに到達する予定時刻又は仮想時刻に基づいて、第１及び第２ルート群に含まれる各ルートを走行するのに必要な料金を算出する。
すなわち、第１ルート群の場合は、車両３が基準ルートを予定時刻通りに走行するのに必要な、予定時刻での「基準料金」と、各乗り直しルートを予定時刻通りに走行するのに必要な、予定時刻での「乗り直し料金」とがそれぞれ算出される（予定時刻料金）。
【００４９】
また、第２ルート群の場合は、車両３が基準ルートを予定時刻からずれた仮想時刻に走行するのに必要な、仮想時刻の「基準料金」と、各乗り直しルートを予定時刻からずれた仮想時刻に走行するのに必要な、仮想時刻の「乗り直し料金」とがそれぞれ算出される（仮想時刻料金）。
そして、判定手段２０は、算出手段１９で算出された上記各料金に基づいて、第１ルート群（予定時刻ルート）について最も安価なルートを判定し、かつ、第２ルート群に属する時間ずらし量が異なる各仮想時刻ルートについてもそれぞれ最も安価なルートを判定する。
【００５０】
すなわち、判定手段２０は、次の１）〜４）に示す各ルートを、それぞれ割安ルートと判定する。
１） 予定時刻通りの基準ルートとすべての乗り直しルート（予定時刻ルート）の中で最も安価なルート
２） 有料道路への流入を１０分遅らせた仮想時刻の基準ルートとすべての乗り直しルート（第１の仮想時刻ルート）の中で最も安価なルート
３） 有料道路への流入を２０分遅らせた仮想時刻の基準ルートとすべての乗り直しルート（第２の仮想時刻ルート）の中で最も安価なルート
４） 有料道路への流入を３０分遅らせた仮想時刻の基準ルートとすべての乗り直しルート（第３の仮想時刻ルート）の中で最も安価なルート
【００５１】
〔経路探索処理のフローチャート〕
図３は、本システム１を利用した割安ルートの経路探索処理を示すフローチャートである。
図３に示すように、まず、車両３の搭乗者が車載装置４に対して出発地点と目的地点の設定を行う（ステップＳ１）。この場合、出発地点の設定がない場合には、車両３の現在位置が出発地点となる。
【００５２】
上記出発地点と目的地点は、携帯電話機８を通じてサーバ装置２に送信され、処理コンピュータ１１によって経路探索処理が行われる。
サーバ装置２の処理コンピュータ１１は、設定された出発地点と目的地点とからリンクコストが最小となる最適経路を探索し、この最適経路に有料道路が含まれている場合に、前記第１及び第２ルート群を生成する（ステップＳ２）。
その後、処理コンピュータ１１は、生成された第１及び第２ルート群に含まれる各ルートについてのすべての料金を算出し（ステップＳ３）、第１ルート群（予定時刻ルート）の中から値段が最小となる割安ルートを判定するとともに、第２ルート群に属する時間ずらし量が異なる各仮想時刻ルートについても値段が最小となる割安ルートを判定する（ステップＳ４）。
【００５３】
そして、処理コンピュータ１１は、第１及び第２ルート群についての各割安ルートを、通信部１３を通じて車載装置４に送信する（ステップＳ５）。
車載装置４は、サーバ装置２から上記割安ルートを受信すると、ディスプレイやスピーカ等の出力装置を介して、有料道路を含む最適経路とこの経路に関連する割安ルートの内容を搭乗者に提供する（ステップＳ６）。
なお、搭乗者に提供する最適経路及び割安ルートの内容に関する情報としては、例えば次のものを含めることができる。
【００５４】
ア） 出発地点から目的地点までの走行経路
イ） 通行料金（通常料金と割引料金）
ウ） 入口ＩＣの名称、出口ＩＣの名称及び乗り直しＩＣの名称
エ） 走行時間（乗り直しに必要な調整時間を含む。）
オ） 今回の走行で適用され得る割引制度の適用条件（時間帯条件や走行距離条件）
カ） 割引制度を受けるために必要な調整時間（待ち時間）
【００５５】
上記の情報提供を受けた車両３の搭乗者は、自身の判断で割安ルートを選択するか否かを判断する（ステップＳ７）。そして、仮に割安ルートを選択した場合には、車両３がその割安ルートに沿って走行し、目的地に到着することになる（ステップＳ８）。
なお、割安ルートが選択されるか否かは、搭乗者自身がその時の価値判断で任意に決定するものであり、料金面よりも時間短縮が優先される場合には、通常の最適経路が選択される場合もあり得る。
【００５６】
〔有料道路の割引制度〕
次に、割引情報１７の基礎となる有料道路の割引制度の内容について説明する。
なお、ここでは、ＮＥＸＣＯが実施しているＥＴＣシステムを利用する車両３に対する高速道路の通行料金の割引制度について説明する。
ただし、これはあくまでも割引制度の一例であって、ここに示す割引制度自体も随時変更される可能性がある。また、ＮＥＸＣＯ以外の事業主体が管理する有料道路でも、割引制度が新たに実施される可能性もある。
【００５７】
図９は、ＮＥＸＣＯが実施する各種ＥＴＣ割引の内容を示す説明図である。
図９（ａ）の深夜割引は、午前０時から午前４時までの間に、車両３が対象区間の入口ＩＣから出口ＩＣを走行した場合に適用されるもので、割引率は３０％である。
図９（ｂ）の通勤割引は、午前６時から午前９時までの間に、車両３が対象区間の入口ＩＣ又は出口ＩＣを通過した場合、或いは、午後５時から午後８時までの間に、車両３が対象区間の入口ＩＣ又は出口ＩＣを通過した場合に適用されるもので、割引率は５０％である。
【００５８】
ただし、この通勤割引の場合には、入口ＩＣから出口ＩＣまでの１回の走行距離が１００ｋｍ以内であること、大都市近郊区間は適用外であること、及び、同日の午前と午後にそれぞれ１回だけ適用可能であるという制限がある。
なお、大都市近郊区間としては、例えば、大阪地区では、名神高速の大津と西宮の間、中国道の中国吹田と西宮北の間、近畿道の吹田と松原の間、阪和道の松原と岸和田和泉の間、西名阪道の天理と松原の間、京滋バイパスの瀬田東と久御山淀の間等がある。
【００５９】
図９（ｃ）の早朝夜間割引は、午後１０時から翌日午前６時までの間に、車両３が対象区間の入口ＩＣ又は出口ＩＣを通過した場合に適用されるもので、割引率は５０％である。ただし、この早朝夜間割引の場合には、大都市近郊区間内を少なくとも１区間走行し、１回の走行距離が１００ｋｍ以内であるという制限がある。
図９（ｄ）の特定区間割引は、車両３が、予め設定された特定の入口ＩＣから流入し、予め設定された特定の出口ＩＣから流出した場合に適用されるもので、割引率は時期によって種々に設定される。
【００６０】
〔割安ルートの経路探索処理〕
以下、図５〜図８を参照しつつ、前記処理コンピュータ１１が行う割安ルートの経路探索処理を、より具体的に説明する。
【００６１】
〔第１ルート群を用いた割安ルート探索：第１探索処理〕
図５は、ルート取得手段１８が生成する第１ルート群の一例を示す説明図である。
図５において、最適経路に含まれる有料道路区間の長さは２００ｋｍであるとし、その区間の入口ＩＣと出口ＩＣの間に、乗り直し可能な３つの途中ＩＣが含まれているものとする。この図５に示す矢印Ｒは、各ＩＣで乗り直しを実行するループ経路を示している。
また、隣り合うＩＣ間の距離は５０ｋｍであり、乗り直しによる有料道路区間の最大分割数は３に設定されているものとする。なお、最大乗り直し回数（乗り直しできる回数の最大値）は「最大分割数−１」となる。
【００６２】
ここで、図５のルート（０）は、最適経路の経路検索ロジックを行った結果の１つであり、このルート（０）では、有料道路区間の途中ＩＣはすべて素通りし、入口ＩＣから出口ＩＣまでノンストップで走行する。従って、このルート（０）は基準ルートである。
一方、図５のルート（１）〜（６）は、有料道路区間の途中ＩＣで乗り直しを行う各乗り直しルートを示し、図５において、ハッチング部分が走行距離条件に適合する分割区間を示している。
【００６３】
このうち、ルート（１）〜（３）は、乗り直し回数が１回（分割区間数が２）の場合であり、ルート（１）では、最初の途中ＩＣで乗り直しを行い、ルート（２）では２番目の途中ＩＣで乗り直しを行い、ルート（３）では３番目の途中ＩＣで乗り直しを行うものとする。
また、図５のルート（４）〜（６）は、乗り直し回数が２回（分割区間数が３）の場合であり、ルート（４）では、最初と２番目の途中ＩＣで乗り直しを行い、ルート（５）では最初と３番目の途中ＩＣで乗り直しを行い、ルート（６）では２番目と３番目の途中ＩＣで乗り直しを行うものとする。
【００６４】
そして、有料道路区間の全区間に対して、通勤割引の時間帯条件を満たしていると仮定すると、ルート（０）〜（６）の各料金は、それぞれ図５の右側に列挙した各ブロックに示す通りとなる。
例えば、ルート（０）では、通勤割引の走行距離条件（１００ｋｍ以内）を充足していないので、すべての分割区間で割引がなく、料金が４７００円となっている。
【００６５】
また、ルート（１）では、最初の分割区間（５０ｋｍ）で割引適用があり、それ以降の分割区間（１５０ｋｍ）で割引適用がなく、料金が４４５０円となっている。
更に、ルート（２）では、最初の分割区間（１００ｋｍ）と次の分割区間（１００ｋｍ）の双方で割引適用があり、料金が４１５０円となっている。
ルート（３）では、最初の分割区間（１５０ｋｍ）では割引適用がなく、それ以降の分割期間（５０ｋｍ）で割引適用があり、料金が４４５０円となっている。
【００６６】
以下、同様に、ルート（４）〜（６）では、それぞれ料金が４９５０円、４９５０円及び４３００円となる。
これらを綜合すると、ルート（２）の料金（＝４１５０円）が最も安価であることが判明する。
【００６７】
なお、ルート取得手段１８が生成する乗り直しルートの総数Ｎを一般化すると、次のようになる。
すなわち、１つの有料道路区間に含まれる全ＩＣの総数（全乗り直しＩＣに入口ＩＣと出口ＩＣを加えた総数）をｎ、乗り直しによってその有料道路区間を分割する際の最大分割数をｍとすると、ルート取得手段１８が生成する乗り直しルートの総数Ｎは、Ｎ＝n-2Ｃ1＋n-2Ｃ2＋……＋n-2Ｃm-1となる。
なお、上記総数Ｎの算出式において、コンビネーション「Ｃ」の左添え字が「ｎ−２」となっているのは、有料道路区間の両端のＩＣでは乗り直しができないからであり、コンビネーション「Ｃ」の右添え字「ｍ−１」は最大乗り直し回数に該当する。
【００６８】
このように、ルート取得手段１８は、有料道路区間の途中に位置するすべての乗り直しＩＣの中から選択し得る１又は複数のＩＣの組み合わせに基づいて、１つの有料道路区間に関して採り得る乗り直しルートを総当たり的に生成する。
そして、この各乗り直しルートに基づく乗り直し料金は、上記の通り、有料道路を途中で降りて敢えて乗り直したことが原因で、有料道路の割引制度が適用され、基準料金（基準ルートを走行する場合の料金）よりも割安になっている場合がある。
【００６９】
そこで、本実施形態の処理コンピュータ１１では、算出手段１９によって基準ルートとすべての乗り直しルートに対応する料金をすべて算出し、これらの各料金の中で最小の料金となるものを、判定手段２０が割安ルートとして判定するようになっている。
このため、本実施形態の処理コンピュータ１１によれば、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを自動的に探索することができる。
【００７０】
〔複数の乗り直し料金を対比する場合の効果〕
図１０は、複数の乗り直し料金を対比する場合の効果を示すための説明図である。
図１０において、有料道路の入口ＩＣと出口ＩＣの間に乗り直し可能なＩＣ１〜ＩＣ４が含まれており、このうち、入口ＩＣとＩＣ１とが大都市近郊エリアの中にあり、それ以外は大都市近郊エリアから外れているものと仮定する。
【００７１】
また、ここでは前記早朝夜間割引を想定し、この割引の適用条件のうち、時間帯条件についてはＩＣ１〜ＩＣ３でクリア可能であり、１回の走行距離が１００ｋｍ以内という走行距離条件と、大都市近郊区間内を少なくとも１区間走行するという走行区間条件が問題になるものとする。
この場合、例えば、早朝夜間割引の走行距離条件だけを考慮し、料金面で有利となる１つの乗り直しルートを考えると、１００ｋｍ以内の範囲で出来るだけ長い走行距離で乗り直しを行うことが料金面で有利となるので、図１０のルートＢに示すように、大都市近郊エリアを外れたＩＣ２（入口ＩＣから９０ｋｍ）で乗り直すルートを採用すればよい。
【００７２】
しかし、早朝夜間割引の場合には、大都市近郊エリアを少なくとも１区間走行すればよいので、そのエリア内に含まれるＩＣ１でいったん乗り直しを行えば、このＩＣ１の前後双方の区間が早朝夜間割引の対象区間になる。
そこで、図１０のルートＡのように、大都市近郊エリアを外れる直前のＩＣ１（入口ＩＣから３０ｋｍ）で１回乗り直しを行い、更に、ＩＣ１から９０ｋｍ離れたＩＣ３でもう一度乗り直しを行うようにすれば、合計１２０ｋｍ（＝３０ｋｍ＋９０ｋｍ）の走行距離に渡って早朝夜間割引を受けられ、乗り直しが１回の前記ルートＢよりも割安になる。
【００７３】
しかし、単一の適用条件（この場合は、走行距離条件）のみを想定してルートＢを導き出すのは比較的容易であるが、複数の適用条件（この場合は、走行距離条件と走行区間条件）のすべてを想定してルートＡを導き出すのは困難である。
すなわち、複数の割引の適用条件を考慮して、想定し得るすべての乗り直しルートの中からルートＡのような最も料金が安くなるルートを直接的に導き出す判定ロジックを規定するのは非常に難しいし、また、そのような判定ロジックを規定できたとしても、割引の適用条件自体が変更されるたびに当該ロジックを変更する必要があるので、その後のメンテナンスが煩雑になる。
【００７４】
この点、本実施形態の処理コンピュータ１１によれば、１つの乗り直しルートだけでなく複数の乗り直しルートを生成するとともに、これらを走行するのにそれぞれ必要な乗り直し料金を算出し、この複数の乗り直し料金に基づいて割安ルートを判定するので、例えば図１０のルートＡ及びＢのような、１つの有料道路区間に対して、乗り直しを行うＩＣの場所や乗り直しの回数が異なる複数の乗り直しルートの中から、最も有利な割安ルートを自動的に探索することができる。
【００７５】
また、本実施形態の処理コンピュータ１１によれば、採り得る乗り直しルートを総当たり的に生成し、生成されたすべての乗り直しルートに対してそれぞれ乗り直し料金を算出するので、算出された各乗り直し料金の中から最小料金を選択するという、簡単な判定ロジックで割安ルートを判定できるとともに、制度の適用条件の変更に対して柔軟に対応できるという利点もある。
【００７６】
すなわち、前記した割引制度の適用条件は任意に変更される可能性があるが、本実施形態では、総当たり的に求めた各乗り直しルートに関してそれぞれ乗り直し料金を算出し、このすべての乗り直し料金に基づいて割安ルートを判定する判定ロジックを採用しているので、仮に割引制度の適用条件が変更されても、交通情報データベース１５に記録された割引情報１７の内容を更新するだけで、変更後の適用条件下での正しい乗り直し料金を算出することができる。
従って、割安ルートの判定ロジック（想定し得るすべての乗り直しルートの中から最低料金のルートを選択するロジック）自体を変更する必要がなく、割引制度の適用条件の変更に対して柔軟に対応することができる。
【００７７】
〔時刻補正処理〕
ところで、前記した通り、本実施形態の処理コンピュータ１１では、ルート取得手段１８が最適経路を演算する経路探索ロジックを実行可能になっており、乗り直し地点を経由地に設定して経路探索ロジックを実行すれば、複数の乗り直しルート（ループ経路Ｒを含む。）を個別に生成することも可能である。しかし、基準ルート以外のすべての乗り直しルートについても経路探索ロジックを実行すると、演算量が大きくなってユーザに対する情報提供が遅れる恐れがある。
【００７８】
特に、本実施形態では、１つの有料道路区間に対して乗り直しルートの組み合わせを総当たり的に生成することから、乗り直し可能な途中のインターチェンジが多数ある場合には、経路探索ロジックを実行すべき乗り直しルートの数が膨大になる可能性があるので、これら膨大数の乗り直しルートについても単純に経路探索ロジックを実行してしまうと、演算量が膨大となってしまう。
【００７９】
そこで、本実施形態の処理コンピュータ１１では、ルート取得手段１８は、基準ルートを決定する場合にのみ経路探索ロジックを実行するようになっている。
すなわち、ルート取得手段１８は、経路探索ロジックにより基準ルートのみを生成し、基準ルートに対応する乗り直しルートについては、基準ルートと同じものを援用することによって経路探索ロジックを実行しないようになっており、これにより、割安ルートの判定のために乗り直しルートを生成するに当たり、演算量が不必要に増大するのを未然に防止している。
【００８０】
もっとも、乗り直しルートトに関して経路探索ロジックを実行しない場合には、そのループ経路Ｒの通行時間（乗り直しに要する走行時間）を考慮しないと、乗り直しＩＣ以降の車両３のループ経路Ｒの通行時間分だけ、各ＩＣへの到着予定時刻がずれてしまい、算出手段１９が算出する乗り直し料金に誤差が生じることがあり、このため、ユーザに対して誤った割安ルートの情報を提供してしまう恐れがある。
【００８１】
そこで、本実施形態では、ルート取得手段１８が、乗り直しルートにおける乗り直しＩＣ以降の各ＩＣへの車両３の到着予定時刻（乗り直し地点において有料道路に復帰する予定時刻を含む。）については、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行し、算出手段１９が、時刻補正された到着予定時刻に基づいて乗り直し料金を算出するようになっている。
図６は、上記時刻補正処理の内容を示す説明図である。
図６において、ＩＣ（Ａ）〜ＩＣ（Ｃ）は有料道路の各インターチェンジを示し、ＩＣ（Ｂ）が乗り直しを行うインターチェンジであるとする。
【００８２】
図６（ａ）は、時刻補正を行わない場合に車両３が各ＩＣ（Ａ）〜ＩＣ（Ｃ）に到着する到着予定時刻を示しており、図例では、ＩＣ（Ａ）の到着予定時刻が１３：５０、ＩＣ（Ｂ）の到着予定時刻が１５：３０、ＩＣ（Ｃ）の到着予定時刻が１６：５０になっている。この場合、車両３がＩＣ（Ｂ）において乗り直しを行うとすると、ＩＣ（Ｂ）の出発予定時刻はその到着予定時刻よりも遅くなっている筈である。
従って、図６（ａ）に示すように、ＩＣ（Ｂ）で乗り直しに要する時間を考慮しない場合には、ＩＣ（Ｃ）の到着予想時刻が１６：５０になり、例えば、ＩＣ（Ｃ）において午後の通勤割引が適用されない。
【００８３】
そこで、図６（ｂ）に示すように、本実施形態の処理コンピュータ１１では、各乗り直しＩＣごとに乗り直しに必要な調整時間（図例では、ＩＣ（Ｂ）について２０分）を予め設定してあり、その調整時間を記憶装置に記憶している。なお、この乗り直しに必要な調整時間は、乗り直し可能な全ＩＣに共通の固定時間であってもよいし、曜日や時間帯等に応じて変動する可変の設定時間であってもよい。
【００８４】
そして、ルート取得手段１８は、車両３がＩＣ（Ｂ）において乗り直しを行う場合には、車両３がＩＣ（Ｂ）をいったん降りる予定時刻にＩＣ（Ｂ）用の調整時間を加算して車両３が当該ＩＣ（Ｂ）に復帰する予定時刻を算出し、ＩＣ（Ｂ）以後の到着予定時刻を補正している。
この場合、車両３のＩＣ（Ｂ）の到着予定時刻（ＩＣ（Ｂ）に復帰する予定時刻）は１５：５０になり、ＩＣ（Ｃ）の到着予定時刻は１７：１０になるので、ＩＣ（Ｃ）において通勤割引が適用可能となる。
【００８５】
〔判定手段での候補選出の優先順位〕
ところで、判定手段２０は、基準ルートと乗り直しルートの中から最低料金の割安ルートを判定するが、この場合において、料金面だけでは優劣がつかない複数の割安ルートが見つかる場合がある。
そこで、本実施形態の判定手段２０は、次の優先順位で割安ルートの判定を行うようになっている。
【００８６】
（１） 最初は最も料金の安いものを優先する。
（２） 次に、同じ料金のルートが複数ある場合には、分割区間数（または乗り直し回数）がより少ない方を優先する。
（３） 更に、料金と分割区間数（または乗り直し回数）が同じ場合には、出発地点により近い乗り直し地点を有する乗り直しルートを他よりも有利なルートとして優先する。
【００８７】
上記の優先順位（２）において、分割区間数（または乗り直し回数）がより少ない方を優先することとしたのは、有料道路から一旦降りて一般道路を走行し、再び有料道路に乗るという乗り直し自体が煩雑な行為であることから、この数が少ないほど、ドライバーの負担がより小さくなるからである。
また、上記の優先順位（３）において、出発地点により近いものを優先することとしたのは、乗り直し地点が異なる複数の乗り直しルートを想定すると、有料道路に対する乗り直しの実行時期が遅いほど、交通状況の変動による乗り直し地点における時刻ずれ（有料道路への乗り直しの予測時刻と実際に有料道路に乗り直した時刻との差）が発生し易いために割引適用が受けられなくなる可能性が高くなり、逆に、乗り直しの実行時期が早いほど、交通状況の変動による時刻ずれが発生し難くいために割引適用を受けられる可能性が高くなると考えられるからである。
【００８８】
〔タイムロスの時間換算〕
本実施形態の算出手段１９において、有料道路に対する乗り直しのために生じるタイムロスを料金に換算し、換算された当該料金を乗り直し料金の算出に反映させるようにしてもよい。
例えば、乗り直しに伴う遅れ時間による換算料金を、１分ごとに５０円とする補正用の換算料金を設定した場合、あるＩＣでの乗り直しに要する走行時間が１０分であるとすると、５００円の補正料金を加算する。
【００８９】
このようにすれば、乗り直しに伴うタイムロスが料金に換算されて乗り直し料金に反映されるので、単純な料金面だけで割安ルートを選択する場合に比べて、実態に即した有意義な判定を行うことができる。
【００９０】
〔第２ルート群を用いた割安ルート探索：第２探索処理〕
図７は、ルート取得手段１８が生成する第２ルート群の一例を示す説明図である。
図７において、ルート（ｔ０）は、有料道路への流入を予定時刻通りに行う予定時刻ルート、すなわち、車両３が現在時刻に出発地点を出て最適経路に沿って走行した場合の予定時刻に、車両３が有料道路に流入するルートを示し、図７に例示するルート（ｔ０）は、第１ルート群に含まれる「乗り直しルート」のうちの１つである。
【００９１】
これに対して、ルート（ｔ１）とルート（ｔ２）は、予定時刻から所定時間（例えば、３０分）内に含まれる範囲において、有料道路への流入を予定時刻から一定の時間間隔（例えば、１０分）ずつずらした前記仮想時刻ルートを示している。
そして、ルート（ｔ１）は、有料道路に対する流入時刻を予定時刻から１０分遅らせた第１の仮想時刻ルートを示し、ルート（ｔ２）は、有料道路に対する流入時刻を予定時刻から２０分遅らせた第２の仮想時刻ルートを示している。
【００９２】
図７の例では、ルート（ｔ０）とルート（ｔ１）の場合には、午後の通勤割引の時間帯条件（午後５時〜８時にＩＣ通過）に適合せず、ＩＣ（Ｃ）における通勤割引の適用がないが、ルート（ｔ２）の場合には、到着予定時刻が１７：０５になって、午後の通勤割引の時間帯条件に適合し、割引適用の対象となる。
そこで、本実施形態の処理コンピュータ１１は、基準ルートと乗り直しルートとからなる前記第１ルート群（予定時刻ルート）を用いた割安ルート探索（第１探索処理）に加えて、更に、前記仮想時刻ルートからなる第２ルート群を用いた割安ルート探索（第２探索処理）を実行する。
【００９３】
すなわち、処理コンピュータ１１のルート取得手段１８は、第１ルート群に含まれる基準ルートと各乗り直しルート（予定時刻ルート）のそれぞれについて、有料道路への流入する予定時刻を敢えて一定の時間間隔（１０分間）だけ遅らせた上記仮想時間ルートを、予定時刻から所定時間（例えば、３０分）内に含まれる範囲において、総当たり的に生成する。
そして、この仮想時刻ルートに基づく仮想時刻料金は、上記の通り、有料道路に対する流入時刻を敢えて遅らせたことが原因で、途中のＩＣ（Ｃ）で有料道路の割引制度が適用され、予定時刻料金（予定時刻ルートを走行する場合の料金）よりも割安になっている場合がある。
【００９４】
そこで、本実施形態の処理コンピュータ１１では、算出手段１９が、予定時刻における基準ルートや乗り直しルート（予定時刻ルート）の通行に必要な料金（予定時刻料金）に加えて、仮想時刻における基準ルートや乗り直しルート（仮想時刻ルート）の通行に必要な料金（仮想時刻料金）も算出し、判定手段２０は、その仮想時刻ルートの中からも、最も安価となるルート（基準ルートの場合もあり得る。）を判定して、これを料金面で割安な割安ルートと判定する。
【００９５】
そして、上記各割安ルートとその通行に必要な料金（割安料金）関する情報は、この情報の出力手段としての前記第２通信部１３等を通じて車載装置４に送信される。
このため、上記情報を受けた車両３の搭乗者（ユーザ）は、予定時刻ルートの中の割安ルートとその料金、１０分ずらした第１の仮想時刻ルートの中の割安ルートとその料金、２０分ずらした第２の仮想時刻ルートの中の割安ルートとその料金、及び、３０分ずらした第３の仮想時刻ルートの中の割安ルートとその料金のそれぞれを、参照することができる。従って、車両３の搭乗者は、これらの割安ルートの中で出発時刻の遅れと料金とを比較検討し、自身が最も適切だと判断したルートを選択することができる。
【００９６】
また、本実施形態では、所定時間（例えば、３０分）の範囲内で総当たり的に求めた各仮想時刻ルートに関してそれぞれ仮想時刻料金を算出し、このすべての仮想時刻料金に基づいて割安ルートを判定する判定ロジックを採用しているので、最適経路に割引率の異なる路線が含まれている場合でも、料金面で有利な割安ルートを正確かつ効率的に探索できるという優れた効果がある。
【００９７】
〔第２探索処理の効果〕
図８は、上記第２探索処理の効果を示すための説明図である。
図８に示す例では、１つの経路に割引条件の異なる路線１と路線２が隣接していると仮定し、その割引条件が例えば次のように定められているものとする。
【００９８】
（路線１の割引条件）
１１：００〜１２：００の間に路線１のＩＣに入るか、路線１のＩＣから出ると料金が３０％割引となる。
（路線２の割引条件）
１２：００〜１３：００の間に路線２のＩＣに入るか、路線２のＩＣから出ると料金が５０％割引となる。
【００９９】
この場合、例えば仮に、路線１の割引条件だけに着目して到着時刻の時間調整を行うとすると、図８のルート（１）の場合には、路線１への入場時刻が間に合わず、路線１で通常料金となってしまうので、路線１への入場時刻を１０分だけ遅らせたルート（２）を採用するのが有利であるということになる。
しかし、ルート（２）を採用すると、路線１については割引料金となるが、その下流側の路線２については、通常料金になってしまう。
【０１００】
この場合、路線１と路線２の走行距離が同じであるとすれば、路線２の方が路線１よりも割引料金が大きいため、却ってトータルの通行料金は高くなってしまうことになる。
また、仮に、各路線１及び２の割引条件をそれぞれ満たすような時間調整を行うことを想定した場合、路線１と路線２においてともに割引適用を受けるようにするには、路線２への入場時刻を翌日まで遅らせなければならず、路線１の退場時刻と路線２の入場時刻の間がほぼ丸１日空いてしまい、非現実的なルートになってしまう。
【０１０１】
これに対して、本実施形態の処理コンピュータ１１では、予定時刻ルートとこれから一定時間間隔（１０分間）でずらした仮想時刻ルートを生成し、これらの各ルートについて算出したすべての予定時刻料金及び仮想時刻料金を出力してユーザに提示することができるので、図８のような、割引条件が異なる路線１，２が含まれている場合でも、ユーザは最終的に最も料金の安いルートを選択可能となり、ユーザにとって有用な情報を提供することができる。
【０１０２】
また、図８に示すような、割引条件が異なる路線１，２が複数跨る最適経路が求まった場合に、各路線１，２の時間帯条件にそれぞれ適合する時間調整を実行して最低料金を模索する判定ロジックでは、上記のような非現実的なルート案内となる可能性があるとともに、判定ロジックそのものが非常に複雑となり実装が困難である。
この点、本実施形態の処理コンピュータ１１では、調整時間（１０分間）を細かくずらした複数の仮想時刻ルートを生成し、これらに対応する仮想時刻料金を算出するので、入場時刻が丸１日異なるような仮想時刻ルートが生成されることがない。このため、非現実的なルート案内が行われることがなく、判定ロジックも単純で実装が簡便であるという利点がある。
【０１０３】
また、各路線１，２の時間帯条件にそれぞれ適合する時間調整を実行して最低料金を模索する判定ロジックでは、仮にそのような判定ロジックを作成できたとしても、路線１又は路線２の割引条件が変更される度に判定ロジックを見直す必要があり、メンテナンスが大変であるという欠点もある。
この点、本実施形態の処理コンピュータ１１では、予定時刻ルートから時間がずれた複数の仮想時刻ルートを先に生成し、その仮想時刻ルートに対応する料金（仮想時刻料金）をすべて算出するので、路線１及び２の割引条件が変更されても必ず正しい料金を求めることができる。このため、判定ロジックを見直す必要がなく、メンテナンスが非常に容易である。
【０１０４】
〔その他の変形例〕
今回開示した各実施形態は本発明の例示であって制限的なものではない。本発明の範囲は、上記実施形態ではなく特許請求の範囲によって示され、特許請求の範囲とその構成と均等な意味及び範囲内での全ての変更が含まれる。
例えば、上記実施形態では、予定時刻ルートと仮想時刻ルートの中からそれぞれ割安ルートを選択し、仮想時刻ごとの割安ルートをユーザに提示するようになっているが、算出手段１９で算出された、予定時刻ルートと仮想時刻ルートの双方を含むすべてのルートの中から、最も安価な割安ルートを処理コンピュータ１１の判定手段２０で予め判定し、予め判定された割安ルートのみをユーザに提示するようにしてもよい。
【０１０５】
また、上記実施形態では、処理コンピュータ１１が、第１ルート群を用いた割安ルート探索（第１探索処理）を行ってから、第２ルート群を用いた割安ルート探索（第２探索処理）実行しているが、第２探索処理を先に実行してから第１探索処理を実行するようにしてもよい。また、第１探索処理と第２探索処理のいずれか一方のみを実行することにしてもよい。
【０１０６】
更に、上記実施形態の第２探索処理（図７）では、予定時刻から一定の時間間隔だけ遅らせた、いわば未来の仮想時刻ルートを生成しているが、予定時刻から一定の時間間隔だけ早めた過去の仮想時刻ルートを生成することにしてもよい。
この場合には、過去の仮想時間ルートに対応する仮想時間料金が割安となる場合があるので、現時点で車両３に搭乗しているユーザに対する割安ルートとして採用することはできないが、例えば翌日以降の旅行計画を立てているユーザに対しては、有用な割安ルートとなり得る。
【０１０７】
また、上記実施形態では、サーバ装置２と車載装置４の間の無線通信を、携帯電話機８を通じて行っているが、この無線通信は、例えば、光ビーコン、無線ＬＡＮ、ＤＳＲＣ（Dedicated Short Range Communication ）等の比較的エリアの狭い路車間通信で行うこともできる。
更に、上記実施形態では処理コンピュータ１１が割安ルートの経路探索を実行しているが、各車両３に搭載された車載装置４が独自に当該経路探索を行うことにしてもよい。
【０１０８】
すなわち、本発明の経路探索装置は、車載装置４の演算装置に組み込むことも可能である。
また、車載装置４の演算装置が基準ルートの探索までを行い、この基準ルートを車載サーバ２に送信してもよい。この場合、車載サーバ２の処理コンピュータ（経路探索装置）１１は、車載装置４から受信した基準ルートに基づいて乗り直しルートや仮想時刻ルートを生成し、この各ルートについてそれぞれ求めた料金に基づいて割安ルートの探索処理を行うことになる。
【０１０９】
更に、上記実施形態では、サーバ装置２と複数の車載装置４とからなるナビゲーションシステム１を例示しているが、当該システム１の構成要素は車載装置４以外のものであってもよい。例えば、サーバ装置２とインターネット通信可能な携帯電話機やノートＰＣ等の端末装置を、上記ナビゲーションシステム１の構成要素とすることもできる。
この場合、出発地点や目的地点の設定作業をＷＥＢサイトの入力画面を通じてユーザが行うことにより、その地点情報をサーバ装置２に送信させることができる。
【０１１０】
〔その他の発明の開示〕
なお、本明細書には、冒頭の特許請求の範囲に記載した請求項だけでなく、以下の請求項１〜３に示す発明も含まれる。
【０１１１】
〔請求項１〕
出発地点から目的地点までの有料道路を含む経路を探索する経路探索ロジックを実行可能なルート生成装置（ルート取得手段１８を有する処理コンピュータ１１）であって、
次の（ａ）の基準ルートのみを前記経路探索ロジックにより生成し、次の（ｂ）の乗り直しルートについては前記基準ルートと同じものを援用することを特徴とするルート生成装置。
（ａ） 車両が有料道路を途中で降りない基準ルート
（ｂ） 車両が有料道路を途中で降りてその降りる地点で同有料道路に復帰する乗り直しルート
【０１１２】
〔請求項２〕
出発地点から目的地点までの有料道路を含む経路を探索する経路探索ロジックを実行可能であり、この経路探索ロジックにより生成可能な次の（ａ）の基準ルート及び（ｂ）の乗り直しルートの中から、料金面で割安となる少なくとも１つの割安ルートを探索するための経路探索装置であって、
前記基準ルートのみを前記経路探索ロジックにより生成し、前記乗り直しルートについては前記基準ルートと同じものを援用することを特徴とする経路探索装置。
（ａ） 車両が有料道路を途中で降りない基準ルート
（ｂ） 車両が有料道路を途中で降りてその降りる地点で同有料道路に復帰する乗り直しルート
【０１１３】
〔請求項３〕
前記乗り直しルートにおける乗り直し地点以降の前記車両の到着予定時刻を、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行する請求項２に記載の経路探索装置。
【０１１４】
上記請求項１及び２に係る発明によれば、経路探索ロジックにより基準ルートのみを生成し、乗り直しルートについては基準ルートと同じものを援用するので、割安ルートの探索のために乗り直しルート（１つでも複数種類でもよい。）を生成するに当たっての経路探索ロジックによる演算量を抑制することができる。
もっとも、当該発明では、乗り直しルートが複数ある場合において、そのすべての乗り直しルートについての援用を強制するものではなく、ユーザに対する情報提供の遅れがさほど問題にならない範囲で、複数ある乗り直しルートのうちの一部のルートに対する経路探索ロジックを実行することにしてもよい。
【０１１５】
一方、乗り直しルートに関して経路探索ロジックを実行しない場合には、そのループ経路の通行時間（すなわち、乗り直しに必要な時間）を考慮しないと、乗り直し地点以降の車両の到着予定時刻（乗り直し地点において有料道路に復帰する予定時刻を含む。）がずれてしまい、乗り直し料金の算出に誤差が生じる。ユーザに対して誤った割安ルートの情報を提供してしまう恐れがある。
しかし、上記請求項３に係る発明によれば、乗り直しに必要な所定時間だけ遅らせる時刻補正を実行するので、そのような誤差が生じるのを未然に回避することができる。
【図面の簡単な説明】
【０１１６】
【図１】ナビゲーションシステムの全体構成を示す概略構成図である。
【図２】ナビゲーションシステムの機能ブロック図である。
【図３】割安ルートの経路探索処理を示すフローチャートである。
【図４】有料道路のインターチェンジの種別を示す説明図である。
【図５】ルート取得手段が生成する第１ルート群の一例を示す説明図である。
【図６】時刻補正処理の内容を示す説明図である。
【図７】ルート取得手段が生成する第２ルート群の一例を示す説明図である。
【図８】第２探索処理の効果を示すための説明図である。
【図９】各種ＥＴＣ割引の内容を示す説明図である。
【図１０】複数の乗り直し料金を対比する場合の効果を示すための説明図である。
【符号の説明】
【０１１７】
１ ナビゲーションシステム
２ サーバ装置
３ 車両
４ 車載装置
５ 交通情報センタ
６ イーサネット網
７ 無線基地局
８ 携帯電話機
１１ 処理コンピュータ（経路探索装置）
１２ 第１通信部
１３ 第２通信部（出力手段）
１４ 会員データベース
１５ 交通情報データベース
１６ 地図データベース
１７ 割引情報
１８ ルート取得手段
１９ 算出手段
２０ 判定手段
ＩＣ インターチェンジ
Ｒ ループ経路
【技術分野】
【０００１】
本発明は、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索するための経路探索装置、経路探索方法及びこれらを実行するためのコンピュータプログラムに関する。
【背景技術】
【０００２】
自車両を出発地点から目的地点まで誘導する経路探索装置（例えば、車載ナビゲーション装置）は既に周知である。この経路探索装置は、出発地点から目的地点までの最適経路を所定の経路探索ロジックを用いて演算し、この演算結果である最適経路を、ディスプレイやスピーカ等の出力装置を介して画像や音声で搭乗者に案内するものである。
かかる最適経路の探索手法は、例えば、リンクコストが最小となる最適経路を特定の経路探索ロジックによって算出するのが一般的であり、この経路探索ロジックとしては、例えばダイクストラ法やポテンシャル法が利用される（特許文献１参照）。
【０００３】
【特許文献１】特開平７−１０３７７７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、高速道路等の有料道路では、料金所での渋滞緩和を主目的として、ＥＴＣシステム（Electronic Toll Collection System ）の整備が進展している。
かかるＥＴＣシステムを採用した有料道路では、車両の走行時間帯、走行距離及び走行区間等の観点から設定された種々の条件を満たす場合に通行料金の割引が適用される、ＥＴＣ割引が既に実施されている。このＥＴＣ割引の代表例としては、深夜割引、通勤割引及び早朝夜間割引といった時間帯割引がある（図９参照）。
【０００５】
上記ＥＴＣ割引の割引率は、大きい場合で５０％という大幅なものであるから、この割引制度を上手く活用すれば、有料道路を含む経路を走行する場合の通行料金を大幅に削減することができる。
しかし、上記の通り、ＥＴＣ割引は、有料道路に対する車両の走行時間帯、走行距離及び走行区間等といった種々の観点からの条件が設定されているので、いかなる経路でいかなる時刻に有料道路を通行すれば割引が受けられるのかを、走行中の車両の搭乗者が即座に判断するのは非常に困難である。
【０００６】
例えば、前記通勤割引の場合には、有料道路の入口インターチェンジ（以下、ＩＣと略記することがある。）と出口ＩＣを所定の時間帯に通過するという時間帯条件に加え、入口ＩＣから出口ＩＣまでの走行距離が１００ｋｍ以内であるという走行距離条件が加重されている。
このため、車載のナビゲーション装置による指示通りに途中のＩＣで降りないで走行を継続した場合には、上記走行距離条件に適合しないが、敢えて途中のＩＣで有料道路を降りていったん一般道路を走行し、その途中のＩＣで当該有料道路に復帰する乗り直しルートを採用すれば、上記走行距離条件に適合することがある。
【０００７】
また、例えば、午後の通勤割引と早朝夜間割引とは、適用される時間帯条件が互いに近接している。
このため、車載のナビゲーション装置による指示通りに途中のＩＣで降りないで走行を継続した場合には、前半の通勤割引しか適用されないが、敢えて途中のＩＣで有料道路を降りて暫く一般道路を走行し、その途中のＩＣで当該有料道路に復帰する乗り直しルートを採用すれば、通勤割引と早朝夜間割引の双方が適用され、より割安となる場合もあり得る。
【０００８】
しかし、上記のような割安となる乗り直しルートを車両の搭乗者が走行中に察知するのは至難であり、かかる乗り直しルートで実際に走行するためには、搭乗者自身がＥＴＣ割引の適用条件を熟知した上で、予め周到な走行計画を立てておく必要がある。
そこで、ＥＴＣ割引の適用条件をコストとして想定し、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索する機能を有する経路探索装置があれば至便であるが、かかる経路探索装置は未だ実現されていない。
【０００９】
本発明は、このような問題点に鑑み、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを事前に自動的に探索できるようにして、ユーザに対して経済的なルート案内を行える経路探索装置等を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の経路探索装置（請求項１）は、出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索するための経路探索装置であって、車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するルート取得手段と、取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートを走行するのにそれぞれ必要な乗り直し料金とを算出する算出手段と、算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定する判定手段と、を備えていることを特徴とする。
【００１１】
本発明の経路探索装置によれば、前記算出手段が、基準ルートを走行するのに必要な基準料金と、複数の乗り直しルートを走行するのに必要な乗り直し料金とを算出する。
この乗り直し料金には、有料道路を途中で降りて再度その降りた地点で当該有料道路に復帰する乗り直すルートを敢えて採ったことが原因で、有料道路の割引制度が適用され、基準料金よりも割安になっているものが含まれている場合がある。
【００１２】
そこで、本発明の経路探索装置では、判定手段が、算出された上記両料金に基づいて、基準ルート及び乗り直しルートの中から少なくとも１つの割安ルートを判定する。これにより、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを自動的に探索することができる。
このため、探索された割安ルートを、例えば車載のディスプレイやスピーカ等の出力装置を通じてユーザ（車両の搭乗者）に提供するようにすれば、そのユーザに対して経済的なルート案内を事前に行うことができる。
【００１３】
また、本発明の経路探索装置によれば、１つの乗り直しルートだけではなく、複数の乗り直しルートを走行するのにそれぞれ必要な乗り直し料金を算出し、この複数の乗り直し料金に基づいて割安ルートを判定するので、１つの有料道路区間に対して、乗り直しを行うインターチェンジの場所や乗り直しの回数が異なる複数の乗り直しルートの中から、料金面で最も有利な割安ルートを探索することができる。
【００１４】
例えば、前記ルート取得手段が取得する複数の前記乗り直しルートの中に、複数のインターチェンジで乗り直しをする乗り直しルートが含まれている場合には（請求項３）、それぞれの乗り直しによって割引適用が複数回受けられ、１つのＩＣだけで乗り直しを行う場合に比べて料金面でより有利な割安ルートとなることがある（後述の図１０参照）。
本発明の経路探索装置では、このような複数種類の乗り直しルートを走行するのにそれぞれ必要な乗り直し料金に基づいて割安ルートを判定するので、その中から料金面で最も有利な割安ルートを探索することができる。
【００１５】
上記の通り、出発地点から目的地点までの経路に含まれる１つの有料道路の途中には、乗り直し可能なインターチェンジ（ＩＣ）が１つだけの場合に限らず、複数箇所あることも考えられる。
この場合、どこの途中ＩＣで乗り直しを行うか、及び、乗り直しを何回行うかの組み合わせによって料金が異なる複数の乗り直しルートを想定することができるので、このうちのどの乗り直しルートが料金面で最も有利となるかの判定ロジックが必要になる。
【００１６】
そこで、本発明の経路探索装置において、前記ルート取得手段は、前記有料道路の途中に位置する乗り直し可能なすべてのインターチェンジの中から選択し得る１又は複数の当該インターチェンジの組み合わせに基づいて、前記有料道路に関して採り得るすべての前記乗り直しルートを総当たり的に生成し、前記算出手段は、生成されたすべての前記乗り直しルートに対してそれぞれ前記乗り直し料金を算出することが好ましい（請求項２）。
【００１７】
この場合、ルート取得手段が、有料道路に関して採り得る乗り直しルートを総当たり的に生成し、算出手段が、そのように総当たり的に生成されたすべての乗り直しルートに対してそれぞれ乗り直し料金を算出するので、例えば料金が最小となる乗り直しルートを割安ルートとして選択するという比較的簡単な判定ロジックを採用することができ、料金面で有利となる割安ルートを簡単に判定できるようになる。
【００１８】
また、上記のように、すべての乗り直しルートを総当たり的に生成し、その各乗り直しルートに対して乗り直し料金を算出するようにすれば、割引制度の適用条件の変更にも柔軟に対応できるという利点がある。
すなわち、有料道路の事業主体が、割引制度の適用条件を将来的に任意に変更することも考えられるが、総当たり的に求めた各乗り直しルートに対してそれぞれ乗り直し料金を算出し、算出されたすべての乗り直し料金に基づいて割安ルートを判定する判定ロジックを採用すれば、正しい料金を算出するために割引適用条件を更新するだけで、同じ判定ロジックで正しい割安ルートを判定することができ、割安ルートの判定ロジック自体を変更する必要がない。
【００１９】
一方、基準ルートと複数の乗り直しルートの中から少なくとも１つの割安ルートを判定する場合において、料金面で優劣がつかない複数の割安ルートが見つかる場合がある。
この場合、有料道路への乗り直しの予測時刻と実際に有料道路に乗り直した時刻との差（以下、「時刻ずれ」という。）について考えると、この時刻ずれは、乗り直し地点までの渋滞や混雑等の交通状況によって大きく変化する。そして、乗り直し地点が異なる複数の乗り直しルートを想定すると、有料道路に対する乗り直しの実行時期が遅いほど、交通状況の変動による時刻ずれが発生し易いために割引適用が受けられなくなる可能性が高くなり、逆に、乗り直しの実行時期が早いほど、交通状況の変動による時刻ずれが発生し難くいために割引適用を受けられる可能性が高くなると考えられる。
【００２０】
そこで、前記判定手段は、料金面では優劣のつかない複数の前記割安ルートが複数ある場合には、前記出発地点により近い乗り直し地点を有する当該乗り直しルートを他よりも有利なルートとして判定を優先させることが好ましい（請求項４）。
なお、料金面で優劣がつかない複数の割安ルートがある場合には、更に乗り直し回数がより少ない乗り直しルートを、他よりも有利なルートとして判定を優先させることにしてもよい。その理由は、有料道路から一旦降りて一般道路を走行し、再び有料道路に乗るという乗り直し自体が煩雑な行為なので、乗り直し回数が少ないほど、ドライバーの負担がより小さくなるからである。
【００２１】
本発明の経路探索装置において、前記ルート取得手段は、前記出発地点から前記目的地点までの経路を探索する経路探索ロジック（例えば、ダイクストラ法やポテンシャル法等）を実行可能なものを採用することができる。
もっとも、かかる経路探索ロジックを実行可能であっても、当該ルート取得手段において、その経路探索ロジックにより前記基準ルートのみを生成し、前記乗り直しルートについては前記基準ルートと同じものを援用することが好ましい（請求項５）。
【００２２】
その理由は、乗り直し地点を経由地に設定して経路探索ロジックを実行すれば、複数の乗り直しルート（有料道路からいったん外れるループ経路を含む。）を個別に生成することもできるが、このような乗り直しルートの生成のための経路探索ロジックを逐一実行すると、演算量が大きくなってユーザに対する情報提供が遅れる恐れがあるからである。
特に、前記した通り、すべての乗り直しルートの組み合わせを総当たり的に生成する場合には、乗り直し可能な途中のインターチェンジが多数ある場合には、経路探索ロジックを実行すべき乗り直しルートの数が膨大になるので、これら膨大数の乗り直しルートについて単純に経路探索ロジックを実行してしまうと、演算量が膨大になる恐れがある。
【００２３】
一方、乗り直しルートについては基準ルートと同じものを援用する場合には、そのループ経路の通行時間（すなわち、乗り直しに必要な時間）を考慮しないと、乗り直し地点以降の車両の到着予定時刻（乗り直し地点において有料道路に復帰する予定時刻を含む。）がずれてしまい、算出手段が算出する乗り直し料金に誤差が生じ、ユーザに対して誤った割安ルートの情報を提供してしまう恐れがある。
そこで、本発明の経路探索装置において、前記ルート取得手段は、前記乗り直しルートにおける乗り直し地点以降の前記車両の到着予定時刻については、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行し、前記算出手段は、時刻補正された前記到着予定時刻に基づいて前記乗り直し料金を算出することが好ましい（請求項６）。
上記「乗り直しに必要な所定時間」は、全ＩＣ共通又は各ＩＣ個別の固定時間であってもよいし、曜日や時間帯等に応じて変動させる可変の設定時間であってもよい。
【００２４】
なお、本発明において、「料金面で割安となる割安ルート」とは、必ずしも単純に最低料金のルートのだけを意味するものではなく、乗り直しに伴うタイムロスとの関係を比較考量した綜合的な判定によって定まるルートも、これに含まれる。
例えば、本発明の経路探索手段において、前記算出手段は、前記有料道路に対する乗り直しのために生じるタイムロスを料金に換算し、換算された当該料金を前記乗り直し料金の算出に反映させるようにしてもよい。
この場合、乗り直しに伴うタイムロスが料金に換算されるので、単純な料金面だけで割安ルートを選択する場合に比べて、実態に即した有意義な判定を行うことができる。
【００２５】
本発明のコンピュータプログラム（請求項７）は、本発明の経路探索装置（請求項１）が行う探索処理をコンピュータに実行させるためのコンピュータプログラムであって、当該経路探索装置（請求項１）と同様の作用効果を奏する。
また、本発明の経路探索方法（請求項８）は、本発明の経路探索装置（請求項１）が行う探索方法であって、当該経路探索装置（請求項１）と同様の作用効果を奏する。
【発明の効果】
【００２６】
以上の通り、本発明によれば、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを事前に自動的に探索することができるので、ユーザに対して経済的なルート案内を行うことができる。
【発明を実施するための最良の形態】
【００２７】
〔システムの全体構成〕
図１は、本発明の経路検索装置を有するナビゲーションシステムの全体構成を示す概略構成図であり、図２は、同システムの機能ブロック図である。
図１及び図２に示すように、本実施形態のナビゲーションシステム１は、サーバ装置２と、複数の車両３にそれぞれ搭載された車載装置４とから構成されている。
なお、本明細書において、「車両」とは、自動車、原動機付き自転車、軽車両及びトロリーバス等のことをいう。また、「車載装置」とは、車両に搭載されており、その搭乗者に対して目的地までの経路を案内するいわゆるナビゲーション装置のことをいう。
【００２８】
このナビゲーションシステム１は、予め入会登録された会員（ユーザ）の車両３自体をセンサーとして、各車両３からサーバ装置２が情報収集し、メンバー間で相互に情報提供し合って運用することにより、サーバ装置２が各会員に対して有用な交通情報を提供するようにしたものである。
従って、本システム１によれば、通常のＶＩＣＳ（登録商標：Vehicle Information and Communication System）情報とともに、このＶＩＣＳ情報に含まれていないより詳細かつ動的な交通情報を、各会員の車両３に提供することができる。
【００２９】
本システム１のサーバ装置２は、専用の通信回線を介して交通情報センタ５に接続されており、必要に応じてＶＩＣＳ情報を交通情報センタ５から入手している。また、サーバ装置２は、インターネット網６を通じて携帯電話機８の無線基地局７と双方向で通信可能である。
各車両３の車両装置４は、搭乗者の携帯端末である携帯電話機８を介して、無線基地局７と双方向で通信可能であり、無線基地局７は上記インターネット網８に接続されている。このため、各車両３の車両装置４は、ほぼリアルタイムでサーバ装置２に対して情報を送受信可能となっている。
【００３０】
各車両３の車載装置４は、ＧＰＳ（Global Positioning System ）アンテナと、ＧＰＳ受信機と、道路地図データベースと、入力デバイスと、ディスプレイ及びスピーカ等よりなる出力装置とを備えており、ＧＰＳ受信機で検出した現在位置をディスプレイの画面上に表示できるようになっている。
また、車載装置４は、入力デバイスで入力された所定の旅行条件に基づいて、旅行ルートを演算可能なルート演算装置（図示せず）を備えている。
【００３１】
車載装置４に入力可能な旅行条件としては、出発地点（現在地点を含む。）や目的地点のほか、経由地や優先経路（ 一般道路優先又は有料道路優先や、距離優先又は道幅優先）等がある。ルート演算装置のメモリには、入力される情報や自身で演算した旅行ルートに加えて、サーバ装置２から提供されたルート探索情報を保存することもできる。
なお、本実施形態の車載装置４は、ＥＴＣ対応であり、有料道路の料金所等に設置されたＥＴＣ路側処理装置と無線による路車間通信を行うことができる。
【００３２】
〔サーバ装置の内部構成〕
図２に示すように、サーバ装置２は、ワークステーション等よりなる処理コンピュータ１１と、この処理コンピュータ１２に接続された通信インターフェースよりなる第１及び第２通信部１２，１３と、各種データベース１４〜１６とから構成されている。
第１通信部１２は、専用回線で交通情報センタ５に接続されている。また、第２通信部１３は、インターネット網６を介して前記無線基地局７に接続され、この無線基地局７と車両３の搭乗者の携帯電話機８との間の無線通信を通じて、車載装置４との間で情報の送受信を行う。
【００３３】
各データベース１４〜１６のうち、会員データベース１４には、当該システム１に参加する登録会員の識別情報が保存されている。処理コンピュータ１１は、会員データベース１４に記録されている特定の登録会員から受信した入力情報（出発地点及び目的地点等）に基づいて、後述する割安ルートの経路探索処理を実行する。
交通情報データベース１５には、第１通信部１２が受信した交通情報センタ５からのＶＩＣＳ情報が保存される。このＶＩＣＳ情報は、処理コンピュータ１１がセンタ５からのＶＩＣＳ情報を抽出するごとに更新され、ほぼ最新の情報が保持される。
【００３４】
また、交通情報データベース１５には、特定の登録会員から受信したリンク番号、リンク進入時刻、リンク退出時刻、リンク旅行時間等よりなる交通情報も保存される。
この場合、車載装置４は、所定時間毎（例えば、０．１秒毎）又は所定距離毎（例えば、５ｍ毎）に位置を検出しており、各リンクについて、検出位置がリンクの始端の位置を通過（一致）した時刻をリンク進入時刻とし、検出位置がリンクの終端の位置を通過（一致）した時刻をリンク退出時刻とし、リンク退出時刻とリンク進入時刻との差をリンク旅行時間として算出する。
【００３５】
更に、交通情報データベース１５には、ＥＴＣ割引に代表される有料道路の割引情報１７が含まれている。
この割引情報１７は、例えばＮＥＸＣＯが公表している各ＩＣ間の通行料金テーブルよりなり、この通行料金テーブルは、深夜割引、通勤割引及び早朝夜間割等の割引制度ごとに定められた複数のテーブルよりなる。なお、この割引情報１７の基礎となる各種ＥＴＣ割引の詳細については後述する。
【００３６】
地図データベース１６には道路地図データが記録されており、この道路地図データには交差点データとリンクデータとが含まれている。
交差点データは、交差点ＩＤと交差点位置とを対応付けたデータである。また、リンクデータは、特定リンクのリンクＩＤに対して、特定リンクの始点・終点・補間点の位置、特定リンクの始点に接続するリンクＩＤ、特定リンクの終点に接続するリンクＩＤ、及び、特定リンクのリンクコストを対応付けたデータよりなる。
【００３７】
リンクコストは、例えば、特定リンクとその終点に接続するリンクの組み合わせの数だけ用意されており、特定リンクの始点に進入してから当該特定リンクの終点を退出し、次に接続するリンクの始点に進入するまでに要する時間として設定されている。
すなわち、リンクコストには、特定リンクの始点から終点までを走行するのに要するコスト（時間）と、その特定リンクの終点から次のリンクの始点までを走行するのに要するコスト（時間）、つまり、交差点通過に要するコストが含まれている。
【００３８】
リンクコストは、平日、土曜、日曜及び祝日といった日種別ごとに、現時点から１日先までの５分毎のデータ（すなわち、現時点のリンクコスト、５分先のリンクコスト、１０分先のリンクコスト、… …、２３時間５５分先のリンクコスト、２４時間先のリンクコスト）が用意されており、これらのデータは、交通情報データベース１５のＶＩＣＳ情報や、特定会員から受信した交通情報に基づいて作成される。
【００３９】
また、地図データベース１６には、地図上の各道路が一般道路か有料道路かの区別情報と、有料道路のインターチェンジ（ＩＣ）の位置情報と、当該ＩＣが乗り直し可能か否かを判断するための種別情報が含まれている。図４は、有料道路のインターチェンジの種別を示す説明図である。
図４に示すように、有料道路のインターチェンジには、「入口のみ」のＩＣと、「出口のみ」のＩＣと、同じ場所に同方向の入口と出口の両方がある「両方あり」のＩＣと、同じ場所に入口と出口があるがその方向が異なる「異方向の出入口」のＩＣとがある。
【００４０】
このうち、「両方あり」のＩＣのみが乗り直し可能なＩＣ（以下、乗り直しＩＣということがある。）として記憶され、「入口のみ」のＩＣ、「出口のみ」のＩＣ及び「異方向の出入口」のＩＣは、乗り直し不能なＩＣとして記憶されている。
なお、本明細書において、「乗り直し」とは、車両３が有料道路を途中のＩＣで降り、その降りたＩＣで当該有料道路に再び復帰することを意味する。
【００４１】
〔処理コンピュータの構成及び機能〕
処理コンピュータ１１は、ＨＤＤやメモリ等よりなる記憶装置と、この記憶装置から各種のコンピュータプログラムを読み出して実行する演算装置とを含んでいる。
上記各コンピュータプログラムのうちの１つは、車両３が有料道路を含む経路を走行する場合の割安ルートを探索する処理を行うものであり、この探索処理用のプログラムの機能定義として、ルート取得手段１８、算出手段１９及び判定手段２０を含んでいる。
【００４２】
このうち、ルート取得手段１８は、出発地点から目的地点までの最小のリンクコストとなる最適経路を探索する、例えば、ダイクストラ法又はポテンシャル法を利用した経路探索ロジックを実行可能である。
例えば、ルート取得手段１８は、各リンクへの進入予測時刻を算出し、その進入予測時刻に該当するリンクコストを用いて経路を探索する。具体的には、出発地点が含まれるリンク（出発リンク）の現時点のリンクコストを用いて、出発リンクの退出予測時刻を算出する。
【００４３】
これがそのまま出発リンクに接続するリンク（一次接続リンク）の進入予測時刻となるため、一次接続リンクについては、この進入予測時刻に該当する時点のリンクコストを用いる（例えば、一次接続リンクの進入予測時刻が５分先までなら現時点のリンクコストを用い、一次接続リンクの進入予測時刻が５分先以上１０分先までなら５分先のリンクコストを用いる）。
【００４４】
そして、このリンクコストを用いて、一次接続リンクの退出予測時刻を算出する。これがそのまま一次接続リンクに接続するリンク（二次接続リンク）の進入予測時刻となるため、二次接続リンクについては、この進入予測時刻に該当する時点のリンクコストを用いる。以降、同様にこれを繰り返す。
また、ルート取得手段１８は、上記経路探索ロジックで得られた最適経路に有料道路が含まれている場合には、以下の（ａ）及び（ｂ）でそれぞれ定義される「第１ルート群」と「第２ルート群」を生成する、ルート生成処理を行う。
【００４５】
（ａ） 第１ルート群（予定時刻ルート）
第１ルート群は、次の「基準ルート」と「乗り直しルート」とからなる。
「基準ルート」：最適経路に含まれる有料道路を、途中のＩＣで乗り直しを行わないでそのまま走行するルート。
「乗り直しルート」：有料道路の途中にある乗り直しＩＣで乗り直しを行うルート。１つの有料道路区間の中に乗り直しＩＣが複数ある場合には、乗り直しＩＣの数と場所が異なるすべての組み合わせからなる。
【００４６】
なお、第１ルート群の基準ルートと乗り直しルートは、有料道路への流入を予定時刻通りに行うものであり、流入時刻を敢えてずらす後述の第２ルート群を構成する「仮想時刻ルート」と対比して、「予定時刻ルート」と呼ぶ。
（ｂ） 第２ルート群
第２ルート群は、次の「仮想時刻ルート」からなる。
「仮想時刻ルート」：「基準ルート」及び「乗り直しルート」のそれぞれについて、予定時刻から所定時間（例えば、３０分）内に含まれる範囲で、予定時刻から敢えて一定の時間間隔（例えば、１０分）ずつずらした仮想時刻に、有料道路に流入するルート。
【００４７】
なお、上記第２ルート群の定義において、「予定時刻」とは、車両３が現在時刻に出発地点を出発して目的地点に向かって経路に沿って走行した場合に、その車両３が有料道路の各ＩＣに流入する時刻のことを意味する。従って、例えば、予定時刻から１０分ずらした仮想時刻ルートは、有料道路の各ＩＣに対応するリンクへの流入予測時刻をそれぞれ１０分ずつずらして生成される。
【００４８】
算出手段１９は、有料道路の割引情報１７と車両３がＩＣに到達する予定時刻又は仮想時刻に基づいて、第１及び第２ルート群に含まれる各ルートを走行するのに必要な料金を算出する。
すなわち、第１ルート群の場合は、車両３が基準ルートを予定時刻通りに走行するのに必要な、予定時刻での「基準料金」と、各乗り直しルートを予定時刻通りに走行するのに必要な、予定時刻での「乗り直し料金」とがそれぞれ算出される（予定時刻料金）。
【００４９】
また、第２ルート群の場合は、車両３が基準ルートを予定時刻からずれた仮想時刻に走行するのに必要な、仮想時刻の「基準料金」と、各乗り直しルートを予定時刻からずれた仮想時刻に走行するのに必要な、仮想時刻の「乗り直し料金」とがそれぞれ算出される（仮想時刻料金）。
そして、判定手段２０は、算出手段１９で算出された上記各料金に基づいて、第１ルート群（予定時刻ルート）について最も安価なルートを判定し、かつ、第２ルート群に属する時間ずらし量が異なる各仮想時刻ルートについてもそれぞれ最も安価なルートを判定する。
【００５０】
すなわち、判定手段２０は、次の１）〜４）に示す各ルートを、それぞれ割安ルートと判定する。
１） 予定時刻通りの基準ルートとすべての乗り直しルート（予定時刻ルート）の中で最も安価なルート
２） 有料道路への流入を１０分遅らせた仮想時刻の基準ルートとすべての乗り直しルート（第１の仮想時刻ルート）の中で最も安価なルート
３） 有料道路への流入を２０分遅らせた仮想時刻の基準ルートとすべての乗り直しルート（第２の仮想時刻ルート）の中で最も安価なルート
４） 有料道路への流入を３０分遅らせた仮想時刻の基準ルートとすべての乗り直しルート（第３の仮想時刻ルート）の中で最も安価なルート
【００５１】
〔経路探索処理のフローチャート〕
図３は、本システム１を利用した割安ルートの経路探索処理を示すフローチャートである。
図３に示すように、まず、車両３の搭乗者が車載装置４に対して出発地点と目的地点の設定を行う（ステップＳ１）。この場合、出発地点の設定がない場合には、車両３の現在位置が出発地点となる。
【００５２】
上記出発地点と目的地点は、携帯電話機８を通じてサーバ装置２に送信され、処理コンピュータ１１によって経路探索処理が行われる。
サーバ装置２の処理コンピュータ１１は、設定された出発地点と目的地点とからリンクコストが最小となる最適経路を探索し、この最適経路に有料道路が含まれている場合に、前記第１及び第２ルート群を生成する（ステップＳ２）。
その後、処理コンピュータ１１は、生成された第１及び第２ルート群に含まれる各ルートについてのすべての料金を算出し（ステップＳ３）、第１ルート群（予定時刻ルート）の中から値段が最小となる割安ルートを判定するとともに、第２ルート群に属する時間ずらし量が異なる各仮想時刻ルートについても値段が最小となる割安ルートを判定する（ステップＳ４）。
【００５３】
そして、処理コンピュータ１１は、第１及び第２ルート群についての各割安ルートを、通信部１３を通じて車載装置４に送信する（ステップＳ５）。
車載装置４は、サーバ装置２から上記割安ルートを受信すると、ディスプレイやスピーカ等の出力装置を介して、有料道路を含む最適経路とこの経路に関連する割安ルートの内容を搭乗者に提供する（ステップＳ６）。
なお、搭乗者に提供する最適経路及び割安ルートの内容に関する情報としては、例えば次のものを含めることができる。
【００５４】
ア） 出発地点から目的地点までの走行経路
イ） 通行料金（通常料金と割引料金）
ウ） 入口ＩＣの名称、出口ＩＣの名称及び乗り直しＩＣの名称
エ） 走行時間（乗り直しに必要な調整時間を含む。）
オ） 今回の走行で適用され得る割引制度の適用条件（時間帯条件や走行距離条件）
カ） 割引制度を受けるために必要な調整時間（待ち時間）
【００５５】
上記の情報提供を受けた車両３の搭乗者は、自身の判断で割安ルートを選択するか否かを判断する（ステップＳ７）。そして、仮に割安ルートを選択した場合には、車両３がその割安ルートに沿って走行し、目的地に到着することになる（ステップＳ８）。
なお、割安ルートが選択されるか否かは、搭乗者自身がその時の価値判断で任意に決定するものであり、料金面よりも時間短縮が優先される場合には、通常の最適経路が選択される場合もあり得る。
【００５６】
〔有料道路の割引制度〕
次に、割引情報１７の基礎となる有料道路の割引制度の内容について説明する。
なお、ここでは、ＮＥＸＣＯが実施しているＥＴＣシステムを利用する車両３に対する高速道路の通行料金の割引制度について説明する。
ただし、これはあくまでも割引制度の一例であって、ここに示す割引制度自体も随時変更される可能性がある。また、ＮＥＸＣＯ以外の事業主体が管理する有料道路でも、割引制度が新たに実施される可能性もある。
【００５７】
図９は、ＮＥＸＣＯが実施する各種ＥＴＣ割引の内容を示す説明図である。
図９（ａ）の深夜割引は、午前０時から午前４時までの間に、車両３が対象区間の入口ＩＣから出口ＩＣを走行した場合に適用されるもので、割引率は３０％である。
図９（ｂ）の通勤割引は、午前６時から午前９時までの間に、車両３が対象区間の入口ＩＣ又は出口ＩＣを通過した場合、或いは、午後５時から午後８時までの間に、車両３が対象区間の入口ＩＣ又は出口ＩＣを通過した場合に適用されるもので、割引率は５０％である。
【００５８】
ただし、この通勤割引の場合には、入口ＩＣから出口ＩＣまでの１回の走行距離が１００ｋｍ以内であること、大都市近郊区間は適用外であること、及び、同日の午前と午後にそれぞれ１回だけ適用可能であるという制限がある。
なお、大都市近郊区間としては、例えば、大阪地区では、名神高速の大津と西宮の間、中国道の中国吹田と西宮北の間、近畿道の吹田と松原の間、阪和道の松原と岸和田和泉の間、西名阪道の天理と松原の間、京滋バイパスの瀬田東と久御山淀の間等がある。
【００５９】
図９（ｃ）の早朝夜間割引は、午後１０時から翌日午前６時までの間に、車両３が対象区間の入口ＩＣ又は出口ＩＣを通過した場合に適用されるもので、割引率は５０％である。ただし、この早朝夜間割引の場合には、大都市近郊区間内を少なくとも１区間走行し、１回の走行距離が１００ｋｍ以内であるという制限がある。
図９（ｄ）の特定区間割引は、車両３が、予め設定された特定の入口ＩＣから流入し、予め設定された特定の出口ＩＣから流出した場合に適用されるもので、割引率は時期によって種々に設定される。
【００６０】
〔割安ルートの経路探索処理〕
以下、図５〜図８を参照しつつ、前記処理コンピュータ１１が行う割安ルートの経路探索処理を、より具体的に説明する。
【００６１】
〔第１ルート群を用いた割安ルート探索：第１探索処理〕
図５は、ルート取得手段１８が生成する第１ルート群の一例を示す説明図である。
図５において、最適経路に含まれる有料道路区間の長さは２００ｋｍであるとし、その区間の入口ＩＣと出口ＩＣの間に、乗り直し可能な３つの途中ＩＣが含まれているものとする。この図５に示す矢印Ｒは、各ＩＣで乗り直しを実行するループ経路を示している。
また、隣り合うＩＣ間の距離は５０ｋｍであり、乗り直しによる有料道路区間の最大分割数は３に設定されているものとする。なお、最大乗り直し回数（乗り直しできる回数の最大値）は「最大分割数−１」となる。
【００６２】
ここで、図５のルート（０）は、最適経路の経路検索ロジックを行った結果の１つであり、このルート（０）では、有料道路区間の途中ＩＣはすべて素通りし、入口ＩＣから出口ＩＣまでノンストップで走行する。従って、このルート（０）は基準ルートである。
一方、図５のルート（１）〜（６）は、有料道路区間の途中ＩＣで乗り直しを行う各乗り直しルートを示し、図５において、ハッチング部分が走行距離条件に適合する分割区間を示している。
【００６３】
このうち、ルート（１）〜（３）は、乗り直し回数が１回（分割区間数が２）の場合であり、ルート（１）では、最初の途中ＩＣで乗り直しを行い、ルート（２）では２番目の途中ＩＣで乗り直しを行い、ルート（３）では３番目の途中ＩＣで乗り直しを行うものとする。
また、図５のルート（４）〜（６）は、乗り直し回数が２回（分割区間数が３）の場合であり、ルート（４）では、最初と２番目の途中ＩＣで乗り直しを行い、ルート（５）では最初と３番目の途中ＩＣで乗り直しを行い、ルート（６）では２番目と３番目の途中ＩＣで乗り直しを行うものとする。
【００６４】
そして、有料道路区間の全区間に対して、通勤割引の時間帯条件を満たしていると仮定すると、ルート（０）〜（６）の各料金は、それぞれ図５の右側に列挙した各ブロックに示す通りとなる。
例えば、ルート（０）では、通勤割引の走行距離条件（１００ｋｍ以内）を充足していないので、すべての分割区間で割引がなく、料金が４７００円となっている。
【００６５】
また、ルート（１）では、最初の分割区間（５０ｋｍ）で割引適用があり、それ以降の分割区間（１５０ｋｍ）で割引適用がなく、料金が４４５０円となっている。
更に、ルート（２）では、最初の分割区間（１００ｋｍ）と次の分割区間（１００ｋｍ）の双方で割引適用があり、料金が４１５０円となっている。
ルート（３）では、最初の分割区間（１５０ｋｍ）では割引適用がなく、それ以降の分割期間（５０ｋｍ）で割引適用があり、料金が４４５０円となっている。
【００６６】
以下、同様に、ルート（４）〜（６）では、それぞれ料金が４９５０円、４９５０円及び４３００円となる。
これらを綜合すると、ルート（２）の料金（＝４１５０円）が最も安価であることが判明する。
【００６７】
なお、ルート取得手段１８が生成する乗り直しルートの総数Ｎを一般化すると、次のようになる。
すなわち、１つの有料道路区間に含まれる全ＩＣの総数（全乗り直しＩＣに入口ＩＣと出口ＩＣを加えた総数）をｎ、乗り直しによってその有料道路区間を分割する際の最大分割数をｍとすると、ルート取得手段１８が生成する乗り直しルートの総数Ｎは、Ｎ＝n-2Ｃ1＋n-2Ｃ2＋……＋n-2Ｃm-1となる。
なお、上記総数Ｎの算出式において、コンビネーション「Ｃ」の左添え字が「ｎ−２」となっているのは、有料道路区間の両端のＩＣでは乗り直しができないからであり、コンビネーション「Ｃ」の右添え字「ｍ−１」は最大乗り直し回数に該当する。
【００６８】
このように、ルート取得手段１８は、有料道路区間の途中に位置するすべての乗り直しＩＣの中から選択し得る１又は複数のＩＣの組み合わせに基づいて、１つの有料道路区間に関して採り得る乗り直しルートを総当たり的に生成する。
そして、この各乗り直しルートに基づく乗り直し料金は、上記の通り、有料道路を途中で降りて敢えて乗り直したことが原因で、有料道路の割引制度が適用され、基準料金（基準ルートを走行する場合の料金）よりも割安になっている場合がある。
【００６９】
そこで、本実施形態の処理コンピュータ１１では、算出手段１９によって基準ルートとすべての乗り直しルートに対応する料金をすべて算出し、これらの各料金の中で最小の料金となるものを、判定手段２０が割安ルートとして判定するようになっている。
このため、本実施形態の処理コンピュータ１１によれば、ＥＴＣ割引に代表される有料道路の割引制度を活用した、料金面で割安となる割安ルートを自動的に探索することができる。
【００７０】
〔複数の乗り直し料金を対比する場合の効果〕
図１０は、複数の乗り直し料金を対比する場合の効果を示すための説明図である。
図１０において、有料道路の入口ＩＣと出口ＩＣの間に乗り直し可能なＩＣ１〜ＩＣ４が含まれており、このうち、入口ＩＣとＩＣ１とが大都市近郊エリアの中にあり、それ以外は大都市近郊エリアから外れているものと仮定する。
【００７１】
また、ここでは前記早朝夜間割引を想定し、この割引の適用条件のうち、時間帯条件についてはＩＣ１〜ＩＣ３でクリア可能であり、１回の走行距離が１００ｋｍ以内という走行距離条件と、大都市近郊区間内を少なくとも１区間走行するという走行区間条件が問題になるものとする。
この場合、例えば、早朝夜間割引の走行距離条件だけを考慮し、料金面で有利となる１つの乗り直しルートを考えると、１００ｋｍ以内の範囲で出来るだけ長い走行距離で乗り直しを行うことが料金面で有利となるので、図１０のルートＢに示すように、大都市近郊エリアを外れたＩＣ２（入口ＩＣから９０ｋｍ）で乗り直すルートを採用すればよい。
【００７２】
しかし、早朝夜間割引の場合には、大都市近郊エリアを少なくとも１区間走行すればよいので、そのエリア内に含まれるＩＣ１でいったん乗り直しを行えば、このＩＣ１の前後双方の区間が早朝夜間割引の対象区間になる。
そこで、図１０のルートＡのように、大都市近郊エリアを外れる直前のＩＣ１（入口ＩＣから３０ｋｍ）で１回乗り直しを行い、更に、ＩＣ１から９０ｋｍ離れたＩＣ３でもう一度乗り直しを行うようにすれば、合計１２０ｋｍ（＝３０ｋｍ＋９０ｋｍ）の走行距離に渡って早朝夜間割引を受けられ、乗り直しが１回の前記ルートＢよりも割安になる。
【００７３】
しかし、単一の適用条件（この場合は、走行距離条件）のみを想定してルートＢを導き出すのは比較的容易であるが、複数の適用条件（この場合は、走行距離条件と走行区間条件）のすべてを想定してルートＡを導き出すのは困難である。
すなわち、複数の割引の適用条件を考慮して、想定し得るすべての乗り直しルートの中からルートＡのような最も料金が安くなるルートを直接的に導き出す判定ロジックを規定するのは非常に難しいし、また、そのような判定ロジックを規定できたとしても、割引の適用条件自体が変更されるたびに当該ロジックを変更する必要があるので、その後のメンテナンスが煩雑になる。
【００７４】
この点、本実施形態の処理コンピュータ１１によれば、１つの乗り直しルートだけでなく複数の乗り直しルートを生成するとともに、これらを走行するのにそれぞれ必要な乗り直し料金を算出し、この複数の乗り直し料金に基づいて割安ルートを判定するので、例えば図１０のルートＡ及びＢのような、１つの有料道路区間に対して、乗り直しを行うＩＣの場所や乗り直しの回数が異なる複数の乗り直しルートの中から、最も有利な割安ルートを自動的に探索することができる。
【００７５】
また、本実施形態の処理コンピュータ１１によれば、採り得る乗り直しルートを総当たり的に生成し、生成されたすべての乗り直しルートに対してそれぞれ乗り直し料金を算出するので、算出された各乗り直し料金の中から最小料金を選択するという、簡単な判定ロジックで割安ルートを判定できるとともに、制度の適用条件の変更に対して柔軟に対応できるという利点もある。
【００７６】
すなわち、前記した割引制度の適用条件は任意に変更される可能性があるが、本実施形態では、総当たり的に求めた各乗り直しルートに関してそれぞれ乗り直し料金を算出し、このすべての乗り直し料金に基づいて割安ルートを判定する判定ロジックを採用しているので、仮に割引制度の適用条件が変更されても、交通情報データベース１５に記録された割引情報１７の内容を更新するだけで、変更後の適用条件下での正しい乗り直し料金を算出することができる。
従って、割安ルートの判定ロジック（想定し得るすべての乗り直しルートの中から最低料金のルートを選択するロジック）自体を変更する必要がなく、割引制度の適用条件の変更に対して柔軟に対応することができる。
【００７７】
〔時刻補正処理〕
ところで、前記した通り、本実施形態の処理コンピュータ１１では、ルート取得手段１８が最適経路を演算する経路探索ロジックを実行可能になっており、乗り直し地点を経由地に設定して経路探索ロジックを実行すれば、複数の乗り直しルート（ループ経路Ｒを含む。）を個別に生成することも可能である。しかし、基準ルート以外のすべての乗り直しルートについても経路探索ロジックを実行すると、演算量が大きくなってユーザに対する情報提供が遅れる恐れがある。
【００７８】
特に、本実施形態では、１つの有料道路区間に対して乗り直しルートの組み合わせを総当たり的に生成することから、乗り直し可能な途中のインターチェンジが多数ある場合には、経路探索ロジックを実行すべき乗り直しルートの数が膨大になる可能性があるので、これら膨大数の乗り直しルートについても単純に経路探索ロジックを実行してしまうと、演算量が膨大となってしまう。
【００７９】
そこで、本実施形態の処理コンピュータ１１では、ルート取得手段１８は、基準ルートを決定する場合にのみ経路探索ロジックを実行するようになっている。
すなわち、ルート取得手段１８は、経路探索ロジックにより基準ルートのみを生成し、基準ルートに対応する乗り直しルートについては、基準ルートと同じものを援用することによって経路探索ロジックを実行しないようになっており、これにより、割安ルートの判定のために乗り直しルートを生成するに当たり、演算量が不必要に増大するのを未然に防止している。
【００８０】
もっとも、乗り直しルートトに関して経路探索ロジックを実行しない場合には、そのループ経路Ｒの通行時間（乗り直しに要する走行時間）を考慮しないと、乗り直しＩＣ以降の車両３のループ経路Ｒの通行時間分だけ、各ＩＣへの到着予定時刻がずれてしまい、算出手段１９が算出する乗り直し料金に誤差が生じることがあり、このため、ユーザに対して誤った割安ルートの情報を提供してしまう恐れがある。
【００８１】
そこで、本実施形態では、ルート取得手段１８が、乗り直しルートにおける乗り直しＩＣ以降の各ＩＣへの車両３の到着予定時刻（乗り直し地点において有料道路に復帰する予定時刻を含む。）については、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行し、算出手段１９が、時刻補正された到着予定時刻に基づいて乗り直し料金を算出するようになっている。
図６は、上記時刻補正処理の内容を示す説明図である。
図６において、ＩＣ（Ａ）〜ＩＣ（Ｃ）は有料道路の各インターチェンジを示し、ＩＣ（Ｂ）が乗り直しを行うインターチェンジであるとする。
【００８２】
図６（ａ）は、時刻補正を行わない場合に車両３が各ＩＣ（Ａ）〜ＩＣ（Ｃ）に到着する到着予定時刻を示しており、図例では、ＩＣ（Ａ）の到着予定時刻が１３：５０、ＩＣ（Ｂ）の到着予定時刻が１５：３０、ＩＣ（Ｃ）の到着予定時刻が１６：５０になっている。この場合、車両３がＩＣ（Ｂ）において乗り直しを行うとすると、ＩＣ（Ｂ）の出発予定時刻はその到着予定時刻よりも遅くなっている筈である。
従って、図６（ａ）に示すように、ＩＣ（Ｂ）で乗り直しに要する時間を考慮しない場合には、ＩＣ（Ｃ）の到着予想時刻が１６：５０になり、例えば、ＩＣ（Ｃ）において午後の通勤割引が適用されない。
【００８３】
そこで、図６（ｂ）に示すように、本実施形態の処理コンピュータ１１では、各乗り直しＩＣごとに乗り直しに必要な調整時間（図例では、ＩＣ（Ｂ）について２０分）を予め設定してあり、その調整時間を記憶装置に記憶している。なお、この乗り直しに必要な調整時間は、乗り直し可能な全ＩＣに共通の固定時間であってもよいし、曜日や時間帯等に応じて変動する可変の設定時間であってもよい。
【００８４】
そして、ルート取得手段１８は、車両３がＩＣ（Ｂ）において乗り直しを行う場合には、車両３がＩＣ（Ｂ）をいったん降りる予定時刻にＩＣ（Ｂ）用の調整時間を加算して車両３が当該ＩＣ（Ｂ）に復帰する予定時刻を算出し、ＩＣ（Ｂ）以後の到着予定時刻を補正している。
この場合、車両３のＩＣ（Ｂ）の到着予定時刻（ＩＣ（Ｂ）に復帰する予定時刻）は１５：５０になり、ＩＣ（Ｃ）の到着予定時刻は１７：１０になるので、ＩＣ（Ｃ）において通勤割引が適用可能となる。
【００８５】
〔判定手段での候補選出の優先順位〕
ところで、判定手段２０は、基準ルートと乗り直しルートの中から最低料金の割安ルートを判定するが、この場合において、料金面だけでは優劣がつかない複数の割安ルートが見つかる場合がある。
そこで、本実施形態の判定手段２０は、次の優先順位で割安ルートの判定を行うようになっている。
【００８６】
（１） 最初は最も料金の安いものを優先する。
（２） 次に、同じ料金のルートが複数ある場合には、分割区間数（または乗り直し回数）がより少ない方を優先する。
（３） 更に、料金と分割区間数（または乗り直し回数）が同じ場合には、出発地点により近い乗り直し地点を有する乗り直しルートを他よりも有利なルートとして優先する。
【００８７】
上記の優先順位（２）において、分割区間数（または乗り直し回数）がより少ない方を優先することとしたのは、有料道路から一旦降りて一般道路を走行し、再び有料道路に乗るという乗り直し自体が煩雑な行為であることから、この数が少ないほど、ドライバーの負担がより小さくなるからである。
また、上記の優先順位（３）において、出発地点により近いものを優先することとしたのは、乗り直し地点が異なる複数の乗り直しルートを想定すると、有料道路に対する乗り直しの実行時期が遅いほど、交通状況の変動による乗り直し地点における時刻ずれ（有料道路への乗り直しの予測時刻と実際に有料道路に乗り直した時刻との差）が発生し易いために割引適用が受けられなくなる可能性が高くなり、逆に、乗り直しの実行時期が早いほど、交通状況の変動による時刻ずれが発生し難くいために割引適用を受けられる可能性が高くなると考えられるからである。
【００８８】
〔タイムロスの時間換算〕
本実施形態の算出手段１９において、有料道路に対する乗り直しのために生じるタイムロスを料金に換算し、換算された当該料金を乗り直し料金の算出に反映させるようにしてもよい。
例えば、乗り直しに伴う遅れ時間による換算料金を、１分ごとに５０円とする補正用の換算料金を設定した場合、あるＩＣでの乗り直しに要する走行時間が１０分であるとすると、５００円の補正料金を加算する。
【００８９】
このようにすれば、乗り直しに伴うタイムロスが料金に換算されて乗り直し料金に反映されるので、単純な料金面だけで割安ルートを選択する場合に比べて、実態に即した有意義な判定を行うことができる。
【００９０】
〔第２ルート群を用いた割安ルート探索：第２探索処理〕
図７は、ルート取得手段１８が生成する第２ルート群の一例を示す説明図である。
図７において、ルート（ｔ０）は、有料道路への流入を予定時刻通りに行う予定時刻ルート、すなわち、車両３が現在時刻に出発地点を出て最適経路に沿って走行した場合の予定時刻に、車両３が有料道路に流入するルートを示し、図７に例示するルート（ｔ０）は、第１ルート群に含まれる「乗り直しルート」のうちの１つである。
【００９１】
これに対して、ルート（ｔ１）とルート（ｔ２）は、予定時刻から所定時間（例えば、３０分）内に含まれる範囲において、有料道路への流入を予定時刻から一定の時間間隔（例えば、１０分）ずつずらした前記仮想時刻ルートを示している。
そして、ルート（ｔ１）は、有料道路に対する流入時刻を予定時刻から１０分遅らせた第１の仮想時刻ルートを示し、ルート（ｔ２）は、有料道路に対する流入時刻を予定時刻から２０分遅らせた第２の仮想時刻ルートを示している。
【００９２】
図７の例では、ルート（ｔ０）とルート（ｔ１）の場合には、午後の通勤割引の時間帯条件（午後５時〜８時にＩＣ通過）に適合せず、ＩＣ（Ｃ）における通勤割引の適用がないが、ルート（ｔ２）の場合には、到着予定時刻が１７：０５になって、午後の通勤割引の時間帯条件に適合し、割引適用の対象となる。
そこで、本実施形態の処理コンピュータ１１は、基準ルートと乗り直しルートとからなる前記第１ルート群（予定時刻ルート）を用いた割安ルート探索（第１探索処理）に加えて、更に、前記仮想時刻ルートからなる第２ルート群を用いた割安ルート探索（第２探索処理）を実行する。
【００９３】
すなわち、処理コンピュータ１１のルート取得手段１８は、第１ルート群に含まれる基準ルートと各乗り直しルート（予定時刻ルート）のそれぞれについて、有料道路への流入する予定時刻を敢えて一定の時間間隔（１０分間）だけ遅らせた上記仮想時間ルートを、予定時刻から所定時間（例えば、３０分）内に含まれる範囲において、総当たり的に生成する。
そして、この仮想時刻ルートに基づく仮想時刻料金は、上記の通り、有料道路に対する流入時刻を敢えて遅らせたことが原因で、途中のＩＣ（Ｃ）で有料道路の割引制度が適用され、予定時刻料金（予定時刻ルートを走行する場合の料金）よりも割安になっている場合がある。
【００９４】
そこで、本実施形態の処理コンピュータ１１では、算出手段１９が、予定時刻における基準ルートや乗り直しルート（予定時刻ルート）の通行に必要な料金（予定時刻料金）に加えて、仮想時刻における基準ルートや乗り直しルート（仮想時刻ルート）の通行に必要な料金（仮想時刻料金）も算出し、判定手段２０は、その仮想時刻ルートの中からも、最も安価となるルート（基準ルートの場合もあり得る。）を判定して、これを料金面で割安な割安ルートと判定する。
【００９５】
そして、上記各割安ルートとその通行に必要な料金（割安料金）関する情報は、この情報の出力手段としての前記第２通信部１３等を通じて車載装置４に送信される。
このため、上記情報を受けた車両３の搭乗者（ユーザ）は、予定時刻ルートの中の割安ルートとその料金、１０分ずらした第１の仮想時刻ルートの中の割安ルートとその料金、２０分ずらした第２の仮想時刻ルートの中の割安ルートとその料金、及び、３０分ずらした第３の仮想時刻ルートの中の割安ルートとその料金のそれぞれを、参照することができる。従って、車両３の搭乗者は、これらの割安ルートの中で出発時刻の遅れと料金とを比較検討し、自身が最も適切だと判断したルートを選択することができる。
【００９６】
また、本実施形態では、所定時間（例えば、３０分）の範囲内で総当たり的に求めた各仮想時刻ルートに関してそれぞれ仮想時刻料金を算出し、このすべての仮想時刻料金に基づいて割安ルートを判定する判定ロジックを採用しているので、最適経路に割引率の異なる路線が含まれている場合でも、料金面で有利な割安ルートを正確かつ効率的に探索できるという優れた効果がある。
【００９７】
〔第２探索処理の効果〕
図８は、上記第２探索処理の効果を示すための説明図である。
図８に示す例では、１つの経路に割引条件の異なる路線１と路線２が隣接していると仮定し、その割引条件が例えば次のように定められているものとする。
【００９８】
（路線１の割引条件）
１１：００〜１２：００の間に路線１のＩＣに入るか、路線１のＩＣから出ると料金が３０％割引となる。
（路線２の割引条件）
１２：００〜１３：００の間に路線２のＩＣに入るか、路線２のＩＣから出ると料金が５０％割引となる。
【００９９】
この場合、例えば仮に、路線１の割引条件だけに着目して到着時刻の時間調整を行うとすると、図８のルート（１）の場合には、路線１への入場時刻が間に合わず、路線１で通常料金となってしまうので、路線１への入場時刻を１０分だけ遅らせたルート（２）を採用するのが有利であるということになる。
しかし、ルート（２）を採用すると、路線１については割引料金となるが、その下流側の路線２については、通常料金になってしまう。
【０１００】
この場合、路線１と路線２の走行距離が同じであるとすれば、路線２の方が路線１よりも割引料金が大きいため、却ってトータルの通行料金は高くなってしまうことになる。
また、仮に、各路線１及び２の割引条件をそれぞれ満たすような時間調整を行うことを想定した場合、路線１と路線２においてともに割引適用を受けるようにするには、路線２への入場時刻を翌日まで遅らせなければならず、路線１の退場時刻と路線２の入場時刻の間がほぼ丸１日空いてしまい、非現実的なルートになってしまう。
【０１０１】
これに対して、本実施形態の処理コンピュータ１１では、予定時刻ルートとこれから一定時間間隔（１０分間）でずらした仮想時刻ルートを生成し、これらの各ルートについて算出したすべての予定時刻料金及び仮想時刻料金を出力してユーザに提示することができるので、図８のような、割引条件が異なる路線１，２が含まれている場合でも、ユーザは最終的に最も料金の安いルートを選択可能となり、ユーザにとって有用な情報を提供することができる。
【０１０２】
また、図８に示すような、割引条件が異なる路線１，２が複数跨る最適経路が求まった場合に、各路線１，２の時間帯条件にそれぞれ適合する時間調整を実行して最低料金を模索する判定ロジックでは、上記のような非現実的なルート案内となる可能性があるとともに、判定ロジックそのものが非常に複雑となり実装が困難である。
この点、本実施形態の処理コンピュータ１１では、調整時間（１０分間）を細かくずらした複数の仮想時刻ルートを生成し、これらに対応する仮想時刻料金を算出するので、入場時刻が丸１日異なるような仮想時刻ルートが生成されることがない。このため、非現実的なルート案内が行われることがなく、判定ロジックも単純で実装が簡便であるという利点がある。
【０１０３】
また、各路線１，２の時間帯条件にそれぞれ適合する時間調整を実行して最低料金を模索する判定ロジックでは、仮にそのような判定ロジックを作成できたとしても、路線１又は路線２の割引条件が変更される度に判定ロジックを見直す必要があり、メンテナンスが大変であるという欠点もある。
この点、本実施形態の処理コンピュータ１１では、予定時刻ルートから時間がずれた複数の仮想時刻ルートを先に生成し、その仮想時刻ルートに対応する料金（仮想時刻料金）をすべて算出するので、路線１及び２の割引条件が変更されても必ず正しい料金を求めることができる。このため、判定ロジックを見直す必要がなく、メンテナンスが非常に容易である。
【０１０４】
〔その他の変形例〕
今回開示した各実施形態は本発明の例示であって制限的なものではない。本発明の範囲は、上記実施形態ではなく特許請求の範囲によって示され、特許請求の範囲とその構成と均等な意味及び範囲内での全ての変更が含まれる。
例えば、上記実施形態では、予定時刻ルートと仮想時刻ルートの中からそれぞれ割安ルートを選択し、仮想時刻ごとの割安ルートをユーザに提示するようになっているが、算出手段１９で算出された、予定時刻ルートと仮想時刻ルートの双方を含むすべてのルートの中から、最も安価な割安ルートを処理コンピュータ１１の判定手段２０で予め判定し、予め判定された割安ルートのみをユーザに提示するようにしてもよい。
【０１０５】
また、上記実施形態では、処理コンピュータ１１が、第１ルート群を用いた割安ルート探索（第１探索処理）を行ってから、第２ルート群を用いた割安ルート探索（第２探索処理）実行しているが、第２探索処理を先に実行してから第１探索処理を実行するようにしてもよい。また、第１探索処理と第２探索処理のいずれか一方のみを実行することにしてもよい。
【０１０６】
更に、上記実施形態の第２探索処理（図７）では、予定時刻から一定の時間間隔だけ遅らせた、いわば未来の仮想時刻ルートを生成しているが、予定時刻から一定の時間間隔だけ早めた過去の仮想時刻ルートを生成することにしてもよい。
この場合には、過去の仮想時間ルートに対応する仮想時間料金が割安となる場合があるので、現時点で車両３に搭乗しているユーザに対する割安ルートとして採用することはできないが、例えば翌日以降の旅行計画を立てているユーザに対しては、有用な割安ルートとなり得る。
【０１０７】
また、上記実施形態では、サーバ装置２と車載装置４の間の無線通信を、携帯電話機８を通じて行っているが、この無線通信は、例えば、光ビーコン、無線ＬＡＮ、ＤＳＲＣ（Dedicated Short Range Communication ）等の比較的エリアの狭い路車間通信で行うこともできる。
更に、上記実施形態では処理コンピュータ１１が割安ルートの経路探索を実行しているが、各車両３に搭載された車載装置４が独自に当該経路探索を行うことにしてもよい。
【０１０８】
すなわち、本発明の経路探索装置は、車載装置４の演算装置に組み込むことも可能である。
また、車載装置４の演算装置が基準ルートの探索までを行い、この基準ルートを車載サーバ２に送信してもよい。この場合、車載サーバ２の処理コンピュータ（経路探索装置）１１は、車載装置４から受信した基準ルートに基づいて乗り直しルートや仮想時刻ルートを生成し、この各ルートについてそれぞれ求めた料金に基づいて割安ルートの探索処理を行うことになる。
【０１０９】
更に、上記実施形態では、サーバ装置２と複数の車載装置４とからなるナビゲーションシステム１を例示しているが、当該システム１の構成要素は車載装置４以外のものであってもよい。例えば、サーバ装置２とインターネット通信可能な携帯電話機やノートＰＣ等の端末装置を、上記ナビゲーションシステム１の構成要素とすることもできる。
この場合、出発地点や目的地点の設定作業をＷＥＢサイトの入力画面を通じてユーザが行うことにより、その地点情報をサーバ装置２に送信させることができる。
【０１１０】
〔その他の発明の開示〕
なお、本明細書には、冒頭の特許請求の範囲に記載した請求項だけでなく、以下の請求項１〜３に示す発明も含まれる。
【０１１１】
〔請求項１〕
出発地点から目的地点までの有料道路を含む経路を探索する経路探索ロジックを実行可能なルート生成装置（ルート取得手段１８を有する処理コンピュータ１１）であって、
次の（ａ）の基準ルートのみを前記経路探索ロジックにより生成し、次の（ｂ）の乗り直しルートについては前記基準ルートと同じものを援用することを特徴とするルート生成装置。
（ａ） 車両が有料道路を途中で降りない基準ルート
（ｂ） 車両が有料道路を途中で降りてその降りる地点で同有料道路に復帰する乗り直しルート
【０１１２】
〔請求項２〕
出発地点から目的地点までの有料道路を含む経路を探索する経路探索ロジックを実行可能であり、この経路探索ロジックにより生成可能な次の（ａ）の基準ルート及び（ｂ）の乗り直しルートの中から、料金面で割安となる少なくとも１つの割安ルートを探索するための経路探索装置であって、
前記基準ルートのみを前記経路探索ロジックにより生成し、前記乗り直しルートについては前記基準ルートと同じものを援用することを特徴とする経路探索装置。
（ａ） 車両が有料道路を途中で降りない基準ルート
（ｂ） 車両が有料道路を途中で降りてその降りる地点で同有料道路に復帰する乗り直しルート
【０１１３】
〔請求項３〕
前記乗り直しルートにおける乗り直し地点以降の前記車両の到着予定時刻を、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行する請求項２に記載の経路探索装置。
【０１１４】
上記請求項１及び２に係る発明によれば、経路探索ロジックにより基準ルートのみを生成し、乗り直しルートについては基準ルートと同じものを援用するので、割安ルートの探索のために乗り直しルート（１つでも複数種類でもよい。）を生成するに当たっての経路探索ロジックによる演算量を抑制することができる。
もっとも、当該発明では、乗り直しルートが複数ある場合において、そのすべての乗り直しルートについての援用を強制するものではなく、ユーザに対する情報提供の遅れがさほど問題にならない範囲で、複数ある乗り直しルートのうちの一部のルートに対する経路探索ロジックを実行することにしてもよい。
【０１１５】
一方、乗り直しルートに関して経路探索ロジックを実行しない場合には、そのループ経路の通行時間（すなわち、乗り直しに必要な時間）を考慮しないと、乗り直し地点以降の車両の到着予定時刻（乗り直し地点において有料道路に復帰する予定時刻を含む。）がずれてしまい、乗り直し料金の算出に誤差が生じる。ユーザに対して誤った割安ルートの情報を提供してしまう恐れがある。
しかし、上記請求項３に係る発明によれば、乗り直しに必要な所定時間だけ遅らせる時刻補正を実行するので、そのような誤差が生じるのを未然に回避することができる。
【図面の簡単な説明】
【０１１６】
【図１】ナビゲーションシステムの全体構成を示す概略構成図である。
【図２】ナビゲーションシステムの機能ブロック図である。
【図３】割安ルートの経路探索処理を示すフローチャートである。
【図４】有料道路のインターチェンジの種別を示す説明図である。
【図５】ルート取得手段が生成する第１ルート群の一例を示す説明図である。
【図６】時刻補正処理の内容を示す説明図である。
【図７】ルート取得手段が生成する第２ルート群の一例を示す説明図である。
【図８】第２探索処理の効果を示すための説明図である。
【図９】各種ＥＴＣ割引の内容を示す説明図である。
【図１０】複数の乗り直し料金を対比する場合の効果を示すための説明図である。
【符号の説明】
【０１１７】
１ ナビゲーションシステム
２ サーバ装置
３ 車両
４ 車載装置
５ 交通情報センタ
６ イーサネット網
７ 無線基地局
８ 携帯電話機
１１ 処理コンピュータ（経路探索装置）
１２ 第１通信部
１３ 第２通信部（出力手段）
１４ 会員データベース
１５ 交通情報データベース
１６ 地図データベース
１７ 割引情報
１８ ルート取得手段
１９ 算出手段
２０ 判定手段
ＩＣ インターチェンジ
Ｒ ループ経路
【特許請求の範囲】
【請求項１】
出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索するための経路探索装置であって、
車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するルート取得手段と、
取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートを走行するのにそれぞれ必要な乗り直し料金とを算出する算出手段と、
算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定する判定手段と、
を備えていることを特徴とする経路探索装置。
【請求項２】
前記ルート取得手段は、前記有料道路の途中に位置する乗り直し可能なすべてのインターチェンジの中から選択し得る１又は複数の当該インターチェンジの組み合わせに基づいて、前記有料道路に関して採り得る前記乗り直しルートを総当たり的に生成し、
前記算出手段は、生成されたすべての前記乗り直しルートに対してそれぞれ前記乗り直し料金を算出する請求項１に記載の経路探索装置。
【請求項３】
前記ルート取得手段が取得する複数の前記乗り直しルートの中に、複数のインターチェンジで乗り直しをする乗り直しルートが含まれている請求項１に記載の経路探索装置。
【請求項４】
前記判定手段は、前記料金面で優劣のつかない複数の前記割安ルートがある場合に、この複数の前記割安ルートのうち、前記出発地点により近い乗り直し地点を有する当該乗り直しルートを他よりも有利なルートとして判定を優先させる請求項１〜３のいずれか１項に記載の経路探索装置。
【請求項５】
前記ルート取得手段は、前記出発地点から前記目的地点までの経路を探索する経路探索ロジックを実行可能であり、前記基準ルートのみを前記経路探索ロジックにより生成し、前記乗り直しルートについては前記基準ルートと同じものを援用する請求項１〜４のいずれか１項に記載の経路探索装置。
【請求項６】
前記ルート取得手段は、前記乗り直しルートにおける乗り直し地点以降の前記車両の到着予定時刻を、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行し、
前記算出手段は、時刻補正された前記到着予定時刻に基づいて前記乗り直し料金を算出する請求項５に記載の経路探索装置。
【請求項７】
出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートの探索処理を、コンピュータに実行させるためのコンピュータプログラムであって、
車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するステップと、
取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートを走行するのにそれぞれ必要な乗り直し料金を算出するステップと、
算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定するステップと、
を含むことを特徴とするコンピュータプログラム。
【請求項８】
出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索する経路探索方法であって、
車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得し、
取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートをそれぞれ走行するのに必要な乗り直し料金を算出し、
算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定することを特徴とする経路探索方法。
【請求項１】
出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索するための経路探索装置であって、
車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するルート取得手段と、
取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートを走行するのにそれぞれ必要な乗り直し料金とを算出する算出手段と、
算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定する判定手段と、
を備えていることを特徴とする経路探索装置。
【請求項２】
前記ルート取得手段は、前記有料道路の途中に位置する乗り直し可能なすべてのインターチェンジの中から選択し得る１又は複数の当該インターチェンジの組み合わせに基づいて、前記有料道路に関して採り得る前記乗り直しルートを総当たり的に生成し、
前記算出手段は、生成されたすべての前記乗り直しルートに対してそれぞれ前記乗り直し料金を算出する請求項１に記載の経路探索装置。
【請求項３】
前記ルート取得手段が取得する複数の前記乗り直しルートの中に、複数のインターチェンジで乗り直しをする乗り直しルートが含まれている請求項１に記載の経路探索装置。
【請求項４】
前記判定手段は、前記料金面で優劣のつかない複数の前記割安ルートがある場合に、この複数の前記割安ルートのうち、前記出発地点により近い乗り直し地点を有する当該乗り直しルートを他よりも有利なルートとして判定を優先させる請求項１〜３のいずれか１項に記載の経路探索装置。
【請求項５】
前記ルート取得手段は、前記出発地点から前記目的地点までの経路を探索する経路探索ロジックを実行可能であり、前記基準ルートのみを前記経路探索ロジックにより生成し、前記乗り直しルートについては前記基準ルートと同じものを援用する請求項１〜４のいずれか１項に記載の経路探索装置。
【請求項６】
前記ルート取得手段は、前記乗り直しルートにおける乗り直し地点以降の前記車両の到着予定時刻を、その乗り直しに必要な所定時間だけ遅らせる時刻補正を実行し、
前記算出手段は、時刻補正された前記到着予定時刻に基づいて前記乗り直し料金を算出する請求項５に記載の経路探索装置。
【請求項７】
出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートの探索処理を、コンピュータに実行させるためのコンピュータプログラムであって、
車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得するステップと、
取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートを走行するのにそれぞれ必要な乗り直し料金を算出するステップと、
算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定するステップと、
を含むことを特徴とするコンピュータプログラム。
【請求項８】
出発地点から目的地点までに有料道路を含む経路の中から、料金面で割安となる割安ルートを探索する経路探索方法であって、
車両が前記有料道路を途中で降りない基準ルートと、前記車両が前記有料道路を途中で降りてその降りる地点で同有料道路に復帰する複数の乗り直しルートとを取得し、
取得された前記基準ルートを走行するのに必要な基準料金と、取得された複数の前記乗り直しルートをそれぞれ走行するのに必要な乗り直し料金を算出し、
算出された前記両料金に基づいて、取得された前記基準ルート及び複数の前記乗り直しルートの中から少なくとも１つの前記割安ルートを判定することを特徴とする経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−２２８２（Ｐ２０１０−２２８２Ａ）
【公開日】平成２２年１月７日（２０１０．１．７）
【国際特許分類】
【出願番号】特願２００８−１６１０６３（Ｐ２００８−１６１０６３）
【出願日】平成２０年６月２０日（２００８．６．２０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（５０４１２６１１２）住友電工システムソリューション株式会社 (78)
【Ｆターム（参考）】
【公開日】平成２２年１月７日（２０１０．１．７）
【国際特許分類】
【出願日】平成２０年６月２０日（２００８．６．２０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（５０４１２６１１２）住友電工システムソリューション株式会社 (78)
【Ｆターム（参考）】
[ Back to top ]