こんにちは。
マップマッチングとは、地理座標点の並びを与え（図例内の 1, 2, 3）、それらの近傍で対応するグラフのエッジ（＝用意した道路地図のリンク（＝実線））の繋がった並びを解として求めるものです（図例内の経路（＝太線））。

したがって、「近傍探索＋経路探索」ということになります。
なお与えた地理座標点が道路の位置から離れていること（図例の各垂線（＝点線）の長さ）を一種の誤差と見なすと、その解消は誤差補正処理に相当します。

理論

この問題に対し、Paul Newson and John Krumm (2009) による定式化が近年広く用いられ¹、下記の最小化解を求めます（$N$は与点の総数、$r_i$は各垂線の長さ、$L$は経路の全長。解は定数$\frac{\sigma^2}{\beta}$の値に依存します）。

\begin{align}
&\min \left(\frac{1}{2} \Sigma_{i=1}^N \left(\frac{r_i}{\sigma}\right)^2 + \frac{L}{\beta}\right)
\end{align}

これは「隠れマルコフモデル」問題と等価であり、$r_i$ の項が emission probability、$L$ の項が transition probability のモデル化に相当します。Viterbi アルゴリズムを用いて効率的に解くことができます²。

なおマップマッチングの歴史は古く、上記の定式化以前は各種の heuristic な解法が使われていました³。

マップマッチング動作例

horizon⁴（および osm2ch、osmium-tool）を動かし、そのサーバーへ web クライアントで接続し、地理座標点（GPS #1,2,3）の並びを与えました。日本の高速道路を対象⁵とした例です。

$ wget https://download.geofabrik.de/asia/japan-latest.osm.pbf
$ osmium tags-filter -o japan-motorway.osm.pbf japan-latest.osm.pbf w/highway=motorway,motorway_link
$ osm2ch --file japan-motorway.osm.pbf --out map.csv --geomf geojson --units m --tags motorway,motorway_link --contract=true
$ horizon -h 0.0.0.0 -p 32800 -f map.csv -sigma 50 -beta 30 -maplon 135.4 -maplat 35.2 -mapzoom 5
Extracting edges from 'map.csv' file...
Done in 9.954906378s
Loading graph and preparing engine...
Done in 91ns
 ┌───────────────────────────────────────────────────┐ 
 │                   Fiber v2.30.0                   │ 
 │              http://127.0.0.1:32800               │ 
 │      (bound on host 0.0.0.0 and port 32800)       │ 
 │ Handlers ............. 8  Processes ........... 1 │ 
 │ Prefork ....... Disabled  PID .............. 5948 │ 
 └───────────────────────────────────────────────────┘

参考情報