Designing a Single-Van Mobile Tire Service Route Planner: Time Windows, Weather Slack, and Explainable Re-Sequencing

Scope note: this is a design exercise with illustrative data for a hypothetical one-van tire business in Calgary; it does not describe any company's live dispatch system, and every number in it is made up for the worked example.

A mobile tire van has one thing a fixed bay never has to think about: the road between jobs. The bay's day is a queue. The van's day is a sequence, and the sequence has a clock attached to every element of it. If the first customer's parkade gate takes ten minutes to open, the last customer in Mahogany is now ten minutes closer to missing the window they took an afternoon off for. The real-world service that motivates this model is a van that mounts, balances and swaps tires at a customer's home, workplace or roadside, the way KMJ Tire's mobile tire service does across the city and the surrounding communities on its service-area page. What follows is how I would model that day so the software can sequence it, keep it feasible as the day drifts, and explain every change in words a dispatcher can read to a customer.

Photo from KMJ Tire's approved image collection, shown for general context; it does not show current inventory or a customer event.

One van, a dozen stops, and a clock that keeps slipping

Strip the problem down and it is small. One vehicle. Somewhere between six and twelve stops on a normal day, fewer when the work is heavy, more during the two seasonal surges. A depot it leaves in the morning and returns to at night. Each stop has a window the customer agreed to, a job type that tells you roughly how long the technician will be there, and a location that tells you roughly how long it takes to get there from wherever the van was before.

The word "roughly" is doing all the work in that paragraph, and it is the whole reason this is worth designing rather than just drawing on a whiteboard. Service durations are not numbers; they are distributions. Travel times depend on when you leave, not just where you are going, because Deerfoot Trail at 07:45 and Deerfoot Trail at 13:00 are different roads. Weather stretches both. And once the day starts, the plan you made at 06:30 begins to decay the moment the first job runs long.

Classroom route planning is about finding the cheapest sequence. Small-business route planning is about keeping promises when the inputs move. Those are related but not the same, and the difference shapes almost every decision below.

Why this is a VRPTW, and why "tiny" changes the engineering

In operations-research terms this is a Vehicle Routing Problem with Time Windows: pick an order of visits for a vehicle such that each customer is served inside their window, the vehicle's capacity is respected, and some cost is minimised. With one vehicle it collapses to a Travelling Salesman Problem with Time Windows, which is still NP-hard in the general case and still completely irrelevant to a day with nine stops.

At nine or twelve stops, the search space is small enough that the hard part is not finding a good sequence. The hard parts are:

• Getting the inputs honest enough that the "good sequence" survives a real Tuesday.
• Recomputing quickly when something changes at 10:40 with the van already on Glenmore Trail.
• Explaining the change so dispatch can pass it on without a translation layer.

Distinguishing the hard windows from the soft ones matters here more than it does in the literature. A hard window is a promise with a consequence: a customer who leaves for the airport at 15:00, a fleet yard that locks its gate at noon, a roadside job where someone is standing on the shoulder of Highway 1 in a crosswind. A soft window is a preference with a cost: "any time this afternoon is fine, morning would be better." Treating everything as hard makes the plan brittle; treating everything as soft makes it dishonest. The model needs both, with different weights.

An illustrative September Tuesday across real Calgary geography

The rest of the article uses a single made-up day. Locations are real places; the jobs, windows and durations are invented for the exercise.

J7 is the interesting one. It does not exist when the day is planned. It arrives as a request at 10:20, the kind of work that a business advertises under emergency roadside services, and it forces the planner to do the thing it is really for: re-sequence a live day without breaking the promises already made.

The depot, for the example, sits in the southeast industrial area; for a real business it is wherever the bays are, the way KMJ's Calgary location anchors its van. The shift runs 07:00 to 18:00. The van holds, say for illustration, ten stored tire sets in its racks plus tools, and starts the day with two sets loaded for J1 and J6 and empty rack space for whatever comes back from J5.

Jobs, windows, and treating lunch as a stop

The job record is the unit of everything. It needs to carry the customer's window, the job type (which keys into the duration priors), what goes on and off the van, and the site-access flags that change what "arrival" even means. Here is the shape I would use in Python before it becomes a table:

from dataclasses import dataclass, field

@dataclass(frozen=True)
class Job:
    job_id: str
    site_id: str                      # key into the travel matrix
    job_type: str                     # "swap4", "repair1", "fleet_pair", "roadside_flat", "lunch"
    hard_open: int                    # minutes after midnight, local
    hard_close: int
    soft_open: int | None = None      # preference, not a promise
    soft_close: int | None = None
    sets_out: int = 0                 # stored sets delivered to the customer
    sets_in: int = 0                  # sets collected for storage
    access: frozenset[str] = field(default_factory=frozenset)
    lateness_weight: float = 1.0      # how much this customer's soft window matters
    urgent: bool = False

Two choices in that record deserve a sentence each. The windows are minutes after local midnight rather than timestamps, because the whole plan lives in one day in one zone (America/Edmonton) and integer arithmetic on minutes is harder to get wrong than datetime arithmetic across a DST edge. And the soft window is optional and separate from the hard one, rather than being the same field with a flag, because a stop can have both: "any time 13:00–16:00 works, 13:00–14:00 would be ideal."

Lunch is modelled as a job with job_type = "lunch", site_id = None, a fixed thirty-minute duration and a window of 11:30–13:30. The planner treats it as a stop whose travel time from the previous location is zero and whose travel time to the next location is whatever the previous site's travel time would have been. This sounds like a hack and it is a good one: it means every invariant the tests check about windows and shift length also applies to the break, so a plan cannot quietly skip the technician's lunch to make a window. If the break cannot fit, the plan is infeasible and says so.

Service-duration priors: p50 and p90, keyed by job type

The single most damaging simplification in a naive planner is one duration per job type. A four-tire seasonal swap in a heated garage with the wheels already off the storage rack is not the same as a four-tire swap in a January parkade where two of the lug nuts have seized to the studs. The median might be 35 minutes. The tail is what breaks the afternoon.

