経路探索装置及び経路探索プログラム
【課題】発着地追加時のルート探索を短時間で行うことを目的とする。
【解決手段】経路探索装置１００を用いたルート探索において、異なる出発地点から同一の目的地点までの経路を探索する場合、地点指定部１０７が出発地点と目的地点を逆転させ、かつ、属性データ変換部１０３が交通規制を逆転させた地図データで経路探索部１０２がルート探索を行い、経路変換部１０５が結果情報を、逆転させる。これにより、経路探索装置１００は、１つの出発地点から複数の目的地点までの経路を計算するルート探索と同様に、複数の出発地点から１つの目的地点までの経路をまとめて計算する。
【解決手段】経路探索装置１００を用いたルート探索において、異なる出発地点から同一の目的地点までの経路を探索する場合、地点指定部１０７が出発地点と目的地点を逆転させ、かつ、属性データ変換部１０３が交通規制を逆転させた地図データで経路探索部１０２がルート探索を行い、経路変換部１０５が結果情報を、逆転させる。これにより、経路探索装置１００は、１つの出発地点から複数の目的地点までの経路を計算するルート探索と同様に、複数の出発地点から１つの目的地点までの経路をまとめて計算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置及び経路探索プログラムに関するものである。本発明は、特に、ルート（経路）逆探索を行う装置及びプログラムに関するものである。
【背景技術】
【０００２】
従来のルート探索は、出発地と目的地を与えられると、その間の所要時間、走行距離、経由する交差点（ノード）のリストなどが求められるものである（例えば、特許文献１及び２参照）。従来のルート探索では、同じ出発地を持つ「出発地−目的地」の組み合わせについて、まとめて探索する機能が広く紹介されている（図９（ａ）参照）。この機能により、例えば１，０００箇所の発着地間全てについて、所要時間と走行距離を求める、即ちルート探索を行う場合、１，０００×（１，０００−１）＝９９９，０００回（出発地と目的地が同一の場合、ルート探索は不要なので左記計算式となる）のルート探索をする必要がなく、１，０００回のルート探索で済ませることができる（図１０（ａ）参照）。
【特許文献１】特開２００１−５０７７０号公報
【特許文献２】特開２０００−３３７９１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記の例では、既に計算された１，０００箇所の発着地に対して、１箇所発着地を追加する場合、
・既存１０００件を出発地とし、新規１件を目的地とする探索・・・１０００件
・新規１件を出発地とし、既存１０００件を目的地とする１対多探索・・・１件
の合計１００１件の探索をしなくてはならなかった（図１０（ｂ）参照）。これは、他の例でも同様である。このため、従来のルート探索では、追加件数に対して、非常に長いルート探索時間を必要としていた。
【０００４】
本発明は、発着地追加時のルート探索を短時間で行うことを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る経路探索装置は、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする。
【０００６】
前記属性データは、前記属性として各道路の一方の地点から他方の地点への進行可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする。
【０００７】
前記属性データは、前記属性として各道路の進行方向ごとのコストを示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、１つの出発地点から複数の目的地点までのコストの総和が最小となる経路を計算することを特徴とする。
【０００８】
前記コストは、各道路の進行方向ごとの所要時間と距離と設定速度と車線数との少なくともいずれかから求められる係数であることを特徴とする。
【０００９】
また、本発明に係る経路探索装置は、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする。
【００１０】
前記属性データは、前記属性として各２つの道路を繋ぐ地点の一方の道路から他方の道路への進入出可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする。
【００１１】
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、Ｎ個（Ｎは２以上の整数）の地点をそれぞれ出発地点とし、当該Ｎ個の地点のうち出発地点を除くＮ−１個の地点を目的地点とする経路を、Ｎ個の出発地点ごとに計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算されたＮ個の出発地点からＮ個の目的地点までの経路を記憶装置に記憶する経路記憶部を備え、
前記地点指定部は、前記Ｎ個の地点以外の地点である追加地点を前記１つの出発地点として指定するとともに、前記Ｎ個の地点を前記複数の目的地点として指定し、
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第１の経路を計算するとともに、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第２の経路を計算し、
前記経路変換部は、前記経路探索部により計算された第２の経路を、前記Ｎ個の地点から前記追加地点まで逆方向に辿る第３の経路に変換し、
前記経路探索装置は、さらに、
前記経路記憶部により記憶されたＮ個の出発地点からＮ個の目的地点までの経路と前記経路探索部により計算された第１の経路と前記経路変換部により出力された第３の経路とを合わせてＮ＋１個の出発地点からＮ＋１個の目的地点までの経路を出力装置により出力する経路出力部を備えることを特徴とする。
【００１２】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記属性データ変換部は、前記第２の地図データ記憶部により記憶された地図データに含まれる属性データが、前記地点指定部により指定された地点が接する道路が前記地点指定部により指定された地点が接する車線の進行方向と逆方向への一方通行であることを示すように、当該属性データを処理装置により変換し、変換した属性データを含む地図データを前記第２の地図データ記憶部に記憶させることを特徴とする。
【００１３】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点までの経路を計算し、
前記経路変換部は、前記経路探索部により計算された経路を、前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された地点又は当該地点が接する道路を繋ぐ地点まで逆方向に辿る経路に変換することを特徴とする。
【００１４】
本発明に係る経路探索プログラムは、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする。
【００１５】
また、本発明に係る経路探索プログラムは、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記第１の地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１６】
本発明では、経路探索装置において、属性データ変換部が、第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換し、第２の地図データ記憶部が、属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶し、経路探索部が、第２の地図データ記憶部により記憶された地図データに基づき、一の地点を出発地点とし、他の複数の地点を目的地点とする経路を処理装置により計算し、経路変換部が、経路探索部により計算された経路を、他の複数の地点から一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力することにより、発着地追加時のルート探索を短時間で行うことが可能となる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施の形態について、図を用いて説明する。
【００１８】
実施の形態１．
本実施の形態では、経路探索装置が、ルート（「経路」ともいう）探索において、異なる出発地（「出発地点」ともいう）と同一の目的地（「目的地点」ともいう）を持つ「出発地−目的地」の組み合わせがある場合、出発地と目的地を逆転させ、かつ、交通規制を逆転させた地図データでルート探索を行い、結果情報を、逆転させる。これにより、異なる出発地と同一の目的地を持つ「出発地−目的地」について、まとめてルート探索を行うことが可能になる。
【００１９】
図１は、本実施の形態に係る経路探索装置１００の構成を示す図である。
【００２０】
図１において、経路探索装置１００は、第１の地図データ記憶部１０１、経路探索部１０２、属性データ変換部１０３、第２の地図データ記憶部１０４、経路変換部１０５、経路記憶部１０６、地点指定部１０７、経路出力部１０８を備える。また、経路探索装置１００は、記憶装置１５１、処理装置１５２、入力装置１５３、出力装置１５４などのハードウェア装置を備える（又はこれらのハードウェア装置が経路探索装置１００に接続される）。これらのハードウェア装置は経路探索装置１００の各部によって利用される。
【００２１】
第１の地図データ記憶部１０１は、地図データを記憶装置１５１に記憶する。地図データは、ノードデータとリンクデータと属性データとを含むデータである。ノードデータは複数の地点（ノード）を示し、リンクデータはノードを結ぶ複数の道路（リンク）を示す。ここで、複数の地点の各々は少なくとも１つの道路の端点となる。複数の地点のうち、特に、２つ以上の道路を繋ぐ地点を交差点という。車両などが交差点を通過（直進、左折、又は右折）する場合にどの道路から進入してどの道路へ進出するかをその交差点の進入出方向という。交差点の進入出方向は、進入元の道路と進出先の道路によって定まる（進入元及び進出先の道路それぞれにおける交差点と反対側の端点によって定まるともいえる）。進入元の道路と進出先の道路が逆になれば、交差点の進入出方向は逆方向になる。また、ここで、複数の道路の各々は２つの地点を結ぶ。車両などが道路を走行する場合にどの地点からどの地点まで進行するかをその道路の進行方向という。属性データは、各交差点の進入出方向ごとの属性、又は／及び各道路の進行方向ごとの属性を示す。本実施の形態では、属性データは、交通規制に係る属性を示すものとする。具体的には、属性データは、各交差点の進入出方向ごとの属性として、各交差点が繋ぐ２つの道路のうち、一方の道路から他方の道路への進入出可否（直進禁止、右折禁止、左折禁止などの規制の有無）を示すものとする。また、各道路の進行方向ごとの属性として、各道路が結ぶ２つの地点のうち、一方の地点から他方の地点への進行可否（一方通行の規制の有無と一方通行の規制がある場合にはその方向）を示すものとする。
【００２２】
経路探索部１０２は、第１の地図データ記憶部１０１により記憶された地図データ（以下、「ルート探索用地図データ」という）に基づき、１つの出発地点から複数の目的地点までの経路を処理装置１５２により計算する（この計算処理のことを「ルート探索」という）。本実施の形態では、経路探索部１０２は、ルート探索用地図データに含まれる属性データに基づき、通行できない経路を除外してルート探索を行う。属性データが、上記交通規制に係る属性以外にも、属性として各道路の進行方向ごとのコストを示す場合、経路探索部１０２は、ルート探索用地図データに含まれる属性データに基づき、１つの出発地点から複数の目的地点までのコストの総和が最小となる経路を計算する。コストは、例えば各道路の進行方向ごとの所要時間（例えば、車両の走行所要時間）、距離（例えば、車両の走行距離）、設定速度（例えば、車両の平均速度）、車線数など、又はこれらから求められる係数である（例えば、所要時間を距離÷設定速度で求めてもよい）。また、コストは、例えばダイクストラ法における重み付けとして利用してもよい。この場合、例えば、経路探索部１０２は、１つの出発地点から複数の目的地点までの最短経路をダイクストラ法によりまとめて計算する。
【００２３】
属性データ変換部１０３は、ルート探索用地図データに含まれる属性データ（以下、「元の属性データ」という）を、元の属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データ（以下、「読替え後の属性データ」という）に処理装置１５２により変換する（読替える）。また、属性データ変換部１０３は、ルート探索用地図データに含まれる属性データ（元の属性データ）を、元の属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データ（読替え後の属性データ）に処理装置１５２により変換する。属性データ変換部１０３が行う処理の詳細については後述する。
【００２４】
第２の地図データ記憶部１０４は、読替え後の属性データを含む地図データ（以下、「ルート逆探索用地図データ」という）を記憶装置１５１に記憶する。第２の地図データ記憶部１０４は、記憶装置１５１に記憶されたルート探索用地図データをルート逆探索用地図データに置換してもよいが、ルート探索用地図データをコピーし、コピーしたルート探索用地図データに含まれる元の属性データを読替え後の属性データに置換したものをルート逆探索用地図データとして記憶装置１５１に記憶するのが望ましい。
【００２５】
経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、一の地点を出発地点とし、他の複数の地点を目的地点とする経路を処理装置１５２により計算する（この計算処理のことを「ルート逆探索」という）。本実施の形態では、経路探索部１０２は、ルート逆探索用地図データに含まれる属性データに基づき、通行できない経路を除外してルート逆探索を行う。
【００２６】
経路変換部１０５は、経路探索部１０２により計算された経路を、他の複数の地点から一の地点まで逆方向に辿る経路に処理装置１５２により変換する。そして、変換した経路を複数の出発地点から１つの目的地点までの経路として出力装置１５４により出力する。
【００２７】
経路記憶部１０６は、経路探索部１０２により計算された１つ又は複数の出発地点から複数の目的地点までの経路を記憶装置１５１に記憶する。
【００２８】
地点指定部１０７は、経路探索部１０２にルート探索又はルート逆探索させる出発地点と目的地点とを入力装置１５３により指定する。
【００２９】
経路出力部１０８は、経路記憶部１０６により記憶された経路、経路探索部１０２により計算された経路、経路変換部１０５により出力された経路、又はそれらの組み合わせを出力装置１５４により出力する。
【００３０】
図２は、経路探索装置１００のハードウェア資源の一例を示す図である。
【００３１】
図２において、経路探索装置１００は、例えば、１台又は複数台のコンピュータで実現できる。経路探索装置１００は、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶ディスプレイ）の表示画面を有する表示装置９０１、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ装置９０６などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。経路探索装置１００は、例えば、ＬＡＮ（ローカルエリアネットワーク）、ＷＡＮ（ワイドエリアネットワーク）、インターネットなどのネットワークに接続されている。
【００３２】
経路探索装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、処理装置１５２の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカードリーダライタなどの記憶媒体が用いられてもよい。
【００３３】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置１５１の一例である。通信ボード９１５、キーボード９０２、ＦＤＤ９０４などは、入力装置１５３の一例である。また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置１５４の一例である。
【００３４】
通信ボード９１５は、ＬＡＮなどに接続されている。通信ボード９１５は、ＬＡＮに限らず、インターネット、ＩＳＤＮ（Ｉｎｔｅｇｒａｔｅｄ・Ｓｅｒｖｉｃｅｓ・Ｄｉｇｉｔａｌ・Ｎｅｔｗｏｒｋ）などのＷＡＮなどに接続されていても構わない。インターネットあるいはＷＡＮなどに接続されている場合、ゲートウェイを介して接続されていても構わない。
【００３５】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」、「〜手段」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。また、ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（ＩＤｅｎｔｉｆｉｅｒ）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として記憶されている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ディスクやメモリなどの記憶媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・制御・出力・印刷・表示などのＣＰＵ９１１の処理（動作）に用いられる。抽出・検索・参照・比較・演算・計算・制御・出力・印刷・表示などのＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００３６】
また、本実施の形態の説明において説明するブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号は、ＲＡＭ９１４などのメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク（ＭＤ）、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）などの記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００３７】
また、本実施の形態の説明において「〜部」、「〜手段」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」、「〜手段」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、ソフトウェアのみ、あるいは、素子・デバイス・基板・配線などのハードウェアのみ、あるいは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤなどの記録媒体に記憶される。このプログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」、「〜手段」としてコンピュータを機能させるものである。あるいは、本実施の形態の説明で述べる「〜部」、「〜手段」の手順や方法をコンピュータに実行させるものである。
【００３８】
図３、図４、及び図８は、経路探索装置１００の動作（処理）を示すフローチャートである。これらの図に示す処理により、ルート逆探索が実現し、同一の目的地に対して複数の出発地がある場合にも１回の探索で済ませることが可能となる。
【００３９】
図３において、第１の地図データ記憶部１０１は、ルート探索用地図データを記憶装置１５１に記憶する（ステップＳ１０１：第１の地図データ記憶処理）。経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、処理装置１５２によりＮ個（Ｎは２以上の整数）の出発地点からＮ個の目的地点まで（出発地、目的地のＮ×Ｎの組み合わせ）のルート探索を行う（ステップＳ１０２：経路探索処理）。経路探索部１０２は、さらに、ルート探索を行ったＮ個の出発地点からＮ個の目的地点までの経路情報（各経路における走行所要時間、走行距離、経由交差点リストなど）を出力する。経路記憶部１０６は、経路探索部１０２によりルート探索が行われたＮ個の出発地点からＮ個の目的地点までの経路情報を経路情報データファイル（図３には、「走行所要時間／走行距離／経由交差点リスト」と記載）として、記憶装置１５１に記憶する（ステップＳ１０３：経路記憶処理）。また、経路情報データファイルに記憶される「経由交差点リスト」とは、地点１から地点２までの経路を、例えば経由するノードを順番に列挙したリストである。
【００４０】
図４において、属性データ変換部１０３は、ステップＳ１０１で第１の地図データ記憶部１０１により記憶されたルート探索用地図データに含まれる属性データ（元の属性データ）を処理装置１５２により変換する（ステップＳ１０４：属性データ変換処理）。第２の地図データ記憶部１０４は、ルート探索用地図データとは別に、属性データ変換部１０３により変換された属性データ（読替え後の属性データ）を含むルート逆探索用地図データを用意して記憶装置１５１に記憶する（ステップＳ１０５：第２の地図データ記憶処理）。本実施の形態では、ステップＳ１０４において、属性データ変換部１０３は、元の属性データが示す交通規則（交通規制）を下記の通り読替える。前述したように、交通規制には道路自体についての規制と、交差点での規制の２つがある。それぞれについて説明する。
【００４１】
道路（リンク）に関する規制の読替え：
道路の端点を地点１、地点２とした場合、規制の種類と読替え方法は図５に示す通りである。
【００４２】
図５（ａ）において、属性データ変換部１０３は、
（１）元の属性データ２０１ａが地点１−地点２間に規制がない（この道路の２つの進行方向はいずれも進行可である）ことを示している場合、読替え後の属性データ３０１ａも地点１−地点２間に規制がないことを示す属性データとする。
（２）元の属性データ２０１ａが地点１−地点２間は通行禁止である（この道路の２つの進行方向はいずれも進行不可である）ことを示している場合、読替え後の属性データ３０１ａも地点１−地点２間が通行禁止であることを示す属性データとする。
（３）元の属性データ２０１ａが地点１から地点２への一方通行である（この道路の地点１から地点２への進行方向は進行可であるが、地点２から地点１への進行方向は進行不可である）ことを示している場合、読替え後の属性データ３０１ａは地点２から地点１への一方通行であることを示す属性データとする。
（４）元の属性データ２０１ａが地点２から地点１への一方通行である（この道路の地点２から地点１への進行方向は進行可であるが、地点１から地点２への進行方向は進行不可である）ことを示している場合、読替え後の属性データ３０１ａは地点１から地点２への一方通行であることを示す属性データとする。
【００４３】
例えば、各道路の進行方向ごとの属性を示す属性データが、図５（ｂ）に示すテーブルとして記憶装置１５１に記憶されているものとする。この場合、属性データ変換部１０３は、元の属性データ２０１ｂのテーブルに含まれる「規制」の列のデータを図５（ａ）に示した方法で読替えることにより（この例では、各データの値として図５（ａ）に示した番号を用いている）、読替え後の属性データ３０１ｂのテーブルを生成する。図５（ｂ）に示す例では、属性データ変換部１０３が、規制「３」（地点１→地点２の一方通行）を、規制「４」（地点１←地点２の一方通行）に読替え、また規制「１」（地点１−地点２間規制なし）を、規制「１」に読替え（あるいは読替え不要を予め指定しておいてもよい）、読替え後の属性データ３０１ｂとして記憶装置１５１に記憶する。同様に、各道路の進行方向ごとの属性を示す属性データが、図５（ｃ）に示すテーブルとして記憶されている場合、属性データ変換部１０３は、元の属性データ２０１ｃのテーブルに含まれる「地点１」の列のデータと「地点２」の列のデータとを相互に入れ替えることにより、読替え後の属性データ３０１ｃのテーブルを生成する。図５（ｃ）に示す例では、属性データ変換部１０３が、「地点１」、「地点２」に、「Ａ」、「Ｂ」と指定されているものを、「Ｂ」、「Ａ」に読替えて読替え後の属性データ３０１ｂとして記憶装置１５１に記憶する。なお、図５（ｂ）、図５（ｃ）により示した属性データ変換部１０３による読み替えは、どちらの方法でも適宜選択できる。また、図５（ｂ）、（ｃ）に示した各テーブルの「時間帯」の列は、時間帯によって交通規制に係る属性が異なる場合に用いるものであるが、必須ではない。
【００４４】
交差点（ノード）に関する規制の読替え：
交差点について、進入元の道路の端点を地点１、進出先の道路の端点を地点２とした場合、規制の種類と読替え方法は図６に示す通りである。
【００４５】
図６（ａ）において、属性データ変換部１０３は、
（１）元の属性データ２０２ａが地点１から交差点を経由して地点２へと通行可である（この交差点の地点１から地点２への進入出方向は進入出可である）ことを示している場合、読替え後の属性データ３０２ａは地点２から交差点を経由して地点１へと通行可であることを示す属性データとする。
（２）元の属性データ２０２ａが地点１から交差点を経由して地点２へは通行不可である（この交差点の地点１から地点２への進入出方向は進入出不可である）ことを示している場合、読替え後の属性データ３０２ａは地点２から交差点を経由して地点１へは通行不可であることを示す属性データとする。
【００４６】
例えば、各交差点の進入出方向ごとの属性を示す属性データが、図６（ｂ）に示すテーブルとして記憶装置１５１に記憶されているものとする。この場合、属性データ変換部１０３は、元の属性データ２０２ｂのテーブルに含まれる「地点１」の列のデータと「地点２」の列のデータとを相互に入れ替えることにより（この例では、「規制」の列の各データの値として図６（ａ）に示した番号を用いている）、読替え後の属性データ３０２ｂのテーブルを生成する。なお、時間帯によって交通規制に係る属性が異なる場合には、図５（ｂ）、（ｃ）に示したように、各テーブルに「時間帯」の列を設けてもよい。
【００４７】
なお、例えば速度情報（設定速度）など、道路の上り／下りを考慮して設定されている属性があれば、合わせて読替え（上り／下りの逆転）を行う。例えば、各道路の進行方向ごとの設定速度を示す属性データが、図７に示すテーブルとして記憶装置１５１に記憶されているものとする。この場合、属性データ変換部１０３は、元の属性データ２０３のテーブルに含まれる「上り」の列のデータと「下り」の列のデータとを相互に入れ替えることにより、読替え後の属性データ３０３のテーブルを生成する。なお、図７に示した各テーブルの「時間帯」の列は、時間帯によって（例えば、通勤ラッシュによる渋滞などを考慮して）設定速度が異なる場合に用いるものであるが、必須ではない。また、図７に示した各テーブルは、各道路を識別するために「道路」の列を含んでいるが、図５（ｂ）、（ｃ）に示した各テーブルの「地点１」、「地点２」の列を含んでいてもよい。
【００４８】
図８に示す経路探索装置１００の動作の開始前に、ステップＳ１０３では、経路記憶部１０６によりＮ個の出発地点からＮ個の目的地点までの経路が記憶されている。図８に示す経路探索装置１００の動作の目的は、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路を得ることである。そのためには、ステップＳ１０２で経路探索部１０２によりルート探索が行われたＮ個の地点以外の地点（以下、「追加地点」という）を新たに指定して（ノードデータが示す複数の地点から１つの地点が選択されるものとする）、追加地点から上記Ｎ個の地点までの経路と上記Ｎ個の地点から追加地点までの経路とを得る必要がある。
【００４９】
図８において、地点指定部１０７は、追加地点を入力装置１５３により指定する（ステップＳ１０６：地点指定処理）。ステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された地点（追加地点）を出発地点とし、上記Ｎ個の地点を目的地点とする第１の経路を計算する（この計算処理は通常のルート探索である）。これにより、追加地点から上記Ｎ個の地点までの経路が得られたことになる。したがって、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路を得るために、あとは上記Ｎ個の地点から追加地点までの経路を得る必要がある。
【００５０】
ステップＳ１０６において、地点指定部１０７は、さらに、出発地と目的地を一時的に逆転する。即ち、上記Ｎ個の地点から追加地点までの経路を得るために、地点指定部１０７は、追加地点を出発地点とし、上記Ｎ個の地点を目的地点として指定する。経路探索部１０２は、ステップＳ１０５で第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された地点（追加地点）を出発地点とし、上記Ｎ個の地点を目的地点とする第２の経路を計算する（この計算処理は、ルート逆探索用地図データを利用してルート探索を通常通り実施するルート逆探索である）（ステップＳ１０７：経路探索処理）。経路変換部１０５は、このルート探索結果について、所要時間・走行距離については探索時に対して出発地と目的地を逆転させ、即ち本来の出発地・目的地にして記憶装置１５１に格納する。また、経由する交差点（ノード）についても逆転させて格納する。即ち、経路変換部１０５は、経路探索部１０２により計算された第２の経路を、上記Ｎ個の地点から地点指定部１０７により指定された地点（追加地点）まで逆方向に辿る第３の経路に処理装置１５２により変換して出力する（ステップＳ１０８：経路変換処理）。これにより、上記Ｎ個の地点から追加地点までの経路も得られたことになる。
【００５１】
経路出力部１０８は、ステップＳ１０３で経路記憶部１０６により記憶されたＮ個の出発地点からＮ個の目的地点までの経路、ステップＳ１０２と同様に経路探索部１０２により計算された第１の経路、ステップＳ１０８で経路変換部１０５により出力された第３の経路を合わせて、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路を出力装置１５４により経路情報データファイル（図８には、「走行所要時間／走行距離／経由交差点リスト」と記載）に出力する（ステップＳ１０９：経路出力処理）。これにより、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路が得られたこととなる。このとき、ステップＳ１０３と同様に、経路記憶部１０６が、経路出力部１０８により出力されたＮ＋１個の出発地点からＮ＋１個の目的地点までの経路を記憶装置１５１に記憶してもよい。
【００５２】
このように、逆探索機能をもつルート探索を使用することにより、同じ目的地を持つ複数のルートをまとめて探索することが可能になる（図９（ｂ）参照）。この機能により、図１０（ｂ）に示した課題について、
・既存１０００件を出発地とし、新規１件を目的地とする探索・・・１件（改善部分）
・新規１件を出発地とし、既存１０００件を目的地とする１対多探索・・・１件
の合計２件の探索で済むようになり（図１０（ｃ）参照）、従来よりも短時間に、発着地追加時のルート探索することが可能になる。なお、図１０は、経路情報データファイル（図３、図８には、「走行所要時間／走行距離／経由交差点リスト」と記載）を模式的に表した表であるが、出発地（行方向）と目的地（列方向）で特定される枠には、発着地間の走行所要時間、走行距離、経由交差点リストが登録される。
【００５３】
また、経路探索部１０２に関する処理は何ら変更することなく、経路探索部１０２に対する入力データと、出力データとを操作することで、逆探索機能を実現できることも本実施の形態の特徴である。
【００５４】
さらに、本実施の形態により、発着地（地点）追加時のルート探索を短時間で行うことができ、経路情報データファイルを短時間で更新することができるようになる。それにより、例えば、経路情報を用いる配送・配車計画策定システムに、本実施の形態で出力する経路情報を受け渡すように構成するとき、更新された経路情報の受け渡しが容易になる。
【００５５】
実施の形態２．
本実施の形態について、主に実施の形態１との差異を説明する。
【００５６】
実施の形態１で説明した経路探索装置１００が、例えば、荷物を配送するトラックなどの車両が走行する経路を探索する場合、現実の出発地点と目的地点において車両を左付け（「左寄せ」ともいう）することを考慮してもよい（ここでは、日本のように車両が左側通行の道路を前提としているため、「左付け」であるが、右側通行の場合には「右付け」となる）。
【００５７】
図１１は、車両４００を左付けすることを考慮する場合に、車両４００のルート探索を行う方法の一例を示す図である。
【００５８】
図１１において、車両４００が店舗Ｘ（現実の出発地点の一例）に左付けした状態で出発し、店舗Ｙ（現実の目的地点の一例）に左付けして到着する経路とその逆方向（店舗Ｙから店舗Ｘまでの）経路を探索することが目的である。ここで、店舗Ｘが左側にある道路Ｘ、店舗Ｙが左側にある道路Ｙの途中では、車両４００はＵターンしない、あるいはＵターンできないものとする。また、図１１（ａ）に示すように、店舗Ｘは道路Ｘの端点ではなく、地点Ａ、Ｂが道路Ｘの端点であるとする。同様に、図１１（ｂ）に示すように、店舗Ｙは道路Ｙの端点ではなく、地点Ｃ、Ｄが道路Ｙの端点であるとする。道路Ｘ、Ｙは、車線数が２以上（片側１車線以上）の道路であるとする。
【００５９】
以下では、図１１と、実施の形態１で用いた図面を用いて、出発地点と目的地点において、車両４００を左付けするルート探索及びルート逆探索を行う方法を説明する。
【００６０】
本実施の形態では、経路探索部１０２は、ルート探索及びルート逆探索を行う際に、現実の出発地点がある道路を現実の出発地点がある側の進行方向への一方通行の道路として、現実の目的地点がある道路を現実の目的地点がある側の進行方向への一方通行の道路として用いる。以下では、説明の便宜上、現実の出発地点と目的地点がそれぞれ１つの場合について説明するが、それぞれが複数ある場合も以下と同様の処理が可能である。
【００６１】
まず、出発地、目的地に左寄せにする方法について、経路探索装置１００がルート逆探索の前に行う処理の流れを簡単に説明する。図８で示したステップＳ１０６で地点指定部１０７が出発地と目的地を一時的に逆転するが、このとき、属性データ変換部１０３が、出発地、目的地が接する道路に関して、出発地、目的地が接する車線の進行方向と逆方向に一方通行であるという情報をルート逆探索用地図データに付加する。その後、経路探索装置１００は、ステップＳ１０７以降の処理に移る。図１１に示した例では、出発地が店舗Ｘの場合、道路Ｘが地点Ｂから地点Ａへの一方通行であり、目的地が店舗Ｙの場合、道路Ｙが地点Ｄから地点Ｃへの一方通行であるという情報がルート逆探索用地図データに付加される。
【００６２】
例えば、実施の形態１で説明した図８のステップＳ１０６において、地点指定部１０７は、店舗Ｘと店舗Ｙを指定する。ここでは、店舗Ｘと店舗Ｙもそれぞれノードデータが示す複数の地点の１つであるとする。属性データ変換部１０３は、一時的に、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに含まれる属性データを処理装置１５２により変換する。具体的には、属性データ変換部１０３は、属性データを、道路Ｘが地点Ａから地点Ｂへの一方通行であり、道路Ｙが地点Ｃから地点Ｄへの一方通行であることを示すものに変換する。図３のステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを出発地点とし、店舗Ｙを目的地点とする経路を計算する。このとき、ルート探索用地図データに含まれる属性データは、道路Ｘが地点Ａから地点Ｂへの一方通行であり、道路Ｙが地点Ｃから地点Ｄへの一方通行であることを示しているため、経路探索部１０２は、経路中、最初に経由する地点（出発地点の直後の地点）を地点Ｂとし、最後に経由する地点（目的地点の直前の地点）を地点Ｃとしてルート探索を行うことになる。属性データ変換部１０３は、ルート探索が完了した後、道路Ｘ、Ｙに係る属性を変換した属性データを元に戻す。また、属性データ変換部１０３は、一時的に、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに含まれる属性データを処理装置１５２により変換する。具体的には、属性データ変換部１０３は、属性データを、道路Ｘが地点Ｂから地点Ａへの一方通行であり、道路Ｙが地点Ｄから地点Ｃへの一方通行であることを示すものに変換する。図８のステップＳ１０７において、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを出発地点とし、店舗Ｙを目的地点とする経路を計算する。このとき、ルート逆探索用地図データに含まれる属性データは、道路Ｘが地点Ｂから地点Ａへの一方通行であり、道路Ｙが地点Ｄから地点Ｃへの一方通行であることを示しているため、経路探索部１０２は、経路中、最初に経由する地点を地点Ａとし、最後に経由する地点を地点Ｄとしてルート逆探索を行うことになる。属性データ変換部１０３は、ルート逆探索が完了した後、道路Ｘ、Ｙに係る属性を変換した属性データを元に戻す。ステップＳ１０８において、経路変換部１０５は、経路探索部１０２により計算された経路を、店舗Ｙから店舗Ｘまで逆方向に辿る経路に変換して出力する。このとき、経路変換部１０５により出力される経路中、最初に経由する地点は地点Ｄ、最後に経由する地点は地点Ａとなっている。ステップＳ１０９において、経路出力部１０８は、経路探索部１０２により計算された店舗Ｘから店舗Ｙまでの経路と経路変換部１０５により出力された店舗Ｙから店舗Ｘまでの経路とを出力する。
【００６３】
以上のように、本実施の形態では、地点指定部１０７が、リンクデータが示す道路であって複数車線（片側１車線以上）の道路に接する地点（図１１の例では、店舗Ｘ、Ｙ）を出発地点、目的地点、又はその両方として指定する（図１１の例では、ルート検索時は店舗Ｘが出発地点、店舗Ｙが目的地点、ルート逆検索時には店舗Ｙが出発地点、店舗Ｘが目的地点）。属性データ変換部１０３は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに含まれる属性データが、地点指定部１０７により指定された店舗Ｘ、Ｙが接する道路（図１１の例では、道路Ｘ、Ｙ）が地点指定部１０７により指定された店舗Ｘ、Ｙが接する車線（図１１の例では、道路Ｘ、Ｙの左車線）の進行方向（図１１の例では、地点Ａ→地点Ｂ、地点Ｃ→地点Ｄ）への一方通行であることを示すように、当該属性データを処理装置１５２により変換する。そして、変換した属性データを含む地図データを第１の地図データ記憶部１０１にルート探索用地図データとして記憶させる。経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘから店舗Ｙまでの第１の経路を計算する。また、属性データ変換部１０３は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに含まれる属性データが、地点指定部１０７により指定された店舗Ｘ、Ｙが接する道路（図１１の例では、道路Ｘ、Ｙ）が地点指定部１０７により指定された店舗Ｘ、Ｙが接する車線（図１１の例では、道路Ｘ、Ｙの左車線）の進行方向と逆方向（図１１の例では、地点Ｂ→地点Ａ、地点Ｄ→地点Ｃ）への一方通行であることを示すように、当該属性データを処理装置１５２により変換する。そして、変換した属性データを含む地図データを第２の地図データ記憶部１０４にルート逆探索用地図データとして記憶させる。経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘから店舗Ｙまでの第２の経路を計算する。経路変換部１０５は、経路探索部１０２により計算された第２の経路を、店舗Ｙから店舗Ｘまで逆方向に辿る第３の経路に変換する。経路出力部１０８は、経路探索部１０２により計算された第１の経路と経路変換部１０５により出力された第３の経路とを出力する。これにより、車両４００を左付けすることを考慮して車両４００のルート探索を行うことが可能となる。また、本実施の形態においても、経路探索部１０２に関する処理は何ら変更することなく、経路探索部１０２に対する入力データと、出力データとを操作することで、逆探索機能を実現できることが特徴である。
【００６４】
実施の形態３．
本実施の形態について、主に実施の形態２との差異を説明する。
【００６５】
図１１を用いて説明したように、実施の形態２は、経路探索部１０２に関する処理は何ら変更することなく、経路探索部１０２に対する入力データと、出力データとを操作することで、車両４００を左付けするルート逆検索の機能を実現するものである。一方、本実施の形態は、経路探索部１０２に関する処理を変更することにより、車両４００を左付けするルート逆検索の機能を実現するものである。
【００６６】
以下では、図１１と、実施の形態１で用いた図面を用いて、出発地点と目的地点において、車両４００を左付けするルート探索及びルート逆探索を行う方法を説明する。
【００６７】
第１の方法として、経路探索部１０２は、ルート探索及びルート逆探索を行う際に、現実の出発地点から前進したときの最初の地点を出発地点として、現実の目的地点から後退したときの最初の地点を目的地点として用いることができる。以下では、説明の便宜上、現実の出発地点と目的地点がそれぞれ１つの場合について説明するが、それぞれが複数ある場合も以下と同様の処理が可能である。
【００６８】
例えば、実施の形態１で説明した図８のステップＳ１０６において、地点指定部１０７は、処理装置１５２により、店舗Ｘをルート探索用の出発地点として地点Ｂに読替え、店舗Ｙをルート探索用の目的地点として地点Ｃに読替え、読替えた地点Ｂ、Ｃを指定する（この読替え処理は、経路探索部１０２がルート探索をする際に独自に行ってもよい）。図３のステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された地点Ｂを出発地点とし、地点Ｃを目的地点とする経路を計算する。また、図８のステップＳ１０６において、地点指定部１０７は、店舗Ｙから店舗Ｘまでの経路をルート逆探索するために、さらに、出発地と目的地を一時的に逆転する。即ち、地点指定部１０７は、目的地となる店舗Ｘをルート逆探索用の出発地点として地点Ａに読替え、出発地となる店舗Ｙをルート逆探索用の目的地点として地点Ｄに読み替え、読替えた地点Ａ、Ｄを指定する（この読替え処理は、経路探索部１０２がルート逆探索をする際に独自に行ってもよい）。図８のステップＳ１０７において、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された地点Ａを出発地点とし、地点Ｄを目的地点とする経路を計算する。ステップＳ１０８において、経路変換部１０５は、経路探索部１０２により計算された経路を、地点Ｄから地点Ａまで逆方向に辿る経路に変換して出力する。ステップＳ１０９において、経路出力部１０８は、経路探索部１０２により計算された地点Ｂから地点Ｃまでの経路と経路変換部１０５により出力された地点Ｄから地点Ａまでの経路とを、それぞれ店舗Ｘから店舗Ｙまでの経路とその逆方向の経路として出力する。
【００６９】
第２の方法として、経路探索部１０２は、ルート探索及びルート逆探索を行う際に、現実の出発地点がある道路を経路中の最初の道路（進行方向は、現実の出発地点がある側の進行方向）として、現実の目的地点がある道路を経路中の最後の道路（進行方向は、現実の目的地点がある側の進行方向）として用いることができる。以下では、説明の便宜上、現実の出発地点と目的地点がそれぞれ１つの場合について説明するが、それぞれが複数ある場合も以下と同様の処理が可能である。
【００７０】
例えば、実施の形態１で説明した図８のステップＳ１０６において、地点指定部１０７は、店舗Ｘと店舗Ｙを指定する。図３のステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを地点Ａに読替えて出発地点とし、店舗Ｙを地点Ｄに読替えて目的地点とする経路を計算する。このとき、経路探索部１０２は、経路中、最初の道路を道路Ｘ（地点Ａから地点Ｂへの進行方向）に固定し、最後の道路を道路Ｙ（地点Ｃから地点Ｄへの進行方向）に固定する。また、図８のステップＳ１０７において、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを地点Ｂに読替えて出発地点とし、店舗Ｙを地点Ｃに読替えて目的地点とする経路を計算する。このとき、経路探索部１０２は、経路中、最初の道路を道路Ｘ（地点Ｂから地点Ａへの進行方向）に固定し、最後の道路を道路Ｙ（地点Ｄから地点Ｃへの進行方向）に固定する。ステップＳ１０８において、経路変換部１０５は、経路探索部１０２により計算された経路を、地点Ｃから地点Ｂまで逆方向に辿る経路に変換して出力する。ステップＳ１０９において、経路出力部１０８は、経路探索部１０２により計算された地点Ａから地点Ｄまでの経路（道路Ｘを経路から削除して、地点Ｂから地点Ｄまでの経路としてもよい）と経路変換部１０５により出力された地点Ｃから地点Ｂまでの経路（道路Ｙを経路から削除して、地点Ｄから地点Ｂまでの経路としてもよい）とを、それぞれ店舗Ｘから店舗Ｙまでの経路とその逆方向の経路として出力する。
【００７１】
以上のように、本実施の形態では、地点指定部１０７が、リンクデータが示す道路であって複数車線（片側１車線以上）の道路に接する地点（図１１の例では、店舗Ｘ、Ｙ）を出発地点、目的地点、又はその両方として指定する（図１１の例では、ルート検索時は店舗Ｘが出発地点、店舗Ｙが目的地点、ルート逆検索時には店舗Ｙが出発地点、店舗Ｘが目的地点）。経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘが接する道路Ｘを繋ぐ地点（図１１の例では、地点Ａ又はＢ）から地点指定部１０７により指定された店舗Ｙが接する道路Ｙを繋ぐ地点（図１１の例では、地点Ｃ又はＤ）までの第１の経路を計算する。また、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘが接する道路Ｘを繋ぐ地点（図１１の例では、地点Ａ又はＢ）から地点指定部１０７により指定された店舗Ｙが接する道路Ｙを繋ぐ地点（図１１の例では、地点Ｃ又はＤ）までの第１の経路を計算する。経路変換部１０５は、経路探索部１０２により計算された第２の経路を、地点Ｃ又はＤから地点Ａ又はＢまで逆方向に辿る第３の経路に変換する。経路出力部１０８は、経路探索部１０２により計算された第１の経路と経路変換部１０５により出力された第３の経路とを出力する。これにより、車両４００を左付けすることを考慮して車両４００のルート探索を行うことが可能となる。
【図面の簡単な説明】
【００７２】
【図１】実施の形態１に係る経路探索装置の構成を示すブロック図である。
【図２】実施の形態１における経路探索装置のハードウェア資源の一例を示す図である。
【図３】実施の形態１に係る経路探索装置の動作を示すフローチャートである。
【図４】実施の形態１に係る経路探索装置の動作を示すフローチャートである。
【図５】実施の形態１における元の属性データと読替え後の属性データとを示す図である。
【図６】実施の形態１における元の属性データと読替え後の属性データとを示す図である。
【図７】実施の形態１における元の属性データと読替え後の属性データとを示す図である。
【図８】実施の形態１に係る経路探索装置の動作を示すフローチャートである。
【図９】実施の形態１におけるルート探索の概念を示す図である。
【図１０】実施の形態１におけるルート探索の概念を示す図である。
【図１１】実施の形態２におけるルート探索の一例を示す図である。
【符号の説明】
【００７３】
１００ 経路探索装置、１０１ 第１の地図データ記憶部、１０２ 経路探索部、１０３ 属性データ変換部、１０４ 第２の地図データ記憶部、１０５ 経路変換部、１０６ 経路記憶部、１０７ 地点指定部、１０８ 経路出力部、１５１ 記憶装置、１５２ 処理装置、１５３ 入力装置、１５４ 出力装置、２０１，２０２，２０３ 元の属性データ、３０１，３０２，３０３ 読替え後の属性データ、４００ 車両、５００ 店舗、９０１ 表示装置、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ装置、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信ボード、９２０ 磁気ディスク装置、９２１ オペレーティングシステム、９２３ プログラム群、９２４ ファイル群。
【技術分野】
【０００１】
本発明は、経路探索装置及び経路探索プログラムに関するものである。本発明は、特に、ルート（経路）逆探索を行う装置及びプログラムに関するものである。
【背景技術】
【０００２】
従来のルート探索は、出発地と目的地を与えられると、その間の所要時間、走行距離、経由する交差点（ノード）のリストなどが求められるものである（例えば、特許文献１及び２参照）。従来のルート探索では、同じ出発地を持つ「出発地−目的地」の組み合わせについて、まとめて探索する機能が広く紹介されている（図９（ａ）参照）。この機能により、例えば１，０００箇所の発着地間全てについて、所要時間と走行距離を求める、即ちルート探索を行う場合、１，０００×（１，０００−１）＝９９９，０００回（出発地と目的地が同一の場合、ルート探索は不要なので左記計算式となる）のルート探索をする必要がなく、１，０００回のルート探索で済ませることができる（図１０（ａ）参照）。
【特許文献１】特開２００１−５０７７０号公報
【特許文献２】特開２０００−３３７９１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記の例では、既に計算された１，０００箇所の発着地に対して、１箇所発着地を追加する場合、
・既存１０００件を出発地とし、新規１件を目的地とする探索・・・１０００件
・新規１件を出発地とし、既存１０００件を目的地とする１対多探索・・・１件
の合計１００１件の探索をしなくてはならなかった（図１０（ｂ）参照）。これは、他の例でも同様である。このため、従来のルート探索では、追加件数に対して、非常に長いルート探索時間を必要としていた。
【０００４】
本発明は、発着地追加時のルート探索を短時間で行うことを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る経路探索装置は、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする。
【０００６】
前記属性データは、前記属性として各道路の一方の地点から他方の地点への進行可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする。
【０００７】
前記属性データは、前記属性として各道路の進行方向ごとのコストを示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、１つの出発地点から複数の目的地点までのコストの総和が最小となる経路を計算することを特徴とする。
【０００８】
前記コストは、各道路の進行方向ごとの所要時間と距離と設定速度と車線数との少なくともいずれかから求められる係数であることを特徴とする。
【０００９】
また、本発明に係る経路探索装置は、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする。
【００１０】
前記属性データは、前記属性として各２つの道路を繋ぐ地点の一方の道路から他方の道路への進入出可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする。
【００１１】
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、Ｎ個（Ｎは２以上の整数）の地点をそれぞれ出発地点とし、当該Ｎ個の地点のうち出発地点を除くＮ−１個の地点を目的地点とする経路を、Ｎ個の出発地点ごとに計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算されたＮ個の出発地点からＮ個の目的地点までの経路を記憶装置に記憶する経路記憶部を備え、
前記地点指定部は、前記Ｎ個の地点以外の地点である追加地点を前記１つの出発地点として指定するとともに、前記Ｎ個の地点を前記複数の目的地点として指定し、
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第１の経路を計算するとともに、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第２の経路を計算し、
前記経路変換部は、前記経路探索部により計算された第２の経路を、前記Ｎ個の地点から前記追加地点まで逆方向に辿る第３の経路に変換し、
前記経路探索装置は、さらに、
前記経路記憶部により記憶されたＮ個の出発地点からＮ個の目的地点までの経路と前記経路探索部により計算された第１の経路と前記経路変換部により出力された第３の経路とを合わせてＮ＋１個の出発地点からＮ＋１個の目的地点までの経路を出力装置により出力する経路出力部を備えることを特徴とする。
【００１２】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記属性データ変換部は、前記第２の地図データ記憶部により記憶された地図データに含まれる属性データが、前記地点指定部により指定された地点が接する道路が前記地点指定部により指定された地点が接する車線の進行方向と逆方向への一方通行であることを示すように、当該属性データを処理装置により変換し、変換した属性データを含む地図データを前記第２の地図データ記憶部に記憶させることを特徴とする。
【００１３】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点までの経路を計算し、
前記経路変換部は、前記経路探索部により計算された経路を、前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された地点又は当該地点が接する道路を繋ぐ地点まで逆方向に辿る経路に変換することを特徴とする。
【００１４】
本発明に係る経路探索プログラムは、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする。
【００１５】
また、本発明に係る経路探索プログラムは、
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記第１の地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１６】
本発明では、経路探索装置において、属性データ変換部が、第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換し、第２の地図データ記憶部が、属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶し、経路探索部が、第２の地図データ記憶部により記憶された地図データに基づき、一の地点を出発地点とし、他の複数の地点を目的地点とする経路を処理装置により計算し、経路変換部が、経路探索部により計算された経路を、他の複数の地点から一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力することにより、発着地追加時のルート探索を短時間で行うことが可能となる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施の形態について、図を用いて説明する。
【００１８】
実施の形態１．
本実施の形態では、経路探索装置が、ルート（「経路」ともいう）探索において、異なる出発地（「出発地点」ともいう）と同一の目的地（「目的地点」ともいう）を持つ「出発地−目的地」の組み合わせがある場合、出発地と目的地を逆転させ、かつ、交通規制を逆転させた地図データでルート探索を行い、結果情報を、逆転させる。これにより、異なる出発地と同一の目的地を持つ「出発地−目的地」について、まとめてルート探索を行うことが可能になる。
【００１９】
図１は、本実施の形態に係る経路探索装置１００の構成を示す図である。
【００２０】
図１において、経路探索装置１００は、第１の地図データ記憶部１０１、経路探索部１０２、属性データ変換部１０３、第２の地図データ記憶部１０４、経路変換部１０５、経路記憶部１０６、地点指定部１０７、経路出力部１０８を備える。また、経路探索装置１００は、記憶装置１５１、処理装置１５２、入力装置１５３、出力装置１５４などのハードウェア装置を備える（又はこれらのハードウェア装置が経路探索装置１００に接続される）。これらのハードウェア装置は経路探索装置１００の各部によって利用される。
【００２１】
第１の地図データ記憶部１０１は、地図データを記憶装置１５１に記憶する。地図データは、ノードデータとリンクデータと属性データとを含むデータである。ノードデータは複数の地点（ノード）を示し、リンクデータはノードを結ぶ複数の道路（リンク）を示す。ここで、複数の地点の各々は少なくとも１つの道路の端点となる。複数の地点のうち、特に、２つ以上の道路を繋ぐ地点を交差点という。車両などが交差点を通過（直進、左折、又は右折）する場合にどの道路から進入してどの道路へ進出するかをその交差点の進入出方向という。交差点の進入出方向は、進入元の道路と進出先の道路によって定まる（進入元及び進出先の道路それぞれにおける交差点と反対側の端点によって定まるともいえる）。進入元の道路と進出先の道路が逆になれば、交差点の進入出方向は逆方向になる。また、ここで、複数の道路の各々は２つの地点を結ぶ。車両などが道路を走行する場合にどの地点からどの地点まで進行するかをその道路の進行方向という。属性データは、各交差点の進入出方向ごとの属性、又は／及び各道路の進行方向ごとの属性を示す。本実施の形態では、属性データは、交通規制に係る属性を示すものとする。具体的には、属性データは、各交差点の進入出方向ごとの属性として、各交差点が繋ぐ２つの道路のうち、一方の道路から他方の道路への進入出可否（直進禁止、右折禁止、左折禁止などの規制の有無）を示すものとする。また、各道路の進行方向ごとの属性として、各道路が結ぶ２つの地点のうち、一方の地点から他方の地点への進行可否（一方通行の規制の有無と一方通行の規制がある場合にはその方向）を示すものとする。
【００２２】
経路探索部１０２は、第１の地図データ記憶部１０１により記憶された地図データ（以下、「ルート探索用地図データ」という）に基づき、１つの出発地点から複数の目的地点までの経路を処理装置１５２により計算する（この計算処理のことを「ルート探索」という）。本実施の形態では、経路探索部１０２は、ルート探索用地図データに含まれる属性データに基づき、通行できない経路を除外してルート探索を行う。属性データが、上記交通規制に係る属性以外にも、属性として各道路の進行方向ごとのコストを示す場合、経路探索部１０２は、ルート探索用地図データに含まれる属性データに基づき、１つの出発地点から複数の目的地点までのコストの総和が最小となる経路を計算する。コストは、例えば各道路の進行方向ごとの所要時間（例えば、車両の走行所要時間）、距離（例えば、車両の走行距離）、設定速度（例えば、車両の平均速度）、車線数など、又はこれらから求められる係数である（例えば、所要時間を距離÷設定速度で求めてもよい）。また、コストは、例えばダイクストラ法における重み付けとして利用してもよい。この場合、例えば、経路探索部１０２は、１つの出発地点から複数の目的地点までの最短経路をダイクストラ法によりまとめて計算する。
【００２３】
属性データ変換部１０３は、ルート探索用地図データに含まれる属性データ（以下、「元の属性データ」という）を、元の属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データ（以下、「読替え後の属性データ」という）に処理装置１５２により変換する（読替える）。また、属性データ変換部１０３は、ルート探索用地図データに含まれる属性データ（元の属性データ）を、元の属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データ（読替え後の属性データ）に処理装置１５２により変換する。属性データ変換部１０３が行う処理の詳細については後述する。
【００２４】
第２の地図データ記憶部１０４は、読替え後の属性データを含む地図データ（以下、「ルート逆探索用地図データ」という）を記憶装置１５１に記憶する。第２の地図データ記憶部１０４は、記憶装置１５１に記憶されたルート探索用地図データをルート逆探索用地図データに置換してもよいが、ルート探索用地図データをコピーし、コピーしたルート探索用地図データに含まれる元の属性データを読替え後の属性データに置換したものをルート逆探索用地図データとして記憶装置１５１に記憶するのが望ましい。
【００２５】
経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、一の地点を出発地点とし、他の複数の地点を目的地点とする経路を処理装置１５２により計算する（この計算処理のことを「ルート逆探索」という）。本実施の形態では、経路探索部１０２は、ルート逆探索用地図データに含まれる属性データに基づき、通行できない経路を除外してルート逆探索を行う。
【００２６】
経路変換部１０５は、経路探索部１０２により計算された経路を、他の複数の地点から一の地点まで逆方向に辿る経路に処理装置１５２により変換する。そして、変換した経路を複数の出発地点から１つの目的地点までの経路として出力装置１５４により出力する。
【００２７】
経路記憶部１０６は、経路探索部１０２により計算された１つ又は複数の出発地点から複数の目的地点までの経路を記憶装置１５１に記憶する。
【００２８】
地点指定部１０７は、経路探索部１０２にルート探索又はルート逆探索させる出発地点と目的地点とを入力装置１５３により指定する。
【００２９】
経路出力部１０８は、経路記憶部１０６により記憶された経路、経路探索部１０２により計算された経路、経路変換部１０５により出力された経路、又はそれらの組み合わせを出力装置１５４により出力する。
【００３０】
図２は、経路探索装置１００のハードウェア資源の一例を示す図である。
【００３１】
図２において、経路探索装置１００は、例えば、１台又は複数台のコンピュータで実現できる。経路探索装置１００は、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶ディスプレイ）の表示画面を有する表示装置９０１、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ装置９０６などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。経路探索装置１００は、例えば、ＬＡＮ（ローカルエリアネットワーク）、ＷＡＮ（ワイドエリアネットワーク）、インターネットなどのネットワークに接続されている。
【００３２】
経路探索装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、処理装置１５２の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカードリーダライタなどの記憶媒体が用いられてもよい。
【００３３】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置１５１の一例である。通信ボード９１５、キーボード９０２、ＦＤＤ９０４などは、入力装置１５３の一例である。また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置１５４の一例である。
【００３４】
通信ボード９１５は、ＬＡＮなどに接続されている。通信ボード９１５は、ＬＡＮに限らず、インターネット、ＩＳＤＮ（Ｉｎｔｅｇｒａｔｅｄ・Ｓｅｒｖｉｃｅｓ・Ｄｉｇｉｔａｌ・Ｎｅｔｗｏｒｋ）などのＷＡＮなどに接続されていても構わない。インターネットあるいはＷＡＮなどに接続されている場合、ゲートウェイを介して接続されていても構わない。
【００３５】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」、「〜手段」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。また、ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（ＩＤｅｎｔｉｆｉｅｒ）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として記憶されている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ディスクやメモリなどの記憶媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・制御・出力・印刷・表示などのＣＰＵ９１１の処理（動作）に用いられる。抽出・検索・参照・比較・演算・計算・制御・出力・印刷・表示などのＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００３６】
また、本実施の形態の説明において説明するブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号は、ＲＡＭ９１４などのメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク（ＭＤ）、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）などの記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００３７】
また、本実施の形態の説明において「〜部」、「〜手段」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」、「〜手段」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、ソフトウェアのみ、あるいは、素子・デバイス・基板・配線などのハードウェアのみ、あるいは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤなどの記録媒体に記憶される。このプログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」、「〜手段」としてコンピュータを機能させるものである。あるいは、本実施の形態の説明で述べる「〜部」、「〜手段」の手順や方法をコンピュータに実行させるものである。
【００３８】
図３、図４、及び図８は、経路探索装置１００の動作（処理）を示すフローチャートである。これらの図に示す処理により、ルート逆探索が実現し、同一の目的地に対して複数の出発地がある場合にも１回の探索で済ませることが可能となる。
【００３９】
図３において、第１の地図データ記憶部１０１は、ルート探索用地図データを記憶装置１５１に記憶する（ステップＳ１０１：第１の地図データ記憶処理）。経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、処理装置１５２によりＮ個（Ｎは２以上の整数）の出発地点からＮ個の目的地点まで（出発地、目的地のＮ×Ｎの組み合わせ）のルート探索を行う（ステップＳ１０２：経路探索処理）。経路探索部１０２は、さらに、ルート探索を行ったＮ個の出発地点からＮ個の目的地点までの経路情報（各経路における走行所要時間、走行距離、経由交差点リストなど）を出力する。経路記憶部１０６は、経路探索部１０２によりルート探索が行われたＮ個の出発地点からＮ個の目的地点までの経路情報を経路情報データファイル（図３には、「走行所要時間／走行距離／経由交差点リスト」と記載）として、記憶装置１５１に記憶する（ステップＳ１０３：経路記憶処理）。また、経路情報データファイルに記憶される「経由交差点リスト」とは、地点１から地点２までの経路を、例えば経由するノードを順番に列挙したリストである。
【００４０】
図４において、属性データ変換部１０３は、ステップＳ１０１で第１の地図データ記憶部１０１により記憶されたルート探索用地図データに含まれる属性データ（元の属性データ）を処理装置１５２により変換する（ステップＳ１０４：属性データ変換処理）。第２の地図データ記憶部１０４は、ルート探索用地図データとは別に、属性データ変換部１０３により変換された属性データ（読替え後の属性データ）を含むルート逆探索用地図データを用意して記憶装置１５１に記憶する（ステップＳ１０５：第２の地図データ記憶処理）。本実施の形態では、ステップＳ１０４において、属性データ変換部１０３は、元の属性データが示す交通規則（交通規制）を下記の通り読替える。前述したように、交通規制には道路自体についての規制と、交差点での規制の２つがある。それぞれについて説明する。
【００４１】
道路（リンク）に関する規制の読替え：
道路の端点を地点１、地点２とした場合、規制の種類と読替え方法は図５に示す通りである。
【００４２】
図５（ａ）において、属性データ変換部１０３は、
（１）元の属性データ２０１ａが地点１−地点２間に規制がない（この道路の２つの進行方向はいずれも進行可である）ことを示している場合、読替え後の属性データ３０１ａも地点１−地点２間に規制がないことを示す属性データとする。
（２）元の属性データ２０１ａが地点１−地点２間は通行禁止である（この道路の２つの進行方向はいずれも進行不可である）ことを示している場合、読替え後の属性データ３０１ａも地点１−地点２間が通行禁止であることを示す属性データとする。
（３）元の属性データ２０１ａが地点１から地点２への一方通行である（この道路の地点１から地点２への進行方向は進行可であるが、地点２から地点１への進行方向は進行不可である）ことを示している場合、読替え後の属性データ３０１ａは地点２から地点１への一方通行であることを示す属性データとする。
（４）元の属性データ２０１ａが地点２から地点１への一方通行である（この道路の地点２から地点１への進行方向は進行可であるが、地点１から地点２への進行方向は進行不可である）ことを示している場合、読替え後の属性データ３０１ａは地点１から地点２への一方通行であることを示す属性データとする。
【００４３】
例えば、各道路の進行方向ごとの属性を示す属性データが、図５（ｂ）に示すテーブルとして記憶装置１５１に記憶されているものとする。この場合、属性データ変換部１０３は、元の属性データ２０１ｂのテーブルに含まれる「規制」の列のデータを図５（ａ）に示した方法で読替えることにより（この例では、各データの値として図５（ａ）に示した番号を用いている）、読替え後の属性データ３０１ｂのテーブルを生成する。図５（ｂ）に示す例では、属性データ変換部１０３が、規制「３」（地点１→地点２の一方通行）を、規制「４」（地点１←地点２の一方通行）に読替え、また規制「１」（地点１−地点２間規制なし）を、規制「１」に読替え（あるいは読替え不要を予め指定しておいてもよい）、読替え後の属性データ３０１ｂとして記憶装置１５１に記憶する。同様に、各道路の進行方向ごとの属性を示す属性データが、図５（ｃ）に示すテーブルとして記憶されている場合、属性データ変換部１０３は、元の属性データ２０１ｃのテーブルに含まれる「地点１」の列のデータと「地点２」の列のデータとを相互に入れ替えることにより、読替え後の属性データ３０１ｃのテーブルを生成する。図５（ｃ）に示す例では、属性データ変換部１０３が、「地点１」、「地点２」に、「Ａ」、「Ｂ」と指定されているものを、「Ｂ」、「Ａ」に読替えて読替え後の属性データ３０１ｂとして記憶装置１５１に記憶する。なお、図５（ｂ）、図５（ｃ）により示した属性データ変換部１０３による読み替えは、どちらの方法でも適宜選択できる。また、図５（ｂ）、（ｃ）に示した各テーブルの「時間帯」の列は、時間帯によって交通規制に係る属性が異なる場合に用いるものであるが、必須ではない。
【００４４】
交差点（ノード）に関する規制の読替え：
交差点について、進入元の道路の端点を地点１、進出先の道路の端点を地点２とした場合、規制の種類と読替え方法は図６に示す通りである。
【００４５】
図６（ａ）において、属性データ変換部１０３は、
（１）元の属性データ２０２ａが地点１から交差点を経由して地点２へと通行可である（この交差点の地点１から地点２への進入出方向は進入出可である）ことを示している場合、読替え後の属性データ３０２ａは地点２から交差点を経由して地点１へと通行可であることを示す属性データとする。
（２）元の属性データ２０２ａが地点１から交差点を経由して地点２へは通行不可である（この交差点の地点１から地点２への進入出方向は進入出不可である）ことを示している場合、読替え後の属性データ３０２ａは地点２から交差点を経由して地点１へは通行不可であることを示す属性データとする。
【００４６】
例えば、各交差点の進入出方向ごとの属性を示す属性データが、図６（ｂ）に示すテーブルとして記憶装置１５１に記憶されているものとする。この場合、属性データ変換部１０３は、元の属性データ２０２ｂのテーブルに含まれる「地点１」の列のデータと「地点２」の列のデータとを相互に入れ替えることにより（この例では、「規制」の列の各データの値として図６（ａ）に示した番号を用いている）、読替え後の属性データ３０２ｂのテーブルを生成する。なお、時間帯によって交通規制に係る属性が異なる場合には、図５（ｂ）、（ｃ）に示したように、各テーブルに「時間帯」の列を設けてもよい。
【００４７】
なお、例えば速度情報（設定速度）など、道路の上り／下りを考慮して設定されている属性があれば、合わせて読替え（上り／下りの逆転）を行う。例えば、各道路の進行方向ごとの設定速度を示す属性データが、図７に示すテーブルとして記憶装置１５１に記憶されているものとする。この場合、属性データ変換部１０３は、元の属性データ２０３のテーブルに含まれる「上り」の列のデータと「下り」の列のデータとを相互に入れ替えることにより、読替え後の属性データ３０３のテーブルを生成する。なお、図７に示した各テーブルの「時間帯」の列は、時間帯によって（例えば、通勤ラッシュによる渋滞などを考慮して）設定速度が異なる場合に用いるものであるが、必須ではない。また、図７に示した各テーブルは、各道路を識別するために「道路」の列を含んでいるが、図５（ｂ）、（ｃ）に示した各テーブルの「地点１」、「地点２」の列を含んでいてもよい。
【００４８】
図８に示す経路探索装置１００の動作の開始前に、ステップＳ１０３では、経路記憶部１０６によりＮ個の出発地点からＮ個の目的地点までの経路が記憶されている。図８に示す経路探索装置１００の動作の目的は、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路を得ることである。そのためには、ステップＳ１０２で経路探索部１０２によりルート探索が行われたＮ個の地点以外の地点（以下、「追加地点」という）を新たに指定して（ノードデータが示す複数の地点から１つの地点が選択されるものとする）、追加地点から上記Ｎ個の地点までの経路と上記Ｎ個の地点から追加地点までの経路とを得る必要がある。
【００４９】
図８において、地点指定部１０７は、追加地点を入力装置１５３により指定する（ステップＳ１０６：地点指定処理）。ステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された地点（追加地点）を出発地点とし、上記Ｎ個の地点を目的地点とする第１の経路を計算する（この計算処理は通常のルート探索である）。これにより、追加地点から上記Ｎ個の地点までの経路が得られたことになる。したがって、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路を得るために、あとは上記Ｎ個の地点から追加地点までの経路を得る必要がある。
【００５０】
ステップＳ１０６において、地点指定部１０７は、さらに、出発地と目的地を一時的に逆転する。即ち、上記Ｎ個の地点から追加地点までの経路を得るために、地点指定部１０７は、追加地点を出発地点とし、上記Ｎ個の地点を目的地点として指定する。経路探索部１０２は、ステップＳ１０５で第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された地点（追加地点）を出発地点とし、上記Ｎ個の地点を目的地点とする第２の経路を計算する（この計算処理は、ルート逆探索用地図データを利用してルート探索を通常通り実施するルート逆探索である）（ステップＳ１０７：経路探索処理）。経路変換部１０５は、このルート探索結果について、所要時間・走行距離については探索時に対して出発地と目的地を逆転させ、即ち本来の出発地・目的地にして記憶装置１５１に格納する。また、経由する交差点（ノード）についても逆転させて格納する。即ち、経路変換部１０５は、経路探索部１０２により計算された第２の経路を、上記Ｎ個の地点から地点指定部１０７により指定された地点（追加地点）まで逆方向に辿る第３の経路に処理装置１５２により変換して出力する（ステップＳ１０８：経路変換処理）。これにより、上記Ｎ個の地点から追加地点までの経路も得られたことになる。
【００５１】
経路出力部１０８は、ステップＳ１０３で経路記憶部１０６により記憶されたＮ個の出発地点からＮ個の目的地点までの経路、ステップＳ１０２と同様に経路探索部１０２により計算された第１の経路、ステップＳ１０８で経路変換部１０５により出力された第３の経路を合わせて、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路を出力装置１５４により経路情報データファイル（図８には、「走行所要時間／走行距離／経由交差点リスト」と記載）に出力する（ステップＳ１０９：経路出力処理）。これにより、Ｎ＋１個の出発地点からＮ＋１個の目的地点までの経路が得られたこととなる。このとき、ステップＳ１０３と同様に、経路記憶部１０６が、経路出力部１０８により出力されたＮ＋１個の出発地点からＮ＋１個の目的地点までの経路を記憶装置１５１に記憶してもよい。
【００５２】
このように、逆探索機能をもつルート探索を使用することにより、同じ目的地を持つ複数のルートをまとめて探索することが可能になる（図９（ｂ）参照）。この機能により、図１０（ｂ）に示した課題について、
・既存１０００件を出発地とし、新規１件を目的地とする探索・・・１件（改善部分）
・新規１件を出発地とし、既存１０００件を目的地とする１対多探索・・・１件
の合計２件の探索で済むようになり（図１０（ｃ）参照）、従来よりも短時間に、発着地追加時のルート探索することが可能になる。なお、図１０は、経路情報データファイル（図３、図８には、「走行所要時間／走行距離／経由交差点リスト」と記載）を模式的に表した表であるが、出発地（行方向）と目的地（列方向）で特定される枠には、発着地間の走行所要時間、走行距離、経由交差点リストが登録される。
【００５３】
また、経路探索部１０２に関する処理は何ら変更することなく、経路探索部１０２に対する入力データと、出力データとを操作することで、逆探索機能を実現できることも本実施の形態の特徴である。
【００５４】
さらに、本実施の形態により、発着地（地点）追加時のルート探索を短時間で行うことができ、経路情報データファイルを短時間で更新することができるようになる。それにより、例えば、経路情報を用いる配送・配車計画策定システムに、本実施の形態で出力する経路情報を受け渡すように構成するとき、更新された経路情報の受け渡しが容易になる。
【００５５】
実施の形態２．
本実施の形態について、主に実施の形態１との差異を説明する。
【００５６】
実施の形態１で説明した経路探索装置１００が、例えば、荷物を配送するトラックなどの車両が走行する経路を探索する場合、現実の出発地点と目的地点において車両を左付け（「左寄せ」ともいう）することを考慮してもよい（ここでは、日本のように車両が左側通行の道路を前提としているため、「左付け」であるが、右側通行の場合には「右付け」となる）。
【００５７】
図１１は、車両４００を左付けすることを考慮する場合に、車両４００のルート探索を行う方法の一例を示す図である。
【００５８】
図１１において、車両４００が店舗Ｘ（現実の出発地点の一例）に左付けした状態で出発し、店舗Ｙ（現実の目的地点の一例）に左付けして到着する経路とその逆方向（店舗Ｙから店舗Ｘまでの）経路を探索することが目的である。ここで、店舗Ｘが左側にある道路Ｘ、店舗Ｙが左側にある道路Ｙの途中では、車両４００はＵターンしない、あるいはＵターンできないものとする。また、図１１（ａ）に示すように、店舗Ｘは道路Ｘの端点ではなく、地点Ａ、Ｂが道路Ｘの端点であるとする。同様に、図１１（ｂ）に示すように、店舗Ｙは道路Ｙの端点ではなく、地点Ｃ、Ｄが道路Ｙの端点であるとする。道路Ｘ、Ｙは、車線数が２以上（片側１車線以上）の道路であるとする。
【００５９】
以下では、図１１と、実施の形態１で用いた図面を用いて、出発地点と目的地点において、車両４００を左付けするルート探索及びルート逆探索を行う方法を説明する。
【００６０】
本実施の形態では、経路探索部１０２は、ルート探索及びルート逆探索を行う際に、現実の出発地点がある道路を現実の出発地点がある側の進行方向への一方通行の道路として、現実の目的地点がある道路を現実の目的地点がある側の進行方向への一方通行の道路として用いる。以下では、説明の便宜上、現実の出発地点と目的地点がそれぞれ１つの場合について説明するが、それぞれが複数ある場合も以下と同様の処理が可能である。
【００６１】
まず、出発地、目的地に左寄せにする方法について、経路探索装置１００がルート逆探索の前に行う処理の流れを簡単に説明する。図８で示したステップＳ１０６で地点指定部１０７が出発地と目的地を一時的に逆転するが、このとき、属性データ変換部１０３が、出発地、目的地が接する道路に関して、出発地、目的地が接する車線の進行方向と逆方向に一方通行であるという情報をルート逆探索用地図データに付加する。その後、経路探索装置１００は、ステップＳ１０７以降の処理に移る。図１１に示した例では、出発地が店舗Ｘの場合、道路Ｘが地点Ｂから地点Ａへの一方通行であり、目的地が店舗Ｙの場合、道路Ｙが地点Ｄから地点Ｃへの一方通行であるという情報がルート逆探索用地図データに付加される。
【００６２】
例えば、実施の形態１で説明した図８のステップＳ１０６において、地点指定部１０７は、店舗Ｘと店舗Ｙを指定する。ここでは、店舗Ｘと店舗Ｙもそれぞれノードデータが示す複数の地点の１つであるとする。属性データ変換部１０３は、一時的に、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに含まれる属性データを処理装置１５２により変換する。具体的には、属性データ変換部１０３は、属性データを、道路Ｘが地点Ａから地点Ｂへの一方通行であり、道路Ｙが地点Ｃから地点Ｄへの一方通行であることを示すものに変換する。図３のステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを出発地点とし、店舗Ｙを目的地点とする経路を計算する。このとき、ルート探索用地図データに含まれる属性データは、道路Ｘが地点Ａから地点Ｂへの一方通行であり、道路Ｙが地点Ｃから地点Ｄへの一方通行であることを示しているため、経路探索部１０２は、経路中、最初に経由する地点（出発地点の直後の地点）を地点Ｂとし、最後に経由する地点（目的地点の直前の地点）を地点Ｃとしてルート探索を行うことになる。属性データ変換部１０３は、ルート探索が完了した後、道路Ｘ、Ｙに係る属性を変換した属性データを元に戻す。また、属性データ変換部１０３は、一時的に、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに含まれる属性データを処理装置１５２により変換する。具体的には、属性データ変換部１０３は、属性データを、道路Ｘが地点Ｂから地点Ａへの一方通行であり、道路Ｙが地点Ｄから地点Ｃへの一方通行であることを示すものに変換する。図８のステップＳ１０７において、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを出発地点とし、店舗Ｙを目的地点とする経路を計算する。このとき、ルート逆探索用地図データに含まれる属性データは、道路Ｘが地点Ｂから地点Ａへの一方通行であり、道路Ｙが地点Ｄから地点Ｃへの一方通行であることを示しているため、経路探索部１０２は、経路中、最初に経由する地点を地点Ａとし、最後に経由する地点を地点Ｄとしてルート逆探索を行うことになる。属性データ変換部１０３は、ルート逆探索が完了した後、道路Ｘ、Ｙに係る属性を変換した属性データを元に戻す。ステップＳ１０８において、経路変換部１０５は、経路探索部１０２により計算された経路を、店舗Ｙから店舗Ｘまで逆方向に辿る経路に変換して出力する。このとき、経路変換部１０５により出力される経路中、最初に経由する地点は地点Ｄ、最後に経由する地点は地点Ａとなっている。ステップＳ１０９において、経路出力部１０８は、経路探索部１０２により計算された店舗Ｘから店舗Ｙまでの経路と経路変換部１０５により出力された店舗Ｙから店舗Ｘまでの経路とを出力する。
【００６３】
以上のように、本実施の形態では、地点指定部１０７が、リンクデータが示す道路であって複数車線（片側１車線以上）の道路に接する地点（図１１の例では、店舗Ｘ、Ｙ）を出発地点、目的地点、又はその両方として指定する（図１１の例では、ルート検索時は店舗Ｘが出発地点、店舗Ｙが目的地点、ルート逆検索時には店舗Ｙが出発地点、店舗Ｘが目的地点）。属性データ変換部１０３は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに含まれる属性データが、地点指定部１０７により指定された店舗Ｘ、Ｙが接する道路（図１１の例では、道路Ｘ、Ｙ）が地点指定部１０７により指定された店舗Ｘ、Ｙが接する車線（図１１の例では、道路Ｘ、Ｙの左車線）の進行方向（図１１の例では、地点Ａ→地点Ｂ、地点Ｃ→地点Ｄ）への一方通行であることを示すように、当該属性データを処理装置１５２により変換する。そして、変換した属性データを含む地図データを第１の地図データ記憶部１０１にルート探索用地図データとして記憶させる。経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘから店舗Ｙまでの第１の経路を計算する。また、属性データ変換部１０３は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに含まれる属性データが、地点指定部１０７により指定された店舗Ｘ、Ｙが接する道路（図１１の例では、道路Ｘ、Ｙ）が地点指定部１０７により指定された店舗Ｘ、Ｙが接する車線（図１１の例では、道路Ｘ、Ｙの左車線）の進行方向と逆方向（図１１の例では、地点Ｂ→地点Ａ、地点Ｄ→地点Ｃ）への一方通行であることを示すように、当該属性データを処理装置１５２により変換する。そして、変換した属性データを含む地図データを第２の地図データ記憶部１０４にルート逆探索用地図データとして記憶させる。経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘから店舗Ｙまでの第２の経路を計算する。経路変換部１０５は、経路探索部１０２により計算された第２の経路を、店舗Ｙから店舗Ｘまで逆方向に辿る第３の経路に変換する。経路出力部１０８は、経路探索部１０２により計算された第１の経路と経路変換部１０５により出力された第３の経路とを出力する。これにより、車両４００を左付けすることを考慮して車両４００のルート探索を行うことが可能となる。また、本実施の形態においても、経路探索部１０２に関する処理は何ら変更することなく、経路探索部１０２に対する入力データと、出力データとを操作することで、逆探索機能を実現できることが特徴である。
【００６４】
実施の形態３．
本実施の形態について、主に実施の形態２との差異を説明する。
【００６５】
図１１を用いて説明したように、実施の形態２は、経路探索部１０２に関する処理は何ら変更することなく、経路探索部１０２に対する入力データと、出力データとを操作することで、車両４００を左付けするルート逆検索の機能を実現するものである。一方、本実施の形態は、経路探索部１０２に関する処理を変更することにより、車両４００を左付けするルート逆検索の機能を実現するものである。
【００６６】
以下では、図１１と、実施の形態１で用いた図面を用いて、出発地点と目的地点において、車両４００を左付けするルート探索及びルート逆探索を行う方法を説明する。
【００６７】
第１の方法として、経路探索部１０２は、ルート探索及びルート逆探索を行う際に、現実の出発地点から前進したときの最初の地点を出発地点として、現実の目的地点から後退したときの最初の地点を目的地点として用いることができる。以下では、説明の便宜上、現実の出発地点と目的地点がそれぞれ１つの場合について説明するが、それぞれが複数ある場合も以下と同様の処理が可能である。
【００６８】
例えば、実施の形態１で説明した図８のステップＳ１０６において、地点指定部１０７は、処理装置１５２により、店舗Ｘをルート探索用の出発地点として地点Ｂに読替え、店舗Ｙをルート探索用の目的地点として地点Ｃに読替え、読替えた地点Ｂ、Ｃを指定する（この読替え処理は、経路探索部１０２がルート探索をする際に独自に行ってもよい）。図３のステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された地点Ｂを出発地点とし、地点Ｃを目的地点とする経路を計算する。また、図８のステップＳ１０６において、地点指定部１０７は、店舗Ｙから店舗Ｘまでの経路をルート逆探索するために、さらに、出発地と目的地を一時的に逆転する。即ち、地点指定部１０７は、目的地となる店舗Ｘをルート逆探索用の出発地点として地点Ａに読替え、出発地となる店舗Ｙをルート逆探索用の目的地点として地点Ｄに読み替え、読替えた地点Ａ、Ｄを指定する（この読替え処理は、経路探索部１０２がルート逆探索をする際に独自に行ってもよい）。図８のステップＳ１０７において、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された地点Ａを出発地点とし、地点Ｄを目的地点とする経路を計算する。ステップＳ１０８において、経路変換部１０５は、経路探索部１０２により計算された経路を、地点Ｄから地点Ａまで逆方向に辿る経路に変換して出力する。ステップＳ１０９において、経路出力部１０８は、経路探索部１０２により計算された地点Ｂから地点Ｃまでの経路と経路変換部１０５により出力された地点Ｄから地点Ａまでの経路とを、それぞれ店舗Ｘから店舗Ｙまでの経路とその逆方向の経路として出力する。
【００６９】
第２の方法として、経路探索部１０２は、ルート探索及びルート逆探索を行う際に、現実の出発地点がある道路を経路中の最初の道路（進行方向は、現実の出発地点がある側の進行方向）として、現実の目的地点がある道路を経路中の最後の道路（進行方向は、現実の目的地点がある側の進行方向）として用いることができる。以下では、説明の便宜上、現実の出発地点と目的地点がそれぞれ１つの場合について説明するが、それぞれが複数ある場合も以下と同様の処理が可能である。
【００７０】
例えば、実施の形態１で説明した図８のステップＳ１０６において、地点指定部１０７は、店舗Ｘと店舗Ｙを指定する。図３のステップＳ１０２と同様に、経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを地点Ａに読替えて出発地点とし、店舗Ｙを地点Ｄに読替えて目的地点とする経路を計算する。このとき、経路探索部１０２は、経路中、最初の道路を道路Ｘ（地点Ａから地点Ｂへの進行方向）に固定し、最後の道路を道路Ｙ（地点Ｃから地点Ｄへの進行方向）に固定する。また、図８のステップＳ１０７において、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘを地点Ｂに読替えて出発地点とし、店舗Ｙを地点Ｃに読替えて目的地点とする経路を計算する。このとき、経路探索部１０２は、経路中、最初の道路を道路Ｘ（地点Ｂから地点Ａへの進行方向）に固定し、最後の道路を道路Ｙ（地点Ｄから地点Ｃへの進行方向）に固定する。ステップＳ１０８において、経路変換部１０５は、経路探索部１０２により計算された経路を、地点Ｃから地点Ｂまで逆方向に辿る経路に変換して出力する。ステップＳ１０９において、経路出力部１０８は、経路探索部１０２により計算された地点Ａから地点Ｄまでの経路（道路Ｘを経路から削除して、地点Ｂから地点Ｄまでの経路としてもよい）と経路変換部１０５により出力された地点Ｃから地点Ｂまでの経路（道路Ｙを経路から削除して、地点Ｄから地点Ｂまでの経路としてもよい）とを、それぞれ店舗Ｘから店舗Ｙまでの経路とその逆方向の経路として出力する。
【００７１】
以上のように、本実施の形態では、地点指定部１０７が、リンクデータが示す道路であって複数車線（片側１車線以上）の道路に接する地点（図１１の例では、店舗Ｘ、Ｙ）を出発地点、目的地点、又はその両方として指定する（図１１の例では、ルート検索時は店舗Ｘが出発地点、店舗Ｙが目的地点、ルート逆検索時には店舗Ｙが出発地点、店舗Ｘが目的地点）。経路探索部１０２は、第１の地図データ記憶部１０１により記憶されたルート探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘが接する道路Ｘを繋ぐ地点（図１１の例では、地点Ａ又はＢ）から地点指定部１０７により指定された店舗Ｙが接する道路Ｙを繋ぐ地点（図１１の例では、地点Ｃ又はＤ）までの第１の経路を計算する。また、経路探索部１０２は、第２の地図データ記憶部１０４により記憶されたルート逆探索用地図データに基づき、地点指定部１０７により指定された店舗Ｘが接する道路Ｘを繋ぐ地点（図１１の例では、地点Ａ又はＢ）から地点指定部１０７により指定された店舗Ｙが接する道路Ｙを繋ぐ地点（図１１の例では、地点Ｃ又はＤ）までの第１の経路を計算する。経路変換部１０５は、経路探索部１０２により計算された第２の経路を、地点Ｃ又はＤから地点Ａ又はＢまで逆方向に辿る第３の経路に変換する。経路出力部１０８は、経路探索部１０２により計算された第１の経路と経路変換部１０５により出力された第３の経路とを出力する。これにより、車両４００を左付けすることを考慮して車両４００のルート探索を行うことが可能となる。
【図面の簡単な説明】
【００７２】
【図１】実施の形態１に係る経路探索装置の構成を示すブロック図である。
【図２】実施の形態１における経路探索装置のハードウェア資源の一例を示す図である。
【図３】実施の形態１に係る経路探索装置の動作を示すフローチャートである。
【図４】実施の形態１に係る経路探索装置の動作を示すフローチャートである。
【図５】実施の形態１における元の属性データと読替え後の属性データとを示す図である。
【図６】実施の形態１における元の属性データと読替え後の属性データとを示す図である。
【図７】実施の形態１における元の属性データと読替え後の属性データとを示す図である。
【図８】実施の形態１に係る経路探索装置の動作を示すフローチャートである。
【図９】実施の形態１におけるルート探索の概念を示す図である。
【図１０】実施の形態１におけるルート探索の概念を示す図である。
【図１１】実施の形態２におけるルート探索の一例を示す図である。
【符号の説明】
【００７３】
１００ 経路探索装置、１０１ 第１の地図データ記憶部、１０２ 経路探索部、１０３ 属性データ変換部、１０４ 第２の地図データ記憶部、１０５ 経路変換部、１０６ 経路記憶部、１０７ 地点指定部、１０８ 経路出力部、１５１ 記憶装置、１５２ 処理装置、１５３ 入力装置、１５４ 出力装置、２０１，２０２，２０３ 元の属性データ、３０１，３０２，３０３ 読替え後の属性データ、４００ 車両、５００ 店舗、９０１ 表示装置、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ装置、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信ボード、９２０ 磁気ディスク装置、９２１ オペレーティングシステム、９２３ プログラム群、９２４ ファイル群。
【特許請求の範囲】
【請求項１】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする経路探索装置。
【請求項２】
前記属性データは、前記属性として各道路の一方の地点から他方の地点への進行可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記属性データは、前記属性として各道路の進行方向ごとのコストを示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、１つの出発地点から複数の目的地点までのコストの総和が最小となる経路を計算することを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記コストは、各道路の進行方向ごとの所要時間と距離と設定速度と車線数との少なくともいずれかから求められる係数であることを特徴とする請求項３に記載の経路探索装置。
【請求項５】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする経路探索装置。
【請求項６】
前記属性データは、前記属性として各２つの道路を繋ぐ地点の一方の道路から他方の道路への進入出可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする請求項５に記載の経路探索装置。
【請求項７】
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、Ｎ個（Ｎは２以上の整数）の地点をそれぞれ出発地点とし、当該Ｎ個の地点のうち出発地点を除くＮ−１個の地点を目的地点とする経路を、Ｎ個の出発地点ごとに計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算されたＮ個の出発地点からＮ個の目的地点までの経路を記憶装置に記憶する経路記憶部を備え、
前記地点指定部は、前記Ｎ個の地点以外の地点である追加地点を前記１つの出発地点として指定するとともに、前記Ｎ個の地点を前記複数の目的地点として指定し、
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第１の経路を計算するとともに、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第２の経路を計算し、
前記経路変換部は、前記経路探索部により計算された第２の経路を、前記Ｎ個の地点から前記追加地点まで逆方向に辿る第３の経路に変換し、
前記経路探索装置は、さらに、
前記経路記憶部により記憶されたＮ個の出発地点からＮ個の目的地点までの経路と前記経路探索部により計算された第１の経路と前記経路変換部により出力された第３の経路とを合わせてＮ＋１個の出発地点からＮ＋１個の目的地点までの経路を出力装置により出力する経路出力部を備えることを特徴とする請求項１から６までのいずれかに記載の経路探索装置。
【請求項８】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記属性データ変換部は、前記第２の地図データ記憶部により記憶された地図データに含まれる属性データが、前記地点指定部により指定された地点が接する道路が前記地点指定部により指定された地点が接する車線の進行方向と逆方向への一方通行であることを示すように、当該属性データを処理装置により変換し、変換した属性データを含む地図データを前記第２の地図データ記憶部に記憶させることを特徴とする請求項１から６までのいずれかに記載の経路探索装置。
【請求項９】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点までの経路を計算し、
前記経路変換部は、前記経路探索部により計算された経路を、前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された地点又は当該地点が接する道路を繋ぐ地点まで逆方向に辿る経路に変換することを特徴とする請求項１から６までのいずれかに記載の経路探索装置。
【請求項１０】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項１１】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記第１の地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項１】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする経路探索装置。
【請求項２】
前記属性データは、前記属性として各道路の一方の地点から他方の地点への進行可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記属性データは、前記属性として各道路の進行方向ごとのコストを示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、１つの出発地点から複数の目的地点までのコストの総和が最小となる経路を計算することを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記コストは、各道路の進行方向ごとの所要時間と距離と設定速度と車線数との少なくともいずれかから求められる係数であることを特徴とする請求項３に記載の経路探索装置。
【請求項５】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索部を備える経路探索装置において、
前記地図データを記憶装置に記憶する第１の地図データ記憶部と、
前記第１の地図データ記憶部により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換部と、
前記属性データ変換部により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶部と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定部とを備え、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点から前記地点指定部により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換部を備えることを特徴とする経路探索装置。
【請求項６】
前記属性データは、前記属性として各２つの道路を繋ぐ地点の一方の道路から他方の道路への進入出可否を示し、
前記経路探索部は、前記地図データに含まれる属性データに基づき、通行できない経路を除外して１つの出発地点から複数の目的地点までの経路を計算することを特徴とする請求項５に記載の経路探索装置。
【請求項７】
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、Ｎ個（Ｎは２以上の整数）の地点をそれぞれ出発地点とし、当該Ｎ個の地点のうち出発地点を除くＮ−１個の地点を目的地点とする経路を、Ｎ個の出発地点ごとに計算し、
前記経路探索装置は、さらに、
前記経路探索部により計算されたＮ個の出発地点からＮ個の目的地点までの経路を記憶装置に記憶する経路記憶部を備え、
前記地点指定部は、前記Ｎ個の地点以外の地点である追加地点を前記１つの出発地点として指定するとともに、前記Ｎ個の地点を前記複数の目的地点として指定し、
前記経路探索部は、前記第１の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第１の経路を計算するとともに、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された追加地点から前記地点指定部により指定されたＮ個の地点までの第２の経路を計算し、
前記経路変換部は、前記経路探索部により計算された第２の経路を、前記Ｎ個の地点から前記追加地点まで逆方向に辿る第３の経路に変換し、
前記経路探索装置は、さらに、
前記経路記憶部により記憶されたＮ個の出発地点からＮ個の目的地点までの経路と前記経路探索部により計算された第１の経路と前記経路変換部により出力された第３の経路とを合わせてＮ＋１個の出発地点からＮ＋１個の目的地点までの経路を出力装置により出力する経路出力部を備えることを特徴とする請求項１から６までのいずれかに記載の経路探索装置。
【請求項８】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記属性データ変換部は、前記第２の地図データ記憶部により記憶された地図データに含まれる属性データが、前記地点指定部により指定された地点が接する道路が前記地点指定部により指定された地点が接する車線の進行方向と逆方向への一方通行であることを示すように、当該属性データを処理装置により変換し、変換した属性データを含む地図データを前記第２の地図データ記憶部に記憶させることを特徴とする請求項１から６までのいずれかに記載の経路探索装置。
【請求項９】
前記地点指定部は、前記リンクデータが示す道路であって複数車線の道路に接する地点を前記一の地点と前記他の複数の地点との少なくともいずれかとして指定し、
前記経路探索部は、前記第２の地図データ記憶部により記憶された地図データに基づき、前記地点指定部により指定された一の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点までの経路を計算し、
前記経路変換部は、前記経路探索部により計算された経路を、前記地点指定部により指定された他の複数の地点又は当該地点が接する道路を繋ぐ地点から前記地点指定部により指定された地点又は当該地点が接する道路を繋ぐ地点まで逆方向に辿る経路に変換することを特徴とする請求項１から６までのいずれかに記載の経路探索装置。
【請求項１０】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各道路の進行方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各道路の進行方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項１１】
複数の地点を示すノードデータと前記ノードデータが示す各２つの地点を結ぶ道路を示すリンクデータと前記リンクデータが示す各２つの道路を繋ぐ地点の進入出方向ごとの属性を示す属性データとを含む地図データに基づき、１つの出発地点から複数の目的地点までの経路を計算する経路探索処理をコンピュータに実行させる経路探索プログラムにおいて、
前記地図データを記憶装置に記憶する第１の地図データ記憶処理と、
前記第１の地図データ記憶処理により記憶された地図データに含まれる属性データを、当該属性データが示す各地点の進入出方向ごとの属性をそれぞれ逆方向の属性として示す属性データに処理装置により変換する属性データ変換処理と、
前記属性データ変換処理により変換された属性データを含む地図データを記憶装置に記憶する第２の地図データ記憶処理と、
目的地点となる一の地点を前記１つの出発地点として指定するととともに、出発地点となる他の複数の地点を前記複数の目的地点として指定する地点指定処理とをコンピュータに実行させ、
前記経路探索処理は、前記第２の地図データ記憶処理により記憶された地図データに基づき、前記地点指定処理により指定された一の地点から前記地点指定処理により指定された他の複数の地点までの経路を処理装置により計算し、
前記経路探索プログラムは、さらに、
前記経路探索処理により計算された経路を、前記他の複数の地点から前記一の地点まで逆方向に辿る経路に処理装置により変換し、変換した経路を複数の出発地点から１つの目的地点までの経路として出力する経路変換処理をコンピュータに実行させることを特徴とする経路探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００７−２６３７８５（Ｐ２００７−２６３７８５Ａ）
【公開日】平成１９年１０月１１日（２００７．１０．１１）
【国際特許分類】
【出願番号】特願２００６−８９９６９（Ｐ２００６−８９９６９）
【出願日】平成１８年３月２９日（２００６．３．２９）
【出願人】（３９４０１３００２）三菱電機インフォメーションシステムズ株式会社 (251)
【Ｆターム（参考）】
【公開日】平成１９年１０月１１日（２００７．１０．１１）
【国際特許分類】
【出願日】平成１８年３月２９日（２００６．３．２９）
【出願人】（３９４０１３００２）三菱電機インフォメーションシステムズ株式会社 (251)
【Ｆターム（参考）】
[ Back to top ]