Time windows are the constraint that turns a tractable routing problem into a hard one, and they are also the constraint dispatchers care most about. Getting them wrong produces one of two outcomes: a model that reports infeasibility on a problem drivers solve daily, or a plan that satisfies every window on paper and misses them in the field. This page covers the OR-Tools time dimension in the detail that avoids both, as part of vehicle routing problem solvers and fleet dispatch inside Routing API Automation & Fleet Integration.

Everything here assumes the matrix has already been converted correctly per feeding a travel-time matrix into OR-Tools, because rounding drift shows up here first.

When to use this approach

A hard time dimension is right when windows are genuinely binding: pharmacy deliveries, chilled goods, sites with staffed receiving hours. Soften them when the business would rather have a late delivery than none — most parcel work, and any operation where the window is a customer preference rather than a physical constraint.

The distinction matters because a hard window that cannot be met makes the entire problem infeasible, taking every other stop down with it. One unreachable pharmacy should not cancel the round.

Arrival against window at three stops At the first stop the vehicle arrives before the window opens and waits, which slack permits. At the second it arrives inside the window. At the third it arrives after the window closes, which a hard window forbids outright and a soft window allows at a penalty. Three arrivals against their windows stop A 09:00 – 12:00 window arrive 08:10 waits 50 min — legal only if slack allows it stop B 13:00 – 15:00 window arrives inside — no wait, no penalty stop C 15:00 – 16:00 window arrive 16:35 Hard window: stop C makes the whole problem infeasible, cancelling stops A and B along with it. Soft window: stop C is served 35 minutes late at a penalty the objective can weigh against dropping it entirely. Which is correct depends on the goods, not on the modelling — ask before choosing.

Implementation

The transit callback for a time dimension is not the same callback as the arc-cost evaluator, because it carries service time.

# requires: ortools, numpy (pip install ortools numpy)
from ortools.constraint_solver import pywrapcp


def add_time_dimension(routing, manager, matrix, service_s: list[int],
                       horizon_s: int = 12 * 3600):
    """Elapsed time = travel + service at the stop being left."""
    def travel_plus_service(from_index: int, to_index: int) -> int:
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        # Service belongs to the DEPARTING arc, not the arriving one
        return int(matrix[i][j]) + int(service_s[i])

    idx = routing.RegisterTransitCallback(travel_plus_service)
    routing.AddDimension(
        idx,
        horizon_s,   # slack — how long a vehicle may wait at a node
        horizon_s,   # capacity — the planning horizon
        False,       # do not force cumulative to start at zero
        "Time",
    )
    return routing.GetDimensionOrDie("Time")

False for fix_start_cumul_to_zero is deliberate. Forcing every vehicle to start at time zero prevents staggered departures, which real fleets use constantly — a second shift leaving at 13:00 cannot be modelled if the dimension insists it left at midnight.

Applying the windows themselves has two halves, and the second is the one people miss.

# requires: ortools (pip install ortools)
def apply_windows(routing, manager, time_dim, windows, depot: int = 0) -> None:
    """Stop windows on nodes; depot windows on each vehicle's own endpoints."""
    for node, (open_s, close_s) in enumerate(windows):
        if node == depot:
            continue
        time_dim.CumulVar(manager.NodeToIndex(node)).SetRange(open_s, close_s)

    depot_open, depot_close = windows[depot]
    for v in range(routing.vehicles()):
        # The depot node is not on any route once vehicles have their own ends
        time_dim.CumulVar(routing.Start(v)).SetRange(depot_open, depot_close)
        time_dim.CumulVar(routing.End(v)).SetRange(depot_open, depot_close)
        routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.Start(v)))
        routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.End(v)))

The finalizer calls are what make departure times meaningful. Without them the solver is free to report any start time consistent with the constraints, and it will typically report the earliest — producing plans that claim a vehicle left at 06:00 and waited an hour at its first stop, when leaving at 07:00 was equally valid and far more useful to a dispatcher.

