RouteMatching

Merging Short Stops Separated by Traffic Queues

A vehicle in a queue does not stand still. It creeps forward two metres, waits ninety seconds, creeps again. To a variance-based detector that is not one stop; it is six stops separated by five short movements, and every one of them is reported.

The consequences are quietly expensive. Stop counts inflate by a factor of three or four on congested rounds, mean dwell time collapses, and any per-stop metric — deliveries per hour, average service time — is diluted by events that were never deliveries. Worse, the inflation is proportional to congestion, so the metric moves with traffic rather than with performance.

This page covers merging those fragments back together, and the threshold that distinguishes them from genuine consecutive deliveries. It extends the detector described in sliding-window variance stop detection.

Compatibility and Configuration Requirements

Requirement Value Notes
Candidate stops With centroids, in a projected CRS Displacement must be in metres
Ordering Sorted by vehicle and time The merge is a sequential scan
Displacement threshold 20–40 m urban, 60 m suburban Derived below rather than assumed
Chain cap 150–250 m total Prevents a long slow crawl merging into one stop
Output Component count on every merged event Distinguishes a merge from a simple stop

The Merge

from __future__ import annotations

import numpy as np
import polars as pl


def merge_queue_stops(
    stops: pl.DataFrame,
    max_step_m: float = 30.0,
    max_chain_m: float = 200.0,
) -> pl.DataFrame:
    """Collapse consecutive candidate stops that are close together in space.

    ``stops`` needs projected ``x``/``y`` centroids and must be sorted by
    (vehicle_id, start_utc). Two adjacent stops merge when the vehicle moved
    less than ``max_step_m`` between them, and a chain stops growing once its
    total span reaches ``max_chain_m``.
    """
    s = stops.sort(["vehicle_id", "start_utc"]).with_columns(
        np.hypot(
            pl.col("x") - pl.col("x").shift(1).over("vehicle_id"),
            pl.col("y") - pl.col("y").shift(1).over("vehicle_id"),
        ).alias("step_m")
    )

    # A new group starts whenever the step is too large, or the vehicle changes.
    s = s.with_columns(
        (
            (pl.col("step_m").fill_null(1e9) > max_step_m)
            | (pl.col("vehicle_id") != pl.col("vehicle_id").shift(1))
        )
        .cum_sum()
        .alias("group_id")
    )

    merged = s.group_by(["vehicle_id", "group_id"]).agg(
        pl.col("start_utc").min().alias("start_utc"),
        pl.col("end_utc").max().alias("end_utc"),
        pl.col("x").mean().alias("x"),
        pl.col("y").mean().alias("y"),
        pl.len().alias("n_components"),
        np.hypot(
            pl.col("x").max() - pl.col("x").min(),
            pl.col("y").max() - pl.col("y").min(),
        ).alias("chain_span_m"),
    )

    # A chain that spans too far is a crawl, not a stop — keep its parts.
    too_long = merged.filter(pl.col("chain_span_m") > max_chain_m).select("group_id")
    return pl.concat([
        merged.join(too_long, on="group_id", how="anti"),
        s.join(too_long, on="group_id", how="semi").with_columns(
            pl.lit(1).alias("n_components"), pl.lit(0.0).alias("chain_span_m")
        ).select(merged.columns),
    ]).sort(["vehicle_id", "start_utc"])

The chain cap is the part that stops the rule overreaching. Without it, a vehicle crawling four hundred metres through congestion merges into a single stop at the average of its positions — a location it occupied only briefly, with a duration covering the whole crawl.

What the displacement threshold separates Above, six candidate stops from a vehicle creeping through a queue, each three to eight metres from the last, merged into a single stop. Below, two genuine deliveries seventy metres apart on the same street, which stay separate because the step between them exceeds the threshold. Threshold 30 m — merge below, keep above queue creep steps of 3–8 m — one stop two deliveries 70 m — stays separate The time gap between the two lower stops is 40 seconds; between the upper ones it is 90. Time cannot separate them. Displacement can, because a creep advances a car length and a delivery round moves to the next building. This is why the rule is expressed in metres and never in seconds.

Deriving the Threshold

Like every threshold in this pipeline, it should come from the data. The measurement is simple: take a set of stops whose nature is known — from the job system, or from a labelled sample — and plot the distribution of the step between consecutive stops, split by whether the pair was two deliveries or one interrupted movement.

The two distributions separate cleanly on almost every fleet, because the physical processes are different. A creep is bounded by the vehicle in front; a move between delivery points is bounded by the spacing of buildings. The valley between them is the threshold, and on urban rounds it sits between twenty and forty metres.

