Detecting route deviation against a planned path

Route deviation is a distance from a line, and every difficulty in it comes from that line being uncertain too. A usable detector measures perpendicular distance to the planned path and progress along it, requires the excursion to persist, and separates “this vehicle left the route” from “this route is no longer correct” — which is the same measurement seen across many vehicles rather than one.

Why this happens

A planned route is a polyline, and a vehicle following it perfectly still produces fixes several metres either side: lane position, GPS error, and the fact that the plan was digitised down the road centreline. Adding those together gives a spread of 10–25 m in normal operation before any deviation occurs, and a naive threshold below that fires constantly.

The second difficulty is that distance alone cannot distinguish two very different situations. A vehicle parked 40 m off the route in a service yard and a vehicle 40 m off it because it has driven three streets away are the same number. What separates them is along-route progress: the parked vehicle’s projection onto the route is stationary, and the diverted one’s is not advancing at all. Measuring both turns a noisy scalar into a usable state. The upstream cleaning that makes either measurement meaningful is covered in movement anomaly detection and handling GPS drift.

Two measurements, two different events, two different responses. Reporting both as "deviation" is why dispatchers stop reading the alerts.

Core pipeline

Project each fix onto the planned route, recording perpendicular distance and the along-route position of the projection.
Differentiate the along-route position to get progress rate, which distinguishes a stop from a diversion.
Gate on persistence — require the deviation to exceed the threshold for a minimum duration or distance before opening an event.
Aggregate across vehicles before alerting, so a systematic deviation is reported against the plan rather than the driver.

Production-ready Python implementation

PYTHON

import numpy as np
import pandas as pd
from shapely.geometry import LineString, Point


def score_route_deviation(
    df: pd.DataFrame,
    route: LineString,
    x_col: str = "x",
    y_col: str = "y",
    time_col: str = "t",
    corridor_m: float = 35.0,
    persist_s: float = 30.0,
    clear_frac: float = 0.6,
) -> pd.DataFrame:
    """
    Score perpendicular deviation and along-route progress for each fix.

    Parameters
    ----------
    route : LineString
        The planned path in the SAME PROJECTED METRIC CRS as x/y. A route in
        degrees produces distances in degrees, which are not comparable to a
        corridor expressed in metres.
    corridor_m : float
        Enter threshold. Set it above positional error plus the legitimate
        spread of the route, not to a round number.
    clear_frac : float
        Hysteresis: an open event clears below corridor_m * clear_frac.

    Returns
    -------
    pd.DataFrame
        Input plus 'dev_m', 'along_m', 'progress_ms', 'state'.

    Raises
    ------
    ValueError
        On missing columns, an empty frame, or a degenerate route.
    """
    required = {x_col, y_col, time_col}
    missing = required - set(df.columns)
    if missing:
        raise ValueError(f"Missing required columns: {missing}")
    if df.empty:
        raise ValueError("Input DataFrame is empty.")
    if route.length <= 0:
        raise ValueError("Route has zero length.")

    out = df.sort_values(time_col).reset_index(drop=True).copy()

    # project() gives distance ALONG the route; distance() gives the
    # perpendicular offset. Both are metres only because the CRS is metric.
    pts = [Point(xy) for xy in zip(out[x_col], out[y_col])]
    out["dev_m"] = [route.distance(p) for p in pts]
    out["along_m"] = [route.project(p) for p in pts]

    dt = out[time_col].diff().dt.total_seconds().to_numpy()
    d_along = out["along_m"].diff().to_numpy()
    with np.errstate(divide="ignore", invalid="ignore"):
        out["progress_ms"] = np.where(dt > 0, d_along / dt, np.nan)

    # ── persistence + hysteresis state machine ────────────────────────
    enter, clear = corridor_m, corridor_m * clear_frac
    state = np.full(len(out), "on_route", dtype=object)
    open_since = None
    for i in range(len(out)):
        d = out["dev_m"].iat[i]
        t = out[time_col].iat[i]
        if open_since is None:
            if d > enter:
                open_since = t          # candidate — not an event yet
            continue
        if d < clear:
            open_since = None
            continue
        if (t - open_since).total_seconds() >= persist_s:
            # Progress tells us WHICH event this is.
            adv = out["progress_ms"].iat[i]
            state[i] = "diverted" if (np.isfinite(adv) and abs(adv) > 0.5) else "off_route_stop"

    out["state"] = state
    return out

