Learn AI Create the Future — with Pranay
Main site

Retail, Demand and Supply Chain

Snapping noisy GPS to roads

Raw GPS readings wobble enough that a delivery bike can appear to be on the wrong road entirely, so the reported position has to be snapped to the road network, not trusted directly.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. Where you have already seen it
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

Raw GPS readings wobble enough that a moving vehicle can appear to be on the wrong road entirely.

Think about writing on ruled notebook paper with a shaky hand. Your pen wanders slightly above and below the printed line the whole time, but everyone reading your handwriting understands you meant to stay on that line. A reader mentally "snaps" your wobbly writing back to the ruled line without even noticing they are doing it.

A delivery bike's GPS signal wobbles the same way. Except there is no ruled line drawn on the real world — only the road, which the GPS device cannot see.

Why it exists

GPS position is never exact. Tall buildings, flyovers, tunnels, and even normal atmospheric interference can shift a reported position by five, ten, sometimes twenty metres from where the vehicle actually is.

On a wide-open road, that wobble barely matters. It becomes a real problem on a divided highway, where two carriageways run parallel only a few metres apart. A wobble at the wrong moment can make the GPS say a bike is on the wrong carriageway. Or worse — floating inside a river, when the actual road only follows the riverbank.

Map matching takes a wobbly sequence of raw GPS points and corrects it to the most plausible path along the real road network. It turns "this delivery bike is standing in the middle of a lake" into "this delivery bike is on the road next to the lake."

How it works

Raw GPS readings, delivery bike moving along one road:

  Point 1: near the correct road
  Point 2: near the correct road
  Point 3: near the correct road
  Point 4: a bad reading — closer to a DIFFERENT, parallel road
  Point 5: near the correct road again

Snapping each point independently: point 4 gets assigned to the wrong road.
Snapping the whole SEQUENCE together: one noisy point, surrounded by five
  consistent points on the real road, gets corrected back — a real vehicle
  does not teleport to another road and back for a single reading.

The key idea is that a single noisy reading should not be trusted on its own. The points immediately before and after it are strong evidence about where the vehicle actually was.

Where you have already seen it

  • Google Maps' blue dot snapping onto the road you are driving on. It does this even when your raw GPS position briefly drifts into a nearby field.
  • A cab app showing your driver's car moving smoothly along the street, instead of jumping erratically between parallel lanes.
  • Delivery tracking showing a rider "on Main Road" rather than jittering between two roads that happen to run close together.

Remember this

  • Raw GPS positions are noisy, sometimes badly enough to appear on the wrong road entirely.
  • Trusting each GPS reading independently means a single bad reading can look like a wrong turn that never happened.
  • Looking at the whole sequence of recent positions together, not one point at a time, is what makes map matching reliable.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install numpy

Minimal runnable code

Two roads run parallel, 15 metres apart — like two carriageways of a divided highway. A bike genuinely stays on one of them the whole time, but one GPS reading gets a large error. We compare snapping each point independently against a sequence-aware method that penalises implausible road switches.

map_matching.py
import numpy as np

rng = np.random.default_rng(15)

# Two parallel roads, 15 metres apart -- like two carriageways of a divided highway.
roads = {"road_A": 0.0, "road_B": 15.0}
road_names = list(roads.keys())

# A bike is really travelling along road_A the whole time. GPS noise wobbles
# the reported position -- and one reading gets a big multipath error, common
# under a flyover or between tall buildings, that lands it closer to road_B.
n_points = 10
true_y = np.zeros(n_points)
noise = rng.normal(0, 4, n_points)
noise[5] = 12.0   # a single bad GPS fix, closer to road_B (15) than road_A (0)
gps_y = true_y + noise

print("noisy GPS y-position at each point:", np.round(gps_y, 1).tolist())
print()

# Naive map matching: snap each point independently to its closest road.
naive_match = [road_names[np.argmin([abs(y - roads[r]) for r in road_names])] for y in gps_y]
print("naive per-point snap:", naive_match)
print()


def viterbi_match(gps_y, roads, switch_penalty):
    names = list(roads.keys())
    n, k = len(gps_y), len(names)
    cost = np.zeros((n, k))
    back = np.zeros((n, k), dtype=int)

    cost[0] = [abs(gps_y[0] - roads[r]) for r in names]
    for t in range(1, n):
        for j, rj in enumerate(names):
            obs_cost = abs(gps_y[t] - roads[rj])
            options = [cost[t - 1, i] + (0 if i == j else switch_penalty) for i in range(k)]
            back[t, j] = int(np.argmin(options))
            cost[t, j] = obs_cost + min(options)

    path = [int(np.argmin(cost[-1]))]
    for t in range(n - 1, 0, -1):
        path.append(back[t, path[-1]])
    path.reverse()
    return [names[i] for i in path]


# Switching roads mid-route is expensive: it should only happen if the
# evidence is strong and consistent, not from one noisy point.
viterbi_result = viterbi_match(gps_y, roads, switch_penalty=8.0)
print("sequence-aware (Viterbi) match:", viterbi_result)
print()

