類似検索を利用したマップマッチング処理

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 測位によ
る緯度経度データをもとに行うマップマッチング処理を取り上げ，十分な処理速度と精度が達成できることを示す．
キーワード
1.
PostgreSQL、類似検索、マップマッチング
はじめに
ムに交通状況を把握することが可能となる．従来，マップマッ
チング処理はカーナビゲーションシステム内においてリアルタ
近年，さまざまなデバイスに GPS センサが取り付けられて
イムに行われる処理であり，個々の車両での処理は搭載された
おり，移動体の位置データ収集が容易に行われるようになって
ジャイロセンサをはじめとするさまざまなセンサを利用して
きている．収集が容易になったことによって収集できるデー
マップマッチングの精度を高めている．しかしながら，今回対
タ量とそれに伴う処理も膨大になっている．現在我々は、位置
象とするデジタコデータに基づくマップマッチング処理では，
データを生み出すデバイスの 1 つである商用車トラックに搭載
利用可能なセンサが GPS センサに限定されているため，同様
されたデジタルタコグラフに着目し，ネットワークを介した通
の方式を使うことができないという問題がある．
信によりリアルタイム収集される位置データの利活用を検討し
ている．
本論文では，類似検索を利用し，デジタコからオンラインで
取得した大量な位置データをリアルタイムにマップマッチング
デジタルタコグラフ（デジタコ）とは，トラックを商用とし
処理する方式を提案する．この方式は，オフラインで高精度に
て取り扱う場合に法律で搭載が義務づけられているタコグラフ
マップマッチング処理した結果をあらかじめデータベース上に
をデータ収集を通信で行えるようにした車載器である．従来の
登録し，その結果を SQL 文を使って検索・参照することで間
タコグラフでは法定三要素と呼ばれる走行時間，走行距離，速
接的にマップマッチング処理を行う，データベース上でマップ
度を車両ごとに車内装置で記録していたが，デジタル化ととも
マッチングのすべての処理を実行する Lookup
にさまざまなセンサデータを記録するようになり，通信によっ
理である．Lookup
て 1 秒間隔でセンサデータを取得することが可能である．デジ
了する検索処理のみを実行すればよいため，高精度な結果を高
タコに組み込まれているセンサデータの 1 つが GPS センサで
速に取り出すことが可能である．また，Lookup
ある．国土交通省は，デジタコの普及・義務化を進めており，
用することで，処理が増大した場合でも，別サーバに Lookup
現在，日本全体の商用車トラックの台数約 90 万台の 38% に相
table
当する約 34 万台の商用車トラックにデジタコが搭載され，そ
列化がとても容易である．ところが，通常の Lookup
table
table
方式の処
方式は，問い合わせ時には短時間で完
table
方式を採
を全てコピーするだけで簡単に対応可能であり，処理の並
Table
方
のデータ件数は年間 1 兆件を超える [1]．取得した大量データの
式で用いられる被検索対象の値とキーの完全一致検索は，緯度
利活用についてもビジネスとして提供され始めており [2]，今後
経度データのような浮動小数値を登録データとするマップマッ
より大量のデータが蓄積されていくことでさらなる利活用の活
チングには用いることができない．そこで，被検索対象の値と
性化が予想される．
キーの値に僅かなずれがあったとしても類似した値のキーを
これら取得した車両の位置データに対して，有益な情報を得
取得できるように，類似検索手法を取り入れることで Lookup
るために最初に実施される処理がマップマッチング処理である．
table
方式のマップマッチングの手法を実現した．本論文では，
マップマッチング処理とは，取得した緯度経度データから車両
提案方式により従来のマップマッチング方式と同程度のマップ
の存在する道路を特定する処理であり，車両の位置と現実の道
マッチング精度と，1 サーバで数万台規模のマップマッチング
路を結びつける交通情報分析の基本となる処理である．
処理をリアルタイムに達成できることを示す．
デジタコから送られてくる大量の位置データを利用したマッ
今回特に、車両データがデータベース上で管理されることを
プマッチング処理がリアルタイムに可能となれば，リアルタイ
想定し，PostgreSQL を使用したマップマッチング処理の精度
と速度に関する実験を行った．
車両の現在の移動行動から未来の存在確率の高い領域を割り
本論文は以下の通り構成されている．2 章では，従来のマッ
出し，DRM 上での車両の存在するリンクや位置を特定するア
プマッチング処理について述べる．3 章では，今回提案する類
ルゴリズムである．より高度な技術や処理を組み合わせたアル
似検索を利用したマップマッチング処理に関して詳しく述べる．
ゴリズムは，Kalman
4
章では，今回の実験で使用するデータセット，実験内容と結
lter [24] [25]，belief theory [26]，fuzzy
logic method [27]- [29]，ベイズ推定の応用 [30]
を取り入れるこ
果の評価について述べる．5 章では，実験結果を示す．6 章で
とで，DRM 上での車両の存在するリンクや位置を特定するア
は，実験結果の内容を考察する．7 章では，今回の実験を総括
ルゴリズムである．
する．
デジタコデータを使用する場合には，緯度経度データのみ
従来のマップマッチング処理
2.
概
2. 1
要
[25] [28]
を使用する必要がある．表 1 は緯度経度データのみを
利用したマップマッチングアルゴリズムにおける精度を示した
従来のマップマッチング処理は，デジタル道路地図 (Digital
Road Map，以下 DRM) [4]
を利用したマップマッチングアルゴリズム [5] [10] [11] [20] [17]
ものである．ここでマップマッチング成功率［完全一致］とは
をもとに，道路の緯度経度情報を
後述するマップマッチングの精度の評価指標である．それぞれ
用いて車両の位置データから道路を特定を行う．DRM は，交
の論文で，使用している GPS 測位装置やそのデータ，またどの
差点などの道路のつなぎ目を点（ノード）で，それらの点から
地域で測位したデータかに関してさまざまであるが，1 つの目
別の点へ線（リンク）を実際の道路として，道路地図を表現し
標値となると考える．表 1 より，今回提案する手法では 80%を
たものである．マップマッチング処理では，車両の位置データ
超えるマップマッチング成功率を達成することを目標とした．
に最も近い
DRM
上のノードの緯度経度情報を検索し，その
ノードから伸びる複数のリンクの中から唯一に特定を行ってい
る．直観的には，車両の位置データに最も近いリンクを選択す
表
1 マップマッチング（MM）成功率［完全一致］．[ ] 内の数値は
Quddus らによる再実験の結果 [18]．
ればよいように思われる．しかし，GPS 測位による位置データ
著者
には十数 m∼数十 m 誤差が含まれているため，最も近いリンク
White et al. [5]
Bouju et al. [10]
Greenfeld [11]
Srinivasan et al. [17]
宮下，他 [20]
Yang et al. [25]
Quddus et al. [28]
が車両の存在した道路に該当するとは限らない．このため，正
しく道路を特定するためには，カーナビゲーションシステムの
ようにジャイロセンサなどのさまざまなセンサや経路探索法を
利用してマップマッチング処理を行うことが一般的である (文
献 [3] を参照されたい)．現在，デジタコデータを利用したマッ
MM 成功率（%）
85.8 [76.8]
91.7
[85.6]
98.5 [80.2]
93.0
96.0
99.2
プマッチングは，使用できるデータは緯度経度データのみであ
るため，経路探索法を利用した手法により処理されている．
さまざまなマップマッチング方法と精度
2. 2
GPS
測位による位置データには誤差が含まれているため，2
本の道路が並走している場所や交差点など道路が交差するよう
な場所では，車両が道路を飛び移りながら移動するといった不
自然な走行経路を特定してしまう場合がある．このような誤差
の影響による不自然な車両の走行経路を特定しないために，最
短経路探索や移動体の速度，走行距離，ジャイロセンサ，加速
度センサなどの助けを借り，補正処理を行っている．
以下にマップマッチング処理として考案されているアルゴリ
ズムの分類を示す．
•
幾何学的アルゴリズム [5]- [10]
•
位相幾何的アルゴリズム [11]- [20]
•
確率論的アルゴリズム [21]- [23]
•
より高度な処理を組み合わせたアルゴリズム [24]- [30]
幾何学的アルゴリズムは，車両のノイズを含む緯度経度データ
をもとに最近傍に存在するノードやリンクを探し出し，DRM
上での車両の存在するリンクや位置を特定するアルゴリズムで
ある．位相幾何的アルゴリズムは，リンクの連結性や連結角度，
リンク長などの道路情報を利用し，連結して閉じている線を多
角形として扱うことで，DRM 上での車両の存在するリンクや
位置を特定するアルゴリズムである．確率論的アルゴリズムは，
2. 3
処理時間
以下の状況下におけるリアルタイムマップマッチングの処理
速度を見積もることにする．
•
車両データを 5 分に一度の通信により取得する．
•
車両がデータを送信するタイミングはランダムである．
この状況下で，日本全国の地図を 10 領域に分割して，それぞ
れの領域に 1 サーバずつ割り振ってマップマッチング処理させ
ることを想定すると，現状の車両台数約 90 万台を処理するた
めには 1 サーバ 10 万台程度の処理能力が必要となる．1 サー
バあたり 10 プロセス程度までで処理させる場合，1 万∼10 万
台の車両データをリアルタイム処理するために車両 1 台当たり
にかけられる処理時間は 3∼30(msec) である．このことより，
今回提案する手法では，1 プロセスで車両 1 台当たり処理時間
30(msec)，5
3.
3. 1
分間で車両 1 万台の処理を目標とした．
類似検索を利用したマップマッチング処理
概
要
今回我々が提案する類似検索を利用したマップマッチング処
理について説明する．上述にもある通り，オフラインで時間か
けて高精度にマップマッチング処理した過去の大量の走行情報
をあらかじめデータベース上に登録し，その結果を類似検索・
参照することで間接的にマップマッチング処理を行う，類似検
する．今回の実験では，以下で定義される Euclid 距離 D を使
索を利用した Lookup
用する．
table
方式のマップマッチングの手法で
v
u 2N
u∑
(i)
(i)
D(q, p ) ≡ t (qk − pk )2 .
ある．
図 1 に具体的な処理の流れを示す．まず，データベースのレ
コードデータ内の属性として以下の 3 つのデータを事前に登録
する．
•
マップマッチング処理済みの緯度経度データ
•
特定された 2 次メッシュ番号
•
特定されたリンク番号
ここで q と p(i) は，式 (1) に従い構成された検索対象と被検索
対象の特徴ベクトルである．
この時のマップマッチング処理済みの緯度経度データは道路上
の位置まで正確に特定されているものとする．その緯度経度
データと紐付けて 2 つ道路情報（2 次メッシュ番号，リンク番
号）を登録する．2 次メッシュ番号とは DRM の地図単位を管
理する番号であり，リンク番号とは各 2 次メッシュ内でのリン
クを管理する番号である．
この状況下で大まかに次の
5
つのステップ経て道路を特定
する．
(1)
GPS
測位による L 秒間の緯度経度データを複数点取
得する．
このデータから特徴ベクトルを作成する．
(3)
最新の位置データを中心とする矩形窓の範囲検索を行
い，類似検索の被検索対象の数を絞り込む．
絞り込まれた被検索対象の特徴ベクトルを検索対象と
して，データベース上の複数の被検索対象である特徴ベクトル
との類似度をそれぞれ算出する．
(5)
複数の被検索対象の中で類似度の最も高い被検索対象
の道路情報（2 次メッシュ番号，リンク番号）を取得し，マッ
プマッチング結果とする．
3. 2
今回の実験では，クエリや被検索対象レコードの特徴ベクト
ルとして以下のデータ配列を使用した．
{
xi ≡
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)
に式 (1) のような特徴ベクトルに事前に加工した上で使用した．
表 3 は，加工した点列データセットの点列長，サンプリング周
Xi
if
Yi−N
if
1<
=i<
=N
N +1<
=i<
= 2N
期，点列内の点数を示したものである．
(2)
ここで車両の各時刻での緯度経度座標を (Xi , Yi ) (i = 1 ∼ N )
とした．以下ではこのような時系列的な複数の点の集合を点列
と呼ぶことにする．
このような点列を採用する理由は，レコードデータから不
自然な走行経路のデータを除外することができるからである．
今回の実験では，レコードデータにマップマッチング処理後の
データからなる点列を使用する．この処理後の点列には，2 本
の道路が並走している場所や交差点など道路が交差するような
場所での道路を飛び移りながら移動するといった不自然な走行
経路のデータが存在しない．そのため，自然な走行経路データ
のみのレコードデータを被検索対象とすることができる．
3. 3
実験と評価
標とリンク番号の情報が存在する．今回の実験では，株式会社
特徴ベクトル
(x1 , x2 , x3 , · · · , x2N )
4.
と取得日時・時刻データ
(2)
(4)
(3)
k=1
今回の実験では，データベースのレコード数の違いによる
マップマッチングの精度への影響を知るために，表 4 に示した
レコード数の異なるデータベースを採用した．使用したデータ
は
2014
年
9
月のデータで，それぞれ
DB1
は
9
月最初の土日
月の 3 日分，DB2 は 9 月全土日月の 12 日分，DB3 は 9 月一
か月分の点列データである．
一方，クエリに使用したデータは季節や長期休暇期間のマッ
プマッチングの精度への影響を知るために，表 5 に示した通常
日，冬季，ゴールデンウィーク (GW)，お盆の 4 通り全 35 日
分の点列データを使用した．クエリは各日付 1 万件を実施した．
また，これらデータベースに登録するレコードデータや次項
で説明するマップマッチング成功率を算出するための正解デー
タとして，前述のマップマッチング処理後のデータを使用した．
類似度の定義
検索対象とデータベース上の被検索対象との類似度を算出す
るために，特徴量空間内での 2 つのデータどうしの距離を使用
（注 1）：マップマッチングのアルゴリズムに関しては非公開．概要に関しては文
献 [32] を参照頂きたい．
図
1 類似検索を利用したマップマッチング処理の流れ．ここでは緯度経度データから構成され
る特徴量ベクトルを使用．
表
2 各 2 次メッシュにおける DRM の概要
2 次メッシュ名 リンク数 平均リンク長 基本ノード数
大阪西南部
6659 本
119.2m
4392 点
大阪東南部
10654 本
114.8m
7143 点
大阪西北部
8957 本
124.2m
5984 点
大阪東北部
12507 本
114.3m
8152 点
表
特定した道路が正解データの道路と一致した割合
(b)
特定した走行経路が正解データの走行経路と一致した
割合
評価指標 (a) は以下の式 (4) で与えられる．
正解データのリンク番号と一致した点列内の点の数
× 100 (%)
クエリに使用した点列内の点の総数
(4)
3 点列データセット
これは，マップマッチング処理により特定した道路（リンク番
点列長 L（秒）
サンプリング周期 M （秒/点）
点数 N （点）
300
10
30
表
(a)
4 データベース登録レコードの概要
号）と正解データの道路とが完全に一致した点列内の点の数を，
点列内の点の総数で割り，百分率で表記した評価指標である．
以下ではマップマッチング（MM）成功率［完全一致］と表記
する．
データベース レコード数（件） データ容量（GB）
DB1
DB2
DB3
43 万
約 188 万
約 549 万
0.4
約 1.8
約 5.3
約
評価指標 (b) は以下の式 (5) で与えられる．
約
正解データのノード番号と一致した点列内の点の数
× 100 (%)
クエリに使用した点列内の点の総数
(5)
表
5 クエリに使用したデータの概要
種類
内容
通常日
2014 年 10 月全土日月の 12 日
2015 年 1 月全土日月の 13 日
2015 年 5 月 2-6 日の 5 日
2014 年 8 月 13-17 日の 5 日
冬季
GW
お盆
これは，マップマッチング処理により特定したリンク番号を構
成する
2
つのノード番号のうち少なくとも
1
つのノード番号
と，正解データのリンク番号を構成する 2 つのうちどちらかの
ノード番号とが一致した点列内の点の数を，点列内の点の総数
で割り，百分率で表記した評価指標である．今回の実験では，
レコードデータにマップマッチング処理後の点列を使用するた
め，レコードデータはすべて自然な走行経路のデータである．
4. 2
マップマッチングの精度の評価指標
今回の実験では，マップマッチングの精度の評価指標として
以下の 2 種類を定義する．
また，隣接するリンクどうしは共通のノードで接続しているた
め，隣接する全てのリンクのリンク番号は必ず 1 つ同じノード
番号を含む．このことから，正解データとどちらか片方のノー
ド番号が一致していれば，正解データと同じ走行経路であると
5.
判断できるため，走行経路の特定の評価指標を式 (5) と定義し
た．以下ではマップマッチング（MM）成功率［片方一致］と
表記する．
4. 3
実験結果
以下のすべての実験計測はシングルプロセスで処理させた結
果である．表 6，表 7，表 8 はレコード数の異なる 3 種類のデー
実
装
タベースを使用し，通常日，冬季，お盆，GW の 4 つの期間の
これらの実験を PostgreSQL
(v.9.4)
上に実装し，マップマッ
データをクエリに使用した場合の平均マップマッチング成功率，
チングの精度と処理時間を計測した．使用したサーバのスペッ
1
クは以下の通りである．
験結果である．また，図 4 と図 5 は各日付でマップマッチング
クエリあたりの候補点列数，1 クエリあたりの処理時間の実
•
Windows Serever 2012 R2 Standard (x64)
成功率をグラフにしたものである．また，表 9 は，1 プロセス
•
Intel(R) Xenon(R) CPU E5-2690 0 @ 2.90GHz×2
での 1 クエリあたりの処理時間の平均値と，この処理時間をも
•
Memory 768GB
とに 5 分間隔で通信を介してランダムに送信される車両データ
また、実装に際して類似検索を行う前段階で行う範囲検索の
矩形窓の大きさを決める必要がある．図
2
は矩形窓の大きさ
を処理する場合の 5 分間での処理可能車両台数を示したもので
ある．
とマップマッチング成功率の関係をグラフ化したものである．
40m
を過ぎた付近からマップマチング成功率の改善が鈍化し始
表
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
めることが分かる．このことから今回の実験では，マップマチ
ング成功率の改善が鈍化し始める 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 を使用している．
表
9 1 プロセスでのマップマッチング処理時間．
データベース名
DB1
DB2
DB3
1 クエリあたりの
5 分間での
処理時間 (msec) 処理台数（台）
4.98
60240
9.48
31645
27.15
11049
1: 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.
特に交通量の多い地域の 2 次メッシュ4 つ分の領域にデータを
察
限定して実験を実施した．さらに，取り扱う 2 次メッシュの数
マップマッチング成功率は，完全一致の場合，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
測位による誤差のために，端の点が右折，直進，左折のど
図
6 点列内の各点におけるマップマチング成功率 [完全一致] のグラ
フ．使用したデータは通常日（2014 年 10 月 4 日）である．縦
軸の単位は [%] である．横軸は点列内の点の位置を表している．
第 1 点が最過去の点，第 30 点が最新の点．
の行動をとった点であるかの曖昧さが生じる．一方で，点列内
部の点はその前後に隣接点が二点存在するため，GPS 測位によ
7.
おわりに
る誤差が存在しても，右折，直進，左折のどの行動を取った点
であるかは前後の点との位置関係から絞られるため，端の点に
本論文では，デジタコからオンラインで取得した大量の位置
比べてマップマッチング成功率が高い．また，図 6 からは，端
データをリアルタイムに処理可能な，類似検索を利用したマッ
の点から真ん中の点になるにつれて徐々に正しい走行経路に矯
プマッチング処理を提案し，十分な精度と処理速度を得られる
正されていることが見て取れる．例えば，点列内の第 1 点から
ことを示した．さらに，このようなマップマッチング結果に車
第 5 点と第 29 点，第 30 点のデータを使用しない場合，完全一
速データを加えることで，リアルタイムの交通状況の把握が見
致のマップマッチング成功率は DB1 で 86.2%，DB2 で 88.4%，
込めると考えている．
DB3
で 89.8%と 1.1 から 1.8 ポイントマップマッチング成功率
今回はデジタコデータを利用したが，より一般的なセンサ
データに同じような方法を使用し，類似検索をすることで処
が改善する．
レコード数の違いによるマップマッチング成功率への影響で
理コストのかかる分析を迅速に行うことが可能である．また，
あるが，DB1 に比べて DB3 のレコード数が約 12.8 倍に増加し
データベース上での Lookup
たことに対し，マップマッチング成功率［完全一致］は 84.4%か
分析データ量が増大した場合でも Lookup
ら 88.5%の 4.1 ポイント，マップマッチング成功率［片方一致］
全てコピーすることで，容易に並列化が可能である．今後，さ
は 89.6%から 92.4%の 2.8 ポイント改善された．ただし，さら
まざまなセンサデータで同様の方式を検討する予定である．
table
方式を採用したことにより，
table
を別サーバに
に精度を上げる場合，単純にレコードデータを増やすことは効
率が良いとは言えない．これは，レコード内のデータ間で似通っ
たデータばかりが増加する傾向にあるためであり，稀なデータ
を重点的に補充したり，各道路に対応するレコード数を見なが
ら，レコード数の少ない個所を補充する処理が必要になると考
える．また，GPS 測位時の誤差が検索窓の大きさである 80m
四方の領域を超える場合や，高速道路上の車両が低速で一般道
の車両と区別できない場合を改善するこで，さらにマップマッ
チング成功率を向上させることが可能であると考える．
また，図 4 と図 5 から読み取れるように，季節や長期休暇期
間によるマップマッチング成功率への影響に大きな違いは無い
ことが分かった．
処理時間と処理可能台数は，表
60240
9
にあるように，DB1 で
台，DB2 で 31645 台，DB3 で 11049 台といずれも当初
の目標であった 1 万台を超える値が得られた．今回の実験では，
文
献
[1] 国土交通省: プラン２００９に定められた各施策の中間実施状況
及び評価（資料２），
http://www.mlit.go.jp/common/001047374.pdf.
[2] 道 路 管 理 者・道 路 コ ン サ ル 向 け 交 通 現 象 分 析 デ ー
タ 提 供 サ ー ビ ス（FUJITSU イ ン テ リ ジェン ト デ ー タ
サ ー ビ ス / 商 用 車 プ ロ ー ブ デ ー タ サ ー ビ ス ） ，
http://jp.fujitsu.com/solutions/cloud/saas/application/roadanalysis/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.
[6] Bentley, J.L., Mauer, H.A., 1980. Ecient worst-case data
structures for range searching. Acta Inf. 13, 155―168.
[7] Bernstein, D., Kornhauser, A., 1996. An introduction to map-matching for personal navigation assistants.,
http://www.njtude.org/reports/mapmatchintro.pdf, Accessed
June 19, 2002.
[8] Phuyal, B., 2002. Method and use of aggragated dead reckoning sensor and GPS data for map-matching. In: proceedings of the Institute of Navigation (ION) annual conference,
Portland, OR (20―27 September).
[9] Taylor, G., Brunsdon, C., Li, J., Olden, A., Steup, D., Winter, 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 systems. IEEE Symposium on Intelligent Vehicle 1, 172―177.
[11] Greenfeld, J.S., 2002. Matching GPS observations to locations 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: Proceedings of the 7th International Conference on Global Navigation 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, Scientic and Statistical Database Management. In: Proceedings of the International Working Conference, vol. 16. pp. 437―438.
[15] Blazquez, C.A., Vonderohe, A.P., 2005. Simple mapmatching algorithm applied to intelligent winter maintenance 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 Geoinformatics, 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 Transportation 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. Mapmatching in complex urban road networks. Brazilian Journal of Cartography (Revista Brasileira de Cartograa) 55
(2), 1―18.
[24] Kim, W., Jee, G., Lee, J., 2000. Ecient 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-
[26]
[27]
[28]
[29]
[30]
[31]
[32]
matching algorithm used in vehicle navigation system. IEEE
Proceedings on Intelligent Transportation Systems 2, 1246
―1250.
Najjar, M.E., Bonnifait, P., 2003. A roadmap matching
method for precise vehicle Localization using belief theory
and Kalman ltering. In: The 11th International Conference in Advanced Robotics, Coimbra, Portugal, June 30―
July 3.
Syed, S., Cannon, M.E., 2004. Fuzzy logic-based map
matching algorithm for vehicle navigation system in urban canyons. In: Proceedings of the Institute of Navigation
(ION) National Technical Meeting, 26―28 January, California, USA.
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. Operat. 10 (3), 103―115.
Fuchs, H., Kedem, Z.M., Naylor, B.F., 1980. On visible surface generation by a priori tree structures. Comput. Graph.
14, 124―133.
Pyo, J., Shin, D., Sung, T., 2001. Development of a map
matching method using the multiple hypothesis technique.
In: IEEE Proceedings on Intelligent Transportation Systems, pp. 23―27.
株式会社富士通交通・道路サービス,
http://pr.fujitsu.com/jp/news/2015/08/3-1.html
濱島光宏, 商用車プローブデータの収集と活用可能性 (特集 ビッ
グデータ), 交通工学研究会機関誌「交通工学」 2015 年 1 月
号（Vol.50, No.1）