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

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

国内特許コード P07A010503
整理番号 P03-37
掲載日 2007年9月14日
出願番号 特願2003-403344
公開番号 特開2005-164384
登録番号 特許第4292062号
出願日 平成15年12月2日(2003.12.2)
公開日 平成17年6月23日(2005.6.23)
登録日 平成21年4月10日(2009.4.10)
発明者
  • 柴田 直樹
  • 丸山 敦史
  • 村田 佳洋
  • 安本 慶一
  • 伊藤 実
出願人
  • 学校法人奈良先端科学技術大学院大学
発明の名称 経路探索システム、サーバ、携帯端末、経路探索装置、経路探索プログラム
発明の概要

【課題】 時間的制約を満たし、かつ、ユーザの移動距離を最短とする最適経路を探索する。
【解決手段】 ユーザにより入力された複数の目的地点の任意の2地点間の最短経路をA*アルゴリズムを用いて探索する2地点経路探索部212と、目的地点を訪問順に並べたものを1つの個体として初期個体群を生成する初期個体群生成部213aと、個体に含まれる各目的地点を訪問順に並べ1つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出部213cと、時間的制約が満たされた目的地点を含む個体に対し所定のポイントを付与する評価部213dと、初期個体群に対し遺伝的アルゴリズムを繰り返し適用し最適経路を探索する個体群生成部213bとを備える。
【選択図】 図3

従来技術、競合技術の概要


近年、PDAなどの携帯端末の高性能化、GPSユニットの小型化等に伴って、GPS機能付の携帯端末を利用したパーソナルナビゲーションシステムが提案されている。カーナビゲーションシステムは、自動車に搭載される車載端末であり、自動車の道路上での移動に特化したものであるが、パーソナルナビゲーションシステムは、移動手段に制約されないシステムである。そして、このようなパーソナルナビゲーションシステムを用いて、観光案内を行なう試みがなされている。この観光案内は、具体的には、「お昼は奈良公園で昼食を食べ、帰りは最終バスの時刻に間に合うように駅に付きたい」という時間的制約の中で、希望する観光名所をできるだけ多く訪問できるというような最適な経路を探索するものである。



一方、複数の目的地点を効率よく訪問できる経路を探索する技術として、遺伝的アルゴリズムを用いるものが知られている(非特許文献1及び2)。

【非特許文献1】狩野:遺伝的アルゴリズムを用いたカーナビのための経路案内方式.情報処理学会研究報告vol.2002,No.21,pp51-58(2002)

【非特許文献2】稲垣,長谷川,北嶋:遺伝的アルゴリズムを用いた複数経由点を伴う経路探索法,電子情報通信学会論文誌D1,vol.J83-D-1,No5,pp504-507(2000)

産業上の利用分野


本発明は、複数の目的地点を効率よく訪問する経路を探索する技術に関する。

特許請求の範囲 【請求項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つの経路を作成し、各個体に含まれる各目的地点の到着予定時刻及び出発予定時刻を算出する予定時刻算出手段と、
ある個体において、時間的制約が課された目的地点の到着予定時刻及び出発予定時刻が、当該時間的制約に対して所定の許容範囲内にある場合、当該個体に所定のポイントを付与することで各個体を評価する評価手段と、
前記初期個体群に対し所定のアルゴリズムを適用し、前記ポイントの高い個体群を生成する個体生成手段と、
前記個体生成手段によって得られた個体群から、前記ポイントの高い順に抽出した所定個数の個体に対応する経路を最適経路として出力するとともに、抽出した最適経路に含まれる各目的地点に対する到着予定時刻及び出発予定時刻を出力する出力手段としてコンピュータを機能させることを特徴とする経路探索プログラム。
産業区分
  • 測定
  • 運動娯楽用
  • その他通信
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2003403344thum.jpg
出願権利状態 権利存続中
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記「問合せ先」までお問い合わせください。


PAGE TOP

close
close
close
close
close
close
close