So durations are stored as quantiles, not points:

# Illustrative priors in minutes. Real values come from the last N completed
# jobs of the same type, recomputed nightly.
DURATION_PRIOR = {
    "swap4":          {"p50": 35, "p90": 55},
    "repair1":        {"p50": 25, "p90": 45},
    "fleet_pair":     {"p50": 45, "p90": 75},
    "roadside_flat":  {"p50": 30, "p90": 70},
    "lunch":          {"p50": 30, "p90": 30},
}

The planner constructs the sequence using p50 and checks feasibility using p90. That asymmetry is deliberate. Building with p90 everywhere makes a day that fits six jobs when it could fit nine, and the business pays for that pessimism every single day. Building with p50 and then asking "if every job runs at its p90, does any hard window break?" gives you a plan that is realistic on the median day and survivable on a bad one. When the p90 check fails, the plan is still allowed, but the affected stops are flagged and the customer-facing ETA widens, which we will get to.

Where do the priors come from? From the business's own completed jobs, and nothing else. A roadside repair on a shoulder is a different animal from a driveway repair even though both are one tire; if the data shows that, split the job type. The kind of repair work a tire business describes on its tire repair page covers plug-and-patch inside the repairable zone, and the mobile version of that job has a longer tail than the bay version simply because the technician cannot walk to a second machine if the first one misbehaves. The same goes for a swap that includes balancing each wheel versus one where the stored set was balanced when it came off in spring: same job type on the invoice, different distribution on the clock, and if the data shows a gap of more than ten minutes at the median, that is two job types.

A useful refinement is to condition the prior on a couple of flags in addition to job type: access contains parkade (add to both quantiles), the vehicle is a heavy pickup or a light commercial unit (add more), the customer's last two jobs at this site overran (add a site-specific offset). Keep it to two or three conditioning variables. Anything more sophisticated needs more data than one van generates.

Capacity in stored sets, not kilograms

Capacity in classic VRP is a scalar. For a tire van it is rack slots, and the constraint is directional. A set delivered at J1 frees a slot; a set collected at J5 consumes one. The van leaves the depot with initial_load sets and the constraint is that the running load never exceeds rack_capacity and never drops below zero at any prefix of the route.

Run the check as part of propagation rather than as a separate pass, because the order matters: doing J5 before J1 means carrying eleven sets in a ten-slot van for one leg, which is either a refusal or a return-to-depot pseudo-stop inserted between them. The planner should be able to propose that depot return as an explicit leg with an explicit reason, not silently exceed capacity and let the technician discover the problem in a driveway in Airdrie.

For a business that also does fleet work, a second capacity dimension shows up: the number of a given size on the van. A fleet pair for a three-quarter-ton needs LT sizes with the load index that truck is placarded for, which a passenger swap does not, and the van cannot carry every size. I model that as a second, sparse capacity vector keyed by size class, checked the same way. For one van it rarely binds; it is there so the code does not need rewriting when it does.

The travel-time matrix and its time-of-day buckets

A single number per site pair is wrong in Calgary in a way that shows up on the first day. Deerfoot Trail southbound between 07:00 and 09:00 is a different duration from the same road at 10:30. Crowchild northbound at 16:30 is a different road from Crowchild at 13:00. Stoney Trail is usually the escape hatch, until it is not.

The matrix is keyed by origin, destination and departure bucket:

BUCKETS = [
    ("night",   0,    6*60),
    ("am_peak", 6*60, 9*60),
    ("midday",  9*60, 15*60),
    ("pm_peak", 15*60, 18*60 + 30),
    ("evening", 18*60 + 30, 24*60),
]

def bucket_for(depart_min: int) -> str:
    for name, lo, hi in BUCKETS:
        if lo <= depart_min < hi:
            return name
    return "night"

def travel_minutes(matrix, origin, dest, depart_min, weather_mult=1.0) -> int:
    if origin == dest:
        return 0
    base = matrix[(origin, dest)][bucket_for(depart_min)]
    return int(round(base * weather_mult))

Four buckets is a compromise. Finer buckets need more data than a single van produces, and the goal is not to model traffic; it is to stop the planner from putting a Beltline-to-Shepard leg at 08:15 and pretending it is twelve minutes. Illustrative values for the example day, in minutes, might be depot→Beltline 22 (midday) / 34 (AM peak), Beltline→Shepard 24 / 38, Shepard→Bridgeland 18 / 26, Inglewood→Airdrie 42 / 60, Airdrie→Mahogany 55 / 78 in the PM peak. Where they come from is a routing provider queried nightly for each pair at four representative departure times, cached with a date stamp, and rebuilt weekly or when a site is added. That is a few hundred requests a week for a twelve-stop day, which is nothing.

One subtlety: departure time depends on the finish time of the previous stop, which depends on the duration prior, which is uncertain. So the bucket choice is itself uncertain near a boundary. I resolve that on the pessimistic side during the feasibility check (use the slower of the two adjacent buckets if the p90 finish crosses the boundary) and on the optimistic side during construction. Same asymmetry as the durations.

Weather slack from an Environment Canada statement

Calgary weather does not change the geometry of the day; it changes its elasticity. A snowfall warning stretches every leg and every roadside job. Freezing rain does worse, and it also changes which jobs should exist at all: nobody should be swapping tires on a shoulder in freezing rain if the customer can be moved to a safer location.

I model this as a weather_state row keyed by date, sourced from the Environment Canada public alert feed for the Calgary region, with an illustrative multiplier and a duration quantile override:

Those multipliers are invented for the example. The real values come from comparing planned versus actual leg durations on days a statement was in effect, and the honest starting point is a guess that you replace after one winter. What matters structurally is that the multiplier is applied to the travel matrix at plan time, recorded on the plan version, and re-applied on re-sequencing, so the plan and every explanation derived from it agree about what the weather was assumed to be. A plan built at 06:30 under a special weather statement that upgrades to a snowfall warning at 09:00 is a plan that should be rebuilt, and the difference in slack between the two builds is a metric worth keeping.

