Top > Search of Japanese Patents > SYSTEM FOR SEARCHING ROUTE, SERVER, PORTABLE TERMINAL, DEVICE FOR SEARCHING ROUTE, PROGRAM FOR SEARCHING ROUTE

SYSTEM FOR SEARCHING ROUTE, SERVER, PORTABLE TERMINAL, DEVICE FOR SEARCHING ROUTE, PROGRAM FOR SEARCHING ROUTE

Patent code P07A010503
File No. P03-37
Posted date Sep 14, 2007
Application number P2003-403344
Publication number P2005-164384A
Patent number P4292062
Date of filing Dec 2, 2003
Date of publication of application Jun 23, 2005
Date of registration Apr 10, 2009
Inventor
  • (In Japanese)柴田 直樹
  • (In Japanese)丸山 敦史
  • (In Japanese)村田 佳洋
  • (In Japanese)安本 慶一
  • (In Japanese)伊藤 実
Applicant
  • (In Japanese)国立大学法人 奈良先端科学技術大学院大学
Title SYSTEM FOR SEARCHING ROUTE, SERVER, PORTABLE TERMINAL, DEVICE FOR SEARCHING ROUTE, PROGRAM FOR SEARCHING ROUTE
Abstract PROBLEM TO BE SOLVED: To search an optimal route satisfying temporal restriction and making a user's the movement distance shortest.
SOLUTION: This system comprises: a two points route searching part 212 searching the shortest route between arbitrary two points of a plurality of destination points inputted by the user using A* algorithm; an initial individual group generation part 213a generating an initial individual group as one individual obtained by arranging the destination points based on the order of visits; a scheduled time calculation part 213c for producing one route by arranging the destination points contained in the individual based on the order of visits to calculate the scheduled arrival time and scheduled departure time of each destination point contained in each individual; an evaluation part of 213d for giving a predetermined point to the individual including the destination point where the temporal restriction is satisfied; and an individual group generation part 213b for repeatedly applying genetic algorithm to the initial individual group to search the optimal route.
Outline of related art and contending technology (In Japanese)


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



一方、複数の目的地点を効率よく訪問できる経路を探索する技術として、遺伝的アルゴリズムを用いるものが知られている(非特許文献1及び2)。
【非特許文献1】
狩野:遺伝的アルゴリズムを用いたカーナビのための経路案内方式.情報処理学会研究報告vol.2002,No.21,pp51-58(2002)
【非特許文献2】
稲垣,長谷川,北嶋:遺伝的アルゴリズムを用いた複数経由点を伴う経路探索法,電子情報通信学会論文誌D1,vol.J83-D-1,No5,pp504-507(2000)

Field of industrial application (In Japanese)


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

Scope of claims (In Japanese)
【請求項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(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2003403344thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close