TOP > 国内特許検索 > 経路探索システム、サーバ、携帯端末、経路探索装置、経路探索プログラム > 明細書

明細書 :経路探索システム、サーバ、携帯端末、経路探索装置、経路探索プログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4292062号 (P4292062)
公開番号 特開2005-164384 (P2005-164384A)
登録日 平成21年4月10日(2009.4.10)
発行日 平成21年7月8日(2009.7.8)
公開日 平成17年6月23日(2005.6.23)
発明の名称または考案の名称 経路探索システム、サーバ、携帯端末、経路探索装置、経路探索プログラム
国際特許分類 G01C  21/00        (2006.01)
G08G   1/005       (2006.01)
G08G   1/137       (2006.01)
G09B  29/00        (2006.01)
G09B  29/10        (2006.01)
FI G01C 21/00 Z
G01C 21/00 G
G08G 1/005
G08G 1/137
G09B 29/00 A
G09B 29/10 A
請求項の数または発明の数 16
全頁数 25
出願番号 特願2003-403344 (P2003-403344)
出願日 平成15年12月2日(2003.12.2)
新規性喪失の例外の表示 特許法第30条第1項適用 2003年6月4日社団法人情報処理学会発行の「マルチメディア,分散,協調とモバイル(DICOMO 2003)シンポジウム論文集」に発表
審査請求日 平成18年11月30日(2006.11.30)
特許権者または実用新案権者 【識別番号】504143441
【氏名又は名称】国立大学法人 奈良先端科学技術大学院大学
発明者または考案者 【氏名】柴田 直樹
【氏名】丸山 敦史
【氏名】村田 佳洋
【氏名】安本 慶一
【氏名】伊藤 実
個別代理人の代理人 【識別番号】100067828、【弁理士】、【氏名又は名称】小谷 悦司
【識別番号】100096150、【弁理士】、【氏名又は名称】伊藤 孝夫
【識別番号】100099955、【弁理士】、【氏名又は名称】樋口 次郎
【識別番号】100109438、【弁理士】、【氏名又は名称】大月 伸介
審査官 【審査官】竹下 晋司
参考文献・文献 特開2000-172664(JP,A)
特開2000-346667(JP,A)
調査した分野 G01C 21/00 - 25/00
G08G 1/00 - 99/00
G09B 29/00 - 29/14
特許請求の範囲 【請求項1】
ユーザによって携帯される携帯端末と、当該携帯装置と通信可能に接続されたサーバとを備え、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを用いて出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索システムであって、
前記携帯端末は、
現在位置を取得する現在位置取得手段と、
複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、
前記現在位置、入力された複数の目的地点及び前記時間的制約を前記サーバに送信する通信手段とを備え、
前記サーバは、
前記地図データを記憶する地図データ記憶手段と、
入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、
目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、
前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、
ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加えることで各個体を評価する評価手段と、
前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体群生成手段と、
前記個体群生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を前記携帯端末に送信する通信手段とを備え、
前記携帯端末は、前記サーバから出力された最適経路及び各目的地点の到着予定時刻及び出発予定時刻を提示する提示手段を備えることを特徴とする経路探索システム。
【請求項2】
複数の観光地点を予め記憶する観光地点記憶手段と、
前記観光地点の任意の2地点間の経路を予め記憶する経路記憶手段とをさらに備え、
前記2地点経路探索手段は、目的地点の任意の2地点が前記観光地点記憶手段に記憶されている場合、当該任意の2地点間の最短経路を前記経路記憶手段を参照することで探索することを特徴とする請求項1記載の経路探索システム。
【請求項3】
前記初期個体群生成手段は、前記観光地点記憶手段に記憶された観光地点と、前記入力受け付け手段によって受け付けられた複数の目的地点とから前記初期個体群を生成することを特徴とする請求項2記載の経路探索システム。
【請求項4】
前記個体群生成手段は、ある個体において、時間的制約が課された目的地点での到着予定時刻が、当該目的地点に対して設定された希望到着時刻よりも規定値以上早い時刻である場合、前記観光地点記憶手段から1又は複数の観光地点を読み出し当該個体に追加することを特徴とする請求項2又は3記載の経路探索システム。
【請求項5】
前記入力受付手段は、入力された複数の目的地点のうち、少なくとも1つの目的地点に対し、ユーザの訪問希望の程度を示す希望度の入力を受け付け、
前記評価手段は、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、前記希望度に応じたポイントを当該個体に加えることを特徴とする請求項1~4のいずれかに記載の経路探索システム。
【請求項6】
前記評価手段は、ある個体において、当該個体に含まれる隣接する目的地点間の最短経路距離が小さいほど、当該個体に大きなポイントをさらに付与することを特徴とする請求項1~5のいずれかに記載の経路探索システム。
【請求項7】
前記評価手段は、ある個体において、当該個体に含まれる隣接する目的地点間の移動時間が短いほど、当該個体に大きなポイントをさらに付与することを特徴とする請求項1~6のいずれかに記載の経路探索システム。
【請求項8】
探索した最適経路に沿ってユーザが移動しているか否かを判定する判定手段と、
前記判定手段により、ユーザが最適経路に沿って移動していないと判定された場合、判定時におけるユーザの現在位置を前記現在位置特定手段によって特定し、前記最適経路を再び探索する再探索手段とをさらに備えることを特徴とする請求項1~7のいずれかに記載の経路探索システム。
【請求項9】
前記2地点経路探索手段は、A*アルゴリズムを用いて経路を探索することを特徴とする請求項1~8のいずれかに記載の経路探索システム。
【請求項10】
前記個体生成手段は、遺伝的アルゴリズムを繰り返し適用し、前記ポイントの高い個体群を得ることを特徴とする請求項1~8のいずれかに記載の経路探索システム。
【請求項11】
前記個体生成手段は、一対の個体を交差させることにより、同一の目的地点を複数含む個体を生成した場合、当該目的地点のうち、1つの目的地点のみを残すことを特徴とする請求項10載の経路探索システム。
【請求項12】
現在位置を取得する現在位置取得手段と、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、前記自己の現在位置、入力された複数の目的地点及び前記時間的制約を前記サーバに送信する通信手段とを備える携帯端末から出力された情報を基に、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを用いて出発地点からユーザが訪問を希望する目的地点までの経路を探索するサーバであって、
前記地図データを記憶する地図データ記憶手段と、
入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、
目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、
前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、
ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価手段と、
前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体群生成手段と、
前記個体群生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を前記携帯端末に出力する通信手段とを備えることを特徴とするサーバ。
【請求項13】
前記地図データを記憶する地図データ記憶手段と、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価手段と、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体群生成手段と、前記個体群生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を前記携帯端末に送信する通信手段とを備えるサーバと通信可能に接続された携帯端末であって、
携帯端末の現在位置を取得する現在位置取得手段と、
複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、
前記自己の現在位置、入力された複数の目的地点及び前記時間的制約を前記サーバに送信する通信手段と、
前記サーバから送信された最適経路及び各目的地点の到着予定時刻及び出発予定時刻をユーザに提示する提示手段とを備えることを特徴とする携帯端末。
【請求項14】
現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを記憶する地図データ記憶手段を備え、当該地図データを基に、出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索装置であって、
出発地点、出発時刻、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、
入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、
目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、
前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、
ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価手段と、
前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成手段と、
前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を提示する提示手段とを備えることを特徴とする経路探索装置。
【請求項15】
現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを記憶するコンピュータにより、出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索方法であって、
前記コンピュータが、出発地点、出発時刻、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付ステップと、
前記コンピュータが、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索ステップと、
前記コンピュータが、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成ステップと、
前記コンピュータが、前記2地点経路探索ステップによって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出ステップと、
前記コンピュータが、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価ステップと、
前記コンピュータが、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成ステップと、
前記コンピュータが、前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を出力する出力ステップとを備えることを特徴とする経路探索方法。
【請求項16】
現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを基に、出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索プログラムであって、
前記地図データを記憶する地図データ記憶手段と、
出発地点、出発時刻、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、
入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、
目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、
前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、
ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを付与することで各個体を評価する評価手段と、
前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成手段と、
前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を出力する出力手段としてコンピュータを機能させることを特徴とする経路探索プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、複数の目的地点を効率よく訪問する経路を探索する技術に関する。
【背景技術】
【0002】
近年、PDAなどの携帯端末の高性能化、GPSユニットの小型化等に伴って、GPS機能付の携帯端末を利用したパーソナルナビゲーションシステムが提案されている。カーナビゲーションシステムは、自動車に搭載される車載端末であり、自動車の道路上での移動に特化したものであるが、パーソナルナビゲーションシステムは、移動手段に制約されないシステムである。そして、このようなパーソナルナビゲーションシステムを用いて、観光案内を行なう試みがなされている。この観光案内は、具体的には、「お昼は奈良公園で昼食を食べ、帰りは最終バスの時刻に間に合うように駅に付きたい」という時間的制約の中で、希望する観光名所をできるだけ多く訪問できるというような最適な経路を探索するものである。
【0003】
一方、複数の目的地点を効率よく訪問できる経路を探索する技術として、遺伝的アルゴリズムを用いるものが知られている(非特許文献1及び2)。