The link between weather and tire work is not incidental. The same cold snap that stretches the travel matrix is the one that fills the day with seasonal changeovers, so the planner's worst days for slack coincide with its busiest days for demand. (Customers running all-weather tires year-round never generate a swap job at all, which is one reason the surge is smaller than the customer count suggests, and a decent demand forecast for the van starts by subtracting them.) A design that only works on a dry September Tuesday is not a design.

Site-access flags: parkade clearance and shoulders without shoulders

Some sites change what arrival means. A Beltline parkade with a 2.0 m clearance may not admit a high-roof van at all; the job is done from street level with the customer bringing the vehicle up, which adds a coordination step and ten minutes to the prior. An acreage with a 1.6 km washboard approach adds time that the routing provider will not know about because the gravel is private. A Highway 1 shoulder near the Stoney interchange has no safe pull-off in one direction, so the technician needs the customer to have been moved, or the job is refused until they are.

These are flags on the site, and they do three things in the model:

1. Some add a fixed offset to the duration prior (parkade, gravel approach, gated yard).
2. Some add a fixed offset to travel (private road distance not in the matrix).
3. Some are hard preconditions that the planner will not schedule past without a human acknowledging them (no safe shoulder, no hazard lights, vehicle in a live lane).

The third category is where a planner earns trust. It should never silently plan a roadside job in a live lane. It should refuse, say why, and let dispatch resolve it with the customer. The refusal itself is a plan event with a reason string, so it shows up in the day's history.

SQL DDL for the core tables

The tables below are the minimum that the rest of the article needs. They are written for PostgreSQL; the only non-portable thing is the jsonb column used to carry reason payloads.

create table site (
    site_id        text primary key,
    label          text not null,
    lat            double precision not null,
    lon            double precision not null,
    access_flags   text[] not null default '{}',    -- e.g. {'parkade_low_clearance','gravel_approach'}
    private_road_min integer not null default 0,     -- minutes not covered by the matrix
    created_at     timestamptz not null default now()
);

create table duration_prior (
    job_type       text primary key,
    p50_min        integer not null,
    p75_min        integer not null,
    p90_min        integer not null,
    sample_size    integer not null,
    computed_at    timestamptz not null
);

create table job (
    job_id         text primary key,
    service_date   date not null,
    site_id        text references site(site_id),   -- null for lunch
    job_type       text not null references duration_prior(job_type),
    hard_open_min  integer not null,
    hard_close_min integer not null,
    soft_open_min  integer,
    soft_close_min integer,
    sets_out       integer not null default 0,
    sets_in        integer not null default 0,
    lateness_weight numeric(4,2) not null default 1.0,
    urgent         boolean not null default false,
    status         text not null default 'planned',  -- planned | en_route | on_site | done | rescheduled | refused
    check (hard_open_min < hard_close_min)
);

create table travel_matrix (
    origin_site    text not null,
    dest_site      text not null,
    bucket         text not null,                    -- night | am_peak | midday | pm_peak | evening
    minutes        integer not null,
    fetched_at     timestamptz not null,
    primary key (origin_site, dest_site, bucket)
);

create table weather_state (
    service_date   date primary key,
    statement      text not null,                    -- none | special | snowfall | freezing_rain | extreme_cold
    travel_mult    numeric(4,2) not null,
    duration_quantile text not null,                 -- p50 | p75 | p90
    source_ref     text,                             -- alert identifier from the feed
    observed_at    timestamptz not null
);

create table plan (
    plan_id        text primary key,
    service_date   date not null,
    vehicle_id     text not null,
    current_version integer not null default 0
);

create table plan_version (
    plan_id        text not null references plan(plan_id),
    version        integer not null,
    built_at       timestamptz not null default now(),
    built_by       text not null,                    -- 'planner' | 'dispatch:<user>' | 'overrun_resequence'
    edit_id        text not null,                    -- client-supplied idempotency key
    weather_mult   numeric(4,2) not null,
    quantile       text not null,
    objective      numeric(10,2) not null,
    summary        jsonb not null,                   -- reason strings for the whole version
    primary key (plan_id, version),
    unique (plan_id, edit_id)
);

create table plan_leg (
    plan_id        text not null,
    version        integer not null,
    seq            integer not null,
    job_id         text references job(job_id),
    from_site      text,
    depart_min     integer not null,
    drive_min      integer not null,
    arrive_min     integer not null,
    wait_min       integer not null,
    start_min      integer not null,
    finish_p50_min integer not null,
    finish_p90_min integer not null,
    load_after     integer not null,
    slack_min      integer not null,                 -- forward time slack at this stop
    reason         text not null,                    -- why this stop is here in this position
    primary key (plan_id, version, seq),
    foreign key (plan_id, version) references plan_version(plan_id, version)
);

create table plan_event (
    event_id       bigserial primary key,
    plan_id        text not null,
    from_version   integer,
    to_version     integer,
    kind           text not null,                    -- built | overrun | inserted | slipped | rescheduled | refused | conflict
    job_id         text,
    reason         text not null,
    payload        jsonb,
    occurred_at    timestamptz not null default now()
);

The plan_leg row carries both p50 and p90 finish times and a slack value, which is what lets the customer-facing ETA be a range without recomputation. The plan_version.edit_id uniqueness constraint is what makes edits idempotent. And plan_event is append-only: nothing in it is ever updated, so the day's story can be replayed.

The objective is not distance

If you minimise kilometres you will build a day that visits Airdrie at 08:30 because it is on the way to nothing, and then arrives at the Beltline parkade at 10:15, fifteen minutes after the customer's hard window closed. Distance is one term. The objective I use has five, with illustrative weights:

WEIGHTS = {            # illustrative; tune against the business's own day history
    "drive_min":       1.0,
    "soft_late_min":   2.5,   # per minute past a soft close, times the job's lateness_weight
    "wait_min":        0.6,   # sitting outside a window that has not opened
    "fatigue":         0.8,   # penalises long back-to-back heavy jobs late in the shift
    "end_buffer_short": 4.0,  # per minute the buffer before the last hard window drops below 30
}

