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 table 方式の処にさまざまなセンサデータを記録するようになり，通信によっ理である．Lookup table 方式は，問い合わせ時には短時間で完て 1 秒間隔でセンサデータを取得することが可能である．デジ了する検索処理のみを実行すればよいため，高精度な結果を高タコに組み込まれているセンサデータの 1 つが GPS センサで速に取り出すことが可能である．また，Lookup table 方式を採ある．国土交通省は，デジタコの普及・義務化を進めており，用することで，処理が増大した場合でも，別サーバに Lookup

現在，日本全体の商用車トラックの台数約 90 万台の 38% に相table を全てコピーするだけで簡単に対応可能であり，処理の並当する約 34 万台の商用車トラックにデジタコが搭載され，そ列化がとても容易である．ところが，通常の Lookup Table 方のデータ件数は年間 1 兆件を超える [1]．取得した大量データの式で用いられる被検索対象の値とキーの完全一致検索は，緯度利活用についてもビジネスとして提供され始めており [2]，今後

経度データのような浮動小数値を登録データとするマップマッ

より大量のデータが蓄積されていくことでさらなる利活用の活チングには用いることができない．そこで，被検索対象の値と性化が予想される．

キーの値に僅かなずれがあったとしても類似した値のキーをこれら取得した車両の位置データに対して，有益な情報を得取得できるように，類似検索手法を取り入れることで Lookup

るために最初に実施される処理がマップマッチング処理である．

table 方式のマップマッチングの手法を実現した．本論文では，

マップマッチング処理とは，取得した緯度経度データから車両提案方式により従来のマップマッチング方式と同程度のマップの存在する道路を特定する処理であり，車両の位置と現実の道マッチング精度と，1 サーバで数万台規模のマップマッチング

路を結びつける交通情報分析の基本となる処理である．

処理をリアルタイムに達成できることを示す．

デジタコから送られてくる大量の位置データを利用したマッ

今回特に、車両データがデータベース上で管理されることをプマッチング処理がリアルタイムに可能となれば，リアルタイ

想定し，PostgreSQL を使用したマップマッチング処理の精度

と速度に関する実験を行った．

車両の現在の移動行動から未来の存在確率の高い領域を割り

本論文は以下の通り構成されている．2 章では，従来のマッ出し，DRM 上での車両の存在するリンクや位置を特定するア

プマッチング処理について述べる．3 章では，今回提案する類

ルゴリズムである．より高度な技術や処理を組み合わせたアル似検索を利用したマップマッチング処理に関して詳しく述べる．

ゴリズムは，Kalman lter [24] [25]，belief theory [26]，fuzzy

4 章では，今回の実験で使用するデータセット，実験内容と結logic method [27]- [29]，ベイズ推定の応用 [30] を取り入れるこ果の評価について述べる．5 章では，実験結果を示す．6 章でとで，DRM 上での車両の存在するリンクや位置を特定するアは，実験結果の内容を考察する．7 章では，今回の実験を総括

ルゴリズムである．

する．

デジタコデータを使用する場合には，緯度経度データのみ

2.

従来のマップマッチング処理

2. 1

概

要

を利用したマップマッチングアルゴリズム [5] [10] [11] [20] [17][25] [28] を使用する必要がある．表 1 は緯度経度データのみを利用したマップマッチングアルゴリズムにおける精度を示した

従来のマップマッチング処理は，デジタル道路地図 (Digital

ものである．ここでマップマッチング成功率［完全一致］とはRoad Map，以下 DRM) [4] をもとに，道路の緯度経度情報を後述するマップマッチングの精度の評価指標である．それぞれ

用いて車両の位置データから道路を特定を行う．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 分間で車両 1 万台の処理を目標とした．

3.

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

3. 1

概

要

今回我々が提案する類似検索を利用したマップマッチング処理について説明する．上述にもある通り，オフラインで時間かけて高精度にマップマッチング処理した過去の大量の走行情報をあらかじめデータベース上に登録し，その結果を類似検索・

参照することで間接的にマップマッチング処理を行う，類似検する．今回の実験では，以下で定義される Euclid 距離 D を使

索を利用した Lookup table 方式のマップマッチングの手法で

用する．

ある．
図 1 に具体的な処理の流れを示す．まず，データベースのレ

v
u 2N
u∑
(i)
(i)
D(q, p ) ≡ t (qk − pk )2 .

コードデータ内の属性として以下の 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
Yi−N

1<
=i<
=N
if N + 1 <
=i<
= 2N

if