【非特許文献1】狩野:遺伝的アルゴリズムを用いたカーナビのための経路案内方式.情報処理学会研究報告vol.2002,No.21,pp51-58(2002)
【非特許文献2】稲垣,長谷川,北嶋:遺伝的アルゴリズムを用いた複数経由点を伴う経路探索法,電子情報通信学会論文誌D1,vol.J83-D-1,No5,pp504-507(2000)
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかしながら、非特許文献1及び2では、訪問を希望する複数の目的地点に対して希望到着時刻及び希望滞在時間等の時間的制約を加味した経路探索が行なわれていないため、上記のような観光案内に適用することができないという問題があった。
【0005】
本発明は、上記課題を解決するためになされたものであり、時間的制約を満たすような最適経路を探索することができる経路探索システム、サーバ、携帯端末、経路探索装置、経路探索プログラム、経路探索方法を提供することを目的とする。
【課題を解決するための手段】
【0006】
本発明にかかる経路探索システムは、ユーザによって携帯される携帯端末と、当該携帯装置と通信可能に接続されたサーバとを備え、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを用いて出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索システムであって、前記携帯端末は、現在位置を取得する現在位置取得手段と、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、前記現在位置、入力された複数の目的地点及び前記時間的制約を前記サーバに送信する通信手段とを備え、前記サーバは、前記地図データを記憶する地図データ記憶手段と、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加えることで各個体を評価する評価手段と、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体群生成手段と、前記個体群生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を前記携帯端末に送信する通信手段とを備え、前記携帯端末は、前記サーバから出力された最適経路及び各目的地点の到着予定時刻及び出発予定時刻を提示する提示手段を備えることを特徴とする(請求項1)。

【0007】
また、複数の観光地点を予め記憶する観光地点記憶手段と、前記観光地点の任意の2地点間の経路を予め記憶する経路記憶手段とをさらに備え、前記2地点経路探索手段は、目的地点の任意の2地点が前記観光地点記憶手段に記憶されている場合、当該任意の2地点間の最短経路を前記経路記憶手段を参照することで探索することが好ましい(請求項2)。

【0008】
また、前記初期個体群生成手段は、前記観光地点記憶手段に記憶された観光地点と、前記入力受け付け手段によって受け付けられた複数の目的地点とから前記初期個体群を生成することが好ましい(請求項3)。
【0009】
また、前記個体群生成手段は、ある個体において、時間的制約が課された目的地点での到着予定時刻が、当該目的地点に対して設定された希望到着時刻よりも規定値以上早い時刻である場合、前記観光地点記憶手段から1又は複数の観光地点を読み出し当該個体に追加することが好ましい(請求項4)。
【0010】
また、前記入力受付手段は、入力された複数の目的地点のうち、少なくとも1つの目的地点に対し、ユーザの訪問希望の程度を示す希望度の入力を受け付け、前記評価手段は、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、前記希望度に応じたポイントを当該個体に加えることが好ましい(請求項5)。
【0011】
また、前記評価手段は、ある個体において、当該個体に含まれる隣接する目的地点間の最短経路距離が小さいほど、当該個体に大きなポイントをさらに付与することが好ましい(請求項6)。
【0012】
また、前記評価手段は、ある個体において、当該個体に含まれる隣接する目的地点間の移動時間が短いほど、当該個体に大きなポイントをさらに付与することが好ましい(請求項7)。
【0013】
また、探索した最適経路に沿ってユーザが移動しているか否かを判定する判定手段と、前記判定手段により、ユーザが最適経路に沿って移動していないと判定された場合、判定時におけるユーザの現在位置を前記現在位置特定手段によって特定し、前記最適経路を再び探索する再探索手段とをさらに備えることが好ましい(請求項8)。
【0014】
また、前記2地点経路探索手段は、A*アルゴリズムを用いて経路を探索することが好ましい(請求項9)。
【0015】
また、前記個体生成手段は、遺伝的アルゴリズムを繰り返し適用し、前記ポイントの高い個体群を得ることが好ましい(請求項10)。