def cost(sched, jobs) -> float:
    drive = sum(leg.drive_min for leg in sched.legs)
    wait = sum(leg.wait_min for leg in sched.legs)
    late = 0.0
    for leg in sched.legs:
        job = jobs[leg.job_id]
        if job.soft_close is not None and leg.start_min > job.soft_close:
            late += (leg.start_min - job.soft_close) * job.lateness_weight
    fatigue = heavy_streak_penalty(sched, jobs)
    last_hard = max((leg for leg in sched.legs if jobs[leg.job_id].hard_close < 24*60),
                    key=lambda l: l.start_min)
    buffer = jobs[last_hard.job_id].hard_close - last_hard.finish_p90_min
    short = max(0, 30 - buffer)
    return (WEIGHTS["drive_min"] * drive
            + WEIGHTS["soft_late_min"] * late
            + WEIGHTS["wait_min"] * wait
            + WEIGHTS["fatigue"] * fatigue
            + WEIGHTS["end_buffer_short"] * short)

Hard windows do not appear in the cost at all. They are constraints: a schedule that misses one is not a worse schedule, it is not a schedule. That separation is what lets the property tests later be absolute.

The fatigue term is the one people question. It exists because a technician who does three four-tire swaps back-to-back in a January parkade and then drives to Airdrie is slower on the fourth job than the prior says, and the prior does not know why. A simple version: for each stop, count the heavy jobs (swap4, fleet_pair) in the preceding 150 minutes of the schedule, and add a penalty per heavy job beyond the second. It nudges the planner to interleave a repair between swaps when the windows allow, which is what a good dispatcher does by hand.

The end-buffer term encodes a rule that experienced dispatchers apply without thinking: arrive at the last hard window of the day with thirty minutes in hand, because there is no one after that stop to absorb a slip. The weight is high on purpose. A plan that saves eight minutes of driving by eating that buffer is the kind of plan that looks efficient on paper and produces a phone conversation at 17:20.

Cheapest insertion as the first draft

Construction is deliberately simple: seed the route with the job whose hard window closes earliest, then repeatedly insert the pending job at the position that increases cost the least while staying feasible.

def build_route(jobs, matrix, shift, weather) -> tuple[list[str], list[str]]:
    pending = sorted(jobs, key=lambda j: jobs[j].hard_close)
    route = [pending.pop(0)]
    parked = []                                   # jobs no position could hold
    while pending:
        best = None
        for jid in pending:
            for pos in range(len(route) + 1):
                candidate = route[:pos] + [jid] + route[pos:]
                sched = propagate(candidate, jobs, matrix, shift, weather, quantile="p50")
                if sched is None:
                    continue
                delta = cost(sched, jobs)
                if best is None or delta < best[0]:
                    best = (delta, jid, pos)
        if best is None:
            worst = max(pending, key=lambda j: jobs[j].hard_close - jobs[j].hard_open)
            pending.remove(worst)
            parked.append(worst)
            continue
        _, jid, pos = best
        route.insert(pos, jid)
        pending.remove(jid)
    return route, parked

The parked list is important and often missing from toy implementations. If no position holds a job, the planner does not fail the whole day; it sets the widest-window job aside and reports it as "could not fit; needs a different day or a different window." That report is a plan_event with kind refused and a reason string built from the constraint that failed most often during the insertion attempts.

The evaluation is full re-propagation for every candidate, which is O(n) per candidate and O(n³) for the whole build. At twelve stops that is under two thousand propagations, each a few microseconds. There is no reason to be clever about incremental evaluation at this size, and the clarity is worth more than the microseconds.

Feasibility with forward time-window propagation

Propagation walks the route once, computing arrival, wait, start and finish for each stop, and refusing the route if any start exceeds its hard close or the running load leaves the rack bounds.

@dataclass
class Leg:
    job_id: str
    from_site: str | None
    depart_min: int
    drive_min: int
    arrive_min: int
    wait_min: int
    start_min: int
    finish_p50_min: int
    finish_p90_min: int
    load_after: int
    slack_min: int = 0
    reason: str = ""

def propagate(route, jobs, matrix, shift, weather, quantile="p50"):
    t = shift.start_min
    here = shift.depot_site
    load = shift.initial_load
    legs = []
    for jid in route:
        job = jobs[jid]
        dest = job.site_id or here                       # lunch stays where the van is
        drive = travel_minutes(matrix, here, dest, t, weather.travel_mult)
        drive += site_private_road_min(dest)
        arrive = t + drive
        start = max(arrive, job.hard_open)
        if start > job.hard_close:
            return None                                  # hard window missed: not a schedule
        load = load - job.sets_out + job.sets_in
        if load < 0 or load > shift.rack_capacity:
            return None
        dur50 = DURATION_PRIOR[job.job_type]["p50"] + access_offset(job)
        dur90 = DURATION_PRIOR[job.job_type]["p90"] + access_offset(job)
        used = dur50 if quantile == "p50" else dur90
        legs.append(Leg(jid, here, t, drive, arrive, start - arrive, start,
                        start + dur50, start + dur90, load))
        t = start + used
        here = dest
    home = travel_minutes(matrix, here, shift.depot_site, t, weather.travel_mult)
    if t + home > shift.end_min:
        return None
    annotate_forward_slack(legs, jobs)
    return Schedule(legs=legs, end_min=t + home)

Forward slack is the quantity that makes overrun handling explainable. For stop i, it answers "how many minutes could this stop start late before some later stop misses its hard window?" The classic formulation walks backward from the end: the slack at the last stop is its hard close minus its start; the slack at any earlier stop is the smaller of its own slack and the next stop's slack plus whatever waiting time sits between them (because a wait absorbs delay).

def annotate_forward_slack(legs, jobs):
    downstream = None
    for leg in reversed(legs):
        own = jobs[leg.job_id].hard_close - leg.start_min
        if downstream is None:
            leg.slack_min = own
        else:
            leg.slack_min = min(own, downstream + next_wait)
        downstream = leg.slack_min
        next_wait = leg.wait_min

