(57)【要約】  経路分析装置は、出発地から目的地までの経路を分析するための装置であり、複数の将来時間それぞれ毎に、出発地から目的地までに存在する複数の区間それぞれにおける交通状況を予測する、交通状況予測部１１と、交通状況予測部１１による予測が行なわれた時点からの経過時間に応じて、将来時間毎に予測された交通状況のいずれかを選択し、選択した交通状況を用いて、複数の区間それぞれの経過時間に応じた移動時間を推定する、推定部１２と、複数の区間について推定された移動時間を用いて、出発地から目的地までの移動時間の最小値を算出する、経路分析部１３と、を備えている。
2017130428.tif 000002
【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を分析するための装置であって、
複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、交通状況予測部と、
前記交通状況予測部による予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、推定部と、
前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、経路分析部と、
を備えていることを特徴とする経路分析装置。
【請求項２】
前記経路分析部は、更に、前記複数の区間を用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項１に記載の経路分析装置。
【請求項３】
前記交通状況予測部は、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記推定部は、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
請求項１または２に記載の経路分析装置。
【請求項４】
出発地から目的地までの経路を分析するための方法であって、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を備えていることを特徴とする経路分析方法。
【請求項５】
前記（ｃ）のステップにおいて、更に、前記複数の区間を用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項４に記載の経路分析方法。
【請求項６】
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
請求項４または５に記載の経路分析方法。
【請求項７】
コンピュータによって、出発地から目的地までの経路を分析するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【請求項８】
前記（ｃ）のステップにおいて、更に、前記複数の区間を用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項７に記載のコンピュータ読み取り可能な記録媒体。
【請求項９】
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
請求項７または８に記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適な経路又は移動時間を予測するための、経路分析装置、経路分析方法、及びこれらを実現するためのプログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
近年、カーナビゲーションシステムにおいては、出発地から目的地に到達するまでの移動時間を正確に予測することが求められている。これは、配送業者などの道路利用者において、高精度な配送計画を立てることが求められているためである。また、時間が正確に予測できることにより、ドライバーにおける利便性が向上すると共に、運転によるストレスの軽減も期待されている。【０００３】
例えば、特許文献１は、このような移動時間を正確に予測するシステムの一つを開示している。特許文献１に開示されたシステムでは、出発地から目的地までの経路が複数のリンクで区切られ、リンクそれぞれについて、時間帯毎に、所要時間又は移動速度の予測値が用意される。そして、特許文献１に開示されたシステムは、ユーザが移動中であるときに、現在の出発からの時間経過と、現在通過しているリンクとを、時間帯毎の予測値に照らし合わせながら、経路の移動時間を計算する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第７８９４９８１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記特許文献１に開示されたシステムによれば、設定された経路の移動時間を、複数時間軸の予測値から計算できるので、移動時間の精度が向上すると考えられる。しかしながら、経路は外部から与えられるものであり、上記特許文献１に開示されたシステムは、この与えられた経路について移動時間を計算するだけである。つまり、出発地と目的地との間に、別の最適な経路が存在していたとしても、上記特許文献１に開示されたシステムでは、別の経路について移動時間を計算することは不可能である。【０００６】
本発明の目的の一例は、上記問題を解消し、目的地から出発地までの最短の移動時間を推定し得る、経路分析装置、経路分析方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明の一側面における経路分析装置は、出発地から目的地までの経路を分析するための装置であって、
複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、交通状況予測部と、
前記交通状況予測部による予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、推定部と、
前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、経路分析部と、
を備えていることを特徴とする。【０００８】
また、上記目的を達成するため、本発明の一側面における経路分析方法は、出発地から目的地までの経路を分析するための方法であって、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を備えていることを特徴とする。【０００９】
更に、上記目的を達成するため、本発明の一側面におけるコンピュータ読み取り可能な記録媒体は、コンピュータによって、出発地から目的地までの経路を分析するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させる命令を含む、プログラムを記録していることを特徴とする。
【発明の効果】
【００１０】
以上のように、本発明によれば、目的地から出発地までの最短の移動時間を推定することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、本発明の実施の形態１における経路分析装置の概略構成を示すブロック図である。
【図２】図２は、本発明の実施の形態１における経路分析装置の具体的構成を示すブロック図である。
【図３】図３は、本発明の実施の形態１における将来時間毎に予測された交通状況の一例を示す図である。
【図４】図４は、本発明の実施の形態１における推定部の処理を説明するための図である。
【図５】図５は、本発明の実施の形態１における経路分析装置の動作を示すフロー図である。
【図６】図６は、図５に示した移動時間の推定処理を具体的に示すフロー図である。
【図７】図７は、図６に示すステップＢ３を説明する図である。
【図８】図８は、図６に示すステップＢ９を説明する図である。
【図９】図９は、本発明の実施の形態２で実行される移動時間の推定処理を具体的に説明する図である。
【図１０】図１０は、本発明の実施の形態２で行なわれる計算処理を説明する図である。
【図１１】図１１は、本発明の実施の形態１及び２における経路分析装置を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００１２】
（実施の形態１）
以下、本発明の実施の形態１における、経路分析装置、経路分析方法、及びプログラムについて、図１〜図８を参照しながら説明する。
【００１３】
［装置構成］
最初に、本実施の形態１における経路分析装置の概略構成について説明する。図１は、本発明の実施の形態１における経路分析装置の概略構成を示すブロック図である。
【００１４】
図１に示す本実施の形態１における経路分析装置１０は、出発地から目的地までの経路を分析するための装置である。図１に示すように、経路分析装置１０は、交通状況予測部１１と、推定部１２と、経路分析部１３とを備えている。
【００１５】
交通状況予測部１１は、複数の将来時間それぞれ毎に、出発地から目的地までに存在する複数の区間それぞれにおける交通状況を予測する。
【００１６】
推定部１２は、交通状況予測部１１による予測が行なわれた時点からの経過時間に応じて、将来時間毎に予測された交通状況のいずれかを選択する。また、推定部１２は、選択した交通状況を用いて、出発地から目的地までに存在する複数の区間それぞれの経過時間に応じた移動時間を推定する。
【００１７】
経路分析部１３は、出発地から目的地までに存在する複数の区間について推定された移動時間を用いて、出発地から目的地までの移動時間の最小値を算出する。
【００１８】
このように、経路分析装置１０では、出発地から目的地までの経路を構成する区間毎に、移動時間が推定されるので、出発から目的地までの経路が複数存在する場合は、各経路について移動時間が推定される。このため、経路分析装置１０によれば、目的地から出発地までの最短の移動時間を推定することが可能となる。
【００１９】
続いて、図２〜図４を更に用いて、本実施の形態１における経路分析装置の構成についてより具体的に説明する。図２は、本発明の実施の形態１における経路分析装置の具体的構成を示すブロック図である。図３は、本発明の実施の形態１における将来時間毎に予測された交通状況の一例を示す図である。図４は、本発明の実施の形態１における推定部の処理を説明するための図である。
【００２０】
図２に示すように、本実施の形態１では、経路分析装置１０は、ネットワークを介して、外部の交通管理システム２０に接続されている。交通管理システム２０は、道路情報を格納する道路情報データベース（ＤＢ）２１と、交通情報を格納する交通情報データベース（ＤＢ）２２とを備えている。
【００２１】
また、道路情報には、道路のトポロジ、車線数、信号機の位置、ランドマーク（建物、駅、公園等）の位置等が含まれている。交通情報には、道路を走る車両の速度、工事区間の位置及び長さ、事故発生地点の位置等が含まれている。更に、交通管理システム２０は、道路の脇に設置されている路側センサからのセンサデータ、車両に搭載されている車載端末からのデータを取得し、取得したデータを用いて交通情報を更新する。
【００２２】
また、図２に示すように、本実施の形態１では、経路分析装置１０は、交通状況予測部１１、推定部１２、及び経路分析部１３に加えて、記憶部１４を更に備えている。記憶部１４は、交通状況予測部１１によって予測された交通状況を格納している。
【００２３】
交通状況予測部１１は、本実施の形態１では、交通管理システム２０にアクセスして、道路情報及び交通情報を取得する。そして、交通状況予測部１１は、取得した道路情報及び交通情報に基づいて、将来時間毎に、交通状況として、各区間の移動時間又は移動速度を予測する。また、交通状況予測部１１は、本実施の形態１では、交通管理システム２０から取得した道路情報及び交通情報から、現在（予測処理の実行時）の交通状況の推定も行なっている。
【００２４】
具体的には、交通状況予測部１１は、曜日、時間帯、天候等の要因をパラメータとして、過去の交通状況のデータを用いて、機械学習を実行し、モデルを構築する。そして、交通状況予測部１１は、モデルを用いて、将来時間毎に、各区間について移動時間又は移動速度を予測する。なお、モデルの構築は、既存の技術を用いて行なわれても良いし、今後新たに開発される技術を用いて行なわれても良い。
【００２５】
交通状況予測部１１によって予測された又は取得された交通状況の例は、図３に示す通りである。図３の例では、将来時間は、一定の間隔（例えば０．５時間）毎に設定されている。交通状況予測部１１は、現在を基準に、０．５時間後、１時間後、１．５時間後、２．０時間後について、交通状況を予測している。なお、図３の例に示す移動時間は、区間を車両が走行した場合の予測移動時間である。また、図３に示された交通状況１５は、記憶部１４に格納される。
【００２６】
推定部１２は、本実施の形態１では、まず、記憶部１４に格納されている交通状況１５を取得する。具体的には、推定部１２は、予測が行なわれた時点（現在）の交通状況と、０．５時間後の交通状況と、１．０時間後の交通状況と、１．５時間後の交通状況と、２．０時間後の交通状況とを取得する。
【００２７】
次に、推定部１２は、取得した各交通状況（移動時間）を用いて、図４に示すように、各区間について、将来時間毎に、即ち現時点からの経過時間に応じて、空間ネットワークトポロジを作成する。また、図４に示す空間ネットワークトポロジにおいては、各区間がノード間を結ぶリンクとなっている。また、リンクは、該当時刻における交通状況予測値をリンク値として保持する。また、ノードは、出発地及び目的地を含む地点である。図４において、地点Ａが出発地、地点Ｄが目的地であるとすると、地点Ｂ及び地点Ｃは経由点となる。
【００２８】
次に、推定部１２は、図４に示すように、各空間ネットワークトポロジを構成する各ノードを、将来時間毎に、時間拡大トポロジに展開する。そして、推定部１２は、各時間拡大トポロジに基づいて、時間拡大トポロジにおいて、各ノードから、これに連結可能なノードへと移動時間に応じた長さでリンクを接続する。例えば、現在の地点が地点Ａであるとすると、経過時間が０の場合、地点Ａが連結可能なノードは地点Ｂと地点Ｃとであり、それぞれへの移動時間は共に０．５ｈであるので、現在の地点Ａは０．５時間後の地点Ｂ及びＣにリンクで接続される。時間拡大トポロジの構築により、各区間において、経過時間に応じた移動時間が推定されたことになる。
【００２９】
経路分析部１３は、本実施の形態１では、推定部１２によって構築された時間拡大トポロジを用いて、現在の地点から目的地までの移動時間の最小値を算出する。また、このとき、経路分析部１３は、移動時間を最小値とする経路を特定することもできる。つまり、経路分析部１３は、現在の地点から目的地までに存在する区間を用いて、現在の地点から目的地までの経路を、移動時間が最小値となるように特定する。移動時間の算出方法、及び経路の特定方法としては、ダイクストラ法等、任意のコスト算出方法及び経路特定方法を用いることができる。
【００３０】
また、経路分析部１３は、算出した最小値と特定した経路とを、ユーザの端末装置３０に送信する。これにより、ユーザは、端末装置３０の画面上で、移動時間の最小値と、経路とを確認することができる。
【００３１】
［装置動作］
次に、本実施の形態１における経路分析装置の動作について図５を用いて説明する。図５は、本発明の実施の形態１における経路分析装置の動作を示すフロー図である。以下の説明においては、適宜図１〜図４を参酌する。また、本実施の形態１では、経路分析装置を動作させることによって、経路分析方法が実施される。よって、本実施の形態における経路分析方法の説明は、以下の経路分析装置１０の動作説明に代える。
【００３２】
最初に、図５に示すように、ユーザからの指示があると、交通状況予測部１１は、交通管理システム２０から道路情報及び交通情報を取得して、将来時間毎に、出発地から目的地までに存在する各区間における交通状況を予測する（ステップＡ１）。また、交通状況予測部１１は、予測した各交通状況を記憶部１４に格納する。
【００３３】
次に、推定部１２は、ステップＡ１による予測が行なわれた時点から経過時間に応じて、将来時間毎に予測された交通状況のいずれかを選択し、選択した交通状況を用いて、各区間の経過時間に応じた移動時間を推定する（ステップＡ２）。なお、ステップＡ２については、図６を用いて後述する。
【００３４】
次に、経路分析部１３は、各区間について推定された移動時間を用いて、出発地から目的地までの移動時間の最小値を算出すると共に、移動時間を最小値とする経路を特定する（ステップＡ３）。
【００３５】
その後、経路分析部１３は、ステップＡ３で算出した最小値と、同じくステップＡ３で特定した経路とを、ユーザの端末装置３０に送信する（ステップＡ４）。ステップＡ１〜Ａ４の実行により、ユーザは、端末装置３０の画面上で、移動時間の最小値と、経路とを確認することができる。
【００３６】
また、ステップＡ１〜Ａ４に示す動作は、ユーザからの要求前に行われ、算出された移動時間及び特定された経路が予め保存されていても良い。この場合は、ユーザからの要求に応じて、予め保存されている移動時間及び経路情報が取得され、ユーザに送信される。また、ユーザからの要求前に、主要な地点間の移動時間の算出及び経路の特定が行われ、ユーザから要求があった場合に、要求に含まれる地点と主要な地点との間について移動時間の算出及び経路の特定が行われても良い。この場合は、要求前に求められた移動時間及び経路と、要求後に求められた移動時間及び経路とが組み合わされ、組み合わせ後の移動時間及び経路が、ユーザに送信される。
【００３７】
ここで、上述したステップＡ２について図６〜図８を用いてより具体的に説明する。図６は、図５に示した移動時間の推定処理を具体的に示すフロー図である。図７は、図６に示すステップＢ３を説明する図である。図８は、図６に示すステップＢ９を説明する図である。
【００３８】
図６に示すように、最初に、ステップＡ２において、推定部１２は、記憶部１４から、将来時間毎の交通状況１５を取得する（ステップＢ１）。次に、推定部１２は、ステップＢ１で取得した各交通状況（移動時間）を用いて、各区間について、将来時間毎に、空間ネットワークトポロジ（図４参照）を作成する（ステップＢ２）。
【００３９】
次に、推定部１２は、図８に示すように、各空間ネットワークトポロジを構成する各ノードを、将来時間毎に、時間拡大トポロジに展開する（ステップＢ３）。また、推定部１２は、各ノードを時間拡大トポロジに展開すると、ｔ＝０に設定して、計算対象となる時間を現在の時刻に設定する。
【００４０】
次に、推定部１２は、空間ネットワークトポロジを構成するリンクの一つ（リンクｉ）を選択する（ステップＢ４）。次に、推定部１２は、交通状況１５から、リンクｉの時刻ｔにおける移動時間ｄ（ｉ,ｔ）を取得する（ステップＢ５）。次に、推定部１２は、繰り返し数として用いる変数Ｌを１に設定する（ステップＢ６）。
【００４１】
次に、推定部１２は、ステップＢ５で取得した移動時間ｄ（ｉ,ｔ）に基づいて、リンクｉにおいては、Ｌ×△ｔの間に、車両は次のノード（リンクｉの端のノード）に到着するかどうかを判定する（ステップＢ７）。なお、△ｔは、各将来時刻の間隔であり、図４の例では、０．５時間に設定されている。
【００４２】
ステップＢ７の判定の結果、到着しない場合は、推定部１２は、Ｌの値を１増加させ（ステップＢ８）、その後に、再度ステップＢ６を実行する。一方、ステップＢ７の判定の結果、到着する場合は、推定部１２は、時間的拡大トポロジにおいて、ノードｉから、時刻（ｔ＋Ｌ×△ｔ）の次のノードへとリンクを接続する（ステップＢ９）。また、推定部１２は、リンクの移動時間をｄ（ｉ，ｔ）とする。
【００４３】
次に、推定部１２は、ｔの値が最大値となっているかどうかを判定し（ステップＢ１０）、最大値となっていない場合は、ｔの値に△ｔを加算し（ステップＢ１１）、その後、再度、ステップＢ５を実行する。一方、最大値となっている場合は、推定部ステップ１２は、全てのリンクについて処理が終了しているかどうかを判定する（ステップＢ１２）。
【００４４】
ステップＢ１２の判定の結果、全てのリンクについて処理が終了していない場合は、推定部１２は、再度ステップＢ４を実行する。一方、ステップＢ１２の判定の結果、全てのリンクについて処理が終了している場合は、推定部１２における処理は終了する。
【００４５】
［実施の形態１における効果］
以上のように本実施の形態１によれば、目的地から出発地までの最短の移動時間を推定することができ、更には、移動時間が最短となる経路の特定も可能となる。また、移動時間の推定は、交通情報及び道路情報による交通状況の予測の結果に基づいて行なわれているので、推定された移動時間の精度は高く、特定される経路は最適なものとなっている。
【００４６】
［プログラム］
本実施の形態１におけるプログラムは、コンピュータに、図５に示すステップＡ１〜Ａ４、図６に示すステップＢ１〜Ｂ１２を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態１における経路分析装置１０と経路分析方法とを実現することができる。この場合、コンピュータのＣＰＵ（Central Processing Unit）は、交通状況予測部１１、推定部１２、及び経路分析部１３として機能し、処理を行なう。
【００４７】
また、本実施の形態１におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、交通状況予測部１１、推定部１２、及び経路分析部１３のいずれかとして機能しても良い。
【００４８】
（実施の形態２）
次に本発明の実施の形態２における、経路分析装置、経路分析方法、及びプログラムについて説明する。
【００４９】
まず、本実施の形態２における経路分析装置は、図１及び図２に示した実施の形態１における経路分析装置１０と同様に構成されている。更に、本実施の形態２においても、経路分析装置は、図５に示したステップＡ１〜Ａ４に沿って動作する。
【００５０】
但し、本実施の形態２における経路分析装置は、交通状況予測部１１及び推定部１２における動作の点でのみ、実施の形態１における経路分析装置と異なっている。つまり、本実施の形態２では、交通状況予測部１１は、将来時間毎に、交通状況として、各区間おける速度を取得する。また、推定部１２は、交通状況のいずれかを選択した後に、区間毎に、未到達距離を求め、選択した交通状況に含まれる各区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を各区間の移動時間として推定する。また、このため、本実施の形態２は、図５に示すステップＡ２の具体的内容の点でも、実施の形態１と異なっている。
【００５１】
以下、実施の形態２との相違点について図９及び図１０を用いて具体的に説明する。図９は、本発明の実施の形態２で実行される移動時間の推定処理を具体的に説明する図である。図１０は、本発明の実施の形態２で行なわれる計算処理を説明する図である。また、以下の説明では適宜図１及び図２を参照すると共に、これらの図で用いた符号も異様する。
【００５２】
図９に示すように、最初に、推定部１２は、記憶部１４から、将来時間毎の交通状況１５を取得する（ステップＣ１）。次に、推定部１２は、ステップＣ１で取得した各交通状況を用いて、各区間について、将来時間毎に、空間ネットワークトポロジ（図４参照）を作成する（ステップＣ２）。なお、本実施の形態２では、各交通状況は、移動速度で表されている。
【００５３】
次に、推定部１２は、各空間ネットワークトポロジを構成する各ノードを、将来時間毎に、時間拡大トポロジに展開する（ステップＣ３）。また、推定部１２は、各ノードを時間拡大トポロジに展開すると、ｔ＝０に設定して、計算対象となる時間を現在の時刻に設定する。
【００５４】
次に、推定部１２は、空間ネットワークトポロジを構成するリンクの一つ（リンクｉ）を選択する（ステップＣ４）。次に、推定部１２は、交通状況１５から、リンクｉの未到達距離ｒをリンクｉの総距離Ｓに設定し、更に、リンクｉの走行にかかる総移動時間Ｄを０（ゼロ）に設定し、繰り返し数として用いる変数Ｌを０に設定する（ステップＣ５）。
【００５５】
次に、推定部１２は、交通状況１５から、リンクｉの時刻ｔ＋Ｌ×△ｔにおける速度ｖ（ｉ,ｔ＋Ｌ×△ｔ）を取得する（ステップＣ６）。次に、推定部１２は、未到達距離ｒを、ステップＣ６で取得した速度ｖ（ｉ,ｔ＋Ｌ×△ｔ）で除算して、移動時間ｄ（ｉ,ｔ＋Ｌ×△ｔ）を算出する（ステップＣ７）。また、ステップＣ７では、リンクｉの走行にかかる総移動時間Ｄに、算出した移動時間ｄ（ｉ,ｔ＋Ｌ×△ｔ）を加算する。
【００５６】
次に、推定部１２は、ステップＣ７で算出した移動時間ｄ（ｉ,ｔ＋Ｌ×△ｔ）に基づいて、リンクｉにおいては、Ｌ×△ｔの間に、車両は次のノード（リンクｉの端のノード）に到着するかどうか（Ｄ＜（Ｌ＋１）×△ｔ）を判定する（ステップＣ８）。
【００５７】
ステップＣ８の判定の結果、到着しない場合は、推定部１２は、リンク内の未到達距離ｒを算出する。即ち、推定部１２は、下記の数１を用いて未到達距離ｒを計算する（ステップＣ９）。また、その後、推定部１２は、Ｌの値を１増加させ（ステップＣ１０）、その後に、再度ステップＣ６を実行する。
【００５８】
（数１）
未到達距離ｒ＝（残りの距離ｒ’）−（△ｔの走行距離）
＝ｒ’−ｖ（ｉ，ｔ）×△ｔ
【００５９】
ステップＣ８の判定の結果、到着する場合は、推定部１２は、時間拡大トポロジにおいて、ノードｉから、時刻（ｔ＋Ｌ×△ｔ）の次のノードへとリンクを接続する（ステップＣ１１）。
【００６０】
次に、推定部１２は、ｔの値が最大値となっているかどうかを判定し（ステップＣ１２）、最大値となっていない場合は、ｔの値に△ｔを加算し（ステップＣ１３）、その後、再度、ステップＣ６を実行する。一方、最大値となっている場合は、推定部ステップ１２は、全てのリンクについて処理が終了しているかどうかを判定する（ステップＣ１４）。
【００６１】
ステップＣ１４の判定の結果、全てのリンクについて処理が終了していない場合は、推定部１２は、再度ステップＣ４を実行する。一方、ステップＣ１４の判定の結果、全てのリンクについて処理が終了している場合は、推定部１２における処理は終了する。
【００６２】
［実施の形態２における効果］
以上のように、本実施の形態２では、図１０に示すように、△ｔの間に車両がリンクを走りきれない場合に、△ｔ×予測速度を途中の移動時間とし、更に、残りの部分のリンクを走りきる際の時間を計算することで、リンクの移動時間が算出される。このため、本実施の形態２によれば、△ｔの間に車両がリンクを走りきれない場合が考慮されることになるので、実施の形態１に比べて、移動時間の算出精度がより向上されることになる。
【００６３】
［プログラム］
本実施の形態２におけるプログラムは、コンピュータに、図５に示すステップＡ１〜Ａ４、図９に示すステップＣ１〜Ｃ１４を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態２における経路分析装置１０と経路分析方法とを実現することができる。この場合、コンピュータのＣＰＵ（Central Processing Unit）は、交通状況予測部１１、推定部１２、及び経路分析部１３として機能し、処理を行なう。
【００６４】
また、本実施の形態２におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、交通状況予測部１１、推定部１２、及び経路分析部１３のいずれかとして機能しても良い。
【００６５】
（変形例）
ここで、実施の形態１及び２の変形例について説明する。まず、推定部１２は、時間拡大トポロジを作成する際において、各リンクに対して、移動時間だけでなく、誤差情報（予測誤差や分散、トポロジ上又は地理上の近傍リンクとの共分散（相関関係））も合わせて登録しても良い。特に、実施の形態２では、一つのリンクに複数の誤差情報が登録されていても良い。
【００６６】
また、上記の場合、経路分析部１３は、誤差情報に基づいて各リンクの予測誤差が最大に積み上がる場合においても、移動時間を最小値とする経路を特定できる。但し、誤差情報が積み上がった状態で計算された経路については、信頼性（特定された経路において算された総移動時間で旅行できる確率）が算出され、これがユーザに提供されているのが良い。
【００６７】
（応用例）
本発明は、上述の実施の形態１及び２は、カーナビゲーションシステムだけでなく、他の用途にも利用できる。他の用途としては、例えば、通信ネットワークが挙げられる。具体的には、本発明は、通信装置（ルータなど）間のパケットの到達時間の予測値に基づき、通信ネットワークトポロジを時間拡大する。時間拡大トポロジ上で、最小コスト経路を計算することで、通信遅延が最小となるネットワーク経路が得られる。
【００６８】
この場合、交通状況予測部は、ネットワーク状況予測部として機能し、ネットワーク状況を予測する。また、推定部は、ネットワークにおけるパケットの転送速度又は到達時間を推定する。また、この態様によれば、ある地域において、装置間で生じる通信量が増大する場合、特に、時間帯又はイベントを要因とする通信ボトルネックが発生する場合を避けつつ、迂回距離最小の通信経路が確保できる。
【００６９】
また、本発明の他の用途としては、複数の交通手段を用いた場合の経路探索も挙げられる。本発明によれば、バス、鉄道、航空機など、公共の交通手段が複数存在するネットワーク上で、各手段によるターミナル間の移動時間を予測できるので、最も移動時間の短い移動経路を選択できる。加えて、本発明は、自動車の自動運転においても有用である。
【００７０】
更に、本発明の他の用途としては、サプライチェーンによる調達経路も挙げられる。例えば、原料の調達、部品の製造、部品の組立による最終製品の製造、製品の輸送等で構成される製造上のネットワークに、本発明を適用できる。この場合、本発明によれば、各チェーンでの所要時間を予測することで、原料の供給から製品が得られるまでの時間を予測できる。
【００７１】
（物理構成）
ここで、実施の形態１及び２におけるプログラムを実行することによって、経路分析装置１０を実現するコンピュータについて図１１を用いて説明する。図１１は、本発明の実施の形態１及び２における経路分析装置を実現するコンピュータの一例を示すブロック図である。
【００７２】
図１１に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。
【００７３】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【００７４】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００７５】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００７６】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記憶媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記憶媒体が挙げられる。
【００７７】
なお、本実施の形態における経路分析装置１０は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、経路分析装置１０は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【００７８】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記１５）によって表現することができるが、以下の記載に限定されるものではない。
【００７９】
（付記１）
出発地から目的地までの経路を分析するための装置であって、
複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、交通状況予測部と、
前記交通状況予測部による予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、推定部と、
前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、経路分析部と、
を備えていることを特徴とする経路分析装置。
【００８０】
（付記２）
前記経路分析部は、更に、前記複数の区間を用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
付記１に記載の経路分析装置。
【００８１】
（付記３）
前記交通状況予測部は、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記推定部は、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
付記１に記載の経路分析装置。
【００８２】
（付記４）
出発地から目的地までの経路を分析するための方法であって、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を備えていることを特徴とする経路分析方法。
【００８３】
（付記５）
前記（ｃ）のステップにおいて、更に、前記複数の区間を用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
付記４に記載の経路分析方法。
【００８４】
（付記６）
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
付記４に記載の経路分析方法。
【００８５】
（付記７）
コンピュータによって、出発地から目的地までの経路を分析するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【００８６】
（付記８）
前記（ｃ）のステップにおいて、更に、前記複数の区間を用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
付記７に記載のコンピュータ読み取り可能な記録媒体。
【００８７】
（付記９）
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
付記７に記載のコンピュータ読み取り可能な記録媒体。
【００８８】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８９】
この出願は、２０１６年１月２８日に出願された米国出願６２／２８８０４４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００９０】
以上のように、本発明によれば、目的地から出発地までの最短の移動時間を推定することができる。本発明は、特にカーナビゲーションシステムに有用である。
【符号の説明】
【００９１】
１０  経路分析装置
１１  交通状況予測部
１２  推定部
１３  経路分析部
１４  記憶部
１５  交通状況
２０  交通管理システム
２１  道路情報データベース
２２  交通情報データベース
２３  路側センサ
２４  車載端末
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2017130428.tif 000003
【図２】
2017130428.tif 000004
【図３】
2017130428.tif 000005
【図４】
2017130428.tif 000006
【図５】
2017130428.tif 000007
【図６】
2017130428.tif 000008
【図７】
2017130428.tif 000009
【図８】
2017130428.tif 000010
【図９】
2017130428.tif 000011
【図１０】
2017130428.tif 000012
【図１１】
2017130428.tif 000013
【手続補正書】
【提出日】平成29年6月5日(2017.6.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を分析するための装置であって、
複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、交通状況予測部と、
前記交通状況予測部による予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、推定部と、
前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、経路分析部と、
を備えていることを特徴とする経路分析装置。
【請求項２】
前記推定部が、
現時点における前記複数の区間それぞれにおける交通状況を取得し、前記複数の将来時間それぞれ毎に予測された、前記複数の区間それぞれにおける交通状況を用いて、
現時点及び前記複数の将来時間それぞれ毎に、前記複数の区間それぞれがノード間を結ぶリンクとなる空間ネットワークトポロジを作成し、更に、
前記複数の将来時間それぞれ毎に各ノードを設定した時間拡大トポロジ上において、作成した前記空間ネットワークトポロジそれぞれを展開して、各ノードとそれに接続可能な別のノードとを対応する前記交通状況に応じた長さのリンクで接続し、
展開後の前記時間拡大トポロジにおける各リンクを用いて、前記複数の区間それぞれの現時点からの経過時間に応じた移動時間を推定し、
前記経路分析部が、展開後の前記時間拡大トポロジを用いて推定された各移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、
請求項１に記載の経路分析装置。
【請求項３】
前記経路分析部は、更に、展開後の前記時間拡大トポロジを用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項２に記載の経路分析装置。
【請求項４】
前記交通状況予測部は、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記推定部は、展開後の前記時間拡大トポロジのリンクそれぞれ毎に、未到達距離が存在するかどうかを判定し、前記未到達距離が存在する場合は、前記未到達距離を求め、当該リンクに対応する区間について予測された前記速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を用いて、当該リンクに対応する区間の前記移動時間を推定する、
請求項２または３に記載の経路分析装置。
【請求項５】
出発地から目的地までの経路を分析するための方法であって、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を備えていることを特徴とする経路分析方法。
【請求項６】
前記（ｂ）のステップにおいて、
現時点における前記複数の区間それぞれにおける交通状況を取得し、前記複数の将来時間それぞれ毎に予測された、前記複数の区間それぞれにおける交通状況を用いて、
現時点及び前記複数の将来時間それぞれ毎に、前記複数の区間それぞれがノード間を結ぶリンクとなる空間ネットワークトポロジを作成し、更に、
前記複数の将来時間それぞれ毎に各ノードを設定した時間拡大トポロジ上において、作成した前記空間ネットワークトポロジそれぞれを展開して、各ノードとそれに接続可能な別のノードとを対応する前記交通状況に応じた長さのリンクで接続し、
展開後の前記時間拡大トポロジにおける各リンクを用いて、前記複数の区間それぞれの現時点からの前記経過時間に応じた移動時間を推定し、
前記（ｃ）のステップにおいて、展開後の前記時間拡大トポロジを用いて推定された各移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、
請求項５に記載の経路分析方法。
【請求項７】
前記（ｃ）のステップにおいて、更に、展開後の前記時間拡大トポロジを用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項６に記載の経路分析方法。
【請求項８】
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、展開後の前記時間拡大トポロジのリンクそれぞれ毎に、未到達距離が存在するかどうかを判定し、前記未到達距離が存在する場合は、前記未到達距離を求め、当該リンクに対応する区間について予測された前記速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を用いて、当該リンクに対応する区間の前記移動時間を推定する、
請求項６または７に記載の経路分析方法。
【請求項９】
コンピュータによって、出発地から目的地までの経路を分析するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【請求項１０】
前記（ｂ）のステップにおいて、現時点における前記複数の区間それぞれにおける交通状況を取得し、前記複数の将来時間それぞれ毎に予測された、前記複数の区間それぞれにおける交通状況を用いて、
現時点及び前記複数の将来時間それぞれ毎に、前記複数の区間それぞれがノード間を結ぶリンクとなる空間ネットワークトポロジを作成し、更に、
前記複数の将来時間それぞれ毎に各ノードを設定した時間拡大トポロジ上において、作成した前記空間ネットワークトポロジそれぞれを展開して、各ノードとそれに接続可能な別のノードとを対応する前記交通状況に応じた長さのリンクで接続し、
展開後の前記時間拡大トポロジにおける各リンクを用いて、前記複数の区間それぞれの現時点からの前記経過時間に応じた移動時間を推定し、
前記（ｃ）のステップにおいて、展開後の前記時間拡大トポロジを用いて推定された各移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、
請求項９に記載のコンピュータ読み取り可能な記録媒体。
【請求項１１】
前記（ｃ）のステップにおいて、更に、展開後の前記時間拡大トポロジを用いて、前記現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項１０に記載のコンピュータ読み取り可能な記録媒体。
【請求項１２】
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、展開後の前記時間拡大トポロジのリンクそれぞれ毎に、未到達距離が存在するかどうかを判定し、前記未到達距離が存在する場合は、前記未到達距離を求め、当該リンクに対応する区間について予測された前記速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を用いて、当該リンクに対応する区間の前記移動時間を推定する、
請求項１０または１１に記載のコンピュータ読み取り可能な記録媒体。
【手続補正書】
【提出日】平成30年7月27日(2018.7.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を分析するための装置であって、
複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、交通状況予測部と、
前記交通状況予測部による予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、推定部と、
前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、経路分析部と、
を備えていることを特徴とする経路分析装置。
【請求項２】
前記推定部が、
現時点における前記複数の区間それぞれにおける交通状況を取得し、前記複数の将来時間それぞれ毎に予測された、前記複数の区間それぞれにおける交通状況を用いて、
現時点及び前記複数の将来時間それぞれ毎に、前記複数の区間それぞれがノード間を結ぶリンクとなる空間ネットワークトポロジを作成し、更に、
前記複数の将来時間それぞれ毎に各ノードを設定した時間拡大トポロジ上において、作成した前記空間ネットワークトポロジそれぞれを展開して、各ノードとそれに接続可能な別のノードとを対応する前記交通状況に応じた長さのリンクで接続し、
展開後の前記時間拡大トポロジにおける各リンクを用いて、前記複数の区間それぞれの現時点からの経過時間に応じた移動時間を推定し、
前記経路分析部が、展開後の前記時間拡大トポロジを用いて推定された各移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、
請求項１に記載の経路分析装置。
【請求項３】
前記経路分析部は、更に、展開後の前記時間拡大トポロジを用いて、現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
請求項２に記載の経路分析装置。
【請求項４】
前記交通状況予測部は、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記推定部は、展開後の前記時間拡大トポロジのリンクそれぞれ毎に、未到達距離が存在するかどうかを判定し、前記未到達距離が存在する場合は、前記未到達距離を求め、当該リンクに対応する区間について予測された前記速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を用いて、当該リンクに対応する区間の前記移動時間を推定する、
請求項２または３に記載の経路分析装置。
【請求項５】
出発地から目的地までの経路を分析するための方法であって、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を備えていることを特徴とする経路分析方法。
【請求項６】
前記（ｂ）のステップにおいて、
現時点における前記複数の区間それぞれにおける交通状況を取得し、前記複数の将来時間それぞれ毎に予測された、前記複数の区間それぞれにおける交通状況を用いて、
現時点及び前記複数の将来時間それぞれ毎に、前記複数の区間それぞれがノード間を結ぶリンクとなる空間ネットワークトポロジを作成し、更に、
前記複数の将来時間それぞれ毎に各ノードを設定した時間拡大トポロジ上において、作成した前記空間ネットワークトポロジそれぞれを展開して、各ノードとそれに接続可能な別のノードとを対応する前記交通状況に応じた長さのリンクで接続し、
展開後の前記時間拡大トポロジにおける各リンクを用いて、前記複数の区間それぞれの現時点からの前記経過時間に応じた移動時間を推定し、
前記（ｃ）のステップにおいて、展開後の前記時間拡大トポロジを用いて推定された各移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、
請求項５に記載の経路分析方法。
【請求項７】
前記（ｃ）のステップにおいて、更に、展開後の前記時間拡大トポロジを用いて、現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、請求項６に記載の経路分析方法。
【請求項８】
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、展開後の前記時間拡大トポロジのリンクそれぞれ毎に、未到達距離が存在するかどうかを判定し、前記未到達距離が存在する場合は、前記未到達距離を求め、当該リンクに対応する区間について予測された前記速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を用いて、当該リンクに対応する区間の前記移動時間を推定する、
請求項６または７に記載の経路分析方法。
【請求項９】
コンピュータによって、出発地から目的地までの経路を分析するためのプログラムであって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させる、プログラム。
【請求項１０】
前記（ｂ）のステップにおいて、現時点における前記複数の区間それぞれにおける交通状況を取得し、前記複数の将来時間それぞれ毎に予測された、前記複数の区間それぞれにおける交通状況を用いて、
現時点及び前記複数の将来時間それぞれ毎に、前記複数の区間それぞれがノード間を結ぶリンクとなる空間ネットワークトポロジを作成し、更に、
前記複数の将来時間それぞれ毎に各ノードを設定した時間拡大トポロジ上において、作成した前記空間ネットワークトポロジそれぞれを展開して、各ノードとそれに接続可能な別のノードとを対応する前記交通状況に応じた長さのリンクで接続し、
展開後の前記時間拡大トポロジにおける各リンクを用いて、前記複数の区間それぞれの現時点からの前記経過時間に応じた移動時間を推定し、
前記（ｃ）のステップにおいて、展開後の前記時間拡大トポロジを用いて推定された各移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、
請求項９に記載のプログラム。
【請求項１１】
前記（ｃ）のステップにおいて、更に、展開後の前記時間拡大トポロジを用いて、現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、請求項１０に記載のプログラム。
【請求項１２】
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、展開後の前記時間拡大トポロジのリンクそれぞれ毎に、未到達距離が存在するかどうかを判定し、前記未到達距離が存在する場合は、前記未到達距離を求め、当該リンクに対応する区間について予測された前記速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を用いて、当該リンクに対応する区間の前記移動時間を推定する、
請求項１０または１１に記載のプログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、最適な経路又は移動時間を予測するための、経路分析装置、経路分析方法
、及びこれらを実現するためのプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
本発明の目的の一例は、上記問題を解消し、目的地から出発地までの最短の移動時間を推定し得る、経路分析装置、経路分析方法、及びプログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、コンピュータによって、出発地から目的地までの経路を分析するためのプログラムであって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させることを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
次に、推定部１２は、図４に示すように、各空間ネットワークトポロジを構成する各ノードを、将来時間毎に、時間拡大トポロジに展開する。そして、推定部１２は、各空間ネットワークトポロジに基づいて、時間拡大トポロジにおいて、各ノードから、これに連結可能なノードへと移動時間に応じた長さでリンクを接続する。例えば、現在の地点が地点Ａであるとすると、経過時間が０の場合、地点Ａが連結可能なノードは地点Ｂと地点Ｃとであり、それぞれへの移動時間は共に０．５ｈであるので、現在の地点Ａは０．５時間後の地点Ｂ及びＣにリンクで接続される。時間拡大トポロジの構築により、各区間において、経過時間に応じた移動時間が推定されたことになる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
次に、推定部１２は、ｔの値が最大値となっているかどうかを判定し（ステップＢ１０）、最大値となっていない場合は、ｔの値に△ｔを加算し（ステップＢ１１）、その後、再度、ステップＢ５を実行する。一方、最大値となっている場合は、推定部１２は、全てのリンクについて処理が終了しているかどうかを判定する（ステップＢ１２）。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
以下、実施の形態２との相違点について図９及び図１０を用いて具体的に説明する。図９は、本発明の実施の形態２で実行される移動時間の推定処理を具体的に説明する図である。図１０は、本発明の実施の形態２で行なわれる計算処理を説明する図である。また、以下の説明では適宜図１及び図２を参照すると共に、これらの図で用いた符号も引用する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
また、上記の場合、経路分析部１３は、誤差情報に基づいて各リンクの予測誤差が最大に積み上がる場合においても、移動時間を最小値とする経路を特定できる。但し、誤差情報が積み上がった状態で計算された経路については、信頼性（特定された経路において算出された総移動時間で旅行できる確率）が算出され、これがユーザに提供されているのが良い。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００７８
【補正方法】変更
【補正の内容】
【００７８】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記９）によって表現することができるが、以下の記載に限定されるものではない。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
（付記２）
前記経路分析部は、更に、前記複数の区間を用いて、現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
付記１に記載の経路分析装置。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００８３
【補正方法】変更
【補正の内容】
【００８３】
（付記５）
前記（ｃ）のステップにおいて、更に、前記複数の区間を用いて、現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
付記４に記載の経路分析方法。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００８５
【補正方法】変更
【補正の内容】
【００８５】
（付記７）
コンピュータによって、出発地から目的地までの経路を分析するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）複数の将来時間それぞれ毎に、前記出発地から前記目的地までに存在する複数の区間それぞれにおける交通状況を予測する、ステップと、
（ｂ）前記（ａ）のステップで予測が行なわれた時点からの経過時間に応じて、前記将来時間毎に予測された前記交通状況のいずれかを選択し、選択した前記交通状況を用いて、前記複数の区間それぞれの前記経過時間に応じた移動時間を推定する、ステップと、
（ｃ）前記複数の区間について推定された前記移動時間を用いて、前記出発地から前記目的地までの移動時間の最小値を算出する、ステップと、
を実行させる、プログラム。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
（付記８）
前記（ｃ）のステップにおいて、更に、前記複数の区間を用いて、現在の地点から前記目的地までの経路を、前記移動時間が前記最小値となるように特定する、
付記７に記載のプログラム。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
（付記９）
前記（ａ）のステップにおいて、前記複数の将来時間を一定の間隔毎に設定し、複数の将来時間それぞれ毎に、前記交通状況として、前記経路を構成する複数の区間それぞれにおける速度を予測し、
前記（ｂ）のステップにおいて、前記交通状況のいずれかを選択した後に、前記複数の区間それぞれ毎に、未到達距離を求め、選択した前記交通状況に含まれる当該区間の速度を用いて、求めた未到達距離を完遂するのにかかる時間を算出し、算出した時間を当該区間の前記移動時間として推定する、
付記７に記載のプログラム。
【手続補正１６】
【補正対象書類名】図面
【補正対象項目名】図４
【補正方法】変更
【補正の内容】
【図４】
2017130428.tif 000014
【手続補正１７】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2017130428.tif 000015
【手続補正１８】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2017130428.tif 000016
【国際調査報告】
2017130428.tif 000017
2017130428.tif 000018