【0016】
また、前記個体生成手段は、一対の個体を交差させることにより、同一の目的地点を複数含む個体を生成した場合、当該目的地点のうち、1つの目的地点のみを残すことが好ましい(請求項11)。
【0017】
本発明にかかるサーバは、現在位置を取得する現在位置取得手段と、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、前記自己の現在位置、入力された複数の目的地点及び前記時間的制約を前記サーバに送信する通信手段とを備える携帯端末から出力された情報を基に、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを用いて出発地点からユーザが訪問を希望する目的地点までの経路を探索するサーバであって、前記地図データを記憶する地図データ記憶手段と、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価手段と、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体群生成手段と、前記個体群生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を前記携帯端末に出力する通信手段とを備えることを特徴とする(請求項12)。

【0018】
本発明にかかる携帯端末は、前記地図データを記憶する地図データ記憶手段と、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価手段と、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体群生成手段と、前記個体群生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を前記携帯端末に送信する通信手段とを備えるサーバと通信可能に接続された携帯端末であって、携帯端末の現在位置を取得する現在位置取得手段と、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、前記自己の現在位置、入力された複数の目的地点及び前記時間的制約を前記サーバに送信する通信手段と、前記サーバから送信された最適経路及び各目的地点の到着予定時刻及び出発予定時刻をユーザに提示する提示手段とを備えることを特徴とする(請求項13)。

【0019】
本発明にかかる経路探索装置は、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを記憶する地図データ記憶手段を備え、当該地図データを基に、出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索装置であって、出発地点、出発時刻、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価手段と、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成手段と、前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を提示する提示手段とを備えることを特徴とする(請求項14)。

【0020】
本発明にかかる経路探索方法は、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを記憶するコンピュータにより、出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索方法であって、前記コンピュータが、出発地点、出発時刻、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付ステップと、前記コンピュータが、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索ステップと、前記コンピュータが、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成ステップと、前記コンピュータが、前記2地点経路探索ステップによって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出ステップと、前記コンピュータが、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを加算することで各個体を評価する評価ステップと、前記コンピュータが、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成ステップと、前記コンピュータが、前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を出力する出力ステップとを備えることを特徴とする(請求項15)。