Once every leg carries its slack, a great deal becomes trivial. "Can J1 run twenty minutes long without harm?" is legs[0].slack_min >= 20. "Which stop is the bottleneck?" is the leg with the minimum slack. "How much weather slack is left?" is the minimum slack across the day. Storing it on plan_leg means dispatch can see it on a screen without the planner running.

Local improvement: 2-opt and or-opt under windows

Cheapest insertion produces a reasonable route and sometimes a stupid one, because early insertions cannot see later jobs. Two classic moves clean it up. A 2-opt move reverses a segment of the route; an or-opt move lifts a segment of one to three consecutive stops and re-inserts it somewhere else. Under time windows, 2-opt is often useless (reversing a segment usually reverses its window order too), but it is cheap to try. Or-opt is the workhorse.

def improve(route, evaluate) -> list[str]:
    best_cost = evaluate(route)
    changed = True
    while changed:
        changed = False
        n = len(route)
        for i in range(n - 1):                           # 2-opt: reverse route[i..k]
            for k in range(i + 1, n):
                cand = route[:i] + route[i:k + 1][::-1] + route[k + 1:]
                c = evaluate(cand)
                if c < best_cost - 1e-9:
                    route, best_cost, changed = cand, c, True
        for seg_len in (1, 2, 3):                        # or-opt: relocate a short segment
            for i in range(n - seg_len + 1):
                seg = route[i:i + seg_len]
                rest = route[:i] + route[i + seg_len:]
                for pos in range(len(rest) + 1):
                    if pos == i:
                        continue
                    cand = rest[:pos] + seg + rest[pos:]
                    c = evaluate(cand)
                    if c < best_cost - 1e-9:
                        route, best_cost, changed = cand, c, True
    return route

evaluate wraps propagate and cost, returning infinity for an infeasible candidate, so the search never leaves the feasible region. The loop is first-improvement rather than best-improvement, which converges faster at this size and, more usefully, produces a sequence of small moves that can each be explained. That last property is the reason the improvement phase logs every accepted move with the two costs and the stops involved, rather than only the final route. When dispatch asks "why is Inglewood before Bridgeland?", the answer exists in the log: "moving J4 ahead of J3 saved 9 minutes of waiting at Bridgeland's soft open."

An honest note on the neighbourhood: at twelve stops, or-opt with segments up to three and 2-opt together explore a few thousand candidates per pass and a handful of passes. It runs in well under a second in plain Python. It also gets stuck in local optima, and it will. We will return to that.

A planned route as JSON with a reason on every leg

Here is the 06:30 plan for the example day, as the API would return it. Times are HH:MM, and every number is illustrative.

{
  "plan_id": "2026-09-16-van1",
  "version": 3,
  "built_by": "planner",
  "weather": {"statement": "none", "travel_mult": 1.0, "quantile": "p50"},
  "objective": 412.5,
  "min_slack_min": 22,
  "bottleneck_job": "J2",
  "legs": [
    {"seq": 1, "job_id": "J1", "from": "depot", "depart": "07:05", "drive_min": 34,
     "arrive": "07:39", "wait_min": 21, "start": "08:00",
     "finish_p50": "08:45", "finish_p90": "09:05", "load_after": 1, "slack_min": 22,
     "reason": "Earliest hard close of the day (10:00) and parkade adds 10 min; leaving first absorbs AM peak on Deerfoot."},
    {"seq": 2, "job_id": "J2", "from": "beltline", "depart": "08:45", "drive_min": 30,
     "arrive": "09:15", "wait_min": 15, "start": "09:30",
     "finish_p50": "10:15", "finish_p90": "10:45", "load_after": 1, "slack_min": 22,
     "reason": "Yard gate locks at 12:00; fleet pair p90 is 75 min so it cannot follow Bridgeland safely."},
    {"seq": 3, "job_id": "J3", "from": "shepard", "depart": "10:15", "drive_min": 18,
     "arrive": "10:33", "wait_min": 0, "start": "10:33",
     "finish_p50": "10:58", "finish_p90": "11:18", "load_after": 1, "slack_min": 84,
     "reason": "Soft window opens 10:30; on the way north from Shepard toward Inglewood."},
    {"seq": 4, "job_id": "J4", "from": "bridgeland", "depart": "10:58", "drive_min": 9,
     "arrive": "11:07", "wait_min": 0, "start": "11:07",
     "finish_p50": "11:32", "finish_p90": "11:52", "load_after": 1, "slack_min": 130,
     "reason": "Flexible window; placed between two soft stops to break up heavy jobs (fatigue term)."},
    {"seq": 5, "job_id": "LUNCH", "from": "inglewood", "depart": "11:32", "drive_min": 0,
     "arrive": "11:32", "wait_min": 0, "start": "11:32",
     "finish_p50": "12:02", "finish_p90": "12:02", "load_after": 1, "slack_min": 130,
     "reason": "Break window 11:30–13:30; taken before the long Airdrie leg so the afternoon starts rested."},
    {"seq": 6, "job_id": "J5", "from": "inglewood", "depart": "12:02", "drive_min": 47,
     "arrive": "12:49", "wait_min": 11, "start": "13:00",
     "finish_p50": "13:45", "finish_p90": "14:05", "load_after": 2, "slack_min": 135,
     "reason": "Only northern stop; midday bucket on Highway 2 is 42 min plus 5 min private gravel approach. Collects one set (load 1 -> 2)."},
    {"seq": 7, "job_id": "J6", "from": "airdrie", "depart": "13:45", "drive_min": 58,
     "arrive": "14:43", "wait_min": 17, "start": "15:00",
     "finish_p50": "15:35", "finish_p90": "15:55", "load_after": 1, "slack_min": 95,
     "reason": "Last hard window (17:30); p90 finish leaves a 95-min buffer, above the 30-min floor."},
    {"seq": 8, "job_id": "DEPOT", "from": "mahogany", "depart": "15:35", "drive_min": 24,
     "arrive": "15:59", "reason": "Return; shift ends 18:00."}
  ]
}