This is the second measurement the detector needs, and it is free: project() already returns it alongside the distance.

Validation block

PYTHON

def validate_deviation_run(out: pd.DataFrame, expected_on_route_frac: float = 0.95) -> None:
    """Three assertions that catch the usual configuration errors."""
    # 1. A route in the wrong CRS makes every fix wildly deviant.
    on_route = (out["state"] == "on_route").mean()
    assert on_route >= expected_on_route_frac, (
        f"only {on_route:.0%} of fixes on route — check the CRS of the route "
        "geometry before believing this is a real diversion"
    )
    # 2. along_m must be non-decreasing for a vehicle following the route.
    #    A large negative jump means the route self-intersects and project()
    #    is snapping to the wrong leg.
    back = (out["along_m"].diff() < -50).mean()
    assert back < 0.02, f"{back:.1%} of fixes project backwards — self-intersecting route"

    # 3. Events should be rare and long, not frequent and short.
    runs = (out["state"] != out["state"].shift()).cumsum()[out["state"] != "on_route"]
    if len(runs):
        median_len = runs.value_counts().median()
        assert median_len >= 3, "events are single-fix — persistence gate is not working"
    print(f"OK — {on_route:.1%} on route, {runs.nunique() if len(runs) else 0} events")

Spatial clustering across vehicles is the cheapest available check on your own reference data, and it costs one GROUP BY over the events you are already producing.

Common mistakes and gotchas

Comparing against raw fixes rather than a matched path. Map-matching the trace first, as in feeding cleaned GPS into an HMM map-matcher, removes most of the lateral noise and lets the corridor be tighter.
A route in a different CRS from the fixes. shapely will compute a distance regardless, and the number will be in degrees. The assertion in the validation block exists because this failure looks exactly like a fleet that never follows its routes.
Self-intersecting routes. project() returns the nearest point along the line, which on a route that doubles back can be the wrong leg entirely. Split such routes into monotone sections and score against each.
No hysteresis. A vehicle tracking the corridor edge opens and closes an event on every fix. Separate enter and clear thresholds fix it; a single threshold never will.
Alerting per vehicle without aggregating. If twenty vehicles deviate at the same corner, that is one finding about the plan, not twenty about drivers.
Ignoring along-route progress. Without it, an unplanned stop and a genuine diversion are indistinguishable, and the two need entirely different operational responses.

FAQ

What corridor width should I start with?

Take a week of trips known to have followed their route, compute the distribution of perpendicular deviation, and set the enter threshold at its 99.9th percentile. That will typically land between 25 and 40 m on urban streets and 60 to 80 m on motorway corridors, and it will be specific to your network data and your cleaning pipeline rather than to anybody else’s.

How do I handle legitimate diversions?

Treat them as reference data rather than exceptions. A roadworks feed, a permitted-diversion table, or simply the set of corners where many vehicles deviate can all suppress events at known locations. The important part is that the suppression is data the detector reads, not a condition somebody adds to the code, because the road will reopen and nobody will remember to remove it.

Can this run in a stream?

Yes, with one caveat: the persistence gate needs to buffer the candidate window before emitting, exactly as described in streaming window processing. Emitting on the first fix past the threshold and retracting later is worse than emitting thirty seconds late.

Movement Anomaly Detection — the parent reference, including the layer model this detector sits in.
Flagging Impossible Jumps and Teleports in GPS Feeds — the physics gate that must run first.
Map-Matching to Road Networks — matching first is what allows a tight corridor.
Optimizing Spatial Joins for Trajectory-to-Zone Matching — making the projection step fast across a fleet.
Streaming Window Processing — running the persistence gate on a live feed.

Back to Movement Anomaly Detection