Softening a window is a separate call on the same dimension:

# requires: ortools (pip install ortools)
def soften_windows(manager, time_dim, windows, late_penalty_per_s: int = 2,
                   depot: int = 0) -> None:
    """Allow late arrival at a linear penalty rather than forbidding it."""
    for node, (_, close_s) in enumerate(windows):
        if node == depot:
            continue
        index = manager.NodeToIndex(node)
        time_dim.SetCumulVarSoftUpperBound(index, close_s, late_penalty_per_s)

The penalty is per second of lateness and enters the same objective as travel time, so it has to be scaled against it. A penalty of 2 means a minute of lateness costs the same as two minutes of driving — enough to matter, not enough to justify an hour-long detour to avoid five minutes late.

Key parameters and tuning

Parameter Recommended value Notes
Slack full horizon Zero slack forbids waiting and is the top cause of false infeasibility
Horizon shift length + 1 h Too tight and late-window stops become structurally unreachable
fix_start_cumul_to_zero False True forbids staggered shift starts
Service time placement departing arc On the arriving arc it shifts every window by one stop
Soft late penalty 1–5 per second Scale against travel-time units; 2 is a reasonable starting point
Depot window on Start(v) and End(v) Setting it on the depot node silently does nothing
Finalizers minimise start and end Without them, reported departure times are arbitrary within the feasible set

Integration points

With the capacity dimension. Time and capacity coexist on the same model and interact only through feasibility. A common surprise is that adding capacity makes a previously feasible time-windowed problem infeasible, because the extra vehicle trips required no longer fit the windows. That is genuine, not a bug — see capacity and multi-depot constraints in fleet dispatch.

With time-dependent travel times. A single matrix assumes travel times are constant across the shift, which they are not. Where windows are tight enough for that to matter, compute the matrix at the shift’s dominant hour using the profile work in time-dependent speed profiles in Python, and accept that the model is an approximation.

With re-routing. When a live event invalidates a plan mid-shift, the remaining stops and their windows become a smaller VRP with the vehicle’s current position as its start. The webhook path in webhook-driven dynamic re-routing is what triggers that re-solve.

Slack against model feasibility With zero slack the model is infeasible because early arrival has no legal continuation. Feasibility appears as soon as slack exceeds the largest gap between an arrival and its window opening, and stays stable thereafter — so there is no reason to tune it finely. Slack allowance against whether the model solves at all 0 30 min 2 h horizon infeasible feasible — and the solution does not change extra slack costs nothing; the solver only waits where it must Because the plateau is flat, there is no benefit to a tight slack value — set it to the horizon and stop thinking about it. Slack permits waiting; it does not encourage it. The objective still penalises the travel time that a wasteful wait implies. How much window width costs in served stops With six vehicles, one-hour delivery windows allow 74 of 120 stops to be served. Widening to two hours reaches 101, four hours reaches 118, and removing windows entirely serves all 120. Stops served against window width, 6 vehicles windows 1 h wide 74 of 120 stops windows 2 h wide 101 windows 4 h wide 118 no windows 120 — the ceiling This curve is the argument for negotiating window width — far more persuasive than a claim that windows are expensive. Run it before adding vehicles — widening a window is usually cheaper than buying a van, and the model can tell you by how much.

Validation checklist

  • A single early arrival is absorbed. Build a two-stop model where the vehicle must arrive before the window opens and confirm it solves. If it does not, slack is wrong.
  • Reported departure times are the latest feasible. With the finalizers in place, a vehicle should not claim to leave an hour before it needs to.
  • Service time appears exactly once. Sum the plan’s arrival deltas and compare against travel plus service computed independently. A doubled service time means it is on both callbacks.
  • A late stop degrades gracefully under soft windows. Push one window out of reach and confirm the model still returns a plan with a penalty rather than reporting infeasibility.
  • Depot windows actually bind. Set an impossibly narrow depot window and confirm the model becomes infeasible. If it still solves, the window was applied to the depot node rather than to the vehicle endpoints.