Notice that the plan finishes at 15:59 on p50 with almost two hours of shift left. That is not waste; that is the room the afternoon has for J7 when it arrives, and for every job that runs long. A planner that fills the shift to 17:55 with p50 estimates is a planner that will be re-sequencing every day by 11:00.

When a job overruns: re-sequencing that can explain itself

At 10:20, two things happen at once in the example. J2 at the Shepard yard is running long (one of the fleet pickup's wheels has a stud that needs the technician's attention, and the revised finish is 11:05 rather than 10:15). And a roadside flat request arrives for a customer on the Highway 1 westbound shoulder near the Stoney Trail interchange. The van is at Shepard.

The re-sequencing routine takes the current version, the stops already completed or in progress, the technician's revised finish estimate, any new urgent job, and rebuilds only the remainder of the day.

def resequence(plan, jobs, matrix, shift, weather, now_min, in_progress, revised_finish, new_jobs=()):
    done = [leg.job_id for leg in plan.legs if jobs[leg.job_id].status == "done"]
    fixed = done + [in_progress]
    remaining = [leg.job_id for leg in plan.legs
                 if leg.job_id not in fixed and leg.job_id != "DEPOT"]
    remaining += list(new_jobs)

    # Anchor: the van is at the in-progress site until revised_finish.
    anchored_shift = shift.anchored_at(jobs[in_progress].site_id, revised_finish)

    baseline = propagate(remaining, jobs, matrix, anchored_shift, weather)
    events = []
    if baseline is None:
        route, parked = build_route({j: jobs[j] for j in remaining}, matrix, anchored_shift, weather)
        for j in parked:
            events.append(("rescheduled", j, f"{label(j)} cannot fit after the overrun at {label(in_progress)}; "
                                            f"needs a new day or a wider window."))
    else:
        route, parked = remaining, []
    route = improve(route, lambda r: evaluate(r, jobs, matrix, anchored_shift, weather))
    new_sched = propagate(route, jobs, matrix, anchored_shift, weather)

    for old_leg in plan.legs:
        new_leg = new_sched.find(old_leg.job_id)
        if new_leg is None or old_leg.job_id in fixed:
            continue
        slip = new_leg.start_min - old_leg.start_min
        if slip > 0:
            events.append(("slipped", old_leg.job_id, slip_reason(old_leg, new_leg, in_progress, slip)))
    for j in new_jobs:
        events.append(("inserted", j, insert_reason(j, new_sched, jobs)))
    return fixed + route, new_sched, events

Three design points in that function. First, it tries the existing order before rebuilding. Most overruns are absorbed by existing slack, and the best explanation for a customer is "nothing changed for you." Second, when it does rebuild, it re-uses the same construction and improvement code as the morning plan, so there is one planner, not a morning planner and an afternoon planner with different opinions. Third, every difference between old and new becomes an event with a reason, before the version is written. The version is not valid without its events.

For the example: with J2 finishing at 11:05 and J7 inserted, the rebuilt remainder runs J7 (arrive 11:35 via Stoney Trail, 45 minutes on the shoulder at p50 with the roadside buffer), then lunch at 12:20 near the interchange, then J5 Airdrie (start 13:40, inside its soft window), then J6 Mahogany (arrive 15:50, start immediately, p90 finish 16:45, buffer 45 minutes), then depot. J3 Bridgeland and J4 Inglewood no longer fit before the Airdrie leg without pushing Mahogany's p90 finish past the 30-minute floor, so the planner proposes moving them after Mahogany (J4 at 17:05, J3 at 17:40, both still inside their windows because J3's soft close is a preference and J4 has none) — or, if dispatch prefers, offering J3 a next-day visit. Either way the customer-facing story is generated, not improvised.

Reason strings dispatch can read out loud

A reason string has one audience: a dispatcher with a customer on the line who wants to know why their 10:30 became 17:40. That audience needs three things: what changed, what caused it, and what the new promise is. The template is boring on purpose.

def slip_reason(old_leg, new_leg, cause_job, slip):
    return (f"{label(new_leg.job_id)} moves from {hhmm(old_leg.start_min)} to about {hhmm(new_leg.start_min)} "
            f"({slip} min later) because {label(cause_job)} ran long. "
            f"Still inside the agreed window; new arrival range {eta_range(new_leg)}.")

def insert_reason(job_id, sched, jobs):
    leg = sched.find(job_id)
    prev = sched.previous(job_id)
    return (f"{label(job_id)} added as an urgent roadside stop after {label(prev.job_id)} "
            f"because it is {leg.drive_min} min away and every later stop keeps its hard window. "
            f"Arrival range {eta_range(leg)}.")

Rules I hold reason strings to:

• Name the cause. "Because the earlier job ran long" beats "due to scheduling changes" every time.
• State the new promise as a range, never a point.
• Never expose another customer's details. "The earlier job" not "the fleet truck at Shepard."
• Fit in two sentences. If it needs three, the move was too complicated to make without a human.
• Be generated from the same data that produced the plan. A reason string that a human types after the fact is a note, not an explanation.

That last rule is why reasons live on plan_leg and plan_event rows written in the same transaction as the version. The plan and its explanation cannot drift apart because they are the same write.

Why the customer-facing ETA is a range, and how to compute it

A single ETA is a lie with a decimal point. The honest number is an interval whose lower end is the p50 arrival and whose upper end is the arrival if every preceding stop runs at its p90 and every preceding leg takes the slower adjacent bucket. For the example day at 06:30, J6's range is 14:43–15:35, which becomes "we'll be there between about 2:45 and 3:30, and we'll message when we leave the stop before yours."

The computation is two propagations, not one:

def eta_range(leg, route, jobs, matrix, shift, weather):
    fast = propagate(route, jobs, matrix, shift, weather, quantile="p50")
    slow = propagate(route, jobs, matrix, shift, weather.pessimistic(), quantile="p90")
    lo = fast.find(leg.job_id).arrive_min
    hi = slow.find(leg.job_id).arrive_min if slow else jobs[leg.job_id].hard_close
    lo = max(lo, jobs[leg.job_id].hard_open)
    hi = min(max(hi, lo + 15), jobs[leg.job_id].hard_close)
    return hhmm(lo), hhmm(hi)