期，点列内の点数を示したものである．
(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.2m4392 点
大阪東南部
10654 本114.8m7143 点
大阪西北部
8957 本124.2m5984 点
大阪東北部
12507 本114.3m8152 点(a)

特定した道路が正解データの道路と一致した割合(b)

特定した走行経路が正解データの走行経路と一致した

割合
評価指標 (a) は以下の式 (4) で与えられる．
正解データのリンク番号と一致した点列内の点の数
× 100 (%)
クエリに使用した点列内の点の総数(4)

表 3 点列データセット

これは，マップマッチング処理により特定した道路（リンク番

点列長 L（秒）サンプリング周期 M （秒/点）

点数 N （点）

300

10

30

表 4 データベース登録レコードの概要号）と正解データの道路とが完全に一致した点列内の点の数を，
点列内の点の総数で割り，百分率で表記した評価指標である．
以下ではマップマッチング（MM）成功率［完全一致］と表記する．

データベース レコード数（件） データ容量（GB）

DB1
DB2
DB3

約 43 万約 0.4

約 188 万約 1.8

約 549 万約 5.3

評価指標 (b) は以下の式 (5) で与えられる．
正解データのノード番号と一致した点列内の点の数
× 100 (%)
クエリに使用した点列内の点の総数(5)

表 5 クエリに使用したデータの概要

これは，マップマッチング処理により特定したリンク番号を構

種類

内容

成する 2 つのノード番号のうち少なくとも 1 つのノード番号

通常日

2014 年 10 月全土日月の 12 日
2015 年 1 月全土日月の 13 日
2015 年 5 月 2-6 日の 5 日2014 年 8 月 13-17 日の 5 日と，正解データのリンク番号を構成する 2 つのうちどちらかの

冬季

GW
お盆

ノード番号とが一致した点列内の点の数を，点列内の点の総数
で割り，百分率で表記した評価指標である．今回の実験では，
レコードデータにマップマッチング処理後の点列を使用するため，レコードデータはすべて自然な走行経路のデータである．

4. 2

マップマッチングの精度の評価指標

今回の実験では，マップマッチングの精度の評価指標として
以下の 2 種類を定義する．

また，隣接するリンクどうしは共通のノードで接続しているた
め，隣接する全てのリンクのリンク番号は必ず 1 つ同じノード番号を含む．このことから，正解データとどちらか片方のノード番号が一致していれば，正解データと同じ走行経路であると判断できるため，走行経路の特定の評価指標を式 (5) と定義した．以下ではマップマッチング（MM）成功率［片方一致］と
表記する．
4. 3

実

実験結果

5.

以下のすべての実験計測はシングルプロセスで処理させた結果である．表 6，表 7，表 8 はレコード数の異なる 3 種類のデー

装

これらの実験を PostgreSQL (v.9.4) 上に実装し，マップマッ

タベースを使用し，通常日，冬季，お盆，GW の 4 つの期間のデータをクエリに使用した場合の平均マップマッチング成功率，チングの精度と処理時間を計測した．使用したサーバのスペッ

1 クエリあたりの候補点列数，1 クエリあたりの処理時間の実

クは以下の通りである．

験結果である．また，図 4 と図 5 は各日付でマップマッチング•

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 成功率 (%)

ング成功率の改善が鈍化し始める 40m の倍の大きさである中心から四方に 80m の矩形窓に設定した．

完全一致 片方一致

85.0
84.9
81.9
84.3
84.4

通常日
冬季
お盆

GW
全平均

表7

90.3
90.0
87.6
89.1
89.6

候補点列数 処理時間

(点列)
731.0
748.2
662.0
695.5
722.5

(msec)
5.13
4.99
4.96
4.59
4.98

類似検索を利用したマップマッチング処理の結果．データベース
として DB2 を使用．

MM 成功率 (%)
完全一致 片方一致

87.9
87.5
85.4
87.1
87.3

通常日
図 2 範囲検索時の矩形窓の大きさとマップマチング成功率 [完全一致]

冬季のグラフ．縦軸の単位は [%] である．横軸は矩形窓の一辺の長

お盆

GW

さの半分の値である．

全平均
4. 4

92.2
91.7
90.2
91.1
91.6

候補点列数 処理時間

(点列)
3191.73259.22888.73050.23153.2(msec)
9.66
9.51
9.32
9.14
9.48

マップマッチング用 SQL 文

図 3 は類似検索利用したマップマッチングの SQL 文の主要部分である．11 行目の query_LonXLatY は式 (1) のマップマッ

表8

類似検索を利用したマップマッチング処理の結果．データベース
として DB3 を使用．

チングしたい点列である．10 行目の tbl_carDataAfterMM

MM 成功率 (%)

は過去のマップマッチング済み点列が登録されているテーブル

完全一致 片方一致

であり，tbl_range_current はマップマッチングしたい点列の最新点の位置から算出した範囲検索窓の緯度経度座標のテーブルである．
まず，7 行目の各点列の最新点の緯度経度座標が格納された

89.2
88.6
87.0
88.2
88.5

通常日
冬季
お盆

GW
全平均

point 型の newestPoint に対して，7 行目から 9 行目で矩形の範囲検索を行い，レコードの絞込みを行っている．この絞込みの結果が，10 行目の tbl_candCarData である．11 行目で緯度経度データからなる点列 tbl_candCarData.LonXLatY
に対して，query_LonXLatY との Euclid 距離を計算し，この距離が最も短いレコードの 2 次メッシュ番号とリンク番号を2 行目と 3 行目で得ている．

このとき，7 行目で参照している newestPoint に対しては，
空間インデックスである SP_GiST を使用している．

表9

93.0
92.4
91.3
91.8
92.4

候補点列数 処理時間

(点列)
9396.19630.78434.98908.49276.3(msec)
29.43
27.95
23.52
23.18
27.15

1 プロセスでのマップマッチング処理時間．

データベース名

DB1
DB2
DB3

1 クエリあたりの5 分間での処理時間 (msec) 処理台数（台）
4.98
60240
9.48
31645
27.15
11049

1: SELECT2:

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%といずれも当初の目標であった

特に交通量の多い地域の 2 次メッシュ4 つ分の領域にデータを限定して実験を実施した．さらに，取り扱う 2 次メッシュの数が増える場合でも，空間インデックスを付与することで線型的な処理時間の増大は避けられるものと考える．

80%を超え，表 1 に匹敵する成功率が得られた．また，片方一致の場合，DB1 で 89.6%，DB2 で 91.6%，DB3 で 92.4%と走行経路の特定は 90%を超える結果が得られた．これは検索に使用したデータを点列にしたことによる効果であると考える．図
6 は，実際に点列内の各点のマップマッチング成功率をグラフにしたものである．第 1 点目が時系列的に最過去の点であり，第 30 点目が時系列的に最新の点である．第 1 点目に比べて範囲検索時に基準とした第 30 点目側のマップマッチング成功率が若干高い傾向にあるが，全体として両端のマップマッチング
成功率が低く，点列の真ん中に近づくにつてれてマップマッチ
ング成功率が高くなる傾向にある．これは，点列の両端では点列内の隣接点が一点しか存在せず，点列内部の点に比べて GPS

図 6 点列内の各点におけるマップマチング成功率 [完全一致] のグラ測位による誤差が道路の特定に大きく影響を与えるためである

フ．使用したデータは通常日（2014 年 10 月 4 日）である．縦と考える．例えば，点列の端の点が交差点付近に位置する場合，軸の単位は [%] である．横軸は点列内の点の位置を表している．

GPS 測位による誤差のために，端の点が右折，直進，左折のど

第 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 table 方式を採用したことにより，たことに対し，マップマッチング成功率［完全一致］は 84.4%か分析データ量が増大した場合でも Lookup table を別サーバにら 88.5%の 4.1 ポイント，マップマッチング成功率［片方一致］

全てコピーすることで，容易に並列化が可能である．今後，さは 89.6%から 92.4%の 2.8 ポイント改善された．ただし，さら

まざまなセンサデータで同様の方式を検討する予定である．

に精度を上げる場合，単純にレコードデータを増やすことは効率が良いとは言えない．これは，レコード内のデータ間で似通ったデータばかりが増加する傾向にあるためであり，稀なデータを重点的に補充したり，各道路に対応するレコード数を見ながら，レコード数の少ない個所を補充する処理が必要になると考える．また，GPS 測位時の誤差が検索窓の大きさである 80m
四方の領域を超える場合や，高速道路上の車両が低速で一般道の車両と区別できない場合を改善するこで，さらにマップマッ
チング成功率を向上させることが可能であると考える．
また，図 4 と図 5 から読み取れるように，季節や長期休暇期
間によるマップマッチング成功率への影響に大きな違いは無い
ことが分かった．
処理時間と処理可能台数は，表 9 にあるように，DB1 で60240 台，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-theart and future research direction. Transportation ResearchPart C: Emerging Technologies 15, 312―328, 2007.
[4] 一般財団法人 日本デジタル道路地図協会, http://www.drm.jp/.
[5] White, C.E., Bernstein, D., Kornhauser, A.L., 2000. Somemap matching algorithms for personal navigation assistants.
Transportation Research Part C: Emerging Technologies 8(1), 91―108.
[6] Bentley, J.L., Mauer, H.A., 1980. Ecient 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 transporttelematics 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 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. Developmentof 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 topologicalmap-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 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-

[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 highaccuracy fuzzy logic-based map matching algorithm for roadtransport. 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）