経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体
【課題】料金割引制度の適用できる経路を探索し、経路探索における選択肢増加を図ること。
【解決手段】経路探索装置１００は、探索部１０１と、判断部１０２と、を備え、情報出力装置１１０は、生成部１１１と出力部１１２と、を備える。探索部１０１は、目的地点までの第１の最適経路を探索し、判断部１０２は、探索部１０１によって探索された第１の最適経路に、走行距離を条件とした料金割引制度を適用している有料道路が含まれている場合に、距離条件を満たしているかを判断する。探索部１０１は、判断部１０２によって第１の最適経路が料金割引制度の距離条件を満たしていないと判断された場合に、距離条件を満たす第２の最適経路を探索する。
【解決手段】経路探索装置１００は、探索部１０１と、判断部１０２と、を備え、情報出力装置１１０は、生成部１１１と出力部１１２と、を備える。探索部１０１は、目的地点までの第１の最適経路を探索し、判断部１０２は、探索部１０１によって探索された第１の最適経路に、走行距離を条件とした料金割引制度を適用している有料道路が含まれている場合に、距離条件を満たしているかを判断する。探索部１０１は、判断部１０２によって第１の最適経路が料金割引制度の距離条件を満たしていないと判断された場合に、距離条件を満たす第２の最適経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、目的地点までの最適経路を探索する経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
近年、車両などの移動体が有料道路を通行する際に徴収される走行料金は、様々な割引サービスの適用が受けられる場合がある。たとえば、ＥＴＣ（Ｅｌｅｃｔｒｏｎｉｃ Ｔｏｌｌ Ｃｏｌｌｅｃｔｉｏｎ Ｓｙｓｔｅｍ）を利用して、ＥＴＣ車載機を搭載した車両が、通過するＥＴＣゲートと、通過する時刻に応じて割引制度の適用（時間帯割引サービス）が受けられる場合などである。
【０００３】
上述した時間帯割引制度の適用を受けるため、有料道路とその有料道路に対する走行料金割引時間帯を記憶して、走行料金割引時間帯に有料道路を通過するように、目的地点へ車両を誘導する車両用ナビゲーション装置の提案がされている（たとえば、下記特許文献１参照。）。
【０００４】
【特許文献１】特開２００１−４１７６０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術は、有料道路に走行距離を条件とした料金割引制度が適用されている場合に、この料金割引制度の距離条件は何ら考慮されていない。したがって、目的地点までの経路で、所定の距離条件を満たせばコストが少なくできるのにも関わらず、距離条件を満たすように車両を誘導しないため、料金割引制度の適用が受けられないという問題が一例として挙げられる。たとえば、有料道路の走行距離が１００キロメートル未満で料金割引制度の適用を受けられる場合、料金割引制度の適用を受けるために、目的地点までの有料道路の距離が１２０キロメートルであっても、１００キロメートル未満の区間は有料道路を走行して、残りの区間は一般道路を走行するよう誘導すればよい。しかしながら、上述の問題により、距離条件を満たすように車両を誘導しないため、有料道路を１２０キロメートル走行して、料金割引制度の適用を受けられない。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するため、請求項１の発明にかかる経路探索装置は、目的地点までの第１の最適経路を探索する探索手段と、走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する判断手段と、を備え、前記探索手段は、前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索することを特徴とする。
【０００７】
また、請求項５の発明にかかる経路探索方法は、目的地点までの第１の最適経路を探索する第１工程と、走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれているかを判断する第２工程と、前記第２工程によって走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する第３工程と、前記第３工程によって前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索する第４工程と、を含むことを特徴とする。
【０００８】
また、請求項６の発明にかかる経路探索プログラムは、請求項５に記載の経路探索方法をコンピュータに実行させることを特徴とする。
【０００９】
また、請求項７の発明にかかるコンピュータに読み取り可能な記録媒体は、請求項６に記載の経路探索プログラムを記録したことを特徴とする。
【発明を実施するための最良の形態】
【００１０】
以下に添付図面を参照して、この発明にかかる経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体の好適な実施の形態を詳細に説明する。
【００１１】
（実施の形態）
（経路探索装置の機能的構成）
図１を用いて、本実施の形態にかかる経路探索装置の機能的構成について説明する。図１は、本実施の形態にかかる経路探索装置の機能的構成の一例を示すブロック図である。
【００１２】
図１において、経路探索装置１００は、探索部１０１と、判断部１０２と、を含んで構成されている。そして、経路探索装置１００は情報を他の装置に出力する。本実施の形態においては、経路探索装置１００は情報出力装置１１０に出力するものとする。この情報出力装置１１０は、生成部１１１と、出力部１１２と、を含んで構成されている。
【００１３】
探索部１０１は、目的地点までの最適経路を探索する。経路探索は、たとえば、図示しない記録媒体や通信部から取得する地図情報や移動体の位置に関する情報に基づいておこなう。そして、探索した最適経路（第１の最適経路）に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれており、且つ、当該経路（第１の最適経路）が料金割引制度の距離条件を満たしていないと後述する判断部１０２によって判断された場合に、有料道路の入口または出口を変更するなどして料金割引制度の距離条件を満たす目的地点までの最適経路（第２の最適経路）を探索する。
【００１４】
判断部１０２は、探索部１０１により探索された最適経路に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれているか否かを判断する。そして、当該最適経路に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれている場合に、当該最適経路がこの料金割引制度の距離条件を満たしているか否かを判断する。この判断結果を探索部１０１に出力する。
【００１５】
生成部１１１は、経路探索装置１００から探索部１０１によって探索された最適経路の情報などを取得し、この取得した情報に基づいて各種情報を生成する。生成する情報は、たとえば、目的地点までの最適経路を示す情報、目的地点までの所要時間の情報、目的地点に到達するのに必要な走行料金の情報などである。なお、最適経路に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれている場合であって当該経路について料金割引制度の距離条件を満たしていない場合に、この経路についての上記の情報と料金割引制度の距離条件を満たす最適経路についての上記の情報をそれぞれについて生成してもよい。
【００１６】
出力部１１２は、生成部１１１によって生成された情報を出力する。情報の出力は、たとえば音声で出力したり、図示しない表示部に画像で出力したりする。
【００１７】
（経路探索装置の処理の内容）
つぎに、本実施の形態にかかる経路探索装置１００の処理の内容について説明する。図２は、本実施の形態にかかる経路探索装置の処理の内容を示すフローチャートである。図２のフローチャートにおいて、まず、探索部１０１は、目的地点までの第１の最適経路を探索する（ステップＳ２０１）。
【００１８】
つづいて、判断部１０２は、ステップＳ２０１において探索された第１の最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれているか否かを判断する（ステップＳ２０２）。走行距離を条件とする料金割引制度は、有料道路を走行する際、所定の距離条件を満たすと、当該有料道路の走行料金の割引を受けることのできる制度である。なお、図２において、走行距離を条件とする料金割引制度を「距離割引制度」と表す。
【００１９】
ステップＳ２０２において、第１の最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれていると判断した場合（ステップＳ２０２：Ｙｅｓ）、判断部１０２は、第１の最適経路がこの料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ２０３）。
【００２０】
ステップＳ２０３において、判断部１０２が第１の最適経路が距離条件を満たしていないと判断した場合（ステップＳ２０３：Ｎｏ）、探索部１０１は距離条件を満たす第２の最適経路を探索する（ステップＳ２０４）。第２の最適経路の探索は、たとえば、有料道路の入口または出口の少なくとも一つを変更しておこなう。この際に、有料道路の入口または出口の少なくとも一つを変更して複数の経路を探索し、この複数の経路のうち距離条件を満たし且つ所定の条件を満たす一の経路を第２の最適経路としてもよい。なお、前述の所定の条件は、たとえば、最短距離や最短時間などでもよい。また、有料道路の入口や出口を変更する際に、たとえば入口と出口のうち都市部に近い側の入口または出口は変更せずに郊外の方のみを変更する、などの選定条件に基づいて出口や入口を変更して第２の最適経路を探索するようにしてもよい。
【００２１】
ステップＳ２０２において、判断部１０２が第１の最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれていないと判断した場合（ステップＳ２０２：Ｎｏ）、ステップＳ２０３において、判断部１０２が第１の最適経路が距離条件を満たしていると判断した場合（ステップＳ２０３：Ｙｅｓ）、およびステップＳ２０４において第２の最適経路が探索された場合は、情報出力装置１１０に、探索された経路の情報を出力し（ステップＳ２０５）、一連の処理を終了する。そして、情報出力装置１１０の生成部１１１は、この経路の情報に基づいて、目的地点までの最適経路を示す情報や目的地点までの所要時間の情報、目的地点に到達するのに必要な走行料金の情報などの各種情報を生成し、情報出力装置の出力部１１２がこれらの情報を出力する。
【００２２】
以上説明したように、本実施の形態にかかる経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体によれば、探索された最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれている場合に、距離条件を満たす最適経路を探索することができる。したがって、ユーザは、探索された最適経路の情報を情報出力装置等を介して取得して、走行距離を条件とする料金割引制度の適用を受けることができる最適経路の確認することができ、また、ナビゲーション装置に案内してもらう経路として当該最適経路を選択することができる。さらに、ユーザは、料金割引制度の距離条件を満たす最適経路に基づいて走行することで走行料金の低減を図ることができる。
【実施例】
【００２３】
以下に、本発明の実施例について説明する。本実施例では、たとえば、車両（四輪車、二輪車を含む）などの移動体に搭載されるナビゲーション装置によって、本発明の経路探索装置を実施した場合の一例について説明する。
【００２４】
（ナビゲーション装置のハードウェア構成）
図３を用いて、本実施例にかかるナビゲーション装置のハードウェア構成について説明する。図３は、本実施例にかかるナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【００２５】
図３において、ナビゲーション装置３００は、車両などの移動体に搭載されており、ナビゲーション制御部３０１と、ユーザ操作部３０２と、表示部３０３と、位置取得部３０４と、記録媒体３０５と、記録媒体デコード部３０６と、音声出力部３０７と、通信部３０８と、経路探索部３０９と、経路誘導部３１０と、音声生成部３１１と、スピーカ３１２と、によって構成される。
【００２６】
ナビゲーション制御部３０１は、ナビゲーション装置３００全体を制御する。ナビゲーション制御部３０１は、たとえば所定の演算処理を実行するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や、各種制御プログラムを格納するＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、および、ＣＰＵのワークエリアとして機能するＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などによって構成されるマイクロコンピュータなどによって実現することができる。
【００２７】
ナビゲーション制御部３０１は、経路誘導に際し、位置取得部３０４によって取得された現在位置に関する情報と、記録媒体３０５から記録媒体デコード部３０６を経由して得られた地図情報に基づいて、地図上のどの位置を走行しているかを算出し、算出結果を表示部３０３へ出力する。また、ナビゲーション制御部３０１は、経路誘導に際し、経路探索部３０９、経路誘導部３１０、音声生成部３１１との間で経路誘導に関する情報の入出力をおこない、その結果得られる情報を表示部３０３および音声出力部３０７へ出力する。
【００２８】
ユーザ操作部３０２は、ユーザがリモコンやスイッチ、タッチパネルなどの操作手段を操作して入力した情報を取得してナビゲーション制御部３０１に対して出力する。
【００２９】
表示部３０３は、たとえば、ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）、ＴＦＴ液晶ディスプレイ、有機ＥＬディスプレイ、プラズマディスプレイなどを含む。表示部３０３は、具体的には、たとえば、映像Ｉ／Ｆ（インターフェース）や映像Ｉ／Ｆに接続された映像表示用のディスプレイ装置によって構成することができる。映像Ｉ／Ｆは、具体的には、たとえば、ディスプレイ装置全体の制御をおこなうグラフィックコントローラと、即時表示可能な画像情報を一時的に記憶するＶＲＡＭ（Ｖｉｄｅｏ ＲＡＭ）などのバッファメモリと、グラフィックコントローラから出力される画像情報に基づいて、ディスプレイ装置を表示制御する制御ＩＣなどによって構成される。表示部３０３には、交通情報や地図情報や経路誘導に関する情報、その他各種情報が表示される。
【００３０】
位置取得部３０４は、ＧＰＳレシーバおよび各種センサーから構成され、移動体の現在位置（ナビゲーション装置３００の現在位置）の情報を取得する。ＧＰＳレシーバは、ＧＰＳ衛星からの電波を受信し、ＧＰＳ衛星との幾何学的位置を求める。なお、ＧＰＳとは、Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍの略称であり、４つ以上の衛星からの電波を受信することによって地上での位置を正確に求めるシステムである。ＧＰＳレシーバは、ＧＰＳ衛星からの電波を受信するためのアンテナ、受信した電波を復調するチューナーおよび復調した情報に基づいて現在位置を算出する演算回路などによって構成される。
【００３１】
各種センサーは、車速センサーや角速度センサー、加速度センサーなど移動体またはナビゲーション装置３００に搭載された各種センサーであり、これらのセンサーから出力される情報から、移動体の移動変位、移動速度、移動方向を求める。このように、ＧＰＳレシーバの受信電波から得られた情報と合わせて、上記各種センサーの出力情報を用いることによって、より高い精度で移動体の位置の認識をおこなうことができる。
【００３２】
記録媒体３０５には、各種制御プログラムや各種情報がコンピュータに読み取り可能な状態で記録されている。この記録媒体３０５は、たとえば、ＨＤ（Ｈａｒｄ Ｄｉｓｋ）やＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）、メモリカードによって実現することができる。なお、記録媒体３０５は、記録媒体デコード部３０６による情報の書き込みを受け付けるとともに、書き込まれた情報を不揮発に記録するようにしてもよい。
【００３３】
また、記録媒体３０５には、経路探索および経路誘導に用いられる地図情報が記録されている。記録媒体３０５に記録されている地図情報は、建物、河川、地表面などの地物（フィーチャ）をあらわす背景データと、道路の形状をあらわす道路形状データとを有しており、表示部３０３の表示画面において２次元または３次元に描画される。ナビゲーション装置３００が経路誘導中の場合は、記録媒体デコード部３０６によって記録媒体３０５から読み取られた地図情報と位置取得部３０４によって取得された移動体の位置を示すマークとが表示部３０３に表示されることとなる。
【００３４】
背景データは、背景の形状をあらわす背景形状データと、背景の種類をあらわす背景種別データとを有する。背景形状データは、たとえば、地物の代表点・ポリライン・ポリゴン・地物の座標などを含んでいる。また、背景種別データは、たとえば、地物の名称や住所・電話番号をあらわすテキストデータ、建物・河川・地表面などの地物の種別データを含んでいる。
【００３５】
道路形状データは、複数のノードと、ノード間を連結するリンクとを有する道路ネットワークである。ノードは、Ｔ字路などの三叉路、十字路、五叉路などの複数の道路が交差する交差点を示している。リンクは、道路を示している。リンクには形状補間点を有するものもあり、この形状補間点によって曲線道路を表現することができる。
【００３６】
道路形状データは、さらに交通条件データを有する。交通条件データとは、たとえば、各ノードについて、信号や横断歩道などの有無、高速道路の出入り口やジャンクションの有無、各リンクについての長さ（距離）、車幅、進行方向、道路種別（有料道路、一般道路など）、過去の渋滞情報を季節・曜日・大型連休・時刻などを基準に統計処理した過去渋滞情報などである。
【００３７】
また、交通条件データは、高速道路などの走行料金が課金される有料道路の走行料金、走行料金に関する料金割引制度の適用条件、料金割引制度適用における割引料金などの情報も含まれている。料金割引制度の適用条件は、たとえば、所定の距離以上の走行または所定の距離未満の走行を条件とする距離条件、所定の時間帯における走行を条件とする時間帯条件、ＥＴＣゲートなど所定のポイントの通過を条件とする通過条件、あるいはそれらの複合などである。
【００３８】
なお、本実施例では地図情報を記録媒体３０５に記録するようにしたが、これに限るものではない。地図情報は、ナビゲーション装置３００外部のサーバなどに記録されていてもよい。その場合、ナビゲーション装置３００は、たとえば、通信部３０８を通じて、ネットワークを介してサーバから地図情報を取得する。取得された地図情報はＲＡＭなどに記憶される。
【００３９】
記録媒体デコード部３０６は、記録媒体３０５に対する情報の読み取り／書き込みの制御をおこなう。たとえば、記録媒体３０５としてＨＤを用いた場合には、記録媒体デコード部３０６は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）となる。
【００４０】
音声出力部３０７は、接続されたスピーカ３１２への出力を制御することによって、案内音などの音声を再生する。スピーカ３１２は、１つであってもよいし、複数であってもよい。この音声出力部３０７は、たとえば、音声デジタル情報のＤ／Ａ変換をおこなうＤ／Ａコンバータと、Ｄ／Ａコンバータから出力される音声アナログ信号を増幅する増幅器と、音声アナログ情報のＡ／Ｄ変換をおこなうＡ／Ｄコンバータと、から構成することができる。
【００４１】
通信部３０８は、各種情報を外部から取得する。たとえば、通信部３０８は、ＦＭ多重チューナー、ＶＩＣＳ（登録商標）／ビーコンレシーバ、無線通信機器およびその他の通信機器によって構成され、他の通信機器との通信をおこなう。また、通信部３０８は、携帯電話、ＰＨＳ、通信カードおよび無線ＬＡＮなどの通信媒体を介して通信をおこなう構成としてもよい。
【００４２】
通信部３０８によって取得される情報は、道路交通情報通信システムセンターから配信される渋滞や交通規制などの交通情報や、事業者が独自の方式で取得した交通情報や、その他インターネット上の公開データなどである。通信部３０８は、たとえば、全国の交通情報を蓄積しているサーバに対しネットワークを介して所望の地域の交通情報を要求し、要求した交通情報を取得するようにしてもよい。
【００４３】
経路探索部３０９は、記録媒体３０５から記録媒体デコード部３０６を介して取得される地図情報や、通信部３０８を介して取得される交通情報などを利用して、出発地点から目的地点までの最適経路を探索する。ここで、最適経路とは、ユーザの要望に最も合致する経路である。
【００４４】
一般に、出発地点から目的地点までの経路は無数存在する。このため、経路探索部３０９は、経路探索にあたって考慮される事項（以下、探索条件という）を設定し、条件に合致する経路を探索するようにしている。探索条件は、ユーザが設定できる構成でもよく、たとえば、目的地点までの所要時間、道路種別、距離、走行料金などである。具体的に、最適経路の探索は、目的地点までの経路を複数探索し、探索結果と探索条件を含んだ経路情報を表示部３０３に出力する。
【００４５】
経路誘導部３１０は、経路探索部３０９によって探索された最適経路情報、位置取得部３０４によって取得された移動体の位置情報、記録媒体３０５から記録媒体デコード部３０６を経由して得られた地図情報に基づいて、ユーザを目的地点まで誘導するための経路誘導情報の生成をおこなう。このとき生成される経路誘導情報は、通信部３０８によって受信した渋滞情報を考慮したものであってもよい。経路誘導部３１０で生成された経路誘導情報は、ナビゲーション制御部３０１を介して表示部３０３へ出力される。
【００４６】
音声生成部３１１は、案内音などの各種音声の情報を生成する。すなわち、経路誘導部３１０で生成された経路誘導情報に基づいて、案内ポイントに対応した仮想音源の設定と音声ガイダンス情報の生成をおこない、これをナビゲーション制御部３０１を介して音声出力部３０７へ出力する。
【００４７】
なお、実施の形態にかかる経路探索装置１００の機能的構成である探索部１０１は経路探索部３０９によって、判断部１０２はナビゲーション制御部３０１によって、それぞれその機能を実現する。
【００４８】
（ナビゲーション装置３００の処理の内容）
つぎに、図４を用いて、本実施例にかかるナビゲーション装置３００の処理の内容について説明する。図４は、本実施例にかかるナビゲーション装置の処理の内容を示すフローチャートである。図４のフローチャートにおいて、まず、ナビゲーション制御部３０１は、経路探索要求を受け付けたか否かを判断する（ステップＳ４０１）。たとえば、経路探索要求は、ユーザがユーザ操作部３０２を操作して要求する構成でもよい。
【００４９】
ステップＳ４０１において、経路探索部３０９は、ナビゲーション制御部３０１が経路探索要求を受け付けるのを待って、受け付けた場合（ステップＳ４０１：Ｙｅｓ）、第１の最適経路を探索する（ステップＳ４０２）。第１の最適経路の探索は、たとえば、出発地点から目的地点までの経路について、記録媒体３０５から記録媒体デコード部３０６を介して取得される地図情報や、通信部３０８を介して取得される交通情報などを利用しておこなう。
【００５０】
つづいて、ナビゲーション制御部３０１は、記録媒体３０５に記録された情報を参照して、第１の最適経路が走行距離を条件とする料金割引制度を適用している有料道路が含まれているか否かを判断する（ステップＳ４０３）。この判断は通信部３０８によって取得する情報を参照しておこなう構成でもよい。なお、図４において、走行距離を条件とする料金割引制度を「距離割引制度」と表す。
【００５１】
ステップＳ４０３において、第１の最適経路に走行距離を条件とした料金割引制度を適用している有料道路が含まれていない場合（ステップＳ４０３：Ｎｏ）、ナビゲーション制御部３０１は、経路探索部３０９から第１の最適経路の情報を取得し、この第１の最適経路に関する経路情報を生成する（ステップＳ４０５）。そして、表示部３０３などに生成した経路情報を出力して（ステップＳ４０６）、一連の処理を終了する。経路情報は、たとえば、第１の最適経路を示す情報や目的地までの所要時間の情報などである。
【００５２】
ステップＳ４０３において、第１の最適経路に走行距離を条件とした料金割引制度を適用している有料道路が含まれている場合（ステップＳ４０３：Ｙｅｓ）、ナビゲーション制御部３０１は、第１の最適経路が、記録媒体３０５に記録された情報を参照して、料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ４０４）。この距離条件は通信部３０８によって取得する構成でもよい。
【００５３】
ステップＳ４０４において、第１の最適経路が料金割引制度の距離条件を満たしている場合（ステップＳ４０４：Ｙｅｓ）、ナビゲーション制御部３０１は、経路探索部３０９から第１の最適経路の情報を取得し、この第１の最適経路に関する経路情報を生成する（ステップＳ４０５）。そして、表示部３０３などに生成した経路情報を出力して（ステップＳ４０６）、一連の処理を終了する。
【００５４】
ステップＳ４０４において、第１の最適経路が料金割引制度の距離条件を満たしていない場合（ステップＳ４０４：Ｎｏ）、ステップＳ４０７〜ステップＳ４１１により、料金割引制度の距離条件を満たす第２の最適経路を探索する。
【００５５】
経路探索部３０９は、第１の最適経路に含まれている有料道路の出入口を変更して経路を探索する（ステップＳ４０７）。出入口の変更は、出口、入口のいずれか一方を変更しても、出入口双方を変更してもよい。そして、ナビゲーション制御部３０１は、ステップＳ４０７において探索した経路が料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ４０８）。
【００５６】
ステップＳ４０８において、ステップＳ４０７で探索した経路が料金割引制度の距離条件を満たしていない場合（ステップＳ４０８：Ｎｏ）、ステップＳ４０７へ戻り、経路探索部３０９は、第１の最適経路の有料道路について、出入口を変更して経路を探索する（ステップＳ４０７）。
【００５７】
ステップＳ４０８において、ステップＳ４０７で探索した経路が料金割引制度の距離条件を満たしている場合（ステップＳ４０８：Ｙｅｓ）、ナビゲーション制御部３０１は、この探索した経路を候補経路としてメモリ等に記憶する（ステップＳ４０９）。そして、出入口を変更した探索を終了するか否かを判断する（ステップＳ４１０）。
【００５８】
ステップＳ４１０において、出入口を変更した探索を終了しない場合（ステップＳ４１０：Ｎｏ）、経路探索部３０９は、さらに第１の最適経路の有料道路の出入口を変更して経路を探索し（ステップＳ４０７）、処理を繰り返す。
【００５９】
また、ステップＳ４１０において、出入口を変更した探索を終了する場合（ステップＳ４１０：Ｙｅｓ）、ナビゲーション制御部３０１は、メモリ等に記憶されている候補経路から第２の最適経路を選定する（ステップＳ４１１）。なお、第２の最適経路は、一または複数選定する構成でもよい。
【００６０】
そして、ナビゲーション制御部３０１は、選定した第２の最適経路に関する経路情報を生成する（ステップＳ４０５）。さらに、表示部３０３などに、生成した経路情報を出力して（ステップＳ４０６）、一連の処理を終了する。なお、ナビゲーション制御部３０１は、経路情報を生成するにあたり、経路探索部３０９が探索した第１の最適経路の情報を取得してこの第１の最適経路に関する情報も生成し、第１の最適経路に関する情報と第２の最適経路に関する情報とを対比できるようにしてもよい。この際に、走行距離や所要時間、走行料金を対比できるように情報を生成してもよい。
【００６１】
上述のステップＳ４１０における探索の終了の判断は、すべての出入口について変更して探索を終了としなくても、距離条件や走行料金についてしきい値を設定して判断してもよい。たとえば、経路探索部３０９は、出発地点から入口を一つずつ離して経路を探索し、距離条件を満たした段階で探索を終了してもよい。同様に、目的地点から出口を一つずつ離して経路を探索し、距離条件を満たした段階で探索を終了してもよい。あるいは、第１の最適経路における走行料金に対して、所定の割引率の適用を受けた段階で、探索を終了してもよい。
【００６２】
また、上述のステップＳ４０７において、所定の基準により有料道路の出入口の変更をおこなう構成としてもよい。たとえば、経路探索部３０９は、渋滞情報および渋滞予測情報などを考慮して、渋滞を回避できるように出入口を変更して経路を探索するようにしてもよい。また、入口と出口のうち都市部に近い側の入口または出口は変更せずに郊外の方のみを変更して経路を探索するようにしてもよい。
【００６３】
さらに、上述のステップＳ４０８をおこなわずに、ステップＳ４１０において、出入口を変更した探索を終了するまで、複数の経路を探索してメモリに記憶しておき、これらの経路から料金割引制度の距離条件を満たす経路を抽出し、この抽出した経路の中から第２の最適経路を選定するようにしてもよい。
【００６４】
（経路探索部３０９における経路探索結果）
ここで、図５を用いて、本実施例にかかる経路探索部３０９における経路探索結果の一例について説明する。図５は、本実施例にかかる経路探索部における経路探索結果の一例を示す説明図である。
【００６５】
図５において、経路探索部３０９は、出発地点５０１から有料道路５０３を介して目的地点５０２まで到達する経路を探索する。
【００６６】
出発地点５０１は、経路探索において、車両などの移動体が出発する地点で、ユーザがユーザ操作部３０２を操作して設定する地点や位置取得部３０４によって取得される移動体の現在地点などである。また、目的地点５０２は、経路探索において、車両などの移動体が到達の目的とする地点で、ユーザがユーザ操作部３０２を操作して設定する地点などである。
【００６７】
有料道路５０３は、車両などの移動体が、出発地点５０１から目的地点５０２への移動に経由できる道路で、通行に際し走行料金が課金され、一般道路より制限速度が高く設定されている。本実施例において、有料道路５０３は、出入口となる複数のＩＣ（インターチェンジ）を有しており、ＩＣ（ａ）５０４と、ＩＣ（ｂ）５０５と、ＩＣ（ｃ）５０６と、ＩＣ（ｄ）５０７と、を含んでおり、それぞれのＩＣ間の距離（道なり距離）は、ＩＣ（ａ）５０４とＩＣ（ｂ）５０５との間は３０キロメートル、ＩＣ（ｂ）５０５とＩＣ（ｃ）５０６との間は４０キロメートル、ＩＣ（ｃ）５０６とＩＣ（ｄ）５０７との間は５０キロメートル、である。また、有料道路５０３は、所定の距離条件を満たすと走行料金が割引される料金割引制度の適用がある。本実施例において、距離条件は、移動体が有料道路５０３を走行する走行距離が１００キロメートル未満であることとし、この距離条件を満たす場合に走行料金が５０パーセント割引されるものとする。
【００６８】
本実施例において、出発地点５０１から有料道路５０３を介して目的地点５０２まで移動する経路は、複数存在する。たとえば、経路（Ａ）５１１は、出発地点５０１からＩＣ（ａ）５０４を有料道路５０３の入口として、ＩＣ（ｂ）５０５と、ＩＣ（ｃ）５０６を介して、ＩＣ（ｄ）５０７を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は１２０キロメートルである。
【００６９】
また、経路（Ｂ１）５１２は、出発地点５０１からＩＣ（ａ）５０４を有料道路５０３の入口として、ＩＣ（ｂ）５０５を介して、ＩＣ（ｃ）５０６を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は７０キロメートルである。
【００７０】
また、経路（Ｂ２）５１３は、出発地点５０１からＩＣ（ａ）５０４を有料道路５０３の入口として、ＩＣ（ｂ）５０５を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は３０キロメートルである。
【００７１】
また、経路（Ｂ３）５１４は、出発地点５０１からＩＣ（ｂ）５０５を有料道路５０３の入口として、ＩＣ（ｃ）５０６を介して、ＩＣ（ｄ）５０７を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は９０キロメートルである。
【００７２】
また、経路（Ｂ４）５１５は、出発地点５０１からＩＣ（ｂ）５０５を有料道路５０３の入口として、ＩＣ（ｃ）５０６を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は４０キロメートルである。
【００７３】
また、経路（Ｂ５）５１６は、出発地点５０１からＩＣ（ｃ）５０６を有料道路５０３の入口として、ＩＣ（ｄ）５０７を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は５０キロメートルである。
【００７４】
上述のとおり、本実施例において、出発地点５０１から目的地点５０２まで有料道路５０３を走行する際、料金割引制度の距離条件を満たしている経路は経路（Ｂ１）５１２〜経路（Ｂ５）５１６である。
【００７５】
ここで、図５を用いて、図４における第１の最適経路および第２の最適経路の探索処理について、具体的な一例を説明する。
【００７６】
ステップＳ４０２において、経路探索部３０９は経路（Ａ）５１１を第１の最適経路として探索する。そして、経路（Ａ）５１１が走行距離を条件とする料金割引制度を適用している有料道路５０３を含んでいるか否かの判断（ステップＳ４０３）において、走行距離を条件とする料金割引制度を適用している有料道路５０３を含んでいるため（ステップＳ４０３：Ｙｅｓ）、つづいて、料金割引制度の距離条件を満たしているか否かの判断をおこなう（ステップＳ４０４）。
【００７７】
ステップＳ４０４において、経路（Ａ）５１１は、有料道路５０３の走行距離１２０キロメートル（１００キロメートル以上）であり、料金割引制度の距離条件を満たしていないため（ステップＳ４０４：Ｎｏ）、経路探索部３０９は、経路（Ａ）５１１における有料道路５０３の出入口を変更して経路を探索する（ステップＳ４０７）。
【００７８】
ステップＳ４０７において、出口を変更して経路（Ｂ１）５１２を探索し、料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ４０８）。経路（Ｂ１）５１２は、走行距離７０キロメートル（１００キロメートル未満）であり、料金割引制度の距離条件を満たしているため（ステップＳ４０８：Ｙｅｓ）、この経路（Ｂ１）５１２を候補経路としてメモリ等に記憶し（ステップＳ４０９）、つづいて、出入口を変更した探索を終了するか否かの判断をおこなう（ステップＳ４１０）。なお、料金割引制度の距離条件を満たしていない場合（ステップＳ４０８：Ｎｏ）、ステップＳ４０７へ戻り、処理を繰り返す。
【００７９】
ステップＳ４１０において、経路（Ｂ１）５１２のみでは、出入口を変更した探索はすべて終了していないため（ステップＳ４１０：Ｎｏ）、ステップＳ４０７へ戻り、処理を繰り返す。同様に、経路（Ｂ２）５１３〜経路（Ｂ５）５１６を探索してこれらの経路を候補経路として記憶し、出入口を変更した探索を終了する（ステップＳ４１０：Ｙｅｓ）。
【００８０】
そして、候補経路である経路（Ｂ１）５１２〜経路（Ｂ５）５１６の中から一または複数の経路を第２の最適経路として選定する（ステップＳ４１１）。この第２の最適経路の選定基準としては、所要時間、走行距離、走行料金などがある。具体的には、経路（Ｂ３）５１４が一番所要時間が短い場合にはこの経路（Ｂ３）５１４を選定する。また、経路（Ｂ１）５１２が一番走行距離が短い場合にはこの経路（Ｂ１）５１２を選定する。さらに、所要時間が短い順に所定の数（たとえば３つ）だけ選定したり、走行距離が短い順に所定の数だけ選定したりしてもよい。
【００８１】
なお、上述したナビゲーション装置３００では、料金割引制度の適用を受ける距離条件について考慮しているが、他の条件と複合して料金割引制度の適用を受ける経路探索をおこなう構成としてもよい。たとえば、時間帯についても料金割引制度の適用に条件がある場合には、時間帯の条件を満たす経路を選択できる構成としてもよい。具体的には、時間帯の条件の終了時刻が間近である時間帯に出発する場合には、出発地点５０１側の入口は最寄りのＩＣ（ａ）５０４を選択して、目的地点５０２側出口を、距離条件を満たすように探索する。あるいは、ＥＴＣゲートの通過が条件であれば、ＥＴＣゲートを通過できる有料道路５０３の出入口を選択する構成としてもよい。
【００８２】
また、上述したナビゲーション装置３００は、車載機に限ることなく、取り外した使用、パーソナル・コンピュータや携帯電話などを用いた経路の計画に利用することもできる。たとえば、インターネットにおける地図情報を使った経路探索に適用してもよい。また、地図情報の代わりに列車などの路線情報を用いて、列車における運賃の距離割引の適用を受けるように、移動の計画に適用することもできる。
【００８３】
また、上述したナビゲーション装置３００は、経路探索要求を受け付けた段階では料金割引制度を考慮せずに第１の最適経路を探索しているが、経路探索要求を受け付けた段階で料金割引制度の距離条件を満たす経路を探索する構成としてもよい。
【００８４】
以上説明したように、上述の実施例のナビゲーション装置３００によれば、探索された最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれている場合に、距離条件を満たす最適経路を探索することができる。したがって、ユーザは、探索された最適経路の情報を情報出力装置等を介して取得して、走行距離を条件とする料金割引制度の適用を受けることができる最適経路の確認することができ、また、ナビゲーション装置に案内してもらう経路として当該最適経路を選択することができる。さらに、ユーザは、料金割引制度の距離条件を満たす最適経路に基づいて走行することで走行料金の低減を図ることができる。
【００８５】
また、料金割引制度の距離条件を満たす最適経路に関する情報と料金割引制度の距離条件を満たさない最適経路に関する情報を生成して出力することで、ユーザは双方の経路情報を確認することができ、選択自由度の増加を図ることができる。また、それぞれの最適経路の情報に距離や所要時間、走行料金を含めて対比できるようにすることで、ユーザの経路選択において効率化を図ることができる。
【００８６】
なお、本実施の形態で説明した経路探索方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【図面の簡単な説明】
【００８７】
【図１】本実施の形態にかかる経路探索装置の機能的構成の一例を示すブロック図である。
【図２】本実施の形態にかかる経路探索装置の処理の内容を示すフローチャートである。
【図３】本実施例にかかるナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【図４】本実施例にかかるナビゲーション装置の処理の内容を示すフローチャートである。
【図５】本実施例にかかる経路探索部における経路探索結果の一例を示す説明図である。
【符号の説明】
【００８８】
１００ 経路探索装置
１０１ 探索部
１０２ 判断部
１１０ 情報出力装置
１１１ 生成部
１１２ 出力部
【技術分野】
【０００１】
この発明は、目的地点までの最適経路を探索する経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
近年、車両などの移動体が有料道路を通行する際に徴収される走行料金は、様々な割引サービスの適用が受けられる場合がある。たとえば、ＥＴＣ（Ｅｌｅｃｔｒｏｎｉｃ Ｔｏｌｌ Ｃｏｌｌｅｃｔｉｏｎ Ｓｙｓｔｅｍ）を利用して、ＥＴＣ車載機を搭載した車両が、通過するＥＴＣゲートと、通過する時刻に応じて割引制度の適用（時間帯割引サービス）が受けられる場合などである。
【０００３】
上述した時間帯割引制度の適用を受けるため、有料道路とその有料道路に対する走行料金割引時間帯を記憶して、走行料金割引時間帯に有料道路を通過するように、目的地点へ車両を誘導する車両用ナビゲーション装置の提案がされている（たとえば、下記特許文献１参照。）。
【０００４】
【特許文献１】特開２００１−４１７６０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術は、有料道路に走行距離を条件とした料金割引制度が適用されている場合に、この料金割引制度の距離条件は何ら考慮されていない。したがって、目的地点までの経路で、所定の距離条件を満たせばコストが少なくできるのにも関わらず、距離条件を満たすように車両を誘導しないため、料金割引制度の適用が受けられないという問題が一例として挙げられる。たとえば、有料道路の走行距離が１００キロメートル未満で料金割引制度の適用を受けられる場合、料金割引制度の適用を受けるために、目的地点までの有料道路の距離が１２０キロメートルであっても、１００キロメートル未満の区間は有料道路を走行して、残りの区間は一般道路を走行するよう誘導すればよい。しかしながら、上述の問題により、距離条件を満たすように車両を誘導しないため、有料道路を１２０キロメートル走行して、料金割引制度の適用を受けられない。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するため、請求項１の発明にかかる経路探索装置は、目的地点までの第１の最適経路を探索する探索手段と、走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する判断手段と、を備え、前記探索手段は、前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索することを特徴とする。
【０００７】
また、請求項５の発明にかかる経路探索方法は、目的地点までの第１の最適経路を探索する第１工程と、走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれているかを判断する第２工程と、前記第２工程によって走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する第３工程と、前記第３工程によって前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索する第４工程と、を含むことを特徴とする。
【０００８】
また、請求項６の発明にかかる経路探索プログラムは、請求項５に記載の経路探索方法をコンピュータに実行させることを特徴とする。
【０００９】
また、請求項７の発明にかかるコンピュータに読み取り可能な記録媒体は、請求項６に記載の経路探索プログラムを記録したことを特徴とする。
【発明を実施するための最良の形態】
【００１０】
以下に添付図面を参照して、この発明にかかる経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体の好適な実施の形態を詳細に説明する。
【００１１】
（実施の形態）
（経路探索装置の機能的構成）
図１を用いて、本実施の形態にかかる経路探索装置の機能的構成について説明する。図１は、本実施の形態にかかる経路探索装置の機能的構成の一例を示すブロック図である。
【００１２】
図１において、経路探索装置１００は、探索部１０１と、判断部１０２と、を含んで構成されている。そして、経路探索装置１００は情報を他の装置に出力する。本実施の形態においては、経路探索装置１００は情報出力装置１１０に出力するものとする。この情報出力装置１１０は、生成部１１１と、出力部１１２と、を含んで構成されている。
【００１３】
探索部１０１は、目的地点までの最適経路を探索する。経路探索は、たとえば、図示しない記録媒体や通信部から取得する地図情報や移動体の位置に関する情報に基づいておこなう。そして、探索した最適経路（第１の最適経路）に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれており、且つ、当該経路（第１の最適経路）が料金割引制度の距離条件を満たしていないと後述する判断部１０２によって判断された場合に、有料道路の入口または出口を変更するなどして料金割引制度の距離条件を満たす目的地点までの最適経路（第２の最適経路）を探索する。
【００１４】
判断部１０２は、探索部１０１により探索された最適経路に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれているか否かを判断する。そして、当該最適経路に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれている場合に、当該最適経路がこの料金割引制度の距離条件を満たしているか否かを判断する。この判断結果を探索部１０１に出力する。
【００１５】
生成部１１１は、経路探索装置１００から探索部１０１によって探索された最適経路の情報などを取得し、この取得した情報に基づいて各種情報を生成する。生成する情報は、たとえば、目的地点までの最適経路を示す情報、目的地点までの所要時間の情報、目的地点に到達するのに必要な走行料金の情報などである。なお、最適経路に走行距離を条件とした料金割引制度を適用している所定の有料道路が含まれている場合であって当該経路について料金割引制度の距離条件を満たしていない場合に、この経路についての上記の情報と料金割引制度の距離条件を満たす最適経路についての上記の情報をそれぞれについて生成してもよい。
【００１６】
出力部１１２は、生成部１１１によって生成された情報を出力する。情報の出力は、たとえば音声で出力したり、図示しない表示部に画像で出力したりする。
【００１７】
（経路探索装置の処理の内容）
つぎに、本実施の形態にかかる経路探索装置１００の処理の内容について説明する。図２は、本実施の形態にかかる経路探索装置の処理の内容を示すフローチャートである。図２のフローチャートにおいて、まず、探索部１０１は、目的地点までの第１の最適経路を探索する（ステップＳ２０１）。
【００１８】
つづいて、判断部１０２は、ステップＳ２０１において探索された第１の最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれているか否かを判断する（ステップＳ２０２）。走行距離を条件とする料金割引制度は、有料道路を走行する際、所定の距離条件を満たすと、当該有料道路の走行料金の割引を受けることのできる制度である。なお、図２において、走行距離を条件とする料金割引制度を「距離割引制度」と表す。
【００１９】
ステップＳ２０２において、第１の最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれていると判断した場合（ステップＳ２０２：Ｙｅｓ）、判断部１０２は、第１の最適経路がこの料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ２０３）。
【００２０】
ステップＳ２０３において、判断部１０２が第１の最適経路が距離条件を満たしていないと判断した場合（ステップＳ２０３：Ｎｏ）、探索部１０１は距離条件を満たす第２の最適経路を探索する（ステップＳ２０４）。第２の最適経路の探索は、たとえば、有料道路の入口または出口の少なくとも一つを変更しておこなう。この際に、有料道路の入口または出口の少なくとも一つを変更して複数の経路を探索し、この複数の経路のうち距離条件を満たし且つ所定の条件を満たす一の経路を第２の最適経路としてもよい。なお、前述の所定の条件は、たとえば、最短距離や最短時間などでもよい。また、有料道路の入口や出口を変更する際に、たとえば入口と出口のうち都市部に近い側の入口または出口は変更せずに郊外の方のみを変更する、などの選定条件に基づいて出口や入口を変更して第２の最適経路を探索するようにしてもよい。
【００２１】
ステップＳ２０２において、判断部１０２が第１の最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれていないと判断した場合（ステップＳ２０２：Ｎｏ）、ステップＳ２０３において、判断部１０２が第１の最適経路が距離条件を満たしていると判断した場合（ステップＳ２０３：Ｙｅｓ）、およびステップＳ２０４において第２の最適経路が探索された場合は、情報出力装置１１０に、探索された経路の情報を出力し（ステップＳ２０５）、一連の処理を終了する。そして、情報出力装置１１０の生成部１１１は、この経路の情報に基づいて、目的地点までの最適経路を示す情報や目的地点までの所要時間の情報、目的地点に到達するのに必要な走行料金の情報などの各種情報を生成し、情報出力装置の出力部１１２がこれらの情報を出力する。
【００２２】
以上説明したように、本実施の形態にかかる経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体によれば、探索された最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれている場合に、距離条件を満たす最適経路を探索することができる。したがって、ユーザは、探索された最適経路の情報を情報出力装置等を介して取得して、走行距離を条件とする料金割引制度の適用を受けることができる最適経路の確認することができ、また、ナビゲーション装置に案内してもらう経路として当該最適経路を選択することができる。さらに、ユーザは、料金割引制度の距離条件を満たす最適経路に基づいて走行することで走行料金の低減を図ることができる。
【実施例】
【００２３】
以下に、本発明の実施例について説明する。本実施例では、たとえば、車両（四輪車、二輪車を含む）などの移動体に搭載されるナビゲーション装置によって、本発明の経路探索装置を実施した場合の一例について説明する。
【００２４】
（ナビゲーション装置のハードウェア構成）
図３を用いて、本実施例にかかるナビゲーション装置のハードウェア構成について説明する。図３は、本実施例にかかるナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【００２５】
図３において、ナビゲーション装置３００は、車両などの移動体に搭載されており、ナビゲーション制御部３０１と、ユーザ操作部３０２と、表示部３０３と、位置取得部３０４と、記録媒体３０５と、記録媒体デコード部３０６と、音声出力部３０７と、通信部３０８と、経路探索部３０９と、経路誘導部３１０と、音声生成部３１１と、スピーカ３１２と、によって構成される。
【００２６】
ナビゲーション制御部３０１は、ナビゲーション装置３００全体を制御する。ナビゲーション制御部３０１は、たとえば所定の演算処理を実行するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や、各種制御プログラムを格納するＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、および、ＣＰＵのワークエリアとして機能するＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などによって構成されるマイクロコンピュータなどによって実現することができる。
【００２７】
ナビゲーション制御部３０１は、経路誘導に際し、位置取得部３０４によって取得された現在位置に関する情報と、記録媒体３０５から記録媒体デコード部３０６を経由して得られた地図情報に基づいて、地図上のどの位置を走行しているかを算出し、算出結果を表示部３０３へ出力する。また、ナビゲーション制御部３０１は、経路誘導に際し、経路探索部３０９、経路誘導部３１０、音声生成部３１１との間で経路誘導に関する情報の入出力をおこない、その結果得られる情報を表示部３０３および音声出力部３０７へ出力する。
【００２８】
ユーザ操作部３０２は、ユーザがリモコンやスイッチ、タッチパネルなどの操作手段を操作して入力した情報を取得してナビゲーション制御部３０１に対して出力する。
【００２９】
表示部３０３は、たとえば、ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）、ＴＦＴ液晶ディスプレイ、有機ＥＬディスプレイ、プラズマディスプレイなどを含む。表示部３０３は、具体的には、たとえば、映像Ｉ／Ｆ（インターフェース）や映像Ｉ／Ｆに接続された映像表示用のディスプレイ装置によって構成することができる。映像Ｉ／Ｆは、具体的には、たとえば、ディスプレイ装置全体の制御をおこなうグラフィックコントローラと、即時表示可能な画像情報を一時的に記憶するＶＲＡＭ（Ｖｉｄｅｏ ＲＡＭ）などのバッファメモリと、グラフィックコントローラから出力される画像情報に基づいて、ディスプレイ装置を表示制御する制御ＩＣなどによって構成される。表示部３０３には、交通情報や地図情報や経路誘導に関する情報、その他各種情報が表示される。
【００３０】
位置取得部３０４は、ＧＰＳレシーバおよび各種センサーから構成され、移動体の現在位置（ナビゲーション装置３００の現在位置）の情報を取得する。ＧＰＳレシーバは、ＧＰＳ衛星からの電波を受信し、ＧＰＳ衛星との幾何学的位置を求める。なお、ＧＰＳとは、Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍの略称であり、４つ以上の衛星からの電波を受信することによって地上での位置を正確に求めるシステムである。ＧＰＳレシーバは、ＧＰＳ衛星からの電波を受信するためのアンテナ、受信した電波を復調するチューナーおよび復調した情報に基づいて現在位置を算出する演算回路などによって構成される。
【００３１】
各種センサーは、車速センサーや角速度センサー、加速度センサーなど移動体またはナビゲーション装置３００に搭載された各種センサーであり、これらのセンサーから出力される情報から、移動体の移動変位、移動速度、移動方向を求める。このように、ＧＰＳレシーバの受信電波から得られた情報と合わせて、上記各種センサーの出力情報を用いることによって、より高い精度で移動体の位置の認識をおこなうことができる。
【００３２】
記録媒体３０５には、各種制御プログラムや各種情報がコンピュータに読み取り可能な状態で記録されている。この記録媒体３０５は、たとえば、ＨＤ（Ｈａｒｄ Ｄｉｓｋ）やＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）、メモリカードによって実現することができる。なお、記録媒体３０５は、記録媒体デコード部３０６による情報の書き込みを受け付けるとともに、書き込まれた情報を不揮発に記録するようにしてもよい。
【００３３】
また、記録媒体３０５には、経路探索および経路誘導に用いられる地図情報が記録されている。記録媒体３０５に記録されている地図情報は、建物、河川、地表面などの地物（フィーチャ）をあらわす背景データと、道路の形状をあらわす道路形状データとを有しており、表示部３０３の表示画面において２次元または３次元に描画される。ナビゲーション装置３００が経路誘導中の場合は、記録媒体デコード部３０６によって記録媒体３０５から読み取られた地図情報と位置取得部３０４によって取得された移動体の位置を示すマークとが表示部３０３に表示されることとなる。
【００３４】
背景データは、背景の形状をあらわす背景形状データと、背景の種類をあらわす背景種別データとを有する。背景形状データは、たとえば、地物の代表点・ポリライン・ポリゴン・地物の座標などを含んでいる。また、背景種別データは、たとえば、地物の名称や住所・電話番号をあらわすテキストデータ、建物・河川・地表面などの地物の種別データを含んでいる。
【００３５】
道路形状データは、複数のノードと、ノード間を連結するリンクとを有する道路ネットワークである。ノードは、Ｔ字路などの三叉路、十字路、五叉路などの複数の道路が交差する交差点を示している。リンクは、道路を示している。リンクには形状補間点を有するものもあり、この形状補間点によって曲線道路を表現することができる。
【００３６】
道路形状データは、さらに交通条件データを有する。交通条件データとは、たとえば、各ノードについて、信号や横断歩道などの有無、高速道路の出入り口やジャンクションの有無、各リンクについての長さ（距離）、車幅、進行方向、道路種別（有料道路、一般道路など）、過去の渋滞情報を季節・曜日・大型連休・時刻などを基準に統計処理した過去渋滞情報などである。
【００３７】
また、交通条件データは、高速道路などの走行料金が課金される有料道路の走行料金、走行料金に関する料金割引制度の適用条件、料金割引制度適用における割引料金などの情報も含まれている。料金割引制度の適用条件は、たとえば、所定の距離以上の走行または所定の距離未満の走行を条件とする距離条件、所定の時間帯における走行を条件とする時間帯条件、ＥＴＣゲートなど所定のポイントの通過を条件とする通過条件、あるいはそれらの複合などである。
【００３８】
なお、本実施例では地図情報を記録媒体３０５に記録するようにしたが、これに限るものではない。地図情報は、ナビゲーション装置３００外部のサーバなどに記録されていてもよい。その場合、ナビゲーション装置３００は、たとえば、通信部３０８を通じて、ネットワークを介してサーバから地図情報を取得する。取得された地図情報はＲＡＭなどに記憶される。
【００３９】
記録媒体デコード部３０６は、記録媒体３０５に対する情報の読み取り／書き込みの制御をおこなう。たとえば、記録媒体３０５としてＨＤを用いた場合には、記録媒体デコード部３０６は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）となる。
【００４０】
音声出力部３０７は、接続されたスピーカ３１２への出力を制御することによって、案内音などの音声を再生する。スピーカ３１２は、１つであってもよいし、複数であってもよい。この音声出力部３０７は、たとえば、音声デジタル情報のＤ／Ａ変換をおこなうＤ／Ａコンバータと、Ｄ／Ａコンバータから出力される音声アナログ信号を増幅する増幅器と、音声アナログ情報のＡ／Ｄ変換をおこなうＡ／Ｄコンバータと、から構成することができる。
【００４１】
通信部３０８は、各種情報を外部から取得する。たとえば、通信部３０８は、ＦＭ多重チューナー、ＶＩＣＳ（登録商標）／ビーコンレシーバ、無線通信機器およびその他の通信機器によって構成され、他の通信機器との通信をおこなう。また、通信部３０８は、携帯電話、ＰＨＳ、通信カードおよび無線ＬＡＮなどの通信媒体を介して通信をおこなう構成としてもよい。
【００４２】
通信部３０８によって取得される情報は、道路交通情報通信システムセンターから配信される渋滞や交通規制などの交通情報や、事業者が独自の方式で取得した交通情報や、その他インターネット上の公開データなどである。通信部３０８は、たとえば、全国の交通情報を蓄積しているサーバに対しネットワークを介して所望の地域の交通情報を要求し、要求した交通情報を取得するようにしてもよい。
【００４３】
経路探索部３０９は、記録媒体３０５から記録媒体デコード部３０６を介して取得される地図情報や、通信部３０８を介して取得される交通情報などを利用して、出発地点から目的地点までの最適経路を探索する。ここで、最適経路とは、ユーザの要望に最も合致する経路である。
【００４４】
一般に、出発地点から目的地点までの経路は無数存在する。このため、経路探索部３０９は、経路探索にあたって考慮される事項（以下、探索条件という）を設定し、条件に合致する経路を探索するようにしている。探索条件は、ユーザが設定できる構成でもよく、たとえば、目的地点までの所要時間、道路種別、距離、走行料金などである。具体的に、最適経路の探索は、目的地点までの経路を複数探索し、探索結果と探索条件を含んだ経路情報を表示部３０３に出力する。
【００４５】
経路誘導部３１０は、経路探索部３０９によって探索された最適経路情報、位置取得部３０４によって取得された移動体の位置情報、記録媒体３０５から記録媒体デコード部３０６を経由して得られた地図情報に基づいて、ユーザを目的地点まで誘導するための経路誘導情報の生成をおこなう。このとき生成される経路誘導情報は、通信部３０８によって受信した渋滞情報を考慮したものであってもよい。経路誘導部３１０で生成された経路誘導情報は、ナビゲーション制御部３０１を介して表示部３０３へ出力される。
【００４６】
音声生成部３１１は、案内音などの各種音声の情報を生成する。すなわち、経路誘導部３１０で生成された経路誘導情報に基づいて、案内ポイントに対応した仮想音源の設定と音声ガイダンス情報の生成をおこない、これをナビゲーション制御部３０１を介して音声出力部３０７へ出力する。
【００４７】
なお、実施の形態にかかる経路探索装置１００の機能的構成である探索部１０１は経路探索部３０９によって、判断部１０２はナビゲーション制御部３０１によって、それぞれその機能を実現する。
【００４８】
（ナビゲーション装置３００の処理の内容）
つぎに、図４を用いて、本実施例にかかるナビゲーション装置３００の処理の内容について説明する。図４は、本実施例にかかるナビゲーション装置の処理の内容を示すフローチャートである。図４のフローチャートにおいて、まず、ナビゲーション制御部３０１は、経路探索要求を受け付けたか否かを判断する（ステップＳ４０１）。たとえば、経路探索要求は、ユーザがユーザ操作部３０２を操作して要求する構成でもよい。
【００４９】
ステップＳ４０１において、経路探索部３０９は、ナビゲーション制御部３０１が経路探索要求を受け付けるのを待って、受け付けた場合（ステップＳ４０１：Ｙｅｓ）、第１の最適経路を探索する（ステップＳ４０２）。第１の最適経路の探索は、たとえば、出発地点から目的地点までの経路について、記録媒体３０５から記録媒体デコード部３０６を介して取得される地図情報や、通信部３０８を介して取得される交通情報などを利用しておこなう。
【００５０】
つづいて、ナビゲーション制御部３０１は、記録媒体３０５に記録された情報を参照して、第１の最適経路が走行距離を条件とする料金割引制度を適用している有料道路が含まれているか否かを判断する（ステップＳ４０３）。この判断は通信部３０８によって取得する情報を参照しておこなう構成でもよい。なお、図４において、走行距離を条件とする料金割引制度を「距離割引制度」と表す。
【００５１】
ステップＳ４０３において、第１の最適経路に走行距離を条件とした料金割引制度を適用している有料道路が含まれていない場合（ステップＳ４０３：Ｎｏ）、ナビゲーション制御部３０１は、経路探索部３０９から第１の最適経路の情報を取得し、この第１の最適経路に関する経路情報を生成する（ステップＳ４０５）。そして、表示部３０３などに生成した経路情報を出力して（ステップＳ４０６）、一連の処理を終了する。経路情報は、たとえば、第１の最適経路を示す情報や目的地までの所要時間の情報などである。
【００５２】
ステップＳ４０３において、第１の最適経路に走行距離を条件とした料金割引制度を適用している有料道路が含まれている場合（ステップＳ４０３：Ｙｅｓ）、ナビゲーション制御部３０１は、第１の最適経路が、記録媒体３０５に記録された情報を参照して、料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ４０４）。この距離条件は通信部３０８によって取得する構成でもよい。
【００５３】
ステップＳ４０４において、第１の最適経路が料金割引制度の距離条件を満たしている場合（ステップＳ４０４：Ｙｅｓ）、ナビゲーション制御部３０１は、経路探索部３０９から第１の最適経路の情報を取得し、この第１の最適経路に関する経路情報を生成する（ステップＳ４０５）。そして、表示部３０３などに生成した経路情報を出力して（ステップＳ４０６）、一連の処理を終了する。
【００５４】
ステップＳ４０４において、第１の最適経路が料金割引制度の距離条件を満たしていない場合（ステップＳ４０４：Ｎｏ）、ステップＳ４０７〜ステップＳ４１１により、料金割引制度の距離条件を満たす第２の最適経路を探索する。
【００５５】
経路探索部３０９は、第１の最適経路に含まれている有料道路の出入口を変更して経路を探索する（ステップＳ４０７）。出入口の変更は、出口、入口のいずれか一方を変更しても、出入口双方を変更してもよい。そして、ナビゲーション制御部３０１は、ステップＳ４０７において探索した経路が料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ４０８）。
【００５６】
ステップＳ４０８において、ステップＳ４０７で探索した経路が料金割引制度の距離条件を満たしていない場合（ステップＳ４０８：Ｎｏ）、ステップＳ４０７へ戻り、経路探索部３０９は、第１の最適経路の有料道路について、出入口を変更して経路を探索する（ステップＳ４０７）。
【００５７】
ステップＳ４０８において、ステップＳ４０７で探索した経路が料金割引制度の距離条件を満たしている場合（ステップＳ４０８：Ｙｅｓ）、ナビゲーション制御部３０１は、この探索した経路を候補経路としてメモリ等に記憶する（ステップＳ４０９）。そして、出入口を変更した探索を終了するか否かを判断する（ステップＳ４１０）。
【００５８】
ステップＳ４１０において、出入口を変更した探索を終了しない場合（ステップＳ４１０：Ｎｏ）、経路探索部３０９は、さらに第１の最適経路の有料道路の出入口を変更して経路を探索し（ステップＳ４０７）、処理を繰り返す。
【００５９】
また、ステップＳ４１０において、出入口を変更した探索を終了する場合（ステップＳ４１０：Ｙｅｓ）、ナビゲーション制御部３０１は、メモリ等に記憶されている候補経路から第２の最適経路を選定する（ステップＳ４１１）。なお、第２の最適経路は、一または複数選定する構成でもよい。
【００６０】
そして、ナビゲーション制御部３０１は、選定した第２の最適経路に関する経路情報を生成する（ステップＳ４０５）。さらに、表示部３０３などに、生成した経路情報を出力して（ステップＳ４０６）、一連の処理を終了する。なお、ナビゲーション制御部３０１は、経路情報を生成するにあたり、経路探索部３０９が探索した第１の最適経路の情報を取得してこの第１の最適経路に関する情報も生成し、第１の最適経路に関する情報と第２の最適経路に関する情報とを対比できるようにしてもよい。この際に、走行距離や所要時間、走行料金を対比できるように情報を生成してもよい。
【００６１】
上述のステップＳ４１０における探索の終了の判断は、すべての出入口について変更して探索を終了としなくても、距離条件や走行料金についてしきい値を設定して判断してもよい。たとえば、経路探索部３０９は、出発地点から入口を一つずつ離して経路を探索し、距離条件を満たした段階で探索を終了してもよい。同様に、目的地点から出口を一つずつ離して経路を探索し、距離条件を満たした段階で探索を終了してもよい。あるいは、第１の最適経路における走行料金に対して、所定の割引率の適用を受けた段階で、探索を終了してもよい。
【００６２】
また、上述のステップＳ４０７において、所定の基準により有料道路の出入口の変更をおこなう構成としてもよい。たとえば、経路探索部３０９は、渋滞情報および渋滞予測情報などを考慮して、渋滞を回避できるように出入口を変更して経路を探索するようにしてもよい。また、入口と出口のうち都市部に近い側の入口または出口は変更せずに郊外の方のみを変更して経路を探索するようにしてもよい。
【００６３】
さらに、上述のステップＳ４０８をおこなわずに、ステップＳ４１０において、出入口を変更した探索を終了するまで、複数の経路を探索してメモリに記憶しておき、これらの経路から料金割引制度の距離条件を満たす経路を抽出し、この抽出した経路の中から第２の最適経路を選定するようにしてもよい。
【００６４】
（経路探索部３０９における経路探索結果）
ここで、図５を用いて、本実施例にかかる経路探索部３０９における経路探索結果の一例について説明する。図５は、本実施例にかかる経路探索部における経路探索結果の一例を示す説明図である。
【００６５】
図５において、経路探索部３０９は、出発地点５０１から有料道路５０３を介して目的地点５０２まで到達する経路を探索する。
【００６６】
出発地点５０１は、経路探索において、車両などの移動体が出発する地点で、ユーザがユーザ操作部３０２を操作して設定する地点や位置取得部３０４によって取得される移動体の現在地点などである。また、目的地点５０２は、経路探索において、車両などの移動体が到達の目的とする地点で、ユーザがユーザ操作部３０２を操作して設定する地点などである。
【００６７】
有料道路５０３は、車両などの移動体が、出発地点５０１から目的地点５０２への移動に経由できる道路で、通行に際し走行料金が課金され、一般道路より制限速度が高く設定されている。本実施例において、有料道路５０３は、出入口となる複数のＩＣ（インターチェンジ）を有しており、ＩＣ（ａ）５０４と、ＩＣ（ｂ）５０５と、ＩＣ（ｃ）５０６と、ＩＣ（ｄ）５０７と、を含んでおり、それぞれのＩＣ間の距離（道なり距離）は、ＩＣ（ａ）５０４とＩＣ（ｂ）５０５との間は３０キロメートル、ＩＣ（ｂ）５０５とＩＣ（ｃ）５０６との間は４０キロメートル、ＩＣ（ｃ）５０６とＩＣ（ｄ）５０７との間は５０キロメートル、である。また、有料道路５０３は、所定の距離条件を満たすと走行料金が割引される料金割引制度の適用がある。本実施例において、距離条件は、移動体が有料道路５０３を走行する走行距離が１００キロメートル未満であることとし、この距離条件を満たす場合に走行料金が５０パーセント割引されるものとする。
【００６８】
本実施例において、出発地点５０１から有料道路５０３を介して目的地点５０２まで移動する経路は、複数存在する。たとえば、経路（Ａ）５１１は、出発地点５０１からＩＣ（ａ）５０４を有料道路５０３の入口として、ＩＣ（ｂ）５０５と、ＩＣ（ｃ）５０６を介して、ＩＣ（ｄ）５０７を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は１２０キロメートルである。
【００６９】
また、経路（Ｂ１）５１２は、出発地点５０１からＩＣ（ａ）５０４を有料道路５０３の入口として、ＩＣ（ｂ）５０５を介して、ＩＣ（ｃ）５０６を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は７０キロメートルである。
【００７０】
また、経路（Ｂ２）５１３は、出発地点５０１からＩＣ（ａ）５０４を有料道路５０３の入口として、ＩＣ（ｂ）５０５を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は３０キロメートルである。
【００７１】
また、経路（Ｂ３）５１４は、出発地点５０１からＩＣ（ｂ）５０５を有料道路５０３の入口として、ＩＣ（ｃ）５０６を介して、ＩＣ（ｄ）５０７を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は９０キロメートルである。
【００７２】
また、経路（Ｂ４）５１５は、出発地点５０１からＩＣ（ｂ）５０５を有料道路５０３の入口として、ＩＣ（ｃ）５０６を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は４０キロメートルである。
【００７３】
また、経路（Ｂ５）５１６は、出発地点５０１からＩＣ（ｃ）５０６を有料道路５０３の入口として、ＩＣ（ｄ）５０７を有料道路５０３の出口として目的地点５０２へ到達する経路で、有料道路５０３の走行距離は５０キロメートルである。
【００７４】
上述のとおり、本実施例において、出発地点５０１から目的地点５０２まで有料道路５０３を走行する際、料金割引制度の距離条件を満たしている経路は経路（Ｂ１）５１２〜経路（Ｂ５）５１６である。
【００７５】
ここで、図５を用いて、図４における第１の最適経路および第２の最適経路の探索処理について、具体的な一例を説明する。
【００７６】
ステップＳ４０２において、経路探索部３０９は経路（Ａ）５１１を第１の最適経路として探索する。そして、経路（Ａ）５１１が走行距離を条件とする料金割引制度を適用している有料道路５０３を含んでいるか否かの判断（ステップＳ４０３）において、走行距離を条件とする料金割引制度を適用している有料道路５０３を含んでいるため（ステップＳ４０３：Ｙｅｓ）、つづいて、料金割引制度の距離条件を満たしているか否かの判断をおこなう（ステップＳ４０４）。
【００７７】
ステップＳ４０４において、経路（Ａ）５１１は、有料道路５０３の走行距離１２０キロメートル（１００キロメートル以上）であり、料金割引制度の距離条件を満たしていないため（ステップＳ４０４：Ｎｏ）、経路探索部３０９は、経路（Ａ）５１１における有料道路５０３の出入口を変更して経路を探索する（ステップＳ４０７）。
【００７８】
ステップＳ４０７において、出口を変更して経路（Ｂ１）５１２を探索し、料金割引制度の距離条件を満たしているか否かを判断する（ステップＳ４０８）。経路（Ｂ１）５１２は、走行距離７０キロメートル（１００キロメートル未満）であり、料金割引制度の距離条件を満たしているため（ステップＳ４０８：Ｙｅｓ）、この経路（Ｂ１）５１２を候補経路としてメモリ等に記憶し（ステップＳ４０９）、つづいて、出入口を変更した探索を終了するか否かの判断をおこなう（ステップＳ４１０）。なお、料金割引制度の距離条件を満たしていない場合（ステップＳ４０８：Ｎｏ）、ステップＳ４０７へ戻り、処理を繰り返す。
【００７９】
ステップＳ４１０において、経路（Ｂ１）５１２のみでは、出入口を変更した探索はすべて終了していないため（ステップＳ４１０：Ｎｏ）、ステップＳ４０７へ戻り、処理を繰り返す。同様に、経路（Ｂ２）５１３〜経路（Ｂ５）５１６を探索してこれらの経路を候補経路として記憶し、出入口を変更した探索を終了する（ステップＳ４１０：Ｙｅｓ）。
【００８０】
そして、候補経路である経路（Ｂ１）５１２〜経路（Ｂ５）５１６の中から一または複数の経路を第２の最適経路として選定する（ステップＳ４１１）。この第２の最適経路の選定基準としては、所要時間、走行距離、走行料金などがある。具体的には、経路（Ｂ３）５１４が一番所要時間が短い場合にはこの経路（Ｂ３）５１４を選定する。また、経路（Ｂ１）５１２が一番走行距離が短い場合にはこの経路（Ｂ１）５１２を選定する。さらに、所要時間が短い順に所定の数（たとえば３つ）だけ選定したり、走行距離が短い順に所定の数だけ選定したりしてもよい。
【００８１】
なお、上述したナビゲーション装置３００では、料金割引制度の適用を受ける距離条件について考慮しているが、他の条件と複合して料金割引制度の適用を受ける経路探索をおこなう構成としてもよい。たとえば、時間帯についても料金割引制度の適用に条件がある場合には、時間帯の条件を満たす経路を選択できる構成としてもよい。具体的には、時間帯の条件の終了時刻が間近である時間帯に出発する場合には、出発地点５０１側の入口は最寄りのＩＣ（ａ）５０４を選択して、目的地点５０２側出口を、距離条件を満たすように探索する。あるいは、ＥＴＣゲートの通過が条件であれば、ＥＴＣゲートを通過できる有料道路５０３の出入口を選択する構成としてもよい。
【００８２】
また、上述したナビゲーション装置３００は、車載機に限ることなく、取り外した使用、パーソナル・コンピュータや携帯電話などを用いた経路の計画に利用することもできる。たとえば、インターネットにおける地図情報を使った経路探索に適用してもよい。また、地図情報の代わりに列車などの路線情報を用いて、列車における運賃の距離割引の適用を受けるように、移動の計画に適用することもできる。
【００８３】
また、上述したナビゲーション装置３００は、経路探索要求を受け付けた段階では料金割引制度を考慮せずに第１の最適経路を探索しているが、経路探索要求を受け付けた段階で料金割引制度の距離条件を満たす経路を探索する構成としてもよい。
【００８４】
以上説明したように、上述の実施例のナビゲーション装置３００によれば、探索された最適経路に走行距離を条件とする料金割引制度を適用している有料道路が含まれている場合に、距離条件を満たす最適経路を探索することができる。したがって、ユーザは、探索された最適経路の情報を情報出力装置等を介して取得して、走行距離を条件とする料金割引制度の適用を受けることができる最適経路の確認することができ、また、ナビゲーション装置に案内してもらう経路として当該最適経路を選択することができる。さらに、ユーザは、料金割引制度の距離条件を満たす最適経路に基づいて走行することで走行料金の低減を図ることができる。
【００８５】
また、料金割引制度の距離条件を満たす最適経路に関する情報と料金割引制度の距離条件を満たさない最適経路に関する情報を生成して出力することで、ユーザは双方の経路情報を確認することができ、選択自由度の増加を図ることができる。また、それぞれの最適経路の情報に距離や所要時間、走行料金を含めて対比できるようにすることで、ユーザの経路選択において効率化を図ることができる。
【００８６】
なお、本実施の形態で説明した経路探索方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【図面の簡単な説明】
【００８７】
【図１】本実施の形態にかかる経路探索装置の機能的構成の一例を示すブロック図である。
【図２】本実施の形態にかかる経路探索装置の処理の内容を示すフローチャートである。
【図３】本実施例にかかるナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【図４】本実施例にかかるナビゲーション装置の処理の内容を示すフローチャートである。
【図５】本実施例にかかる経路探索部における経路探索結果の一例を示す説明図である。
【符号の説明】
【００８８】
１００ 経路探索装置
１０１ 探索部
１０２ 判断部
１１０ 情報出力装置
１１１ 生成部
１１２ 出力部
【特許請求の範囲】
【請求項１】
目的地点までの第１の最適経路を探索する探索手段と、
走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する判断手段と、
を備え、
前記探索手段は、前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索することを特徴とする経路探索装置。
【請求項２】
前記探索手段は、前記第１の最適経路に含まれる有料道路の入口または出口の少なくとも一つを変更して前記第２の最適経路を探索することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記探索手段は、前記第１の最適経路に含まれる有料道路の入口または出口を変更した複数の経路を探索し、当該複数の経路のうち前記距離条件を満たし且つ所定の条件を満たす一の経路を前記第２の最適経路とすることを特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記探索手段は、所定の条件に基づいて前記第１の最適経路に含まれる有料道路の入口または出口を変更して前記第２の最適経路を探索することを特徴とする請求項２に記載の経路探索装置。
【請求項５】
目的地点までの第１の最適経路を探索する第１工程と、
走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれているかを判断する第２工程と、
前記第２工程によって走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する第３工程と、
前記第３工程によって前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索する第４工程と、
を含むことを特徴とする経路探索方法。
【請求項６】
請求項５に記載の経路探索方法をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項７】
請求項６に記載の経路探索プログラムを記録したことを特徴とするコンピュータに読み取り可能な記録媒体。
【請求項１】
目的地点までの第１の最適経路を探索する探索手段と、
走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する判断手段と、
を備え、
前記探索手段は、前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索することを特徴とする経路探索装置。
【請求項２】
前記探索手段は、前記第１の最適経路に含まれる有料道路の入口または出口の少なくとも一つを変更して前記第２の最適経路を探索することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記探索手段は、前記第１の最適経路に含まれる有料道路の入口または出口を変更した複数の経路を探索し、当該複数の経路のうち前記距離条件を満たし且つ所定の条件を満たす一の経路を前記第２の最適経路とすることを特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記探索手段は、所定の条件に基づいて前記第１の最適経路に含まれる有料道路の入口または出口を変更して前記第２の最適経路を探索することを特徴とする請求項２に記載の経路探索装置。
【請求項５】
目的地点までの第１の最適経路を探索する第１工程と、
走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれているかを判断する第２工程と、
前記第２工程によって走行距離を条件とした料金割引制度を適用している有料道路が前記第１の最適経路に含まれている場合に、前記第１の最適経路が前記料金割引制度の距離条件を満たしているかを判断する第３工程と、
前記第３工程によって前記第１の最適経路が前記料金割引制度の距離条件を満たしていないと判断された場合に、前記料金割引制度の距離条件を満たす前記目的地点までの第２の最適経路を探索する第４工程と、
を含むことを特徴とする経路探索方法。
【請求項６】
請求項５に記載の経路探索方法をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項７】
請求項６に記載の経路探索プログラムを記録したことを特徴とするコンピュータに読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００７−７１６４０（Ｐ２００７−７１６４０Ａ）
【公開日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願番号】特願２００５−２５７７９８（Ｐ２００５−２５７７９８）
【出願日】平成１７年９月６日（２００５．９．６）
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【Ｆターム（参考）】
【公開日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願日】平成１７年９月６日（２００５．９．６）
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【Ｆターム（参考）】
[ Back to top ]