true_path = ["road_A"] * n_points
print("naive accuracy:   ", sum(a == b for a, b in zip(naive_match, true_path)), "/", n_points, "correct")
print("Viterbi accuracy: ", sum(a == b for a, b in zip(viterbi_result, true_path)), "/", n_points, "correct")
Output
noisy GPS y-position at each point: [-5.7, -3.7, 1.6, -2.1, 2.1, 12.0, -5.8, 4.1, -2.4, 8.4]

naive per-point snap: ['road_A', 'road_A', 'road_A', 'road_A', 'road_A', 'road_B', 'road_A', 'road_A', 'road_A', 'road_B']

sequence-aware (Viterbi) match: ['road_A', 'road_A', 'road_A', 'road_A', 'road_A', 'road_A', 'road_A', 'road_A', 'road_A', 'road_A']

naive accuracy:    8 / 10 correct
Viterbi accuracy:  10 / 10 correct

What actually happened

The naive method looks at each reading in total isolation. Points 6 and 10 happened to land closer to road_B, so that is where they get assigned — two wrong answers out of ten, even though the bike never left road_A.

viterbi_match is a small dynamic-programming algorithm. For every point and every candidate road, it tracks the cheapest possible way to have arrived there — either continuing on the same road as the step before (free), or switching from the other road (paying switch_penalty). Because switch_penalty=8.0 is larger than one noisy point's evidence is worth, the algorithm decides it is cheaper to eat that single point's mismatch and stay on road_A, than to pay the penalty of switching there and back. That single design decision fixes both errors at once.

Common mistakes

Setting the switch penalty too low. With little or no penalty, this collapses back into the naive method — every noisy point can trigger a road switch.

Setting the switch penalty too high. A genuine lane change or turn becomes very expensive to detect, and the algorithm can stay locked onto the wrong road for too long after a real change of direction.

Using straight-line distance on a real road network without accounting for connectivity. Real map matching needs to know which roads actually connect to which — a candidate road that is physically close but has no path to the previous point's road should never be reachable in one step, however small the observation cost looks.

Forgetting this needs to run in real time. A delivery app cannot wait for the whole trip to end before deciding where the bike currently is. Production map matchers process points as they arrive, using only the recent window of the sequence, not the entire future.

Try it yourself

Add a second consecutive bad reading — set both noise[5] = 12.0 and noise[6] = 13.0. Re-run and watch the Viterbi method's decision change: two consistent noisy points in a row are now real evidence of an actual road switch, not something to override.

What to learn next

Researcher — Mathematics and papers.

Map matching as a Hidden Markov Model

Newson and Krumm (2009), Hidden Markov Map Matching Through Noise and Sparseness, ACM SIGSPATIAL, formalise map matching exactly as the developer example does, at full scale: the true road segment at each timestep is a hidden state, the noisy GPS reading is an observation, and the goal is the most likely hidden state sequence given the observations — solved by the Viterbi algorithm.

emission probability:    p(z_t | r) proportional to  exp( -0.5 * (gc_dist(z_t, r) / sigma_z)^2 )
transition probability:  p(r_t | r_{t-1})  based on  |route_dist(r_{t-1}, r_t) - great_circle_dist(z_{t-1}, z_t)|
  • z_t — the observed GPS point at time t
  • r, r_t — a candidate road segment
  • gc_dist — great-circle (straight-line) distance between the GPS point and the candidate segment
  • sigma_z — the standard deviation of GPS measurement error, estimated from device characteristics
  • route_dist(r_{t-1}, r_t) — the shortest path distance along the actual road network between two candidate segments

The transition term is the key insight beyond the toy example above: it penalises a candidate path whose road-network distance disagrees with the straight-line distance implied by the two raw GPS points, since a real vehicle's road-network travel distance should be reasonably close to its straight-line displacement over a short time step, and a large mismatch signals an implausible jump (or a genuinely circuitous real route, which the transition probability also has to accommodate).

Complexity and streaming constraints

Exact Viterbi decoding over a full trip is O(T * K^2) where T is the number of GPS points and K the number of road-segment candidates considered per point. Production systems bound K by only considering segments within a small radius of each raw point, and run Viterbi in a sliding window or with online forward decoding with a lag, committing to a match once enough future evidence has arrived to be confident, rather than waiting for the full trip — necessary because delivery tracking is a live service, not an offline analysis.

Beyond point-to-segment: full trajectory reconstruction

A complete map-matching system also has to choose which path was taken between two matched segments when several routes are geometrically plausible, not only which segment each point sits on. This is typically solved by extending the transition cost to also weigh route plausibility — shortest path, or a learned routing cost incorporating road class and typical travel time — rather than raw distance alone. Quddus, Ochieng and Noland (2007), Current Map-Matching Algorithms for Transport Applications, Transportation Research Part C, survey the broader family of approaches, including topological, probabilistic, and Kalman-filter-based methods that predate and parallel the HMM formulation.

Key references

  • Newson, P. & Krumm, J. (2009). Hidden Markov Map Matching Through Noise and Sparseness. ACM SIGSPATIAL GIS.
  • Quddus, M., Ochieng, W. & Noland, R. (2007). Current Map-Matching Algorithms for Transport Applications: State-of-the Art and Future Research Directions. Transportation Research Part C 15(5).
  • Viterbi, A. (1967). Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE Transactions on Information Theory 13(2). Origin of the Viterbi algorithm itself.

What to learn next