DEIM Forum 2016 D8-6
類似検索を利用したマップマッチング処理
三浦 貴司
†野間
唯
††
株式会社富士通研究所 〒
211-8588
神奈川県川崎市上小田中
4-1-1
E-mail: †{miura_takashi,noma.yui}@jp.fujitsu.com
あらまし
日々生み出される大量のセンサデータから有益な情報を取り出すためには，一般的に膨大な処理コスト
を伴う．データの特性がある程度パターン化されている場合には，リアルタイムに有益な情報を得るために
Lookup
table 方式を採用することで，必要な情報を高速に取得することが可能である．Lookup table 方式とは，予め処理前
データもしくは観測結果と分析結果を同じテーブル内に登録し，観測結果を検索することで間接的に分析結果を得る
方法であり，処理前データもしくは構造化されたデータを扱う場合に適用されてきた．しかしこの方式は，浮動小数
値データからなるセンサデータを扱う場合には，データの完全一致による検索ができないという課題がある．今回，
我々は類似検索を利用し，センサデータに対して
Lookup table 方式を使うことを試みた．例として，GPS 測位によ
る緯度経度データをもとに行うマップマッチング処理を取り上げ，十分な処理速度と精度が達成できることを示す．
キーワード
PostgreSQL、類似検索、マップマッチング
1.
は じ め に
近年，さまざまなデバイスにGPSセンサが取り付けられて おり，移動体の位置データ収集が容易に行われるようになって きている．収集が容易になったことによって収集できるデー タ量とそれに伴う処理も膨大になっている．現在我々は、位置 データを生み出すデバイスの1つである商用車トラックに搭載 されたデジタルタコグラフに着目し，ネットワークを介した通 信によりリアルタイム収集される位置データの利活用を検討し ている． デジタルタコグラフ（デジタコ）とは，トラックを商用とし て取り扱う場合に法律で搭載が義務づけられているタコグラフ をデータ収集を通信で行えるようにした車載器である．従来の タコグラフでは法定三要素と呼ばれる走行時間，走行距離，速 度を車両ごとに車内装置で記録していたが，デジタル化ととも にさまざまなセンサデータを記録するようになり，通信によっ て1秒間隔でセンサデータを取得することが可能である．デジ タコに組み込まれているセンサデータの1つがGPSセンサで ある．国土交通省は，デジタコの普及・義務化を進めており， 現在，日本全体の商用車トラックの台数約90万台の38%に相 当する約34万台の商用車トラックにデジタコが搭載され，そ のデータ件数は年間1兆件を超える[1]．取得した大量データの 利活用についてもビジネスとして提供され始めており[2]，今後 より大量のデータが蓄積されていくことでさらなる利活用の活 性化が予想される． これら取得した車両の位置データに対して，有益な情報を得 るために最初に実施される処理がマップマッチング処理である． マップマッチング処理とは，取得した緯度経度データから車両 の存在する道路を特定する処理であり，車両の位置と現実の道 路を結びつける交通情報分析の基本となる処理である． デジタコから送られてくる大量の位置データを利用したマッ プマッチング処理がリアルタイムに可能となれば，リアルタイ ムに交通状況を把握することが可能となる．従来，マップマッ チング処理はカーナビゲーションシステム内においてリアルタ イムに行われる処理であり，個々の車両での処理は搭載された ジャイロセンサをはじめとするさまざまなセンサを利用して マップマッチングの精度を高めている．しかしながら，今回対 象とするデジタコデータに基づくマップマッチング処理では， 利用可能なセンサがGPSセンサに限定されているため，同様 の方式を使うことができないという問題がある． 本論文では，類似検索を利用し，デジタコからオンラインで 取得した大量な位置データをリアルタイムにマップマッチング 処理する方式を提案する．この方式は，オフラインで高精度に マップマッチング処理した結果をあらかじめデータベース上に 登録し，その結果をSQL文を使って検索・参照することで間 接的にマップマッチング処理を行う，データベース上でマップ マッチングのすべての処理を実行するLookup table方式の処 理である．Lookup table方式は，問い合わせ時には短時間で完 了する検索処理のみを実行すればよいため，高精度な結果を高 速に取り出すことが可能である．また，Lookup table方式を採 用することで，処理が増大した場合でも，別サーバにLookup tableを全てコピーするだけで簡単に対応可能であり，処理の並 列化がとても容易である．ところが，通常のLookup Table方 式で用いられる被検索対象の値とキーの完全一致検索は，緯度 経度データのような浮動小数値を登録データとするマップマッ チングには用いることができない．そこで，被検索対象の値と キーの値に僅かなずれがあったとしても類似した値のキーを 取得できるように，類似検索手法を取り入れることでLookup table方式のマップマッチングの手法を実現した．本論文では， 提案方式により従来のマップマッチング方式と同程度のマップ マッチング精度と，1サーバで数万台規模のマップマッチング 処理をリアルタイムに達成できることを示す． 今回特に、車両データがデータベース上で管理されることを 想定し，PostgreSQLを使用したマップマッチング処理の精度と速度に関する実験を行った． 本論文は以下の通り構成されている．2章では，従来のマッ プマッチング処理について述べる．3章では，今回提案する類 似検索を利用したマップマッチング処理に関して詳しく述べる． 4章では，今回の実験で使用するデータセット，実験内容と結 果の評価について述べる．5章では，実験結果を示す．6章で は，実験結果の内容を考察する．7章では，今回の実験を総括 する．
2.
従来のマップマッチング処理
2. 1 概 要 従来のマップマッチング処理は，デジタル道路地図(Digital Road Map，以下DRM) [4]をもとに，道路の緯度経度情報を 用いて車両の位置データから道路を特定を行う．DRMは，交 差点などの道路のつなぎ目を点（ノード）で，それらの点から 別の点へ線（リンク）を実際の道路として，道路地図を表現し たものである．マップマッチング処理では，車両の位置データ に最も近いDRM上のノードの緯度経度情報を検索し，その ノードから伸びる複数のリンクの中から唯一に特定を行ってい る．直観的には，車両の位置データに最も近いリンクを選択す ればよいように思われる．しかし，GPS測位による位置データ には十数m∼数十m誤差が含まれているため，最も近いリンク が車両の存在した道路に該当するとは限らない．このため，正 しく道路を特定するためには，カーナビゲーションシステムの ようにジャイロセンサなどのさまざまなセンサや経路探索法を 利用してマップマッチング処理を行うことが一般的である(文 献[3]を参照されたい)．現在，デジタコデータを利用したマッ プマッチングは，使用できるデータは緯度経度データのみであ るため，経路探索法を利用した手法により処理されている． 2. 2 さまざまなマップマッチング方法と精度 GPS測位による位置データには誤差が含まれているため，2 本の道路が並走している場所や交差点など道路が交差するよう な場所では，車両が道路を飛び移りながら移動するといった不 自然な走行経路を特定してしまう場合がある．このような誤差 の影響による不自然な車両の走行経路を特定しないために，最 短経路探索や移動体の速度，走行距離，ジャイロセンサ，加速 度センサなどの助けを借り，補正処理を行っている． 以下にマップマッチング処理として考案されているアルゴリ ズムの分類を示す． • 幾何学的アルゴリズム[5]- [10] • 位相幾何的アルゴリズム[11]- [20] • 確率論的アルゴリズム[21]- [23] • より高度な処理を組み合わせたアルゴリズム[24]- [30] 幾何学的アルゴリズムは，車両のノイズを含む緯度経度データ をもとに最近傍に存在するノードやリンクを探し出し，DRM 上での車両の存在するリンクや位置を特定するアルゴリズムで ある．位相幾何的アルゴリズムは，リンクの連結性や連結角度， リンク長などの道路情報を利用し，連結して閉じている線を多 角形として扱うことで，DRM上での車両の存在するリンクや 位置を特定するアルゴリズムである．確率論的アルゴリズムは， 車両の現在の移動行動から未来の存在確率の高い領域を割り 出し，DRM上での車両の存在するリンクや位置を特定するア ルゴリズムである．より高度な技術や処理を組み合わせたアル ゴリズムは，Kalman lter [24] [25]，belief theory [26]，fuzzylogic method [27]- [29]，ベイズ推定の応用[30]を取り入れるこ とで，DRM上での車両の存在するリンクや位置を特定するア ルゴリズムである． デジタコデータを使用する場合には，緯度経度データのみ を利用したマップマッチングアルゴリズム[5] [10] [11] [20] [17] [25] [28]を使用する必要がある．表1は緯度経度データのみを 利用したマップマッチングアルゴリズムにおける精度を示した ものである．ここでマップマッチング成功率［完全一致］とは 後述するマップマッチングの精度の評価指標である．それぞれ の論文で，使用しているGPS測位装置やそのデータ，またどの 地域で測位したデータかに関してさまざまであるが，1つの目 標値となると考える．表1より，今回提案する手法では80%を 超えるマップマッチング成功率を達成することを目標とした． 表1 マップマッチング（MM）成功率［完全一致］．[ ] 内の数値は Quddus らによる再実験の結果 [18]． 著者 MM 成功率（%） White et al. [5] 85.8 [76.8] Bouju et al. [10] 91.7 Greenfeld [11] [85.6] Srinivasan et al. [17] 98.5 [80.2] 宮下，他 [20] 93.0 Yang et al. [25] 96.0 Quddus et al. [28] 99.2 2. 3 処 理 時 間 以下の状況下におけるリアルタイムマップマッチングの処理 速度を見積もることにする． • 車両データを5分に一度の通信により取得する． • 車両がデータを送信するタイミングはランダムである． この状況下で，日本全国の地図を10領域に分割して，それぞ れの領域に1サーバずつ割り振ってマップマッチング処理させ ることを想定すると，現状の車両台数約90万台を処理するた めには1サーバ10万台程度の処理能力が必要となる．1サー バあたり10プロセス程度までで処理させる場合，1万∼10万 台の車両データをリアルタイム処理するために車両1台当たり にかけられる処理時間は3∼30(msec)である．このことより， 今回提案する手法では，1プロセスで車両1台当たり処理時間 30(msec)，5分間で車両1万台の処理を目標とした．
3.
類似検索を利用したマップマッチング処理
3. 1 概 要 今回我々が提案する類似検索を利用したマップマッチング処 理について説明する．上述にもある通り，オフラインで時間か けて高精度にマップマッチング処理した過去の大量の走行情報 をあらかじめデータベース上に登録し，その結果を類似検索・参照することで間接的にマップマッチング処理を行う，類似検 索を利用したLookup table方式のマップマッチングの手法で ある． 図1に具体的な処理の流れを示す．まず，データベースのレ コードデータ内の属性として以下の3つのデータを事前に登録 する． • マップマッチング処理済みの緯度経度データ • 特定された2次メッシュ番号 • 特定されたリンク番号 この時のマップマッチング処理済みの緯度経度データは道路上 の位置まで正確に特定されているものとする．その緯度経度 データと紐付けて2つ道路情報（2次メッシュ番号，リンク番 号）を登録する．2次メッシュ番号とはDRMの地図単位を管 理する番号であり，リンク番号とは各2次メッシュ内でのリン クを管理する番号である． この状況下で大まかに次の5つのステップ経て道路を特定 する． (1) GPS測位によるL秒間の緯度経度データを複数点取 得する． (2) このデータから特徴ベクトルを作成する． (3) 最新の位置データを中心とする矩形窓の範囲検索を行 い，類似検索の被検索対象の数を絞り込む． (4) 絞り込まれた被検索対象の特徴ベクトルを検索対象と して，データベース上の複数の被検索対象である特徴ベクトル との類似度をそれぞれ算出する． (5) 複数の被検索対象の中で類似度の最も高い被検索対象 の道路情報（2次メッシュ番号，リンク番号）を取得し，マッ プマッチング結果とする． 3. 2 特徴ベクトル 今回の実験では，クエリや被検索対象レコードの特徴ベクト ルとして以下のデータ配列を使用した． (x1, x2, x3,· · · , x2N) (1) xi≡ { Xi if 1 <= i <= N Yi−N if N + 1 <= i <= 2N (2) ここで車両の各時刻での緯度経度座標を(Xi, Yi) (i = 1∼ N) とした．以下ではこのような時系列的な複数の点の集合を点列 と呼ぶことにする． このような点列を採用する理由は，レコードデータから不 自然な走行経路のデータを除外することができるからである． 今回の実験では，レコードデータにマップマッチング処理後の データからなる点列を使用する．この処理後の点列には，2本 の道路が並走している場所や交差点など道路が交差するような 場所での道路を飛び移りながら移動するといった不自然な走行 経路のデータが存在しない．そのため，自然な走行経路データ のみのレコードデータを被検索対象とすることができる． 3. 3 類似度の定義 検索対象とデータベース上の被検索対象との類似度を算出す るために，特徴量空間内での2つのデータどうしの距離を使用 する．今回の実験では，以下で定義されるEuclid距離Dを使 用する． D(q, p(i))≡ v u u t∑2N k=1 (qk− p(i)k )2. (3) ここでqとp(i)は，式(1)に従い構成された検索対象と被検索 対象の特徴ベクトルである．
4.
実験と評価
4. 1 データセット 今回の実験では，デジタコで取得され，マップマッチング処 理された以下のデータを使用した． • 国土地理院発行の2.5万分の1地図に基づく2次メッ シュ「大阪西南部」「大阪東南部」「大阪西北部」「大阪西北部」 の範囲のデータ(表2) • 1つの2次メッシュの大きさは経度方向に約11.5km，緯 度方向に約9.2km • 1秒に1回取得されるGPS測位による緯度経度データ と取得日時・時刻データ • GPS測位による緯度経度データはマップマッチング処理 され，処理後の緯度経度座標とリンク番号が付随 • このマップマッチング処理は道路幅が5.5m以上の基本 道路のデータが対象 この範囲における緯度経度データの1日の取得点数は約700 万点である．全体に占める道路の種類ごとの割合として，約 85%が高速自動車道や都市高速道路である．また，GPS測位に よる緯度経度データにはマップマッチング処理後の緯度経度座 標とリンク番号の情報が存在する．今回の実験では，株式会社 富士通交通・道路サービス[31]で取り扱っているマップマッチ ング処理前と後のデータセットを使用した（注1）． このデータをもとに，類似検索の検索対象，被検索対象とも に式(1)のような特徴ベクトルに事前に加工した上で使用した． 表3は，加工した点列データセットの点列長，サンプリング周 期，点列内の点数を示したものである． 今回の実験では，データベースのレコード数の違いによる マップマッチングの精度への影響を知るために，表4に示した レコード数の異なるデータベースを採用した．使用したデータ は2014年9月のデータで，それぞれDB1は9月最初の土日 月の3日分，DB2は9月全土日月の12日分，DB3は9月一 か月分の点列データである． 一方，クエリに使用したデータは季節や長期休暇期間のマッ プマッチングの精度への影響を知るために，表5に示した通常 日，冬季，ゴールデンウィーク(GW)，お盆の4通り全35日 分の点列データを使用した．クエリは各日付1万件を実施した． また，これらデータベースに登録するレコードデータや次項 で説明するマップマッチング成功率を算出するための正解デー タとして，前述のマップマッチング処理後のデータを使用した． （注1）：マップマッチングのアルゴリズムに関しては非公開．概要に関しては文 献[32] を参照頂きたい．図1 類似検索を利用したマップマッチング処理の流れ．ここでは緯度経度データから構成され る特徴量ベクトルを使用． 表2 各 2 次メッシュにおける DRM の概要 2 次メッシュ名 リンク数 平均リンク長 基本ノード数 大阪西南部 6659 本 119.2m 4392 点 大阪東南部 10654 本 114.8m 7143 点 大阪西北部 8957 本 124.2m 5984 点 大阪東北部 12507 本 114.3m 8152 点 表3 点列データセット 点列長 L（秒） サンプリング周期 M （秒/点） 点数 N（点） 300 10 30 表4 データベース登録レコードの概要 データベース レコード数（件） データ容量（GB） DB1 約43 万 約0.4 DB2 約188 万 約1.8 DB3 約549 万 約5.3 表5 クエリに使用したデータの概要 種類 内容 通常日 2014 年 10 月全土日月の 12 日 冬季 2015 年 1 月全土日月の 13 日 GW 2015 年 5 月 2-6 日の 5 日 お盆 2014 年 8 月 13-17 日の 5 日 4. 2 マップマッチングの精度の評価指標 今回の実験では，マップマッチングの精度の評価指標として 以下の2種類を定義する． (a) 特定した道路が正解データの道路と一致した割合 (b) 特定した走行経路が正解データの走行経路と一致した 割合 評価指標(a)は以下の式(4)で与えられる． 正解データのリンク番号と一致した点列内の点の数 クエリに使用した点列内の点の総数 × 100 (%) (4) これは，マップマッチング処理により特定した道路（リンク番 号）と正解データの道路とが完全に一致した点列内の点の数を， 点列内の点の総数で割り，百分率で表記した評価指標である． 以下ではマップマッチング（MM）成功率［完全一致］と表記 する． 評価指標(b)は以下の式(5)で与えられる． 正解データのノード番号と一致した点列内の点の数 クエリに使用した点列内の点の総数 × 100 (%) (5) これは，マップマッチング処理により特定したリンク番号を構 成する2つのノード番号のうち少なくとも1つのノード番号 と，正解データのリンク番号を構成する2つのうちどちらかの ノード番号とが一致した点列内の点の数を，点列内の点の総数 で割り，百分率で表記した評価指標である．今回の実験では， レコードデータにマップマッチング処理後の点列を使用するた め，レコードデータはすべて自然な走行経路のデータである． また，隣接するリンクどうしは共通のノードで接続しているた め，隣接する全てのリンクのリンク番号は必ず1つ同じノード 番号を含む．このことから，正解データとどちらか片方のノー
ド番号が一致していれば，正解データと同じ走行経路であると 判断できるため，走行経路の特定の評価指標を式(5)と定義し た．以下ではマップマッチング（MM）成功率［片方一致］と 表記する． 4. 3 実 装 これらの実験をPostgreSQL (v.9.4)上に実装し，マップマッ チングの精度と処理時間を計測した．使用したサーバのスペッ クは以下の通りである．
• Windows Serever 2012 R2 Standard (x64) • Intel(R) Xenon(R) CPU E5-2690 0 @ 2.90GHz×2 • Memory 768GB また、実装に際して類似検索を行う前段階で行う範囲検索の 矩形窓の大きさを決める必要がある．図2は矩形窓の大きさ とマップマッチング成功率の関係をグラフ化したものである． 40mを過ぎた付近からマップマチング成功率の改善が鈍化し始 めることが分かる．このことから今回の実験では，マップマチ ング成功率の改善が鈍化し始める40mの倍の大きさである中 心から四方に80mの矩形窓に設定した． 図2 範囲検索時の矩形窓の大きさとマップマチング成功率 [完全一致] のグラフ．縦軸の単位は[%] である．横軸は矩形窓の一辺の長 さの半分の値である． 4. 4 マップマッチング用SQL文 図3は類似検索利用したマップマッチングのSQL文の主要部 分である．11行目のquery_LonXLatYは式(1)のマップマッ チングしたい点列である．10行目のtbl_carDataAfterMM は過去のマップマッチング済み点列が登録されているテーブル であり，tbl_range_currentはマップマッチングしたい点列 の最新点の位置から算出した範囲検索窓の緯度経度座標のテー ブルである． まず，7行目の各点列の最新点の緯度経度座標が格納された point型のnewestPointに対して，7行目から9行目で矩形 の範囲検索を行い，レコードの絞込みを行っている．この絞込 みの結果が，10行目のtbl_candCarDataである．11行目で 緯度経度データからなる点列tbl_candCarData.LonXLatY に対して，query_LonXLatYとのEuclid距離を計算し，こ の距離が最も短いレコードの2次メッシュ番号とリンク番号を 2行目と3行目で得ている． このとき，7行目で参照しているnewestPointに対しては， 空間インデックスであるSP_GiSTを使用している．
5.
実 験 結 果
以下のすべての実験計測はシングルプロセスで処理させた結 果である．表6，表7，表8はレコード数の異なる3種類のデー タベースを使用し，通常日，冬季，お盆，GWの4つの期間の データをクエリに使用した場合の平均マップマッチング成功率， 1クエリあたりの候補点列数，1クエリあたりの処理時間の実 験結果である．また，図4と図5は各日付でマップマッチング 成功率をグラフにしたものである．また，表9は，1プロセス での1クエリあたりの処理時間の平均値と，この処理時間をも とに5分間隔で通信を介してランダムに送信される車両データ を処理する場合の5分間での処理可能車両台数を示したもので ある． 表6 類似検索を利用したマップマッチング処理の結果．データベース としてDB1 を使用． MM 成功率 (%) 候補点列数 処理時間 完全一致 片方一致 (点列) (msec) 通常日 85.0 90.3 731.0 5.13 冬季 84.9 90.0 748.2 4.99 お盆 81.9 87.6 662.0 4.96 GW 84.3 89.1 695.5 4.59 全平均 84.4 89.6 722.5 4.98 表7 類似検索を利用したマップマッチング処理の結果．データベース としてDB2 を使用． MM 成功率 (%) 候補点列数 処理時間 完全一致 片方一致 (点列) (msec) 通常日 87.9 92.2 3191.7 9.66 冬季 87.5 91.7 3259.2 9.51 お盆 85.4 90.2 2888.7 9.32 GW 87.1 91.1 3050.2 9.14 全平均 87.3 91.6 3153.2 9.48 表8 類似検索を利用したマップマッチング処理の結果．データベース としてDB3 を使用． MM 成功率 (%) 候補点列数 処理時間 完全一致 片方一致 (点列) (msec) 通常日 89.2 93.0 9396.1 29.43 冬季 88.6 92.4 9630.7 27.95 お盆 87.0 91.3 8434.9 23.52 GW 88.2 91.8 8908.4 23.18 全平均 88.5 92.4 9276.3 27.15 表9 1 プロセスでのマップマッチング処理時間． データベース名 1 クエリあたりの 5 分間での 処理時間(msec) 処理台数（台） DB1 4.98 60240 DB2 9.48 31645 DB3 27.15 110491: SELECT 2: tbl_candCarData.meshNum, 3: tbl_candCarData.linkID 4: FROM (SELECT 5: * 6: FROM tbl_carDataAfterMM 7: WHERE tbl_carDataAfterMM.newestPoint <@ 8: box(point(tbl_range_current.windowOriginLonX, tbl_range_current.windowOriginLonY), 9: point(tbl_range_current.windowFarLonX, tbl_range_current.windowFarLonY)) 10: ) AS tbl_candCarData, tbl_range_current
11: ORDER BY calcEuclidDist(tbl_candCarData.LonXLatY, query_LonXLatY) 12: LIMIT 1; 図3 マップマッチング用 SQL 文 図4 各日付でのマップマチング成功率 [完全一致] のグラフ．左上の図は通常日，右上の図は冬 季，左下の図はお盆，右下の図はGW．縦軸の単位は [%] である．横軸は日付である． 図5 各日付でのマップマチング成功率 [片方一致] のグラフ．左上の図は通常日，右上の図は冬 季，左下の図はお盆，右下の図はGW．縦軸の単位は [%] である．横軸は日付である．
6.
考
察
マップマッチング成功率は，完全一致の場合，DB1で84.4%， DB2で87.3%，DB3で88.5%といずれも当初の目標であった 80%を超え，表1に匹敵する成功率が得られた．また，片方一 致の場合，DB1で89.6%，DB2で91.6%，DB3で92.4%と走 行経路の特定は90%を超える結果が得られた．これは検索に使 用したデータを点列にしたことによる効果であると考える．図 6は，実際に点列内の各点のマップマッチング成功率をグラフ にしたものである．第1点目が時系列的に最過去の点であり， 第30点目が時系列的に最新の点である．第1点目に比べて範 囲検索時に基準とした第30点目側のマップマッチング成功率 が若干高い傾向にあるが，全体として両端のマップマッチング 成功率が低く，点列の真ん中に近づくにつてれてマップマッチ ング成功率が高くなる傾向にある．これは，点列の両端では点 列内の隣接点が一点しか存在せず，点列内部の点に比べてGPS 測位による誤差が道路の特定に大きく影響を与えるためである と考える．例えば，点列の端の点が交差点付近に位置する場合， GPS測位による誤差のために，端の点が右折，直進，左折のど の行動をとった点であるかの曖昧さが生じる．一方で，点列内 部の点はその前後に隣接点が二点存在するため，GPS測位によ る誤差が存在しても，右折，直進，左折のどの行動を取った点 であるかは前後の点との位置関係から絞られるため，端の点に 比べてマップマッチング成功率が高い．また，図6からは，端 の点から真ん中の点になるにつれて徐々に正しい走行経路に矯 正されていることが見て取れる．例えば，点列内の第1点から 第5点と第29点，第30点のデータを使用しない場合，完全一 致のマップマッチング成功率はDB1で86.2%，DB2で88.4%， DB3で89.8%と1.1から1.8ポイントマップマッチング成功率 が改善する． レコード数の違いによるマップマッチング成功率への影響で あるが，DB1に比べてDB3のレコード数が約12.8倍に増加し たことに対し，マップマッチング成功率［完全一致］は84.4%か ら88.5%の4.1ポイント，マップマッチング成功率［片方一致］ は89.6%から92.4%の2.8ポイント改善された．ただし，さら に精度を上げる場合，単純にレコードデータを増やすことは効 率が良いとは言えない．これは，レコード内のデータ間で似通っ たデータばかりが増加する傾向にあるためであり，稀なデータ を重点的に補充したり，各道路に対応するレコード数を見なが ら，レコード数の少ない個所を補充する処理が必要になると考 える．また，GPS測位時の誤差が検索窓の大きさである80m 四方の領域を超える場合や，高速道路上の車両が低速で一般道 の車両と区別できない場合を改善するこで，さらにマップマッ チング成功率を向上させることが可能であると考える． また，図4と図5から読み取れるように，季節や長期休暇期 間によるマップマッチング成功率への影響に大きな違いは無い ことが分かった． 処理時間と処理可能台数は，表9にあるように，DB1で 60240台，DB2で31645台，DB3で11049台といずれも当初 の目標であった1万台を超える値が得られた．今回の実験では， 特に交通量の多い地域の2次メッシュ4つ分の領域にデータを 限定して実験を実施した．さらに，取り扱う2次メッシュの数 が増える場合でも，空間インデックスを付与することで線型的 な処理時間の増大は避けられるものと考える． 図6 点列内の各点におけるマップマチング成功率 [完全一致] のグラ フ．使用したデータは通常日（2014 年 10 月 4 日）である．縦 軸の単位は[%] である．横軸は点列内の点の位置を表している． 第1 点が最過去の点，第 30 点が最新の点．7.
お わ り に
本論文では，デジタコからオンラインで取得した大量の位置 データをリアルタイムに処理可能な，類似検索を利用したマッ プマッチング処理を提案し，十分な精度と処理速度を得られる ことを示した．さらに，このようなマップマッチング結果に車 速データを加えることで，リアルタイムの交通状況の把握が見 込めると考えている． 今回はデジタコデータを利用したが，より一般的なセンサ データに同じような方法を使用し，類似検索をすることで処 理コストのかかる分析を迅速に行うことが可能である．また， データベース上でのLookup table方式を採用したことにより， 分析データ量が増大した場合でもLookup tableを別サーバに 全てコピーすることで，容易に並列化が可能である．今後，さ まざまなセンサデータで同様の方式を検討する予定である． 文 献 [1] 国土交通省: プラン２００９に定められた各施策の中間実施状況 及び評価（資料２）， http://www.mlit.go.jp/common/001047374.pdf. [2] 道 路 管 理 者・道 路 コ ン サ ル 向 け 交 通 現 象 分 析 デ ー タ 提 供 サ ー ビ ス（FUJITSU イ ン テ リ ジェン ト デ ー タ サ ー ビ ス / 商 用 車 プ ロ ー ブ デ ー タ サ ー ビ ス ） ， http://jp.fujitsu.com/solutions/cloud/saas/application/road-analysis/probe/[3] Quddus, M.A., Ochieng, W.Y., Noland, R.B.: Current map matching algorithm for transport applications: state-of-the art and future research direction. Transportation Research Part C: Emerging Technologies 15, 312―328, 2007. [4] 一般財団法人 日本デジタル道路地図協会, http://www.drm.jp/. [5] White, C.E., Bernstein, D., Kornhauser, A.L., 2000. Some
map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies 8 (1), 91―108.
structures for range searching. Acta Inf. 13, 155―168. [7] Bernstein, D., Kornhauser, A., 1996. An
introduc-tion to map-matching for personal navigaintroduc-tion assistants., http://www.njtude.org/reports/mapmatchintro.pdf, Accessed June 19, 2002.
[8] Phuyal, B., 2002. Method and use of aggragated dead reck-oning sensor and GPS data for map-matching. In: proceed-ings of the Institute of Navigation (ION) annual conference, Portland, OR (20―27 September).
[9] Taylor, G., Brunsdon, C., Li, J., Olden, A., Steup, D., Win-ter, M., 2006. GPS accuracy estimation using map-matching techniques: Applied to vehicle positioning and odometer calibration. Computers, Environments, and Urban Systems 30, 757―772.
[10] Bouju, A., Stockus, A., Bertrand, F., Boursier, P., 2002. Location-based spatial data management in navigation sys-tems. IEEE Symposium on Intelligent Vehicle 1, 172―177. [11] Greenfeld, J.S., 2002. Matching GPS observations to loca-tions on a digital map. In proceedings of the 81st Annual Meeting of the Transportation Research Board, January, Washington D.C.
[12] Chen, W., YU, M., LI, Z.-L., Chen, Y.-Q., 2003. Integrated vehicle navigation system for urban applications. In: Pro-ceedings of the 7th International Conference on Global Nav-igation Satellite Systems (GNSS), European Space Agency, Graz, Austria, pp. 15―22 (April 22―24).
[13] Quddus, M.A., Ochieng, W.Y., Zhao, L., Noland, R.B., 2003. A general map-matching algorithm for transport telematics applications. GPS Solutions 7 (3), 157―167. [14] Yin, H., Wolfson, O., 2004. A weight-based map-matching
method in moving objects databases, Scienti c and Statis-tical Database Management. In: Proceedings of the Inter-national Working Conference, vol. 16. pp. 437―438. [15] Blazquez, C.A., Vonderohe, A.P., 2005. Simple
map-matching algorithm applied to intelligent winter mainte-nance vehicle data. Transportation Research Record 1935, 68―76.
[16] Meng, Y., 2006. Improved Positioning of Land Vehicle in ITS Using Digital Map and Other Accessory Information. PhD Thesis. Department of Land Surveying and Geoinfor-matics, Hong Kong Polytechnic University.
[17] Srinivasan, D., Chue, R.L., Tan, C.W., 2003. Development of an improved ERP system using GPS and AI technique. In: Proceedings of IEEE Conference on Intelligent Trans-portation Systems, pp. 554―559.
[18] Nagendra R. Velaga, Mohammed A. Quddus and Abigail L. Bristow, Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems, Transportation Research Part C 17 (2009) 672―683. [19] Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C., 2005.
On Map-Matching Vehicle Tracking Data., Proc. 31st Very Large Data Base Conference (VLDB), pp.853-864. [20] 宮下浩一，寺田努，田中宏平西，尾章治郎，目的予測型カーナビ
ゲーションシステムのためのマップマッチング手法，情報処理 学会論文誌，Vol.50 No.1 75-86 (2009).
[21] Honey, S.K., Zavoli, W.B., Milnes, K.A., Phillips, A.C., White, M.S., Loughmiller, G.E., 1989. Vehicle navigational system and method, United States Patent No., 4796191. [22] Zhao, Y., 1997. Vehicle Location and Navigation System.
Artech House, Inc., MA.
[23] Ochieng, W.Y., Quddus, M.A., Noland, R.B., 2004. Map-matching in complex urban road networks. Brazilian Jour-nal of Cartography (Revista Brasileira de Cartogra a) 55 (2), 1―18.
[24] Kim, W., Jee, G., Lee, J., 2000. E cient use of digital road map in various positioning for ITS. In: IEEE Symposium on Position Location and Navigation, San Deigo, CA. [25] Yang, D., Cai, B., Yuan, Y., 2003. An improved
map-matching algorithm used in vehicle navigation system. IEEE Proceedings on Intelligent Transportation Systems 2, 1246 ―1250.
[26] Najjar, M.E., Bonnifait, P., 2003. A roadmap matching method for precise vehicle Localization using belief theory and Kalman ltering. In: The 11th International Confer-ence in Advanced Robotics, Coimbra, Portugal, June 30― July 3.
[27] Syed, S., Cannon, M.E., 2004. Fuzzy logic-based map matching algorithm for vehicle navigation system in ur-ban canyons. In: Proceedings of the Institute of Navigation (ION) National Technical Meeting, 26―28 January, Cali-fornia, USA.
[28] Quddus, M.A., Ochieng, W.Y., Noland, R.B., 2006. A high accuracy fuzzy logic-based map matching algorithm for road transport. J. Intell. Transport. Syst. Technol. Plann. Op-erat. 10 (3), 103―115.
[29] Fuchs, H., Kedem, Z.M., Naylor, B.F., 1980. On visible sur-face generation by a priori tree structures. Comput. Graph. 14, 124―133.
[30] Pyo, J., Shin, D., Sung, T., 2001. Development of a map matching method using the multiple hypothesis technique. In: IEEE Proceedings on Intelligent Transportation Sys-tems, pp. 23―27. [31] 株式会社富士通交通・道路サービス, http://pr.fujitsu.com/jp/news/2015/08/3-1.html [32] 濱島光宏, 商用車プローブデータの収集と活用可能性 (特集 ビッ グデータ), 交通工学研究会機関誌「交通工学」 2015 年 1 月 号（Vol.50, No.1）
