車両走行位置データ処理方法及び装置
【課題】走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定する。
【解決手段】過去の走行実績から算出される各道路リンクの正規化走行頻度（＝頻度／リンクの長さ）に基づき、各リンクについて車両走行の蓋然性を表す値を算出し、２地点間で最も蓋然性が高いリンクの組み合わせである走行経路を特定する。すなわち、走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定することができる。
【解決手段】過去の走行実績から算出される各道路リンクの正規化走行頻度（＝頻度／リンクの長さ）に基づき、各リンクについて車両走行の蓋然性を表す値を算出し、２地点間で最も蓋然性が高いリンクの組み合わせである走行経路を特定する。すなわち、走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、走行中の車両で計測される位置情報を解析する技術に関する。
【背景技術】
【０００２】
例えば、経路案内を行う車両用経路案内装置において、使用者の走行状況を反映した目的地経路の設定を行う技術が存在している。具体的には、車両が走行した走行道路のうち利用頻度が所定値以上となる走行道路のデータを自動的に記憶しておき、経路対象道路のデータと記憶しておいた走行道路のデータを用いて出発地から目的地に至る目的地経路を設定する。また、現在地に最も近いリンク上の位置を出発地（経路計算上の開始点）とし、設定された目的地（以下、設定目的地という）に最も近いリンク上の位置を目的地（経路計算上の終了点）とし、出発地から目的地までの経路をダイクストラ法を用いたコスト計算により設定する。すなわち、出発地から目的地までの各リンクでの経路コストを例えば次の式を用いて計算する。経路コスト＝リンク長×道路幅係数×道路種別係数。ここで、リンク長はノード間の距離であり、道路幅係数とは道路幅の大きさに対して設定される係数であり、道路種別係数とは、有料道路等の道路種別に応じて設定される係数である。但し、この技術は、経路探索の一つであり、過去の離散的な走行位置から当該走行位置間の経路を同定する技術ではない。
【０００３】
また、よりユーザの嗜好に合った走行経路を推奨することができるナビゲーション装置も存在する。具体的には、ナビゲーション装置は、複数の領域に分けられた地図に関するデータを有する地図データ格納部と、目的地とする領域のエリアＩＤ毎にそれぞれのリンクの走行回数を格納する走行回数データ格納部とを有し、車両が走行したリンクの情報を順次記録し、エンジン始動時に、現在位置が含まれる領域に応じて、エリアＩＤ毎のリンクの走行回数を更新する。そして、ナビゲーション装置は、目的地が設定された場合に、設定された目的地が含まれる地図上の領域のエリアＩＤに対応する走行回数を用いて、それぞれのリンクデータのコストを修正し、修正したコストを用いて、目的地までの経路を探索して出力する。この技術も、過去の離散的な走行位置から当該走行位置間の経路を同定する技術ではない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３４０６１４４号公報
【特許文献２】特開２００８−９６２７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上で述べたように、従来技術では、道路に対応するリンクのコストをその目的に適切な属性に応じて重み付けして、これから走行しようとする経路の探索を実施するものである。
【０００６】
しかしながら、走行中の車両で計測される走行位置を離散的にしか得られない場合に、当該走行位置間の過去の走行経路を同定するようなことはできない。
【０００７】
従って、本技術の目的は、走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定するための技術を提供することである。
【課題を解決するための手段】
【０００８】
本車両走行位置データ処理方法は、計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、計測時刻と車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、読み出された車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおけるノード及びリンクの位置データ及びリンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている複数のリンクのうち車両走行位置データ・レコードの車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、複数のリンクの各々について、頻度カウンタの値を道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、正規化走行頻度データ格納部に格納されている各リンクの正規化走行頻度の値に基づき、走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップとを含む。
【発明の効果】
【０００９】
走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、本技術の実施の形態に係るシステム概要図である。
【図２】図２は、道路リンクとノードの関係を示す模式図である。
【図３】図３は、道路地図ネットワーク情報格納部に格納されるデータの一例を示す図である。
【図４】図４は、メインの処理フローを示す図である。
【図５】図５は、走行位置情報格納部に格納されるデータの一例を示す図である。
【図６】図６は、正規化走行頻度情報生成処理の処理フローを示す図である。
【図７】図７は、道路リンク毎の走行頻度を表すデータの一例を示す図である。
【図８】図８は、道路リンク毎の走行頻度を模式的に示した図である。
【図９】図９は、正規化走行頻度情報格納部に格納されるデータの一例を示す図である。
【図１０】図１０は、車両別走行経路算出処理の処理フローを示す図である。
【図１１】図１１は、経路同定を行う区間を説明するための図である。
【図１２】図１２は、第１の走行経路算出処理の説明における道路ネットワークの一例を示す図である。
【図１３】図１３は、第２の走行経路算出処理の説明における道路ネットワークの一例を示す図である。
【図１４】図１４は、車両別走行リンクテーブルの一例を示す図である。
【図１５】図１５は、メインの処理フローを示す図である。
【図１６】図１６は、車両及び道路リンク別走行時間算出処理の処理フローを示す図である。
【図１７】図１７は、道路交通情報ＤＢに格納されるデータの一例を示す図である。
【図１８】図１８は、リンク別平均走行時間算出処理の処理フローを示す図である。
【図１９】図１９は、道路交通情報ＤＢに格納されるデータの一例を示す図である。
【図２０】図２０は、第１の走行経路算出処理の処理フローを示す図である。
【図２１】図２１は、第１経路探索処理の処理フローを示す図である。
【図２２】図２２は、第２の走行経路算出処理の処理フローを示す図である。
【図２３】図２３は、第２経路探索処理の処理フローを示す図である。
【図２４】図２４は、第２経路探索処理を説明するための図である。
【図２５】図２５は、探索テーブルの一例を示す図である。
【図２６】図２６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１１】
［本実施の形態の概要］
本実施の形態では、例えばＧＰＳ（Global Positioning System）端末及び無線通信機を車両に搭載する複数のプローブ車両を用意する。そして、複数のプローブ車両は、走行中、一定の時間間隔（例えば数十秒から数分間）又は一定の走行距離（数百メートル間隔乃至数キロメートル間隔）毎に、ＧＰＳ端末により走行位置を計測し、無線通信機によって走行位置データを以下で述べるプローブ道路交通情報システムに送信する。なお、送信間隔が短いほど、以下で述べる処理の精度は向上し、極端な場合にはリアルタイムで送信するようなことも考えられるが、プローブ車両の数、通信コストや無線通信負荷の問題からして、ある程度の間隔毎に走行位置データを送信するのが現実的である。そうすると、走行位置データに含まれる計測位置間をプローブ車両がどのような経路で走行したかについては一義的には決まらない場合が生じ（得）るということになる。
【００１２】
これに対してプローブ道路交通情報システムでは、複数のプローブ車両の走行位置データを受信して蓄積する。そして、蓄積された走行位置データを、既存の道路地図ネットワークにおける道路リンク（以下では、単にリンクと述べる場合もある）に投影して、各道路リンクについてプローブ車両が走行した頻度を計数する。そして、道路リンクの長さで頻度を除することによって正規化し、正規化された頻度の値を当該道路リンクを走行する蓋然性（又は利用しやすさ）を表すデータとして用いて、同一プローブ車両の２つの走行位置間の経路として最も可能性の高い経路を求める。これが、経路同定の結果となる。
【００１３】
さらに、経路が同定されれば、経路上の各リンクについて所要走行時間を算出することができ、さらにリンク毎の平均走行時間も算出できる。このようにすれば、どこで渋滞が発生しているのか、どこが空いている道なのかを特定することも可能となる。
【００１４】
［本実施の形態の具体的な構成］
図１に本実施の形態におけるシステム概要を示す。プローブ道路交通情報システム１００は、上で述べたようにＧＰＳ端末及び無線通信機を有する複数のプローブ車両から無線を含む通信網を介して走行位置情報を受信するプローブ車両位置収集部１０１と、プローブ車両位置収集部１０１によって取得された走行位置情報を格納する走行位置情報格納部１０２と、複数のノードと当該ノード間のリンクによって表される道路地図ネットワークのデータを格納する道路地図ネットワーク情報格納部１０５と、走行位置情報格納部１０２と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて道路リンク毎に走行頻度を計算する道路リンク別走行頻度算出部１０３と、道路リンク別走行頻度算出部１０３の処理結果を格納する道路リンク別走行頻度情報格納部１０４と、道路リンク別走行頻度情報格納部１０４と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて道路リンク毎に正規化走行頻度を算出する正規化走行頻度算出部１０６と、正規化走行頻度算出部１０６の処理結果を格納する正規化走行頻度情報格納部１０７と、走行位置情報格納部１０２と正規化走行頻度情報格納部１０７と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて車両毎に走行経路を同定するための経路計算を実施する車両別走行経路算出部１０９と、車両別走行経路算出部１０９の処理結果を格納する車両別走行リンク情報格納部１１０と、車両別走行リンク情報格納部１１０と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて道路リンク毎に平均走行時間を算出する道路リンク別平均走行時間算出部１１１と、道路リンク別平均走行時間算出部１１１の処理結果を格納する道路交通情報ＤＢ１１２と、道路地図ネットワーク情報格納部１０５と道路交通情報ＤＢ１１２や車両別走行リンク情報格納部１１０に格納されているデータを用いて出力データを生成して出力する出力部１１３と、道路リンク別走行頻度算出部１０３及び車両別走行経路算出部１０９に対して必要な入力データをユーザから受け取り出力する入力部１０８とを有する。
【００１５】
道路地図ネットワークは、図２に模式的に示すように、例えば交差点（交差点でない位置にノードが設けられる場合もある）に対応する複数のノードｎ１００１乃至ｎ１００５を、道路に対応する道路リンク１０００乃至１００７で接続するようなネットワークである。本実施の形態では、一方通行でない場合には基本的には互いに逆方向の２本のリンクで、ノード間を接続するものとする。但し、場合によっては双方向で通行できる場合でも１本のリンクで繋がれている場合もある。
【００１６】
このような道路ネットワークを表現するためのデータとして、道路地図ネットワーク情報格納部１０５には、図３に示すようなデータが格納される。図３の例では、道路リンク番号に対応付けられて、道路種別と、リンク距離（リンク長）と、位置（例えば始点位置−終点位置）とが登録されるようになっている。なお、位置については、始点ノード番号及び終点ノード番号で特定しておき、ノード番号と位置の関係を保持する別のテーブルを用いて具体的な位置を特定するようにしても良い。
【００１７】
次に、図４乃至図１９を用いて、プローブ道路交通情報システム１００の動作について説明する。
【００１８】
上でも述べたが、プローブ車両は、走行位置情報を、所定時間間隔又は所定走行距離毎に、無線を含む通信網を介してプローブ道路交通情報システム１００に送信する。この走行位置情報は、例えば、車両種別、車両ＩＤ、取得日時、車両位置、移動方向、移動速度、状態（例えばタクシーであれば顧客が乗車中であるか否か、トラックであれば顧客の荷物を積載中であるか否かなど。）などのデータを含む。
【００１９】
プローブ道路交通情報システム１００のプローブ車両位置収集部１０１は、全てのプローブ車両から走行位置情報を随時受信し、走行位置情報格納部１０２に格納する（図４：ステップＳ１）。なお、このステップは、説明の便宜上最初に行う処理として説明しているが、実際はこれ以降に述べる処理とは別スレッドで随時実施される。
【００２０】
例えば、図５に示すようなデータが、走行位置情報格納部１０２に格納される。図５の例では、車両種別、車両ＩＤ、日時、位置、移動方向、速度及び状態が登録されるようになっている。本実施の形態において以下の処理で用いられないデータもあるが、そのようなデータは本実施の形態以外の処理において用いられる場合もある。
【００２１】
そして、入力部１０８は、正規化走行頻度算出及び平均走行時間算出のためのデータ抽出範囲の指定をユーザに対して促し、ユーザからの入力を受け付ける（ステップＳ３）。
【００２２】
正規化走行頻度は、以下で述べる正規化走行頻度算出部１０６で算出され且つ各リンクをプローブ車両が通過する可能性を表す数値（単位距離（単位長さ）あたりの走行頻度）である。そして、正規化走行頻度算出のためのデータ抽出範囲については、どのようなプローブ車両が通過する可能性をどのような時間／地域のデータをベースに算出するかを指定するために入力する。例えば、タクシーを含む一般車両が通過する可能性を直近１ヶ月間東京２３区内の範囲で算出するといった指定を行う。
【００２３】
また、平均走行時間は、プローブ車両が各道路リンクをどの程度の時間で通過しているかを表す数値である。平均走行時間算出のためのデータ抽出範囲は、どのようなプローブ車両がどのような時間／地域について走行した結果をベースに平均走行時間を算出するかを指定するために入力する。例えば、タクシーを含む一般車両が直近３０分間東京２３区内の範囲を走行した結果で平均走行時間を算出するといった指定を行う。
【００２４】
正規化走行頻度を基に平均走行時間を算出するので、正規化走行頻度算出のためのデータ抽出範囲と、平均走行時間算出のためのデータ抽出範囲とは、ある程度の関連性を有するものとなる。すなわち、同様の地域についてデータ抽出範囲を指定する必要があり、時間についても、例えば前者が金曜日の１４時から１５時というようなデータ抽出範囲であれば、後者は過去６ヶ月において平日の１４時から１５時というようなデータ抽出範囲とする。
【００２５】
なお、ある程度ルールを決めてしまえば、平均走行時間算出のためのデータ抽出範囲のみを入力するようにして、当該データ抽出範囲から自動的に正規化走行頻度算出のためのデータ抽出範囲を特定するようにしても良い。
【００２６】
また、これとは別に、天気のデータをも収集しておき、データ抽出範囲についても天気を指定するようにしても良い。
【００２７】
さらに、例えば３０分毎に３０分時間だけがシフトするが他の条件については同一のデータ抽出範囲について定期的に処理する場合には、平均走行時間算出のためのデータ抽出範囲についても自動的に生成するような構成を採用するようにしても良い。
【００２８】
入力部１０８は、正規化走行頻度算出のためのデータ抽出範囲のデータについては道路リンク別走行頻度算出部１０３に出力する。平均走行時間算出のためのデータ抽出範囲のデータについては車両別走行経路算出部１０９に出力する。
【００２９】
次に、道路リンク別走行頻度算出部１０３は、正規化走行頻度算出のためのデータ抽出範囲に応じて、走行位置情報格納部１０２から該当する走行位置情報を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ５）。また、車両別走行経路算出部１０９も、平均走行時間算出のためのデータ抽出範囲に応じて、走行位置情報格納部１０２から該当する走行位置情報を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ７）。
【００３０】
そして、道路リンク別走行頻度算出部１０３等は、正規化走行頻度情報生成処理を実施する（ステップＳ９）。この正規化走行頻度情報生成処理については、図６乃至図９を用いて説明する。
【００３１】
まず、道路リンク別走行頻度算出部１０３は、正規化走行頻度算出のためのデータ抽出範囲に含まれる未処理の走行位置レコードを１つ特定する（図６：ステップＳ２１）。そして、周知のマップマッチングにより、道路地図ネットワーク情報格納部１０５に登録されている道路リンクのうち、特定された走行位置レコードの走行位置が対応付けられるリンクを特定し、当該リンクのカウントを１インクリメントする（ステップＳ２３）。ＧＰＳによる位置情報は必ずしも正確ではなく、走行位置が道路地図ネットワーク情報格納部１０５に登録されているいずれかの道路リンク上に常に載るわけではない。従って、道路リンクから離れていた場合、走行位置をどの道路リンクに対応付けるのかというのは、従来のカーナビゲーションシステムにおいても問題となっていた。このような問題を解決するためマップマッチングという手法が以前より用いられており、本実施の形態でもステップＳ２３で用いる。簡単に述べれば、走行位置から候補リンクに垂線を下ろした際に最も短い垂線が下ろされたリンクを選択するものである。但し、走行規制など他の補助的なデータを用いてリンクを選択する技術も存在しており、そのような技術を本ステップで用いるようにしても良い。
【００３２】
また、ステップＳ２３のカウント結果は、例えば道路リンク別走行頻度情報格納部１０４に格納される。この道路リンク別走行頻度情報格納部１０４に格納されるデータの一例を図７に示す。図７の例では、道路リンク番号毎に、走行頻度のカウンタが設けられている。ステップＳ２３で１つのリンクが特定されると、該当するリンク番号のカウンタの値が１インクリメントされる。
【００３３】
ステップＳ２３の処理結果を模式的に示すと図８のようなものになる。すなわち、各リンク（ノードである丸印の間の線）には、測定された走行位置に相当する点（矩形）がマッピングされており、各リンクにマッピングされた走行位置の数が、そのリンクの走行頻度ということになる。なお、図８の星マークは、以下で述べる車両別走行経路算出処理の対象となる、特定車両の計測位置の２点（始点及び終点）を示している。この２点間の経路を同定することになる。
【００３４】
そして、道路リンク別走行頻度算出部１０３は、正規化走行頻度算出のためのデータ抽出範囲に含まれる走行位置レコードを全て処理したか判断する（ステップＳ２５）。未処理の走行位置レコードが存在する場合にはステップＳ２１に戻る。
【００３５】
一方、正規化走行頻度算出のためのデータ抽出範囲に含まれる走行位置レコードを全て処理した場合には、正規化走行頻度算出部１０６の処理に移行する。
【００３６】
すなわち、正規化走行頻度算出部１０６は、道路リンク別走行頻度情報格納部１０４における未処理のリンクを１つ特定する（ステップＳ２７）。そして、該当レコードにおける頻度を、道路リンク番号に対応付けて道路地図ネットワーク情報格納部１０５に格納されているリンク距離で除することによって正規化走行頻度（すなわち、単位距離あたりの走行頻度）を算出し、正規化走行頻度情報格納部１０７に格納する（ステップＳ２９）。例えば、図９に示すようなデータが正規化走行頻度情報格納部１０７に格納される。図９の例では、道路リンク番号に対応付けて、正規化走行頻度が登録されるようになっている。なお、本実施の形態では単純に、走行頻度をリンク距離で除することによって正規化走行頻度を算出することとしているが、さらに他の情報を用いて正規化走行頻度を調整するようにしても良い。例えば、道路地図ネットワーク情報格納部１０５には、リンク毎に道路種別が登録されている。道路種別には、一般道、幹線、細街路のような種別が含まれ、例えば幹線の方が走行する可能性が高いものとして、例えば１以上の所定の係数を、正規化走行頻度に乗ずるようにしても良い。また、実際に速く走行できるリンクの方が利用可能性が高いので、過去の平均走行速度（例えば道路交通情報ＤＢ１１２に格納されているデータ）の高低により調整しても良い。
【００３７】
そして、正規化走行頻度算出部１０６は、道路リンク別走行頻度情報格納部１０４に登録されている全てのリンクについて処理したか判断する（ステップＳ３１）。未処理のリンクが存在する場合にはステップＳ２７に戻る。一方、全てのリンクについて処理した場合には、元の処理に戻る。
【００３８】
このような処理を実施することによって、各道路リンクについて比較可能な、プローブ車両が走行する可能性を表す評価値が算出されたことになる。
【００３９】
図４の処理の説明に戻って、車両別走行経路算出部１０９は、車両別走行経路算出処理を実施する（ステップＳ１１）。この車両別走行経路算出処理については、図１０乃至図１４を用いて説明する。なお、ステップＳ１１が終了すると処理は端子Ａを介して図１５の処理に移行する。
【００４０】
車両別走行経路算出部１０９は、平均走行時間算出のためのデータ抽出範囲に含まれる走行位置レコードを、車両毎且つ時間順にソートする（図１０：ステップＳ４１）。本実施の形態では、各車両について連続する２走行位置間の経路を同定する。しかしながら、データ抽出範囲で指定された時間内において、同一車両につき３以上の走行位置が特定される場合がある。以下の処理は、同一車両について、連続する２つの走行位置を１つずつずらしながら、それぞれの２走行位置間の経路を同定する。図１１に模式的に示すように、ＡからＣの順番で走行位置が得られた場合には、Ａ及びＢを第１セットとして最初に経路同定を実施し、次に、Ｂ及びＣを第２セットとして次に経路同定を実施する。
【００４１】
従って、車両別走行経路算出部１０９は、走行位置レコードのソート結果において未処理の車両を１つ特定する（ステップＳ４３）。そして、特定された車両についての走行位置レコードのうち未処理の連続レコードを時刻順に特定する（ステップＳ４５）。そして、特定された車両の特定された走行位置レコード及び道路地図ネットワーク情報格納部１０５に格納されているデータを用いて、走行経路算出処理を実施する（ステップＳ４７）。図８の例では、星印で示した始点から終点までの経路を算出する。本実施の形態では、図８で示した各リンクにおける正規化走行頻度の値に基づき、最も使用した可能性が高いと推定される経路上のリンクを特定する。走行経路算出処理の処理の詳細については後に詳述する。
【００４２】
ここでは２つの手法について、その概要を説明しておく。
【００４３】
［第１の走行経路算出処理］
図１２には、着目車両が、第１の時刻ｔ0から第２の時刻ｔ1の間に差し掛かっている地域付近の道路ネットワークを示している。着目車両が、時刻ｔ0に点Ｃ0（本実施の形態では、実際の測定位置ではなく、道路ネットワークにマッピングされているので「地点」とは呼ばず、「点」と呼ぶことにする）を通過し、時刻ｔ1に点Ｃ1を通過した（又は通過しつつある）ものとする。点Ｃ0と点Ｃ1の間の経路は、測定されていないので不明であり、以下のような考え方で経路同定を行う。
【００４４】
なお、図１２において、道路ネットワークにはノードＡ00乃至Ａ22が含まれており、リンクＢ00-01乃至Ｂ21-22も含まれている。リンク番号の付与の仕方は、例えば［発ノードのシリアル番号］−［着ノードのシリアル番号」となっている。また、図１２には示されていないが、リンクＢx-yの正規化走行頻度を、「ｂx-y」と表すものとする。
【００４５】
また、ノード間のリンクには上でも述べたように向きがあり、いずれかを「上り」とする場合には、逆方向を「下り」として特定できる。但し、図１２の例では、「上り」及び「下り」のいずれかのみを示している。ここでは、議論を単純化するため、図１２の矢印の向き（場所により、上り又は下りに対応）にのみ移動可能という前提で考える。
【００４６】
そして、本実施の形態では、ノードＡij上にいる（又はノードＡijを通過しつつある）場合に、その先は「ノードＡijを起点とするリンク」が到達している隣接ノードにしか移動できないものとする。例えば、ノードＡ11にいるとすると、その先はノードＡ12又はノードＡ21にしか移動できないものとする。すなわち、ノードＡ01及びＡ10へは移動できないものとする。
【００４７】
さらに、同じ仮定の下、（ノードＡ11から）ノードＡ12へ移動する可能性（場合によっては移動確率とも呼ぶ）Ｐ11-12は、「ｂ11-12／（ｂ11-12＋ｂ11-21）」であるものとする。すなわち、移動可能性のあるリンクＢ11-12及びＢ11-21の正規化走行頻度の総和に対するリンクＢ11-12についての正規化走行頻度の比率である。さらに、ノードＡ21へ移動する可能性Ｐ11-21は、「ｂ11-21／（ｂ11-12＋ｂ11-21）」であるものとする。すなわち、移動可能性のあるリンクＢ11-12及びＢ11-21の正規化走行頻度の総和に対するリンクＢ11-21についての正規化走行頻度の比率である。なお、ノード列で経路を特定しても良いが、以下で述べるように処理プロセスの最後の方でリンクに関わる値としてのリンクの平均走行速度を算出するので、リンク列で表している。但し、ノード列とリンク列とは道路地図ネットワーク情報格納部１０５のデータを用いれば容易に変換可能である。
【００４８】
なお、着目ノードＡ11から隣接ノードに繋がるリンクのいずれにおいても上で述べた正規化走行頻度ｂの値が０である場合には、Ａ11から先への移動は不可能となるため、これ以上の探索は行わない。
【００４９】
同様に、Ｃ0からＣ1までの多くの（又は全ての）リンクの正規化走行頻度ｂが０であり、ｂが０でないリンクのみを辿ってＣ0からＣ1に到達することが不可能である場合には、（本方式による）これらの点の間の経路同定は不可能であり、同定処理を終了するものとする。
【００５０】
そうすると、経路「リンクＢi0j0-i1j1（添字はｉ0ｊ0−ｉ1ｊ1を表す。以下同様とする。），Ｂi1j1-i2j2，．．．，Ｂi(n-1)j(n-1)-injn」上を移動する場合における経路選択可能性Ｐi0j0-i1j1-...-injnは、「可能性Ｐi0j0-i1j1・Ｐi1j1-i2j2・．．・Ｐi(n-1)j(n-1)-injn」で計算される。
【００５１】
例えば図１２で示した範囲を車両が走行する可能性のある範囲（この範囲については予め定められた妥当な範囲に設定する）であるとすると、図１２に示されているリンクであって上で述べたような引き返しやループを行わないという条件を満たすように選択した、点Ｃ0からＣ1までの連続リンク列で特定される複数の経路について、それぞれ経路選択可能性を算出する。そして最も経路選択可能性が大きな値となった経路を、本実施の形態における経路同定で特定された経路とする。
【００５２】
なお、具体的には、進行方向に点Ｃ0に隣接するノードＡ00から、進行方向とは逆方向に点Ｃ1に隣接するノードＡ22までの経路を見つけ出した後に、点Ｃ0が載っているリンクと、点Ｃ1が載っているリンクとを連結することによって、全体の経路が特定される。
【００５３】
このようにすれば、同じような時間などの条件において同じような種類のプローブ車両が通っていた可能性の最も高い経路を特定することができるようになる。
【００５４】
なお、上で述べた移動可能性Ｐの式については、各リンクについてそのリンクを走行する車両の平均速度がほぼ一定であるとみなした場合の式である。そもそも走行位置情報と共に、走行速度情報が採取でき、且つそのリンク毎の平均を求めることができる等の条件が成立し、且つリンク毎の車両の平均速度を考慮して、より正確に移動可能性Ｐの値を求める場合には、以下のような式を用いるものとする。（ｖi-jは、リンクＢi-jの平均速度である。）リンク毎の車両の平均速度については、例えば、道路交通情報ＤＢ１１２に格納されている過去のデータを用いればよい。
Ｐ11-12＝（ｂ11-12・ｖ11-12）／（ｂ11-12・ｖ11-12＋ｂ11-21・ｖ11-21）
Ｐ11-21＝（ｂ11-21・ｖ11-21）／（ｂ11-12・ｖ11-12＋ｂ11-21・ｖ11-21）
【００５５】
［第２の走行経路算出処理］
図１３には、着目車両が、第１の時刻ｔ1から第２の時刻ｔ2の間に差し掛かっている地域付近の道路ネットワークを示している。着目車両が、時刻ｔ1に点Ｃ1を通過し、時刻ｔ2に点Ｃ2を通過した（又は通過しつつある）ものとする。点Ｃ1と点Ｃ2の間の経路は、測定されていないので不明であり、以下のような考え方で経路同定を行う。
【００５６】
なお、図１３において、道路ネットワークにはノードＡ1乃至Ａ11が含まれており、リンクＢ1-2乃至Ｂ11-10も含まれている。リンク番号の付与の仕方は、例えば［発ノードのシリアル番号］−［着ノードのシリアル番号」となっている。また、図１３には示されていないが、リンクＢx-yの正規化走行頻度を、「ｂx-y」と表すものとする。
【００５７】
図１２とは異なり、ノード間に双方向のリンクが設定されている場合も考慮されている。
【００５８】
また、ノード間のリンクには上でも述べたように向きがあり、いずれかを「上り」とする場合には、逆方向を「下り」として特定できる。
【００５９】
そして、本実施の形態では、ノードＡi上にいる（又はノードＡiを通過しつつある）場合に、その先は「ノードＡiを起点とするリンク」が到達している隣接リンクにしか移動できないものとする。例えば、図１３におけるノードＡ5にいるとすると、その先はノードＡ2、Ａ4、Ａ6又はノードＡ9にしか移動できないものとする。
【００６０】
さらに、同じ仮定の下、ノードＡ5からノードＡ2、Ａ4、Ａ6及びＡ9へ移動する可能性（場合によっては移動確率とも呼ぶ）Ｐ5-2、Ｐ5-4、Ｐ5-6、Ｐ5-9は、それぞれ以下のように表される。
Ｐ5-2＝ｂ5-2／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
Ｐ5-4＝ｂ5-4／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
Ｐ5-6＝ｂ5-6／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
Ｐ5-9＝ｂ5-9／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
【００６１】
すなわち、移動可能性のあるリンクの正規化走行頻度の総和に対する注目リンクについての正規化走行頻度の比率である。
【００６２】
そうすると、経路「ノードＡi1，Ａi2，．．．，Ａin」上を移動する場合における経路選択可能性Ｐi1-i2-...-inは、「可能性Ｐi1-i2・Ｐi2-i3・．．・Ｐi(n-1)-in」で計算される。この経路選択可能性Ｐi1-i2-...-inが最大となる経路を、注目車両が実際に通過した経路とみなす。なお、ノード列で経路を特定しているが、リンク列で特定するようにしても良い。
【００６３】
また、例えばノードＡ5から隣接ノードに繋がるリンクのいずれにおいても、正規化走行頻度ｂ5-jが０である場合又は０に近いほど小さい場合には、Ａ5から先への移動は可能性が０ということで、それ以上経路同定を継続しない。
【００６４】
また、Ｃ1からＣ2までのリンクの正規化走行頻度が０又は０に近いほど小さく、現実的な経路長の範囲で経路同定を行うことができない状態、或いはそう見做せる状態であれば、（本方式による）経路同定処理を中止する。同様な考え方に基づき、Ｃ1からＣ2までのリンクの大部分の正規化走行頻度が０又は０に近いほど小さい場合に、（本方式による）経路同定処理を中止することもできる。
【００６５】
そして、既に通過しているノードを再度通過するような探索や、ループを構成するような探索については行わないものとする。但し、このような条件を満たしていれば、Ａ1、Ａ2、Ａ5と移動してきて、さらにＡ4、Ａ8、Ａ9、Ａ10というように、一見すると遠回りとなるような経路も考慮するものとする。
【００６６】
より具体的に経路選択可能性Ｐi1-i2-...-inが最大となる経路は、以下に述べる事項に従って得られる。
【００６７】
（ａ）図１３の各道路リンクＢi-jに対して、属性値Ｑi-j＝１／Ｐi-jを算出する。第１の走行経路算出処理の移動可能性の逆数を属性値として用いるものである。
【００６８】
（ｂ）点Ｃ1から点Ｃ2までの経路のうち、自明である点Ｃ1からノードＡ1まで、ノードＡ11から点Ｃ2までを除き、ノードＡ1からＡ11までの経路を探索する。
【００６９】
（ｃ）この際、Ｑi1-i2-...-in＝Ｑi1-i2・Ｑi2-i3・．．・Ｑi(n-1)-inが最小となるような経路を特定する。
【００７０】
（ｄ）そのため、Ｆ（ｉj）を、出発ノードＡi1（ｉ1＝１）からＡijに至る経路のうちＱi1-i2-...-ijが最小の値を取る経路におけるＱi1-i2-...-ijの値であるとする。なお、Ｆ（ｉ1）＝Ｆ（１）＝１であるとする。
【００７１】
（ｅ）そして、Ａi1（＝Ａ1）からはじめて、
【００７２】
【数１】
Ｆ（ｉ’1），Ｆ（ｉ’2），．．．，Ｆ（ｉ’m）（ここでｉ’1＝ｉ1）を、この順に、Ａin（＝Ａ11）まで計算してゆく。（ｉ’m＝ｉnである。ｉ’mは初めから知ることはできない。Ｆ（ｉ’1），Ｆ（ｉ’2），．．．，Ｆ（ｉ’n）を順に求めてゆき、ｉnに一致するｉ’mに到達した時点で、ｉ’mを知ることができる。）ここでＦ（ｉ’1）≦Ｆ（ｉ’2）≦．．．≦Ｆ（ｉ’n）である。
【００７３】
Ｆ（ｉ’1），Ｆ（ｉ’2），．．．，Ｆ（ｉ’n）は、詳細には、次のように求めてゆく。まずＦ（ｉ’1）（すなわちＦ（ｉ1））は、上記のようにＦ（ｉ1）＝Ｆ（１）＝１であることから１である。（すなわちＦ（ｉ’1）＝Ｆ（ｉ1）＝１である。）次にＦ（ｉ’2）を求めるが、この段階では、ノードＡi'1（ｉ’1は式（１）のｉ’jに対応）に隣接するノード（すなわち１つのリンクを介してＡi'1につながるノード）の中で、式（１）のＦ（ｉ’k）の値が最小となるようなノードＡi'k（「式（１）のＦ（ｉ’k）の値が最小となるようなｉ’k」に対応する（そのようなｉ’kを添字として持つ）ノードＡi'k）を選び、それをＡi'2とする。この時、Ａi'1からＡi'2に至る経路のうち、Ｑi'1-i'2が最小となる経路におけるＱi'1-i'2の値がＦ（ｉ’2）である。（ここに述べたことから分かるように、Ａi'2とＦ（ｉ’2）は、相互に対応するものと捉えることができる。）次にＦ（ｉ’3）を求めるが、この段階では、既に到達したノード（ここではＡi'1、Ａi'2（ｉ’1、ｉ’2は、式（１）のｉ’jに対応））のいずれかに隣接するノード（但し未到達のノード）の中で、式（１）のＦ（ｉ’k）の値が最小となるようなノードＡi'k（「式（１）のＦ（ｉ’k）の値が最小となるようなｉ’k」に対応するノードＡｉ’k）を選び、それをＡi'3とする。この時、Ａi'1からＡi'3に至る経路のうち、Ｑi'1-...-i'3が最小となる経路におけるＱi'1-...-i'3の値がＦ（ｉ’3）である。（Ａi'3とＦ（ｉ’3）は、相互に対応するものと捉えることができる。）
【００７４】
以下、順次、既に到達したノードのいずれかに隣接するノード（但し未到達のノード）の中で、式（１）のＦ（ｉ’k）の値が最小となるようなノードＡi'k（「式（１）のＦ（ｉ’k）の値が最小となるようなｉ’k」に対応するノードＡi'k）を求めてゆき、それに対応するＦ（ｉ’k）を求めてゆく。以上のことは、最終到達ノード（すなわちＡin）に到達するまで続ける。
【００７５】
（ｆ）その結果、Ｑi1-i2-...-in（ｉ1＝１，ｉｎ＝１１）が最小になる経路を特定する。Ｑi1-i2-...-inの添字ｉ1，ｉ2，．．．，ｉnの値は、（ｅ）で最終的に求めたＱi'1-...i'mの添字ｉ’1，．．．，ｉ’mを参照して知る。「ｉ1，ｉ2，．．．，ｉn」と「ｉ’1，．．．，ｉ’m」において、（左から数えて）同じ位置にあるものの値同士は等しい。
【００７６】
（ｇ）この経路の前に点Ｃ1からノードＡ1の経路を、後にノードＡ11から点Ｃ2までの経路を連結すれば、点Ｃ1から求めるべき点Ｃ2までの経路同定の結果となる。
【００７７】
以上のような処理を実施する場合においても、過去のプローブ車両の走行実績から今回のプローブ車両も採用した可能性が高い経路を同定することができるようになる。
【００７８】
なお、上で述べた移動可能性Ｐの式については、各リンクについてそのリンクを走行する車両の平均速度が一定であるとみなした場合の式である。そもそも、走行位置情報と共に、走行速度情報が採取でき、且つそのリンク毎の平均を求めることができる等の条件が成立して、リンク毎の車両の平均速度を考慮できる場合には、以下のような式を用いるものとする。リンク毎の車両の平均速度については、例えば、道路交通情報ＤＢ１１２に格納されている過去のデータを用いればよい。なお、リンクＢi-jの平均速度をｖi-jとすると、例えばＰ5-2、Ｐ5-4、Ｐ5-6、Ｐ5-9は以下のように表される。
Ｐ5-2＝(ｂ5-2・ｖ5-2)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
Ｐ5-4＝(ｂ5-4・ｖ5-4)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
Ｐ5-6＝(ｂ5-6・ｖ5-6)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
Ｐ5-9＝(ｂ5-9・ｖ5-9)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
【００７９】
この処理の結果、例えば図１４に示すような車両別走行リンクテーブルが、車両別走行リンク情報格納部１１０に格納されるようになる。図１４の例では、車両ＩＤと、処理に係る２走行位置レコードのうち時間的に先の走行位置レコードに含まれる時刻である発時刻と、処理に係る２走行位置レコードのうち時間的に後の走行位置レコードに含まれる時刻である着時刻と、経路同定で特定されたリンク列（リンク１乃至３．．．）とが登録されるようになっている。なお、リンク列のうち最初と最後のリンクについては、注目している車両はそれらのリンク個々において全ての区間は走行していない可能性がある。また、同一車両についてのレコードが複数登録されている場合もある。
【００８０】
図１０の説明に戻って、車両別走行経路算出部１０９は、特定された車両の走行位置レコードを全て処理したか判断する（ステップＳ４９）。特定された車両について未処理の走行位置レコードのペアが存在する場合にはステップＳ４５に戻る。
【００８１】
一方、特定された車両について全ての走行位置レコードを処理した場合には、車両別走行経路算出部１０９は、平均走行時間算出のためのデータ抽出範囲に含まれる走行位置レコードに係る全ての車両について処理したか判断する（ステップＳ５１）。未処理の車両が残っている場合にはステップＳ４３に戻る。一方、全ての車両について処理した場合には、元の処理に戻る。元の処理に戻ると端子Ａを介して図１５の処理に移行する。
【００８２】
図１５の処理の説明に移行して、道路リンク別平均走行時間算出部１１１は、車両及び道路リンク別走行時間算出処理を実施する（ステップＳ６１）。この車両及び道路リンク別走行時間算出処理については、図１６及び図１７を用いて説明する。
【００８３】
道路リンク別平均走行時間算出部１１１は、図１４に示したような車両別走行リンクテーブルにおいて、未処理のレコードを１つ特定する（ステップＳ７１）。そして、特定されたレコードに登録されている各リンクの距離（＝長さ）を道路地図ネットワーク情報格納部１０５から読み出し、当該各リンクの距離に応じて発時刻から着時刻までの時間を各リンクに割り振り、各リンクに対応付けて時間を道路交通情報ＤＢ１１２に登録する（ステップＳ７３）。（そもそも、走行位置情報と共に、走行速度情報が採取でき、且つそのリンク毎の平均を求めることができる等の条件が成立する場合は、発時刻から着時刻までの時間を各リンクに割り振る際、リンク毎にリンク長を平均速度で除した値を求め、その比に従って割り振っても良い。）上でも述べたように、注目車両は、両端のリンクについては、それらのリンクの全てを走行しているわけではない。従って、両端のリンクの影響を除去するか、又は無視する。
【００８４】
具体的には、前者であれば、例えばマップマッチングで走行位置の対応付けを行った際に、対応付けされたリンク上のどの位置で対応付けられたかを保持しておく。そして、経路同定がなされた後に、始点から進行方向で当該始点に隣接するノードまでの距離と、終点から当該終点に進行方向とは逆方向で隣接するノードまでの距離と、両端リンク以外の各リンクの距離とで、発時刻から着時刻までの時間を按分する。但し、始点から当該始点に隣接するノードまでの距離のための時間と、終点から当該終点に隣接するノードまでの距離のための時間とは、以下の処理では用いない。また、後者であれば、両端リンク以外の各リンクの距離で、発時刻から着時刻までの時間を按分する。多少各リンクに割り振られる時間が長くなるが、処理は簡単で高速であり、以下の処理で平均化するので精度的に問題ない場合もある。
【００８５】
このような処理を実施することにより、図１７に示すようなデータが道路交通情報ＤＢ１１２に格納される。図１７の例では、リンクＩＤに対応付けられて所要時間が登録されている。
【００８６】
そして、道路リンク別平均走行時間算出部１１１は、車両別走行リンクテーブルにおける全てのレコードについて処理したか判断する（ステップＳ７５）。未処理のレコードが存在する場合にはステップＳ７１に戻る。一方、全てのレコードを処理した場合には、元の処理に戻る。
【００８７】
このような処理を実施することによって、各車両が走行した各リンクについて要した走行時間を特定することができるようになる。
【００８８】
図１５の処理の説明に戻って、道路リンク別平均走行時間算出部１１１は、道路交通情報ＤＢ１１２に登録されているテーブル（図１７）を用いてリンク別平均走行時間算出処理を実施する（ステップＳ６３）。リンク別平均走行時間算出処理については、図１８及び図１９を用いて説明する。
【００８９】
まず、道路リンク別平均走行時間算出部１１１は、道路交通情報ＤＢ１１２に登録されているテーブル（図１７）において、リンクＩＤでレコードをソートする（ステップＳ８１）。そして、未処理のリンクＩＤを１つ特定する（ステップＳ８３）。そして、特定されたリンクＩＤについての全てのレコードを、上で述べたテーブルから抽出する（ステップＳ８５）。その後、抽出レコード数をカウントすると共に、時間の総和を算出し、当該時間の総和を抽出レコード数で除することによって、処理に係るリンクについての平均走行時間を算出し、道路交通情報ＤＢ１１２に登録する（ステップＳ８７）。
【００９０】
例えば、図１９に示すようなデータが道路交通情報ＤＢ１１２に登録される。図１９の例では、リンクＩＤに対応付けて平均走行時間が登録されている。このように平均走行時間が得られれば、この数値の大小によってスムーズに流れているリンクや、渋滞が発生しているようなリンクを容易に特定できるようになる。
【００９１】
そして、道路リンク別平均走行時間算出部１１１は、図１７のようなテーブルにおいて全てのリンクＩＤについて処理したか判断する（ステップＳ８９）。未処理のリンクＩＤが存在している場合にはステップＳ８３に戻る。一方、全てのリンクＩＤを処理した場合には、元の処理に戻る。
【００９２】
このような処理を実施することによって、道路状況を把握するための基本的なデータを得ることができる。
【００９３】
図１５の処理の説明に戻って、出力部１１３は、道路交通情報ＤＢ１１２に格納されている各リンクについての平均走行時間を、表示装置や印刷装置などの出力装置に出力する（ステップＳ６５）。図１９のようなテーブルをそのまま出力しても良いが、例えば道路地図ネットワーク情報格納部１０５から道路ネットワークのデータを読み出して、道路ネットワークを表示すると共に、例えば各リンクに関連付けて平均走行時間を表示するようにしても良い。さらに、平均走行時間のランク付けを行って、道路ネットワークにおいてランク付けに応じてリンクの色分けを行って表示するようにしても良い。
【００９４】
なお、出力部１１３は、例えばプローブ車両以外の車両にデータを配信するような処理部であってもよい。さらにＷｅｂサーバのようにアクセスに応じてデータを送信するようにしても良い。
【００９５】
［第１の走行経路算出処理の詳細］
上では概略のみを示したが、ここで処理フローを図２０及び図２１を用いて説明しておく。まず、車両別走行経路算出部１０９は、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、始点Ｃ0から進行方向で隣接するノードＡ00と、終点Ｃ1から進行方向とは逆方向で隣接するノードＡ22とを特定する（図２０：ステップＳ１０１）。そして、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、Ａ00からＡ22までの第１経路探索処理を実施する（ステップＳ１０３）。この第１経路探索処理については、図２１を用いて説明する。
【００９６】
第１の走行経路算出処理においては、図１２に示したように、一定の範囲に探索範囲を限定すると共に、引き返したり、迂回したり、ループしたりするような経路を除外した形で、全経路を特定するような探索方法を採用している。
【００９７】
具体的には、まず、車両別走行経路算出部１０９は、Ａ00からＡ22までの全経路を探索する（図２１：ステップＳ１１１）。図１２の例では、（１）Ａ00、Ａ01、Ａ02、Ａ12、Ａ22、（２）Ａ00、Ａ01、Ａ11、Ａ12、Ａ22、（３）Ａ00、Ａ01、Ａ11、Ａ21、Ａ22、（４）Ａ00、Ａ10、Ａ11、Ａ12、Ａ22、（５）Ａ00、Ａ10、Ａ11、Ａ21、Ａ22、（６）Ａ00、Ａ10、Ａ20、Ａ21、Ａ22というように６通りの経路が探索される。
【００９８】
そして、車両別走行経路算出部１０９は、全ての経路について移動可能性Ｐ00-・・・-22を算出し、当該値が最大となる経路を選択する（ステップＳ１１３）。６通りの経路のうちいずれか１つを選択する。そして元の処理に戻る。
【００９９】
図２０の説明に戻って、車両別走行経路算出部１０９は、始点Ｃ0からＡ00までの経路と、Ａ22から終点Ｃ1までの経路とをステップＳ１０３における経路探索結果に連結して、経路同定結果を車両別走行リンク情報格納部１１０に格納する（ステップＳ１０５）。
【０１００】
このような処理を実施することによって、処理に係る車両が走行した可能性の最も高い経路が同定されたことになる。
【０１０１】
［第２の走行経路算出処理の詳細］
第２の走行経路算出処理についても、ここで処理フローを図２２乃至図２５を用いて説明しておく。
【０１０２】
まず、車両別走行経路算出部１０９は、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、始点Ｃ1から進行方向で隣接するノードＡ1と、終点Ｃ2から進行方向とは逆方向で隣接するノードＡ11とを特定する（ステップＳ１２１）。そして、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、ノードＡ1からＡ11までの第２経路探索処理を実施する（ステップＳ１２３）。第２経路探索処理については、図２３乃至図２５を用いて説明する。
【０１０３】
車両別走行経路算出部１０９は、探索回数のカウンタであるｋを１に初期化し（図２３：ステップＳ１３１）、遷移先ノードＡikの添え字ｉkに開始ノードＡ1に対応する「１」をセットする（ステップＳ１３３）。さらに、遷移先ノードＡik＝Ａ1とセットする（ステップＳ１３５）。このデータについては、車両別走行リンク情報格納部１１０の探索テーブルに格納する。
【０１０４】
そして、車両別走行経路算出部１０９は、遷移先ノードＡikが終了ノードＡ11であるかどうか判断する（ステップＳ１３７）。このように、遷移先ノードＡikが終了ノードＡ11に到達した場合には、そこで探索を終了する。
【０１０５】
上で述べたように、図１３の例で例えばノードＡ5からノードＡ2への（リンクＢ5-2を通った）移動可能性Ｐ5-2は以下のとおりである。
Ｐ5-2＝ｂ5-2／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
このように移動可能性Ｐは、０以上１以下の値になる。そして属性値Ｑ5-2は、１／Ｐ5-2であるので、属性値Ｑ5-2は必ず１以上の実数となる。（但しＰ5-2が０の時Ｑ5-2は∞となる。）従って、遷移先ノードにおける総合の評価値を表す（１）式の値は必ず増加する（または等しい値のままである）。ステップＳ１３７で示すような探索終了条件を用いれば、（１）式の値ができるだけ小さな値になる（留る）ようなノード（経路）を順次求めて行くことによって、ノードＡ1からノードＡ11迄の、（１）式が最小の値となるような経路を求めることができる。
【０１０６】
多くの場合、そして少なくともこの例の場合、最初に実行する際にはステップＳ１３７の条件を満たすことはないので、遷移先ノードＡikが終了ノードＡ11ではないと判断され、車両別走行経路算出部１０９は、ｋを１インクリメントし（ステップＳ１３９）、（１）式によってｉk及びAikを決定し、例えば車両別走行リンク情報格納部１１０の探索テーブルに格納する（ステップＳ１４１）。そして、ステップＳ１３７に戻る。
【０１０７】
このようにステップＳ１３７乃至Ｓ１４１をステップＳ１３７の条件を満たすようになるまで繰り返す。車両別走行リンク情報格納部１１０の探索テーブルは、例えば図２５に示すようなテーブルである。すなわち、ｋと、ｉkと、遷移先ノードＡikと、遷移先ノードＡikに到達する直前のノード（探索元のノード）Ｍikとが登録されるようになっている。
【０１０８】
ここでは図１３と同じ道路ネットワークを今回の探索を説明するために図２４に示す。図２４においてノード付近に示された括弧付きの数字は、図２５の探索テーブルのｋの値と一致している。ｋ＝１の場合には、上で述べたように、ｉk＝１でＡik＝Ａ1となる（図２５の第１行）。ｋ＝２となると、（新たな探索の起点となり得る）探索元ノードは、探索テーブルにおける遷移先ノードＡikの列に既に登録されているノードＡ1であり（この場合、既に登録されているのはＡ1のみである）、このノードから（１）式によって得られる。すなわち、Ｆ(1)＝１と遷移の属性値Ｑ（「遷移に対応するリンク」の属性値Ｑ）との積が最も小さくなるようなノードを探索する。ｋ＝２の段階では、遷移先の候補となるのはＡ2とＡ4であるが、ここではＡ2の方がその遷移の属性値Ｑが小さいので採用され、ｉ2＝２、Ａi2＝Ａ2と特定され、図２５の探索テーブルの２行目に登録される。なお、Ｍi2は探索元ノードＡ1である。また、Ｆ(2)については、Ｆ(2)＝Ｆ(1)＊Ｑ1-2である。Ｆ(4)についてはこの段階ではＦ(4)＝Ｆ(1)＊Ｑ1-4である。Ｆ(2)及びＦ(4)の値については以下の処理で用いるので保持しておく。また、（図２５の探索テーブルに（少なくともこの段階で）登録されていない）Ａ4については、Ａ4が遷移先候補として取上げられたということ（事実）、及びＡ4の探索元が（この段階で）Ａ1であることを、以下の処理のための情報として、保持しておく。
【０１０９】
ｋ＝３となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ1及びノードＡ2となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(1)＝１と遷移の属性値Ｑとの積及びＦ(2)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝３の段階では、遷移先ノードの候補は、Ａ3、Ａ4、Ａ5である。そうすると、Ｆ(4)、Ｆ(5)＝Ｆ(2)＊Ｑ2-5、Ｆ(3)＝Ｆ(2)＊Ｑ2-3の三者を比較することになるが、（この例では）Ｆ(4)が最小であるとして、ノードＡ4が選択される。（Ｆ(5)、Ｆ(3)は、ここで新たに算出するが、Ｆ(4)はｋ＝２の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの３行目には、ｉk＝４、Ａik＝Ａ4、Ｍik＝Ａ1が登録される。Ｆ(4)、Ｆ(5)、Ｆ(3)の値については保持しておく。また、Ａ3、Ａ5については、Ａ3、Ａ5が遷移先候補として取上げられたということ、及びＡ3、Ａ5の探索元が（この段階で）Ａ2であることを、以下の処理のための情報として保持しておく。
【０１１０】
ｋ＝４となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ2及びノードＡ4となる。ノードＡ1は全ての可能な遷移先ノードについて探索テーブルのＡikの列に登録されてしまったので（新たな探索の起点となり得る）探索元ノードから外れる。これらのノードから（１）式によって得られるノード、すなわち、Ｆ(2)と遷移の属性値Ｑとの積及びＦ(4)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝４の段階では、遷移先ノードの候補は、Ａ3、Ａ5、Ａ8である。そうすると、ノードＡ2経由のＦ(5)（＝Ｆ(2)＊Ｑ2-5）、ノードＡ4経由のＦ(5)＝Ｆ(4)＊Ｑ4-5、Ｆ(3)、Ｆ(8)＝Ｆ(4)＊Ｑ4-8とを比較して、ノードＡ2経由のＦ(5)が最小であるとして、ノードＡ5が選択される。（「Ａ4経由のＦ(5)」、Ｆ(8)は、ここで新たに算出するが、「Ａ2経由のＦ(5)」、Ｆ(3)は、ｋ＝３の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの４行目には、ｉk＝５、Ａik＝Ａ5、Ｍik＝Ａ2が登録される。Ｆ(3)、Ｆ(4)、ノードＡ2経由のＦ(5)、Ｆ(8)の値については保持しておく。（Ｆ(5)については、このＡ2経由の値が、この段階で（更新を最大に施した）最新のものであると考える。）
【０１１１】
ｋ＝５となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ2、ノードＡ4及びノードＡ5となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(2)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積及びＦ(5)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝５の段階では、遷移先ノードの候補は、Ａ3、Ａ6、Ａ8、Ａ9である。そうすると、Ｆ(3)、Ｆ(6)＝Ｆ(5)＊Ｑ5-6、Ｆ(9)＝Ｆ(5)＊Ｑ5-9、Ｆ(8)とを比較することになるが、ノードＡ2経由のＦ(3)が最小であるとして、ノードＡ3が選択される。（Ｆ(6)、Ｆ(9)は、ここで新たに算出するが、Ｆ(3)、Ｆ(8)は、ｋ＝４の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの５行目には、ｉk＝３、Ａik＝Ａ3、Ｍik＝Ａ2が登録される。Ｆ(3)、ノードＡ2経由のＦ(5)、ノードＡ5経由のＦ(6)、Ｆ(8)、Ｆ(9)の値については保持しておく。また、Ａ6、Ａ9については、Ａ6、Ａ9が遷移先候補として取上げられたということ、及びＡ6、Ａ9の探索元が（この段階で）Ａ5であることを以下の処理のための情報として保持しておく。
【０１１２】
ｋ＝６となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ4、ノードＡ5、ノードＡ3となる。ノードＡ2は全ての可能な遷移先ノードについて探索テーブルのＡikの列に登録されてしまったので探索元ノードから外れる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑの積及びＦ(3)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝６の段階では、遷移先ノードの候補は、Ａ7、Ａ6、Ａ8、Ａ9である。そうすると、Ｆ(7)＝Ｆ(3)＊Ｑ3-7、Ｆ(6)、Ｆ(9)、Ｆ(8)とを比較して、ノードＡ5経由のＦ(9)が最小であるとして、ノードＡ9が選択される。Ｆ(7)は、ここで新たに算出するが、Ｆ(6)、Ｆ(9)、Ｆ(8)は、ｋ＝５の場合迄の処理で算出済みのものを用いる。従って、探索テーブルの６行目には、ｉk＝９、Ａik＝Ａ9、Ｍik＝Ａ5が登録される。ノードＡ5経由のＦ(6)、Ｆ(7)、ノードＡ4経由のＦ(8)、ノードＡ5経由のＦ(9)の値については保持しておく。また、Ａ7については、Ａ7が遷移先候補として取上げられたということ、及びＡ7の探索元が（この段階で）Ａ3であることを、以下の処理のための情報として、保持しておく。
【０１１３】
ｋ＝７となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ3、ノードＡ4、ノードＡ5、ノードＡ9となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(3)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑの積及びＦ(9)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝７の段階では、遷移先ノードの候補は、Ａ7、Ａ6、ノードＡ4経由のＡ8、ノードＡ9経由のＡ8、ノードＡ9経由のＡ4、Ａ10である。そうすると、Ｆ(7)、Ｆ(6)、Ｆ(10)＝Ｆ(9)＊Ｑ9-10、Ｆ(8)（＝Ｆ(4)＊Ｑ4-8）と、Ｆ(8)＝Ｆ(9)＊Ｑ9-8を比較して、ノードＡ9経由のＦ(10)が最小であるとして、ノードＡ10が選択される。（Ｆ(10)、「Ａ9経由のＦ(8)」は、ここで新たに算出するが、Ｆ(7)、Ｆ(6)、「Ａ4経由のＦ(8)」は、ｋ＝６の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの７行目には、ｉk＝１０、Ａik＝Ａ10、Ｍik＝Ａ9が登録される。ノードＡ5経由のＦ(6)、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(8)、ノードＡ9経由のＦ(4)、Ｆ(7)、Ｆ(10)の値については保持しておく。また、Ａ10については、Ａ10が遷移先候補として取上げられたということ、及びＡ10の探索元が（この段階で）Ａ9であることを、以下の処理のための情報として、保持しておく。
【０１１４】
ｋ＝８となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ3、ノードＡ4、ノードＡ5、ノードＡ10、ノードＡ9となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(3)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑとの積、Ｆ(9)と遷移の属性値Ｑの積及びＦ(10)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝８の段階では、遷移先ノードの候補は、Ａ7、ノードＡ5経由のＡ6、ノードＡ4経由のＡ8、ノードＡ9経由のＡ8、ノードＡ10経由のノードＡ6、Ａ11である。そうすると、Ｆ(7)、ノードＡ5経由のＦ(6)（＝Ｆ(5)＊Ｑ5-6）、ノードＡ10経由のＦ(6)＝Ｆ(10)＊Ｑ10-6、Ｆ(11)＝Ｆ(10)＊Ｑ10-11、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(4)、ノードＡ9経由のＦ(8)を比較して、ノードＡ9経由のＦ(8)が最小であるとして、ノードＡ8が選択される。（「Ａ10経由のＦ(6)」、Ｆ(11)は、ここで新たに算出するが、Ｆ(7)、「Ａ5経由のＦ(6)」、「Ａ4経由のＦ(8)」、「Ａ9経由のＦ(8)」は、ｋ＝７の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの８行目には、ｉk＝８、Ａik＝Ａ8、Ｍik＝Ａ9が登録される。ノードＡ5経由のＦ(6)、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(8)、Ｆ(7)、ノードＡ9経由のＦ(4)、ノードＡ10経由のＦ(6)、Ｆ(11)の値については保持しておく。また、Ａ11については、Ａ11が遷移先候補として取上げられたということ、及びＡ11の探索元が（この段階で）Ａ10であることを、以下の処理のための情報として、保持しておく。
【０１１５】
ｋ＝９となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ3、ノードＡ5、ノードＡ10となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(3)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑとの積、Ｆ(9)と遷移の属性値Ｑの積、Ｆ(8)と遷移の属性値Ｑの積及びＦ(10)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝９の段階では、遷移先ノードの候補は、Ａ7、ノードＡ10経由又はノードＡ5経由のＡ6、ノードＡ4経由のＡ8、ノードＡ9経由又はノードＡ8経由のＡ4、Ａ11である。そうすると、Ｆ(7)、ノードＡ5経由のＦ(6)、ノードＡ10経由のＦ(6)、Ｆ(11)、Ｆ(8)と、ノードＡ9経由のＦ(4)、ノードＡ8経由のＦ(4)＝Ｆ(8)＊Ｑ8-4を比較して、ノードＡ3経由のＦ(7)が最小であるとして、ノードＡ7が選択される。「Ａ8経由のＦ(4)」は、ここで新たに算出するが、Ｆ(7)、「Ａ5経由のＦ(6)」、「Ａ10経由のＦ(6)」、Ｆ(11)、Ｆ(8)、「Ａ9経由のＦ(4)」は、ｋ＝８の場合迄の処理で算出済みのものを用いる。従って、探索テーブルの９行目には、ｉk＝７、Ａik＝Ａ7、Ｍik＝Ａ3が登録される。ノードＡ5経由のＦ(6)、ノードＡ10経由のＦ(6)、ノードＡ4経由のＦ(8)、ノードＡ8経由のＦ(4)、ノードＡ9経由のＦ(4)、Ｆ(7)、ノードＡ10経由のＦ(11)の値については保持しておく。
【０１１６】
ｋ＝１０となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ4、ノードＡ5、ノードＡ10、ノードＡ9、ノードＡ8、Ａ7となる。ノードＡ3については、遷移先ノードが全てＡikに登録されたので探索元ノードから外れる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑとの積、Ｆ(9)と遷移の属性値Ｑの積、Ｆ(8)と遷移の属性値Ｑの積、Ｆ(10)と遷移の属性値Ｑの積及びＦ(7)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝１０の段階では、遷移先ノードの候補は、ノードＡ10経由、ノードＡ7経由又はノードＡ5経由のＡ6、ノードＡ4経由のＡ8、ノードＡ9経由又はノードＡ8経由のＡ4、ノードＡ7経由又はノードＡ10経由のＡ11である。そうすると、ノードＡ5経由のＦ(6)（＝Ｆ(5)＊Ｑ5-6）、ノードＡ7経由のＦ(6)＝Ｆ(7)＊Ｑ7-6、ノードＡ10経由のＦ(6)（＝Ｆ(10)＊Ｑ10-6）、ノードＡ10経由のＦ(11)（＝Ｆ(10)＊Ｑ10-11）、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(4)、ノードＡ8経由のＦ(4)、ノードＡ7経由のＦ(11)＝Ｆ(7)＊Ｑ7-11を比較して、ノードＡ10経由のＦ(11)が最小であるとして、ノードＡ11が選択される。「Ａ7経由のＦ(6)」、「Ａ7経由のＦ(11)」は、ここで新たに算出するが、「Ａ5経由のＦ(6)」、「Ａ10経由のＦ(6)」、「Ａ10経由のＦ(11)」、「Ａ4経由のＦ(8)」、「Ａ9経由のＦ(4)」、「Ａ8経由のＦ(4)」は、ｋ＝９の場合迄の処理で算出済みのものを用いる。従って、探索テーブルの１０行目には、ｉk＝１１、Ａik＝Ａ11、Ｍik＝Ａ10が登録される。
【０１１７】
このようにｋ＝１０になると、Ａik＝Ａ11となってステップＳ１３７の条件を満たすことになる。ステップＳ１３７の条件を満たしたと判断されると、車両別走行経路算出部１０９は、探索テーブルにおいて、Ａikの列のＡ11から直前ノードＭikを辿ってＡ1までノード列を特定し、逆順でＡ1からＡ11まで並べ替えて目的の経路を特定する（ステップＳ１４３）。以下の処理では、リンク列が必要となるので、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、リンク列に変換する。そして元の処理に戻る。
【０１１８】
図２５の探索テーブルの例では、１０行目のＭik＝Ａ10から、Ａikの列にＡ10が出現する行を探索すると、７行目であることが分かる。この７行目のＭik＝Ａ9から、Ａikの列にＡ9が出現する行を探索すると、６行目であることが分かる。この６行目のＭik＝Ａ5から、Ａikの列にＡ5が出現する行を探索すると、４行目であることが分かる。この４行目のＭik＝Ａ2から、Ａikの列にＡ2が出現する行を探索すると、２行目であることが分かる。この２行目のＭik＝Ａ1から、開始ノードまで辿ることができたことになる。従って、Ａ11、Ａ10、Ａ9、Ａ5、Ａ2、Ａ1というノード列から、Ａ1、Ａ2、Ａ5、Ａ9、Ａ10、Ａ11が求めるべき経路（図２４の太一点鎖線）である。
【０１１９】
なお、ノードＡ6については、遷移先ノードとして特定されることがなかった。これは、上で述べたように属性値Ｑの特性からしてＱ6-11がどのような値であってもこのノードＡ6を経由すると必ず（１）式の値は他の経路の場合より大きくなるためである。
【０１２０】
このような処理を実施することによって、（１）式を用いて次の遷移先ノードを探索されるノード、すなわち、探索元ノードまでの累積属性値と、その探索元ノードから候補ノードまでの属性値Ｑとの積が最も小さくなるような候補ノードが遷移先ノードとして選択され、走行可能性が最も高い経路が特定されるようになる。
【０１２１】
図２２の説明に戻って、車両別走行経路算出部１０９は、始点Ｃ1からＡ1までの経路と、Ａ11から終点Ｃ2までの経路とをステップＳ１２３における経路探索結果に連結して経路同定結果を、車両別走行リンク情報格納部１１０に格納する（ステップＳ１２５）。
【０１２２】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図１に示したプローブ道路交通情報システム１００の機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成と一致しない場合もある。
【０１２３】
さらに、処理フローについても処理結果が変わらない限りにおいて処理順番を入れ替えたり、並列に実行したりするようにしても良い。
【０１２４】
さらに、上で述べた機能を全て１台のコンピュータで実施しなければならないわけではなく、複数台のコンピュータで実現するようにしても良い。
【０１２５】
なお、上で述べたプローブ道路交通情報システム１００は、コンピュータ装置であって、図２６に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１２６】
以上本実施の形態をまとめると以下のようになる。
【０１２７】
本車両走行位置データ処理方法は、計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、計測時刻と車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、読み出された車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおけるノード及びリンクの位置データ及びリンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている複数のリンクのうち車両走行位置データ・レコードの車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、複数のリンクの各々について、頻度カウンタの値を道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、正規化走行頻度データ格納部に格納されている各リンクの正規化走行頻度の値に基づき、走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップとを含む。
【０１２８】
このように過去の走行実績から算出される各リンクの正規化走行頻度に基づき、各リンクについて車両走行の蓋然性が分かるようになるので、２地点間で最も蓋然性が高いリンクの組み合わせである走行経路が特定できる。すなわち、走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定することができる。
【０１２９】
また、本車両走行位置データ処理方法は、２つの車両走行位置データ・レコードで特定される２地点間の走行時間を、車両別走行リンク情報格納部に格納されている走行経路に含まれる各経路上リンクに、道路地図ネットワーク情報格納部に格納されている経路上リンクの長さデータ（又は長さデータを平均速度データで除した値）を基に振り分け、経路上リンクの識別子に対応付けて振り分けられた走行時間を時間推定結果格納部に格納するステップをさらに含むようにしても良い。同定された走行経路に含まれる各経路上リンクについて、特定の時間における所要走行時間を得ることができるようになる。これにより例えば渋滞の発生などを認識することができるようになる。
【０１３０】
さらに、本車両走行位置データ処理方法は、時間推定結果格納部に格納されている経路上リンクの識別子毎に、対応する走行時間の平均値を算出し、時間推定結果格納部に格納するステップをさらに含むようにしても良い。このように各経路上リンクについて、所要走行時間の平均値を算出することにより、各道路について走行状態の概要を把握することができるようになる。
【０１３１】
また、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、候補リンクの正規化走行頻度の値の総和に対する当該候補リンクの正規化走行頻度の値の比率を当該候補リンクが採用される可能性を表す評価値とする場合もある。このような場合には、上で述べた経路推定ステップにおいて、２地点のうちの始点に最も近いノードである始点ノードから２地点のうち終点に最も近いノードである終点ノードまで、移動元ノードと複数の移動先候補ノードとの全ての組み合わせについて順次評価値を算出して、当該評価値を各候補経路に沿って乗算し、終点ノードに達した候補経路のうち、評価値の総乗算値が最大となる候補経路を特定するようにしてもよい。最短経路探索のダイクストラ法などとは異なり、始点ノードから終点ノードへ候補リンクを辿る際に、正規化走行頻度から得られ且つ候補リンクが採用される可能性（確率とも呼ぶ）を乗算することによって、より採用される可能性の高い候補リンク群を含む走行経路を特定することができるようになる。
【０１３２】
さらに、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの正規化走行頻度の値に対する全ての候補リンクの正規化走行頻度の値の和の比率を当該候補リンクの評価値とする場合もある。このような場合には、上で述べた経路推定ステップにおいて、２地点のうちの始点に最も近いノードである始点ノードから２地点のうち終点に最も近いノードである終点ノードまで、移動元ノードと複数の移動先候補ノードとの全ての組み合わせについて順次評価値を算出して、当該評価値を各候補経路に沿って乗算し、終点ノードに達した候補経路のうち、評価値の総乗算値が最小となる候補経路を特定するようにしてもよい。このように、上で述べた候補リンクが採用される可能性を表す評価値の逆数で走行経路を特定することもできるようになる。
【０１３３】
また、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和に対する当該候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積の比率を当該候補リンクが採用される可能性を表す評価値とする場合もある。さらに、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積に対する候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和の比率を当該候補リンクの評価値として規定する場合もある。このように、各リンクについて平均走行速度にばらつきがある場合には、このような評価値を採用することによって、平均走行速度の高低を評価値に適切に反映させることができるようになる。
【０１３４】
なお、上で述べたような処理をハードウエアに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０１３５】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１３６】
（付記１）
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップと、
を含み、コンピュータに実行される車両走行位置データ処理方法。（１、図４）
【０１３７】
（付記２）
２つの前記車両走行位置データ・レコードで特定される２地点間の走行時間を、前記車両別走行リンク情報格納部に格納されている前記走行経路に含まれる各経路上リンクに、前記道路地図ネットワーク情報格納部に格納されている前記経路上リンクの長さデータ（又は長さデータを平均速度データで除した値）を基に振り分け、前記経路上リンクの識別子に対応付けて振り分けられた走行時間を時間推定結果格納部に格納するステップ
をさらに含む付記１記載の車両走行位置データ処理方法。（２，図１６）
【０１３８】
（付記３）
前記時間推定結果格納部に格納されている前記経路上リンクの識別子毎に、対応する前記走行時間の平均値を算出し、前記時間推定結果格納部に格納するステップ、
をさらに含む付記２記載の車両走行位置データ処理方法。（３，図１８）
【０１３９】
（付記４）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値の総和に対する当該候補リンクの前記正規化走行頻度の値の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（４）
【０１４０】
（付記５）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値に対する全ての前記候補リンクの前記正規化走行頻度の値の和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（５）
【０１４１】
（付記６）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和に対する当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（６）
【０１４２】
（付記７）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積に対する前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（７）
【０１４３】
（付記８）
付記１乃至７のいずれか１つ記載の車両走行データ処理方法をコンピュータに実行させるためのプログラム。（８）
【０１４４】
（付記９）
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出す手段と、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントする手段と、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納する手段と、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定手段と、
を有する車両走行位置データ処理装置。（９）
【符号の説明】
【０１４５】
１０１ プローブ車両位置収集部 １０２ 走行位置情報格納部
１０３ 道路リンク別走行頻度算出部 １０４ 道路リンク別走行頻度情報格納部
１０５ 道路地図ネットワーク情報格納部 １０６ 正規化走行頻度算出部
１０７ 正規化走行頻度情報格納部 １０８ 入力部
１０９ 車両別走行経路算出部 １１０ 車両別走行リンク情報格納部
１１１ 道路リンク別平均走行時間算出部 １１２ 道路交通情報ＤＢ
１１３ 出力部
【技術分野】
【０００１】
本技術は、走行中の車両で計測される位置情報を解析する技術に関する。
【背景技術】
【０００２】
例えば、経路案内を行う車両用経路案内装置において、使用者の走行状況を反映した目的地経路の設定を行う技術が存在している。具体的には、車両が走行した走行道路のうち利用頻度が所定値以上となる走行道路のデータを自動的に記憶しておき、経路対象道路のデータと記憶しておいた走行道路のデータを用いて出発地から目的地に至る目的地経路を設定する。また、現在地に最も近いリンク上の位置を出発地（経路計算上の開始点）とし、設定された目的地（以下、設定目的地という）に最も近いリンク上の位置を目的地（経路計算上の終了点）とし、出発地から目的地までの経路をダイクストラ法を用いたコスト計算により設定する。すなわち、出発地から目的地までの各リンクでの経路コストを例えば次の式を用いて計算する。経路コスト＝リンク長×道路幅係数×道路種別係数。ここで、リンク長はノード間の距離であり、道路幅係数とは道路幅の大きさに対して設定される係数であり、道路種別係数とは、有料道路等の道路種別に応じて設定される係数である。但し、この技術は、経路探索の一つであり、過去の離散的な走行位置から当該走行位置間の経路を同定する技術ではない。
【０００３】
また、よりユーザの嗜好に合った走行経路を推奨することができるナビゲーション装置も存在する。具体的には、ナビゲーション装置は、複数の領域に分けられた地図に関するデータを有する地図データ格納部と、目的地とする領域のエリアＩＤ毎にそれぞれのリンクの走行回数を格納する走行回数データ格納部とを有し、車両が走行したリンクの情報を順次記録し、エンジン始動時に、現在位置が含まれる領域に応じて、エリアＩＤ毎のリンクの走行回数を更新する。そして、ナビゲーション装置は、目的地が設定された場合に、設定された目的地が含まれる地図上の領域のエリアＩＤに対応する走行回数を用いて、それぞれのリンクデータのコストを修正し、修正したコストを用いて、目的地までの経路を探索して出力する。この技術も、過去の離散的な走行位置から当該走行位置間の経路を同定する技術ではない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３４０６１４４号公報
【特許文献２】特開２００８−９６２７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上で述べたように、従来技術では、道路に対応するリンクのコストをその目的に適切な属性に応じて重み付けして、これから走行しようとする経路の探索を実施するものである。
【０００６】
しかしながら、走行中の車両で計測される走行位置を離散的にしか得られない場合に、当該走行位置間の過去の走行経路を同定するようなことはできない。
【０００７】
従って、本技術の目的は、走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定するための技術を提供することである。
【課題を解決するための手段】
【０００８】
本車両走行位置データ処理方法は、計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、計測時刻と車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、読み出された車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおけるノード及びリンクの位置データ及びリンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている複数のリンクのうち車両走行位置データ・レコードの車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、複数のリンクの各々について、頻度カウンタの値を道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、正規化走行頻度データ格納部に格納されている各リンクの正規化走行頻度の値に基づき、走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップとを含む。
【発明の効果】
【０００９】
走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、本技術の実施の形態に係るシステム概要図である。
【図２】図２は、道路リンクとノードの関係を示す模式図である。
【図３】図３は、道路地図ネットワーク情報格納部に格納されるデータの一例を示す図である。
【図４】図４は、メインの処理フローを示す図である。
【図５】図５は、走行位置情報格納部に格納されるデータの一例を示す図である。
【図６】図６は、正規化走行頻度情報生成処理の処理フローを示す図である。
【図７】図７は、道路リンク毎の走行頻度を表すデータの一例を示す図である。
【図８】図８は、道路リンク毎の走行頻度を模式的に示した図である。
【図９】図９は、正規化走行頻度情報格納部に格納されるデータの一例を示す図である。
【図１０】図１０は、車両別走行経路算出処理の処理フローを示す図である。
【図１１】図１１は、経路同定を行う区間を説明するための図である。
【図１２】図１２は、第１の走行経路算出処理の説明における道路ネットワークの一例を示す図である。
【図１３】図１３は、第２の走行経路算出処理の説明における道路ネットワークの一例を示す図である。
【図１４】図１４は、車両別走行リンクテーブルの一例を示す図である。
【図１５】図１５は、メインの処理フローを示す図である。
【図１６】図１６は、車両及び道路リンク別走行時間算出処理の処理フローを示す図である。
【図１７】図１７は、道路交通情報ＤＢに格納されるデータの一例を示す図である。
【図１８】図１８は、リンク別平均走行時間算出処理の処理フローを示す図である。
【図１９】図１９は、道路交通情報ＤＢに格納されるデータの一例を示す図である。
【図２０】図２０は、第１の走行経路算出処理の処理フローを示す図である。
【図２１】図２１は、第１経路探索処理の処理フローを示す図である。
【図２２】図２２は、第２の走行経路算出処理の処理フローを示す図である。
【図２３】図２３は、第２経路探索処理の処理フローを示す図である。
【図２４】図２４は、第２経路探索処理を説明するための図である。
【図２５】図２５は、探索テーブルの一例を示す図である。
【図２６】図２６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１１】
［本実施の形態の概要］
本実施の形態では、例えばＧＰＳ（Global Positioning System）端末及び無線通信機を車両に搭載する複数のプローブ車両を用意する。そして、複数のプローブ車両は、走行中、一定の時間間隔（例えば数十秒から数分間）又は一定の走行距離（数百メートル間隔乃至数キロメートル間隔）毎に、ＧＰＳ端末により走行位置を計測し、無線通信機によって走行位置データを以下で述べるプローブ道路交通情報システムに送信する。なお、送信間隔が短いほど、以下で述べる処理の精度は向上し、極端な場合にはリアルタイムで送信するようなことも考えられるが、プローブ車両の数、通信コストや無線通信負荷の問題からして、ある程度の間隔毎に走行位置データを送信するのが現実的である。そうすると、走行位置データに含まれる計測位置間をプローブ車両がどのような経路で走行したかについては一義的には決まらない場合が生じ（得）るということになる。
【００１２】
これに対してプローブ道路交通情報システムでは、複数のプローブ車両の走行位置データを受信して蓄積する。そして、蓄積された走行位置データを、既存の道路地図ネットワークにおける道路リンク（以下では、単にリンクと述べる場合もある）に投影して、各道路リンクについてプローブ車両が走行した頻度を計数する。そして、道路リンクの長さで頻度を除することによって正規化し、正規化された頻度の値を当該道路リンクを走行する蓋然性（又は利用しやすさ）を表すデータとして用いて、同一プローブ車両の２つの走行位置間の経路として最も可能性の高い経路を求める。これが、経路同定の結果となる。
【００１３】
さらに、経路が同定されれば、経路上の各リンクについて所要走行時間を算出することができ、さらにリンク毎の平均走行時間も算出できる。このようにすれば、どこで渋滞が発生しているのか、どこが空いている道なのかを特定することも可能となる。
【００１４】
［本実施の形態の具体的な構成］
図１に本実施の形態におけるシステム概要を示す。プローブ道路交通情報システム１００は、上で述べたようにＧＰＳ端末及び無線通信機を有する複数のプローブ車両から無線を含む通信網を介して走行位置情報を受信するプローブ車両位置収集部１０１と、プローブ車両位置収集部１０１によって取得された走行位置情報を格納する走行位置情報格納部１０２と、複数のノードと当該ノード間のリンクによって表される道路地図ネットワークのデータを格納する道路地図ネットワーク情報格納部１０５と、走行位置情報格納部１０２と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて道路リンク毎に走行頻度を計算する道路リンク別走行頻度算出部１０３と、道路リンク別走行頻度算出部１０３の処理結果を格納する道路リンク別走行頻度情報格納部１０４と、道路リンク別走行頻度情報格納部１０４と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて道路リンク毎に正規化走行頻度を算出する正規化走行頻度算出部１０６と、正規化走行頻度算出部１０６の処理結果を格納する正規化走行頻度情報格納部１０７と、走行位置情報格納部１０２と正規化走行頻度情報格納部１０７と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて車両毎に走行経路を同定するための経路計算を実施する車両別走行経路算出部１０９と、車両別走行経路算出部１０９の処理結果を格納する車両別走行リンク情報格納部１１０と、車両別走行リンク情報格納部１１０と道路地図ネットワーク情報格納部１０５とに格納されているデータを用いて道路リンク毎に平均走行時間を算出する道路リンク別平均走行時間算出部１１１と、道路リンク別平均走行時間算出部１１１の処理結果を格納する道路交通情報ＤＢ１１２と、道路地図ネットワーク情報格納部１０５と道路交通情報ＤＢ１１２や車両別走行リンク情報格納部１１０に格納されているデータを用いて出力データを生成して出力する出力部１１３と、道路リンク別走行頻度算出部１０３及び車両別走行経路算出部１０９に対して必要な入力データをユーザから受け取り出力する入力部１０８とを有する。
【００１５】
道路地図ネットワークは、図２に模式的に示すように、例えば交差点（交差点でない位置にノードが設けられる場合もある）に対応する複数のノードｎ１００１乃至ｎ１００５を、道路に対応する道路リンク１０００乃至１００７で接続するようなネットワークである。本実施の形態では、一方通行でない場合には基本的には互いに逆方向の２本のリンクで、ノード間を接続するものとする。但し、場合によっては双方向で通行できる場合でも１本のリンクで繋がれている場合もある。
【００１６】
このような道路ネットワークを表現するためのデータとして、道路地図ネットワーク情報格納部１０５には、図３に示すようなデータが格納される。図３の例では、道路リンク番号に対応付けられて、道路種別と、リンク距離（リンク長）と、位置（例えば始点位置−終点位置）とが登録されるようになっている。なお、位置については、始点ノード番号及び終点ノード番号で特定しておき、ノード番号と位置の関係を保持する別のテーブルを用いて具体的な位置を特定するようにしても良い。
【００１７】
次に、図４乃至図１９を用いて、プローブ道路交通情報システム１００の動作について説明する。
【００１８】
上でも述べたが、プローブ車両は、走行位置情報を、所定時間間隔又は所定走行距離毎に、無線を含む通信網を介してプローブ道路交通情報システム１００に送信する。この走行位置情報は、例えば、車両種別、車両ＩＤ、取得日時、車両位置、移動方向、移動速度、状態（例えばタクシーであれば顧客が乗車中であるか否か、トラックであれば顧客の荷物を積載中であるか否かなど。）などのデータを含む。
【００１９】
プローブ道路交通情報システム１００のプローブ車両位置収集部１０１は、全てのプローブ車両から走行位置情報を随時受信し、走行位置情報格納部１０２に格納する（図４：ステップＳ１）。なお、このステップは、説明の便宜上最初に行う処理として説明しているが、実際はこれ以降に述べる処理とは別スレッドで随時実施される。
【００２０】
例えば、図５に示すようなデータが、走行位置情報格納部１０２に格納される。図５の例では、車両種別、車両ＩＤ、日時、位置、移動方向、速度及び状態が登録されるようになっている。本実施の形態において以下の処理で用いられないデータもあるが、そのようなデータは本実施の形態以外の処理において用いられる場合もある。
【００２１】
そして、入力部１０８は、正規化走行頻度算出及び平均走行時間算出のためのデータ抽出範囲の指定をユーザに対して促し、ユーザからの入力を受け付ける（ステップＳ３）。
【００２２】
正規化走行頻度は、以下で述べる正規化走行頻度算出部１０６で算出され且つ各リンクをプローブ車両が通過する可能性を表す数値（単位距離（単位長さ）あたりの走行頻度）である。そして、正規化走行頻度算出のためのデータ抽出範囲については、どのようなプローブ車両が通過する可能性をどのような時間／地域のデータをベースに算出するかを指定するために入力する。例えば、タクシーを含む一般車両が通過する可能性を直近１ヶ月間東京２３区内の範囲で算出するといった指定を行う。
【００２３】
また、平均走行時間は、プローブ車両が各道路リンクをどの程度の時間で通過しているかを表す数値である。平均走行時間算出のためのデータ抽出範囲は、どのようなプローブ車両がどのような時間／地域について走行した結果をベースに平均走行時間を算出するかを指定するために入力する。例えば、タクシーを含む一般車両が直近３０分間東京２３区内の範囲を走行した結果で平均走行時間を算出するといった指定を行う。
【００２４】
正規化走行頻度を基に平均走行時間を算出するので、正規化走行頻度算出のためのデータ抽出範囲と、平均走行時間算出のためのデータ抽出範囲とは、ある程度の関連性を有するものとなる。すなわち、同様の地域についてデータ抽出範囲を指定する必要があり、時間についても、例えば前者が金曜日の１４時から１５時というようなデータ抽出範囲であれば、後者は過去６ヶ月において平日の１４時から１５時というようなデータ抽出範囲とする。
【００２５】
なお、ある程度ルールを決めてしまえば、平均走行時間算出のためのデータ抽出範囲のみを入力するようにして、当該データ抽出範囲から自動的に正規化走行頻度算出のためのデータ抽出範囲を特定するようにしても良い。
【００２６】
また、これとは別に、天気のデータをも収集しておき、データ抽出範囲についても天気を指定するようにしても良い。
【００２７】
さらに、例えば３０分毎に３０分時間だけがシフトするが他の条件については同一のデータ抽出範囲について定期的に処理する場合には、平均走行時間算出のためのデータ抽出範囲についても自動的に生成するような構成を採用するようにしても良い。
【００２８】
入力部１０８は、正規化走行頻度算出のためのデータ抽出範囲のデータについては道路リンク別走行頻度算出部１０３に出力する。平均走行時間算出のためのデータ抽出範囲のデータについては車両別走行経路算出部１０９に出力する。
【００２９】
次に、道路リンク別走行頻度算出部１０３は、正規化走行頻度算出のためのデータ抽出範囲に応じて、走行位置情報格納部１０２から該当する走行位置情報を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ５）。また、車両別走行経路算出部１０９も、平均走行時間算出のためのデータ抽出範囲に応じて、走行位置情報格納部１０２から該当する走行位置情報を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ７）。
【００３０】
そして、道路リンク別走行頻度算出部１０３等は、正規化走行頻度情報生成処理を実施する（ステップＳ９）。この正規化走行頻度情報生成処理については、図６乃至図９を用いて説明する。
【００３１】
まず、道路リンク別走行頻度算出部１０３は、正規化走行頻度算出のためのデータ抽出範囲に含まれる未処理の走行位置レコードを１つ特定する（図６：ステップＳ２１）。そして、周知のマップマッチングにより、道路地図ネットワーク情報格納部１０５に登録されている道路リンクのうち、特定された走行位置レコードの走行位置が対応付けられるリンクを特定し、当該リンクのカウントを１インクリメントする（ステップＳ２３）。ＧＰＳによる位置情報は必ずしも正確ではなく、走行位置が道路地図ネットワーク情報格納部１０５に登録されているいずれかの道路リンク上に常に載るわけではない。従って、道路リンクから離れていた場合、走行位置をどの道路リンクに対応付けるのかというのは、従来のカーナビゲーションシステムにおいても問題となっていた。このような問題を解決するためマップマッチングという手法が以前より用いられており、本実施の形態でもステップＳ２３で用いる。簡単に述べれば、走行位置から候補リンクに垂線を下ろした際に最も短い垂線が下ろされたリンクを選択するものである。但し、走行規制など他の補助的なデータを用いてリンクを選択する技術も存在しており、そのような技術を本ステップで用いるようにしても良い。
【００３２】
また、ステップＳ２３のカウント結果は、例えば道路リンク別走行頻度情報格納部１０４に格納される。この道路リンク別走行頻度情報格納部１０４に格納されるデータの一例を図７に示す。図７の例では、道路リンク番号毎に、走行頻度のカウンタが設けられている。ステップＳ２３で１つのリンクが特定されると、該当するリンク番号のカウンタの値が１インクリメントされる。
【００３３】
ステップＳ２３の処理結果を模式的に示すと図８のようなものになる。すなわち、各リンク（ノードである丸印の間の線）には、測定された走行位置に相当する点（矩形）がマッピングされており、各リンクにマッピングされた走行位置の数が、そのリンクの走行頻度ということになる。なお、図８の星マークは、以下で述べる車両別走行経路算出処理の対象となる、特定車両の計測位置の２点（始点及び終点）を示している。この２点間の経路を同定することになる。
【００３４】
そして、道路リンク別走行頻度算出部１０３は、正規化走行頻度算出のためのデータ抽出範囲に含まれる走行位置レコードを全て処理したか判断する（ステップＳ２５）。未処理の走行位置レコードが存在する場合にはステップＳ２１に戻る。
【００３５】
一方、正規化走行頻度算出のためのデータ抽出範囲に含まれる走行位置レコードを全て処理した場合には、正規化走行頻度算出部１０６の処理に移行する。
【００３６】
すなわち、正規化走行頻度算出部１０６は、道路リンク別走行頻度情報格納部１０４における未処理のリンクを１つ特定する（ステップＳ２７）。そして、該当レコードにおける頻度を、道路リンク番号に対応付けて道路地図ネットワーク情報格納部１０５に格納されているリンク距離で除することによって正規化走行頻度（すなわち、単位距離あたりの走行頻度）を算出し、正規化走行頻度情報格納部１０７に格納する（ステップＳ２９）。例えば、図９に示すようなデータが正規化走行頻度情報格納部１０７に格納される。図９の例では、道路リンク番号に対応付けて、正規化走行頻度が登録されるようになっている。なお、本実施の形態では単純に、走行頻度をリンク距離で除することによって正規化走行頻度を算出することとしているが、さらに他の情報を用いて正規化走行頻度を調整するようにしても良い。例えば、道路地図ネットワーク情報格納部１０５には、リンク毎に道路種別が登録されている。道路種別には、一般道、幹線、細街路のような種別が含まれ、例えば幹線の方が走行する可能性が高いものとして、例えば１以上の所定の係数を、正規化走行頻度に乗ずるようにしても良い。また、実際に速く走行できるリンクの方が利用可能性が高いので、過去の平均走行速度（例えば道路交通情報ＤＢ１１２に格納されているデータ）の高低により調整しても良い。
【００３７】
そして、正規化走行頻度算出部１０６は、道路リンク別走行頻度情報格納部１０４に登録されている全てのリンクについて処理したか判断する（ステップＳ３１）。未処理のリンクが存在する場合にはステップＳ２７に戻る。一方、全てのリンクについて処理した場合には、元の処理に戻る。
【００３８】
このような処理を実施することによって、各道路リンクについて比較可能な、プローブ車両が走行する可能性を表す評価値が算出されたことになる。
【００３９】
図４の処理の説明に戻って、車両別走行経路算出部１０９は、車両別走行経路算出処理を実施する（ステップＳ１１）。この車両別走行経路算出処理については、図１０乃至図１４を用いて説明する。なお、ステップＳ１１が終了すると処理は端子Ａを介して図１５の処理に移行する。
【００４０】
車両別走行経路算出部１０９は、平均走行時間算出のためのデータ抽出範囲に含まれる走行位置レコードを、車両毎且つ時間順にソートする（図１０：ステップＳ４１）。本実施の形態では、各車両について連続する２走行位置間の経路を同定する。しかしながら、データ抽出範囲で指定された時間内において、同一車両につき３以上の走行位置が特定される場合がある。以下の処理は、同一車両について、連続する２つの走行位置を１つずつずらしながら、それぞれの２走行位置間の経路を同定する。図１１に模式的に示すように、ＡからＣの順番で走行位置が得られた場合には、Ａ及びＢを第１セットとして最初に経路同定を実施し、次に、Ｂ及びＣを第２セットとして次に経路同定を実施する。
【００４１】
従って、車両別走行経路算出部１０９は、走行位置レコードのソート結果において未処理の車両を１つ特定する（ステップＳ４３）。そして、特定された車両についての走行位置レコードのうち未処理の連続レコードを時刻順に特定する（ステップＳ４５）。そして、特定された車両の特定された走行位置レコード及び道路地図ネットワーク情報格納部１０５に格納されているデータを用いて、走行経路算出処理を実施する（ステップＳ４７）。図８の例では、星印で示した始点から終点までの経路を算出する。本実施の形態では、図８で示した各リンクにおける正規化走行頻度の値に基づき、最も使用した可能性が高いと推定される経路上のリンクを特定する。走行経路算出処理の処理の詳細については後に詳述する。
【００４２】
ここでは２つの手法について、その概要を説明しておく。
【００４３】
［第１の走行経路算出処理］
図１２には、着目車両が、第１の時刻ｔ0から第２の時刻ｔ1の間に差し掛かっている地域付近の道路ネットワークを示している。着目車両が、時刻ｔ0に点Ｃ0（本実施の形態では、実際の測定位置ではなく、道路ネットワークにマッピングされているので「地点」とは呼ばず、「点」と呼ぶことにする）を通過し、時刻ｔ1に点Ｃ1を通過した（又は通過しつつある）ものとする。点Ｃ0と点Ｃ1の間の経路は、測定されていないので不明であり、以下のような考え方で経路同定を行う。
【００４４】
なお、図１２において、道路ネットワークにはノードＡ00乃至Ａ22が含まれており、リンクＢ00-01乃至Ｂ21-22も含まれている。リンク番号の付与の仕方は、例えば［発ノードのシリアル番号］−［着ノードのシリアル番号」となっている。また、図１２には示されていないが、リンクＢx-yの正規化走行頻度を、「ｂx-y」と表すものとする。
【００４５】
また、ノード間のリンクには上でも述べたように向きがあり、いずれかを「上り」とする場合には、逆方向を「下り」として特定できる。但し、図１２の例では、「上り」及び「下り」のいずれかのみを示している。ここでは、議論を単純化するため、図１２の矢印の向き（場所により、上り又は下りに対応）にのみ移動可能という前提で考える。
【００４６】
そして、本実施の形態では、ノードＡij上にいる（又はノードＡijを通過しつつある）場合に、その先は「ノードＡijを起点とするリンク」が到達している隣接ノードにしか移動できないものとする。例えば、ノードＡ11にいるとすると、その先はノードＡ12又はノードＡ21にしか移動できないものとする。すなわち、ノードＡ01及びＡ10へは移動できないものとする。
【００４７】
さらに、同じ仮定の下、（ノードＡ11から）ノードＡ12へ移動する可能性（場合によっては移動確率とも呼ぶ）Ｐ11-12は、「ｂ11-12／（ｂ11-12＋ｂ11-21）」であるものとする。すなわち、移動可能性のあるリンクＢ11-12及びＢ11-21の正規化走行頻度の総和に対するリンクＢ11-12についての正規化走行頻度の比率である。さらに、ノードＡ21へ移動する可能性Ｐ11-21は、「ｂ11-21／（ｂ11-12＋ｂ11-21）」であるものとする。すなわち、移動可能性のあるリンクＢ11-12及びＢ11-21の正規化走行頻度の総和に対するリンクＢ11-21についての正規化走行頻度の比率である。なお、ノード列で経路を特定しても良いが、以下で述べるように処理プロセスの最後の方でリンクに関わる値としてのリンクの平均走行速度を算出するので、リンク列で表している。但し、ノード列とリンク列とは道路地図ネットワーク情報格納部１０５のデータを用いれば容易に変換可能である。
【００４８】
なお、着目ノードＡ11から隣接ノードに繋がるリンクのいずれにおいても上で述べた正規化走行頻度ｂの値が０である場合には、Ａ11から先への移動は不可能となるため、これ以上の探索は行わない。
【００４９】
同様に、Ｃ0からＣ1までの多くの（又は全ての）リンクの正規化走行頻度ｂが０であり、ｂが０でないリンクのみを辿ってＣ0からＣ1に到達することが不可能である場合には、（本方式による）これらの点の間の経路同定は不可能であり、同定処理を終了するものとする。
【００５０】
そうすると、経路「リンクＢi0j0-i1j1（添字はｉ0ｊ0−ｉ1ｊ1を表す。以下同様とする。），Ｂi1j1-i2j2，．．．，Ｂi(n-1)j(n-1)-injn」上を移動する場合における経路選択可能性Ｐi0j0-i1j1-...-injnは、「可能性Ｐi0j0-i1j1・Ｐi1j1-i2j2・．．・Ｐi(n-1)j(n-1)-injn」で計算される。
【００５１】
例えば図１２で示した範囲を車両が走行する可能性のある範囲（この範囲については予め定められた妥当な範囲に設定する）であるとすると、図１２に示されているリンクであって上で述べたような引き返しやループを行わないという条件を満たすように選択した、点Ｃ0からＣ1までの連続リンク列で特定される複数の経路について、それぞれ経路選択可能性を算出する。そして最も経路選択可能性が大きな値となった経路を、本実施の形態における経路同定で特定された経路とする。
【００５２】
なお、具体的には、進行方向に点Ｃ0に隣接するノードＡ00から、進行方向とは逆方向に点Ｃ1に隣接するノードＡ22までの経路を見つけ出した後に、点Ｃ0が載っているリンクと、点Ｃ1が載っているリンクとを連結することによって、全体の経路が特定される。
【００５３】
このようにすれば、同じような時間などの条件において同じような種類のプローブ車両が通っていた可能性の最も高い経路を特定することができるようになる。
【００５４】
なお、上で述べた移動可能性Ｐの式については、各リンクについてそのリンクを走行する車両の平均速度がほぼ一定であるとみなした場合の式である。そもそも走行位置情報と共に、走行速度情報が採取でき、且つそのリンク毎の平均を求めることができる等の条件が成立し、且つリンク毎の車両の平均速度を考慮して、より正確に移動可能性Ｐの値を求める場合には、以下のような式を用いるものとする。（ｖi-jは、リンクＢi-jの平均速度である。）リンク毎の車両の平均速度については、例えば、道路交通情報ＤＢ１１２に格納されている過去のデータを用いればよい。
Ｐ11-12＝（ｂ11-12・ｖ11-12）／（ｂ11-12・ｖ11-12＋ｂ11-21・ｖ11-21）
Ｐ11-21＝（ｂ11-21・ｖ11-21）／（ｂ11-12・ｖ11-12＋ｂ11-21・ｖ11-21）
【００５５】
［第２の走行経路算出処理］
図１３には、着目車両が、第１の時刻ｔ1から第２の時刻ｔ2の間に差し掛かっている地域付近の道路ネットワークを示している。着目車両が、時刻ｔ1に点Ｃ1を通過し、時刻ｔ2に点Ｃ2を通過した（又は通過しつつある）ものとする。点Ｃ1と点Ｃ2の間の経路は、測定されていないので不明であり、以下のような考え方で経路同定を行う。
【００５６】
なお、図１３において、道路ネットワークにはノードＡ1乃至Ａ11が含まれており、リンクＢ1-2乃至Ｂ11-10も含まれている。リンク番号の付与の仕方は、例えば［発ノードのシリアル番号］−［着ノードのシリアル番号」となっている。また、図１３には示されていないが、リンクＢx-yの正規化走行頻度を、「ｂx-y」と表すものとする。
【００５７】
図１２とは異なり、ノード間に双方向のリンクが設定されている場合も考慮されている。
【００５８】
また、ノード間のリンクには上でも述べたように向きがあり、いずれかを「上り」とする場合には、逆方向を「下り」として特定できる。
【００５９】
そして、本実施の形態では、ノードＡi上にいる（又はノードＡiを通過しつつある）場合に、その先は「ノードＡiを起点とするリンク」が到達している隣接リンクにしか移動できないものとする。例えば、図１３におけるノードＡ5にいるとすると、その先はノードＡ2、Ａ4、Ａ6又はノードＡ9にしか移動できないものとする。
【００６０】
さらに、同じ仮定の下、ノードＡ5からノードＡ2、Ａ4、Ａ6及びＡ9へ移動する可能性（場合によっては移動確率とも呼ぶ）Ｐ5-2、Ｐ5-4、Ｐ5-6、Ｐ5-9は、それぞれ以下のように表される。
Ｐ5-2＝ｂ5-2／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
Ｐ5-4＝ｂ5-4／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
Ｐ5-6＝ｂ5-6／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
Ｐ5-9＝ｂ5-9／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
【００６１】
すなわち、移動可能性のあるリンクの正規化走行頻度の総和に対する注目リンクについての正規化走行頻度の比率である。
【００６２】
そうすると、経路「ノードＡi1，Ａi2，．．．，Ａin」上を移動する場合における経路選択可能性Ｐi1-i2-...-inは、「可能性Ｐi1-i2・Ｐi2-i3・．．・Ｐi(n-1)-in」で計算される。この経路選択可能性Ｐi1-i2-...-inが最大となる経路を、注目車両が実際に通過した経路とみなす。なお、ノード列で経路を特定しているが、リンク列で特定するようにしても良い。
【００６３】
また、例えばノードＡ5から隣接ノードに繋がるリンクのいずれにおいても、正規化走行頻度ｂ5-jが０である場合又は０に近いほど小さい場合には、Ａ5から先への移動は可能性が０ということで、それ以上経路同定を継続しない。
【００６４】
また、Ｃ1からＣ2までのリンクの正規化走行頻度が０又は０に近いほど小さく、現実的な経路長の範囲で経路同定を行うことができない状態、或いはそう見做せる状態であれば、（本方式による）経路同定処理を中止する。同様な考え方に基づき、Ｃ1からＣ2までのリンクの大部分の正規化走行頻度が０又は０に近いほど小さい場合に、（本方式による）経路同定処理を中止することもできる。
【００６５】
そして、既に通過しているノードを再度通過するような探索や、ループを構成するような探索については行わないものとする。但し、このような条件を満たしていれば、Ａ1、Ａ2、Ａ5と移動してきて、さらにＡ4、Ａ8、Ａ9、Ａ10というように、一見すると遠回りとなるような経路も考慮するものとする。
【００６６】
より具体的に経路選択可能性Ｐi1-i2-...-inが最大となる経路は、以下に述べる事項に従って得られる。
【００６７】
（ａ）図１３の各道路リンクＢi-jに対して、属性値Ｑi-j＝１／Ｐi-jを算出する。第１の走行経路算出処理の移動可能性の逆数を属性値として用いるものである。
【００６８】
（ｂ）点Ｃ1から点Ｃ2までの経路のうち、自明である点Ｃ1からノードＡ1まで、ノードＡ11から点Ｃ2までを除き、ノードＡ1からＡ11までの経路を探索する。
【００６９】
（ｃ）この際、Ｑi1-i2-...-in＝Ｑi1-i2・Ｑi2-i3・．．・Ｑi(n-1)-inが最小となるような経路を特定する。
【００７０】
（ｄ）そのため、Ｆ（ｉj）を、出発ノードＡi1（ｉ1＝１）からＡijに至る経路のうちＱi1-i2-...-ijが最小の値を取る経路におけるＱi1-i2-...-ijの値であるとする。なお、Ｆ（ｉ1）＝Ｆ（１）＝１であるとする。
【００７１】
（ｅ）そして、Ａi1（＝Ａ1）からはじめて、
【００７２】
【数１】
Ｆ（ｉ’1），Ｆ（ｉ’2），．．．，Ｆ（ｉ’m）（ここでｉ’1＝ｉ1）を、この順に、Ａin（＝Ａ11）まで計算してゆく。（ｉ’m＝ｉnである。ｉ’mは初めから知ることはできない。Ｆ（ｉ’1），Ｆ（ｉ’2），．．．，Ｆ（ｉ’n）を順に求めてゆき、ｉnに一致するｉ’mに到達した時点で、ｉ’mを知ることができる。）ここでＦ（ｉ’1）≦Ｆ（ｉ’2）≦．．．≦Ｆ（ｉ’n）である。
【００７３】
Ｆ（ｉ’1），Ｆ（ｉ’2），．．．，Ｆ（ｉ’n）は、詳細には、次のように求めてゆく。まずＦ（ｉ’1）（すなわちＦ（ｉ1））は、上記のようにＦ（ｉ1）＝Ｆ（１）＝１であることから１である。（すなわちＦ（ｉ’1）＝Ｆ（ｉ1）＝１である。）次にＦ（ｉ’2）を求めるが、この段階では、ノードＡi'1（ｉ’1は式（１）のｉ’jに対応）に隣接するノード（すなわち１つのリンクを介してＡi'1につながるノード）の中で、式（１）のＦ（ｉ’k）の値が最小となるようなノードＡi'k（「式（１）のＦ（ｉ’k）の値が最小となるようなｉ’k」に対応する（そのようなｉ’kを添字として持つ）ノードＡi'k）を選び、それをＡi'2とする。この時、Ａi'1からＡi'2に至る経路のうち、Ｑi'1-i'2が最小となる経路におけるＱi'1-i'2の値がＦ（ｉ’2）である。（ここに述べたことから分かるように、Ａi'2とＦ（ｉ’2）は、相互に対応するものと捉えることができる。）次にＦ（ｉ’3）を求めるが、この段階では、既に到達したノード（ここではＡi'1、Ａi'2（ｉ’1、ｉ’2は、式（１）のｉ’jに対応））のいずれかに隣接するノード（但し未到達のノード）の中で、式（１）のＦ（ｉ’k）の値が最小となるようなノードＡi'k（「式（１）のＦ（ｉ’k）の値が最小となるようなｉ’k」に対応するノードＡｉ’k）を選び、それをＡi'3とする。この時、Ａi'1からＡi'3に至る経路のうち、Ｑi'1-...-i'3が最小となる経路におけるＱi'1-...-i'3の値がＦ（ｉ’3）である。（Ａi'3とＦ（ｉ’3）は、相互に対応するものと捉えることができる。）
【００７４】
以下、順次、既に到達したノードのいずれかに隣接するノード（但し未到達のノード）の中で、式（１）のＦ（ｉ’k）の値が最小となるようなノードＡi'k（「式（１）のＦ（ｉ’k）の値が最小となるようなｉ’k」に対応するノードＡi'k）を求めてゆき、それに対応するＦ（ｉ’k）を求めてゆく。以上のことは、最終到達ノード（すなわちＡin）に到達するまで続ける。
【００７５】
（ｆ）その結果、Ｑi1-i2-...-in（ｉ1＝１，ｉｎ＝１１）が最小になる経路を特定する。Ｑi1-i2-...-inの添字ｉ1，ｉ2，．．．，ｉnの値は、（ｅ）で最終的に求めたＱi'1-...i'mの添字ｉ’1，．．．，ｉ’mを参照して知る。「ｉ1，ｉ2，．．．，ｉn」と「ｉ’1，．．．，ｉ’m」において、（左から数えて）同じ位置にあるものの値同士は等しい。
【００７６】
（ｇ）この経路の前に点Ｃ1からノードＡ1の経路を、後にノードＡ11から点Ｃ2までの経路を連結すれば、点Ｃ1から求めるべき点Ｃ2までの経路同定の結果となる。
【００７７】
以上のような処理を実施する場合においても、過去のプローブ車両の走行実績から今回のプローブ車両も採用した可能性が高い経路を同定することができるようになる。
【００７８】
なお、上で述べた移動可能性Ｐの式については、各リンクについてそのリンクを走行する車両の平均速度が一定であるとみなした場合の式である。そもそも、走行位置情報と共に、走行速度情報が採取でき、且つそのリンク毎の平均を求めることができる等の条件が成立して、リンク毎の車両の平均速度を考慮できる場合には、以下のような式を用いるものとする。リンク毎の車両の平均速度については、例えば、道路交通情報ＤＢ１１２に格納されている過去のデータを用いればよい。なお、リンクＢi-jの平均速度をｖi-jとすると、例えばＰ5-2、Ｐ5-4、Ｐ5-6、Ｐ5-9は以下のように表される。
Ｐ5-2＝(ｂ5-2・ｖ5-2)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
Ｐ5-4＝(ｂ5-4・ｖ5-4)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
Ｐ5-6＝(ｂ5-6・ｖ5-6)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
Ｐ5-9＝(ｂ5-9・ｖ5-9)/(ｂ5-2・ｖ5-2＋ｂ5-4・ｖ5-4＋ｂ5-6・ｖ5-6＋ｂ5-9・ｖ5-9)
【００７９】
この処理の結果、例えば図１４に示すような車両別走行リンクテーブルが、車両別走行リンク情報格納部１１０に格納されるようになる。図１４の例では、車両ＩＤと、処理に係る２走行位置レコードのうち時間的に先の走行位置レコードに含まれる時刻である発時刻と、処理に係る２走行位置レコードのうち時間的に後の走行位置レコードに含まれる時刻である着時刻と、経路同定で特定されたリンク列（リンク１乃至３．．．）とが登録されるようになっている。なお、リンク列のうち最初と最後のリンクについては、注目している車両はそれらのリンク個々において全ての区間は走行していない可能性がある。また、同一車両についてのレコードが複数登録されている場合もある。
【００８０】
図１０の説明に戻って、車両別走行経路算出部１０９は、特定された車両の走行位置レコードを全て処理したか判断する（ステップＳ４９）。特定された車両について未処理の走行位置レコードのペアが存在する場合にはステップＳ４５に戻る。
【００８１】
一方、特定された車両について全ての走行位置レコードを処理した場合には、車両別走行経路算出部１０９は、平均走行時間算出のためのデータ抽出範囲に含まれる走行位置レコードに係る全ての車両について処理したか判断する（ステップＳ５１）。未処理の車両が残っている場合にはステップＳ４３に戻る。一方、全ての車両について処理した場合には、元の処理に戻る。元の処理に戻ると端子Ａを介して図１５の処理に移行する。
【００８２】
図１５の処理の説明に移行して、道路リンク別平均走行時間算出部１１１は、車両及び道路リンク別走行時間算出処理を実施する（ステップＳ６１）。この車両及び道路リンク別走行時間算出処理については、図１６及び図１７を用いて説明する。
【００８３】
道路リンク別平均走行時間算出部１１１は、図１４に示したような車両別走行リンクテーブルにおいて、未処理のレコードを１つ特定する（ステップＳ７１）。そして、特定されたレコードに登録されている各リンクの距離（＝長さ）を道路地図ネットワーク情報格納部１０５から読み出し、当該各リンクの距離に応じて発時刻から着時刻までの時間を各リンクに割り振り、各リンクに対応付けて時間を道路交通情報ＤＢ１１２に登録する（ステップＳ７３）。（そもそも、走行位置情報と共に、走行速度情報が採取でき、且つそのリンク毎の平均を求めることができる等の条件が成立する場合は、発時刻から着時刻までの時間を各リンクに割り振る際、リンク毎にリンク長を平均速度で除した値を求め、その比に従って割り振っても良い。）上でも述べたように、注目車両は、両端のリンクについては、それらのリンクの全てを走行しているわけではない。従って、両端のリンクの影響を除去するか、又は無視する。
【００８４】
具体的には、前者であれば、例えばマップマッチングで走行位置の対応付けを行った際に、対応付けされたリンク上のどの位置で対応付けられたかを保持しておく。そして、経路同定がなされた後に、始点から進行方向で当該始点に隣接するノードまでの距離と、終点から当該終点に進行方向とは逆方向で隣接するノードまでの距離と、両端リンク以外の各リンクの距離とで、発時刻から着時刻までの時間を按分する。但し、始点から当該始点に隣接するノードまでの距離のための時間と、終点から当該終点に隣接するノードまでの距離のための時間とは、以下の処理では用いない。また、後者であれば、両端リンク以外の各リンクの距離で、発時刻から着時刻までの時間を按分する。多少各リンクに割り振られる時間が長くなるが、処理は簡単で高速であり、以下の処理で平均化するので精度的に問題ない場合もある。
【００８５】
このような処理を実施することにより、図１７に示すようなデータが道路交通情報ＤＢ１１２に格納される。図１７の例では、リンクＩＤに対応付けられて所要時間が登録されている。
【００８６】
そして、道路リンク別平均走行時間算出部１１１は、車両別走行リンクテーブルにおける全てのレコードについて処理したか判断する（ステップＳ７５）。未処理のレコードが存在する場合にはステップＳ７１に戻る。一方、全てのレコードを処理した場合には、元の処理に戻る。
【００８７】
このような処理を実施することによって、各車両が走行した各リンクについて要した走行時間を特定することができるようになる。
【００８８】
図１５の処理の説明に戻って、道路リンク別平均走行時間算出部１１１は、道路交通情報ＤＢ１１２に登録されているテーブル（図１７）を用いてリンク別平均走行時間算出処理を実施する（ステップＳ６３）。リンク別平均走行時間算出処理については、図１８及び図１９を用いて説明する。
【００８９】
まず、道路リンク別平均走行時間算出部１１１は、道路交通情報ＤＢ１１２に登録されているテーブル（図１７）において、リンクＩＤでレコードをソートする（ステップＳ８１）。そして、未処理のリンクＩＤを１つ特定する（ステップＳ８３）。そして、特定されたリンクＩＤについての全てのレコードを、上で述べたテーブルから抽出する（ステップＳ８５）。その後、抽出レコード数をカウントすると共に、時間の総和を算出し、当該時間の総和を抽出レコード数で除することによって、処理に係るリンクについての平均走行時間を算出し、道路交通情報ＤＢ１１２に登録する（ステップＳ８７）。
【００９０】
例えば、図１９に示すようなデータが道路交通情報ＤＢ１１２に登録される。図１９の例では、リンクＩＤに対応付けて平均走行時間が登録されている。このように平均走行時間が得られれば、この数値の大小によってスムーズに流れているリンクや、渋滞が発生しているようなリンクを容易に特定できるようになる。
【００９１】
そして、道路リンク別平均走行時間算出部１１１は、図１７のようなテーブルにおいて全てのリンクＩＤについて処理したか判断する（ステップＳ８９）。未処理のリンクＩＤが存在している場合にはステップＳ８３に戻る。一方、全てのリンクＩＤを処理した場合には、元の処理に戻る。
【００９２】
このような処理を実施することによって、道路状況を把握するための基本的なデータを得ることができる。
【００９３】
図１５の処理の説明に戻って、出力部１１３は、道路交通情報ＤＢ１１２に格納されている各リンクについての平均走行時間を、表示装置や印刷装置などの出力装置に出力する（ステップＳ６５）。図１９のようなテーブルをそのまま出力しても良いが、例えば道路地図ネットワーク情報格納部１０５から道路ネットワークのデータを読み出して、道路ネットワークを表示すると共に、例えば各リンクに関連付けて平均走行時間を表示するようにしても良い。さらに、平均走行時間のランク付けを行って、道路ネットワークにおいてランク付けに応じてリンクの色分けを行って表示するようにしても良い。
【００９４】
なお、出力部１１３は、例えばプローブ車両以外の車両にデータを配信するような処理部であってもよい。さらにＷｅｂサーバのようにアクセスに応じてデータを送信するようにしても良い。
【００９５】
［第１の走行経路算出処理の詳細］
上では概略のみを示したが、ここで処理フローを図２０及び図２１を用いて説明しておく。まず、車両別走行経路算出部１０９は、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、始点Ｃ0から進行方向で隣接するノードＡ00と、終点Ｃ1から進行方向とは逆方向で隣接するノードＡ22とを特定する（図２０：ステップＳ１０１）。そして、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、Ａ00からＡ22までの第１経路探索処理を実施する（ステップＳ１０３）。この第１経路探索処理については、図２１を用いて説明する。
【００９６】
第１の走行経路算出処理においては、図１２に示したように、一定の範囲に探索範囲を限定すると共に、引き返したり、迂回したり、ループしたりするような経路を除外した形で、全経路を特定するような探索方法を採用している。
【００９７】
具体的には、まず、車両別走行経路算出部１０９は、Ａ00からＡ22までの全経路を探索する（図２１：ステップＳ１１１）。図１２の例では、（１）Ａ00、Ａ01、Ａ02、Ａ12、Ａ22、（２）Ａ00、Ａ01、Ａ11、Ａ12、Ａ22、（３）Ａ00、Ａ01、Ａ11、Ａ21、Ａ22、（４）Ａ00、Ａ10、Ａ11、Ａ12、Ａ22、（５）Ａ00、Ａ10、Ａ11、Ａ21、Ａ22、（６）Ａ00、Ａ10、Ａ20、Ａ21、Ａ22というように６通りの経路が探索される。
【００９８】
そして、車両別走行経路算出部１０９は、全ての経路について移動可能性Ｐ00-・・・-22を算出し、当該値が最大となる経路を選択する（ステップＳ１１３）。６通りの経路のうちいずれか１つを選択する。そして元の処理に戻る。
【００９９】
図２０の説明に戻って、車両別走行経路算出部１０９は、始点Ｃ0からＡ00までの経路と、Ａ22から終点Ｃ1までの経路とをステップＳ１０３における経路探索結果に連結して、経路同定結果を車両別走行リンク情報格納部１１０に格納する（ステップＳ１０５）。
【０１００】
このような処理を実施することによって、処理に係る車両が走行した可能性の最も高い経路が同定されたことになる。
【０１０１】
［第２の走行経路算出処理の詳細］
第２の走行経路算出処理についても、ここで処理フローを図２２乃至図２５を用いて説明しておく。
【０１０２】
まず、車両別走行経路算出部１０９は、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、始点Ｃ1から進行方向で隣接するノードＡ1と、終点Ｃ2から進行方向とは逆方向で隣接するノードＡ11とを特定する（ステップＳ１２１）。そして、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、ノードＡ1からＡ11までの第２経路探索処理を実施する（ステップＳ１２３）。第２経路探索処理については、図２３乃至図２５を用いて説明する。
【０１０３】
車両別走行経路算出部１０９は、探索回数のカウンタであるｋを１に初期化し（図２３：ステップＳ１３１）、遷移先ノードＡikの添え字ｉkに開始ノードＡ1に対応する「１」をセットする（ステップＳ１３３）。さらに、遷移先ノードＡik＝Ａ1とセットする（ステップＳ１３５）。このデータについては、車両別走行リンク情報格納部１１０の探索テーブルに格納する。
【０１０４】
そして、車両別走行経路算出部１０９は、遷移先ノードＡikが終了ノードＡ11であるかどうか判断する（ステップＳ１３７）。このように、遷移先ノードＡikが終了ノードＡ11に到達した場合には、そこで探索を終了する。
【０１０５】
上で述べたように、図１３の例で例えばノードＡ5からノードＡ2への（リンクＢ5-2を通った）移動可能性Ｐ5-2は以下のとおりである。
Ｐ5-2＝ｂ5-2／（ｂ5-2＋ｂ5-4＋ｂ5-6＋ｂ5-9）
このように移動可能性Ｐは、０以上１以下の値になる。そして属性値Ｑ5-2は、１／Ｐ5-2であるので、属性値Ｑ5-2は必ず１以上の実数となる。（但しＰ5-2が０の時Ｑ5-2は∞となる。）従って、遷移先ノードにおける総合の評価値を表す（１）式の値は必ず増加する（または等しい値のままである）。ステップＳ１３７で示すような探索終了条件を用いれば、（１）式の値ができるだけ小さな値になる（留る）ようなノード（経路）を順次求めて行くことによって、ノードＡ1からノードＡ11迄の、（１）式が最小の値となるような経路を求めることができる。
【０１０６】
多くの場合、そして少なくともこの例の場合、最初に実行する際にはステップＳ１３７の条件を満たすことはないので、遷移先ノードＡikが終了ノードＡ11ではないと判断され、車両別走行経路算出部１０９は、ｋを１インクリメントし（ステップＳ１３９）、（１）式によってｉk及びAikを決定し、例えば車両別走行リンク情報格納部１１０の探索テーブルに格納する（ステップＳ１４１）。そして、ステップＳ１３７に戻る。
【０１０７】
このようにステップＳ１３７乃至Ｓ１４１をステップＳ１３７の条件を満たすようになるまで繰り返す。車両別走行リンク情報格納部１１０の探索テーブルは、例えば図２５に示すようなテーブルである。すなわち、ｋと、ｉkと、遷移先ノードＡikと、遷移先ノードＡikに到達する直前のノード（探索元のノード）Ｍikとが登録されるようになっている。
【０１０８】
ここでは図１３と同じ道路ネットワークを今回の探索を説明するために図２４に示す。図２４においてノード付近に示された括弧付きの数字は、図２５の探索テーブルのｋの値と一致している。ｋ＝１の場合には、上で述べたように、ｉk＝１でＡik＝Ａ1となる（図２５の第１行）。ｋ＝２となると、（新たな探索の起点となり得る）探索元ノードは、探索テーブルにおける遷移先ノードＡikの列に既に登録されているノードＡ1であり（この場合、既に登録されているのはＡ1のみである）、このノードから（１）式によって得られる。すなわち、Ｆ(1)＝１と遷移の属性値Ｑ（「遷移に対応するリンク」の属性値Ｑ）との積が最も小さくなるようなノードを探索する。ｋ＝２の段階では、遷移先の候補となるのはＡ2とＡ4であるが、ここではＡ2の方がその遷移の属性値Ｑが小さいので採用され、ｉ2＝２、Ａi2＝Ａ2と特定され、図２５の探索テーブルの２行目に登録される。なお、Ｍi2は探索元ノードＡ1である。また、Ｆ(2)については、Ｆ(2)＝Ｆ(1)＊Ｑ1-2である。Ｆ(4)についてはこの段階ではＦ(4)＝Ｆ(1)＊Ｑ1-4である。Ｆ(2)及びＦ(4)の値については以下の処理で用いるので保持しておく。また、（図２５の探索テーブルに（少なくともこの段階で）登録されていない）Ａ4については、Ａ4が遷移先候補として取上げられたということ（事実）、及びＡ4の探索元が（この段階で）Ａ1であることを、以下の処理のための情報として、保持しておく。
【０１０９】
ｋ＝３となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ1及びノードＡ2となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(1)＝１と遷移の属性値Ｑとの積及びＦ(2)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝３の段階では、遷移先ノードの候補は、Ａ3、Ａ4、Ａ5である。そうすると、Ｆ(4)、Ｆ(5)＝Ｆ(2)＊Ｑ2-5、Ｆ(3)＝Ｆ(2)＊Ｑ2-3の三者を比較することになるが、（この例では）Ｆ(4)が最小であるとして、ノードＡ4が選択される。（Ｆ(5)、Ｆ(3)は、ここで新たに算出するが、Ｆ(4)はｋ＝２の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの３行目には、ｉk＝４、Ａik＝Ａ4、Ｍik＝Ａ1が登録される。Ｆ(4)、Ｆ(5)、Ｆ(3)の値については保持しておく。また、Ａ3、Ａ5については、Ａ3、Ａ5が遷移先候補として取上げられたということ、及びＡ3、Ａ5の探索元が（この段階で）Ａ2であることを、以下の処理のための情報として保持しておく。
【０１１０】
ｋ＝４となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ2及びノードＡ4となる。ノードＡ1は全ての可能な遷移先ノードについて探索テーブルのＡikの列に登録されてしまったので（新たな探索の起点となり得る）探索元ノードから外れる。これらのノードから（１）式によって得られるノード、すなわち、Ｆ(2)と遷移の属性値Ｑとの積及びＦ(4)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝４の段階では、遷移先ノードの候補は、Ａ3、Ａ5、Ａ8である。そうすると、ノードＡ2経由のＦ(5)（＝Ｆ(2)＊Ｑ2-5）、ノードＡ4経由のＦ(5)＝Ｆ(4)＊Ｑ4-5、Ｆ(3)、Ｆ(8)＝Ｆ(4)＊Ｑ4-8とを比較して、ノードＡ2経由のＦ(5)が最小であるとして、ノードＡ5が選択される。（「Ａ4経由のＦ(5)」、Ｆ(8)は、ここで新たに算出するが、「Ａ2経由のＦ(5)」、Ｆ(3)は、ｋ＝３の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの４行目には、ｉk＝５、Ａik＝Ａ5、Ｍik＝Ａ2が登録される。Ｆ(3)、Ｆ(4)、ノードＡ2経由のＦ(5)、Ｆ(8)の値については保持しておく。（Ｆ(5)については、このＡ2経由の値が、この段階で（更新を最大に施した）最新のものであると考える。）
【０１１１】
ｋ＝５となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ2、ノードＡ4及びノードＡ5となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(2)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積及びＦ(5)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝５の段階では、遷移先ノードの候補は、Ａ3、Ａ6、Ａ8、Ａ9である。そうすると、Ｆ(3)、Ｆ(6)＝Ｆ(5)＊Ｑ5-6、Ｆ(9)＝Ｆ(5)＊Ｑ5-9、Ｆ(8)とを比較することになるが、ノードＡ2経由のＦ(3)が最小であるとして、ノードＡ3が選択される。（Ｆ(6)、Ｆ(9)は、ここで新たに算出するが、Ｆ(3)、Ｆ(8)は、ｋ＝４の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの５行目には、ｉk＝３、Ａik＝Ａ3、Ｍik＝Ａ2が登録される。Ｆ(3)、ノードＡ2経由のＦ(5)、ノードＡ5経由のＦ(6)、Ｆ(8)、Ｆ(9)の値については保持しておく。また、Ａ6、Ａ9については、Ａ6、Ａ9が遷移先候補として取上げられたということ、及びＡ6、Ａ9の探索元が（この段階で）Ａ5であることを以下の処理のための情報として保持しておく。
【０１１２】
ｋ＝６となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ4、ノードＡ5、ノードＡ3となる。ノードＡ2は全ての可能な遷移先ノードについて探索テーブルのＡikの列に登録されてしまったので探索元ノードから外れる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑの積及びＦ(3)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝６の段階では、遷移先ノードの候補は、Ａ7、Ａ6、Ａ8、Ａ9である。そうすると、Ｆ(7)＝Ｆ(3)＊Ｑ3-7、Ｆ(6)、Ｆ(9)、Ｆ(8)とを比較して、ノードＡ5経由のＦ(9)が最小であるとして、ノードＡ9が選択される。Ｆ(7)は、ここで新たに算出するが、Ｆ(6)、Ｆ(9)、Ｆ(8)は、ｋ＝５の場合迄の処理で算出済みのものを用いる。従って、探索テーブルの６行目には、ｉk＝９、Ａik＝Ａ9、Ｍik＝Ａ5が登録される。ノードＡ5経由のＦ(6)、Ｆ(7)、ノードＡ4経由のＦ(8)、ノードＡ5経由のＦ(9)の値については保持しておく。また、Ａ7については、Ａ7が遷移先候補として取上げられたということ、及びＡ7の探索元が（この段階で）Ａ3であることを、以下の処理のための情報として、保持しておく。
【０１１３】
ｋ＝７となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ3、ノードＡ4、ノードＡ5、ノードＡ9となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(3)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑの積及びＦ(9)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝７の段階では、遷移先ノードの候補は、Ａ7、Ａ6、ノードＡ4経由のＡ8、ノードＡ9経由のＡ8、ノードＡ9経由のＡ4、Ａ10である。そうすると、Ｆ(7)、Ｆ(6)、Ｆ(10)＝Ｆ(9)＊Ｑ9-10、Ｆ(8)（＝Ｆ(4)＊Ｑ4-8）と、Ｆ(8)＝Ｆ(9)＊Ｑ9-8を比較して、ノードＡ9経由のＦ(10)が最小であるとして、ノードＡ10が選択される。（Ｆ(10)、「Ａ9経由のＦ(8)」は、ここで新たに算出するが、Ｆ(7)、Ｆ(6)、「Ａ4経由のＦ(8)」は、ｋ＝６の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの７行目には、ｉk＝１０、Ａik＝Ａ10、Ｍik＝Ａ9が登録される。ノードＡ5経由のＦ(6)、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(8)、ノードＡ9経由のＦ(4)、Ｆ(7)、Ｆ(10)の値については保持しておく。また、Ａ10については、Ａ10が遷移先候補として取上げられたということ、及びＡ10の探索元が（この段階で）Ａ9であることを、以下の処理のための情報として、保持しておく。
【０１１４】
ｋ＝８となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ3、ノードＡ4、ノードＡ5、ノードＡ10、ノードＡ9となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(3)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑとの積、Ｆ(9)と遷移の属性値Ｑの積及びＦ(10)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝８の段階では、遷移先ノードの候補は、Ａ7、ノードＡ5経由のＡ6、ノードＡ4経由のＡ8、ノードＡ9経由のＡ8、ノードＡ10経由のノードＡ6、Ａ11である。そうすると、Ｆ(7)、ノードＡ5経由のＦ(6)（＝Ｆ(5)＊Ｑ5-6）、ノードＡ10経由のＦ(6)＝Ｆ(10)＊Ｑ10-6、Ｆ(11)＝Ｆ(10)＊Ｑ10-11、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(4)、ノードＡ9経由のＦ(8)を比較して、ノードＡ9経由のＦ(8)が最小であるとして、ノードＡ8が選択される。（「Ａ10経由のＦ(6)」、Ｆ(11)は、ここで新たに算出するが、Ｆ(7)、「Ａ5経由のＦ(6)」、「Ａ4経由のＦ(8)」、「Ａ9経由のＦ(8)」は、ｋ＝７の場合迄の処理で算出済みのものを用いる。）従って、探索テーブルの８行目には、ｉk＝８、Ａik＝Ａ8、Ｍik＝Ａ9が登録される。ノードＡ5経由のＦ(6)、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(8)、Ｆ(7)、ノードＡ9経由のＦ(4)、ノードＡ10経由のＦ(6)、Ｆ(11)の値については保持しておく。また、Ａ11については、Ａ11が遷移先候補として取上げられたということ、及びＡ11の探索元が（この段階で）Ａ10であることを、以下の処理のための情報として、保持しておく。
【０１１５】
ｋ＝９となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ3、ノードＡ5、ノードＡ10となる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(3)と遷移の属性値Ｑとの積、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑとの積、Ｆ(9)と遷移の属性値Ｑの積、Ｆ(8)と遷移の属性値Ｑの積及びＦ(10)と遷移の属性値Ｑの積のうち値が最も小さくなるようなノードを探索する。ｋ＝９の段階では、遷移先ノードの候補は、Ａ7、ノードＡ10経由又はノードＡ5経由のＡ6、ノードＡ4経由のＡ8、ノードＡ9経由又はノードＡ8経由のＡ4、Ａ11である。そうすると、Ｆ(7)、ノードＡ5経由のＦ(6)、ノードＡ10経由のＦ(6)、Ｆ(11)、Ｆ(8)と、ノードＡ9経由のＦ(4)、ノードＡ8経由のＦ(4)＝Ｆ(8)＊Ｑ8-4を比較して、ノードＡ3経由のＦ(7)が最小であるとして、ノードＡ7が選択される。「Ａ8経由のＦ(4)」は、ここで新たに算出するが、Ｆ(7)、「Ａ5経由のＦ(6)」、「Ａ10経由のＦ(6)」、Ｆ(11)、Ｆ(8)、「Ａ9経由のＦ(4)」は、ｋ＝８の場合迄の処理で算出済みのものを用いる。従って、探索テーブルの９行目には、ｉk＝７、Ａik＝Ａ7、Ｍik＝Ａ3が登録される。ノードＡ5経由のＦ(6)、ノードＡ10経由のＦ(6)、ノードＡ4経由のＦ(8)、ノードＡ8経由のＦ(4)、ノードＡ9経由のＦ(4)、Ｆ(7)、ノードＡ10経由のＦ(11)の値については保持しておく。
【０１１６】
ｋ＝１０となると、（新たな探索の起点となり得る）探索元ノードは、ノードＡ4、ノードＡ5、ノードＡ10、ノードＡ9、ノードＡ8、Ａ7となる。ノードＡ3については、遷移先ノードが全てＡikに登録されたので探索元ノードから外れる。これらのノードから（１）式を用いて次の遷移先ノードを探索する。すなわち、Ｆ(4)と遷移の属性値Ｑとの積、Ｆ(5)と遷移の属性値Ｑとの積、Ｆ(9)と遷移の属性値Ｑの積、Ｆ(8)と遷移の属性値Ｑの積、Ｆ(10)と遷移の属性値Ｑの積及びＦ(7)と遷移の属性値Ｑとの積のうち値が最も小さくなるようなノードを探索する。ｋ＝１０の段階では、遷移先ノードの候補は、ノードＡ10経由、ノードＡ7経由又はノードＡ5経由のＡ6、ノードＡ4経由のＡ8、ノードＡ9経由又はノードＡ8経由のＡ4、ノードＡ7経由又はノードＡ10経由のＡ11である。そうすると、ノードＡ5経由のＦ(6)（＝Ｆ(5)＊Ｑ5-6）、ノードＡ7経由のＦ(6)＝Ｆ(7)＊Ｑ7-6、ノードＡ10経由のＦ(6)（＝Ｆ(10)＊Ｑ10-6）、ノードＡ10経由のＦ(11)（＝Ｆ(10)＊Ｑ10-11）、ノードＡ4経由のＦ(8)、ノードＡ9経由のＦ(4)、ノードＡ8経由のＦ(4)、ノードＡ7経由のＦ(11)＝Ｆ(7)＊Ｑ7-11を比較して、ノードＡ10経由のＦ(11)が最小であるとして、ノードＡ11が選択される。「Ａ7経由のＦ(6)」、「Ａ7経由のＦ(11)」は、ここで新たに算出するが、「Ａ5経由のＦ(6)」、「Ａ10経由のＦ(6)」、「Ａ10経由のＦ(11)」、「Ａ4経由のＦ(8)」、「Ａ9経由のＦ(4)」、「Ａ8経由のＦ(4)」は、ｋ＝９の場合迄の処理で算出済みのものを用いる。従って、探索テーブルの１０行目には、ｉk＝１１、Ａik＝Ａ11、Ｍik＝Ａ10が登録される。
【０１１７】
このようにｋ＝１０になると、Ａik＝Ａ11となってステップＳ１３７の条件を満たすことになる。ステップＳ１３７の条件を満たしたと判断されると、車両別走行経路算出部１０９は、探索テーブルにおいて、Ａikの列のＡ11から直前ノードＭikを辿ってＡ1までノード列を特定し、逆順でＡ1からＡ11まで並べ替えて目的の経路を特定する（ステップＳ１４３）。以下の処理では、リンク列が必要となるので、道路地図ネットワーク情報格納部１０５に格納されているデータに基づき、リンク列に変換する。そして元の処理に戻る。
【０１１８】
図２５の探索テーブルの例では、１０行目のＭik＝Ａ10から、Ａikの列にＡ10が出現する行を探索すると、７行目であることが分かる。この７行目のＭik＝Ａ9から、Ａikの列にＡ9が出現する行を探索すると、６行目であることが分かる。この６行目のＭik＝Ａ5から、Ａikの列にＡ5が出現する行を探索すると、４行目であることが分かる。この４行目のＭik＝Ａ2から、Ａikの列にＡ2が出現する行を探索すると、２行目であることが分かる。この２行目のＭik＝Ａ1から、開始ノードまで辿ることができたことになる。従って、Ａ11、Ａ10、Ａ9、Ａ5、Ａ2、Ａ1というノード列から、Ａ1、Ａ2、Ａ5、Ａ9、Ａ10、Ａ11が求めるべき経路（図２４の太一点鎖線）である。
【０１１９】
なお、ノードＡ6については、遷移先ノードとして特定されることがなかった。これは、上で述べたように属性値Ｑの特性からしてＱ6-11がどのような値であってもこのノードＡ6を経由すると必ず（１）式の値は他の経路の場合より大きくなるためである。
【０１２０】
このような処理を実施することによって、（１）式を用いて次の遷移先ノードを探索されるノード、すなわち、探索元ノードまでの累積属性値と、その探索元ノードから候補ノードまでの属性値Ｑとの積が最も小さくなるような候補ノードが遷移先ノードとして選択され、走行可能性が最も高い経路が特定されるようになる。
【０１２１】
図２２の説明に戻って、車両別走行経路算出部１０９は、始点Ｃ1からＡ1までの経路と、Ａ11から終点Ｃ2までの経路とをステップＳ１２３における経路探索結果に連結して経路同定結果を、車両別走行リンク情報格納部１１０に格納する（ステップＳ１２５）。
【０１２２】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図１に示したプローブ道路交通情報システム１００の機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成と一致しない場合もある。
【０１２３】
さらに、処理フローについても処理結果が変わらない限りにおいて処理順番を入れ替えたり、並列に実行したりするようにしても良い。
【０１２４】
さらに、上で述べた機能を全て１台のコンピュータで実施しなければならないわけではなく、複数台のコンピュータで実現するようにしても良い。
【０１２５】
なお、上で述べたプローブ道路交通情報システム１００は、コンピュータ装置であって、図２６に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１２６】
以上本実施の形態をまとめると以下のようになる。
【０１２７】
本車両走行位置データ処理方法は、計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、計測時刻と車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、読み出された車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおけるノード及びリンクの位置データ及びリンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている複数のリンクのうち車両走行位置データ・レコードの車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、複数のリンクの各々について、頻度カウンタの値を道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、正規化走行頻度データ格納部に格納されている各リンクの正規化走行頻度の値に基づき、走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップとを含む。
【０１２８】
このように過去の走行実績から算出される各リンクの正規化走行頻度に基づき、各リンクについて車両走行の蓋然性が分かるようになるので、２地点間で最も蓋然性が高いリンクの組み合わせである走行経路が特定できる。すなわち、走行中の車両で計測される走行位置を離散的にしか得られない場合であっても、当該計測された走行位置間の過去の走行経路を同定することができる。
【０１２９】
また、本車両走行位置データ処理方法は、２つの車両走行位置データ・レコードで特定される２地点間の走行時間を、車両別走行リンク情報格納部に格納されている走行経路に含まれる各経路上リンクに、道路地図ネットワーク情報格納部に格納されている経路上リンクの長さデータ（又は長さデータを平均速度データで除した値）を基に振り分け、経路上リンクの識別子に対応付けて振り分けられた走行時間を時間推定結果格納部に格納するステップをさらに含むようにしても良い。同定された走行経路に含まれる各経路上リンクについて、特定の時間における所要走行時間を得ることができるようになる。これにより例えば渋滞の発生などを認識することができるようになる。
【０１３０】
さらに、本車両走行位置データ処理方法は、時間推定結果格納部に格納されている経路上リンクの識別子毎に、対応する走行時間の平均値を算出し、時間推定結果格納部に格納するステップをさらに含むようにしても良い。このように各経路上リンクについて、所要走行時間の平均値を算出することにより、各道路について走行状態の概要を把握することができるようになる。
【０１３１】
また、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、候補リンクの正規化走行頻度の値の総和に対する当該候補リンクの正規化走行頻度の値の比率を当該候補リンクが採用される可能性を表す評価値とする場合もある。このような場合には、上で述べた経路推定ステップにおいて、２地点のうちの始点に最も近いノードである始点ノードから２地点のうち終点に最も近いノードである終点ノードまで、移動元ノードと複数の移動先候補ノードとの全ての組み合わせについて順次評価値を算出して、当該評価値を各候補経路に沿って乗算し、終点ノードに達した候補経路のうち、評価値の総乗算値が最大となる候補経路を特定するようにしてもよい。最短経路探索のダイクストラ法などとは異なり、始点ノードから終点ノードへ候補リンクを辿る際に、正規化走行頻度から得られ且つ候補リンクが採用される可能性（確率とも呼ぶ）を乗算することによって、より採用される可能性の高い候補リンク群を含む走行経路を特定することができるようになる。
【０１３２】
さらに、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの正規化走行頻度の値に対する全ての候補リンクの正規化走行頻度の値の和の比率を当該候補リンクの評価値とする場合もある。このような場合には、上で述べた経路推定ステップにおいて、２地点のうちの始点に最も近いノードである始点ノードから２地点のうち終点に最も近いノードである終点ノードまで、移動元ノードと複数の移動先候補ノードとの全ての組み合わせについて順次評価値を算出して、当該評価値を各候補経路に沿って乗算し、終点ノードに達した候補経路のうち、評価値の総乗算値が最小となる候補経路を特定するようにしてもよい。このように、上で述べた候補リンクが採用される可能性を表す評価値の逆数で走行経路を特定することもできるようになる。
【０１３３】
また、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和に対する当該候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積の比率を当該候補リンクが採用される可能性を表す評価値とする場合もある。さらに、移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積に対する候補リンクの正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和の比率を当該候補リンクの評価値として規定する場合もある。このように、各リンクについて平均走行速度にばらつきがある場合には、このような評価値を採用することによって、平均走行速度の高低を評価値に適切に反映させることができるようになる。
【０１３４】
なお、上で述べたような処理をハードウエアに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０１３５】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１３６】
（付記１）
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップと、
を含み、コンピュータに実行される車両走行位置データ処理方法。（１、図４）
【０１３７】
（付記２）
２つの前記車両走行位置データ・レコードで特定される２地点間の走行時間を、前記車両別走行リンク情報格納部に格納されている前記走行経路に含まれる各経路上リンクに、前記道路地図ネットワーク情報格納部に格納されている前記経路上リンクの長さデータ（又は長さデータを平均速度データで除した値）を基に振り分け、前記経路上リンクの識別子に対応付けて振り分けられた走行時間を時間推定結果格納部に格納するステップ
をさらに含む付記１記載の車両走行位置データ処理方法。（２，図１６）
【０１３８】
（付記３）
前記時間推定結果格納部に格納されている前記経路上リンクの識別子毎に、対応する前記走行時間の平均値を算出し、前記時間推定結果格納部に格納するステップ、
をさらに含む付記２記載の車両走行位置データ処理方法。（３，図１８）
【０１３９】
（付記４）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値の総和に対する当該候補リンクの前記正規化走行頻度の値の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（４）
【０１４０】
（付記５）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値に対する全ての前記候補リンクの前記正規化走行頻度の値の和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（５）
【０１４１】
（付記６）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和に対する当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（６）
【０１４２】
（付記７）
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積に対する前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
付記１乃至３のいずれか１つ記載の車両走行位置データ処理方法。（７）
【０１４３】
（付記８）
付記１乃至７のいずれか１つ記載の車両走行データ処理方法をコンピュータに実行させるためのプログラム。（８）
【０１４４】
（付記９）
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出す手段と、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントする手段と、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納する手段と、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定手段と、
を有する車両走行位置データ処理装置。（９）
【符号の説明】
【０１４５】
１０１ プローブ車両位置収集部 １０２ 走行位置情報格納部
１０３ 道路リンク別走行頻度算出部 １０４ 道路リンク別走行頻度情報格納部
１０５ 道路地図ネットワーク情報格納部 １０６ 正規化走行頻度算出部
１０７ 正規化走行頻度情報格納部 １０８ 入力部
１０９ 車両別走行経路算出部 １１０ 車両別走行リンク情報格納部
１１１ 道路リンク別平均走行時間算出部 １１２ 道路交通情報ＤＢ
１１３ 出力部
【特許請求の範囲】
【請求項１】
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップと、
を含み、コンピュータに実行される車両走行位置データ処理方法。
【請求項２】
２つの前記車両走行位置データ・レコードで特定される２地点間の走行時間を、前記車両別走行リンク情報格納部に格納されている前記走行経路に含まれる各経路上リンクに、前記道路地図ネットワーク情報格納部に格納されている前記経路上リンクの長さデータ（又はリンクの長さデータを平均速度データで除した値）を基に振り分け、前記経路上リンクの識別子に対応付けて振り分けられた走行時間を時間推定結果格納部に格納するステップ
をさらに含む請求項１記載の車両走行位置データ処理方法。
【請求項３】
前記時間推定結果格納部に格納されている前記経路上リンクの識別子毎に、対応する前記走行時間の平均値を算出し、前記時間推定結果格納部に格納するステップ、
をさらに含む請求項２記載の車両走行位置データ処理方法。
【請求項４】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値の総和に対する当該候補リンクの前記正規化走行頻度の値の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項５】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値に対する全ての前記候補リンクの前記正規化走行頻度の値の和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項６】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和に対する当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項７】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積に対する前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項８】
請求項１乃至７のいずれか１つ記載の車両走行データ処理方法をコンピュータに実行させるためのプログラム。
【請求項９】
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出す手段と、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントする手段と、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納する手段と、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定手段と、
を有する車両走行位置データ処理装置。
【請求項１】
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出すステップと、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントするステップと、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納するステップと、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定ステップと、
を含み、コンピュータに実行される車両走行位置データ処理方法。
【請求項２】
２つの前記車両走行位置データ・レコードで特定される２地点間の走行時間を、前記車両別走行リンク情報格納部に格納されている前記走行経路に含まれる各経路上リンクに、前記道路地図ネットワーク情報格納部に格納されている前記経路上リンクの長さデータ（又はリンクの長さデータを平均速度データで除した値）を基に振り分け、前記経路上リンクの識別子に対応付けて振り分けられた走行時間を時間推定結果格納部に格納するステップ
をさらに含む請求項１記載の車両走行位置データ処理方法。
【請求項３】
前記時間推定結果格納部に格納されている前記経路上リンクの識別子毎に、対応する前記走行時間の平均値を算出し、前記時間推定結果格納部に格納するステップ、
をさらに含む請求項２記載の車両走行位置データ処理方法。
【請求項４】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値の総和に対する当該候補リンクの前記正規化走行頻度の値の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項５】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値に対する全ての前記候補リンクの前記正規化走行頻度の値の和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項６】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和に対する当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の比率を当該候補リンクが採用される可能性を表す評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最大となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項７】
移動元ノードから複数の移動先候補ノードへの候補リンクの各々について、当該候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積に対する前記候補リンクの前記正規化走行頻度の値と当該候補リンクの平均走行速度との積の総和の比率を当該候補リンクの評価値とし、
前記経路推定ステップにおいて、
前記２地点のうちの始点に最も近いノードである始点ノードから前記２地点のうち終点に最も近いノードである終点ノードまで、前記移動元ノードと前記複数の移動先候補ノードとの全ての組み合わせについて順次前記評価値を算出して、当該評価値を各候補経路に沿って乗算し、
前記終点ノードに達した前記候補経路のうち、前記評価値の総乗算値が最小となる候補経路を特定する
請求項１乃至３のいずれか１つ記載の車両走行位置データ処理方法。
【請求項８】
請求項１乃至７のいずれか１つ記載の車両走行データ処理方法をコンピュータに実行させるためのプログラム。
【請求項９】
計測時刻と車両位置とを含む車両走行位置データ・レコードを格納する走行位置情報格納部から、前記計測時刻と前記車両位置との少なくともいずれかに関連する条件を満たす車両走行位置データ・レコードを読み出す手段と、
読み出された前記車両走行位置データ・レコードの各々について、複数のノードと当該ノード間を接続する複数のリンクとで表される道路ネットワークにおける前記ノード及びリンクの位置データ及び前記リンクの長さデータを格納する道路地図ネットワーク情報格納部に格納されている前記複数のリンクのうち前記車両走行位置データ・レコードの前記車両位置に対して所定の条件を満たす１つのリンクを特定し、当該リンクについての頻度カウンタの値をインクリメントする手段と、
前記複数のリンクの各々について、前記頻度カウンタの値を前記道路地図ネットワーク情報格納部に格納されている当該リンクの長さで除することによって、正規化走行頻度の値を算出し、正規化走行頻度データ格納部に格納する手段と、
前記正規化走行頻度データ格納部に格納されている各前記リンクの前記正規化走行頻度の値に基づき、前記走行位置情報格納部に格納されている、経路同定対象車両及び時間についての２つの前記車両走行位置データ・レコードで特定される２地点間の当該経路同定対象車両の走行経路を推定し、推定結果を車両別走行リンク情報格納部に格納する経路推定手段と、
を有する車両走行位置データ処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２０１１−６００４９（Ｐ２０１１−６００４９Ａ）
【公開日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願番号】特願２００９−２０９８４９（Ｐ２００９−２０９８４９）
【出願日】平成２１年９月１０日（２００９．９．１０）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願日】平成２１年９月１０日（２００９．９．１０）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]