経路探索システム
【課題】複数地点間の経路情報を短時間で計算する経路探索システムを提供する。
【解決手段】経路探索システムは、複数の地点のうちの２地点の全ての組合せにおける該２地点間の第１経路全ての探索要求を受け付ける受付手段と、前記受付手段によって前記探索要求が受け付けられると、前記探索要求に含まれる探索条件に基づいて前記第１経路を全て探索する探索手段と、前記探索手段によって探索された前記第１経路を全て含む経路情報を送信する提供手段とを備え、前記受付手段が前記探索要求を受け付ける回数と、前記提供手段が前記経路情報を送信する回数とが、いずれも前記複数の地点の地点数よりも小さい。
【解決手段】経路探索システムは、複数の地点のうちの２地点の全ての組合せにおける該２地点間の第１経路全ての探索要求を受け付ける受付手段と、前記受付手段によって前記探索要求が受け付けられると、前記探索要求に含まれる探索条件に基づいて前記第１経路を全て探索する探索手段と、前記探索手段によって探索された前記第１経路を全て含む経路情報を送信する提供手段とを備え、前記受付手段が前記探索要求を受け付ける回数と、前記提供手段が前記経路情報を送信する回数とが、いずれも前記複数の地点の地点数よりも小さい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の地点間の経路情報を提供する経路探索システムに関する。
【背景技術】
【０００２】
ナビゲーションサービス向けに発展してきた交通情報や経路サービスを物流分野の配送計画に利用する動きがある。少ない記憶データで、短時間に配送地点間の経路を得るための方法が検討されている。
【０００３】
例えば、特許文献１には、小分割したエリアに代表ノードを設定し、代表ノード間の経路を予め計算し記憶する方法が開示されている。２地点が与えられると、各地点に最も近い代表ノードを探し、得られた代表ノード間の経路を予め計算した代表ノード間経路記憶手段から取得する。上記２地点と代表ノードとの間の経路を計算し、その経路と代表ノード間経路とを合成することにより、少ない記憶データで短時間に配送地点間の経路が得られるとしている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−６４０２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、代表ノード間の経路計算が、代表ノード数と代表ノード間距離とに依存するため、代表ノード数と代表ノード間距離とが増加すると経路計算処理時間を要する。
【課題を解決するための手段】
【０００６】
本発明による経路探索システムは、複数の地点のうちの２地点の全ての組合せにおける該２地点間の第１経路全ての探索要求を受け付ける受付手段と、受付手段によって探索要求が受け付けられると、探索要求に含まれる探索条件に基づいて第１経路を全て探索する探索手段と、探索手段によって探索された第１経路を全て含む経路情報を送信する提供手段とを備え、受付手段が探索要求を受け付ける回数と、提供手段が経路情報を送信する回数とが、いずれも複数の地点の地点数よりも小さいことを特徴とする。
【発明の効果】
【０００７】
本発明によれば、Ｎ地点間の複数経路が短時間で得られる経路探索システムを提供できる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施の形態における経路探索システムの全体構成を示す図である。
【図２】経路探索システムの全体処理フローを示す図である。
【図３】経路探索システムによるマップマッチング処理フローの一例を示す図である。
【図４】経路探索システムによるマップマッチング処理を説明するための補足図である。
【図５】経路情報記憶部によって記憶される確定経路のデータフォーマットの一例を示す図である。
【図６】コストデータおよび経路データの参照方法を説明するための経路例を示す図である。
【図７】経路探索システムによる全体処理フローに対して、交通情報に関わる処理を追加した処理フローの一例を示す図である。
【図８】経路探索部１６による経路コストの補正処理フローの一例を示す図である。
【図９】経路コストの補正処理フローを説明するための経路補正例を示す図である。
【図１０】第２の実施の形態における経路探索システムが、過去に確定した経路を用いて計算対象ノードを絞込む動作手順を示すフローチャートである。
【発明を実施するための形態】
【０００９】
−−−第１の実施の形態−−−
以下、図面を参照して本発明の第１の実施の形態について詳しく説明する。図１は、本発明の第１の実施の形態に係る経路探索システム１の全体構成を示した図である。図１において、本実施形態に係る経路探索システム１は、ローカルネットワーク３に接続され配送計画システム２に接続されている。また、ブロードバンドネットワーク５を介して、交通情報センタ、天気情報センタ、観光情報センタなどの外部情報センタ５にも接続されている。
【００１０】
経路探索システム１は、図示しないＣＰＵ（Central Processing Unit）、メモリ装置、ハードディスク装置などを含んで構成されたコンピュータのような情報処理装置によって構成される。そして、その経路探索システム１は、機能的には、図１に示すように、通信インタフェース部１１、外部情報取得部１２、外部情報記憶部１３、経路要求受付部１４、経路条件設定部１５、経路探索部１６、経路情報提供部１７、経路情報記憶部１８、地図データ１９などの機能ブロックを含んで構成される。なお、これらの機能ブロックは、経路探索システム１のＣＰＵが半導体メモリやハードディスク装置に記憶されているプログラムを実行することによって実現される。
【００１１】
図１において、外部情報取得部１２は、外部情報センタ４から交通情報や天候、施設情報等の様々な情報（音声や映像情報を含む）を取得し、外部情報データベース１３に蓄積する。経路要求受付部１４は、配送計画システム５から送信される経路要求を受信する。
【００１２】
受信した経路要求に一般道路優先、高速道路優先などの探索条件が含まれる場合、経路条件設定部１５は、出発地から目的地群への経路を探索するための経路条件としてその探索条件を設定する。経路条件設定部１５は、経路要求に含まれる複数地点の位置情報を、地図データ１９に記憶される道路ノードあるいは道路リンクにマッチングする。経路条件設定部１５は、マッチングした地図上の位置情報（ノード番号あるいはリンク番号）を用いて、上記複数地点の中から出発地を選択し、出発地以外の地点を目的地群とし、出発地と目的地群から成る探索地点情報を生成する。経路要求に出発日時や探索対象領域が含まれる場合も同様に経路条件を設定する。
【００１３】
経路探索部１６は、地図データ１９を用い、経路条件設定部１５で設定された出発地と目的地群、経路条件に基づいて出発地から各目的地までの経路を計算する。ここで、経路条件設定部１５は、経路要求に含まれる複数地点の全ての地点が出発地として選ばれるまで順に出発地を選択し、出発地と目的地群からなる探索地点情報を生成し、経路探索部１６に対して出発地から各目的地までの経路探索を要求する。
【００１４】
経路情報記憶部１８は、経路探索部１６で確定したノード間の経路および移動コストを記憶する。経路情報記憶部１８に記憶された経路情報は、外部情報取得部１２を介して外部情報センタ４から交通情報が取得され、外部情報記憶部１３が更新されたときに解放される。また、外部情報センタ４から取得した天気や施設情報等の様々な情報を利用して計算した経路情報を経路情報記憶部１８に保持する場合、経路情報の計算に利用した情報を新たに取得し、外部情報記憶部１３が更新されたタイミングで経路情報を解放する。経路情報提供部１７は、経路探索部１６が出力した複数地点間の経路情報を配送計画システム２に送信する。
【００１５】
本実施例は、経路探索システム１と配送計画システム２をローカルネットワークで接続する構成をとったが、ネットワークを介さず、同一のコンピュータで実行する構成にしても良い。
【００１６】
経路探索システムの全体処理フローを図２に示す。経路探索システム１は、配送計画システム２から経路要求を受信し、経路要求に含まれる複数地点の位置情報、探索条件などを参照し、それら複数地点間の経路を計算する。以下、経路探索システム１が配送計画システム２から経路要求を受信した場合の処理手順について説明する。
【００１７】
経路探索システム１において、経路要求受付部１４は通信インタフェース部１１を介して複数地点の位置情報と探索条件とを含む経路要求を受け付ける（ステップＳ２００）。経路条件設定部１５は、複数地点の位置を地図データ１９で管理される道路ノードやリンクの位置に対応付けるマップマッチング処理を実行する（ステップＳ２０１）。経路条件設定部１５は、経路要求に含まれる、例えば高速道優先等の道路種別に関する探索条件、幅員に関する探索条件、車線数に関する探索条件、探索コストを時間優先にするか距離優先にするかについての探索条件等を解釈し、解釈した探索条件に基づいて経路探索の探索条件を設定する（ステップＳ２０２）。
【００１８】
経路条件設定部１５は、ステップＳ２０１でマッチングした地図データ１９上の位置データを用い、上記複数地点の中から出発地を選択し、出発地以外の複数地点を目的地群とする（ステップＳ２０３）。経路探索部１６は、出発地と目的地群とが含まれるよう探索エリアを設定し（ステップＳ２０４）、その探索エリアから候補ノードを選択し（ステップＳ２０５）、候補ノードへの到達経路およびその到達経路のコストを決定する（ステップＳ２０６）。経路探索部１６は、候補ノードを始点とする各ノードへの確定経路であって、かつ設定された探索条件に対応する確定経路が存在するかどうか経路情報記憶部１８を検索する。経路探索部１６は、確定経路が存在する場合は（ステップＳ２０７でＹｅｓ）、当該出発地から候補ノードまでの到達経路およびその到達経路のコストと、候補ノードから上記各ノードへの確定経路およびその確定経路のコストとを合成計算し、当該出発地から上記各ノードへの到達経路およびその到達経路のコストを決定する（ステップＳ２０８）。
【００１９】
経路探索部１６は、探索エリア内にコスト更新決定対象となるノードが無くなるまで（ステップＳ２０９）候補ノードを更新選択し（ステップＳ２０５）、ステップＳ２０６からＳ２０８までの処理を繰り返す。経路探索部１６は、探索エリア内の全てのノードについてコスト更新決定処理を終えると（ステップＳ２０９でＮｏ）、当該出発地から各ノードへの確定経路およびその確定経路のコストを経路情報記憶部１８に記憶させる（ステップＳ２１０）。経路条件設定部１５は、上記複数地点の全てを出発地に設定し、経路探索部１６によって全地点間の経路情報が得られるまで（ステップＳ２１１でＹｅｓ）、出発地および目的地群を更新設定し（ステップＳ２０３）、経路探索部１６によるステップＳ２０４からＳ２１０までの処理が繰り返される。
【００２０】
経路探索部１６による上記複数地点間の経路探索が終了すると（ステップＳ２１１でＹｅｓ）、ステップＳ２００で経路要求受付部１４により受け付けられた経路要求に、ステップＳ２０２で経路条件設定部１５により設定された探索条件とは異なる探索条件が含まれ、その全ての探索条件で経路計算が終了していなければ（ステップＳ２１２でＮｏ）、経路条件設定部１５は、探索条件を更新設定し（ステップＳ２０２）、ステップＳ２０３以降の処理が繰り返される。経路探索部１６は、要求された全ての探索条件で上記複数地点間の経路情報が得られたら（ステップＳ２１２でＹｅｓ）、得られた経路のコストは探索地点間（道路ノード間）のコストであるため、元の地点から探索地点（ノード）までのコストを計算し（図８にて説明する）、各経路のコストを補正（ステップＳ２１３）する。経路探索部１６が経路コストを補正し終えた経路情報を、ステップＳ２００で受け付けた経路要求に対する経路情報として、経路情報提供部１７が通信インタフェース部１１を介し、経路要求元である配送計画システム２に送信する。
【００２１】
ステップＳ２００で経路探索システム１が受信する１回の経路要求に複数地点の位置情報が含まれているので、従来技術のようにそれら複数地点の中から選択される出発地および目的地の組合せの組合せ数と等しいＮ回の経路要求を受け付けることが無い。同様に、ステップＳ２１４で経路探索システム１が送信する１回の経路情報に上記組合せ数と等しい経路数の経路が含まれているので、従来技術のようにその経路数と等しいＮ回の経路情報を送信することが無い。すなわち、経路要求受付回数も経路情報送信回数もともに１回であるため、図１における経路探索システム１の配送計画システム２とのインタフェース１１０の処理負荷が低減される。
【００２２】
経路要求のデータ量が大きい場合は、経路要求受付回数をＮ回よりは小さい複数回としても良い。この場合、経路情報のデータ量も大きくなるため、経路情報送信回数も複数回となるが、Ｎ回よりも小さいならば上述した処理負荷の低減効果は得られる。また、１回の経路要求に対して、経路情報送信回数を複数回としても良い。
【００２３】
次に、図３および図４を参照して、経路探索システム１におけるマップマッチング処理（ステップＳ２０１）について、詳細に説明する。
【００２４】
ここで、図３は、経路探索システム１によるマップマッチング処理フローの一例を示す図である。図４は、経路探索システム１によるマップマッチング処理を説明するための補足図である。
【００２５】
本処理は、経路要求受付部１４により受け付けられた経路要求から経路探索を実行する経路条件設定部１５により実行される。経路要求に含まれる複数地点の位置情報を参照し（ステップＳ３００）、位置情報を用いて各地点間の距離（例えばユークリッド距離）を算出する（ステップＳ３０１）。一般的に位置情報として緯度経度が用いられるが、座標系が明確であれば、座標系で扱うエリアの識別番号（例えば、地図メッシュコード）と正規化座標といった位置情報で指定されても良い。複数地点の地点間の距離が所定値以下、すなわち地点同士が近傍に存在する場合（ステップＳ３０３でＹｅｓ）、近傍に存在する地点同士を抽出して地点群を構成する（ステップＳ３０４）。構成した地点群の位置座標から重心座標を算出し（ステップＳ３０５）、得られた重心座標を地図データ１９で扱う座標系に変換する（ステップＳ３０６）。
【００２６】
変換した重心座標に最も近い道路ノードあるいは道路リンクを地図データ１９から探す（ステップＳ３０７）。地点群が存在する位置よりも所定以上離れた道路ノードへの対応付けを防止するため、道路ノードの検索範囲を所定範囲内とする。所定範囲内に対応する道路ノードが見つかった場合（ステップＳ３０７でＹｅｓ）、上記地点群を構成する地点を道路ノードに対応付けるものとし、得られた道路ノードを地点群の集約探索地点として設定する（ステップＳ３０８）。ステップＳ３０７において所定範囲内に対応する道路ノードが見つからなかった場合（ステップＳ３０７でＮｏ）、該当ノード無し（ステップＳ３１２）とし、本地点群を探索地点に含めない。
【００２７】
近傍に地点が存在しなければ（ステップＳ３０３でＮｏ）、当該地点を地図データ１９の座標系に変換し（ステップＳ３０８）、変換した地点座標近傍の所定範囲内に道路ノードが存在すれば（ステップＳ３１０でＹｅｓ）、当該道路ノードをその地点の探索地点に設定する（ステップＳ３１１）。全ての地点について道路ノードへの対応づけを行い探索地点を設定したとき（ステップＳ３１３でＹｅｓ）、本マップマッチング処理は終了する。
【００２８】
図４において、地点４１１〜４１５は互いに近傍に存在する地点を示しており、このような地点同士を地点群４２０として扱う。図３に示すステップＳ３０５およびＳ３０６において地点群４２０の重心座標４２１を計算し、重心座標４２１に最も近い道路ノード４０２を地点群４２０の探索地点とし、このような探索地点を本発明では集約探索地点とする。地点４１０は近傍地点が存在しないため、ステップＳ３０９からＳ３１１によって道路ノード４０１が地点４１０に対応付けられ、探索地点として設定される。
【００２９】
経路要求に含まれる地点の位置情報は、経路探索で扱う道路データと必ずしも一致するものではなく、道路データ上の探索地点として同じ道路ノード（あるいは道路リンク）に対応付けられる地点が含まれる可能性がある。そこで、複数の同一探索地点を一つにまとめて集約探索地点として扱うことで全体の探索地点数が減少し、探索処理時間を短くすることができる。本実施の形態では、複数の近傍地点の重心座標を計算し探索地点を設定する方法を示したが、各地点を道路ノードに対応付けてから、同じ道路ノードに対応付けられた地点を地点群としても同様の効果が得られる。
【００３０】
図５は、経路情報記憶部１８によって記憶される確定経路のデータフォーマットの一例を示す図である。確定経路は、各探索条件５１０に対しコストデータ５２０と経路データ５３０とが保持される。コストデータ５２０は出発ノードＮｉから目的ノードＮｊへの移動に要するコストのデータであり、コストには所要時間、距離、料金、燃料消費量、有害物質排出量などがある。経路情報記憶部１８は、経路探索部１６によりノード間の移動コストが最小となる経路が計算されて得られた経路の最小コストをコストデータ、その経路を経路データとして保持する。探索条件５１０は、経路種別、経路を利用する日付に応じて分類される日種、出発日時、優先道路などの様々な項目から成り、各項目の設定内容の組み合わせで複数の探索条件が存在する。経路計算に交通情報が利用される場合は、使用した交通情報の識別情報として時刻情報、例えば交通情報提供日時を保存する。
【００３１】
本発明は、経路情報を経路情報記憶部１８が記憶しておき、同一の探索条件での経路探索に再利用することで経路計算に関わる計算負荷を軽減し処理時間を短縮することを目的としているが、交通情報を利用する場合、交通情報は時々刻々と変動するので、過去の経路情報が必ずしも有効とならない。そこで、経路情報と共に交通情報提供日時を記憶し、交通情報提供日時から所定時間の範囲で経路情報を再利用する。交通情報は統計交通情報を利用しても良い。また、交通情報を識別するための時刻情報として、交通情報更新日時を用いても良く、その場合、上述した交通情報更新日時から所定時間の範囲で過去の経路情報を利用する。
【００３２】
交通情報を利用した経路情報は、交通情報を更新した時、新たな交通情報で経路情報が計算された時、経路情報が計算されてから所定時刻を経過した時など、上述した交通情報更新日時から所定時間の範囲に含まれるいずれかのタイミングで経路情報記憶部１８から削除されることで経路情報の陳腐化を防止するのが好ましい。経路情報が計算された日時、すなわち経路情報生成日時は、経路探索部１６が経路情報記憶部１８に記憶されている当該経路情報の付属データを参照することにより得られる。
【００３３】
図６は、図５におけるコストデータ５２０と経路データ５３０の参照方法を説明するための経路例を示す図である。図６に示すようなノードＮ１〜Ｎ６から成る道路ネットワークが与えられたとする。ノードＮ２を出発ノードとして、ノードＮ２から残り全てのノードへの経路が確定すると、コストデータ５２０のｉ＝２の行に各ノードへの到達コスト、経路データ５３０には、出発ノードＮ２から各ノードへの経路が登録される。経路データ５３０に関して、例えば、ノードＮ２からノードＮ６に向かう経路において、ｉ＝２、かつｊ＝６の項の値ｎ＝４であることから、出発ノードＮ２の次ノードＮｎがノードＮ４であることを意味する。次にノードＮ４からノードＮ６に向かう経路において、ｉ＝４、かつｊ＝６の項には、ノードＮ４の次ノードＮｎがノードＮ６であることを意味する値ｎ＝６が登録されている。ノードＮ６は終点ノードなので、ノードＮ２からノードＮ６に向かう経路はノードＮ２→Ｎ４→Ｎ６ということになる。
【００３４】
図２のステップＳ２１１における繰返し処理により、今度はノードＮ４を出発ノードに設定し、ノードＮ４から各ノードへの到達経路とコストを計算する（ステップＳ２０３）。この場合、ステップＳ２０８において経路情報記憶部１８の記憶するコストデータと経路データに、ノードＮ４からノードＮ５およびＮ６への経路とコストが存在するので、これらの経路及びコストは改めて計算することなく、ノードＮ４からの経路が確定していない目的ノードＮ１、Ｎ２、およびＮ３を対象に経路計算を実行する。更に出発ノードをノードＮ３とした場合、目的ノードＮ６への経路の検索過程で候補ノードＮ４が選択されると、ノードＮ４からノードＮ６への経路は既に存在するので、出発ノードＮ３から候補ノードＮ４までの経路およびコストと、候補ノードＮ４から目的ノードＮ６への確定経路およびコストとを合成することにより、出発ノードＮ３から目的ノードＮ６への経路が構成される。例えば、出発ノードＮ３から候補ノードＮ４までの経路がノードＮ３→Ｎ１→Ｎ４で構成され、その経路のコストが１５とする。候補ノードＮ４から目的ノードＮ６への確定経路ノードＮ４→Ｎ６で構成され、その経路のコストが図５に示す例では２５なので、合成して得られる経路全体はノードＮ３→Ｎ１→Ｎ４→Ｎ６で構成され、その経路全体のコストは１５＋２５＝４０になる。なお、候補ノードとは、出発ノードから目的ノードへの経路の検索過程で経由ノードとして選択されるノードをいう。
【００３５】
図７は、図２で説明した経路探索システム１の全体処理フローに対して、交通情報に関わる処理を追加した処理フローの一例を示す図である。経路要求受付部１４は、ステップＳ２００で受け付けられる経路要求に含まれる探索条件に交通情報の利用要求が含まれているか否かを判定する（ステップＳ７０１）。経路要求受付部１４は、探索条件に交通情報の利用要求が含まれている場合（ステップＳ７０１でＹｅｓ）、その探索条件に含まれる出発日時に基づいて外部情報取得部１２に取得させる交通情報の日時を設定し、外部情報取得部１２は通信インタフェース部１１を介して外部情報センタ４に接続する（ステップＳ７０２）。外部情報センタ４が保持する交通情報の更新日時が、外部情報記憶部１３に記憶されている交通情報更新日時よりも新しいとき（ステップＳ７０３でＹｅｓ）、外部情報取得部１２は外部情報センタ４から最新の交通情報を受信し、外部情報記憶部１３に記憶させる（ステップＳ７０４）。このとき、経路探索部１６は、経路情報記憶部１８によって記憶されている経路情報から、更新日時が古い交通情報を用いて計算された経路情報を検索し削除する（ステップＳ７０５）。なお、ステップＳ７０５の処理を行わずに、経路情報記憶部１８に古い交通情報を記憶させたままとしてもよい。
【００３６】
外部情報センタ４から取得される交通情報は、出発日時の他に現況や将来を含む複数の時刻情報が指定されると、その指定した時刻情報に対応する複数の交通情報となる。経路探索部１６は、交通情報が提供される交通情報エリアを経路探索システム１が通過する時刻をその交通情報エリアと出発地との直線距離に基づいて見積もるなどして出発地から各地点への通過予想時刻を大まかに見積もり、その通過予想時刻に基づいて交通情報が取得され、各地点間の経路計算が実行される。
【００３７】
本実施の形態の経路探索システム１が経路探索に用いる交通情報を外部情報センタ４から取得する構成としたが、過去の交通情報あるいは過去の交通情報に基づいて日種毎に計算された統計交通情報を、地図データ１９などを記憶する記憶装置に予め記憶させる構成としても良い。この場合、上述した経路要求が日種に応じた経路探索の探索条件を含んでいても良い。
【００３８】
また、経路探索システム１が外部から取得する情報は交通情報に限らず、経路探索システム１は、施設情報、通行料金、観光情報など様々な外部情報を取得し、経路計算に用いることもある。外部情報センタ４から得られる外部情報が交通情報と同様に変化する情報であり、変化する外部情報を用いて計算した経路情報は、その外部情報が更新された時点でその利用価値を失うため、経路情報記憶部１８から削除される必要がある。
【００３９】
経路探索部１６は、地図データ１９の道路上にマッチングした探索地点からその探索地点に対応する複数の地点の各々までの距離を考慮し、経路コストを補正する。図８は、経路探索部１６による経路コストの補正処理フローの一例を示す図であり、図２のステップＳ２１３に対応する。図９は、図８における経路コストの補正処理フローを説明するための経路補正例を示す図である。
【００４０】
経路探索部１６の経路計算で得られた経路コスト（所要時間や距離など）は、地図の道路ノードにマッチングされた探索地点間の経路コストである。その探索地点に対応する地点、あるいは探索地点が集約探索地点の場合にはその集約探索地点に対応する地点群に属する地点の各々と探索地点との間の移動コストは、その経路コストに含まれない。その移動コストは、例えば図９における地点１０１０と探索地点１０００との間の移動コスト、あるいは地点１０２０〜１０４０の各々と探索地点１０００との間の移動コストである。探索地点とその探索地点に対応する地点との距離が極めて近い場合は問題ないが、探索地点として設定されている道路ノードと離れた位置に対応する地点が存在する場合や、交通渋滞などによって探索地点とこれに対応する地点との間のリンク移動コストが距離に関係なく大きいことも考えられる。そのため、経路探索部１６は、本処理によってそれら両地点間の移動コストを推定し経路コストを補正する。本補正処理は、図２のステップＳ２１３に示すように、経路探索部１６によって、ステップＳ２１２における複数地点間の経路計算が終了した後、ステップＳ２１４の直前に実行する。
【００４１】
経路探索部１６は、複数の地点から未処理の地点を選択し（ステップＳ８０１）、選択した地点に対応する位置情報を参照する（ステップＳ８０２）。経路探索部１６は、当該地点から当該地点の近傍リンクに垂線を下ろし、垂線距離の最も短いリンクを近傍リンクとして選択し、垂線と交差する近傍リンク上の地点を最近傍点とする（ステップＳ８０３）。図９の例では、選択した地点が地点１０１０の場合、所定範囲内に垂線１０１３を下ろす近傍リンクが存在し、最近傍点１０１１が設定される。しかし、選択した地点が地点１０３０の場合のように所定範囲内に垂線を下ろす近傍リンクが存在せず、最近傍点が設定できない場合（ステップＳ８０４でＮｏ）、経路探索部１６は、上記の選択した地点と当該地点の探索地点とを結ぶ直線距離を計算し（ステップＳ８０７）、得られた距離と所定の速度とに基づき旅行時間を計算する（ステップＳ８０８）。地点１０３０が選択された場合、ステップＳ８０７で計算されるこの直線距離は直線１０１４の距離となる。ステップＳ８０８における所定の速度は、周囲リンクの速度情報、すなわち規制速度や交通情報から得た速度など、またはその周囲リンクのリンクコストから計算によって得られる速度としてもよい。あるいは、例えばプローブカーなどの車両の過去の走行データから得られる速度としてもよい。ステップＳ２１１およびＳ２１２で検索された全ての経路のうち、ステップＳ８０１で選択された地点に対応する探索地点を出発地または目的地とする経路に対して、この選択された地点と探索地点との間の距離と旅行時間とを追加して（ステップＳ８１２）、ステップＳ８１１へ進む。
【００４２】
一方、最近傍点を設定できた場合（ステップＳ８０４でＹｅｓ）は、経路探索部１６は最近傍点とステップＳ８０１で選択された地点との間の距離を計算する（ステップＳ８０５）。経路探索部１６は、ステップＳ８０５で得られた距離と最近傍点が設定されたリンクの速度情報、すなわち規制速度や交通情報から得た速度などとから移動時間を計算する（ステップＳ８０６）。経路探索部１６は、ステップＳ８０５で得られた距離とステップＳ８０６で得られた旅行時間と、図２のステップＳ２０８で決定された経路とコストとをステップＳ８０９およびＳ８１０の処理を用いて補正する。ステップＳ８０９では、選択した地点に対応する探索地点を端点とする経路を、最近傍点を端点とする経路に補正する。図９の例では、地点１０１０を選択対象としたとき、この地点１０１０に対応する探索地点１０００を端点とする補正対象の経路１０１２が、この経路上の最近傍点１０１１を端点とした経路に補正される。補正対象の経路上に最近傍点が存在しない場合、その経路に対して端点と最近傍点との間の経路を追加することで補正が行われる。この補正は選択した地点を出発地または目的地とする全ての経路について実行される。次に、ステップＳ８１０において、ステップＳ８０９で補正した経路に、最近傍点からステップＳ８０１で選択された地点までの経路情報を追加し、最終的な経路情報を計算する処理を実行する。経路探索部１６は、全ての地点についての補正処理を終えるまで処理を繰り返す（ステップＳ８１１）。
【００４３】
このように、選択された地点の最近傍点と探索地点との間の経路の旅行時間や距離を、その探索地点を出発地または目的地ノードとして得られた確定経路の旅行時間や距離から差し引いて（あるいは加算して）、最近傍点を端点とする経路の経路情報を計算する。本実施の形態では、最近傍点が見つからなかったとき、ステップＳ８０７、Ｓ８０８、およびＳ８１２において、地点から対応する探索地点まで（あるいはその逆）の経路情報をその確定経路の確定経路情報に含めて、最終的な地点間経路を生成する。しかし、全ての地点において、最近傍点を用いずに、地点と対応する探索地点との間の経路情報を用いて補正しても良い。このとき、より詳細な地図データを用いて、この地点と対応する探索地点との間の近距離探索で経路情報を取得する。しかし、地点とこれに対応する探索地点とを直線で結んで旅行時間や距離を計算してもよい。
【００４４】
−−−第２の実施の形態−−−
図１０は、第２の実施の形態における経路探索システム１が、確定経路を用いて探索対象ノードを絞込む動作手順を示すフローチャートである。
【００４５】
基本手順は図２に示す手順と同様であるため、同一の符号を付した共通する処理ステップについての説明を省略し、図２に示す処理と異なる処理を説明する。経路探索部１６が選択した候補ノードを始点とする各ノードへの確定経路が存在する場合（ステップＳ２０７でＹｅｓ）は、経路探索部１６は、出発ノードからその候補ノードまでの到達コストと、その候補ノードから上記各ノードへの確定経路のコストとに基づき、各ノードにおける上限コストを設定する（ステップＳ９０１）。各ノードの上限コストは、例えば候補ノードの到達コストと上記確定経路のコストとの和として決定される。確定経路のコストは図５に示すコストデータ５２０として管理されるが、本実施の形態において、経路データ５３０は管理されない。
【００４６】
経路探索部１６は、各ノードの到達コストがそのノードに設定された上限コストよりも小さいノードを、コスト更新決定対象ノード（候補ノード）とする（ステップＳ９０２）。このように確定経路を用いて経路計算の対象ノードを絞り込むことで、経路計算に関わる計算量が削減されるので、計算時間の短縮が可能となる。第１の実施の形態においては、確定経路データとして記憶された確定経路がそのまま、出発地からその確定経路に対応する候補ノードを経由して各ノードへ至る経路に含まれる。しかし、本実施の形態においては、確定経路を用いて絞り込まれた上限コスト範囲内のノードを経由する経路が経路計算によって得られる。図２のステップＳ２１０において、その経路計算が行われるとともに、その経路計算で得られた経路が、出発地から目的地群の各ノードへ至る経路として経路情報記憶部に記憶される。
【００４７】
以上、第１および第２の実施の形態による経路探索システム１は、Ｎ地点間の全ての組合せの経路を組合せ毎に要求するよりも少ないリクエスト回数でＮ地点間の全ての経路要求を受け付け、Ｎ地点間の全ての組合せの経路を組合せ毎に応答するよりも少ないレスポンス回数でＮ地点間の全ての経路情報を配送計画システム２へ提供する。したがって、経路探索システム１の、経路探索システム１を利用する配送計画システム２などのアプリケーションとの間のインタフェース１１０に要する処理負荷が軽減できるようになる。
【００４８】
更に、Ｎ地点間の経路探索過程で、経路が確定したノード間の経路を記憶し、記憶した確定経路を新たな探索地点間の経路計算に利用することで、経路計算における計算量が削減され、より短い時間でＮ地点間の経路が計算される。
【符号の説明】
【００４９】
１ 経路探索システム
２ 配送計画システム
３ ローカルネットワーク
４ 外部情報センタ
５ ブロードバンドネットワーク
１１ 通信インタフェース部
１２ 外部情報取得部
１３ 外部情報記憶部
１４ 端末要求受付部
１５ 経路条件設定部
１６ 経路探索部
１７ 経路情報提供部
１８ 経路情報記憶部
１９ 地図データ
４０１、４０２ 道路ノード
４１０〜４１５ 地点
４２０ 地点群
４２１ 重心座標
５１０ 探索条件
５２０ コストデータ
５３０ 経路データ
【技術分野】
【０００１】
本発明は、複数の地点間の経路情報を提供する経路探索システムに関する。
【背景技術】
【０００２】
ナビゲーションサービス向けに発展してきた交通情報や経路サービスを物流分野の配送計画に利用する動きがある。少ない記憶データで、短時間に配送地点間の経路を得るための方法が検討されている。
【０００３】
例えば、特許文献１には、小分割したエリアに代表ノードを設定し、代表ノード間の経路を予め計算し記憶する方法が開示されている。２地点が与えられると、各地点に最も近い代表ノードを探し、得られた代表ノード間の経路を予め計算した代表ノード間経路記憶手段から取得する。上記２地点と代表ノードとの間の経路を計算し、その経路と代表ノード間経路とを合成することにより、少ない記憶データで短時間に配送地点間の経路が得られるとしている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−６４０２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、代表ノード間の経路計算が、代表ノード数と代表ノード間距離とに依存するため、代表ノード数と代表ノード間距離とが増加すると経路計算処理時間を要する。
【課題を解決するための手段】
【０００６】
本発明による経路探索システムは、複数の地点のうちの２地点の全ての組合せにおける該２地点間の第１経路全ての探索要求を受け付ける受付手段と、受付手段によって探索要求が受け付けられると、探索要求に含まれる探索条件に基づいて第１経路を全て探索する探索手段と、探索手段によって探索された第１経路を全て含む経路情報を送信する提供手段とを備え、受付手段が探索要求を受け付ける回数と、提供手段が経路情報を送信する回数とが、いずれも複数の地点の地点数よりも小さいことを特徴とする。
【発明の効果】
【０００７】
本発明によれば、Ｎ地点間の複数経路が短時間で得られる経路探索システムを提供できる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施の形態における経路探索システムの全体構成を示す図である。
【図２】経路探索システムの全体処理フローを示す図である。
【図３】経路探索システムによるマップマッチング処理フローの一例を示す図である。
【図４】経路探索システムによるマップマッチング処理を説明するための補足図である。
【図５】経路情報記憶部によって記憶される確定経路のデータフォーマットの一例を示す図である。
【図６】コストデータおよび経路データの参照方法を説明するための経路例を示す図である。
【図７】経路探索システムによる全体処理フローに対して、交通情報に関わる処理を追加した処理フローの一例を示す図である。
【図８】経路探索部１６による経路コストの補正処理フローの一例を示す図である。
【図９】経路コストの補正処理フローを説明するための経路補正例を示す図である。
【図１０】第２の実施の形態における経路探索システムが、過去に確定した経路を用いて計算対象ノードを絞込む動作手順を示すフローチャートである。
【発明を実施するための形態】
【０００９】
−−−第１の実施の形態−−−
以下、図面を参照して本発明の第１の実施の形態について詳しく説明する。図１は、本発明の第１の実施の形態に係る経路探索システム１の全体構成を示した図である。図１において、本実施形態に係る経路探索システム１は、ローカルネットワーク３に接続され配送計画システム２に接続されている。また、ブロードバンドネットワーク５を介して、交通情報センタ、天気情報センタ、観光情報センタなどの外部情報センタ５にも接続されている。
【００１０】
経路探索システム１は、図示しないＣＰＵ（Central Processing Unit）、メモリ装置、ハードディスク装置などを含んで構成されたコンピュータのような情報処理装置によって構成される。そして、その経路探索システム１は、機能的には、図１に示すように、通信インタフェース部１１、外部情報取得部１２、外部情報記憶部１３、経路要求受付部１４、経路条件設定部１５、経路探索部１６、経路情報提供部１７、経路情報記憶部１８、地図データ１９などの機能ブロックを含んで構成される。なお、これらの機能ブロックは、経路探索システム１のＣＰＵが半導体メモリやハードディスク装置に記憶されているプログラムを実行することによって実現される。
【００１１】
図１において、外部情報取得部１２は、外部情報センタ４から交通情報や天候、施設情報等の様々な情報（音声や映像情報を含む）を取得し、外部情報データベース１３に蓄積する。経路要求受付部１４は、配送計画システム５から送信される経路要求を受信する。
【００１２】
受信した経路要求に一般道路優先、高速道路優先などの探索条件が含まれる場合、経路条件設定部１５は、出発地から目的地群への経路を探索するための経路条件としてその探索条件を設定する。経路条件設定部１５は、経路要求に含まれる複数地点の位置情報を、地図データ１９に記憶される道路ノードあるいは道路リンクにマッチングする。経路条件設定部１５は、マッチングした地図上の位置情報（ノード番号あるいはリンク番号）を用いて、上記複数地点の中から出発地を選択し、出発地以外の地点を目的地群とし、出発地と目的地群から成る探索地点情報を生成する。経路要求に出発日時や探索対象領域が含まれる場合も同様に経路条件を設定する。
【００１３】
経路探索部１６は、地図データ１９を用い、経路条件設定部１５で設定された出発地と目的地群、経路条件に基づいて出発地から各目的地までの経路を計算する。ここで、経路条件設定部１５は、経路要求に含まれる複数地点の全ての地点が出発地として選ばれるまで順に出発地を選択し、出発地と目的地群からなる探索地点情報を生成し、経路探索部１６に対して出発地から各目的地までの経路探索を要求する。
【００１４】
経路情報記憶部１８は、経路探索部１６で確定したノード間の経路および移動コストを記憶する。経路情報記憶部１８に記憶された経路情報は、外部情報取得部１２を介して外部情報センタ４から交通情報が取得され、外部情報記憶部１３が更新されたときに解放される。また、外部情報センタ４から取得した天気や施設情報等の様々な情報を利用して計算した経路情報を経路情報記憶部１８に保持する場合、経路情報の計算に利用した情報を新たに取得し、外部情報記憶部１３が更新されたタイミングで経路情報を解放する。経路情報提供部１７は、経路探索部１６が出力した複数地点間の経路情報を配送計画システム２に送信する。
【００１５】
本実施例は、経路探索システム１と配送計画システム２をローカルネットワークで接続する構成をとったが、ネットワークを介さず、同一のコンピュータで実行する構成にしても良い。
【００１６】
経路探索システムの全体処理フローを図２に示す。経路探索システム１は、配送計画システム２から経路要求を受信し、経路要求に含まれる複数地点の位置情報、探索条件などを参照し、それら複数地点間の経路を計算する。以下、経路探索システム１が配送計画システム２から経路要求を受信した場合の処理手順について説明する。
【００１７】
経路探索システム１において、経路要求受付部１４は通信インタフェース部１１を介して複数地点の位置情報と探索条件とを含む経路要求を受け付ける（ステップＳ２００）。経路条件設定部１５は、複数地点の位置を地図データ１９で管理される道路ノードやリンクの位置に対応付けるマップマッチング処理を実行する（ステップＳ２０１）。経路条件設定部１５は、経路要求に含まれる、例えば高速道優先等の道路種別に関する探索条件、幅員に関する探索条件、車線数に関する探索条件、探索コストを時間優先にするか距離優先にするかについての探索条件等を解釈し、解釈した探索条件に基づいて経路探索の探索条件を設定する（ステップＳ２０２）。
【００１８】
経路条件設定部１５は、ステップＳ２０１でマッチングした地図データ１９上の位置データを用い、上記複数地点の中から出発地を選択し、出発地以外の複数地点を目的地群とする（ステップＳ２０３）。経路探索部１６は、出発地と目的地群とが含まれるよう探索エリアを設定し（ステップＳ２０４）、その探索エリアから候補ノードを選択し（ステップＳ２０５）、候補ノードへの到達経路およびその到達経路のコストを決定する（ステップＳ２０６）。経路探索部１６は、候補ノードを始点とする各ノードへの確定経路であって、かつ設定された探索条件に対応する確定経路が存在するかどうか経路情報記憶部１８を検索する。経路探索部１６は、確定経路が存在する場合は（ステップＳ２０７でＹｅｓ）、当該出発地から候補ノードまでの到達経路およびその到達経路のコストと、候補ノードから上記各ノードへの確定経路およびその確定経路のコストとを合成計算し、当該出発地から上記各ノードへの到達経路およびその到達経路のコストを決定する（ステップＳ２０８）。
【００１９】
経路探索部１６は、探索エリア内にコスト更新決定対象となるノードが無くなるまで（ステップＳ２０９）候補ノードを更新選択し（ステップＳ２０５）、ステップＳ２０６からＳ２０８までの処理を繰り返す。経路探索部１６は、探索エリア内の全てのノードについてコスト更新決定処理を終えると（ステップＳ２０９でＮｏ）、当該出発地から各ノードへの確定経路およびその確定経路のコストを経路情報記憶部１８に記憶させる（ステップＳ２１０）。経路条件設定部１５は、上記複数地点の全てを出発地に設定し、経路探索部１６によって全地点間の経路情報が得られるまで（ステップＳ２１１でＹｅｓ）、出発地および目的地群を更新設定し（ステップＳ２０３）、経路探索部１６によるステップＳ２０４からＳ２１０までの処理が繰り返される。
【００２０】
経路探索部１６による上記複数地点間の経路探索が終了すると（ステップＳ２１１でＹｅｓ）、ステップＳ２００で経路要求受付部１４により受け付けられた経路要求に、ステップＳ２０２で経路条件設定部１５により設定された探索条件とは異なる探索条件が含まれ、その全ての探索条件で経路計算が終了していなければ（ステップＳ２１２でＮｏ）、経路条件設定部１５は、探索条件を更新設定し（ステップＳ２０２）、ステップＳ２０３以降の処理が繰り返される。経路探索部１６は、要求された全ての探索条件で上記複数地点間の経路情報が得られたら（ステップＳ２１２でＹｅｓ）、得られた経路のコストは探索地点間（道路ノード間）のコストであるため、元の地点から探索地点（ノード）までのコストを計算し（図８にて説明する）、各経路のコストを補正（ステップＳ２１３）する。経路探索部１６が経路コストを補正し終えた経路情報を、ステップＳ２００で受け付けた経路要求に対する経路情報として、経路情報提供部１７が通信インタフェース部１１を介し、経路要求元である配送計画システム２に送信する。
【００２１】
ステップＳ２００で経路探索システム１が受信する１回の経路要求に複数地点の位置情報が含まれているので、従来技術のようにそれら複数地点の中から選択される出発地および目的地の組合せの組合せ数と等しいＮ回の経路要求を受け付けることが無い。同様に、ステップＳ２１４で経路探索システム１が送信する１回の経路情報に上記組合せ数と等しい経路数の経路が含まれているので、従来技術のようにその経路数と等しいＮ回の経路情報を送信することが無い。すなわち、経路要求受付回数も経路情報送信回数もともに１回であるため、図１における経路探索システム１の配送計画システム２とのインタフェース１１０の処理負荷が低減される。
【００２２】
経路要求のデータ量が大きい場合は、経路要求受付回数をＮ回よりは小さい複数回としても良い。この場合、経路情報のデータ量も大きくなるため、経路情報送信回数も複数回となるが、Ｎ回よりも小さいならば上述した処理負荷の低減効果は得られる。また、１回の経路要求に対して、経路情報送信回数を複数回としても良い。
【００２３】
次に、図３および図４を参照して、経路探索システム１におけるマップマッチング処理（ステップＳ２０１）について、詳細に説明する。
【００２４】
ここで、図３は、経路探索システム１によるマップマッチング処理フローの一例を示す図である。図４は、経路探索システム１によるマップマッチング処理を説明するための補足図である。
【００２５】
本処理は、経路要求受付部１４により受け付けられた経路要求から経路探索を実行する経路条件設定部１５により実行される。経路要求に含まれる複数地点の位置情報を参照し（ステップＳ３００）、位置情報を用いて各地点間の距離（例えばユークリッド距離）を算出する（ステップＳ３０１）。一般的に位置情報として緯度経度が用いられるが、座標系が明確であれば、座標系で扱うエリアの識別番号（例えば、地図メッシュコード）と正規化座標といった位置情報で指定されても良い。複数地点の地点間の距離が所定値以下、すなわち地点同士が近傍に存在する場合（ステップＳ３０３でＹｅｓ）、近傍に存在する地点同士を抽出して地点群を構成する（ステップＳ３０４）。構成した地点群の位置座標から重心座標を算出し（ステップＳ３０５）、得られた重心座標を地図データ１９で扱う座標系に変換する（ステップＳ３０６）。
【００２６】
変換した重心座標に最も近い道路ノードあるいは道路リンクを地図データ１９から探す（ステップＳ３０７）。地点群が存在する位置よりも所定以上離れた道路ノードへの対応付けを防止するため、道路ノードの検索範囲を所定範囲内とする。所定範囲内に対応する道路ノードが見つかった場合（ステップＳ３０７でＹｅｓ）、上記地点群を構成する地点を道路ノードに対応付けるものとし、得られた道路ノードを地点群の集約探索地点として設定する（ステップＳ３０８）。ステップＳ３０７において所定範囲内に対応する道路ノードが見つからなかった場合（ステップＳ３０７でＮｏ）、該当ノード無し（ステップＳ３１２）とし、本地点群を探索地点に含めない。
【００２７】
近傍に地点が存在しなければ（ステップＳ３０３でＮｏ）、当該地点を地図データ１９の座標系に変換し（ステップＳ３０８）、変換した地点座標近傍の所定範囲内に道路ノードが存在すれば（ステップＳ３１０でＹｅｓ）、当該道路ノードをその地点の探索地点に設定する（ステップＳ３１１）。全ての地点について道路ノードへの対応づけを行い探索地点を設定したとき（ステップＳ３１３でＹｅｓ）、本マップマッチング処理は終了する。
【００２８】
図４において、地点４１１〜４１５は互いに近傍に存在する地点を示しており、このような地点同士を地点群４２０として扱う。図３に示すステップＳ３０５およびＳ３０６において地点群４２０の重心座標４２１を計算し、重心座標４２１に最も近い道路ノード４０２を地点群４２０の探索地点とし、このような探索地点を本発明では集約探索地点とする。地点４１０は近傍地点が存在しないため、ステップＳ３０９からＳ３１１によって道路ノード４０１が地点４１０に対応付けられ、探索地点として設定される。
【００２９】
経路要求に含まれる地点の位置情報は、経路探索で扱う道路データと必ずしも一致するものではなく、道路データ上の探索地点として同じ道路ノード（あるいは道路リンク）に対応付けられる地点が含まれる可能性がある。そこで、複数の同一探索地点を一つにまとめて集約探索地点として扱うことで全体の探索地点数が減少し、探索処理時間を短くすることができる。本実施の形態では、複数の近傍地点の重心座標を計算し探索地点を設定する方法を示したが、各地点を道路ノードに対応付けてから、同じ道路ノードに対応付けられた地点を地点群としても同様の効果が得られる。
【００３０】
図５は、経路情報記憶部１８によって記憶される確定経路のデータフォーマットの一例を示す図である。確定経路は、各探索条件５１０に対しコストデータ５２０と経路データ５３０とが保持される。コストデータ５２０は出発ノードＮｉから目的ノードＮｊへの移動に要するコストのデータであり、コストには所要時間、距離、料金、燃料消費量、有害物質排出量などがある。経路情報記憶部１８は、経路探索部１６によりノード間の移動コストが最小となる経路が計算されて得られた経路の最小コストをコストデータ、その経路を経路データとして保持する。探索条件５１０は、経路種別、経路を利用する日付に応じて分類される日種、出発日時、優先道路などの様々な項目から成り、各項目の設定内容の組み合わせで複数の探索条件が存在する。経路計算に交通情報が利用される場合は、使用した交通情報の識別情報として時刻情報、例えば交通情報提供日時を保存する。
【００３１】
本発明は、経路情報を経路情報記憶部１８が記憶しておき、同一の探索条件での経路探索に再利用することで経路計算に関わる計算負荷を軽減し処理時間を短縮することを目的としているが、交通情報を利用する場合、交通情報は時々刻々と変動するので、過去の経路情報が必ずしも有効とならない。そこで、経路情報と共に交通情報提供日時を記憶し、交通情報提供日時から所定時間の範囲で経路情報を再利用する。交通情報は統計交通情報を利用しても良い。また、交通情報を識別するための時刻情報として、交通情報更新日時を用いても良く、その場合、上述した交通情報更新日時から所定時間の範囲で過去の経路情報を利用する。
【００３２】
交通情報を利用した経路情報は、交通情報を更新した時、新たな交通情報で経路情報が計算された時、経路情報が計算されてから所定時刻を経過した時など、上述した交通情報更新日時から所定時間の範囲に含まれるいずれかのタイミングで経路情報記憶部１８から削除されることで経路情報の陳腐化を防止するのが好ましい。経路情報が計算された日時、すなわち経路情報生成日時は、経路探索部１６が経路情報記憶部１８に記憶されている当該経路情報の付属データを参照することにより得られる。
【００３３】
図６は、図５におけるコストデータ５２０と経路データ５３０の参照方法を説明するための経路例を示す図である。図６に示すようなノードＮ１〜Ｎ６から成る道路ネットワークが与えられたとする。ノードＮ２を出発ノードとして、ノードＮ２から残り全てのノードへの経路が確定すると、コストデータ５２０のｉ＝２の行に各ノードへの到達コスト、経路データ５３０には、出発ノードＮ２から各ノードへの経路が登録される。経路データ５３０に関して、例えば、ノードＮ２からノードＮ６に向かう経路において、ｉ＝２、かつｊ＝６の項の値ｎ＝４であることから、出発ノードＮ２の次ノードＮｎがノードＮ４であることを意味する。次にノードＮ４からノードＮ６に向かう経路において、ｉ＝４、かつｊ＝６の項には、ノードＮ４の次ノードＮｎがノードＮ６であることを意味する値ｎ＝６が登録されている。ノードＮ６は終点ノードなので、ノードＮ２からノードＮ６に向かう経路はノードＮ２→Ｎ４→Ｎ６ということになる。
【００３４】
図２のステップＳ２１１における繰返し処理により、今度はノードＮ４を出発ノードに設定し、ノードＮ４から各ノードへの到達経路とコストを計算する（ステップＳ２０３）。この場合、ステップＳ２０８において経路情報記憶部１８の記憶するコストデータと経路データに、ノードＮ４からノードＮ５およびＮ６への経路とコストが存在するので、これらの経路及びコストは改めて計算することなく、ノードＮ４からの経路が確定していない目的ノードＮ１、Ｎ２、およびＮ３を対象に経路計算を実行する。更に出発ノードをノードＮ３とした場合、目的ノードＮ６への経路の検索過程で候補ノードＮ４が選択されると、ノードＮ４からノードＮ６への経路は既に存在するので、出発ノードＮ３から候補ノードＮ４までの経路およびコストと、候補ノードＮ４から目的ノードＮ６への確定経路およびコストとを合成することにより、出発ノードＮ３から目的ノードＮ６への経路が構成される。例えば、出発ノードＮ３から候補ノードＮ４までの経路がノードＮ３→Ｎ１→Ｎ４で構成され、その経路のコストが１５とする。候補ノードＮ４から目的ノードＮ６への確定経路ノードＮ４→Ｎ６で構成され、その経路のコストが図５に示す例では２５なので、合成して得られる経路全体はノードＮ３→Ｎ１→Ｎ４→Ｎ６で構成され、その経路全体のコストは１５＋２５＝４０になる。なお、候補ノードとは、出発ノードから目的ノードへの経路の検索過程で経由ノードとして選択されるノードをいう。
【００３５】
図７は、図２で説明した経路探索システム１の全体処理フローに対して、交通情報に関わる処理を追加した処理フローの一例を示す図である。経路要求受付部１４は、ステップＳ２００で受け付けられる経路要求に含まれる探索条件に交通情報の利用要求が含まれているか否かを判定する（ステップＳ７０１）。経路要求受付部１４は、探索条件に交通情報の利用要求が含まれている場合（ステップＳ７０１でＹｅｓ）、その探索条件に含まれる出発日時に基づいて外部情報取得部１２に取得させる交通情報の日時を設定し、外部情報取得部１２は通信インタフェース部１１を介して外部情報センタ４に接続する（ステップＳ７０２）。外部情報センタ４が保持する交通情報の更新日時が、外部情報記憶部１３に記憶されている交通情報更新日時よりも新しいとき（ステップＳ７０３でＹｅｓ）、外部情報取得部１２は外部情報センタ４から最新の交通情報を受信し、外部情報記憶部１３に記憶させる（ステップＳ７０４）。このとき、経路探索部１６は、経路情報記憶部１８によって記憶されている経路情報から、更新日時が古い交通情報を用いて計算された経路情報を検索し削除する（ステップＳ７０５）。なお、ステップＳ７０５の処理を行わずに、経路情報記憶部１８に古い交通情報を記憶させたままとしてもよい。
【００３６】
外部情報センタ４から取得される交通情報は、出発日時の他に現況や将来を含む複数の時刻情報が指定されると、その指定した時刻情報に対応する複数の交通情報となる。経路探索部１６は、交通情報が提供される交通情報エリアを経路探索システム１が通過する時刻をその交通情報エリアと出発地との直線距離に基づいて見積もるなどして出発地から各地点への通過予想時刻を大まかに見積もり、その通過予想時刻に基づいて交通情報が取得され、各地点間の経路計算が実行される。
【００３７】
本実施の形態の経路探索システム１が経路探索に用いる交通情報を外部情報センタ４から取得する構成としたが、過去の交通情報あるいは過去の交通情報に基づいて日種毎に計算された統計交通情報を、地図データ１９などを記憶する記憶装置に予め記憶させる構成としても良い。この場合、上述した経路要求が日種に応じた経路探索の探索条件を含んでいても良い。
【００３８】
また、経路探索システム１が外部から取得する情報は交通情報に限らず、経路探索システム１は、施設情報、通行料金、観光情報など様々な外部情報を取得し、経路計算に用いることもある。外部情報センタ４から得られる外部情報が交通情報と同様に変化する情報であり、変化する外部情報を用いて計算した経路情報は、その外部情報が更新された時点でその利用価値を失うため、経路情報記憶部１８から削除される必要がある。
【００３９】
経路探索部１６は、地図データ１９の道路上にマッチングした探索地点からその探索地点に対応する複数の地点の各々までの距離を考慮し、経路コストを補正する。図８は、経路探索部１６による経路コストの補正処理フローの一例を示す図であり、図２のステップＳ２１３に対応する。図９は、図８における経路コストの補正処理フローを説明するための経路補正例を示す図である。
【００４０】
経路探索部１６の経路計算で得られた経路コスト（所要時間や距離など）は、地図の道路ノードにマッチングされた探索地点間の経路コストである。その探索地点に対応する地点、あるいは探索地点が集約探索地点の場合にはその集約探索地点に対応する地点群に属する地点の各々と探索地点との間の移動コストは、その経路コストに含まれない。その移動コストは、例えば図９における地点１０１０と探索地点１０００との間の移動コスト、あるいは地点１０２０〜１０４０の各々と探索地点１０００との間の移動コストである。探索地点とその探索地点に対応する地点との距離が極めて近い場合は問題ないが、探索地点として設定されている道路ノードと離れた位置に対応する地点が存在する場合や、交通渋滞などによって探索地点とこれに対応する地点との間のリンク移動コストが距離に関係なく大きいことも考えられる。そのため、経路探索部１６は、本処理によってそれら両地点間の移動コストを推定し経路コストを補正する。本補正処理は、図２のステップＳ２１３に示すように、経路探索部１６によって、ステップＳ２１２における複数地点間の経路計算が終了した後、ステップＳ２１４の直前に実行する。
【００４１】
経路探索部１６は、複数の地点から未処理の地点を選択し（ステップＳ８０１）、選択した地点に対応する位置情報を参照する（ステップＳ８０２）。経路探索部１６は、当該地点から当該地点の近傍リンクに垂線を下ろし、垂線距離の最も短いリンクを近傍リンクとして選択し、垂線と交差する近傍リンク上の地点を最近傍点とする（ステップＳ８０３）。図９の例では、選択した地点が地点１０１０の場合、所定範囲内に垂線１０１３を下ろす近傍リンクが存在し、最近傍点１０１１が設定される。しかし、選択した地点が地点１０３０の場合のように所定範囲内に垂線を下ろす近傍リンクが存在せず、最近傍点が設定できない場合（ステップＳ８０４でＮｏ）、経路探索部１６は、上記の選択した地点と当該地点の探索地点とを結ぶ直線距離を計算し（ステップＳ８０７）、得られた距離と所定の速度とに基づき旅行時間を計算する（ステップＳ８０８）。地点１０３０が選択された場合、ステップＳ８０７で計算されるこの直線距離は直線１０１４の距離となる。ステップＳ８０８における所定の速度は、周囲リンクの速度情報、すなわち規制速度や交通情報から得た速度など、またはその周囲リンクのリンクコストから計算によって得られる速度としてもよい。あるいは、例えばプローブカーなどの車両の過去の走行データから得られる速度としてもよい。ステップＳ２１１およびＳ２１２で検索された全ての経路のうち、ステップＳ８０１で選択された地点に対応する探索地点を出発地または目的地とする経路に対して、この選択された地点と探索地点との間の距離と旅行時間とを追加して（ステップＳ８１２）、ステップＳ８１１へ進む。
【００４２】
一方、最近傍点を設定できた場合（ステップＳ８０４でＹｅｓ）は、経路探索部１６は最近傍点とステップＳ８０１で選択された地点との間の距離を計算する（ステップＳ８０５）。経路探索部１６は、ステップＳ８０５で得られた距離と最近傍点が設定されたリンクの速度情報、すなわち規制速度や交通情報から得た速度などとから移動時間を計算する（ステップＳ８０６）。経路探索部１６は、ステップＳ８０５で得られた距離とステップＳ８０６で得られた旅行時間と、図２のステップＳ２０８で決定された経路とコストとをステップＳ８０９およびＳ８１０の処理を用いて補正する。ステップＳ８０９では、選択した地点に対応する探索地点を端点とする経路を、最近傍点を端点とする経路に補正する。図９の例では、地点１０１０を選択対象としたとき、この地点１０１０に対応する探索地点１０００を端点とする補正対象の経路１０１２が、この経路上の最近傍点１０１１を端点とした経路に補正される。補正対象の経路上に最近傍点が存在しない場合、その経路に対して端点と最近傍点との間の経路を追加することで補正が行われる。この補正は選択した地点を出発地または目的地とする全ての経路について実行される。次に、ステップＳ８１０において、ステップＳ８０９で補正した経路に、最近傍点からステップＳ８０１で選択された地点までの経路情報を追加し、最終的な経路情報を計算する処理を実行する。経路探索部１６は、全ての地点についての補正処理を終えるまで処理を繰り返す（ステップＳ８１１）。
【００４３】
このように、選択された地点の最近傍点と探索地点との間の経路の旅行時間や距離を、その探索地点を出発地または目的地ノードとして得られた確定経路の旅行時間や距離から差し引いて（あるいは加算して）、最近傍点を端点とする経路の経路情報を計算する。本実施の形態では、最近傍点が見つからなかったとき、ステップＳ８０７、Ｓ８０８、およびＳ８１２において、地点から対応する探索地点まで（あるいはその逆）の経路情報をその確定経路の確定経路情報に含めて、最終的な地点間経路を生成する。しかし、全ての地点において、最近傍点を用いずに、地点と対応する探索地点との間の経路情報を用いて補正しても良い。このとき、より詳細な地図データを用いて、この地点と対応する探索地点との間の近距離探索で経路情報を取得する。しかし、地点とこれに対応する探索地点とを直線で結んで旅行時間や距離を計算してもよい。
【００４４】
−−−第２の実施の形態−−−
図１０は、第２の実施の形態における経路探索システム１が、確定経路を用いて探索対象ノードを絞込む動作手順を示すフローチャートである。
【００４５】
基本手順は図２に示す手順と同様であるため、同一の符号を付した共通する処理ステップについての説明を省略し、図２に示す処理と異なる処理を説明する。経路探索部１６が選択した候補ノードを始点とする各ノードへの確定経路が存在する場合（ステップＳ２０７でＹｅｓ）は、経路探索部１６は、出発ノードからその候補ノードまでの到達コストと、その候補ノードから上記各ノードへの確定経路のコストとに基づき、各ノードにおける上限コストを設定する（ステップＳ９０１）。各ノードの上限コストは、例えば候補ノードの到達コストと上記確定経路のコストとの和として決定される。確定経路のコストは図５に示すコストデータ５２０として管理されるが、本実施の形態において、経路データ５３０は管理されない。
【００４６】
経路探索部１６は、各ノードの到達コストがそのノードに設定された上限コストよりも小さいノードを、コスト更新決定対象ノード（候補ノード）とする（ステップＳ９０２）。このように確定経路を用いて経路計算の対象ノードを絞り込むことで、経路計算に関わる計算量が削減されるので、計算時間の短縮が可能となる。第１の実施の形態においては、確定経路データとして記憶された確定経路がそのまま、出発地からその確定経路に対応する候補ノードを経由して各ノードへ至る経路に含まれる。しかし、本実施の形態においては、確定経路を用いて絞り込まれた上限コスト範囲内のノードを経由する経路が経路計算によって得られる。図２のステップＳ２１０において、その経路計算が行われるとともに、その経路計算で得られた経路が、出発地から目的地群の各ノードへ至る経路として経路情報記憶部に記憶される。
【００４７】
以上、第１および第２の実施の形態による経路探索システム１は、Ｎ地点間の全ての組合せの経路を組合せ毎に要求するよりも少ないリクエスト回数でＮ地点間の全ての経路要求を受け付け、Ｎ地点間の全ての組合せの経路を組合せ毎に応答するよりも少ないレスポンス回数でＮ地点間の全ての経路情報を配送計画システム２へ提供する。したがって、経路探索システム１の、経路探索システム１を利用する配送計画システム２などのアプリケーションとの間のインタフェース１１０に要する処理負荷が軽減できるようになる。
【００４８】
更に、Ｎ地点間の経路探索過程で、経路が確定したノード間の経路を記憶し、記憶した確定経路を新たな探索地点間の経路計算に利用することで、経路計算における計算量が削減され、より短い時間でＮ地点間の経路が計算される。
【符号の説明】
【００４９】
１ 経路探索システム
２ 配送計画システム
３ ローカルネットワーク
４ 外部情報センタ
５ ブロードバンドネットワーク
１１ 通信インタフェース部
１２ 外部情報取得部
１３ 外部情報記憶部
１４ 端末要求受付部
１５ 経路条件設定部
１６ 経路探索部
１７ 経路情報提供部
１８ 経路情報記憶部
１９ 地図データ
４０１、４０２ 道路ノード
４１０〜４１５ 地点
４２０ 地点群
４２１ 重心座標
５１０ 探索条件
５２０ コストデータ
５３０ 経路データ
【特許請求の範囲】
【請求項１】
複数の地点のうちの２地点の全ての組合せにおける該２地点間の第１経路全ての探索要求を受け付ける受付手段と、
前記受付手段によって前記探索要求が受け付けられると、前記探索要求に含まれる探索条件に基づいて前記第１経路を全て探索する探索手段と、
前記探索手段によって探索された前記第１経路を全て含む経路情報を送信する提供手段とを備え、
前記受付手段が前記探索要求を受け付ける回数と、前記提供手段が前記経路情報を送信する回数とが、いずれも前記複数の地点の地点数よりも小さいことを特徴とする経路探索システム。
【請求項２】
請求項１に記載の経路探索システムにおいて、
前記探索手段によって前記第１経路の各経路が探索されるとき、該各経路が経由する第１候補ノードから該各経路が経由する第２候補ノードまでの区間、または前記第１候補ノードから該各経路の目的地までの区間の第２経路に関する経路関連情報を、前記探索条件に対応付けて記憶する記憶手段と、
前記記憶手段によって前記経路関連情報が記録された後に前記探索手段によって前記第１経路の各経路が探索され、かつ該各経路が前記第２経路を含むとき、前記前記記憶手段を参照して前記経路関連情報を検索する検索手段とをさらに備え、
前記探索手段は、前記探索条件と前記経路関連情報とに基づいて前記第１経路を全て探索することを特徴とする経路探索システム。
【請求項３】
請求項２に記載の経路探索システムにおいて、
外部サーバから出発日時および交通情報を取得する取得手段をさらに備え、
前記探索条件は、前記出発日時に対応する前記交通情報に基づいて前記第１経路が探索されることを含むことを特徴とする経路探索システム。
【請求項４】
請求項３に記載の経路探索システムにおいて、
前記取得手段は、前記出発日時に対応する前記交通情報とともに、前記複数の地点の各地点の通過予想時刻に対応する前記交通情報を取得し、
前記探索条件は、前記出発日時に対応する前記交通情報とともに、前記各地点の通過予想時刻に対応する前記交通情報に基づいて前記第１経路が探索されることを含むことを特徴とする経路探索システム。
【請求項５】
請求項４に記載の経路探索システムにおいて、
前記取得手段が前記出発日時に対応する前記交通情報を取得したとき、前記記憶手段に記憶される前記経路関連情報を削除する削除手段をさらに備え、
前記記憶手段は、新たに前記第２経路を前記探索条件に対応づけて記憶することを特徴とする経路探索システム。
【請求項６】
請求項４に記載の経路探索システムにおいて、
前記交通情報は統計交通情報を含むことを特徴とする経路探索システム。
【請求項７】
請求項６に記載の経路探索システムにおいて、
前記統計交通情報は日種に応じて構成され、
前記探索条件は、前記日種に応じた前記統計交通情報に基づいて前記第１経路が探索されることを含むことを特徴とする経路探索システム。
【請求項８】
請求項２乃至７のいずれか１項に記載の経路探索システムにおいて、
前記探索条件は、道路種別条件、幅員条件、および車線数条件を含む複数の条件を含み、
前記検索手段は前記複数の条件の各条件に対応する前記第２経路を検索し、
前記探索手段は該各条件に基づいて前記第１経路を探索することを特徴とする経路探索システム。
【請求項９】
請求項２乃至８のいずれか１項に記載の経路探索システムにおいて、
前記経路関連情報は前記第２経路のコスト情報を含み、
前記探索手段は、前記探索条件と前記経路関連情報とに基づいて、前記第１経路を全て探索するとともに前記第１経路の各々のコストを決定することを特徴とする経路探索システム。
【請求項１０】
請求項９に記載の経路探索システムにおいて、
前記経路関連情報は前記第２経路と該第２経路のコスト情報とを含み、
前記探索手段は、前記探索条件と前記経路関連情報とに基づいて前記各経路の出発地から前記第１候補ノードまでの区間の第３経路および該第３経路のコストを決定し、前記第２経路および該第２経路の前記コスト情報と、前記第３経路および該第３経路の前記コストとに基づいて、前記第１経路を全て探索するとともに前記第１経路の各々のコストを決定することを特徴とする経路探索システム。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の経路探索システムにおいて、
前記複数の地点を複数の道路ノードに夫々対応付ける対応付け手段をさらに備え、
前記第１経路は、前記複数の道路ノードのうちの２つのノードの全ての組合せにおける該２つのノード間の第４経路と、該２つのノードと該２つのノードに夫々対応付けられた２地点との間の第５経路および第６経路とを含み、
前記探索手段は、前記探索条件に基づいて前記第４経路を全て探索するとともに、前記第４経路に対応する前記第５経路のコストおよび前記第６経路のコストを探索することによって、前記第１経路を全て探索するとともに前記第１経路の各々のコストを決定することを特徴とする経路探索システム。
【請求項１２】
請求項１１に記載の経路探索システムにおいて、
前記対応付け手段は、前記複数の地点のうち、互いに近接する一部の地点を１つの道路ノードに対応付けることを特徴とする経路探索システム。
【請求項１】
複数の地点のうちの２地点の全ての組合せにおける該２地点間の第１経路全ての探索要求を受け付ける受付手段と、
前記受付手段によって前記探索要求が受け付けられると、前記探索要求に含まれる探索条件に基づいて前記第１経路を全て探索する探索手段と、
前記探索手段によって探索された前記第１経路を全て含む経路情報を送信する提供手段とを備え、
前記受付手段が前記探索要求を受け付ける回数と、前記提供手段が前記経路情報を送信する回数とが、いずれも前記複数の地点の地点数よりも小さいことを特徴とする経路探索システム。
【請求項２】
請求項１に記載の経路探索システムにおいて、
前記探索手段によって前記第１経路の各経路が探索されるとき、該各経路が経由する第１候補ノードから該各経路が経由する第２候補ノードまでの区間、または前記第１候補ノードから該各経路の目的地までの区間の第２経路に関する経路関連情報を、前記探索条件に対応付けて記憶する記憶手段と、
前記記憶手段によって前記経路関連情報が記録された後に前記探索手段によって前記第１経路の各経路が探索され、かつ該各経路が前記第２経路を含むとき、前記前記記憶手段を参照して前記経路関連情報を検索する検索手段とをさらに備え、
前記探索手段は、前記探索条件と前記経路関連情報とに基づいて前記第１経路を全て探索することを特徴とする経路探索システム。
【請求項３】
請求項２に記載の経路探索システムにおいて、
外部サーバから出発日時および交通情報を取得する取得手段をさらに備え、
前記探索条件は、前記出発日時に対応する前記交通情報に基づいて前記第１経路が探索されることを含むことを特徴とする経路探索システム。
【請求項４】
請求項３に記載の経路探索システムにおいて、
前記取得手段は、前記出発日時に対応する前記交通情報とともに、前記複数の地点の各地点の通過予想時刻に対応する前記交通情報を取得し、
前記探索条件は、前記出発日時に対応する前記交通情報とともに、前記各地点の通過予想時刻に対応する前記交通情報に基づいて前記第１経路が探索されることを含むことを特徴とする経路探索システム。
【請求項５】
請求項４に記載の経路探索システムにおいて、
前記取得手段が前記出発日時に対応する前記交通情報を取得したとき、前記記憶手段に記憶される前記経路関連情報を削除する削除手段をさらに備え、
前記記憶手段は、新たに前記第２経路を前記探索条件に対応づけて記憶することを特徴とする経路探索システム。
【請求項６】
請求項４に記載の経路探索システムにおいて、
前記交通情報は統計交通情報を含むことを特徴とする経路探索システム。
【請求項７】
請求項６に記載の経路探索システムにおいて、
前記統計交通情報は日種に応じて構成され、
前記探索条件は、前記日種に応じた前記統計交通情報に基づいて前記第１経路が探索されることを含むことを特徴とする経路探索システム。
【請求項８】
請求項２乃至７のいずれか１項に記載の経路探索システムにおいて、
前記探索条件は、道路種別条件、幅員条件、および車線数条件を含む複数の条件を含み、
前記検索手段は前記複数の条件の各条件に対応する前記第２経路を検索し、
前記探索手段は該各条件に基づいて前記第１経路を探索することを特徴とする経路探索システム。
【請求項９】
請求項２乃至８のいずれか１項に記載の経路探索システムにおいて、
前記経路関連情報は前記第２経路のコスト情報を含み、
前記探索手段は、前記探索条件と前記経路関連情報とに基づいて、前記第１経路を全て探索するとともに前記第１経路の各々のコストを決定することを特徴とする経路探索システム。
【請求項１０】
請求項９に記載の経路探索システムにおいて、
前記経路関連情報は前記第２経路と該第２経路のコスト情報とを含み、
前記探索手段は、前記探索条件と前記経路関連情報とに基づいて前記各経路の出発地から前記第１候補ノードまでの区間の第３経路および該第３経路のコストを決定し、前記第２経路および該第２経路の前記コスト情報と、前記第３経路および該第３経路の前記コストとに基づいて、前記第１経路を全て探索するとともに前記第１経路の各々のコストを決定することを特徴とする経路探索システム。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の経路探索システムにおいて、
前記複数の地点を複数の道路ノードに夫々対応付ける対応付け手段をさらに備え、
前記第１経路は、前記複数の道路ノードのうちの２つのノードの全ての組合せにおける該２つのノード間の第４経路と、該２つのノードと該２つのノードに夫々対応付けられた２地点との間の第５経路および第６経路とを含み、
前記探索手段は、前記探索条件に基づいて前記第４経路を全て探索するとともに、前記第４経路に対応する前記第５経路のコストおよび前記第６経路のコストを探索することによって、前記第１経路を全て探索するとともに前記第１経路の各々のコストを決定することを特徴とする経路探索システム。
【請求項１２】
請求項１１に記載の経路探索システムにおいて、
前記対応付け手段は、前記複数の地点のうち、互いに近接する一部の地点を１つの道路ノードに対応付けることを特徴とする経路探索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１６８１０３（Ｐ２０１２−１６８１０３Ａ）
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願番号】特願２０１１−３０８７２（Ｐ２０１１−３０８７２）
【出願日】平成２３年２月１６日（２０１１．２．１６）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願日】平成２３年２月１６日（２０１１．２．１６）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
[ Back to top ]