JP2014209111A5 - - Google Patents

Claims (7)

1. ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索装置であって、
   経路を構成するノードおよびリンクを特定するデータと、各リンクが通過される際に必要とされる時間に関連付けられたリンクコストを特定するデータと、を記憶する経路情報記憶部と、
   第１の出発地点と前記第１の出発地点を出発する第１の出発時刻とを特定する第１の出発条件と、第２の出発地点と前記第２の出発地点を出発する第２の出発時刻とを特定する第２の出発条件と、到着地点と前記到着地点に到着する到着時刻とを特定する到着条件と、を取得する条件取得部と、
   前記第１の出発地点から前記到着地点までの経路の内、各リンクのリンクコストの累計値が前記到着時刻から前記第１の出発時刻までの時間の差に基づいて算出される値である第１の許容タイム以下である少なくとも１つの経路を第１の許容経路として探索すると共に、前記第２の出発地点から前記到着地点までの経路の内、各リンクのリンクコストの累計値が前記到着時刻から前記第２の出発時刻までの時間の差に基づいて算出される値である第２の許容タイム以下である少なくとも１つの経路を第２の許容経路として探索する許容経路探索部と、
   前記第１の許容経路と前記第２の許容経路とが重複する部分である重複部分の内の特定の重複部分を含む前記第１の許容経路を前記第１の出発条件における前記到着地点までの第１の候補経路として抽出すると共に、前記特定の重複部分を含む前記第２の許容経路を前記第２の出発条件における前記到着地点までの第２の候補経路として抽出する候補経路抽出部と、を備える、経路探索装置。
2. 請求項１に記載の経路探索装置であって、
   前記候補経路抽出部は、前記特定の重複部分における任意のノードまたはリンクにおける任意の位置を待ち合わせ場所として決定し、
   前記経路探索装置は、さらに、
   前記第１の候補経路において前記待ち合わせ場所に到着する第１の待ち合わせ時刻と、前記第２の候補経路において前記待ち合わせ場所に到着する第２の待ち合わせ時刻と、を推定する時刻推定部を備え、
   前記候補経路抽出部は、前記待ち合わせ場所として、前記第１の待ち合わせ時刻と前記第２の待ち合わせ時刻とにおける時間の差が最小となる任意の位置を抽出する、経路探索装置。
3. 請求項１または請求項２に記載の経路探索装置であって、
   前記第１の出発条件は、経路を移動する手段である第１の移動手段を特定し、
   前記第２の出発条件は、経路を移動する手段である第２の移動手段を特定し、
   前記許容経路探索部は、前記第１の移動手段に基づいて前記経路情報記憶部に記憶された各リンクのリンクコストを選択した後に、選択されたリンクコストに基づいて前記第１の許容経路を探索すると共に、前記第２の移動手段に基づいて前記経路情報記憶部に記憶された各リンクのリンクコストを選択した後に、選択されたリンクコストに基づいて前記第２の許容経路を探索する、経路探索装置。
4. 請求項１から請求項３までのいずれか一項に記載の経路探索装置であって、さらに、
   任意のノードとリンクにおける任意の位置との少なくとも一方に関連付けられた目印を特定する目印情報を記憶する目印情報記憶部を備え、
   前記候補経路抽出部は、前記重複部分であると共に、前記目印に関連付けられた任意のノードまたはリンクにおける任意の位置を待ち合わせ場所として決定し、
   前記第１および第２の候補経路は、前記待ち合わせ場所を経由する経路である、経路探索装置。
5. ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索装置であって、
   経路を構成するノードおよびリンクを特定するデータと、各リンクが通過される際に必要とされる時間に関連付けられたリンクコストを特定するデータと、を記憶する経路情報記憶部と、
   第３の出発地点と前記第３の出発地点とを出発する第３の出発時刻とを特定する第３の出発条件と、第４の出発地点と前記第４の出発地点とを出発する第４の出発時刻とを特定する第４の出発条件と、第１の到着地点と前記第１の到着地点に到着する第１の到着時刻を特定する第１の到着条件と、第２の到着地点と前記第２の到着地点に到着する第２の到着時刻を特定する第２の到着条件と、を取得する条件取得部と、
   前記第３の出発地点から前記第１の到着地点までの経路の内、各リンクのリンクコストの累計値が前記第１の到着時刻から前記第３の出発時刻までの時間の差に基づいて算出される値である第３の許容タイム以下である少なくとも１つの経路を第３の許容経路として探索すると共に、前記第４の出発地点から前記第２の到着地点までの経路の内、各リンクのリンクコストの累計値が前記第２の到着時刻から前記第４の出発時刻までの時間の差に基づいて算出される値である第４の許容タイム以下である少なくとも１つの経路を第４の許容経路として探索する許容経路探索部と、
   前記第３の許容経路と前記第４の許容経路とが重複する部分である重複部分の内の特定の重複部分を含む前記第３の許容経路を前記第３の出発条件と前記第１の到着条件との第１の条件組み合わせにおける前記第１の到着地点までの第３の候補経路として抽出すると共に、前記特定の重複部分を含む前記第４の許容経路を前記第４の出発条件と前記第２の到着条件との第２の条件組み合わせにおける前記第２の到着地点までの第４の候補経路として抽出する候補経路抽出部と、を備え、
   前記第３の出発地点および前記第１の到着地点との組み合わせと、前記第４の出発地点と前記第２の到着地点との組み合わせと、は異なる、経路探索装置。
6. 請求項５に記載の経路探索装置であって、
   前記第１の条件組み合わせは、経路を移動する手段である第３の移動手段を特定し、
   前記第２の条件組み合わせは、経路を移動する手段である第４の移動手段を特定し、
   前記許容経路探索部は、前記第３の移動手段に基づいて前記経路情報記憶部に記憶された各リンクのリンクコストを選択した後に、選択されたリンクコストに基づいて前記第３の許容経路を探索すると共に、前記第４の移動手段に基づいて前記経路情報記憶部に記憶された各リンクのリンクコストを選択した後に、選択されたリンクコストに基づいて前記第４の許容経路を探索する、経路探索装置。
7. 請求項５または請求項６に記載の経路探索装置であって、さらに、
   任意のノードとリンクにおける任意の位置との少なくとも一方に関連付けられた目印を特定する目印情報を記憶する目印情報記憶部を備え、
   前記候補経路抽出部は、前記重複部分であると共に、前記目印に関連付けられた任意のノードまたはリンクにおける任意の位置を解散場所として決定し、
   前記第３および第４の候補経路は、前記解散場所を経由する経路である、経路探索装置。