マップマッチングとは？GPSトレースを道路ネットワークにスナップする技術

マップマッチングは、ノイズの多いGPS点群を実際の道路に沿うクリーンな経路に変える、地味だが不可欠なステップです。これがないと、フリートダッシュボードはトラックが建物を貫通する様子を表示し、保険料モデルは高速道路と裏通りを区別できず、ライドシェアの行程は酔った鳩の飛行計画のようになります。これがあれば、各点は道路グラフの既知区間上の位置となり、進行方向とエッジ上の距離が付与されます。

このガイドでは、マップマッチングとは実際に何か、なぜ生のGPSでは不十分か、アルゴリズムがどう動くか、本番システムでどこに登場するかを解説します。

マップマッチングの本質

最もシンプルな形では、マップマッチングは2つの入力を取ります。時系列順のGPS測位値列（緯度、経度、タイムスタンプ、しばしば速度と方位）と、ルーティング可能な道路ネットワーク（通常はOpenStreetMapをエッジとノードのグラフに加工したもの）です。出力は、すべての測位値がそのグラフの特定エッジにスナップされ、エッジ上の正確な位置と区間メタデータが付与されたものです。

結果として得られるのは、実際のストリートに沿うポリラインと、実際に通過した道路区間のリストです。後者の出力が下流分析のロックを解除します。区間ごとの制限速度、道路クラス、右左折回数、国・地域の帰属、測位値間の直線距離ではなくエッジごとの正確な距離です。

トレースだけでは、デバイスがおおよそどこに行ったかが分かります。マッチ済みトレースは、どの道路を使ったかを教えてくれます。

生のGPSでは不十分な理由

民生用GPSは良条件で約5メートル、通常使用時のスマホや低価格トラッカーで10〜30メートルの精度です。本番テレメトリでは構造的に3つの問題がそれをさらに悪化させます。

都市の谷間。密集した都心では、高層ビルが衛星への直接見通しをブロックし、信号がガラス外壁で反射します。受信機は遅延した信号コピー（マルチパス）を見て、真の位置から1ブロック離れた、しばしば平行する街路上の位置を計算します。

コールドスタートのドリフト。デバイス起動時、確実な測位に必要な衛星捕捉に30〜90秒かかることがあります。トレースの最初の数点は50メートル以上ずれることが多く、それはまさに車両が駐車場やデポを出発しているときです。

スパースサンプリング。バッテリー駆動のIoTトラッカーは、電力節約のため30秒または1分ごとに1点しかロギングしないことがよくあります。高速道路速度では1km以上点が離れ、点間の直線が実際のルートに一致することは稀です。マッチャーは線を引くのではなく、グラフ上をルーティングしてギャップを埋める必要があります。

これらが重なると、生の測位値を真値として扱うシステムは、間違った距離・道路・課金を静かに生成します。

マップマッチングの仕組み

支配的な本番アプローチは、Newson and Krummが2009年に普及させた隠れマルコフモデル定式化です。道路グラフを隠れ状態の集合（デバイスが本当はどのエッジ上にあるか）、GPSトレースをそれらの状態のノイズ観測としてモデル化します。マッチャーを動かすのは2つの確率です。

出力確率。各測位値について、アルゴリズムは探索半径内（典型的には25〜200メートル）の候補エッジを見つけ、観測測位値を踏まえて真の位置がそのエッジ上にあることがどれくらい妥当かでスコア付けします。スコアは通常、測位値からエッジへの垂直距離のガウス分布です。

遷移確率。連続する測位値ペアについて、アルゴリズムは経過時間内に第1から第2へ移動することがどれくらい妥当かで候補エッジペアをスコア付けします。これには候補間でグラフをルーティングし、ルート距離と測位値間の大圏距離を比較する必要があります。不一致はペナルティを受け、不可能なジャンプ（川を渡る、一方通行に逆行、道路クラスが許さない速度）は潰されます。

Viterbiアルゴリズムがトレース全体で最も尤もらしいエッジ列を1パスで見つけます。OSRMとValhallaはどちらもこのアプローチに基づく本番用HMMマッチャーを提供しており、スパーストレース、時間ギャップ、デバイスがネットワークを離れた区切り点への拡張も含みます。

