(57)【要約】【課題】有料道路での通行料金を的確に反映したコストを算出して推奨経路を好適に決定することが可能な経路探索装置を提供する。【解決手段】システムコントローラ２０は、暫定的に探索した近似解ルート上の高速施設の少なくとも１つを疑似的に通行止めとみなし、料金を考慮しない料金未考慮コストに基づき近似解ルート以外のルートを探索する。そして、システムコントローラ２０は、近似解ルートと探索した近似解以外のルートとのそれぞれの料金を考慮した料金考慮コストを算出し、当該コストが最も低いルートを推奨経路として出力する。【選択図】図４
2018072193.tif 000002
【特許請求の範囲】
【請求項１】
経路を探索する探索手段と、
前記探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御手段と、
前記探索手段によって探索された複数の経路の通行料金を夫々算出する算出手段と、
通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定手段と、を備え、
前記算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する経路探索装置。
【請求項２】
前記制御手段は、前記探索手段で探索された経路に含まれる経路上施設を抽出し、
前記経路上施設のうち少なくとも１つを通行困難施設とすることで、通過する経路上施設の組み合わせが異なる複数の経路を前記探索手段に探索させる請求項１記載の経路探索装置。
【請求項３】
前記制御手段は、前記経路上施設として、通行の有無によって通行料金に影響がある有料道路施設を抽出する請求項２に記載の経路探索装置。
【請求項４】
前記有料道路を含む経路を第１条件に従い分割する分割手段を有し、
前記制御手段は、前記分割手段により分割された分割区間ごとに、通過する経路上施設の組み合わせが異なる複数の経路を前記探索手段に探索させることで、前記分割区間ごとに通行困難施設とすべき経路上施設を決定する請求項２または３に記載の経路探索装置。
【請求項５】
前記制御手段は、前記分割区間ごとに決定した通行困難施設を全て通過しない経路を、前記推奨経路の候補として前記探索手段に探索させる請求項４に記載の経路探索装置。
【請求項６】
前記分割手段は、前記第１条件として、距離、コスト又は前記経路上施設の数の少なくともいずれかに基づき、前記有料道路を含む経路を分割する請求項４または５に記載の経路探索装置。
【請求項７】
前記分割手段は、前記有料道路を含む経路を分割した分割区間内の経路上施設の数が所定数以上存在する場合、当該分割区間をさらに分割する請求項４〜６のいずれか一項に記載の経路探索装置。
【請求項８】
前記分割手段は、前記有料道路を含む経路を異なる分割位置により複数通りに分割し、
前記制御手段は、前記複数通りの各々について、分割区間ごとに通行困難施設とすべき経路上施設を決定することで、前記推奨経路の候補を前記探索手段に探索させ、
前記決定手段は、前記複数通りの各々に対する前記推奨経路の候補の複合コストを比較することで、前記推奨経路を決定する請求項４〜７のいずれか一項に記載の経路探索装置。
【請求項９】
前記分割手段は、前記有料道路を含む経路を、同一の指標の異なる値を用いることで、異なる分割位置により複数通りに分割する請求項８に記載の経路探索装置。
【請求項１０】
前記分割手段は、前記有料道路を含む経路を、異なる指標を用いることで、異なる分割位置により複数通りに分割する請求項８に記載の経路探索装置。
【請求項１１】
経路探索装置が実行する制御方法であって、
経路を探索する探索工程と、
前記探索工程に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御工程と、
前記探索工程によって探索された複数の経路の通行料金を夫々算出する算出工程と、
通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定工程と、を有し、
前記算出工程は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する制御方法。
【請求項１２】
コンピュータが実行するプログラムであって、
経路を探索する探索手段と、
前記探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御手段と、
前記探索手段によって探索された複数の経路の通行料金を夫々算出する算出手段と、
通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定手段
として前記コンピュータを機能させ、
前記算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出するプログラム。
【請求項１３】
請求項１２に記載のプログラムを記憶したことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路を探索する技術に関する。
【背景技術】
【０００２】
従来から、目的地までのルート探索において、高速道路の距離単価に比例したコストを各リンクに付与し、ダイクストラ法により有料道路の料金と所要時間を考慮したルート探索を行う技術が知られている。例えば、特許文献１には、通行料金と所要時間を含む複合コストで経路を探索することにより、料金と時間のバランスを勘案した推奨経路を出力するナビゲーション装置が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１１−７７０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従量制料金所の場合には、距離に応じた料金に関するコストをリンクコストに加えることで、現実の料金の値を探索に反映しつつ、ダイクストラ法によりルート探索を行うことができていた。しかし、２０１６年４月以降、首都圏を中心に、距離によらない均一料金体系が適用されることになったため、この場合には、リンクごとに料金を反映した正確なコストを決定することが困難となる。よって、距離によらない均一料金体系では、現実の料金を的確に反映した探索を従来のダイクストラ法を用いて行うことが難しいという問題がある。
【０００５】
本発明は、上記のような課題を解決するためになされたものであり、有料道路での通行料金を的確に反映したコストを算出して推奨経路を好適に決定することが可能な経路探索装置を提供することを主な目的とする。
【課題を解決するための手段】
【０００６】
請求項に記載の発明は、経路探索装置であって、経路を探索する探索手段と、前記探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御手段と、前記探索手段によって探索された複数の経路の通行料金を夫々算出する算出手段と、通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定手段と、を備え、前記算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。
【０００７】
また、請求項に記載の発明は、経路探索装置が実行する制御方法であって、経路を探索する探索工程と、前記探索工程に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御工程と、前記探索工程によって探索された複数の経路の通行料金を夫々算出する算出工程と、通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定工程と、を有し、前記算出工程は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。
【０００８】
また、請求項に記載の発明は、コンピュータが実行するプログラムであって、経路を探索する探索手段と、前記探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御手段と、前記探索手段によって探索された複数の経路の通行料金を夫々算出する算出手段と、通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定手段として前記コンピュータを機能させ、前記算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。
【図面の簡単な説明】
【０００９】
【図１】各実施例に共通するナビゲーション装置の概略構成である。
【図２】料金テーブルのデータ構造の一例を示す。
【図３】近似解ルート及び近似解ルート上の高速施設を示した図である。
【図４】第１実施例に係るルート探索処理の手順を示すフローチャートである。
【図５】近似解ルート及び近似解ルート上の高速施設を示した図である。
【図６】推奨ルートを決定する際に料金考慮コストを比較するルートを示す。
【図７】第２実施例に係るルート探索処理の手順を示すフローチャートである。
【図８】近似解ルートを多段階に分割する例を示す。
【図９】区間ごとに区間最良ルートとなる疑似通行止めの高速施設の組合せを示す。
【図１０】ルート選択画面の第１表示例を示す。
【図１１】９００円／ｈのテーブルをユーザがタッチパネル等により選択した場合のルート選択画面を示す。
【図１２】ルート選択画面の第２表示例である。
【図１３】ルート選択画面の第３表示例である。
【図１４】変形例１において探索するルートを示す。
【図１５】変形例２に係る経路探索システムの構成を示す。
【発明を実施するための形態】
【００１０】
本発明の好適な実施形態によれば、経路探索装置は、経路を探索する探索手段と、前記探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御手段と、前記探索手段によって探索された複数の経路の通行料金を夫々算出する算出手段と、通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定手段と、を備え、前記算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。
【００１１】
上記経路探索装置は、探索手段と、制御手段と、算出手段と、決定手段とを備える。制御手段は、探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる。算出手段は、探索手段によって探索された複数の経路の通行料金を夫々算出する。このとき、算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。決定手段は、通行料金以外のコスト及び前記通行料金に基づき算出した経路毎のコストである複合コストを比較することで、推奨経路を決定する。ここで、決定手段が複合コストの算出に用いる「通行料金以外のコスト」は、制御手段が探索手段に有料道路を含む経路を探索させる際に用いる「通行料金以外のコスト」と同一の指標で算出されたコストであってもよく、異なる指標で算出されたコストであってもよい。また、「推奨経路」とは、ユーザに推奨する経路であって、コストが最も低い１つの経路であってもよく、コストが所定番目以内に低い複数の経路であってもよい。経路探索装置は、この態様により、走行距離によらずに通行料金が定まる有料道路を含む場合であっても、実際に要する通行料金を的確に反映させた複合コストを経路ごとに算出し、推奨経路を好適に決定することができる。
【００１２】
上記経路探索装置の一態様では、前記制御手段は、前記探索手段で探索された経路に含まれる経路上施設を抽出し、前記経路上施設のうち少なくとも１つを通行困難施設とすることで、通過する経路上施設の組み合わせが異なる複数の経路を前記探索手段に探索させる。この態様により、経路探索装置は、探索手段で最初に探索された経路に加えて、推奨経路となり得る他の経路を好適に探索することができる。
【００１３】
上記経路探索装置の他の一態様では、前記制御手段は、前記経路上施設として、通行の有無によって通行料金に影響がある有料道路施設を抽出する。これにより、経路探索装置は、種々の通行料金となる経路を探索対象とすることができるため、通行料金を加味した複合コストで比較した場合に、推奨経路となり得る経路を好適に探索することができる。
【００１４】
上記経路探索装置の他の一態様では、前記有料道路を含む経路を第１条件に従い分割する分割手段を有し、前記制御手段は、前記分割手段により分割された分割区間ごとに、通過する経路上施設の組み合わせが異なる複数の経路を前記探索手段に探索させることで、前記分割区間ごとに通行困難施設とすべき経路上施設を決定する。この態様により、経路探索装置は、通行困難施設とすべき経路上施設を特定するための処理負荷を好適に低減することができる。
【００１５】
上記経路探索装置の他の一態様では、前記制御手段は、前記分割区間ごとに決定した通行困難施設を全て通過しない経路を、前記推奨経路の候補として前記探索手段に探索させる。この態様により、経路探索装置は、複合コストが最小となる可能性が高い経路を好適に探索することができる。
【００１６】
上記経路探索装置の他の一態様では、前記分割手段は、前記第１条件として、距離、コスト又は前記経路上施設の数の少なくともいずれかに基づき、前記有料道路を含む経路を分割する。この態様により、経路探索装置は、分割区間を定めることができる。
【００１７】
上記経路探索装置の他の一態様では、前記分割手段は、前記有料道路を含む経路を分割した分割区間内の経路上施設の数が所定数以上存在する場合、当該分割区間をさらに分割する。この態様により、経路探索装置は、１つの分割区間内の経路上施設を所定数未満にして処理効率を好適に向上させることができる。
【００１８】
上記経路探索装置の他の一態様では、前記分割手段は、前記有料道路を含む経路を異なる分割位置により複数通りに分割し、前記制御手段は、前記複数通りの各々について、分割区間ごとに通行困難施設とすべき経路上施設を決定することで、前記推奨経路の候補を前記探索手段に探索させ、前記決定手段は、前記複数通りの各々に対する前記推奨経路の候補の複合コストを比較することで、前記推奨経路を決定する。この態様により、経路探索装置は、分割区間の分割位置によって推奨経路の探索結果に影響が生じるのを好適に抑制することができる。
【００１９】
上記経路探索装置の他の一態様では、前記分割手段は、前記有料道路を含む経路を、同一の指標の異なる値を用いることで、異なる分割位置により複数通りに分割する。上記経路探索装置の他の一態様では、前記分割手段は、前記有料道路を含む経路を、異なる指標を用いることで、異なる分割位置により複数通りに分割する。これらの態様により、経路探索装置は、経路を異なる分割位置により複数通りに好適に分割することができる。
【００２０】
本発明に係る他の好適な実施形態では、経路探索装置が実行する制御方法であって、経路を探索する探索工程と、前記探索工程に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御工程と、前記探索工程によって探索された複数の経路の通行料金を夫々算出する算出工程と、通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定工程と、を有し、前記算出工程は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。経路探索装置は、この制御方法を実行することで、走行距離によらずに通行料金が定まる有料道路を含む場合であっても、実際に要する通行料金を的確に反映させた複合コストを経路ごとに算出し、推奨経路を好適に決定することができる。
【００２１】
本発明に係る他の好適な実施形態では、コンピュータが実行するプログラムであって、経路を探索する探索手段と、前記探索手段に、有料道路を含む経路を、当該経路の通行料金以外のコストに基づき探索させる制御手段と、前記探索手段によって探索された複数の経路の通行料金を夫々算出する算出手段と、通行料金以外のコスト及び前記通行料金に基づき算出した前記経路毎のコストである複合コストを比較することで、推奨経路を決定する決定手段として前記コンピュータを機能させ、前記算出手段は、走行距離によらず有料道路の入口施設及び出口施設を含む有料道路施設の組合せに応じた通行料金を算出する。コンピュータは、このプログラムを実行することで、走行距離によらずに通行料金が定まる有料道路を含む場合であっても、実際に要する通行料金を的確に反映させた複合コストを経路ごとに算出し、推奨経路を好適に決定することができる。好適には、このプログラムは、記憶媒体に記憶される。
【実施例】
【００２２】
以下、図面を参照して本発明の好適な実施例について説明する。
【００２３】
［構成例］
図１は、本発明における経路探索装置が適用されたナビゲーション装置１の概略構成を示す。ナビゲーション装置１は、実際の料金に応じたコストを経路毎に的確に計算することで、ユーザに提示すべき推奨経路を決定し、経路選択画面の表示などを行う。図１に示すように、ナビゲーション装置１は、自立測位装置１０、ＧＰＳ受信機１８、システムコントローラ２０、データ記憶ユニット３１、通信装置３８、表示ユニット４０、音声出力ユニット５０及び入力装置６０を備える。
【００２４】
自立測位装置１０は、加速度センサ１１、角速度センサ１２及び距離センサ１３を備える。加速度センサ１１は、例えば圧電素子からなり、車両の加速度を検出し、加速度データを出力する。角速度センサ１２は、例えば振動ジャイロからなり、車両の方向変換時における車両の角速度を検出し、角速度データ及び相対方位データを出力する。距離センサ１３は、車両の車輪の回転に伴って発生されているパルス信号からなる車速パルスを計測する。
【００２５】
ＧＰＳ受信機１８は、複数のＧＰＳ衛星から、測位用データを含む下り回線データを搬送する電波１９を受信する。測位用データは、緯度及び経度情報等から車両の絶対的な位置を検出するために用いられる。
【００２６】
システムコントローラ２０は、インタフェース２１、ＣＰＵ２２、ＲＯＭ２３及びＲＡＭ２４を含んでおり、ナビゲーション装置１全体の制御を行う。システムコントローラ２０は、後述するように、本発明における「探索手段」、「制御手段」、「算出手段」、「決定手段」、「分割手段」、「複合コスト算出手段」、「提示手段」及び本発明におけるプログラムを実行するコンピュータの一例である。
【００２７】
インタフェース２１は、加速度センサ１１、角速度センサ１２及び距離センサ１３並びにＧＰＳ受信機１８とのインタフェース動作を行う。そして、これらから、車速パルス、加速度データ、相対方位データ、角速度データ、ＧＰＳ測位データ、絶対方位データ等をシステムコントローラ２０に入力する。ＣＰＵ２２は、システムコントローラ２０全体を制御する。ＲＯＭ２３は、システムコントローラ２０を制御する制御プログラム等が格納された図示しない不揮発性メモリ等を有する。ＲＡＭ２４は、入力装置６０を介して使用者により予め設定された経路データ等の各種データを読み出し可能に格納したり、ＣＰＵ２２に対してワーキングエリアを提供したりする。
【００２８】
システムコントローラ２０、データ記憶ユニット３１、表示ユニット４０、音声出力ユニット５０及び入力装置６０は、バスライン３０を介して相互に接続されている。
【００２９】
データ記憶ユニット３１は、例えば、ＨＤＤなどの記憶媒体などにより構成され、地図データ３２などのナビゲーション処理に用いられる各種データを記憶する。地図データ３２は、道路に相当するリンクと、道路の接続部分（交差点）に相当するノードとにより表された道路データを含む。
【００３０】
また、データ記憶ユニット３１は、料金テーブル３３を記憶する。料金テーブル３３は、高速道路（有料道路）を走行した際に課せられる料金を、入口及び出口として利用したインターチェンジ等から特定するためのテーブルである。図２は、料金テーブル３３のデータ構造の一例である。図２に示す料金テーブル３３では、入口地点と、出口地点と、経由地点（経由地点１、…）と、割引時間帯（割引時間帯１、…）及び割引率（割引率１、…）と、料金とが関連付けられている。ここで、経由地点は、検札所などの通過の有無で料金に影響がある施設を指す。以後では、料金テーブル３３に登録されている入口地点、出口地点、経由地点を、単に「高速施設」とも呼ぶ。高速施設は、本発明における「有料道路施設」の一例である。
【００３１】
このように、料金テーブル３３には、高速道路を利用する際の料金を決定する各要素の組合せごとに、料金が関連付けられている。よって、システムコントローラ２０は、料金テーブル３３を参照することで、探索したルートが高速道路を含む場合に、高速道路の通行料金を的確に特定することが可能である。
【００３２】
再び図１を参照してナビゲーション装置１の構成を説明する。通信装置３８は、ＶＩＣＳ（登録商標、Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）センタから配信される渋滞情報や、図示しない渋滞情報を配信するサーバ装置から配信される渋滞情報などを受信する。なお、通信装置３８は、システムコントローラ２０の制御に基づき、地図データ３２としてデータ記憶ユニット３１に記憶させる情報を、図示しないサーバ装置から受信してもよい。
【００３３】
表示ユニット４０は、システムコントローラ２０の制御の下、各種表示データをディスプレイなどの表示装置に表示する。具体的には、システムコントローラ２０は、データ記憶ユニット３１から地図データ３２を読み出す。表示ユニット４０は、システムコントローラ２０によってデータ記憶ユニット３１から読み出された地図データ３２に基づく画像を、ディスプレイなどの表示画面上に表示する。表示ユニット４０は、バスライン３０を介してＣＰＵ２２から送られる制御データに基づいて表示ユニット４０全体の制御を行うグラフィックコントローラ４１と、ＶＲＡＭ（Ｖｉｄｅｏ  ＲＡＭ）等のメモリからなり即時表示可能な画像情報を一時的に記憶するバッファメモリ４２と、グラフィックコントローラ４１から出力される画像データに基づいて、液晶、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）等のディスプレイ４４を表示制御する表示制御部４３と、ディスプレイ４４とを備える。ディスプレイ４４は、例えば対角５〜１０インチ程度の液晶表示装置等からなり、車内のフロントパネル付近に装着される。
【００３４】
音声出力ユニット５０は、システムコントローラ２０の制御の下、ＲＡＭ２４等からバスライン３０を介して送られる音声デジタルデータのＤ／Ａ変換を行うＤ／Ａコンバータ５１と、Ｄ／Ａコンバータ５１から出力される音声アナログ信号を増幅する増幅器（ＡＭＰ）５２と、増幅された音声アナログ信号を音声に変換して車内に出力するスピーカ５３とを備えて構成されている。
【００３５】
入力装置６０は、各種コマンドやデータを入力するための、キー、スイッチ、ボタン、リモコン、音声入力装置等から構成されている。入力装置６０は、車内に搭載された当該車載用電子システムの本体のフロントパネルやディスプレイ４４の周囲に配置される。また、ディスプレイ４４がタッチパネル方式である場合には、ディスプレイ４４の表示画面上に設けられたタッチパネルも入力装置６０として機能する。
【００３６】
［第１実施例］
第１実施例では、概略的には、システムコントローラ２０は、暫定的に探索したルート（「近似解ルート」とも呼ぶ。）上の高速施設の少なくとも１つを疑似的に通行止めとみなし、料金を考慮しないコスト（「料金未考慮コスト」とも呼ぶ。）に基づき近似解ルート以外のルートを探索する。そして、システムコントローラ２０は、近似解ルートと探索した近似解以外のルートとのそれぞれの料金を考慮したコスト（「料金考慮コスト」とも呼ぶ。）を算出し、当該コストが最も低いルートを推奨経路として出力する。料金考慮コストは、本発明における「複合コスト」の一例である。
【００３７】
図３（Ａ）は、近似解ルート及び近似解ルート上の高速施設を示した図である。図３（Ａ）は、一般道路と重なる近似解ルートを破線、高速道路と重なる近似解ルートを実線により示している。ここで、近似解ルートは、ダイクストラ法により実行可能な既存のルート探索アルゴリズムにより探索されたルートであって、例えば、所要時間又は／及び距離をリンクごとにコスト（リンクコスト）として設定することで探索されたルートであってもよい。他の例では、近似解ルートは、高速道路の走行距離が料金に比例すると仮定してリンクごとに仮定の料金を反映したリンクコストを設定することで探索されたルートであってもよい。
【００３８】
図３（Ａ）の例では、近似解ルートは、入口及び出口のＩＣを含む４つの高速施設６Ａ〜６Ｄを通過する。この場合、システムコントローラ２０は、高速施設６Ａ〜６Ｄの少なくとも１つを疑似的な通行止めとみなし、料金を考慮しない料金未考慮コストに基づき近似解ルート以外のルートを探索する。この場合、例えば、システムコントローラ２０は、所要時間又は／及び距離をコストの指標とし、経路全体のリンクコストの積算値を料金未考慮コストとして算出する。疑似的に通行止めとする高速施設は、本発明における「通行困難施設」の一例である。
【００３９】
図３（Ｂ）は、高速施設６Ｂを疑似的な通行止めとした場合の料金未考慮コストが最小となるルートを示す。図３（Ｂ）の例では、システムコントローラ２０は、高速施設６Ｂを通過しないルートを探索する。この場合、システムコントローラ２０は、例えば、所要時間又は／及び距離等に基づきリンク毎にリンクコストを設定し、ダイクストラ法などを用いて、リンクコストの積算値が最小となるルートを探索する。そして、システムコントローラ２０は、高速施設６Ａ〜６Ｄの少なくとも１つを疑似的な通行止めとする全パターン（２４−１通り）について、上述のリンクコストの積算値（即ち料金未考慮コスト）が最小となるルートを探索する。
【００４０】
また、システムコントローラ２０は、高速施設６Ａ〜６Ｄの少なくとも１つを疑似的な通行止めとするパターンごとに料金未考慮コストが最小となるルートについて、通過する高速施設及び通過する時間帯等に基づき、料金テーブル３３を参照することで通行料金を算出する。そして、システムコントローラ２０は、算出した料金に対して所定の換算率を乗じることで料金未考慮コストと同じ単位のコストに換算し、換算したコストを料金未考慮コストに加算することで料金考慮コストを算出する。同様に、システムコントローラ２０は、近似解ルートについても、通行料金を算出して料金考慮コストを算出する。そして、システムコントローラ２０は、通行料金を算出したルートのうち最も料金考慮コストが小さいルートを推奨ルートとみなす。
【００４１】
図３（Ｃ）は、料金考慮コストが最も小さいルートを示す。この場合、システムコントローラ２０は、高速施設６Ｂ、６Ｃを疑似的に通行止めとしたときに料金未考慮コストが最小となったルートの料金考慮コストが、近似解ルートや他の高速施設を疑似通行止めにするパターンのルートよりも小さくなると判断し、推奨ルートとして設定する。
図４は、第１実施例に係るルート探索処理の手順を示すフローチャートである。図４のフローチャートでは、一例として、仮の（暫定的な）推奨ルートを「第１候補ルート」、第１候補ルートと比較する対象となるルートを「第２候補ルート」とし、第１及び第２候補ルートの料金考慮コストを比較することで、第１候補ルートを順次更新するアルゴリズムとなっている。
【００４２】
まず、システムコントローラ２０は、近似解ルートを探索する（ステップＳ１００）。次に、システムコントローラ２０は、近似解ルート上に存在する高速施設のリスト（「高速施設リスト」とも呼ぶ。）を作成する（ステップＳ１０１）。近似解ルート上に存在する高速施設は、本発明における「経路上施設」の一例である。そして、システムコントローラ２０は、近似解ルートの料金考慮コストを算出し、第１候補ルートとして設定する（ステップＳ１０２）。この場合、システムコントローラ２０は、近似解ルートの料金未考慮コストの算出後、料金テーブル３３により特定した近似解ルートの通行料金を所定の換算率によりコストに換算し、料金未考慮コストに加算することで、近似解ルートの料金考慮コストを算出する。
【００４３】
次に、システムコントローラ２０は、高速施設リストから、疑似通行止めにする高速施設を少なくとも１つ選択し、料金未考慮コストが最小となる第２候補ルートを探索する（ステップＳ１０３）。この場合、システムコントローラ２０は、料金を考慮することなくリンク毎に距離や所要時間等に応じたコストを決定することができるため、ダイクストラ法により効率的に第２候補ルートを探索することが可能である。
【００４４】
そして、システムコントローラ２０は、ステップＳ１０３で探索した第２候補ルートの料金未考慮コストに、料金テーブル３３を参照して特定した通行料金に応じたコストを加算することで、第２候補ルートの料金考慮コストを算出する（ステップＳ１０４）。
【００４５】
そして、システムコントローラ２０は、第２候補ルートの料金考慮コストが第１候補ルートの料金考慮コストよりも小さいか否か判定する（ステップＳ１０５）。そして、システムコントローラ２０は、第２候補ルートの料金考慮コストが第１候補ルートの料金考慮コストよりも小さい場合（ステップＳ１０５；Ｙｅｓ）、第２候補ルートを第１候補ルートに設定する（ステップＳ１０６）。一方、第２候補ルートの料金考慮コストが第１候補ルートの料金考慮コスト以上の場合（ステップＳ１０５；Ｎｏ）、第１候補ルートを入れ替える必要がないと判断し、ステップＳ１０７へ処理を進める。
【００４６】
次に、システムコントローラ２０は、疑似通行止めにする高速施設の全パターンを実行したか否か判定する（ステップＳ１０７）。即ち、システムコントローラ２０は、高速施設リストの高速施設の少なくとも１つを疑似通行止めとする場合に疑似通行止めとする高速施設の全パターンについて、ステップＳ１０３〜Ｓ１０６の処理を実行したか否か判定する。
【００４７】
そして、システムコントローラ２０は、疑似通行止めにする高速施設の全パターンを実行したと判断した場合（ステップＳ１０７；Ｙｅｓ）、現在の第１候補ルートが最も料金考慮コストが低いルートであるとみなし、第１候補ルートを推奨ルートとして出力する（ステップＳ１０８）。
【００４８】
一方、システムコントローラ２０は、疑似通行止めにする高速施設の全パターンを実行していないと判断した場合（ステップＳ１０７；Ｎｏ）、ステップＳ１０３へ処理を戻す。そして、システムコントローラ２０は、ステップＳ１０３において、ステップＳ１０３〜Ｓ１０６の処理を実行していない疑似通行止めにする高速施設のパターンを対象にルート探索を行い、第２候補ルートを設定する。このように、システムコントローラ２０は、疑似通行止めにする高速施設の全パターンを実行するまで、ステップＳ１０３〜Ｓ１０６の処理を繰り返し実行する。
【００４９】
なお、システムコントローラ２０は、１つのルートを推奨ルートとして出力する代わりに、料金考慮コストが最も低い所定個数分のルートを推奨ルートとして出力してもよい。この場合、システムコントローラ２０は、例えば、第１候補ルートとして最大で所定個数分のルートを設定し、第１候補ルートが所定個数未満の場合には、ステップＳ１０５の判定を行うことなく第２候補ルートを第１候補ルートの１つに加える。一方、システムコントローラ２０は、第１候補ルートが上限の所定個数存在する場合には、料金考慮コストが最も高い第１候補ルートと第２候補ルートとを比較し、第２候補ルートの料金考慮コストの方が低い場合に、比較した第１候補ルートに代えて、第２候補ルートを第１候補ルートに設定する。
【００５０】
［第２実施例］
第２実施例では、システムコントローラ２０は、近似解ルートを複数の区間に分割し、分割した区間ごとに料金考慮コストが最小となる疑似通行止めの高速施設のパターンを決定する。これにより、システムコントローラ２０は、好適にルート探索の実行回数を削減し、近似解ルート上の高速施設数が多い場合であっても、処理時間が増大するのを好適に抑制する。
【００５１】
図５（Ａ）は、５つの高速施設６Ａ〜６Ｅが存在する近似解ルートを示す。この場合、疑似通行止めにする高速施設のパターンは、２５−１（＝３１）通り存在し、第１実施例の場合にはステップＳ１０３〜Ｓ１０６の処理を３１回実行する必要がある。
【００５２】
図５（Ｂ）は、近似解ルートを距離に基づいて３つの区間（区間１〜区間３）に分割した例を示す。この場合、システムコントローラ２０は、各区間でルートに沿った距離が等しくなるように近似解ルートを区間１〜区間３に分割し、かつ、区間１〜区間３のそれぞれに属する高速施設を特定する。図５（Ｂ）の例では、システムコントローラ２０は、区間１に高速施設６Ａ、６Ｂが存在し、区間２に高速施設６Ｃ、６Ｄが存在し、区間３に高速施設６Ｅが存在することを認識する。
【００５３】
その後、システムコントローラ２０は、各区間について、他の区間の高速施設を通行可能とした場合に、対象となる区間の高速施設を疑似通行止めにする全パターンについて、料金未考慮コストが最小となるルートを探索する。これにより、システムコントローラ２０は、区間ごとに、疑似通行止めにすべき高速施設を決定する。
【００５４】
図５（Ｃ）〜（Ｅ）は、区間１に対して疑似通行止めとする高速施設を決定する際に探索するルートを示す。図５（Ｃ）の例では、システムコントローラ２０は、区間１の高速施設６Ａを通行止めとし、区間１内の他の高速施設６Ｂ及び他の区間の高速施設６Ｃ〜６Ｅを通行可として料金未考慮コストが最小となるルートを探索する。また、図５（Ｄ）の例では、システムコントローラ２０は、区間１の高速施設６Ｂを通行止めとし、区間１内の他の高速施設６Ａ及び他の区間の６Ｃ〜６Ｅを通行可として料金未考慮コストが最小となるルートを探索する。さらに、図５（Ｅ）の例では、システムコントローラ２０は、区間１の高速施設６Ａ、６Ｂを通行止めとし、他の区間の高速施設６Ｃ〜６Ｅを通行可として料金未考慮コストが最小となるルートを探索する。
【００５５】
そして、システムコントローラ２０は、図５（Ｃ）〜（Ｅ）の各々のルート探索で得られたルート及び図５（Ｂ）に示す区間１の全高速施設を通行可としたルートから、料金未考慮コストが最小となるルートを決定することで、区間１において疑似通行止めにすべき高速施設を決定する。例えば、システムコントローラ２０は、高速施設６Ｂを疑似通行止めとした場合（即ち図５（Ｄ）の場合）に料金未考慮コストが最小となると判断した場合、区間１では高速施設６Ｂを疑似通行止めにするのが最良であると判断する。同様に、システムコントローラ２０は、区間２、３についても区間１と同様の処理を実行することで、各区間において疑似通行止めにすべき高速施設を決定する。
【００５６】
次に、システムコントローラ２０は、区間ごとに決定した疑似通行止めにする高速施設の組合せに基づき、料金考慮コストが最小となるルートを決定する。
【００５７】
図６（Ａ）〜（Ｅ）は、推奨ルートを決定する際にシステムコントローラ２０が料金考慮コストを比較する各ルートを示す。ここで、図６（Ａ）は、近似解ルートを示し、図６（Ｂ）は、区間１において疑似通行止めにすべきと決定した高速施設（ここでは高速施設６Ｂ）を疑似通行止めにした場合に、料金未考慮コストが最小となるルートを示す。また、図６（Ｃ）は、区間２において疑似通行止めにすべきと決定した高速施設（ここでは高速施設６Ｃ）を疑似通行止めにした場合に、料金未考慮コストが最小となるルートを示し、図６（Ｄ）は、区間３において疑似通行止めにすべきと決定した高速施設（ここでは高速施設６Ｅ）を疑似通行止めにした場合に、料金未考慮コストが最小となるルートを示す。また、図６（Ｅ）は、各区間において疑似通行止めにすべきと決定した高速施設をすべて疑似通行止めにした場合に、料金未考慮コストが最小となるルートを示す。
【００５８】
以後では、図６（Ｂ）〜（Ｄ）に示すように、ある区間において疑似通行止めにすべきと決定した高速施設を疑似通行止めにし、他の区間の高速施設を通行可とした場合に料金未考慮コストが最小となるルートを「区間最良ルート」と呼ぶ。また、図６（Ｅ）に示すように、各区間において疑似通行止めにすべきと決定した高速施設を全て疑似通行止めにした場合に料金未考慮コストが最小となるルートを「全体最良ルート」と呼ぶ。
【００５９】
このように、システムコントローラ２０は、近似解ルート（図６（Ａ）参照）と、各区間に対応する区間最良ルート（図６（Ｂ）〜（Ｄ）参照）と、全体最良ルート（図６（Ｅ）参照）とをそれぞれ探索する。そして、システムコントローラ２０は、これらのルートのうち、料金考慮コストが最小となるルートを推奨ルートに定める。この場合、システムコントローラ２０は、第１実施例と比較して推奨ルートの決定に要する処理負荷を好適に削減することができる。具体的には、第１実施例の場合には、図６（Ａ）に示す近似解ルートが得られた場合、料金見考慮コストに基づく図４のステップＳ１０３のルート探索を３１（＝２５−１）回行うのに対し、第２実施例の場合には料金見考慮コストに基づくルート探索を７（＝（２２−１）＋（２２−１）＋（２１−１））回実行すればよい。即ち、第２実施例の場合には、料金見考慮コストに基づくルート探索を、区間１について３（＝２２−１）通り（両方の高速施設を疑似通行止めにしていないケースは計算済のため除外）、区間２について３（＝２２−１）通り（両方の高速施設を疑似通行止めにしていないケースは計算済のため除外）、区間３について１（＝２１−１）通り（高速施設を疑似通行止めにしていないケースは計算済のため除外）だけ実行すればよい。
【００６０】
ここで、区間の分割方法について補足説明する。
【００６１】
図５及び図６の例では、システムコントローラ２０は、３つの区間に分割したがこれに限定されず、２又は４以上の任意の区間数に定めてもよい。この場合、例えば、システムコントローラ２０は、高速施設リストの高速施設の数が多いほど、上述の区間数を多くするように設定してもよい。他の例では、システムコントローラ２０は、近似解ルートの必要走行距離又は所要時間が長いほど、上述の区間数を多くするように設定してもよい。これらの場合、データ記憶ユニット３１には、上述の区間数を決定するためのマップ又はテーブルが予め記憶されていてもよい。
【００６２】
同様に、図５及び図６の例では、システムコントローラ２０は、各区間内の近似解ルートの距離が均等になるように各区間を区切ったが、各区間を区切るのに用いる指標（尺度）は距離に限定さない。例えば、システムコントローラ２０は、近似解ルートのルート探索時に算出したコストに基づき、各区間の区切りを決定してもよい。この場合、システムコントローラ２０は、近似解ルートのルート探索時に算出したリンクコストの区間ごとの合計値が区間ごとに等しくなるように各区間を決定する。これによっても、システムコントローラ２０は、好適に近似解ルートを分割することができる。他の例では、システムコントローラ２０は、高速施設数に基づき各区間を区切ってもよい。この場合、例えば、システムコントローラ２０は、各区間に属する高速施設の数が同数又は１個差以内となるように各区間を決定する。この場合、例えば、システムコントローラ２０は、各区間に所属させる高速施設を決定した後、異なる区間で隣り合う高速施設間の中間地点（例えば距離又はコストを基準とした中間地点）を、これらの区間の境界位置に定める。これらによっても、システムコントローラ２０は、好適に各区間の境界位置を決定することができる。
【００６３】
図７は、第２実施例においてシステムコントローラ２０が実行するルート探索処理の手順を示すフローチャートである。図７のフローチャートでは、システムコントローラ２０は、一例として、近似解ルートと、各区間の区間最良ルート（図６（Ｂ）〜（Ｄ）参照）との料金考慮コストを順次比較した後に、全体最良ルート（図６（Ｅ）参照）の料金考慮コストを算出して推奨ルートを決定している。ここで、近似解ルートと、各区間の区間最良ルートとの料金考慮コストを順次比較する際、暫定的に料金考慮コストが最も低いルートを第１候補ルートとしている。
【００６４】
まず、システムコントローラ２０は、近似解ルートを探索する（ステップＳ２００）。このとき、好適には、システムコントローラ２０は、区間分割に必要となる出発地から各高速施設までの積算の距離又はコストを記憶しておく。次に、システムコントローラ２０は、高速施設リストを作成する（ステップＳ２０１）。そして、システムコントローラ２０は、近似解ルートの料金考慮コストを算出し、第１候補ルートとして設定する（ステップＳ２０２）。そして、システムコントローラ２０は、近似解ルートを距離又はコスト等に基づき所定の区間数により分割し、高速施設を区間（１〜ｎ；ｎは２以上の整数）ごとのグループに分ける（ステップＳ２０３）。
【００６５】
次に、システムコントローラ２０は、選択した１つの区間ｋ（ｋは初期値が１の整数）について、疑似通行止めにする高速施設の全パターンのルート探索を実行し、料金未考慮コストが最小となるルートを探索する（ステップＳ２０４）。これにより、システムコントローラ２０は、対象の区間ｋにおいて疑似通行止めにすべき高速施設を決定すると共に、当区間ｋに対応する区間最良ルートを特定する。
【００６６】
次に、システムコントローラ２０は、ステップＳ２０４で探索した区間最良ルートについて、料金テーブル３３を参照することで特定した高速道路の通行料金に応じたコストを料金未考慮コストに加算することで、料金考慮コストを算出する（ステップＳ２０５）。
【００６７】
そして、システムコントローラ２０は、ステップＳ２０５で算出した区間最良ルートの料金考慮コストが第１候補ルートの料金考慮コストよりも小さいか否か判定する（ステップＳ２０６）。そして、システムコントローラ２０は、ステップＳ２０４で探索した区間最良ルートの料金考慮コストが第１候補ルートの料金考慮コストよりも小さい場合（ステップＳ２０６；Ｙｅｓ）、ステップＳ２０４で探索した区間最良ルートを第１候補ルートに設定する（ステップＳ２０７）。一方、ステップＳ２０４で探索した区間最良ルートの料金考慮コストが第１候補ルートの料金考慮コスト以上の場合（ステップＳ２０６；Ｎｏ）、第１候補ルートを更新する必要がないと判断し、ステップＳ２０８へ処理を進める。
【００６８】
次に、システムコントローラ２０は、全区間（ｋ＝１〜ｎ）についてステップＳ２０４〜Ｓ２０７の処理を実行したか否か判定する（ステップＳ２０８）。そして、システムコントローラ２０は、全区間についてステップＳ２０４〜Ｓ２０７の処理を実行したと判断した場合（ステップＳ２０８；Ｙｅｓ）、ステップＳ２０９へ処理を進める。一方、システムコントローラ２０は、ステップＳ２０４〜Ｓ２０７の処理を実行していない区間が存在する場合（ステップＳ２０８；Ｎｏ）、ステップＳ２０４へ処理を戻す。この場合、システムコントローラ２０は、区間のインデックスｋを１だけ加算してステップＳ２０４〜Ｓ２０７を再実行する。
【００６９】
次に、ステップＳ２０９では、システムコントローラ２０は、各区間において疑似通行止めにすべきと決定した高速施設を全て疑似通行止めにしたパターン（即ち全体最良パターン）について、料金未考慮コストが最小となるルート（即ち全体最良ルート）を探索する（ステップＳ２０９）。そして、システムコントローラ２０は、ステップＳ２０９で探索した全体最良ルートについて、料金テーブル３３を参照することで特定した全体最良ルート上の高速道路の通行料金に応じたコストを料金未考慮コストに加算することで、料金考慮コストを算出する（ステップＳ２１０）。そして、システムコントローラ２０は、第１候補ルートと全体最良ルートのうち、料金考慮コストが小さい方を推奨ルートとして出力する（ステップＳ２１１）。これにより、システムコントローラ２０は、ルート探索回数を好適に削減しつつ、料金考慮コストが低いルートを推奨ルートとして的確に定めることができる。
【００７０】
［第３実施例］
第３実施例では、システムコントローラ２０は、近似解ルートを多段階に分割可能にする。これにより、システムコントローラ２０は、区間内の高速施設数を調整して処理効率を好適に向上させる。
【００７１】
図８（Ａ）は、高速施設６ａ〜６ｋが存在する近似解ルートを区間１と区間２との２つの区間に分割した例を示す。図８（Ａ）の例では、システムコントローラ２０は、区間１に６つの高速施設６ａ〜６ｆが含まれ、区間２に５つの高速施設６ｇ〜６ｋが含まれるように近似解ルートを２つの区間に分けている。この場合、区間１において疑似通行止めにする高速施設のパターンは、２６（＝６４）通り存在し、区間２において疑似通行止めにする高速道路のパターンは２５（＝３２）通り存在することから、区間数が２の場合には少なくとも９６回以上のルート探索が必要となる。そこで、本実施例では、システムコントローラ２０は、区間内の高速施設数が所定個数（「閾値個数」とも呼ぶ。）以上となる区間をさらに分割する。ここでは、システムコントローラ２０は、閾値個数を３個に設定したものとする。
【００７２】
図８（Ｂ）は、区間１をさらに区間１Ａと区間１Ｂとに分け、区間２をさらに区間２Ａと区間２Ｂとに分けた例を示す。図８（Ｂ）の例では、システムコントローラ２０は、区間１、２にはそれぞれ閾値個数以上の高速施設が存在することから、区間１及び区間２をそれぞれ高速施設数が同一又は１個差になるように再分割している。その結果、区間１Ａには３つの高速施設６ａ〜６ｃが存在し、区間１Ｂには３つの高速施設６ｄ〜６ｆが存在し、区間２Ａには３つの高速施設６ｇ〜６ｉが存在し、区間２Ｂには２つの高速施設６ｊ、６ｋが存在している。
【００７３】
ここで、システムコントローラ２０は、区間１Ａ、区間１Ｂ、区間２Ａについては閾値個数以上の高速施設数が存在することから、これらの区間について再分割を行う。図８（Ｃ）は、図８（Ｂ）の例からさらに区間を分割した場合の各区間と各区間に属する高速施設との関係を示す。図８（Ｃ）の例では、システムコントローラ２０は、区間１Ａを、２つの高速施設６ａ、６ｂを含む区間１Ａａと、１つの高速施設６ｃを含む区間１Ａｂとに分割している。また、システムコントローラ２０は、区間１Ｂを、２つの高速施設６ｄ、６ｅを含む区間１Ｂａと１つの高速施設６ｆを含む区間１Ｂｂとに分割している。また、システムコントローラ２０は、区間２Ａを、２つの高速施設６ｇ、６ｈを含む区間２Ａａと１つの高速施設６ｉを含む区間２Ａｂとに分割している。一方、システムコントローラ２０は、区間２Ｂについては、高速施設数が既に閾値個数未満となっていることから、再分割を行っていない。
【００７４】
そして、システムコントローラ２０は、全ての区間の高速施設数が閾値個数未満になった場合、区間ごとに、高速施設を疑似通行止めにする全パターンについて、料金未考慮コストが最小となる区間最良ルートを探索し、区間ごとに疑似通行止めにすべき高速施設を決定する。
【００７５】
図９（Ａ）は、区間ごとに疑似通行止めにすべき高速施設を決定した結果を反映した図である。図９（Ａ）の例では、区間１Ａａの場合、高速施設６ｂを疑似通行止めとした場合に料金未考慮コストが最小となり、区間１Ａｂ、区間１Ｂａ、区間２Ａａの場合、疑似通行止めとする高速施設を設けない場合に料金未考慮コストが最小となり、区間１Ｂｂの場合、高速施設６ｆを疑似通行止めとした場合に料金未考慮コストが最小となり、区間２Ａｂの場合、高速施設６ｉを疑似通行止めとした場合に料金未考慮コストが最小となり、区間２Ｂの場合、高速施設６ｋを疑似通行止めとした場合に料金未考慮コストが最小となっている。
【００７６】
その後、第１の例では、システムコントローラ２０は、第２実施例の図７のフローチャートを実行することで、推奨ルートを決定する。図９（Ａ）の例では、システムコントローラ２０は、７つの区間が存在すると見なし、図７のフローチャートを実行する。
【００７７】
第２の例では、システムコントローラ２０は、再分割された区間において疑似通行止めにすべきと決定した高速施設を、分割元の区間において疑似通行止めにすべき高速施設として定める。図９（Ｂ）は、区間１Ａ、区間１Ｂ、区間２Ａ、区間２Ｂにおいて疑似通行止めにすべき高速施設を、再分割された各区間１Ａａ、区間１Ａｂ、区間１Ｂａ、区間１Ｂｂ、区間２Ａａ、区間２Ａｂでの区間最良ルートの探索結果に基づき決定した例を示す。
【００７８】
図９（Ｂ）の例では、システムコントローラ２０は、図９（Ａ）に示した区間１Ａａ、１Ａｂにおいて疑似通行止めにすべきと決定した高速施設を、区間１Ａにおいて疑似通行止めにすべき高速施設として定めている。区間１Ｂ、区間２Ａについても同様に、システムコントローラ２０は、疑似通行止めにすべき高速施設を定めている。その後、システムコントローラ２０は、区間１Ａ、区間１Ｂ、区間２Ａ、区間２Ｂに対して第２実施例の図７のフローチャートを実行することで、推奨ルートを決定してもよく、さらにこれらの区間において疑似通行止めにした高速施設の組合せに基づき区間１及び区間２において疑似通行止めにする高速施設を決定してもよい。図９（Ｃ）は、区間１及び区間２において疑似通行止めにすべき高速施設を、再分割された各区間１Ａ、区間１Ｂ、区間２Ａ、区間２Ｂにおいて疑似通行止めにした高速施設の組合せに基づき決定した例を示す。この場合、システムコントローラ２０は、図９（Ｂ）に示した区間１Ａ、１Ｂにおける疑似通行止めにする高速施設の組合せにより、区間１において疑似通行止めにする高速施設を定めている。区間２についても同様に、システムコントローラ２０は、疑似通行止めにする高速施設を定める。その後、システムコントローラ２０は、区間１と区間２の２つの区間が存在するとみなし、図７のフローチャートを実行する。
【００７９】
なお、図８及び図９では、システムコントローラ２０は、近似解ルートを２分割により順次分割したが、これに限らず３以上の分割数により順次分割してもよい。
【００８０】
このように、第３実施例によれば、システムコントローラ２０は、近似解ルートを区間内の高速施設数に応じて区間の再分割の要否を決定し、区間内の高速施設数を閾値個数未満にする。これにより、システムコントローラ２０は、近似解ルート上の高速施設数が多い場合であっても、高速施設数に応じた適切な区間を設定して処理の効率を向上させることができる。
【００８１】
［第４実施例］
第４実施例では、システムコントローラ２０は、料金考慮コストの算出時に用いる料金からコストへの換算率を指定する入力を受け付け、指定された換算率を反映した推奨ルートの表示出力を行う。以後では、一例として、料金考慮コストの単位は時間であるものとする。
【００８２】
図１０は、ルート選択画面の第１表示例を示す。図１０のルート選択画面では、システムコントローラ２０は、料金からコスト（料金ベース時間コスト）への換算率を５００円／ｈ、７００円／ｈ、９００円／ｈと設定した場合にそれぞれ料金考慮コストが低い上位４つのルートを推奨ルートとして提示している。図１０では、システムコントローラ２０は、ルート選択画面上に、料金からコストへの換算率（レート）を５００円／ｈとした場合の上位４つのルートの料金考慮コストを示したテーブル７Ａと、換算率を７００円／ｈとした場合の上位４つのルートの料金考慮コストを示したテーブル７Ｂと、換算率を９００円／ｈとした場合の上位４つのルートの料金考慮コストを示したテーブル７Ｃと、各ルートの概要を示したルート概要図８Ａとを表示させている。
【００８３】
テーブル７Ａ〜７Ｃに示すように、１時間当たりの料金の換算率を変化させることで、ルートＣ、ルートＥなどの高速道路を利用するルートの料金考慮コストが変化する。具体的には、換算率を９００円／ｈとした場合には、換算率を５００円／ｈとする場合よりも料金に対する時間の価値が相対的に上がるため、ルートＣ、ルートＥなどの高速道路を利用するルートの料金考慮コストが下がり、その結果、これらのルートの順位が上がっている。
【００８４】
また、テーブル７Ａ〜７Ｃは選択可能であり、システムコントローラ２０は、選択されたテーブルに対応する料金考慮コストに基づくルートの概要をルート概要図８Ａに表示させている。図１０の例では、システムコントローラ２０は、テーブル７Ａが選択されていることから、換算率が５００円／ｈの場合に最上位となるルートＡを最も太く表示し、ルートＢ、ルートＣ、ルートＤの順に、これらを表す線を徐々に細く表示させている。図１１は、テーブル７Ｃをユーザがタッチパネル等により選択した場合のルート選択画面を示す。この場合、システムコントローラ２０は、選択されたテーブル７Ｃにおいて最上位となるルートＣを最も太くし、ルートＡ、ルートＢ、ルートＥの順に、これらを表す線を徐々に細くしたルート概要図８Ｃを表示させている。その後、ユーザは、例えば、テーブル７Ａ〜７Ｃ又はルート概要図８Ａ、８Ｃにおいて、設定したいルートをタッチパネル等により指定することで、ルートを設定する。
【００８５】
図１２は、ルート選択画面の第２表示例である。図１２の例では、システムコントローラ２０は、ルート選択画面上に、換算率が５００円／ｈのテーブル７Ａと、テーブル７Ａの各ルートの概要を示したルート概要図８Ａと、換算率ボタン２６とを表示させている。そして、システムコントローラ２０は、換算率ボタン２６が選択された場合、換算率を選択するための複数の換算率指定ボタン２８を含む吹き出し２７を表示させる。換算率指定ボタン２８は、ユーザが選択可能な換算率ごとに設けられている。システムコントローラ２０は、現在選択されている換算率とは異なる換算率を示す換算率指定ボタン２８が選択された場合、選択された換算率指定ボタン２８に対応する換算率の料金考慮コストを示すテーブルと、ルート概要図とを、テーブル７Ａ及びルート概要図８Ａに代えてルート選択画面上に表示させる。この態様によれば、システムコントローラ２０は、ユーザが指定した換算率に対応するルート探索結果を、好適にルート選択画面上に表示させることができる。
【００８６】
図１３は、ルート選択画面の第３表示例である。図１３の例では、システムコントローラ２０は、各換算率において最も料金考慮コストが小さいルートを、料金考慮コストと共に示したテーブル７Ｘを表示させている。さらに、システムコントローラ２０は、テーブル７Ｘに列挙したルートの概要を示すルート概要図８Ｘをテーブル７Ｘと共に表示させている。この態様によれば、システムコントローラ２０は、各換算率での料金考慮コストが最小となるルートを容易にユーザに把握させることができる。
【００８７】
［変形例］
以下、第１〜第４実施例に好適な各変形例について説明する。なお、これらの各変形例は、組み合わせて上述の実施例に適用してもよい。
【００８８】
（変形例１）
第２及び第３実施例において、システムコントローラ２０は、全体最良パターンでのルート探索に加えて、隣接区間の境界に存在する高速施設の疑似通行付けの有無を全体最良パターンから変化させたパターンのルート探索をさらに実行してもよい。
【００８９】
図１４（Ａ）は、高速施設６ａ〜６ｋを含む近似解ルートを区間１及び区間２により分割した場合の全体最良パターンを示す。図１４（Ａ）の例では、区間１に対して図７のステップＳ２０４を実行することで探索した区間最良ルートのときに疑似通行止めとした高速施設が高速施設６ｂ、６ｆであり、区間２に対して図７のステップＳ２０４を実行することで探索した区間最良ルートのときに疑似通行止めとした高速施設が高速施設６ｉ、６ｋとなっている。よって、図１４（Ａ）の例では、高速施設６ｂ、６ｆ、６ｉ、６ｋを疑似通行止めとするパターンが全体最良パターンとなっている。
【００９０】
ここで、システムコントローラ２０は、図７のステップＳ２０９において全体最良ルートを探索するのに加えて、区間１及び区間２の境界で隣接する高速施設６ｆ、６ｇの疑似通行止めの有無を全体最良パターンから変更したパターンについても、料金未考慮コストが最小となるルートを探索する。図１４（Ｂ）は、区間１及び区間２の境界で隣接する高速施設６ｆの疑似通行止めの有無を全体最良パターンから変更したパターンを示し、図１４（Ｃ）は、区間１及び区間２の境界で隣接する高速施設６ｇの疑似通行止めの有無を全体最良パターンから変更したパターンを示す。そして、システムコントローラ２０は、図１４（Ｂ）、（Ｃ）に対応するパターンについても料金未考慮コストが最小となるルートを探索し、探索したルートに対して料金考慮コストを算出して推奨ルートとなり得るか否か判定する。
【００９１】
一般に、区間の境界付近に存在する高速施設については、隣接する他の区間の高速施設の疑似通行止めの有無に基づく影響を受けてやすいため、隣接する区間の境界付近において特に全体最良パターンに誤差が生じている可能性がある。以上を勘案し、本変形例では、隣接する区間の境界に存在する高速施設の疑似通行止めの有無を全体最良パターンから変更したパターンについてもルート探索を行う。これにより、ルート探索回数の過度な増加を防ぎつつ、推奨ルートの候補となり得るルートを効率的に探索することができる。
【００９２】
（変形例２）
ナビゲーション装置１が実行するルート探索処理を、ナビゲーション装置１とネットワークを介して通信を行うサーバ装置が実行してもよい。
【００９３】
図１５は、変形例に係る経路探索システムの構成を示す。図１５の例では、経路探索システムは、ナビゲーション装置１と、地図データ３２及び料金テーブル３３を有するサーバ装置３とを有する。
【００９４】
図１５の構成例では、ナビゲーション装置１は、目的地等を指定する入力を受け付けた後、目的地等の入力情報及び現在位置情報をサーバ装置３へ送信する。その後、サーバ装置３は、第１〜第３実施例に基づき、地図データ３２及び料金テーブル３３を参照して推奨ルートを決定し、ルート探索結果を示す情報をナビゲーション装置１へ送信する。また、サーバ装置３は、ナビゲーション装置１に対して第４実施例で説明したルート選択画面の表示情報を送信することで、ルート選択画面をナビゲーション装置１に表示させる。このとき、ナビゲーション装置１は、ルート選択画面で入力された換算率に関する情報をサーバ装置３へ送信する。
【００９５】
なお、本変形例では、サーバ装置３は、本発明における「経路探索装置」の一例であり、サーバ装置３のＣＰＵなどは、本発明における「探索手段」、「制御手段」、「算出手段」、「決定手段」、「分割手段」、「複合コスト算出手段」、「提示手段」及び本発明におけるプログラムを実行するコンピュータの一例である。
【００９６】
（変形例３）
第２及び第３実施例において、システムコントローラ２０は、複数の分割方法により区間を定めて分割方法ごとにルートを算出し、算出したこれらのルートから推奨ルートを決定してもよい。
【００９７】
この場合、第１の例では、システムコントローラ２０は、所定の指標（距離、コスト、高速施設数など）により近似解ルートを分割する際に、１区間当たりの長さを規定する数値を変更することで、異なる分割位置により近似解ルートを区切る。例えば、システムコントローラ２０は、距離に基づき近似解ルートを分割する場合、１区間を５０ｋｍとする分割方法と、１区間を６０ｋｍとする分割する方法とでそれぞれ近似解ルートの分割位置を決定する。この場合、システムコントローラ２０は、同一の指標で３つ以上の数値により近似解ルートを区切り、それぞれの場合で探索したルートから料金考慮コストが最小となるルートを推奨ルートとして決定してもよい。
【００９８】
第２の例では、システムコントローラ２０は、異なる指標により近似解ルートを分割し、それぞれの場合で探索したルートから料金考慮コストが最小となるルートを推奨ルートとして決定する。例えば、システムコントローラ２０は、距離に基づき近似解ルートを複数の区間に分割した場合と、コストに基づき近似解ルートを複数の区間に分割した場合とでそれぞれ第２又は第３実施例のルート探索を行う。そして、システムコントローラ２０は、それぞれの場合のルート探索で得られたルートから、料金考慮コストが最小となるルートを推奨ルートとして決定する。なお、システムコントローラ２０は、３つ以上の指標を用いて近似解ルートを区切り、それぞれの場合で探索したルートから料金考慮コストが最小となるルートを推奨ルートとして決定してもよい。
【００９９】
これらの例によれば、近似解ルートの区切り方によって推奨ルートの結果に影響が生じるのを好適に低減することができる。
【０１００】
（変形例４）
第１実施例において、システムコントローラ２０は、図４のステップＳ１０３のルート探索で用いる料金未考慮コストと、ステップＳ１０４で料金考慮コストを算出する際に用いる料金未考慮コストとで別の指標によりコストを算出してもよい。例えば、前者は、距離を指標としたコストであって、後者は、時間を指標としたコストであってもよい。第２実施例及び第３実施例においても同様に、システムコントローラ２０は、区間最良ルートを探索する際に用いる料金未考慮コストと、料金考慮コストを算出する際に用いる料金未考慮コストとで別の指標によりコストを算出してもよい。
【符号の説明】
【０１０１】
１  ナビゲーション装置
３  サーバ装置
１０  自立測位装置
１２  ＧＰＳ受信機
２０  システムコントローラ
２２  ＣＰＵ
３１  データ記憶ユニット
３８  通信装置
４０  表示ユニット
４４  ディスプレイ
５０  音声出力ユニット
６０  入力装置
【図１】
2018072193.tif 000003
【図２】
2018072193.tif 000004
【図３】
2018072193.tif 000005
【図４】
2018072193.tif 000006
【図５】
2018072193.tif 000007
【図６】
2018072193.tif 000008
【図７】
2018072193.tif 000009
【図８】
2018072193.tif 000010
【図９】
2018072193.tif 000011
【図１０】
2018072193.tif 000012
【図１１】
2018072193.tif 000013
【図１２】
2018072193.tif 000014
【図１３】
2018072193.tif 000015
【図１４】
2018072193.tif 000016
【図１５】
2018072193.tif 000017