Waze-Style Navigation at Scale: Routing Engines, Map Matching, and the Traffic Model

Navigation looks like a shortest-path problem because the first thing you build is a shortest-path problem, and it works fine on a highway. It fails in a city, it fails in a tunnel, and it fails at 5pm on a Tuesday. The reasons are a road graph problem, a signal-processing problem, and a statistics problem, in that order, and none of them is the one you expect.

The scale

  a country-scale navigation service
    5M km of road network
    40M road segments (nodes and edges)
    2M nodes

    1,000 concurrent users
      - 1 route request every 10s
      - 1 location update every 1s per user
    peak: 50,000 users
      - 5,000 route requests/s
      - 50,000 location updates/s

  and every user generates
    - continuous GPS at 1Hz
    - a reroute every 20-60s as the
      ETA drifts

50,000 location updates a second is the number that shapes the architecture, because each one is not a point — it is a question about which road the user is on, and answering it wrong poisons everything downstream.

The three problems

  +----------------------------------------------------------+
  |  3. TRAFFIC MODEL                                        |
  |  speed on a road at a time, from probe traces            |
  |  "how fast is this road right now"                        |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  2. ROUTING                                               |
  |  shortest path on a directed graph with time-dependent     |
  |  weights                                                  |
  |  "given current speeds, what is the best path"            |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  1. MAP MATCHING                                          |
  |  GPS trace -> position on the road graph                  |
  |  "which road is this device on, and how far along it"     |
  +------------------------------------------------------------+

Each layer’s output is the next layer’s input, and each has a characteristic failure. Map matching fails and the route thinks you are on a parallel street. Routing fails and it sends you down a road that is closed. The traffic model fails and the ETA is consistently wrong in one direction at rush hour.

Map matching

  raw input
    1Hz GPS, 5-15m accuracy
    10 points, so a ~100m trail

  the problem
    which edges of the road graph does
    this trail correspond to, in order?

  why it is non-trivial
    - urban canyons: GPS reflects off
      buildings, a 15m error becomes 100m
    - parallel roads 20m apart: a
      surface street and an elevated
      highway, both plausible
    - underpasses and tunnels: no signal
      for 200-800m, and the position
      jumps on exit
    - one-way streets: matching onto a
      one-way in the wrong direction is
      a common error
    - U-turns made legitimately at a
      median look like a GPS failure

  the algorithm that works: HMM
    states   = candidate positions on
               nearby road segments
    emission = GPS distance to that
               candidate position
    transition = distance travelled
                  between candidates
                  (drives the state
                   continuity)
    output   = Viterbi decode, with
               backtracking to recover the
               full path

  the transition term is what does the
  work: a candidate 200m away is not
  reachable in 1 second at any legal
  speed, so it is eliminated

In the common HMM formulation, candidate road positions are hidden states. The emission probability models how plausible a GPS observation is for a candidate, commonly from distance/error. The transition probability compares network travel between candidates with observed displacement and elapsed time. Candidate generation and reachability pruning keep the state space bounded; they are not the HMM prior itself.

Two details that separate production matchers from textbook ones:

Candidate and transition bounds. Generate nearby road candidates spatially, then reject transitions whose network distance, direction, or implied speed is implausible. A Euclidean disc alone cannot see barriers, turn restrictions, or two parallel carriageways.

Tunnel handling. When the signal drops, the matcher should coast on dead reckoning — position plus heading plus speed — and treat the first post-tunnel fix as a fresh, low-confidence observation rather than a hard constraint. A matcher that demands continuity across a 400m gap will snap the device to the wrong exit when it reappears, which is one of the most visible navigation failures there is.