マップマッチングの活用シーン

マップマッチングはほぼUIを持たないバックオフィス機能ですが、多くの製品の機関室です。

• フリートテレメトリ。トラックとバンのフリートは数秒ごとに測位値をロギングします。マップマッチングはストリームをドライバー別、車両別、地域別の区間レベルの走行距離に変換し、給与計算、燃料照合、ルート遵守に供給します。
• ドライバー行動分析。急ブレーキや速度超過のイベントは、ドライバーが走っていた区間の制限速度を知って初めて意味を持ちます。それには生の測位値ではなく、マッチされたエッジが必要です。
• ライドシェアの行程再構築。乗客が運賃に異議を唱えたとき、プラットフォームはドライバーのGPSログから行程を再構築します。マッチ済みトレースは実際のストリートに沿う監査品質のポリラインと、防御可能な距離を提供します。
• 走行ベース保険。マイル別やドライブ行動別ポリシーには、行程ごとの正確な走行距離と道路クラスエクスポージャーが必要です。生GPSの5%誤差は、ポートフォリオ全体で利益と損失の差です。
• IoTアセット追跡。貨物コンテナ、Eスクーター、レンタル機材はスパースな測位値を送ります。マップマッチングは、測位値が分単位で離れていても、適切な距離で行程に縫い合わせます。
• 道路利用分析。都市と通行料当局はマッチ済みトレースを使って、物理センサーを設置せずに流量を推定し、混雑区間を特定し、モードシェアを研究します。

本番環境での落とし穴

マップマッチングはデモではクリーンに見え、実世界の負荷下では汚くなります。

スパーストレース。測位値が1km以上離れていると、マッチャーはそれらの間で1つのルートにコミットしなければなりません。妥当なルートが2つ存在すれば、間違った方が一定割合で勝ちます。候補ウィンドウを広げると改善しますが、実行時間が爆発します。

ネットワーク外区間。車両は定期的にネットワークを離れます。駐車場、私道、フェリー、砂利道など。素朴なマッチャーはこれらを最寄り道路に強制スナップし、幻の走行距離を生成します。本番マッチャーは区切り点を検出し、推測する代わりに未マッチギャップを発行します。

並行道路。高速道路と側道、分離車線のある幹線道路、密な都市グリッドはすべて、ほぼ同等にスコア付けされる候補を生成します。方位と速度の信号が（利用可能なとき）タイブレーカーになります。

複数日の縫い合わせ。一晩駐車する車両は、12時間ギャップのある1つのトレースではなく、2つの別行程を生成します。マッチング前に入力を行程に分割するのが、巨大なViterbiパスを実行するより通常安価かつ正確です。

プライバシー。マッチ済みトレースは人がどこにいつ居たかの高解像度記録です。これはGDPRや同等の規制下の個人データです。ストレージ、保持、アクセスログは機密性に合わせる必要があり、集約はパイプラインのできるだけ早い段階で行うべきです。

MapAtlasのマップマッチング

MapAtlas Map Matching APIはGPS測位値列を受け取り、道路ネットワークに沿うスナップ済みポリラインを返します。各点にはエッジID、区間メタデータ、マッチごとの信頼度スコアが付与されます。スパーストレース、ネットワーク外区間の区切り点検出、一般的な本番ユースケース（フリートテレメトリ、行程再構築、IoT追跡）を、自前のOSRMやValhallaクラスタをホストすることなく扱えます。

マッチ済み履歴ルートを最適ルートと比較する必要があるときはMapAtlas Directions APIと、マッチ済み行程の開始・終了をダッシュボードや顧客向けレシートのために人間が読める住所に変換する必要があるときはMapAtlas Geocoding APIと自然に組み合わさります。

マッチ済みトレースは派手ではありません。ただのポリラインです。しかし、課金から分析からコンプライアンスまで、すべての下流システムが、デバイスが実際にどの道路にいたかについて合意できるようにするポリラインです。