出発地から経由地を経由して目的地まで至る案内経路の候補である第1候補経路を探索する第1候補経路探索手段と、前記第1候補経路探索手段により探索された前記第1候補経路の内、前記出発地から前記経由地までの間又は前記経由地から前記目的地までの間の少なくともいずれか一方に高速道路が含まれるか否かを判定する道路判定手段と、前記道路判定手段によって、前記出発地から前記経由地までの間に高速道路が含まれると判定された場合に、高速道路から退出するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する第1対応判定手段と、前記道路判定手段によって、前記経由地から前記目的地までの間に高速道路が含まれると判定された場合に、高速道路へ進入するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する第2対応判定手段と、前記第1対応判定手段又は前記第2対応判定手段によって高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、前記出発地から前記経由地を経由して前記目的地まで至る案内経路の候補である第2候補経路を探索する第2候補経路探索手段と、前記第2候補経路探索手段により探索された前記第2候補経路を案内する候補経路案内手段と、を有することを特徴とする経路探索装置。前記第2候補経路を車両が走行する際に必要な料金をスマートパーキングエリアサービスの利用を考慮して算出する料金算出手段を有し、前記候補経路案内手段は、前記第2候補経路を走行する際に必要な料金とともに案内することを特徴とする請求項1に記載の経路探索装置。前記第1対応判定手段又は前記第2対応判定手段によって高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジの周辺の高速道路上に仮の経由地を設定し、前記出発地から前記仮の経由地を経由して前記目的地まで至る案内経路の候補である第3候補経路を探索する第3候補経路探索手段と、前記出発地から前記経由地の経由を考慮せずに前記目的地まで至る案内経路の候補である第4候補経路を探索する第4候補経路探索手段と、前記第3候補経路と前記第4候補経路とが一致するか否かを判定する経路一致判定手段と、を有し、前記第2候補経路探索手段は、前記経路一致判定手段によって前記第3候補経路と前記第4候補経路とが一致すると判定された場合に、前記第2候補経路の探索を行うことを特徴とする請求項1に記載の経路探索装置。前記第2候補経路に基づいて、前記第2候補経路に従って車両が走行した場合に、前記インターチェンジを退出してから前記経由地を経由して該インターチェンジとスマートパーキングエリアサービスにおいて対応付けられた他のインターチェンジに進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過するか否かを予測する時間超過判定手段を有し、前記候補経路案内手段は、前記時間超過判定手段によってスマートパーキングエリアサービスの利用時間を超過しないと予測された場合に、前記第2候補経路を案内することを特徴とする請求項1乃至請求項3のいずれかに記載の経路探索装置。前記第2候補経路とスマートパーキングエリアサービスの利用時間とに基づいて、前記第2候補経路に従って車両が走行した場合に、前記車両が前記経由地で滞在可能な滞在可能時間を算出する滞在可能時間算出手段を有し、前記候補経路案内手段は、前記第2候補経路を、前記滞在可能時間とともに案内することを特徴とする請求項1乃至請求項4のいずれかに記載の経路探索装置。出発地から経由地を経由して目的地まで至る案内経路の候補である第1候補経路を探索する第1候補経路探索ステップと、前記第1候補経路探索ステップにより探索された前記第1候補経路の内、前記出発地から前記経由地までの間又は前記経由地から前記目的地までの間の少なくともいずれか一方に高速道路が含まれるか否かを判定する道路判定ステップと、前記道路判定ステップによって、前記出発地から前記経由地までの間に高速道路が含まれると判定された場合に、高速道路から退出するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する第1対応判定ステップと、前記道路判定ステップによって、前記経由地から前記目的地までの間に高速道路が含まれると判定された場合に、高速道路へ進入するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する第2対応判定ステップと、前記第1対応判定ステップ又は前記第2対応判定ステップによって高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、前記出発地から前記経由地を経由して前記目的地まで至る案内経路の候補である第2候補経路を探索する第2候補経路探索ステップと、前記第2候補経路探索ステップにより探索された前記第2候補経路を案内する候補経路案内ステップと、を有することを特徴とする経路探索方法。コンピュータに搭載され、出発地から経由地を経由して目的地まで至る案内経路の候補である第1候補経路を探索する第1候補経路探索機能と、前記第1候補経路探索機能により探索された前記第1候補経路の内、前記出発地から前記経由地までの間又は前記経由地から前記目的地までの間の少なくともいずれか一方に高速道路が含まれるか否かを判定する道路判定機能と、前記道路判定機能によって、前記出発地から前記経由地までの間に高速道路が含まれると判定された場合に、高速道路から退出するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する第1対応判定機能と、前記道路判定機能によって、前記経由地から前記目的地までの間に高速道路が含まれると判定された場合に、高速道路へ進入するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する第2対応判定機能と、前記第1対応判定機能又は前記第2対応判定機能によって高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、前記出発地から前記経由地を経由して前記目的地まで至る案内経路の候補である第2候補経路を探索する第2候補経路探索機能と、前記第2候補経路探索機能により探索された前記第2候補経路を案内する候補経路案内機能と、をプロセッサに実行させることを特徴とするコンピュータプログラム。ここで、上記特許文献1及び特許文献2に記載された技術では、上述したスマートパーキングエリアサービスについて考慮した経路探索や料金の算出が行われていなかった。従って、ユーザに対して最適な経路を提供することができない場合があった。本発明は前記従来における問題点を解消するためになされたものであり、スマートパーキングエリアサービスについて考慮することにより、出発地から経由地を経由して目的地へと至る経路を探索する際において、ユーザに対して最適な経路を提供することを可能とした経路探索装置、経路探索方法及びコンピュータプログラムを提供することを目的とする。前記目的を達成するため本願の請求項1に係る経路探索装置1は、出発地51から経由地52を経由して目的地53まで至る案内経路の候補である第1候補経路を探索する第1候補経路探索手段13と、前記第1候補経路探索手段により探索された前記第1候補経路の内、前記出発地から前記経由地までの間又は前記経由地から前記目的地までの間の少なくともいずれか一方に高速道路54が含まれるか否かを判定する道路判定手段13と、前記道路判定手段によって、前記出発地から前記経由地までの間に高速道路が含まれると判定された場合に、前記車両が高速道路から退出するインターチェンジ65がスマートパーキングエリアサービスに対応しているか否かを判定する第1対応判定手段13と、前記道路判定手段によって、前記経由地から前記目的地までの間に高速道路が含まれると判定された場合に、前記車両が高速道路へ進入するインターチェンジ66がスマートパーキングエリアサービスに対応しているか否かを判定する第2対応判定手段13と、前記第1対応判定手段又は前記第2対応判定手段によって前記車両が高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、前記出発地から前記経由地を経由して前記目的地まで至る案内経路の候補である第2候補経路を探索する第2候補経路探索手段13と、前記第2候補経路探索手段により探索された前記第2候補経路を案内する候補経路案内手段と、を有することを特徴とする。また、請求項2に係る経路探索装置1は、請求項1に記載の経路探索装置であって、前記第2候補経路を車両が走行する際に必要な料金をスマートパーキングエリアサービスの利用を考慮して算出する料金算出手段13を有し、前記候補経路案内手段13は、前記第2候補経路を走行する際に必要な料金とともに案内することを特徴とする。また、請求項3に係る経路探索装置1は、請求項1に記載の経路探索装置であって、前記第1対応判定手段13又は前記第2対応判定手段13によって前記車両が高速道路54へ進入又は退出する前記インターチェンジ65、66がスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジの周辺の高速道路上に仮の経由地81を設定し、前記出発地から前記仮の経由地を経由して前記目的地まで至る案内経路の候補である第3候補経路を探索する第3候補経路探索手段13と、前記出発地から前記経由地の経由を考慮せずに前記目的地まで至る案内経路の候補である第4候補経路を探索する第4候補経路探索手段13と、前記第3候補経路と前記第4候補経路とが一致するか否かを判定する経路一致判定手段13と、を有し、前記第2経路探索手段13は、前記経路一致判定手段によって前記第3候補経路と前記第4候補経路とが一致すると判定された場合に、前記第2候補経路の探索を行うことを特徴とする。また、請求項4に係る経路探索装置1は、請求項1乃至請求項3のいずれかに記載の経路探索装置であって、前記第2候補経路に基づいて、前記第2候補経路に従って車両が走行した場合に、前記インターチェンジ65を退出してから前記経由地52を経由して該インターチェンジとスマートパーキングエリアサービスにおいて対応付けられた他のインターチェンジ66に進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過するか否かを予測する時間超過判定手段13を有し、前記候補経路案内手段13は、前記時間超過判定手段によってスマートパーキングエリアサービスの利用時間を超過しないと予測された場合に、前記第2候補経路を案内することを特徴とする。尚、同一名称のインターチェンジであっても、出口と入口はそれぞれ他のインターチェンジとする。また、請求項5に係る経路探索装置1は、請求項1乃至請求項4のいずれかに記載の経路探索装置であって、前記第2候補経路とスマートパーキングエリアサービスの利用時間とに基づいて、前記第2候補経路に従って車両が走行した場合に、前記車両が前記経由地52で滞在可能な滞在可能時間を算出する滞在可能時間算出手段13を有し、前記候補経路案内手段13は、前記第2候補経路を、前記滞在可能時間とともに案内することを特徴とする。また、請求項6に係る経路探索方法は、出発地51から経由地52を経由して目的地53まで至る案内経路の候補である第1候補経路を探索する第1候補経路探索ステップと、前記第1候補経路探索ステップにより探索された前記第1候補経路の内、前記出発地から前記経由地までの間又は前記経由地から前記目的地までの間の少なくともいずれか一方に高速道路54が含まれるか否かを判定する道路判定ステップと、前記道路判定ステップによって、前記出発地から前記経由地までの間に高速道路が含まれると判定された場合に、高速道路から退出するインターチェンジ65がスマートパーキングエリアサービスに対応しているか否かを判定する第1対応判定ステップと、前記道路判定ステップによって、前記経由地から前記目的地までの間に高速道路が含まれると判定された場合に、高速道路へ進入するインターチェンジ66がスマートパーキングエリアサービスに対応しているか否かを判定する第2対応判定ステップと、前記第1対応判定ステップ又は前記第2対応判定ステップによって高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、前記出発地から前記経由地を経由して前記目的地まで至る案内経路の候補である第2候補経路を探索する第2候補経路探索ステップと、前記第2候補経路探索ステップにより探索された前記第2候補経路を案内する候補経路案内ステップと、を有することを特徴とする。更に、請求項7に係るコンピュータプログラムは、コンピュータに搭載され、出発地51から経由地52を経由して目的地53まで至る案内経路の候補である第1候補経路を探索する第1候補経路探索機能と、前記第1候補経路探索機能により探索された前記第1候補経路の内、前記出発地から前記経由地までの間又は前記経由地から前記目的地までの間の少なくともいずれか一方に高速道路54が含まれるか否かを判定する道路判定機能と、前記道路判定機能によって、前記出発地から前記経由地までの間に高速道路が含まれると判定された場合に、高速道路から退出するインターチェンジ65がスマートパーキングエリアサービスに対応しているか否かを判定する第1対応判定機能と、前記道路判定機能によって、前記経由地から前記目的地までの間に高速道路が含まれると判定された場合に、高速道路へ進入するインターチェンジ66がスマートパーキングエリアサービスに対応しているか否かを判定する第2対応判定機能と、前記第1対応判定機能又は前記第2対応判定機能によって高速道路へ進入又は退出する前記インターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、前記出発地から前記経由地を経由して前記目的地まで至る案内経路の候補である第2候補経路を探索する第2候補経路探索機能と、前記第2候補経路探索機能により探索された前記第2候補経路を案内する候補経路案内機能と、をプロセッサに実行させることを特徴とする。前記構成を有する請求項1に記載の経路探索装置によれば、インターチェンジにおけるスマートパーキングエリアサービスの利用が可能な場合には、スマートパーキングエリアサービスの利用を考慮して経路を探索するので、出発地から経由地を経由して目的地へと至る経路を探索する際において、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路探索を、必要な状況でのみ行うことが可能となるので、経路探索時のプロセッサの処理負担を軽減できる。また、請求項2に記載の経路探索装置によれば、スマートパーキングエリアサービスの利用を考慮して探索された経路において車両が走行するのに必要な料金を案内する場合には、スマートパーキングエリアサービスの適用を考慮して料金を算出し、案内するので、スマートパーキングエリアサービスを利用する経路について、走行に必要となる正確な料金を算出することが可能となる。また、請求項3に記載の経路探索装置によれば、出発地から目的地までの案内経路として、高速道路を優先的に走行する経路が適切であるか否かを推定することが可能である。そして、高速道路を優先的に走行する経路が適切であると推定した場合に、スマートパーキングエリアサービスの利用を考慮して経路を探索するので、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路探索を、必要な状況でのみ行うことが可能となるので、経路探索時のプロセッサの処理負担を軽減できる。また、請求項4に記載の経路探索装置によれば、スマートパーキングエリアサービスの利用を考慮して探索された経路が、適切にスマートパーキングエリアサービスを利用することが可能か否かを判定することができ、適切にスマートパーキングエリアサービスを利用することが可能である場合に、スマートパーキングエリアサービスの利用を考慮して探索された経路を案内するので、ユーザに対して最適な経路を提供することが可能となる。また、請求項5に記載の経路探索装置によれば、スマートパーキングエリアサービスの利用を考慮した経路を案内する場合には、経由地で滞在可能な時間についても案内するので、ユーザにスマートパーキングエリアサービスを適切に利用させることが可能となる。また、請求項6に記載の経路探索方法によれば、インターチェンジにおけるスマートパーキングエリアサービスの利用が可能な場合には、スマートパーキングエリアサービスの利用を考慮して経路を探索するので、出発地から経由地を経由して目的地へと至る経路を探索する際において、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路探索を、必要な状況でのみ行うことが可能となるので、経路探索時のプロセッサの処理負担を軽減できる。更に、請求項7に記載のコンピュータプログラムによれば、インターチェンジにおけるスマートパーキングエリアサービスの利用が可能な場合には、スマートパーキングエリアサービスの利用を考慮して経路を探索させるので、出発地から経由地を経由して目的地へと至る経路を探索する際において、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路探索を、必要な状況でのみ行うことが可能となるので、経路探索時のプロセッサの処理負担を軽減できる。以下、本発明に係る経路探索装置をナビゲーション装置に具体化した第1実施形態及び第2実施形態について図面を参照しつつ詳細に説明する。[第1実施形態]先ず、第1実施形態に係るナビゲーション装置1の概略構成について図1を用いて説明する。図1は第1実施形態に係るナビゲーション装置1を示したブロック図である。図1に示すように第1実施形態に係るナビゲーション装置1は、ナビゲーション装置1が搭載された車両の現在位置を検出する現在位置検出部11と、各種のデータが記録されたデータ記録部12と、入力された情報に基づいて、各種の演算処理を行うナビゲーションECU13と、ユーザからの操作を受け付ける操作部14と、ユーザに対して車両周辺の地図や施設の関する施設情報を表示する液晶ディスプレイ15と、経路案内に関する音声ガイダンスを出力するスピーカ16と、記憶媒体であるDVDを読み取るDVDドライブ17と、プローブセンタやVICS登録商標:VehicleInformationandCommunicationSystemセンタ等の情報センタとの間で通信を行う通信モジュール18と、から構成されている。また、ナビゲーション装置1には、ETCElectronicTollCollectionSystem装置19がインターフェースを介して相互に通信可能に接続されている。以下に、ナビゲーション装置1を構成する各構成要素について順に説明する。現在位置検出部11は、GPS21、車速センサ22、ステアリングセンサ23、ジャイロセンサ24等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ22は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションECU13に出力する。そして、ナビゲーションECU13は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記5種類のセンサをナビゲーション装置1が全て備える必要はなく、これらの内の1又は複数種類のセンサのみをナビゲーション装置1が備える構成としても良い。また、データ記録部12は、外部記憶装置及び記録媒体としてのハードディスク図示せずと、ハードディスクに記録された地図情報DB31やスマートパーキング設定データ32や所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド図示せずとを備えている。尚、データ記録部12をハードディスクの代わりにメモリーカードやCDやDVD等の光ディスクにより構成しても良い。ここで、地図情報DB31は、例えば、道路リンクに関するリンクデータ33、ノード点に関するノードデータ34、施設に関する施設データ35、地図を表示するための地図表示データ、各交差点に関する交差点データ、経路を探索するための探索データ、地点を検索するための検索データ等が記憶された記憶手段である。更に、地図情報DB31には、高速道路等の有料道路について、走行区間毎の料金についても記憶されている。また、リンクデータ33としては、リンク長、旅行時間、接続されるノード等に関する情報に加えて、リンクの道路種別高速自動車道路、都市高速道路、自動車専用道路、一般有料道路、取付道路、一般道路、細街路等に関する情報についても記憶される。また、施設データ35としては、ナビゲーション装置1において出発地、経由地、目的地、案内対象等となる施設に関する情報が記憶される。例えば、ホテル、旅館等の宿泊施設、ガソリンスタンド等の給油施設、ショッピングモール、スーパーマーケット、ショッピングセンタ等の商業施設、テーマパーク、ゲームセンタ等の娯楽施設、レストラン、バー、居酒屋等の飲食施設、公共駐車場等の駐車施設、サービスエリア、パーキングエリア、インターチェンジIC等の交通施設、寺院、教会等の宗教施設、美術館、博物館等の公共施設等の施設に関する情報が該当する。また、施設データ35は、施設毎に、施設の識別子である施設番号、施設の名称を示す施設名称、施設のジャンル駐車場、郵便局、インターチェンジ等を示す施設ジャンル、施設の位置を示す位置座標等から構成されている。また、スマートパーキング設定データ32は、スマートパーキングエリアサービスに関する各種設定データである。ここで、スマートパーキングエリアサービスとは、前述したようにパーキングエリアの無い区間において、高速道路外にある施設をパーキングエリアとして利用する為のシステムである図13参照。そして、具体的にスマートパーキング設定データ32としては、インターチェンジ毎に、スマートパーキングエリアサービスへの対応情報と、スマートパーキングエリアサービスにおいて対応付けられた他のICを特定する情報について記憶される。尚、スマートパーキングエリアサービスにおいて対応付けられた他のICとは、スマートパーキングエリアサービスを利用する際に高速道路から退出するICと高速道路へと進入するICとの対応関係例えば、図13ではIC103とIC104の対応関係を特定するデータである。ここで、図2は地図情報DB31に記憶されるスマートパーキング設定データ32の一例について示した図である。図2に示すように、スマートパーキング設定データ32は、インターチェンジの施設名称と、スマートパーキングエリアサービスへの対応情報と、スマートパーキングエリアサービスにおいて対応付けられた他のインターチェンジを特定する情報とから構成される。例えば、○○IC入口は、スマートパーキングエリアサービスに対応しており、○○IC出口又は○×IC出口から高速道路を退出した場合であっても、所定時間以内例えば1時間以内に○○IC入口から再び高速道路に進入すれば、スマートパーキングエリアサービスが適用され、継続して高速道路を走行していたものとみなされることを示す。また、○○IC出口は、スマートパーキングエリアサービスに対応しており、○○IC出口から高速道路を退出した場合であっても、所定時間以内に○○IC入口又は○×IC入口から再び高速道路に進入すれば、スマートパーキングエリアサービスが適用され、継続して高速道路を走行していたものとみなされることを示す。一方、××IC入口や××IC出口は、スマートパーキングエリアサービスに対応していないことを示す。一方、ナビゲーションECUエレクトロニックコントロールユニット13は、ナビゲーション装置1の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのCPU41、並びにCPU41が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるRAM42、制御用のプログラムのほか、後述の経路探索処理プログラム図3参照等が記録されたROM43、ROM43から読み出したプログラムを記憶するフラッシュメモリ44等の内部記憶装置を備えている。尚、ナビゲーションECU13は、処理アルゴリズムとしての各種手段を構成する。例えば、第1経路探索手段は、出発地から経由地を経由して目的地まで至る案内経路の候補である第1候補経路を探索する。道路判定手段は、第1候補経路の内、出発地から経由地までの間又は経由地から目的地までの間の少なくともいずれか一方に高速道路が含まれるか否かを判定する。第1対応判定手段は、道路判定手段によって、出発地から経由地までの間に高速道路が含まれると判定された場合に、車両が高速道路から退出するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する。第2対応判定手段は、道路判定手段によって、経由地から目的地までの間に高速道路が含まれると判定された場合に、車両が高速道路へ進入するインターチェンジがスマートパーキングエリアサービスに対応しているか否かを判定する。第2経路探索手段は、第1対応判定手段又は第2対応判定手段によって車両が高速道路へ進入又は退出するインターチェンジがスマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、出発地から経由地を経由して目的地まで至る案内経路の候補である第2候補経路を探索し、候補経路案内手段は、第2候補経路探索手段により探索された第2候補経路を案内する。第2料金算出手段は、第2候補経路を走行する際に必要な料金をスマートパーキングエリアサービスの利用を考慮して算出する。時間超過判定手段は、第2候補経路に従って車両が走行した場合に、インターチェンジを退出してから経由地を経由して該インターチェンジとスマートパーキングエリアサービスにおいて対応付けられた他のインターチェンジに進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過するか否かを予測する。操作部14は、走行開始地点としての出発地、経由する地点としての経由地及び走行終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ図示せずから構成される。そして、ナビゲーションECU13は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部14は液晶ディスプレイ15の前面に設けたタッチパネルによって構成することもできる。また、マイクと音声認識装置によって構成することもできる。また、液晶ディスプレイ15には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの案内経路、案内経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。また、ナビゲーションECU13が後述の経路探索処理を行った場合には、探索結果に基づいて特定された案内経路の候補である候補経路について表示される。尚、候補経路が複数ある場合には、複数の候補経路についてそれぞれ表示される。また、候補経路が高速道路などの有料道路を走行する場合には、走行に必要となる料金についても併せて表示される図5、図8参照。また、スピーカ16は、ナビゲーションECU13からの指示に基づいて案内経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。また、DVDドライブ17は、DVDやCD等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、地図情報DB31の更新等が行われる。また、通信モジュール18は、交通情報センタ、例えば、VICSセンタやプローブセンタ等から送信された渋滞情報、規制情報、交通事故情報等の各情報から成る交通情報を受信する為の通信装置であり、例えば携帯電話機やDCMが該当する。また、ETC装置19は、ノンストップ自動料金支払いシステムETCにおいて使用される車載器であり、高速道路のICの料金所ゲートに設けられた路上機図示せずと無線通信を行い、ETC装置19のETCカードスロット図示せずに挿入されたETCカードと呼ばれるICカードに対して、有料道路利用料金の課金を行う装置である。また、ETC装置19は、路上機と通信を行うことによって、車両が高速道路へ進入した時刻や退出した時刻、進入及び退出したICを特定する情報についても取得する。続いて、上記構成を有する第1実施形態に係るナビゲーション装置1においてCPU41が実行する経路探索処理プログラムについて図3に基づき説明する。図3は第1実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムはナビゲーション装置1において経路探索を行う為の所定の操作例えば、経由地と目的地の設定操作を受け付けた際に実行され、出発地から目的地までの経路を探索するプログラムである。但し、以下の実施例では、特に、出発地から経由地を経由して目的地へと到る経路を探索する場合について説明する。尚、以下の図3にフローチャートで示されるプログラムは、ナビゲーション装置1が備えているRAM42やROM43に記憶されており、CPU41により実行される。先ず、経路探索処理プログラムではステップ以下、Sと略記する1において、CPU41は、受け付けたユーザの操作に基づいて出発地、経由地及び目的地をそれぞれ設定する。尚、出発地については車両の現在位置としても良い。次に、S2においてCPU41は、前記S1で設定された出発地から経由地を経由して目的地まで至る案内経路の候補である第1候補経路を探索する第1経路探索処理を行う。また、第1経路探索処理では、公知のダイクストラ法を用いる。また、スマートパーキングエリアサービスについては考慮しない。具体的には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストノードコスト及びリンクコストと目的地側から累積された探索コストと、走行に必要な料金に応じた料金コストを加算した値、即ち、コスト加算値が算出される。そして、CPU41は、算出されたコスト加算値が最小になる経路を第1候補経路として特定する。尚、第1候補経路は複数の探索条件例えば、距離優先、有料優先、一般優先毎に特定する構成としても良い。続いて、S3においてCPU41は、前記S2で探索された第1候補経路の内、出発地から経由地までの間又は経由地から目的地までの間の少なくともいずれか一方に高速道路を含むか否かを判定する。尚、前記S3において第1候補経路が高速道路を含むと判定される場合は、図4Aに示すように第1候補経路の内、出発地51から経由地52までの間に高速道路54を含むパターンと、図4Bに示すように経由地52から目的地53までの間に高速道路54を含むパターンと、図4Cに示すように出発地51から経由地52までの間と経由地52から目的地53までの間にそれぞれ高速道路54を含むパターンとが存在する。そして、第1候補経路の内、出発地から経由地までの間又は経由地から目的地までの間の少なくともいずれか一方に高速道路を含むと判定された場合S3:YESには、S6へと移行する。それに対して、第1候補経路に高速道路を含まないと判定された場合S3:NOには、S5へと移行する。S5においてCPU41は、前記S2で探索された第1候補経路を案内する。また、第1候補経路が複数ある場合には、複数の第1候補経路をリスト表示することにより案内する。例えば、図5は前記S2において異なる探索条件で5本の第1候補経路が探索された場合に、前記S5で液晶ディスプレイ15に表示される走行経路案内画面61を示した図である。尚、図5に示す例では探索条件として推奨目的地までの所要時間が短くなることを優先、有料優先有料道路を走行することを優先する、一般優先一般道路を走行することを優先する、距離優先走行距離が短くなることを優先する、別ルート上記以外の経路の5条件を用いた場合を示す。図5に示すように、走行経路案内画面61には、車両周辺の地図画像上に重ねて出発地から目的地までの5本の第1候補経路62が表示される。また、経路の全長、有料道路の距離、料金、目的地までの所要時間に関する情報を、経路毎にリスト状に表示する情報ウィンドウ63についても表示される。それによって、出発地から目的地までの経路とその経路を走行するのに必要な料金等をユーザに対して案内することが可能となる。その後、ユーザは走行経路案内画面61を参照することによって、いずれの経路をナビゲーション装置1の案内経路として設定するかを選択する。そして、ナビゲーション装置1は設定された案内経路に基づいて走行の案内を行う。一方、S6においてCPU41は、データ記録部12に記憶されたスマートパーキング設定データ32図2に基づいて、前記S2で探索された第1候補経路において利用するICの内、少なくとも一以上のICがスマートパーキングエリアサービスに対応するICであるか否かを判定する。具体的には、図4Aに示すように第1候補経路の出発地51から経由地52までの間に高速道路54が含まれる場合には、高速道路54から退出するIC65がスマートパーキングエリアサービスに対応しているか否かを判定する。一方、図4Bに示すように第1候補経路の経由地52から目的地53までの間に高速道路54が含まれる場合には、高速道路54へと進入するIC66がスマートパーキングエリアサービスに対応しているか否かを判定する。また、図4Cに示すように第1候補経路の出発地51から経由地52までの間と経由地52から目的地53までの間にそれぞれ高速道路54が含まれる場合には、高速道路から退出するIC65と高速道路54へと進入するIC65がスマートパーキングエリアサービスに対応しているか否かをそれぞれ判定する。そして、第1候補経路において利用するICの内、少なくとも一以上のICがスマートパーキングエリアサービスに対応するICであると判定された場合S6:YESには、S8へと移行する。それに対して、第1候補経路において利用するICがいずれもスマートパーキングエリアサービスに対応しないICであると判定された場合S6:NOには、S7へと移行する。S7においてCPU41は、第1候補経路において利用するIC具体的には、第1候補経路の出発地から経由地までの間に高速道路が含まれる場合には、高速道路から退出するIC図4ではIC65。第1候補経路の経由地から目的地までの間に高速道路が含まれる場合には、高速道路へと進入するIC図4ではIC65。から所定距離以内にスマートパーキングエリアサービスに対応したICが存在するか否かを判定する。尚、前記S7の判定基準となる所定距離は、第1候補経路の形状に基づいて値を設定することが望ましい。具体的には、図6Aに示すように第1候補経路の出発地51から経由地52までの間に高速道路54が含まれる場合には、出発地51から高速道路54より退出するIC65までの距離L1と、高速道路54より退出するIC65から経由地52までの距離L2を比較し、L1の比率が高い程、所定距離を長く設定する。一方、図6Bに示すように第1候補経路の経由地52から目的地53までの間に高速道路54が含まれる場合には、経由地52から高速道路54へ進入するIC66までの距離L3と、高速道路54へ進入するIC66から目的地53までの距離L4を比較し、L4の比率が高い程、所定距離を長く設定する。尚、第1候補経路に含まれる高速道路と一般道路の距離を比較する構成としても良い。その場合には、高速道路の比率が高い程、所定距離を長く設定する。そして、第1候補経路において利用するICから所定距離以内にスマートパーキングエリアサービスに対応したICが存在すると判定された場合S7:YESには、スマートパーキングエリアサービスを利用した経路の探索が可能であると判定し、S8へと移行する。それに対して、第1候補経路において利用するICから所定距離以内にスマートパーキングエリアサービスに対応したICが存在しないと判定された場合S7:NOには、スマートパーキングエリアサービスを利用した経路の探索が困難であると判定し、S4へと移行する。S4においてCPU41は、前記S2で探索された第1候補経路を走行した場合に必要となる料金を算出する。具体的には、第1候補経路に含まれる有料道路の走行区間と地図情報DB31に記憶された高速道路の料金データに基づいて算出する。尚、第1候補経路が複数ある場合には、複数の第1候補経路毎に算出する。次に、S5においてCPU41は、前記S2で探索された第1候補経路を案内する。また、前記S4で算出された料金についても併せて案内する図5参照。更に、第1候補経路が複数ある場合には、複数の第1候補経路をリスト表示することにより案内する。S8においてCPU41は、スマートパーキングエリアサービスの利用を考慮して前記S1で設定された出発地から経由地を経由して目的地まで至る案内経路の候補である第2候補経路を探索する第2経路探索処理を行う。具体的な処理内容は前記S2と同様である。但し、第2経路探索処理では、スマートパーキングエリアサービスを利用した経路を探索する。具体的には、前記S2と同様に出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストノードコスト及びリンクコストと目的地側から累積された探索コストと、走行に必要な料金に応じた料金コストを加算した値、即ち、コスト加算値が算出される。そして、CPU41は算出されたコスト加算値が最小になる経路を第2候補経路として特定する。但し、加算される料金コストはスマートパーキングエリアサービスを適用した料金コストとなる。即ち、一定条件を満たす高速道路の走行区間については第1経路探索処理よりも加算される料金コストを下げて経路探索を行う。更に、経由地と一定条件を満たす高速道路のICとの間の経路の探索コストを下げて高速道路が経路中に含まれ易くなるようにしても良い。尚、第2候補経路は複数の探索条件例えば、距離優先、有料優先、一般優先毎に特定する構成としても良い。尚、第1候補経路と第2候補経路が同一となる場合、即ち、スマートパーキングエリアサービスの利用を考慮してもコスト加算値が最小となる経路が変化しない場合もある。以下に、S2で実行される第1経路探索処理とS8で実行される第2経路探索処理の相違について図7を用いて説明する。図7では、出発地51からIC67、IC65を介して経由地52へと至り、更にIC66、IC68を介して目的地53へと至る経路を対象としたコスト加算値の算出について例を挙げて説明する。第1経路探索処理では、スマートパーキングエリアサービスを考慮しないので、高速道路54の走行料金が全区間500円であった場合には、IC67~IC65の区間と、IC66~IC68の区間のそれぞれについて料金が発生する。従って、走行に必要な料金は1000円となり、1000円分の料金コストが加算される。一方、第2経路探索処理では、スマートパーキングエリアサービスを考慮するので、高速道路54の走行料金が全区間500円であった場合には、IC67~IC68の区間について料金が発生する。従って、走行に必要な料金は500円となり、500円分の料金コストが加算される。即ち、第2経路探索処理では、同一区間の高速道路を走行する経路であっても、第1経路探索処理と比較して加算される料金コストが小さくなり、図7に示すような高速道路を走行する経路が選ばれ易くなる。次に、S9においてCPU41は、前記S8で探索された第2候補経路に基づいて、第2候補経路に従って車両が走行した場合に、ICを退出してから経由地を経由して該ICとスマートパーキングエリアサービスにおいて対応付けられた他のICに進入するまでの時間例えば、図7に示す例ではIC65を退出してから経由地52を経由してIC66に進入するまでの時間が、スマートパーキングエリアサービスの利用時間例えば1時間を超過するか否かを判定する。尚、ICと経由地の間の走行時間は、リンクの旅行時間から予測する。また、経由地の滞在時間は過去の履歴から予測しても良いし、ユーザに入力させるように構成しても良い。そして、第2候補経路に従って車両が走行した場合に、ICを退出してから経由地を経由して該ICとスマートパーキングエリアサービスにおいて対応付けられた他のICに進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過しないと判定された場合S9:YESには、第2候補経路でスマートパーキングエリアサービスを利用することが可能であると判定し、S10へと移行する。それに対して、第2候補経路に従って車両が走行した場合に、ICを退出してから経由地を経由して該ICとスマートパーキングエリアサービスにおいて対応付けられた他のICに進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過すると判定された場合S9:NOには、第2候補経路ではスマートパーキングエリアサービスを利用することが困難であると判定し、S4へと移行する。その後、上述したように第1候補経路の案内が行われるS4、S5。S10においてCPU41は、前記S8で探索された第2候補経路とスマートパーキングエリアサービスの利用時間とに基づいて、第2候補経路に従って車両が走行した場合に、車両が経由地で滞在可能な滞在可能時間を算出する。具体的には、スマートパーキングエリアサービスの利用時間例えば1時間から、ICから経由地までの走行時間と経由地からICまでの走行時間をそれぞれ減算した時間が滞在可能時間となる。次に、S11においてCPU41は、前記S8で探索された第2候補経路に高速道路等の有料道路を含む場合において、第2候補経路を走行した場合に必要となる料金を算出する。具体的には、第2候補経路に含まれる有料道路の走行区間と地図情報DB31に記憶された高速道路の料金データに基づいて算出する。尚、第2候補経路が複数ある場合には、複数の第2候補経路毎に算出する。続いて、S12においてCPU41は、前記S8で探索された第2候補経路を案内する。また、第2候補経路に高速道路等の有料道路を含む場合においては、前記S11で算出された料金についても併せて案内する。また、第2候補経路がスマートパーキングエリアサービスを利用する場合においては、前記S10で算出された滞在可能時間についても併せて案内する。更に、第2候補経路が複数ある場合には、複数の第2候補経路をリスト表示することにより案内する。例えば、図8は前記S8において異なる探索条件で5本の第2候補経路が探索された場合に、前記S12で液晶ディスプレイ15に表示される走行経路案内画面71を示した図である。尚、図8に示す例では探索条件として推奨目的地までの所要時間が短くなることを優先、有料優先有料道路を走行することを優先する、一般優先一般道路を走行することを優先する、距離優先走行距離が短くなることを優先する、別ルート上記以外の経路の5条件を用いた場合を示す。図8に示すように、走行経路案内画面71には、車両周辺の地図画像上に重ねて出発地から目的地までの5本の第2候補経路72が表示される。また、経路の全長、有料道路の距離、料金、目的地までの所要時間に関する情報を、経路毎にリスト状に表示する情報ウィンドウ73についても表示される。更に、情報ウィンドウ73には、スマートパーキングエリアサービスを利用する経路については前記S10で算出された滞在可能時間についても表示される。それによって、出発地から目的地までの経路とその経路を走行するのに必要な料金、経由地で滞在可能な時間等をユーザに対して案内することが可能となる。ここで、図8に示す第2候補経路72を図5に示す第1候補経路62と比較すると、第2候補経路では推奨の経路と有料優先の経路がスマートパーキングエリアサービスを利用した経路となる。そして、第2候補経路では、推奨の経路は有料優先の経路と一致し、走行に必要な料金についても第1候補経路より少額となる。その後、ユーザは走行経路案内画面71を参照することによって、いずれの経路をナビゲーション装置1の案内経路として設定するかを選択する。そして、ナビゲーション装置1は設定された案内経路に基づいて走行の案内を行う。以上詳細に説明した通り、第1実施形態に係るナビゲーション装置1、ナビゲーション装置1による経路探索方法及びナビゲーション装置1で実行されるコンピュータプログラムでは、出発地から経由地を経由して目的地まで至る第1候補経路を探索しS2、第1候補経路の内、出発地から経由地までの間又は経由地から目的地までの間の少なくともいずれか一方に高速道路が含まれる場合に、高速道路へ進入又は退出するICがスマートパーキングエリアサービスに対応しているか否か判定しS6、スマートパーキングエリアサービスに対応していると判定された場合に、該インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、出発地から経由地を経由して目的地まで至る第2候補経路を探索しS8、探索された第2候補経路を案内するS12ので、インターチェンジにおけるスマートパーキングエリアサービスの利用が可能な場合において、スマートパーキングエリアサービスの利用を考慮して経路を探索することが可能となる。従って、出発地から経由地を経由して目的地へと至る経路を探索する際において、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路探索を、必要な状況でのみ行うことが可能となるので、経路探索時のプロセッサの処理負担を軽減できる。また、スマートパーキングエリアサービスの利用を考慮して探索された第2候補経路において車両が走行するのに必要な料金を案内する場合には、スマートパーキングエリアサービスの適用を考慮して料金を算出し、案内するS11、S12ので、スマートパーキングエリアサービスを利用する経路について、走行に必要となる正確な料金を算出することが可能となる。また、スマートパーキングエリアサービスの利用を考慮して探索された第2候補経路に従って車両が走行した場合に、ICを退出してから経由地を経由して該ICとスマートパーキングエリアサービスにおいて対応付けられた他のICに進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過するか否かを予測しS9、スマートパーキングエリアサービスの利用時間を超過しないと予測された場合に、第2候補経路を案内するので、スマートパーキングエリアサービスの利用を考慮して探索された第2候補経路が、適切にスマートパーキングエリアサービスを利用することが可能か否かを判定することができる。そして、適切にスマートパーキングエリアサービスを利用することが可能である場合に、スマートパーキングエリアサービスの利用を考慮して探索された経路を案内するので、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路を案内する場合には、経由地で滞在可能な時間についても案内するS10、S12ので、ユーザにスマートパーキングエリアサービスを適切に利用させることが可能となる。[第2実施形態]次に、第2実施形態に係るナビゲーション装置について、図9乃至図12に基づいて説明する。尚、第2実施形態に係るナビゲーション装置の概略構成は、第1実施形態に係るナビゲーション装置1とほぼ同じ構成である。但し、後述のように経路探索処理プログラムの処理内容が異なっている。以下の説明において上記図1乃至図8の第1実施形態に係るナビゲーション装置1等の構成と同一符号は、前記第1実施形態に係るナビゲーション装置1等の構成と同一あるいは相当部分を示すものである。以下に、第2実施形態に係るナビゲーション装置1のCPU41が実行する経路探索処理プログラムについて図9に基づき説明する。図9は第2実施形態に係る経路探索処理プログラムのフローチャートである。尚、S101~S107の処理は第1実施形態に係る経路探索処理プログラム図3のS1~S7の処理と同様の処理であるので、説明は省略する。先ず、S108においてCPU41は、前記S102で探索された第1候補経路において利用するIC具体的には、第1候補経路の出発地から経由地までの間に高速道路が含まれる場合には、高速道路から退出するIC図4ではIC65。第1候補経路の経由地から目的地までの間に高速道路が含まれる場合には、高速道路へと進入するIC図4ではIC65。であってスマートパーキングエリアサービスに対応するICの周辺の高速道路上に仮の経由地を設定する。そして、CPU41は、前記S101で設定された出発地から仮の経由地を経由して目的地まで至る案内経路の候補である第3候補経路を探索する第3経路探索処理を行う。尚、前記S108においてCPU41は、第1候補経路において利用するICに直線状で最も近い高速道路上の地点に仮の経由地を設定する。具体的には、図10Aに示すように第1候補経路の出発地51から経由地52までの間に高速道路54が含まれる場合には、出発地51から高速道路54より退出するIC65に直線状で最も近い高速道路54上の地点に仮の経由地81を設定して、出発地51から仮の経由地81を経由して目的地53まで至る経路の探索を行う。一方、図10Bに示すように第1候補経路の経由地52から目的地53までの間に高速道路54が含まれる場合には、経由地52から高速道路54へ進入するIC66に直線状で最も近い高速道路54上の地点に仮の経由地81を設定して、出発地51から仮の経由地81を経由して目的地53まで至る経路の探索を行う。また、前記S109の第3経路探索処理では、公知のダイクストラ法を用いる。具体的には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストノードコスト及びリンクコストと目的地側から累積された探索コストと、走行に必要な料金に応じた料金コストを加算した値、即ち、コスト加算値が算出される。そして、CPU41は、算出されたコスト加算値が最小になる経路を第3候補経路として特定する。尚、第3経路探索では、経由地を高速道路上に設定しているので、第3候補経路は高速道路を意図的に走行する経路となる。続いて、S109においてCPU41は、前記S101で設定された出発地から経由地の経由を考慮せずに目的地まで至る案内経路の候補である第4候補経路を探索する第4経路探索処理を行う。また、前記S109の第4経路探索処理では、S108と同じく公知のダイクストラ法を用いる。具体的な処理内容は前記S108と同様である。その後、S110においてCPU41は、前記S108で探索された第3候補経路と前記S109で探索された第4候補経路を比較し、第3候補経路と第4候補経路が一致するか否かを判定する。例えば、図11に示すように第3候補経路と第4候補経路が一致する場合には、出発地51から目的地53へは本来、高速道路54を優先して走行して行くべきであることが推定できる。即ち、出発地51から目的地53へと高速道路54を意図的に走行する経路を示す第3候補経路と、基本的な出発地51から目的地53までの推奨経路を示す第4候補経路とが同一であるということは、高速道路54を優先的に走行する経路が、出発地51から目的地53までの案内経路としてより適切であると推定できる。従って、後述のようにスマートパーキングエリアサービスの利用を考慮した第2経路探索処理S111を実行する。一方、図12に示すように第3候補経路と第4候補経路が一致しない場合には、出発地51から目的地53へは本来、高速道路54を優先して走行して行くべきでないことが推定できる。即ち、出発地51から目的地53へと高速道路54を意図的に走行する経路を示す第3候補経路と、基本的な出発地51から目的地53までの推奨経路を示す第4候補経路とが同一とならないということは、高速道路54を優先的に走行する経路が、出発地51から目的地53までの案内経路としてより適切であるとは推定できない。従って、後述のようにスマートパーキングエリアサービスの利用を考慮した第2経路探索処理S111は実行せず、第1候補経路の案内を行うS106。そして、第3候補経路と第4候補経路が一致すると判定された場合S110:YESには、S111へと移行する。それに対して、第3候補経路と第4候補経路が一致しないと判定された場合S110:NOには、S104へと移行する。S104においてCPU41は、前記S102で探索された第1候補経路に高速道路等の有料道路を含む場合において、第1候補経路を走行した場合に必要となる料金を算出する。具体的な処理内容は、前記S4と同様であるので説明は省略する。次に、S105においてCPU41は、前記S102で探索された第1候補経路を案内する。また、第1候補経路に高速道路等の有料道路を含む場合においては、前記S104で算出された料金についても併せて案内する。更に、第1候補経路が複数ある場合には、複数の第1候補経路をリスト表示することにより案内する。一方、S111においてCPU41は、前記S101で設定された出発地から経由地を経由して目的地まで至る案内経路の候補である第2候補経路を探索する第2経路探索処理を行う。具体的な処理内容は前記S8と同様であるので説明は省略する。以降のS112~S115の処理は第1実施形態に係る経路探索処理プログラム図3のS9~S12の処理と同様の処理であるので、説明は省略する。以上詳細に説明した通り、第2実施形態に係るナビゲーション装置、ナビゲーション装置による経路探索方法及びナビゲーション装置で実行されるコンピュータプログラムでは、出発地から経由地を経由して目的地まで至る第1候補経路を探索しS102、第1候補経路の内、出発地から経由地までの間又は経由地から目的地までの間の少なくともいずれか一方に高速道路が含まれる場合に、高速道路へ進入又は退出するICがスマートパーキングエリアサービスに対応しているか否か判定するS106。そして、スマートパーキングエリアサービスに対応していると判定された場合に、該ICの周辺の高速道路上に仮の経由地を設定し、出発地から仮の経由地を経由して目的地まで至る第3候補経路を探索しS108、一方で、出発地から経由地の経由を考慮せずに目的地まで至る第4候補経路を探索しS109、第3候補経路と第4候補経路とが一致する場合に、インターチェンジにおけるスマートパーキングエリアサービスの利用を考慮して、出発地から経由地を経由して目的地まで至る第2候補経路を探索しS111、探索された第2候補経路を案内するS115ので、出発地から目的地までの案内経路として、高速道路を優先的に走行する経路が適切であるか否かを推定することが可能である。そして、高速道路を優先的に走行する経路が適切であると推定した場合に、スマートパーキングエリアサービスの利用を考慮して経路を探索するので、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路探索を、必要な状況でのみ行うことが可能となるので、経路探索時のプロセッサの処理負担を軽減できる。また、スマートパーキングエリアサービスの利用を考慮して探索された第2候補経路において車両が走行するのに必要な料金を案内する場合には、スマートパーキングエリアサービスの適用を考慮して料金を算出し、案内するS114、S115ので、スマートパーキングエリアサービスを利用する経路について、走行に必要となる正確な料金を算出することが可能となる。また、スマートパーキングエリアサービスの利用を考慮して探索された第2候補経路に従って車両が走行した場合に、ICを退出してから経由地を経由して該ICとスマートパーキングエリアサービスにおいて対応付けられた他のICに進入するまでの時間が、スマートパーキングエリアサービスの利用時間を超過するか否かを予測しS112、スマートパーキングエリアサービスの利用時間を超過しないと予測された場合に、第2候補経路を案内するので、スマートパーキングエリアサービスの利用を考慮して探索された第2候補経路が、適切にスマートパーキングエリアサービスを利用することが可能か否かを判定することができる。そして、適切にスマートパーキングエリアサービスを利用することが可能である場合に、スマートパーキングエリアサービスの利用を考慮して探索された経路を案内するので、ユーザに対して最適な経路を提供することが可能となる。また、スマートパーキングエリアサービスの利用を考慮した経路を案内する場合には、経由地で滞在可能な時間についても案内するS113、S115ので、ユーザにスマートパーキングエリアサービスを適切に利用させることが可能となる。尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。例えば、第1実施形態及び第2実施形態では、図5や図8に示すように5つの探索条件で探索された第1候補経路や第2候補経路を案内する構成としているが、より少ない経路例えば推奨の経路のみを案内する構成としても良い。また、経由地を2個以上設定する構成としても良い。尚、経由地を2個以上設定した場合には2個目の経由地を目的地とみなすことによって本願発明を適用することが可能である。また、第2実施形態では、第1候補経路において利用するICに直線状で最も近い高速道路上の地点に仮の経由地を設定する構成としているが、利用するICの周辺であれば他の地点に仮の目的地を設定しても良い。また、第1実施形態及び第2実施形態では、本願発明をナビゲーション装置1に適用した例について説明したが、携帯電話機等の携帯端末やパーソナルコンピュータ等に適用することも可能である。また、携帯端末やパーソナルコンピュータに適用した場合には、車両以外に歩行者や二輪車等に対する経路の案内にも本願発明を適用することが可能である。