【手続補正書】
【提出日】平成27年12月8日(2015.12.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索装置であって、
経路を構成するノードおよびリンクを特定するデータと、各リンクの通過に要する時間を表すリンクコストを特定するデータと、を記憶する経路情報記憶部と、
ノードまたはリンクの少なくとも一方に関連付けられた施設を特定するデータと、前記施設に設定された特性を特定するデータと、を記憶する施設情報記憶部と、
第１地点と第２地点とを特定するデータを取得する地点取得部と、
前記第１地点から前記第２地点までの経路を通過するのに要する時間の上限値である移動上限時間を設定する上限時間設定部と、
前記第１地点から前記第２地点までの経路の内、前記第１地点から前記第２地点まで移動するために要する時間である移動所要時間が前記移動上限時間以下である少なくとも１つの経路を許容経路として探索する許容経路探索部と、
それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設および前記施設に設定された前記特性を、前記許容経路ごとに特定する経路別特性特定部と、を備える、経路探索装置。
【請求項２】
請求項１に記載の経路探索装置であって、
前記許容経路探索部は、前記第１地点から特定のノードまでを結ぶ複数の経路の内、各リンクのリンクコストの累計値が最小となる最小コスト経路とそれ以外の非最小コスト経路とを探索し、前記特定のノードが前記第２地点である場合の前記最小コスト経路を最適経路として設定する最適経路探索部を有し、
前記経路情報記憶部は、前記第１地点から前記第２地点までの経路に含まれる複数の特定のノードのそれぞれについて、前記第１地点から前記特定のノードまでを結ぶ複数の経路の内、前記最小コスト経路および前記非最小コスト経路のリンクコストの累計値を記憶するノード別経路記憶部を有し、
前記許容経路探索部は、前記最適経路に含まれる複数の前記特定のノードを順に最適ノードとして選択し、前記最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記移動上限時間から前記最適経路のリンクコストの累計値を差し引いた許容タイム以下になる前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記最適ノードから前記第２地点までの経路が前記最適経路と同じ経路と、を組み合わせた経路を類似経路として設定する類似経路設定部を有し、
前記最適経路探索部は、前記最小コスト経路および非最小コスト経路のリンクコストの累計値が前記最適経路のリンクコスト累計値に前記許容タイムを加算した値まで探索し、
前記許容経路は、前記最適経路および前記類似経路である、経路探索装置。
【請求項３】
請求項２に記載の経路探索装置であって、
前記類似経路設定部は、前記最適経路に含まれないと共に前記類似経路に含まれる前記特定のノードを順に準最適ノードとして選択し、前記準最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記許容タイムから前記最適経路と前記準最適ノードを含む前記類似経路とのリンクコストの累計値の差である経路別時間差以下である前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記準最適ノードから前記第２地点までの経路が前記類似経路と同じ経路と、を組み合わせた経路を準類似経路として設定し、さらに前記準類似経路を前記類似経路として設定した後に、設定された前記類似経路に含まれる前記準最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記許容タイムから前記最適経路のリンクコストの累計値と前記経路別時間差とを差し引いた値以下である前記非最小コスト経路がなくなるまで探索する、経路探索装置。
【請求項４】
請求項２または請求項３に記載の経路探索装置であって、
前記特性を特定するデータは、指標値であり、
前記経路探索装置は、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記経路別特性特定部は、それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の前記指標値を前記許容経路ごとに特定する、経路探索装置。
【請求項５】
請求項２から請求項４までのいずれか一項に記載の経路探索装置であって、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記経路別特性特定部は、同じノードにおいて、それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の組み合わせが同じであると共に、前記経路加算コストが異なる前記ラベル情報が付与されている場合には、前記経路加算コストが小さい方の前記ラベル情報のみを特定する、経路探索装置。
【請求項６】
請求項２から請求項５までのいずれか一項に記載の経路探索装置であって、
前記施設情報記憶部は、前記施設の利用に要する時間を表す施設利用時間を記憶し、
前記特性を特定するデータは、指標値であり、
前記経路探索装置は、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられていた際に、同一の前記直前ノードのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用された場合の前記ラベル情報には、前記経路加算コストの代わりに、前記経路加算コストと前記経路加算コストに利用された前記施設の前記施設利用時間とを足した時間を付与する、経路探索装置。
【請求項７】
請求項２から請求項６までのいずれか一項に記載の経路探索装置であって、
前記施設情報記憶部は、前記施設に設定された特定のイベントが開始するイベント開始時刻と前記特定のイベントが終了するイベント終了時刻とを記憶し、
前記経路探索装置は、さらに、
前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え、
前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり、
前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられている際に、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間である場合には、同一の前記直前ノードのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間でない場合には、前記施設が利用されていない場合のみのラベル情報を付与する、経路探索装置。
【請求項８】
請求項１から請求項７までのいずれか一項に記載の経路探索装置であって、
前記特性を特定するデータは、指標値であり、
前記経路探索装置は、さらに、
複数の前記施設から少なくとも１つの特定の施設を選択する特定施設選択部と、
前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設の組み合わせの中に前記特定の施設が含まれる場合には、前記特定の施設に予め設定された指標加算値を前記許容経路の前記指標値の合計に加える指標値加算部と、を備える、経路探索装置。
【請求項９】
請求項１から請求項８までのいずれか一項に記載の経路探索装置であって、
前記許容経路探索部は、前記施設がリンクにおける任意の位置に関連付けられて記憶されている場合に、前記任意の位置を新たなノードである施設ノードとして設定すると共に、前記施設ノードに隣接する２つのノードのそれぞれを第１の隣接ノードと第２の隣接ノードとして設定し、前記施設ノードと前記第１の隣接ノードとを結ぶ第１のリンクと前記施設ノードと前記第２の隣接ノードとを結ぶ第２のリンクとのそれぞれのリンクコストを、前記第１の隣接ノードと前記第２の隣接ノードとを結ぶリンクのリンクコストの長さに対して前記第１のリンクの長さと前記第２のリンクの長さとで按分したリンクコストを設定し、新たに前記許容経路を探索する、経路探索装置。
【請求項１０】
請求項１から請求項９までのいずれか一項に記載の経路探索装置であって、さらに、
ぞれぞれの前記許容経路と、前記許容経路ごとに特定された前記施設および前記施設に設定された前記特性の内の少なくとも一方と、を関連付けて表示させる表示情報を送信する表示情報送信部を備える、経路探索装置。
【請求項１１】
ネットワーク上における任意の２つの地点を結ぶ経路を探索する経路探索システムであって、
経路を構成するノードおよびリンクを特定するデータと、各リンクの通過に要する時間を表すリンクコストを特定するデータと、を記憶する経路情報記憶部と、
ノードまたはリンクの少なくとも一方に関連付けられた施設を特定するデータと、前記施設に設定された特性を特定するデータと、を記憶する施設情報記憶部と、
第１地点と第２地点とを特定するデータを設定する地点設定部と、
前記第１地点から前記第２地点までの経路を通過するのに要する時間の上限値である移動上限時間を設定する上限時間設定部と、
前記第１地点から前記第２地点までの経路の内、前記第１地点から前記第２地点まで移動するために要する時間である移動所要時間が前記移動上限時間以下である少なくとも１つの経路を許容経路として探索する許容経路探索部と、
それぞれの前記許容経路に含まれるノードおよびリンクに関連付けられた前記施設および前記施設に設定された前記特性を、前記許容経路ごとに特定する経路別特性特定部と、を備える、経路探索システム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
（２）上記形態の経路探索装置において、前記許容経路探索部は、前記第１地点から特定のノードまでを結ぶ複数の経路の内、各リンクのリンクコストの累計値が最小となる最小コスト経路とそれ以外の非最小コスト経路とを探索し、前記特定のノードが前記第２地点である場合の前記最小コスト経路を最適経路として設定する最適経路探索部を有し；前記経路情報記憶部は、前記第１地点から前記第２地点までの経路に含まれる複数の特定のノードのそれぞれについて、前記第１地点から前記特定のノードまでを結ぶ複数の経路の内、前記最小コスト経路および前記非最小コスト経路のリンクコストの累計値を記憶するノード別経路記憶部を有し；前記許容経路探索部は、前記最適経路に含まれる複数の前記特定のノードを順に最適ノードとして選択し、前記最適ノードにおける前記最小コスト経路と前記非最小コスト経路とのリンクコストの累計値の差が、前記移動上限時間から前記最適経路のリンクコストの累計値を差し引いた許容タイム以下になる前記非最小コスト経路を選択し、選択された前記非最小コスト経路と、前記最適ノードから前記第２地点までの経路が前記最適経路と同じ経路と、を組み合わせた経路を類似経路として設定する類似経路設定部を有し；前記最適経路探索部は、前記最小コスト経路および非最小コスト経路のリンクコストの累計値が前記最適経路のリンクコスト累計値に前記許容タイムを加算した値まで探索し；前記許容経路は、前記最適経路および前記類似経路であってもよい。この形態の経路探索装置によれば、許容経路として、最適経路の探索および類似経路の設定を効率的に行なうことができ、第１地点から第２地点までの経路を効率的に設定できる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
（７）上記形態の経路探索装置において、前記施設情報記憶部は、前記施設の利用に要する時間を表す施設利用時間を記憶し；前記特性を特定するデータは、指標値であり；前記経路探索装置は、さらに；前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え；前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の前記指標値の合計と、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり；前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられていた際に、同一の前記直前ノードのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用された場合の前記ラベル情報には、前記経路加算コストの代わりに、前記経路加算コストと前記経路加算コストに利用された前記施設の前記施設利用時間とを足した時間を付与してもよい。この形態の経路探索装置によれば、第１地点から第２地点までの経路の移動所要時間に、利用された施設の施設利用時間も加味されているため、実際の移動所要時間を踏まえて第２地点に到着する到着時刻を経路探索装置の利用者に提供でき、利用者の利便性が向上する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
（８）上記形態の経路探索装置において、前記施設情報記憶部は、前記施設に設定された特定のイベントが開始するイベント開始時刻と前記特定のイベントが終了するイベント終了時刻とを記憶し；前記経路探索装置は、さらに；前記許容経路に含まれる特定のノードにラベル情報を付与するラベル付与部を備え；前記ラベル情報は、前記第１地点から前記特定のノードまでの経路に関連付けられた前記施設の組み合わせと、前記第１地点から前記特定のノードまでの前記許容経路に含まれるノードのそれぞれについて、選択された経路の前記非最小コスト経路と前記最小コスト経路とのリンクコストの累計値の差を全て足した経路加算コストと、前記許容経路における前記特定のノードの１つ前のノードである直前ノードにおけるラベル情報と、を含む情報であり；前記ラベル付与部は、前記直前ノードから前記特定のノードまでを結ぶリンクである直前リンクに前記施設が関連付けられている際に、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間である場合には、同一の前記直前ノードのラベル情報から前記直前リンクに関連付けられた前記施設が利用された場合の前記ラベル情報と利用されていない場合のラベル情報との２種類のラベル情報を付与し、前記施設が利用される時刻が前記イベント開始時刻から前記イベント終了時刻の間でない場合には、前記施設が利用されていない場合のみのラベル情報を付与してもよい。この形態の経路探索装置によれば、許容経路に関連付けられた施設があっても、施設が利用できる時間外に当該施設と関連付けられたノードまたはリンクを経路探索装置の利用者が通過する場合には、施設が利用されないラベル情報のみが当該施設通過直後のノードに付与される。よって、実際の移動所要時間を踏まえて第２地点に到着する到着時刻を利用者に提供でき、利用者の利便性が向上する。