【手続補正書】
【提出日】平成28年9月16日(2016.9.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
設定された出発地から目的地までの経路を探索する経路探索装置であって、
道路網を表すノードおよびリンクと、各リンクの通過時間の平均を表す平均コスト値と、前記通過時間のばらつきの程度を表すばらつき値と、を含むネットワークデータを記憶する記憶部と、
前記出発地から前記目的地までに至るまでの経路を、前記平均コスト値と、前記ばらつき値と、前記ばらつき値の重み係数とを含む関数に従って算出される総合コスト値に基づいて推奨経路として決定する経路探索部と、を備える、経路探索装置。
【請求項２】
請求項１に記載の経路探索装置であって、
前記経路探索部は、前記推奨経路の候補となる複数の経路候補のうち、前記出発地から前記目的地までに通過した前記リンクに対応する前記平均コスト値の積算値に、前記重み係数と前記通過した前記リンクに対応する前記ばらつき値の積算値に対して正の相関を有する値とを乗じて算出した補正値を加えることで前記総合コスト値を算出する、経路探索装置。
【請求項３】
請求項１または請求項２に記載の経路探索装置であって、
前記経路探索部は、前記出発地から前記目的地に至るまでの経路において、前記出発地から前記経路の途中における特定の地点に対応するノードへ至るまでに通過した前記リンクの前記平均コスト値の積算値を示す第１項に、前記重み係数と前記通過した前記リンクに対応する前記ばらつき値の積算値とに基づいて算出した補正値を示す第２項を加えた候補総合コスト値に基づいて前記出発地から前記経路の途中における特定の地点に対応するノードへ至るまでの経路を前記推奨経路の途中経路として決定する、経路探索装置。
【請求項４】
請求項３に記載の経路探索装置であって、
前記経路探索部は、前記途中経路の候補となる複数の途中経路候補のうち、複数の前記候補総合コスト値のうち最小の前記候補総合コスト値を有する前記途中経路候補を前記途中経路として決定する、経路探索装置。
【請求項５】
請求項３に記載の経路探索装置であって、
前記経路探索部は、前記途中経路の候補となる複数の途中経路候補が有するそれぞれの前記候補総合コスト値のうち、互いの前記候補総合コスト値の差が所定値以下である複数の前記候補総合コスト値がある場合は、前記重み係数に応じて選択される前記第１項と前記第２項のうちの一方に基づいて前記途中経路を決定する、経路探索装置。
【請求項６】
請求項３に記載の経路探索装置であって、
前記経路探索部は、
前記途中経路の候補となる複数の途中経路候補のうち、複数の前記候補総合コスト値の中で最小の前記候補総合コスト値を有する第１途中経路候補を決定する第１決定工程と、
前記第１途中経路候補以外の前記途中経路候補である残余途中経路候補のうち、前記第１途中経路候補の前記平均コスト値の積算値よりも小さい前記平均コスト値の積算値を有する次点途中経路候補が１つ以上存在する場合に、前記１つ以上の前記次点途中経路候補のうち最小の前記候補総合コスト値を有する第２途中経路候補を決定する第２決定工程と、
前記第２決定工程によって決定した前記第２途中経路候補を前記第１途中経路候補とし、既に決定した前記第１途中経路候補および第２途中経路候補以外の前記途中経路候補を前記残余途中経路候補として、前記第２決定工程を繰り返し実行する第３決定工程と、を実行し、
前記第１〜３決定工程によって決定した前記第１途中経路候補および第２途中経路候補を前記途中経路として決定する、経路探索装置。
【請求項７】
請求項１に記載の経路探索装置であって、
前記経路探索部は、
前記出発地から前記目的地までに至るまでの経路において、前記出発地から前記経路の途中における特定の地点に対応する前記ノードに至るまでの途中経路の候補となる途中経路候補が複数存在する場合に、前記途中経路候補を通過した道路に対応する各リンクの前記通過時間の各ヒストグラムを表す各統計情報を畳み込み演算することでそれぞれの前記途中経路候補における通過時間のヒストグラムを表す候補統計情報を生成し、
前記候補統計情報から算出した前記途中経路候補の通過時間の平均を表す候補平均コスト値及び前記途中経路候補の通過時間のばらつきの程度を表す候補ばらつき値と、前記重み係数とを含む関数に従って算出される候補総合コスト値に基づいて、複数の前記途中経路候補から前記途中経路を決定する、経路探索装置。
【請求項８】
請求項７に記載の経路探索装置であって、
前記経路探索部は、前記候補平均コスト値を示す第１項と、前記候補ばらつき値と前記重み係数とに基づいて算出した補正値を示す第２項とを含む関数に従って、前記候補総合コスト値を算出する、経路探索装置。
【請求項９】
請求項８に記載の経路探索装置であって、
前記経路探索部は、前記複数の途中経路候補が有するそれぞれの前記候補総合コスト値のうち、互いの前記候補総合コスト値の差が所定値以下である複数の前記候補総合コスト値がある場合は、前記重み係数に応じて選択される前記第１項と前記第２項のうちの一方に基づいて前記途中経路を決定する、経路探索装置。
【請求項１０】
請求項１から請求項９までのいずれか一項に記載の経路探索装置であって、
前記経路探索部は、前記重み係数の複数の異なる値ごとに前記推奨経路を決定する、経路探索装置。
【請求項１１】
請求項１から請求項１０までのいずれか一項に記載の経路探索装置であって、
前記経路探索部は、各リンクの通過時間の各ヒストグラムを表す各統計情報を畳み込み演算することで前記推奨経路の通過時間のヒストグラムを表す統計情報を生成し、前記生成した統計情報の標準偏差に基づいて前記推奨経路の前記通過時間のばらつきの程度を表す指標を算出する、経路探索装置。
【請求項１２】
請求項１から請求項１１までのいずれか一項に記載の経路探索装置であって、
前記リンクの前記平均コスト値と前記ばらつき値とは、前記通過時間を表す通過時間データと前記通過時間ごとの発生確率を表す元情報に基づいて算出され、
前記リンクの前記通過時間が一定の頻度で地物によって影響を受ける場合において、
前記影響を受けるリンクである特定リンクの前記平均コスト値は、前記元情報が有する全ての前記通過時間データ及び前記発生確率をもとに算出され、
前記特定リンクの前記ばらつき値は、前記元情報のうち、前記地物の影響を受けずに通過したと推定された前記通過時間データ及び前記発生確率をもとに算出される、経路探索装置。
【請求項１３】
設定された出発地から目的地までの経路を探索する経路探索方法であって、
コンピュータが、道路網を表すノードおよびリンクと、各リンクの通過時間の平均を表す平均コスト値と、前記通過時間のばらつきの程度を表すばらつき値と、を含むネットワークデータを記憶装置に記憶する工程と、
コンピュータが、前記出発地から前記目的地までに至るまでの経路を、前記平均コスト値と、前記ばらつき値と、前記ばらつき値の重み係数とを含む関数に従って算出される総合コスト値に基づいて推奨経路として決定する工程と、を備える、経路探索方法。
【請求項１４】
設定された出発地から目的地までの経路を探索する機能をコンピュータに実現させるためのプログラムであって、
道路網を表すノードおよびリンクと、各リンクの通過時間の平均を表す平均コスト値と、前記通過時間のばらつきの程度を表すばらつき値と、を含むネットワークデータを記憶装置に記憶する機能と、
前記出発地から前記目的地までに至るまでの経路を、前記平均コスト値と、前記ばらつき値と、前記ばらつき値の重み係数とを含む関数に従って算出される総合コスト値に基づいて推奨経路として決定する機能と、を実現させるためのプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
（５）上記形態の経路探索装置において、前記経路探索部は、前記途中経路の候補となる複数の途中経路候補が有するそれぞれの前記候補総合コスト値のうち、互いの前記候補総合コスト値の差が所定値以下である２以上の前記候補総合コスト値がある場合は、前記重み係数に応じて選択される前記第１項と前記第２項のうちの一方に基づいて前記途中経路を決定しても良い。この形態の経路探索装置によれば、設定された重み係数に基づいて出発地から目的地までの推奨経路を柔軟に決定できる。例えば、重み係数が小さい場合は、平均コスト値をばらつき値よりも重視して平均コスト値の累積値が小さい経路を推奨経路とし、重み係数が大きい場合は、ばらつき値を平均コスト値よりも重視してばらつき値の積算値が小さい経路を推奨経路として決定できる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
（６）上記形態の経路探索装置において、前記経路探索部は、前記途中経路の候補となる複数の途中経路候補のうち、複数の前記候補総合コスト値の中で最小の前記候補総合コスト値を有する第１途中経路候補を決定する第１決定工程と、前記第１途中経路候補以外の前記途中経路候補である残余途中経路候補のうち、前記第１途中経路候補の前記平均コスト値の積算値よりも小さい前記平均コスト値の積算値を有する次点途中経路候補が１つ以上存在する場合に、前記１つ以上の前記次点途中経路候補のうち最小の前記候補総合コスト値を有する第２途中経路候補を決定する第２決定工程と、前記第２決定工程によって決定した前記第２途中経路候補を前記第１途中経路候補とし、既に決定した前記第１途中経路候補および第２途中経路候補以外の前記途中経路候補を前記残余途中経路候補として、前記第２決定工程を繰り返し実行する第３決定工程と、を実行し、前記第１〜３決定工程によって決定した前記第１途中経路候補および第２途中経路候補を前記途中経路として決定しても良い。この形態の経路探索装置によれば、より正確に総合コスト値が最小となる経路を推奨経路として決定できる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
付加情報の項目ＡＩに表された３つの選択枝と、重み係数λとの関係は例えば以下の通りである。
（ｉ）選択枝「早い」：重み係数λが「０」に設定され、出発地から目的地までに至る複数の経路のうち平均通過時間がばらつき値に無関係に最も短い経路が推奨経路として経路サーバ２０によって決定される。
（ｉｉ）選択枝「普通」：重み係数λが「１」に設定され、出発地から目的地までに至る複数の経路のうち、ばらつき値を選択枝「早い」よりも重視した経路が推奨経路として経路サーバ２０によって決定される。
（ｉｉｉ）選択枝「正確」：重み係数λが「２」に設定され、出発地から目的地までに至る複数の経路のうちばらつき値を選択枝「普通」よりも重視した経路が推奨経路として経路サーバ２０によって決定される。
なお、重み係数λは、「０」、「１」、「２」の３段階に限らず、複数の整数によって設定されても良いし、バーなどによって連続的な数値として設定されても良い。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
図２は、道路ネットワークデータ２４の具体例として所定範囲の道路を示す道路ネットワークデータＮＷ１の説明図である。道路ネットワークデータＮＷ１は、道路の配置をリンクおよびノードを用いて表したデータである。以下の説明では、図中のノードを個別に示す場合には、英文字「Ｎ」の後に数字を付した符号を用い、図中のリンクを個別に示す場合には、英文字「Ｌ」の後に数字を付した符号を用いる。図２には、４個のノードＮ１〜Ｎ４と、４個のリンクＬ１〜Ｌ４とが図示されている。ノードＮ１〜Ｎ４は、道路や車線における特徴的な基準点を表現する。この基準点としては、交差点、分岐点、幅員が変化する点などが挙げられる。リンクＬ１〜Ｌ４は、ノードＮ１〜Ｎ４の間を接続する道路や車線を表現する。各リンクＬ１〜Ｌ４にはそれぞれ、出発地点Ｓから目的地点Ｇまでの経路を探索するために利用される経路探索情報ＲＳＩが対応して規定されている。経路探索情報ＲＳＩは、各リンクＬ１〜Ｌ４の通過時間の平均を表す平均コスト値ＡＣと、通過時間のばらつきの程度を表すばらつき値ＶＶとを含む。平均コスト値ＡＣは、横軸に通過時間、縦軸に通過時間ごとの発生確率（％）を表すデータであるヒストグラムから算出される。本実施形態において、このヒストグラムは、プローブカーからネットワークを介して収集されたプローブデータを元に生成される。また、本実施形態において、ばらつき値ＶＶはヒストグラムから算出した分散である。なお、他の実施形態では、ばらつき値ＶＶを分散に代えて標準偏差などを用いても良い。図２の道路ネットワークデータＮＷ１において、各リンクＬ１〜Ｌ４の括弧書きで付された一番目の数値が平均コスト値ＡＣであり、二番目の数値がばらつき値ＶＶである。また、道路ネットワークデータＮＷ１には、交通規制に関する規制情報が規定されている。規制情報としては、リンクＬ３からリンクＬ２への左折禁止を表す情報などがある。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
ノード属性データ３１のノード番号は、ノードを識別するためにノード毎に割り当てられた固有の番号である。ノード属性データ３１の位置座標は、地図上におけるノードの位置を表す。ノード属性データ３１のノード種別は、ノードが表現する基準点の種別を表す。ノード属性データ３１の接続リンク数は、ノードに接続するリンクの数を示す。ノード属性データ３１の接続リンク番号は、ノードに接続するリンクを識別するための情報である。図４に示す例は、ノード番号「Ｎ２」が割り当てられたノードＮ２に関するノード属性データ３１の詳細内容を示している。具体的には、ノードＮ２が座標「Ｘｎ２（経度）、Ｙｎ２（緯度）」上に位置し、ノードＮ２が「交差点」を表し、ノードＮ２に接続するリンクの数が「２」であり、接続するリンクの番号が「Ｌ１，Ｌ２」であることが表されている。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
経路探索部２９は、経路探索処理を開始すると、実行開始情報に含まれる地点情報に基づいて経路探索処理に用いる出発地の座標及び目的地の座標の設定を行う（ステップＳ１２）。ステップＳ１２の後に、出発地の座標及び目的地の座標に基づいて、経路探索処理を行う上での経路の始点である出発地点Ｓと、終点である目的地点Ｇとを設定する（ステップＳ１４）。本実施形態では、ノードＮ１が出発地点Ｓに設定され、ノードＮ４が目的地点Ｇに設定された例を示す。なお、設定された出発地又は目的地がノード上に存在しない場合は、出発地又は目的地に最も近いリンク上の点（引込点とも呼ぶ）を出発地点Ｓ又は目的地点Ｇとして設定する。そして、経路探索部２９は、出発地点Ｓから目的地点Ｇまでの経路のうち、通過する経路の総合コスト値の総和が最小となる経路を推奨経路として決定する。総合コスト値は、出発地点Ｓから目的地点Ｇまでに通過したリンクに対応する平均コスト値ＡＣの積算値に、重み係数λと通過したリンクに対応するばらつき値ＶＶの積算値とに基づいて算出した補正値を加えた値である。具体的には、本実施形態では以下の式（１）を用いて総合コスト値が定められる。
【数１】
2015161557.tif 000001
ここで、Ａは出発地点Ｓから目的地点Ｇに至る経路のリンク毎の平均コスト値ＡＣ、λは重み係数、Ｖは出発地点Ｓから目的地点Ｇに至る経路のリンク毎のばらつき値ＶＶである。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
サブステップＣ４では、出発地点Ｓから次のノードＮ３までに至る経路の候補総合コスト値が上記式（２）を用いて算出される。具体的には、出発地点Ｓに設定された平均コスト値ＡＣ「０」に、リンクＬ３に設定された平均コスト値ＡＣ「３０」を積算することでコスト積算値「３０」を算出する。また、サブステップＣ４では、出発地点Ｓに設定されたばらつき値ＶＶ「０」に、リンクＬ３に設定されたばらつき値ＶＶ「１５」を積算することで分散積算値「１５」を算出する。次に、サブステップＣ３と同様に、経路探索部２９は、コスト積算値「３０」に、分散積算値「１５」の正の平方根と重み係数λとの積である補正値を加えた候補総合コスト値Ｖ２を算出する。算出した候補総合コスト値Ｖ２は「３７．７」である。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００４４
【補正方法】変更
【補正の内容】
【００４４】
図７は、表示パネル６５に表示された出力情報画面Ｗ２の説明図である。本実施形態では、利用者は、探索設定画面Ｗ１において「普通（λ＝１）」と「早い（λ＝０）」の２つを選択したとする。出力情報画面Ｗ２は、重み係数λごとに決定された推奨経路と、通過時間とを含む。推奨経路は地図データ上に赤線などの目印を付すことで表される。通過時間は、平均通過時間と標準偏差とによって表される。詳細には、重み係数λが「１」である「ルート（普通）」では、平均通過時間の４６分に、標準偏差「４」をプラスマイナスした式（４６±４）によって通過時間が表される。利用者は、表示された２つのルート（普通、早い）のいずれかの推奨経路を選択することで、カーナビ５０による経路案内が開始される。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００５８
【補正方法】変更
【補正の内容】
【００５８】
ステップＳ６０の後に、経路探索部２９は既に決定した第１と第２途中経路候補Ｒ１１，Ｒ１０以外の途中経路候補Ｒ９を残余途中経路候補Ｒ９として再びステップＳ５６の処理を実行する。図１２に示すように、残余途中経路候補Ｒ９に対応する候補ラベルＴ９のコスト積算値「８９」は、直前の処理において決定した第２途中経路候補Ｒ１０に対応する候補ラベルＴ１０のコスト積算値「７８」よりも大きい。よって、図９に示すように、経路探索部２９は、ステップＳ５６において「ＮＯ」の判定を行い、今までの処理によって決定した候補ラベルＴ１１，１０を確定ラベルとして決定する。これにより、確定ラベルＴ１１，１０に対応する第１と第２の途中経路候補Ｒ１１，Ｒ１０が途中経路Ｒ１１、Ｒ１０として決定する（ステップＳ６２）。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
図１０に示すようにノードＮ１０の地点では、最小の候補総合コスト値を有する第１候補ラベルが候補ラベルＴ５であるにもかかわらず、図１２に示すように探索枝を伸ばした際には第１候補ラベルが候補ラベルＴ１１となっている。候補ラベルＴ１１は、図１０において候補ラベルＴ７から探索枝を伸ばしたラベルである。すなわち、最小の候補総合コスト値を有するラベルのみを確定ラベルとして決定し、探索枝を伸ばした場合、最小の候補総合コスト値を有する経路が推奨経路として決定できない場合が生じ得る。しかしながら、以上説明したように上記実施形態では、最小の候補総合コスト値を有する候補ラベル（第１候補ラベル）に加え、第１候補ラベルよりもコスト積算値が小さい候補ラベルのうち所定の条件を満たす候補ラベル（第２候補ラベル）も確定ラベルとして決定している。これにより、より正確に総合コスト値が最小となる経路を推奨経路として決定できる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
Ｄ．変形例
Ｄ−１．第１変形例：
上記第１，２実施形態では、ばらつき指標をばらつき積算値の正の平方根をとることで算出していたが、これに代えて推奨経路又は途中経路を構成する各リンクの平均コスト値ＡＣを算出する際に用いるヒストグラムを表す統計情報を用いても良い。具体的には、各リンクの統計情報を畳み込み演算し、畳み込み演算後のヒストグラムを表す統計情報から算出した標準偏差をばらつき指標としても良い。また、畳み込み演算後のヒストグラムを表す統計情報から算出した平均コスト値を推奨経路又は途中経路を決定する際に用いても良い。以下に詳細を説明する。図１３は、畳み込み演算の概念図である。図１３の例では、出発地点Ｓから目的地点Ｇの推奨経路がリンクＬ１０，Ｌ１２，Ｌ１４によって構成されている。また、リンクデータ２５には、リンク番号、始点ノード、終点ノード、平均コスト値ＡＣ、及び、ばらつき値ＶＶに加えてヒストグラムＨ１０，Ｈ１２，Ｈ１４を表すデータ（統計情報）が規定されている。ヒストグラムＨ１０，Ｈ１２，Ｈ１４は、例えばプローブカーから収集されたプローブデータを元に生成され、横軸にリンクの通過時間（分）、縦軸に通過時間ごとの発生確率（％）をとっている。出発地点Ｓから目的地点Ｇに向かう直近のリンクＬ１０と次のリンクＬ１２とのヒストグラムを畳み込み演算し、新たなヒストグラムＨ１８を生成する。そして、リンクＬ１２の次のリンクであるリンクＬ１４のヒストグラムＨ１４と、ヒストグラムＨ１８とを畳み込み演算し、新たなヒストグラムＨ２０を生成する。畳み込み演算により生成したヒストグラムＨ１８，Ｈ２０を表す統計情報から標準偏差を求める。言い換えれば、上記のヒストグラムの畳み込み演算は、以下の式（３）によって規定される。
【数３】
2015161557.tif 000002
ここで、左辺のＦ(m)は、二つのヒストグラムを畳み込み演算することで生成される関数であり、ｆは、一つ目のヒストグラムで定義された関数であり、ｇは、二つ目のヒストグラムで定義された関数であり、ｎは、一つ目のヒストグラムにおける通過時間を表し、ｍは、一つ目と二つ目とのヒストグラムを畳み込み演算した際の通過時間（合計時間）を表す。このようにしても、上記第１，２実施形態と同様に推奨経路または途中経路における通過時間に対するばらつき指標を標準偏差として算出できる。また、畳み演算後のヒストグラムが表す統計情報から標準偏差を算出することで、上記実施形態に比べ誤差を低減したより正確なばらつき指標を算出できる。