The routing engine

  road graph
    nodes  = intersections, turn points
    edges  = road segments, directed
    weight = travel time = length / speed
             with time-dependence from
             the traffic model

  the baseline problem
    2M nodes, 40M edges
    a naive Dijkstra explores a large
    fraction of the graph: ~200ms+ and
    huge memory per query

  the fix: contraction hierarchies
    1. PREPROCESS (offline, ~10 min)
       - add shortcut edges over
         high-importance nodes
       - rank nodes by importance
       - repeatedly contract the least
         important node, adding shortcuts
    2. QUERY
       - bidirectional upward search
         from source and target
       - a few hundred node expansions
         total
       - ~0.5ms per query

  the shape of the win
    preprocessing: expensive, rare
    query: cheap, constant-ish
    -> the whole design bets that
       queries vastly outnumber graph
       changes

Contraction hierarchies precompute shortcuts so a query searches upward from both ends. Topology changes such as a new road affect preprocessing, but weight changes are not free in a classic hierarchy either: shortcut weights must remain valid for the metric. Customizable Route Planning and Customizable Contraction Hierarchies separate topology preprocessing from a faster metric-customization phase, which is the relevant design for live traffic and user-specific costs.

The alternative family is ALT (A*, Landmarks, and Triangles), which precomputes a small set of landmark distances per node to make A* admissible and much more directed. ALT has better local updates than CH; CH has a much smaller query cost. Most production engines use CH for the fast path and accept the rebuild cost, batching graph changes.

Turn costs matter more than distance. A turn from a motorway onto a service road is not a simple edge traversal — it has a time penalty that depends on the turn type and the traffic light. Ignoring turn restrictions and turn penalties is the most common cause of “why did it send me down that impossible turn”.

The traffic model

  probe data
    phones reporting GPS
    20M users x 1Hz x a few hours
      of driving each = billions of
      matched points per day

  the pipeline
    1. map-match the traces (same
       matcher as navigation)
    2. segment them into runs of
       consistent direction
    3. attribute speed to (edge, time
       bucket, day-of-week)
    4. aggregate, smooth, and
       sanity-filter

  the statistical problem
    a single trace on a road at a time
    tells you very little
    - one slow drive might be a traffic
      light, a truck, or a phone in a cup
      holder
    - you need many traces, and a
      robust estimator

  one estimator contract
    for each (edge, 15-min bucket,
    weekday/weekend):
      collect speeds
      estimate a travel-time distribution
        - robust central estimate for ETA
        - upper travel-time percentile for
          a stated on-time reliability target
        - confidence from probe count/age
      with a prior from historical data
      for low-traffic edges

A high percentile of speed selects the faster observations and tends to underestimate travel time; it is not a general ETA estimator. For reliability, transportation practice commonly reports an upper percentile of travel time—for example the 95th-percentile planning time—not a high speed percentile. A traffic-light distribution may be multimodal, so retain time-of-day/signal context or estimate the travel-time distribution. Publish whether the route ETA is expected, median, or reliability-buffered; each answers a different product question.

Coverage is the other half. Most edges have no probes — side streets, rural roads, anything at 3am. The model needs a prior from historical and road-class-based defaults, blended with observations where they exist, and it needs to be explicit about which is which, because a road with three observations should not be trusted as much as one with thirty thousand.

Incremental rerouting

  the naive approach
    every 30 seconds:
      recompute the full route from
      the user's CURRENT position to
      the destination

  why it is wrong
    - the "current position" is on the
      matched road, which can be a
      wrong guess; a full recompute
      propagates that guess into a
      confident wrong route
    - the user gets a "recalculating"
      that flips the route for a
      200m improvement
    - it is far more computation than
      necessary

  the correct approach
    1. keep the matched position as
       (edge, offset, direction)
    2. recompute FORWARD from that node
       using an A* / bidirectional search
       bounded by the current remaining
       distance
    3. only replace the route if the new
       one is better by a margin
       (e.g. > 30s or > 2%)
    4. the "rerouting" announcement is
       gated on the same margin, so
       the user is not told about
       improvements they do not care about

The margin is the detail that decides whether the app feels good. Without it, a nav app recalculates every twenty seconds and the route line visibly jitters; with a 30-second or 2% margin, the route only changes when it genuinely should, and the occasional recalculation reads as “it noticed the traffic changed” rather than “it is broken”.