【0021】
本発明にかかる経路探索プログラムは、現実の道路上の所定の位置に対応するノードと、現実の道路に応じてノード間を接続するリンクとにより道路網が表された地図データを基に、出発地点からユーザが訪問を希望する目的地点までの経路を探索する経路探索プログラムであって、前記地図データを記憶する地図データ記憶手段と、出発地点、出発時刻、複数の目的地点の入力を受け付けるとともに、入力された複数の目的地点のうち、少なくとも1つの目的地点に対する希望到着時刻及び希望滞在時間を含む時間的制約の入力を受け付ける入力受付手段と、入力された複数の目的地点の任意の2地点間の経路を所定のアルゴリズムを用いて探索する2地点経路探索手段と、目的地点を訪問順で並べたものを1つの個体とし、当該個体を複数パターン生成し、初期個体群とする初期個体群生成手段と、前記2地点経路探索手段によって探索された経路を基に、個体に含まれる各目的地点を訪問順につなぎ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを付与することで各個体を評価する評価手段と、前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成手段と、前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を出力する出力手段としてコンピュータを機能させることを特徴とする(請求項16)。
【発明の効果】
【0022】
請求項1、12~16記載の発明によれば、出発地点及び出発時刻が取得され、訪問を希望する複数の目的地点及びいずれかの目的地点に対する到着希望時刻及び希望滞在時間を含む時間的制約の入力が受け付けられ、複数の目的地点の任意の2地点の経路が探索される。ここで、任意の2地点とは、原則として、複数の目的地点のうち、組み合わせる2地点間の全パターンのことをいう。ただし、本発明では、組み合わせうる2地点の全パターンのうち一部のパターンに対して経路を探索するものも含まれる。これにより、各目的地点間の経路が特定される。
【0023】
そして、複数の目的地点の巡回順序が例えばランダムに決定されて、目的地点を遺伝子として有する個体が複数生成され、初期個体群が生成される。生成された各個体は、各目的地点に対する到着予定時刻及び出発予定時刻が算出され、時間的制約が課された目的地点に対する到着予定時刻及び出発予定時刻が、当該時間的制約に対し所定の許容範囲内にある場合、この個体に対し所定のポイントが付与されて評価される。これにより、当該時間的制約を満たす目的地点が多い経路ほど高い評価を得ることとなる。
【0024】
初期個体群は、所定のアルゴリズムが適用され、より評価の高い個体群とされる。そして、評価の高い個体群から、評価の高い順に抽出された所定個数の個体が最適経路として出力されるとともに、最適経路に含まれる各目的地点の出発予定時刻及び到着予定時刻も併せて出力される。以上の処理により、ユーザが希望する時間的制約を満たすような最適な経路を探索することができる。ここで、所定個数としては、1個又は複数個が含まれる。
【0025】
請求項2記載の発明によれば、入力された複数の目的地点の任意の2地点間の経路が経路記憶手段に記憶されている場合、当該経路記憶手段から経路を読み出すことにより、任意の2地点間の経路が探索されるため、より高速に経路を探索することができる。特に、目的地点の数が多い場合、かかる構成は効果がある。
【0026】
請求項3記載の発明によれば、ユーザが訪問を希望する目的地点以外の本システムが推奨する観光地点を最適経路に含ませることができる。観光地点としては、寺、神社、公園、博物館、美術館、映画館、学校等のユーザが訪問を希望する可能性が高い場所を想定している。
【0027】
請求項4記載の発明によれば、ある個体において、時間的制約が課された目的地点での到着予定時刻が、希望到着時刻に対して規定値以上早い時刻である場合、すなわち時間的余裕がある場合、1又は複数の目的地点が当該個体に追加されるため、観光地点を効率よく訪問することができる観光経路をユーザに提示することができる。
【0028】
請求項5記載の発明によれば、ユーザが訪問を強く希望する目的地点を含む個体ほど高く評価されるため、希望度の高い目的地点を含むような最適経路を探索することができる。
【0029】
請求項6記載の発明によれば、隣接する目的地点間の経路の距離が小さい経路を最適経路として抽出することができる。そのため、時間的制約を満たすあまり、ユーザの移動距離が長くなるような経路が探索されることを防止することができる。
【0030】
請求項7記載の発明によれば、隣接する目的地点間の移動時間の小さい経路を最適経路として抽出することができる。そのため、時間的制約を満たすあまり、ユーザの移動時間が長くなるような経路が探索されることを防止することができる。
【0031】
請求項8記載の発明によれば、ユーザが最適経路に沿って移動していないと判定された場合、判定された場所を出発地点として再度最適経路が探索されるため、動的に最適経路を探索することができる。
【0032】
請求項9記載の発明によれば、A*アルゴリズムを用いたため、高速に2地点間の経路を探索することができる。
【0033】
請求項10記載の発明によれば、遺伝的アルゴリズムを用いたため、高速に最適経路を算出することができる。
【0034】
請求項11記載の発明によれば、同一の目的地点を複数訪問するような経路が探索されることを防止することができる。
【発明を実施するための最良の形態】
【0035】
(第1実施形態)
以下、本発明にかかる経路探索システムの第1実施形態について図面を参照して説明する。図1は、本発明の第1実施形態にかかる経路探索システムのネットワーク構成を示した図である。本経路探索システムは、ユーザによって携帯される携帯端末1と、携帯端末1と通信ネットワーク3を介して接続されたサーバ2とから構成されている。
【0036】
携帯端末1は、GPSユニットが搭載されたPDA(PersonalDigitalAssistant)又は携帯電話から構成される。本実施形態では、携帯端末1は、自転車に乗って観光を行なうユーザによって携帯されることを想定している。
【0037】
サーバ2は、通信機能を備えるコンピュータから構成される。通信ネットワーク3としては、例えばインターネットが採用される。なお、インターネットに代えて、例えば、本経路探索システムを提供するサービス会社が構築した専用の通信回線を用いても良い。
【0038】
図2は、携帯端末1の構成を示したブロック図である。携帯端末1は、種々の情報を表示する表示部11と、ユーザからの入力を受け付ける操作部12と、無線信号を出力するアンテナ13と、制御部16で処理された種々のデータを無線信号としてアンテナ13から出力させる通信部14、携帯端末1の現在位置を取得するGPSユニット15と、携帯端末1全体を制御する制御部16とを備えている。
【0039】
操作部12は、ユーザが訪問を希望する複数の目的地点と、複数の目的地点のうち、少なくとも1つの目的地点に対する時間的制約及び希望度(プリファレンス値)との入力指令を受け付ける。この場合、時間的制約としては、目的地点に対する希望到着時刻及び希望滞在時間が含まれる。また、目的地点としては、最終目的地点及び出発地点から最終目的地点に至るまでに経由する1又は複数の目的地点及び最終目的地点を含む。プリファレンス値は、ユーザが訪問を希望する程度を示す値であり、希望の度合いに応じて例えば1~5の5段階の数値(最も強く希望する目的地点に対しては5)で表される。
【0040】
表示部11は、液晶表示パネルからなり、制御部16の制御の下、目的地点及び時間的制約の入力をユーザに促す入力画面及び出発地点周辺のエリアの地図を表示する地図画面を表示する。地図画面に表示される地図は、サーバ2から送信された地図データを基に表示される。
【0041】
GPS(GlobalPositioningSystem)ユニット15は、専用のハードウェア回路からなり、地球軌道衛星上に打ち上げられた衛星からのデータを受信し、所定の演算を行い携帯端末1の現在位置(緯度及び経度)を測定する。
【0042】
制御部16は、例えば、CPU(中央処理装置)、RAM(ランダムアクセスメモリ)、ROM(リードオンリーメモリ)及び専用のハードウェア回路等から構成されている。ROMには、携帯端末1を制御するための制御プログラムが記憶されており、CPUは、この制御プログラムを実行することで、携帯端末1を制御する。
【0043】
また、制御部16は、サーバ2から送信された地図データを基に、地図画面上に地図を表示させる。さらに、制御部16は、操作部12を用いたユーザからの操作に応じて地図画面上を移動するポインタを表示部11に表示させる。そして、このポインタが地図画面上の所定の位置に置かれ、操作部12により選択指令が行なわれると、当該位置を目的地点として受け付ける。このとき、制御部16は、受け付けた目的地点の地名を、入力画面上の所定の欄に表示させてもよい。さらに、制御部16は、操作部12を用いて地名が入力されると、当該地名を目的地点として受け付ける。さらに、制御部16は、サーバ2によって探索された最適経路を通信部14を介して受信し、当該最適経路を地図画面に重ねて表示させる。さらに、制御部16は、測定した現在位置、受け付けた目的地点及び時間的制約を通信部14を介してサーバ2に送信する。
【0044】
図3は、サーバ2の構成を示したブロック図である。サーバ2は、CPU(中央処理装置)、RAM(ランダムアクセスメモリ)、ROM(リードオンリーメモリ)、ハードディスク、記録媒体駆動装置、通信ボード等から構成されている。ハードディスクには、コンピュータを経路探索システムのサーバとして機能させるプログラムが記憶されており、CPUは、当該プログラムを実行することで、コンピュータを上記サーバとして機能させる。サーバ2は、機能的には、経路探索部21、地図データ記憶部22、通信部23及び観光地点記憶部24を備えている。
【0045】
地図データ記憶部22は、CD-ROM、DVD-ROM、半導体記憶素子、ハードディスクドライブ等を用いた記憶装置によって構成され、道路交通網の地図データを記憶する。地図データとしては、交差点等の道路上の所定の地点に対応するノードと、各ノードをつなぎ道路に対応するリンクとからなる有向グラフと、地形及び地名を示すデータ等が含まれる。この場合、各ノードとリンクには、それぞれ固有の識別符号が割り当てられている。有向グラフGは、G=(V,E)で表される。ただし、Vは、ノードの集合を示し、Eはリンクの集合を示している。また、各リンクEの距離Rは、距離関数Cを用いて求められる(C:E→R)。
【0046】
また、目的地点の集合をD={d,d,・・・,d}と表す。nは目的地点の数を示す。各目的地点dは、d={v,st,et,dur,pref}のデータからなる。ここで、v∈Vであり、st,etはそれぞれ希望到着時刻に対する許容範囲の開始時刻及び終了時刻を示している。durは希望滞在時間、prefは後述するプレファレンス値を示している。
【0047】
通信部23は、通信ネットワーク3に対し種々のデータを送受信する。
【0048】
観光地点記憶部24は、寺院や、公園、観光名所等、ユーザが目的地点として入力する傾向が高いと想定される複数の観光地点の名称及び位置データを対応付けて記憶している。
【0049】
2地点経路記憶部27は、観光地点記憶部24によって記憶されている複数の観光地点の任意の2地点の最短経路を予め記憶している。
【0050】
経路探索部21は、CPUから構成され、入力受付部211、2地点経路探索部212、遺伝的アルゴリズム実行部213及び出力部214を備えている。
【0051】
入力受付部211は、携帯端末1から出力された、現在位置、目的地点、時間的制約及びプレファレンス値を通信部23を介して受け付け、時間的制約として入力された希望到着時刻に対し、予め定められた規定値を差し引いた値をstとして設定し、希望到着時刻に対し、予め定められた規定値を加えた値をetとして設定する。また、入力受付部211は、時間制約が課された目的地点に対しては、当該目的地点のprefに、ユーザによって入力されたプレファレンス値を設定する。
【0052】
なお、etは、上記の設定に代えて、ユーザに到着予定時刻の許容範囲を入力させ、許容範囲の開始時刻をstとして設定し、許容範囲の終了時刻をetとして設定してもよい。さらに、入力受付部211は、携帯端末1から送信された現在位置等のデータを受信したときの時刻をコンピュータが備える時計機能により特定し、出発時刻として設定する。なお、携帯端末1が現在位置に付随して現在位置の測定時刻を送信したときは、入力受付部211は、当該測定時刻を出発時刻として設定してもよい。
【0053】
2地点経路探索部212は、ユーザによって入力された複数の目的地点の任意の2地点間の最短経路を地図データを用いて探索する。詳細には、まず、入力された複数の目的地点が、観光地点記憶部24に記憶されている場所であるか否かを判定する。そして、観光地点記憶部24に記憶されていない目的地点から、任意に2つの目的地点を選び、選んだ目的地点間の最短経路をA*アルゴリズムにより探索する。また、観光地点記憶部24に記憶していない目的地点と、観光地点記憶部24に記憶された目的地点とからなる各ペアの最短経路をA*アルゴリズムにより探索する。さらに、ユーザによって入力された目的地点であって、観光地点記憶部24に記憶された目的地点の各ペアに対しては、2地点経路記憶部27を参照することで、当該2地点間の最短経路を探索する。
【0054】
A*アルゴリズムは、人工知能の分野で広く用いられ、ダイクストラ法に終点の情報をヒューリスティック値として用いることによって、探索効率を高めた手法である。この場合、任意の2地点間の直線距離をヒューリスティック値として用いる。
【0055】
ここで、任意の2地点とは、目的地点が例えばA,B,Cからなるとすると、{A,B},{B,C},{C,A}というように、ユーザによって入力された複数の目的地点から組み合わせることができる2地点の全パターンを指す。
【0056】
さらに、2地点経路探索部212は、探索した任意の2地点間の最短経路を構成する各リンクEに対して距離関数Cを適用し、2地点間の最短経路の距離を算出する。さらに2地点経路探索部212は、算出した2地点間の最短経路の距離を、想定されるユーザの移動速度で割ることにより、2地点間の移動時間を算出する。
【0057】
遺伝的アルゴリズム実行部213は、初期個体群生成部213a、個体群生成部213b、予定時刻算出部213c及び評価部213dを備えている。
【0058】
初期個体群生成部213aは、ユーザによって入力された複数の目的地点及び観光地点記憶部24に記憶された観光地点の中から、所定個数の場所を抽出し、これらの場所を例えばランダムに並べたものを1つの個体とし、得られた個体を複数パターン生成して初期個体群を生成する。本実施形態では、各個体を可変長リスト構造で表すものとする。これにより、個体に含まれる目的地点及び観光地点の追加及び削除を容易に行なうことができる。
【0059】
予定時刻算出部213cは、初期個体群生成部213a及び個体群生成部213bによって生成される各個体に含まれる各目的地点に対する到着予定時刻、出発予定時刻を算出する。詳細には、個体に含まれる隣接する目的地点同士を、2地点経路探索部212によって探索された最短経路でつなぎ1つの経路を作成し、出発時刻と、当該経路から特定される各目的地点間の移動時間と、希望滞在時間とから各目的地点の到着予定時刻及び出発予定時刻を算出する。
【0060】
評価部213dは、例えば式(1)を用いて各個体の評価値を算出する。
【0061】
評価値=α(プレファレンス値の合計)-β(総移動距離/訪問する目的地点数)-γ(総移動時間/訪問する目的地点数)・・・式(1)
α、β及びγは、定数である。プレファレンス値は、ユーザによって入力され、個体中に含まれる時間的制約が課された目的地点が当該時間的制約を満たす場合に、当該個体に付与される値である。ここで、時間的制約を満たす場合とは、到着予定時刻が、上記st及びetの範囲内にある場合をいう。総移動距離は、個体に対応する経路において、出発地点からゴール地点にいたるまでにユーザが移動する距離を示す。訪問する目的地点数は、個体に含まれる目的地点の数を示す。総移動時間は、個体に対応する経路において、出発地点からゴール地点にいたるまでにユーザが移動するのに要する時間を示す。したがって、第1項により時間的制約を満たす目的地点が多い個体ほど評価値は高くなり、第2項により各目的地点間の移動距離が短い個体ほど評価値は高くなり、第3項により各目的地点間移動時間が短い個体ほど評価値は高くなる。
【0062】
式(1)により、プレファレンス値のみを用いて個体を評価した場合、時間的制約を満たすことだけが最優先されて訪問順序が決定されるおそれがある。つまり、時間的制約を満たすために近い所にある目的地点を続けて回らずに、遠回りした順序を採った方がよい評価値を得られるという状況になる。こうなると、時間的制約は満たしていても、移動する距離が多い経路が探索されてしまい、効率のよい観光を行なうことができない。
【0063】
そこで、式(1)では、第1項に加えて、第2項及び第3項を追加している。これにより、時間的に余裕がでた場合、この時間を利用して、ユーザによって入力された目的地点以外の推奨観光地が追加するような経路を探索することが可能となり、効率よい観光を行なうことができる。なお、評価部213dは、式(1)において、第2項及び第3項のいずれか一方又は両方が省略された式を用いて個体の評価を行なってもよい。ここで、時間的に余裕がでた場合とは、ある目的地点において算出された到着予定時刻が、stに対し規定値以上早い時刻である場合が該当する。
【0064】
個体群生成部213bは、選択部213b1、交差部213b2及び突然変異部213b3を備え、個体群に対して、遺伝的アルゴリズムによる世代交代処理を繰り返し実行し、より評価値の高い個体からなる個体群を生成する。本実施形態では、個体群生成部213bは、処理を開始してから、予め定められた制限時間に達するまで、世代交代処理を繰り返す。
【0065】
選択部213b1は、現世代の個体群の中で最大の評価値をもつ個体をエリート個体として特定するとともに、エリート個体以外の残りの個体に対しトーナメント選択処理を施し、得られた個体及びエリート個体からなる個体群を次世代の個体群として残す。
【0066】
交差部213b2は、選択部213b1により次世代の個体として選択された個体群以外の個体から所定個数のペアの個体を親個体として選択し、選択した各ペアの各個体に対して、例えばランダムに一つの交差点を選択し、一点交差により、ペアの親個体同士の遺伝子(目的地点)の入れ替えを行い新たな個体(子個体)を生成する。この場合、交差部213b2は、子個体に、同じ目的地点が複数含まれている場合は、後の遺伝子座に位置する目的地点を削除することにより当該目的地点を1つにする。なお、交差部213b2は、一点交差に代えて、多点交差や一様交差により新たな個体を生成してもよいが、これらの交差の場合、同じ目的地点が複数含まれる個体が生成される可能性が高くなるため、一点交差を用いることが好ましい。また、親個体の選択は、例えばランダムに行なえばよい。
【0067】
突然変異部213b3は、選択部213b1によって選択された個体群以外の個体及び交差部213b2により新たに生成された個体から所定個数の個体を選択し、得られた各個体において、2-opt法を用いて目的地点を入れ替える突然変異処理を行なう。2-opt法は、同一個体上でランダムに選んだ2地点を交換する処理である。突然変異処理が施される個体の選択は、例えば、ランダムに選択すればよい。
【0068】
また、突然変異部213b3は、交差部213b2により、個体長が短くなった個体又は時間的に余裕がある個体に対し、目的地点を追加する処理を行なう。詳細には、個体長が短くなった個体からランダムに選択された所定個数の目的地点、又は、時間的に余裕がある目的地点に対し、観光地点記憶部24に記憶されている観光地点からランダムに選んだ観光地点を追加する。ランダムに選ぶ上記所定個数としては、例えば、個体長を元の個体と同一にするために、交差によって目的地点が減少した個体の目的地点減少数分の個数を設定すればよい。また、ランダムに選択された目的地点、又は、時間的に余裕がある目的地点に対し、近所の観光地点を観光地点記憶部24から読み出して追加してもよい。
【0069】
出力部214は、個体群生成部213bによって生成された評価値の高い個体群から、評価値の高い順の所定個数の個体を抽出し、抽出した個体に対応する経路と、各経路に含まれる目的地点の到着予定時刻及び出発予定時刻と、経路を含むエリアの地図データとを通信部23を介して携帯端末1に出力する。
【0070】
次に、本経路探索システムの動作について、図4に示すフローチャートを用いて説明する。ステップS11において、携帯端末1により、ユーザからの目的地点及び時間的制約の入力が受け付けられると(ステップS11でYES)、GPSユニット15により携帯端末の現在位置が測定される(ステップS12)。ステップS13において、制御部16及び通信部14により、目的地点、時間的制約、現在位置がサーバ2に出力される。
【0071】
ステップS21において、サーバ2により、目的地点、時間的制約及び現在位置が受信されると、入力受付部211により、各目的地点dを構成するデータ(v,st,et,dur,pref)が設定される(ステップS22)。
【0072】
ステップS23において、2地点経路探索部212により、複数の目的地点のうち組み合わせることができる2地点の全パターンのそれぞれに対し、2地点経路記憶部27を参照することにより、又は、A*アルゴリズムを用いて最短経路が探索される。
【0073】
ステップS24において、2地点経路探索部212により、ステップS23で探索された各最短経路についての距離が算出され、当該距離がユーザの移動速度で除算され、任意の2地点間の移動時間が算出される。
【0074】
ステップS25において、遺伝的アルゴリズム実行部213により最適経路が探索される。この処理の詳細については後述する。次いで、出力部214により、探索された最適経路、最適経路を含むエリアの地図データ及び最適経路の各目的地点の到着時刻及び出発時刻が、通信部23を介して携帯端末1に送信される(ステップS26)。
【0075】
ステップS14において、携帯端末1により、サーバ2から送信されたデータが受信されると、制御部16により、受信した最適経路がそのエリアを含む地図に重ね合わされて表示部11に表示される(ステップS15)。
【0076】
この場合、図5に示すような、最適経路が地図に重ね合わせられた画像が地図表示画面に表示される。図5の例では、各目的地点の名称及び訪問順序が地図上の対応する位置の近傍に表示されている。また、最適経路に沿ってユーザの移動方向を示す矢印が表示されている。これにより、ユーザは、どのような順序で目的地点を訪問すればよいのかを一目で知ることができる。
【0077】
さらに、表示部11の画面上の所定の欄には、図6に示すような、各目的地点に対する到着予定時刻、出発予定時刻及び滞在予定時間が示されたテーブルが表示される。これによりユーザは、探索された最適経路にしたがって、各目的地点を訪問した場合の各目的地点に対する到着予定時刻等を一目で知ることができる。
【0078】
図7は、ステップS25の最適経路を探索する処理のサブルーチンを示している。まず、ステップS31において、遺伝的アルゴリズムの実行時間を計測するためのタイマTに0がセットされ、タイマTが初期化される。ステップS32において、タイマTにより、実行時間の計測が開始される。
【0079】
ステップS33において、初期個体群生成部213aにより、ランダムにより複数パターンの個体が生成され、初期個体群が生成される。図8は、生成された初期個体群の一例を示した図である。この場合、東大寺、法隆寺、薬師寺及びNAIST(奈良先端科学技術大学院大学)が目的地点として入力されており、一段目に示した個体は、これら全ての目的地点と観光地点記憶部24に記憶された春日大社、唐招提寺及び興福寺の観光地点から生成された個体であり、2段目に示した個体は、法隆寺、東大寺及び薬師寺の目的地点と、観光地点記憶部24に記憶された春日大社、唐招提寺及び興福寺から生成された個体であり、3段目に示した個体は、薬師寺、東大寺及び法隆寺の目的地点と、観光地点記憶部24に記憶された唐招提寺及び興福寺の観光地点から生成された個体である。このように、本実施形態では、各個体が可変長リスト構造で表されているため、各個体の長さは一定ではない。
【0080】
ステップS34において、評価部213dにより、式(1)を用いて各個体の評価値が算出される。ステップS35において、選択部213b1により、現世代の個体群から評価値が最も高い個体がエリート個体として選択され、次世代の個体として保存される。ステップS36において、選択部213b1により、エリート個体以外の現世代の個体に対し、トーナメント選択処理が施され、選択された1又は複数の個体が次世代の個体として保存される。
【0081】
ステップS37において、交差部213b2により、ステップS35及びS36において次世代の個体として保存された個体以外の個体から1又は複数ペアの個体が親個体として選択され、当該親個体に対して、一点交差により新たな個体が生成される。
【0082】
図9は、一点交差の一例を示した図である。親個体1は、東大寺、法隆寺、春日大社、二月堂、西大寺、薬師寺及び新薬師寺からなる。親個体2は、唐招提寺、NAIST、正倉院、興福寺、東大寺、薬師寺及び法隆寺からなる。親個体1は、3番目の目的地点である春日大社と4番目の目的地点である二月堂との間が交差点として選択されている。親個体2は、4番目の目的地点である興福寺と、5番目の目的地点である東大寺との間が交差点として選択されている。そして、親個体1の1~3番目の目的地点に対し、親個体2の5~7番目の目的地点が追加され、親個体1に対する子個体1が生成される。この場合、子個体1は、東大寺及び法隆寺がそれぞれ2個存在するため、後に遺伝子座に位置する東大寺及び法隆寺が子個体1から削除される。その結果、子個体1は、東大寺、法隆寺、春日大社及び薬師寺の計4個の目的地点から構成され、親個体よりも個体長が短くなっている。
【0083】
また、親個体2の1~4番目の目的地点に対し、親個体1の4~7番目の目的地点が追加され、親個体2に対する子個体2が生成される。子個体2は、合計8個の目的地点から構成されており、親個体2に対し、個体長が長くなっている。
【0084】
ステップS38において、突然変異部213b3により、現世代の個体において、ステップS35及びS36で選択された個体以外の個体から所定個数の個体が選択され、当該個体に対し2-opt法による突然変異処理が施される。図10は、2-opt法による突然変異処理の一例を示した図である。東大寺、法隆寺、春日大社、唐招提寺、興福寺、薬師寺及びNAISTからなる個体に対し、1番目の目的地点である東大寺と、5番目の目的地点である興福寺とが交換され、新たな個体が生成されている。これにより、解に多様性を持たせることができる。
【0085】
ステップS39において、突然変異部213b3により、交差により個体長が短くなった個体のランダムに選ばれた遺伝子座に観光地点記憶部24に記憶された観光地点が追加される。図11は、観光地点の追加の一例を示した図である。図11では、東大寺、法隆寺、春日大社、興福寺、薬師寺及びNAISTからなる交差によって個体長が短くなった個体が示されている。この場合、春日大社(法隆寺)がランダムに選ばれた目的地点であり、春日大社の前(法隆寺の後)の遺伝子座に唐招提寺が新たに追加されている。このように、個体長が短くなり、時間的余裕が生じた個体に対し、観光地点が追加されると、当該個体は、各目的地点間の移動距離の平均が低くなる。そして、移動距離の平均が低い個体は、式(1)により高い評価が得られるため、かかる個体が次世代の個体へと残され、結果、時間的制限のみに拘束されず、効率よく観光名所を訪問することができる経路が最適経路として探索されることとなる。
【0086】
ステップS40において、タイマTの値が予め定められた探索制限時間と比較され、タイマTの値が探索制限時間未満の場合(ステップS40でYES)ステップS33に戻り、再度、遺伝的アルゴリズムが実行され、次世代の個体が生成される。一方、ステップS41において、タイマTの値が探索制限時間以上の場合(ステップS41でNO)、処理が終了される。なお、図7のフローチャートでは、タイマTが制限時間となるまで遺伝的アルゴリズムを実行するという態様を示したが、これに限定されず、例えば、個体群の評価値の平均値が、世代交代により一定の値以上上昇しないケースが所定回数連続した場合に、処理を終了させてもよい。
【0087】
図12は、本経路探索システムによって得られた最適経路の一例を示した図であり、(a)はユーザが希望する観光内容を示し、(b)はそれによって得られた最適経路を示し、(c)は得られた最適経路に対して付与されるプレファレンス値を示している。(a)に示すように、ユーザは、9時に現在位置を出発し、法隆寺、東大寺及び薬師寺を訪問し、20時にゴールである現在位置に戻る観光を希望している。そして、法隆寺に対しては、12時に到着することを希望している。また、各目的地点に対して、プレファレンス値として5が設定されている。これによって、(b)に示すように、現在位置を9時に出発し、10時に東大寺に到着し、13時に唐招提寺に到着し、16時に春日大社に到着し、17時に幸福寺に到着し、18時に薬師寺に到着し、19時にNAISTに到着し、20時に現在位置に戻る経路が最適経路として探索されている。この場合、時間制約が課された目的地点である法隆寺は、当該時間的制約が満たされているため、プレファレンス値分のポイント(=5)が付与されている。また、ゴールに対しても時間的制約が満たされているためプレファレンス値分のポイント(=5)が付与されている。したがって、当該経路に付与されるプレファレンス値の合計は10ポイントとなる。
【0088】
以上説明したように、第1実施形態の経路探索システムによれば、ユーザが希望する時間的制約を満たし、かつ、ユーザの移動距離が最短となるような最適経路を探索することができる。また、入力された目的地点の最短経路を2地点経路記憶部27を参照することで探索しているため、多数(例えば20個以上)の目的地点が設定されている場合であっても、最適経路を高速に算出することができる。さらに、式(1)に第2項及び第3項を設けたため、時間的制限に余裕がある個体に対しては、観光地点記憶部24に記憶された観光地点を追加した場合の個体に高い評価が得られ、より多くの観光地点を訪問できるような最適経路をユーザに提示することができる。
【0089】
(第2実施形態)
第1実施形態では、携帯端末1とサーバ2とで構成された経路探索システムを示したが、第2実施形態では、一台の装置からなる経路探索装置を示す。図13は、第2実施形態にかかる経路探索装置のブロック図を示している。
【0090】
経路探索装置は、通常のコンピュータから構成され、CPUがハードディスクに記憶された経路探索プログラムを実行することで、ブロック図に示す各種機能が実現される。以下の説明では、第1実施形態と同一のものは同一の符号を付し説明を省略する。操作部25は、ユーザによる出発地点、出発時刻、目的地点及び時間的制約の入力を受け付ける。第1実施形態では、GPSにより得られた現在位置を出発地点として設定していたが、第2実施形態では、ユーザによって入力された出発地点及び出発時刻を基に、最適経路を探索する。
【0091】
表示部26は、CRT(陰極線管)、液晶パネル、プラズマパネル等から構成され、第1実施形態の携帯端末1の表示部11に相当するものであり、CPUの制御の下、経路探索部21によって探索された最適経路や入力画面を表示する。
【0092】
次に、第2実施形態にかかる経路探索装置の動作について図14のフローチャートを用いて説明する。ステップS51において、ユーザによる出発地点、出発時刻、目的地点及び時間的制約が入力されると(ステップS51でYES)、入力受付部211´により、各目的地点に対するデータが設定されるとともに、出発地点、出発時刻及びプレファレンス値が設定される。
【0093】
次いで、ステップS53~S55の処理が実行され、最適経路が探索される。ステップS53~S55の処理は、それぞれ図4に示すステップS23~S25と同一の処理であるため説明を省略する。
【0094】
ステップS56において、探索された最適経路が表示部26に表示され、処理が終了される。
【0095】
以上説明したように第1及び第2実施形態にかかる経路探索システム及び経路探索装置によれば、ユーザによって入力された複数の目的地点間及び時間的制約を満たすような最適経路を探索することができる。
【0096】
本発明は、以下の態様を採用してもよい。
【0097】
(1)上記実施形態では、遺伝的アルゴリズムを用いて最適経路を探索したが、これに加えて、Multi-level Approachを用いて最適経路を探索してもよい。この手法は、問題を荒く分割した部分問題として解き、除々にもとのサイズに戻していく手法である。
【0098】
(2)上記実施形態では、2地点経路探索部212は、A*アルゴリズムを用いたが、これに限定されず、ダイクストラ法を用いても良い。ダイクストラ法は、2つの目的地点間を結ぶ経路を求める代表的な手法であり、市販されているカーナビゲーションシステムでは、この手法が広く使用されているが、A*アルゴリズムに比べ短時間で最短経路を探索することができない。そのため、探索時間の高速化という観点からは、A*アルゴリズムを用いることが好ましい。
【0099】
(3)上記実施形態では、遺伝的アルゴリズムを用いたが、これに限定されず、TSP(巡回セールスマン問題)を解決することができる他のアルゴリズムを用いても良い。
【0100】
(4)第2の実施形態では、出発地点及び出発時刻として、ユーザによって入力されたものを採用したが、これに限定されず、GPSユニットを備え、GPSにより測定された現在位置と現在位置取得時の時刻等を出発地点及び出発時刻として設定してもよい。これにより本発明を、カーナビゲーションシステムに用いることができる。
【0101】
(5)第1の実施形態では、ユーザが自転車に乗って移動する態様を示したがこれに限定されず、自転車以外の乗り物あるいは徒歩により移動する態様も含まれる。この場合、ユーザの乗り物に応じて想定される移動速度(徒歩の場合は、人間の歩く速度)を基に、移動時間を計算すればよい。
【0102】
(6)上記実施形態では、2地点経路探索部212は、任意の2地点間の最短経路を探索したが、これに限定されず、有料道路の料金等のコストが最小となる経路を探索してもよいし、道路の大きさや制限速度等を加味して移動時間が最小となる経路を探索してもよい。これにより、ユーザが望む最適経路を探索することが可能となる。
【0103】
(7)上記実施形態では、示さなかったが、システムが探索した経路に沿ってユーザが移動していない場合、再度、最適経路を再探索してユーザに提示してもよい。経路に沿って移動しているか否かの判定は、システムが探索したある目的地点における到着予定時刻を所定の閾値以上経過してもユーザが到達していない場合に、最適経路に沿って移動していないと判定し、判定した時点におけるユーザの現在位置をGPSにより取得し、出発地点として探索すればよい。この場合、サーバは、一定の期間毎にGPSによりユーザの現在位置を取得すればよい。また、最初にシステムが提示した最適経路に含まれる目的地点のうち、ユーザが訪問した目的地点をメモリに記憶しておき、ユーザが通った目的地点を除外して、再探索を行なっても良い。これにより、ユーザが一度訪問した目的地点を再度訪問するような経路をユーザに提示することを防止することができる。
【実施例】
【0104】
次に本発明にかかる経路探索システムを評価するために行なった実験を実施例として示す。本実験では、地図データとして、市販のナビ研S規格に準拠したカーナビゲーション用デジタル地図を利用した。実験環境は、CPU:AMD Duron 1.3GHz、メモリ:768Mbyte、OS:VineLinux2.6の計算機を使用した。対象とした地図データは、奈良県北部で総ノード数は約3800、目的置換の移動速度を時速30km/hとして移動時間を計算した。
【0105】
実験を行なうために、表2及び表3で示す入力を与えた。プリファレンス値は、指定した目的地を全て5とした。
【0106】
【表1】
JP0004292062B2_000002t.gif