The interval is clamped to the window: the customer was promised the window, and the range should never suggest we might arrive outside it. If the pessimistic propagation is infeasible, the upper end becomes the hard close and the leg is flagged at_risk, which is dispatch's cue to widen the window with the customer before the day forces the issue. Range width is a diagnostic in its own right: a leg with a 90-minute range in the morning is a leg whose upstream priors are too fat or whose upstream stops are too many.

Plan versions, idempotent edits, and what happens when two edits race

Dispatch edits plans. The technician's app edits plans (marking done, revising a finish). The overrun routine edits plans. Two of those can happen in the same second: the dispatcher drags J3 to the end of the day at 10:20:14 while the technician's app reports the J2 overrun at 10:20:15 and triggers a resequence.

The scheme is optimistic concurrency with client-supplied edit identifiers:

1. Every edit carries base_version (the version it was made against) and edit_id (a UUID generated by the client and reused on retry).
2. The write is insert into plan_version ... where plan.current_version = base_version, in a transaction that also bumps plan.current_version. If the predicate fails, the write is rejected with 409 and the current version is returned.
3. If edit_id already exists for the plan, the write returns the existing version unchanged, with 200. A retried request after a dropped connection cannot create two versions.
4. On 409, the client rebases: it re-applies its intent (not its literal sequence) to the new version and retries with a new base_version and the same edit_id.

"Re-applies its intent" is the important phrase. The dispatcher's intent was "J3 goes after J6", not "J3 is at index 7." Re-applying the index to a re-sequenced plan would put J3 somewhere absurd; re-applying the intent is a move followed by a propagate, which either succeeds or produces a reason for why it no longer can. Intent is stored on the version's summary for the same reason: when someone reads the history a week later, "dispatch moved J3 after J6 at customer's request" is the record, not a diff of two arrays.

The overrun routine gets no special priority. If it loses the race, it rebases exactly the way a human edit does. That is the whole benefit of having one edit path.

Property-based tests: invariants that must never bend

Example-based tests catch the day you thought of. Property tests catch the day you did not. Using Hypothesis, the generator produces a random shift (start, end, depot, rack capacity, initial load), a random weather state, a random travel matrix with bucket values in plausible ranges, and between two and twelve random jobs with random windows, types and access flags. Then the planner runs and the properties are asserted.

from hypothesis import given, settings, strategies as st

def planned(day):
    """Build, improve and propagate one generated day; returns (route, parked, sched)."""
    args = (day.jobs, day.matrix, day.shift, day.weather)
    score = lambda r: evaluate(r, *args)
    first, parked = build_route(*args)
    better = improve(first, score)
    return better, parked, propagate(better, *args, quantile="p50"), first, score

@settings(max_examples=500, deadline=None)
@given(day=day_strategy())
def test_no_hard_window_violated(day):
    _, _, sched, _, _ = planned(day)
    assert sched is not None
    for leg in sched.legs:
        job = day.jobs[leg.job_id]
        assert job.hard_open <= leg.start_min <= job.hard_close

@given(day=day_strategy())
def test_total_time_within_shift(day):
    assert planned(day)[2].end_min <= day.shift.end_min

@given(day=day_strategy())
def test_load_never_leaves_rack_bounds(day):
    for leg in planned(day)[2].legs:
        assert 0 <= leg.load_after <= day.shift.rack_capacity

@given(day=day_strategy())
def test_lunch_is_scheduled_or_day_is_refused(day):
    route, parked, _, _, _ = planned(day)
    assert "LUNCH" in route or "LUNCH" in parked

@given(day=day_strategy(), overrun=st.integers(min_value=1, max_value=120))
def test_resequence_never_touches_completed_stops(day, overrun):
    ...   # completed prefix is byte-identical before and after resequence

@given(day=day_strategy())
def test_improvement_never_worsens_cost(day):
    better, _, _, first, score = planned(day)
    assert score(better) <= score(first)

@given(day=day_strategy())
def test_every_leg_has_a_nonempty_reason(day):
    assert all(leg.reason.strip() for leg in planned(day)[2].legs)

A few properties are subtler than they look. "Improvement never worsens cost" sounds trivial until a floating-point tie makes the loop accept a move of −0.0000001 forever; the 1e-9 guard in improve exists because that test found the loop. "Lunch is scheduled or the day is refused" is the property that stops a future edit to the cost function from quietly making it cheaper to skip the break. And "completed stops are untouched by resequence" is what protects the technician from a plan that rewrites history under them.

There is one property I deliberately do not assert: that the planner finds the optimal route. It does not, and a test that pretended otherwise would either be wrong or would fix the heuristic's quirks in place.

Metrics worth tracking: p90 lateness, plan churn, and slack the weather ate

Four metrics, computed nightly from plan_leg and the actual arrival timestamps the technician's app records:

Plan churn is the one I watch first. A day with nine versions is not a day the planner handled; it is a day dispatch handled with the planner in the way. Position changes are the finer signal: a version that only revises finish times is housekeeping, a version that moves four stops is a re-plan, and the second kind should be rare.

Weather slack consumed is the metric that tunes the multiplier table. If snowfall-warning days consume an average of 55 minutes of slack against a planned 40, the multiplier is low. It is also the metric that tells the business when to stop taking roadside jobs for the afternoon on a given day, which is a decision no planner should make on its own but every planner should support with a number.

One more, less obvious: overrun ratio by job type, defined as the share of jobs whose actual duration exceeded the p90 prior. If it is above ten percent, the prior is not a p90. This is the feedback loop that keeps the priors honest, and it should be automated, because nobody recomputes quantiles by hand in November.

The honest limits of heuristics at one van