Forward recomputation also needs the destination to be reached robustly when the current position is wrong. The safe pattern is to keep a short “committed” prefix of the previous route — the next few hundred metres along the currently-matched road — and search from the end of that. This prevents the classic flip where a GPS error on a service road makes the app turn around and rejoin the main road behind you.

Failure stories worth testing

Drive a route with the GPS in a car park with a 200m reflection

Confirm the matcher does not snap to the wrong parallel street, and that turn restrictions are respected on the matched road.

Tunnel for 400m with a dead-reckoned position

The first fix after the tunnel must be low-confidence. If it snaps to the nearest road, it will pick the wrong exit.

Add a new road and time the rebuild

This is the constraint that decides whether you can use contraction hierarchies at all. If the rebuild is 10 minutes, all map changes must be batched.

Time 10,000 route queries per second

The query path should be sub-millisecond and the answer is whether the hierarchy is doing its job.

Remove all turn penalties and rerun the city benchmark

Routes will include illegal turns and counterflow violations. This is the most common cause of a “the map is wrong” bug report.

Compare mean/median travel time and a reliability percentile on a signalized road

The ETA becomes wrong in both directions and users describe it as “it thinks every road is a traffic jam”.

Remove the reroute margin and drive a 30-minute route

The route line jitters continuously and users report the app as unreliable. This is the single most important UX parameter in the rerouting loop.

Make an offline map and reroute in a dead zone

Fallback behaviour: dead reckoning on the last matched edge plus a coarse route. Confirm the app degrades to a usable state instead of freezing.

Confine a user to one side of a dual carriageway with a fence line

Test whether the matcher respects the fence line and whether U-turns are only allowed at legal points. Fence lines are part of the graph and are frequently forgotten.

Add a high-frequency bus lane that is only open at certain times

Time-dependent edges are needed, and the accessibility rules have to come from the routing profile, not the base graph.

Set the probe threshold too low and include stationary GPS

Stationary traces at a red light will drag the distribution. Test with and without a movement filter.

Run a query from a node that is not in the hierarchy because it was added late

This is the classic “works in tests, fails for new roads” bug. Every new node must be contracted into the hierarchy.

Make the destination unreachable and check the messaging

The app should say it cannot find a route, not silently draw a line to the nearest reachable point.

A production-ready architecture

   OS location (1Hz)
        |
        v
  +----------------------------------------------------------+
  |  MAP MATCHER                                             |
  |  HMM over road segments                                   |
  |  - reachable-set filtering (roads only)                   |
  |  - transition term eliminates impossible candidates        |
  |  - dead reckoning through tunnels                          |
  |  - confidence score per matched position                  |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  ROUTE ENGINE (contraction hierarchy)                    |
  |  - preprocessed shortcuts, bidirectional upward search    |
  |  - time-dependent weights from the traffic model          |
  |  - turn costs and restrictions from the profile          |
  |  - forward-only search for reroutes                       |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  TRAFFIC MODEL                                            |
  |  - probe traces -> matched runs -> (edge, bucket, day)   |
  |  - p85/p90 estimator, not mean                            |
  |  - prior blended with observations for low coverage       |
  |  - per-edge confidence                                    |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  ROUTE GUIDANCE                                           |
  |  - reroute only if better by a margin (30s or 2%)         |
  |  - committed prefix to survive position errors             |
  |  - offline fallback: dead reckoning + coarse route        |
  +----------------------------+-----------------------------+

  watch: match confidence, match error (vs ground truth),
        route recompute rate, reroute flip rate, ETA error
        by time of day, edge coverage

Delivery checklist:

1. Build the matcher before the router. Everything downstream inherits the matcher’s mistakes, and a route over a wrongly matched position is confidently wrong.
2. Use an HMM with a transition term that reflects real travel speed; it is what eliminates impossible candidates in urban canyons.
3. Handle tunnels by dead reckoning and treating the first post-tunnel fix as low confidence.
4. Use contraction hierarchies for the query path and batch all graph changes to fit the preprocessing budget.
5. Never encode live traffic as new edges. Time-dependent weights on the existing graph, or you will be re-preprocessing all day.
6. Include turn restrictions and turn costs in the graph, not in the UI layer.
7. Use a high percentile of observed speed per time bucket, not a mean, and blend a prior into low-coverage edges.
8. Recompute reroutes forward from the matched position with a small committed prefix, never from scratch.
9. Gate reroute announcements on a margin so the route does not visibly jitter.
10. Filter out stationary and low-speed-because-parked traces from the traffic estimator.
11. Respect fence lines and legal U-turn points in the graph.
12. Carry a confidence score on the matched position and degrade gracefully on low confidence.
13. Make the offline mode a real degraded state (dead reckoning plus a coarse route) rather than a freeze.
14. Measure match error against ground truth in a test city; without it, map matching regressions are invisible.

Common mistakes

Mistake	What actually happens	Better decision
Routing before matching is solid	Confidently wrong routes from bad positions	Matcher first, measure error
Mean speed for traffic	Wrong in both directions on signalised roads	p85/p90 of the distribution
No transition term in matching	Parallel streets and one-ways mis-matched	HMM with reachability constraints
Tunnel treated as a hard constraint	Snaps to the wrong exit	Dead reckon, low-confidence re-entry
Rebuild the hierarchy per map change	Never keeps up with traffic events	Time-dependent weights, batched rebuilds
No turn costs or restrictions	Illegal turns in the route	Turn costs in the graph
Reroute on every ETA change	Route jitters, app feels broken	Reroute margin, committed prefix
Reroute from scratch each time	GPS error propagates into a wrong route	Forward search from matched node
No stationary-trace filter	Traffic lights dominate the model	Movement filter before aggregation
Low-coverage edges trusted fully	Rural ETAs wildly wrong	Prior blended with observations
Fence lines missing	U-turns through medians	Fence lines and legal U-turns in graph
No offline degraded path	App freezes in a dead zone	Dead reckoning plus coarse route
No match-confidence carried	Low-confidence fixes trusted fully	Confidence score, degrade on it
New nodes not contracted into hierarchy	Works in tests, fails on new roads	Contraction as part of the build
No ground-truth match measurement	Regressions invisible	Test city with known routes

The complete story in one minute

Navigation is three problems stacked. Map matching uses candidate road positions, an observation-error model, and network-aware transition likelihoods; tunnels need an uncertainty-growing dead-reckoning state and cautious re-entry. Routing can use contraction hierarchies, but live metrics require shortcut customization or a dynamic-routing design, not arbitrary weight replacement in a static hierarchy. Traffic estimation must distinguish expected ETA from reliability: a high speed percentile is optimistic, while an upper travel-time percentile is a buffer. State the estimator contract or the same model will be judged against incompatible meanings of “arrival time.”

Rerouting is what makes the app feel good or broken, and it is not a full recompute. Recompute forward from the matched node with a short committed prefix, and gate the change on a margin — around 30 seconds or 2%. Without that margin the route line visibly jitters every twenty seconds and users conclude the app is unreliable; with it, the occasional recalculation reads as “it noticed the traffic”. Measure map-matching error against ground truth in a test city, because without that metric every matching regression is invisible.

matcher first (HMM + reachability + dead reckoning), then router
contraction hierarchies, time-dependent weights, no per-traffic rebuild
p85 speeds per bucket with a prior, stationary traces filtered
forward reroute with a committed prefix and a change margin

The hard part was never only the shortest path. It was carrying uncertainty from map matching into a metric that can be customized safely, then telling the user whether the ETA is expected or reliability-buffered.

Technical references

• Newson and Krumm: Hidden Markov Map Matching Through Noise and Sparseness
• Geisberger et al.: Exact Routing Using Contraction Hierarchies
• Delling et al.: Customizable Route Planning
• FHWA: travel-time reliability measures