【0107】
【表2】
JP0004292062B2_000003t.gif

【0108】
【表3】
JP0004292062B2_000004t.gif

【0109】
【表4】
JP0004292062B2_000005t.gif

【0110】
【表5】
JP0004292062B2_000006t.gif

【0111】
図5は、表1及び表2の入力に対して本アルゴリズムを適用した結果の一例である。図中の数字は巡回する順序を示し、矢印は経路の進行方向を示している。また、表3は、得られた結果の詳細である。表5は遺伝的アルゴリズムによる巡回順序決定の実行時間ごとの評価値の変化を示したものである。表3に示すように、時間制約を付けた4つの目的地点は経路に含まれており、いずれも指定した時間制約を満たしている。また、生成された経路に含まれている目的地点は8箇所であり、そのうち訪れることを希望した目的地は6箇所、システムが推奨する追加目的地は2箇所となった。
【0112】
実行時間は、表4に示すように、181秒かかった。この探索時間の大部分は、A*アルゴリズムによるすべての目的地点間の経路を求める時間であり、巡回順序決定に要した時間は30秒である。したがって、主要な目的地点間の距離を登録したデータベースを作成し、探索時にはそのデータを利用するようにすれば、実行時間は30秒で済むことになり、十分実用に耐えると考えられる。
【0113】
また、表5に示すように、評価値の値は探索時間が増えるごとに高くなっているが、30秒程度で一定の値になった。実行時間5秒では、評価値は10秒以降に比べてかなり低い値であるが、10秒以降での評価値の向上率はわずかである。したがって、実行時間が10~15秒でもそれなりによい評価値が得られると考えられる。
【図面の簡単な説明】
【0114】
【図1】本発明の第1実施形態にかかる経路探索システムのネットワーク構成を示した図である。
【図2】携帯端末の構成を示したブロック図である。
【図3】サーバの構成を示したブロック図である。
【図4】本経路探索システムの動作を示すフローチャートである。
【図5】地図に重ね合わせて表された最適経路の画像の一例を示した図である。
【図6】各目的地点に対する到着予定時刻及び出発予定時刻が示されたテーブルを示した図である。
【図7】最適経路を探索する処理のサブルーチンを示したフローチャートである。
【図8】初期個体群の一例を示した図である。
【図9】一点交差の一例を示した図である。
【図10】2-opt法による突然変異処理の一例を示した図である。
【図11】観光地点の追加の一例を示した図である。
【図12】本経路探索システムによって得られた最適経路の一例を示した図であり、(a)はユーザが希望する観光内容を示し、(b)はそれによって得られた最適経路を示し、(c)は得られた最適経路に対して付与されるプレファレンス値を示している。
【図13】第2実施形態にかかる経路探索装置を示すブロック図である。
【図14】第2実施形態にかかる経路探索装置の動作を示したフローチャートである。
【符号の説明】
【0115】
1 携帯端末
2 サーバ
3 通信ネットワーク
11 表示部
12 操作部
13 アンテナ
14 通信部
15 GPSユニット
16 制御部
21 経路探索部
22 地図データ記憶部
23 通信部
24 観光地点記憶部
25 操作部
26 表示部
211 入力受付部
212 地点経路探索部
213 遺伝的アルゴリズム実行部
213a 初期個体群生成部
213b 個体群生成部
213b1 選択部
213b2 交差部
213b3 突然変異部
213c 予定時刻算出部
213d 評価部
214 出力部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13