Pat

J-GLOBAL ID：200903078502589096

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

Inventor： 柴田 直樹 ,  丸山 敦史 ,  村田 佳洋 ,  安本 慶一 ,  伊藤 実
Applicant, Patent owner： 国立大学法人 奈良先端科学技術大学院大学
Agent (4)： 小谷 悦司 ,  伊藤 孝夫 ,  樋口 次郎 ,  大月 伸介
Gazette classification：公開公報
Application number (International application number)：2003403344
Publication number (International publication number)：2005164384
Application date： Dec. 02, 2003
Publication date： Jun. 23, 2005
Summary：

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

Claim (excerpt)：

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

IPC (5)：

G01C21/00 ,  G08G1/005 ,  G08G1/137 ,  G09B29/00 ,  G09B29/10

FI (6)：

G01C21/00 Z ,  G01C21/00 G ,  G08G1/005 ,  G08G1/137 ,  G09B29/00 A ,  G09B29/10 A

F-Term (29)：

2C032HB06 ,  2C032HB22 ,  2C032HB25 ,  2C032HC08 ,  2C032HC11 ,  2C032HC13 ,  2C032HC27 ,  2C032HD04 ,  2C032HD21 ,  2F029AA02 ,  2F029AA07 ,  2F029AB07 ,  2F029AB13 ,  2F029AC02 ,  2F029AC06 ,  2F029AC09 ,  2F029AC14 ,  2F029AC16 ,  5H180AA01 ,  5H180AA21 ,  5H180BB04 ,  5H180BB05 ,  5H180EE02 ,  5H180FF01 ,  5H180FF05 ,  5H180FF13 ,  5H180FF22 ,  5H180FF27 ,  5H180FF33

Patent cited by the Patent：

Cited by examiner (2)

• 最適経路及び最適巡回経路探索方法
  Gazette classification：公開公報   Application number：特願平11-153568   Applicant：長谷山美紀, アルパイン株式会社
• 車載用ナビゲーション装置
  Gazette classification：公開公報   Application number：特願平11-156468   Applicant：株式会社デンソー