Cheapest insertion plus or-opt is a 1970s technique and it gets stuck. Concretely, on the example day it will sometimes settle on a route that does Inglewood before Bridgeland when the reverse is cheaper, because the move that fixes it passes through an infeasible intermediate. Random restarts help (rebuild from three or four different seed jobs and keep the best) and cost nothing at this scale.

There is a more honest observation, though. At twelve stops or fewer, an exact method is cheap. A bitmask dynamic program over subsets of visited stops, with the state being (visited set, last stop) and the value being the earliest feasible finish time, has 2¹² × 12 ≈ 49,000 states. With time-dependent travel and a non-additive cost it needs label dominance rather than a single value per state, but it remains well under a second. So why keep the heuristic at all?

Because the exact method produces a route and the heuristic produces a story. An insertion followed by four accepted or-opt moves is a sequence of small, nameable decisions, each of which becomes a reason string. A DP produces a permutation with no narrative; "this is optimal" is not something a dispatcher can read to a customer whose stop moved from morning to evening. My compromise: run the exact method as a check in the nightly metrics (how far from optimal was today's plan?) and keep the explainable heuristic in the loop that customers feel. If the gap is consistently large, that is a signal to widen the neighbourhood, not to swap the solver.

Two other limits worth stating plainly. The priors are only as good as the last few weeks of data, and a one-van business generates a few hundred jobs a season, so job types have to stay coarse. And the travel matrix is a nightly snapshot; a collision on Deerfoot at 08:10 is invisible to it, which is why the technician's app should let the technician report a "running late, road" event that widens the current leg without pretending to know why.

When OR-Tools earns its complexity: the third van

The moment a second van appears, the problem gains an assignment dimension (which van gets which job) on top of sequencing, and the moment a third one appears, the assignment dimension dominates. Three vans and thirty stops is 3³⁰ assignments before any sequencing. Cheapest insertion across vans still works, but the local moves need to include cross-route exchanges, and the explainability story gets harder because "your stop moved to the other van" is a different kind of change from "your stop moved later."

That is where a real constraint solver like OR-Tools' routing library pays for itself: it handles multiple vehicles, time windows, capacity dimensions and time-dependent travel as first-class concepts, with metaheuristics (guided local search, tabu) that do not get stuck the way or-opt does. What it does not give you is the reason string, so the design around it stays the same: the solver produces a candidate, the diff against the current version is computed, every difference is explained by a template that names its cause, and any difference the templates cannot explain is a difference a human reviews before it is published.

For one van, wiring in OR-Tools is a week of integration for a result the DP already gives you and the heuristic already explains. For three, it is the difference between a planner and a spreadsheet. Businesses that do commercial and fleet tire work across a city tend to hit that threshold earlier than they expect, because fleet yards cluster in the southeast and the northeast and the customer homes do not.

Questions that come up in review

Why not just use the routing provider's optimiser? Most routing APIs offer route optimisation, and for pure distance it is fine. None of them know your duration priors, your rack capacity, your lunch rule or your 30-minute end buffer, and none of them will explain a change in your words. Use them for the matrix. Keep the sequencing.

What about a customer who is not home? That is a no-show, modelled as an overrun with a duration of the wait limit (say, 10 minutes) and a status of rescheduled. The resequence routine handles it the same way as any other overrun; the reason string says "customer not available" instead of "ran long."

Does the planner decide which jobs the business should accept? No. Whether a given address is inside the area the van covers is a separate eligibility question, and it is answered before the job exists. The planner only sequences jobs that already exist.

How does a technician's phone survive a parkade with no signal? Same answer as any field app: the plan is cached on the device, status updates queue and sync when signal returns, and the server-side version scheme treats late-arriving updates as edits with a base_version that may be stale. The rebase path handles it.

What if the job needs tires the van is not carrying? Then it is not a van job that day. The planner marks it refused with a reason ("size not on vehicle"), and the customer is offered a bay visit or a later van date once the tires are sourced, the same path a customer takes when choosing new tires from scratch. The planner never pretends inventory it cannot see.

How do you keep the technician's judgement in the loop? The app shows the technician the next three stops with their slack, and lets them flag "this one will run long" before it does. It also leaves room for the five minutes of pressure and tread checks that a good technician does at every stop, by including them in the prior rather than treating them as overrun. A technician who sees a seized wheel at 10:05 and flags it saves the planner from finding out at 10:40. Nothing in the design replaces the person who has the tire iron in their hand; it just makes sure what they know reaches dispatch as a number and not a phone conversation.

What I would ship first

Not all of this on day one. In order:

1. The job table, the site table with access flags, and the duration priors as a hand-typed table. One week of nightly recomputation of priors from real completions before trusting them.
2. The travel matrix with four buckets, fetched nightly. Compare planned versus actual leg durations for two weeks and adjust the buckets if the AM peak boundary is wrong for the corridors the van uses most.
3. Propagation with forward slack, and nothing else. Even without construction or improvement, showing dispatch the slack per stop on the plan they made by hand changes how they plan.
4. Cheapest insertion with the five-term objective. Let dispatch override it freely for a month and log every override with a reason; the overrides are the training data for the weights.
5. Or-opt improvement and the accepted-move log.
6. The resequence routine, the reason templates, and the ETA range. Publish ranges to customers only once the range width is under 60 minutes for most legs.
7. The weather multiplier table, tuned after the first cold snap, which in Calgary tends to arrive in October whether or not the planner is ready.
8. Property tests from step three onward, before anything else is built on the propagation function.

The customer-facing changes come last on purpose. A plan that is right and silent is better than a plan that is wrong and chatty, and the winter surge — the weeks where everyone with winter tires in storage wants them on in the same fortnight — is not the time to discover that the ETA ranges were built on priors from September. For a business whose bays and van both take work through an online arrangement form, the planner's real job is to make sure the promise made on that form is one the van can keep on the day, with the road, the weather and the seized lug nut all accounted for.

The design exercise ends where it started: one van, a dozen stops, a clock that slips. The software does not make the clock stop slipping. It makes the slip visible, bounded, and explainable, which for a small service business is most of what "on time" ever meant.