| 特許：最適ルート探索エンジンeREXの基本アイディア |
1. はじめに |
| 本特許は、最適ルート探索エンジンeREX の基本アイディアに該当します。本特許にはeREXの複雑な技術が数多く含まれていますが、その中の一部を紹介します。 |
| 2. 問題点 |
| 現在の最適ルート探索におけるリンク上制御点 の指定は極めて限定的、厳密であり、逆に言うと融通がききません。例えば下図において、最近隣の道路が一方通行であるばかりに、求まるルートが一旦先のUターン路、 又はインターチェンジまで行ってから逆走することになります。 |
 |
| またこの結果、下図に示す通り、出発地と目的地を反転させた場合に求まるルートが必ずしも対称にならないと言う問題も発生します。 これらの事象の原因は、リンク上制御点として最近隣の１点のみを用いてルート探索を行なっているためです。 |
 |
| 3. 弊社の発明 |
| そこで、弊社では余計な迂回をせず、対称性を保った最適ルートを求める方法を発明しました。具体的な方法を以下に示します。 |
| 指示制御点を元にして、距離的に近い順に、複数のリンク上制御点を求める。 |
 |
|
どの位まで離れたリンク上制御点を求めるかはRankDistanceパラメータにより制御する。 例えばRankDistanceが1の場合は、S1とG1がリンク上制御点となり、RankDistanceが2の場合は、S1、S2とG1、G2がリンク制御点となる。 |
※マウスを画像に重ねるとRankDistanceが変わります |
| 出発側のリンク上制御点と目的地側のリンク上制御点の組み合わせに対して、最適ルート探索を行う。 |
| ルート探索の結果から最小コストのルート（１本のみ）を抽出する。例えば下図では、S1、S2とG1、G2の組み合わせで合計2×2=4本最適ルートから、 一番最適なルート１本を抽出して答えをする（図の例ではルートS2⇒G2が選択される。） |
|
S1 ⇒ G1 |
 |
S1 ⇒ G2 |
 |
S2 ⇒ G1 |
 |
S2 ⇒ G2 |
| この方法によって余計な迂回をせず、対称性を保った最適ルートを求めることが可能になります。 |
| ※本特許は、出願番号２００２年特許願第２６６１４１号として現在出願中です。 |