steps = (
    labelled.with_columns(
        np.hypot(
            pl.col("x") - pl.col("x").shift(1).over("vehicle_id"),
            pl.col("y") - pl.col("y").shift(1).over("vehicle_id"),
        ).alias("step_m")
    )
    .group_by("pair_kind")          # "queue" | "consecutive_delivery"
    .agg(pl.col("step_m").quantile(0.05), pl.col("step_m").quantile(0.95))
)

Expect the threshold to differ by round type more than by city. A kerbside courier round in a dense centre has delivery points twelve metres apart and needs a tight threshold; a suburban round with driveways needs a looser one. Keying it off the round type — which the schedule already knows — is the same pattern as the DBSCAN parameter choice in tuning DBSCAN eps and min_samples.

Two processes, two distributions The step between consecutive candidate stops. Queue creeps cluster between two and twelve metres, bounded by the vehicle in front. Consecutive deliveries cluster between fifty and a hundred and forty metres, bounded by building spacing. The valley between them sits near thirty metres. Step between consecutive candidate stops, urban round queue creeps consecutive deliveries threshold 30 m 0 100 m 200 m A shallow valley means the round mixes dense kerbside and suburban work — split it before setting one value. Key the threshold off the round type, which the schedule already knows, rather than off the city.

What the Merge Costs

Merging is not free of risk, and the risk is asymmetric. A false merge destroys a genuine delivery event, which is unrecoverable downstream; a missed merge leaves an inflated stop count, which is visible and correctable. That asymmetry argues for a conservative threshold.

The n_components column is what keeps the decision reversible. A merged stop carrying six components can be unpacked by a consumer that would rather see the fragments — and more importantly, it can be audited. A sudden rise in the mean component count means congestion increased, or the detector’s sensitivity changed, and either is worth knowing.

Track two numbers after enabling the merge:

Stops per round. Should fall substantially — typically by a third on congested urban rounds — and then stay stable. A count that keeps falling week on week means the threshold is too loose and genuine deliveries are being absorbed.

Mean component count. Should sit between one and a half and three on urban work. Above four, chains are forming that the cap should be catching.

The inflation the merge removes is proportional to congestion Stops per round before and after merging, for free-flowing, moderate and heavy congestion. Free-flowing rounds barely change. Heavily congested rounds fall from 71 reported stops to 23, which is close to the 21 deliveries actually made. Reported stops per round, before and after merging free flowing 24 → 22 moderate 42 → 23 heavy 71 → 23 21 deliveries were actually made on each of these rounds. The unmerged count tracks traffic, not work done. Any productivity metric built on the faint bars rewards drivers for working in light traffic.

Common Pitfalls Specific to This Technique

Merging on the time gap. Two deliveries can be closer in time than two creeps, so a time-based rule merges real work and splits real queues.

Averaging the centroid of a long chain. The merged position is somewhere the vehicle passed through briefly. The chain cap exists to keep that from happening, and removing it produces stops at plausible-looking locations the vehicle never occupied for long.

Merging before the minimum-dwell filter. Six thirty-second fragments merge into one three-minute stop that then passes a two-minute minimum, creating a stop where the filter would have removed every component. Filter first, merge second.

Discarding the component count. Without it there is no way to distinguish a merged stop from a simple one, no way to audit the rule, and no way to unpick a merge that turns out to have been wrong.

Where the Merge Belongs in the Pipeline

Order matters here more than in most stages, because the merge interacts with two neighbours in ways that are easy to get backwards.

After the minimum-dwell filter, not before. Filtering first removes the sub-threshold fragments a queue produces, so the merge sees fewer, larger candidates and the chain cap rarely engages. Merging first creates composite stops that then pass a filter every component would have failed, manufacturing events out of nothing.

Before location typing. A merged stop has one centroid, and matching that centroid to a point of interest once is both cheaper and more accurate than matching six fragments and reconciling the results. Running POI matching on fragments produces a stop attributed to whichever building each creep happened to be outside.

Before dwell aggregation. The duration of a merged stop is the span from the first component’s start to the last component’s end, which includes the creeping time between them. That is the right answer for idle-cost reporting and the wrong one for service-time analysis, and the component count is what lets a consumer choose.

A useful sanity check after wiring it in is that the total stationary time across a vehicle-day is unchanged by the merge. Merging redistributes time between events; it must not create or destroy any. An assertion on that identity catches a surprising number of implementation errors, particularly ones involving the chain-cap fallback path.

Related

Up to section Sliding-Window Variance Stop Detection Related Detecting Engine Idle vs True Stops with Variance Windows