Time Window Constraints for Waste Route Optimization

A collection truck that arrives at the right stop at the wrong time is not early or late — it is non-compliant. Time window constraints dictate the exact operational hours during which a vehicle may service a node, and in municipal solid waste (MSW) and regulated-waste logistics those hours are rarely arbitrary. They are codified through municipal noise ordinances, commercial service-level agreements (SLAs), transfer-station gate hours, and the federal driving-time ceilings that cap how long a driver can be behind the wheel. When a routing engine treats these windows as advisory, the solver returns a plan that looks efficient on paper and puts a 40,000 lb packer onto a residential street at 5:40 a.m. against a 7:00 a.m. noise cutoff. The failure surfaces as an ordinance complaint filed against the city, a missed-SLA penalty on a commercial contract, or a rejected chain-of-custody record whose pickup timestamp does not reconcile with the facility receipt.

This page is the temporal sub-system of the VRP Route Optimization Algorithms pipeline. It shows how to encode service windows as hard bounds on a solver time dimension the optimizer cannot cross, how those bounds map to the regulations and contracts that authorize them, how to verify the constraint actually fires, and what the engine should do when the windows make a route infeasible. Every code block is complete and pasteable into a Python 3.10+ dispatch worker.

Prerequisites

Pin the solver and validation stack so a dispatch run is byte-for-byte reproducible during an audit. These versions are what the code below is tested against:

python --version   # 3.10 or newer
pip install \
  ortools==9.11.4210 \
  pydantic==2.9.2

Before any time dimension is registered, every service stop must pass a typed schema. An under-specified window — a None bound, a latest earlier than earliest, or a service duration longer than the window itself — is the most common cause of a silently infeasible solve, so reject it at ingestion rather than mid-search. The TimedStop model mirrors the ServiceNode schema used across the OR-Tools Implementation guide and normalizes every timestamp to integer seconds since the shift epoch, because solver dimension arithmetic is integer-only and floating-point minutes accumulate drift across thousands of node insertions.

from __future__ import annotations
from pydantic import BaseModel, Field, model_validator

# The solver counts in whole seconds from the start of the dispatch shift
# (e.g. 04:00 local = 0). Carrying wall-clock strings into the solver is the
# classic source of off-by-a-timezone infeasibility, so we normalise up front.


class TimedStop(BaseModel):
    node_id: int = Field(ge=0)
    lat: float = Field(ge=-90.0, le=90.0)
    lon: float = Field(ge=-180.0, le=180.0)
    earliest_s: int = Field(ge=0)          # window opens, seconds from shift epoch
    latest_s: int = Field(ge=0)            # window closes, seconds from shift epoch
    service_s: int = Field(ge=0)           # dwell time at the stop, seconds
    hard: bool = True                      # hard window vs. soft (penalised) window

    @model_validator(mode="after")
    def check_window(self) -> "TimedStop":
        if self.latest_s < self.earliest_s:
            raise ValueError(f"node {self.node_id}: latest_s < earliest_s")
        if self.service_s > (self.latest_s - self.earliest_s) and self.hard:
            raise ValueError(
                f"node {self.node_id}: service_s exceeds hard window span")
        return self

Each stop carries a hard flag. Hard windows enforce strict arrival bounds; a violation makes the whole plan infeasible. Soft windows permit temporal deviation but apply an escalating penalty that degrades the objective score — appropriate for a courtesy SLA but never for a noise ordinance or a driving-time ceiling. This classification is the single most important decision on the page: a soft constraint is, by definition, one the optimizer is allowed to break when the cost math favors it.

Core Implementation

The temporal model has three moving parts: a transit callback that returns travel-plus-service time between nodes, a time dimension registered with bounded slack, and a per-node range applied to the cumulative arrival variable. Build them in that order.

Step 1 — Deterministic transit callback. The callback must return integer seconds and must be deterministic; non-deterministic or floating-point approximations introduce solver instability that flips borderline routes between feasible and infeasible between runs. Cache the traffic-adjusted matrix and validate it against known depot-to-node baselines before passing it in.

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def make_transit_callback(manager, travel_s, stops):
    """Travel time from i to j plus the dwell time consumed at i."""
    def transit(from_index: int, to_index: int) -> int:
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        return int(travel_s[i][j]) + int(stops[i].service_s)
    return transit

Step 2 — Register the time dimension. AddDimension binds the callback to a cumulative “Time” quantity. The slack_max argument is wait time the truck may absorb when it arrives before a window opens; max_route_time is the per-vehicle ceiling that later carries the hours-of-service cap. Wrap initialization in explicit exception handling so an infeasible constraint graph is caught at build time, not mid-solve.

def build_time_dimension(routing, transit_index, max_route_time, slack_max):
    try:
        routing.AddDimension(
            transit_index,
            slack_max,        # max wait (slack) allowed before a window opens
            max_route_time,   # per-vehicle upper bound — carries the HOS ceiling
            False,            # do NOT force cumulative start to zero
            "Time",
        )
        return routing.GetDimensionOrDie("Time")
    except Exception as exc:  # infeasible dimension graph surfaces here
        raise RuntimeError(f"time dimension init failed: {exc}") from exc

Step 3 — Apply per-node windows and assemble the model. Setting the range on each node’s CumulVar is what makes a hard window hard: the solver treats an arrival outside [earliest_s, latest_s] as infeasible rather than as a penalty. Soft stops instead get a SetCumulVarSoftUpperBound penalty so the solver may overshoot at a cost.

def build_time_model(stops, travel_s, num_vehicles, depot=0,
                     max_route_time=11 * 3600, slack_max=1800):
    manager = pywrapcp.RoutingIndexManager(len(stops), num_vehicles, depot)
    routing = pywrapcp.RoutingModel(manager)

    transit_index = routing.RegisterTransitCallback(
        make_transit_callback(manager, travel_s, stops))
    routing.SetArcCostEvaluatorOfAllVehicles(transit_index)

    time_dim = build_time_dimension(
        routing, transit_index, max_route_time, slack_max)

    for node, stop in enumerate(stops):
        if node == depot:
            continue
        index = manager.NodeToIndex(node)
        if stop.hard:
            time_dim.CumulVar(index).SetRange(stop.earliest_s, stop.latest_s)
        else:
            time_dim.CumulVar(index).SetRange(stop.earliest_s, max_route_time)
            time_dim.SetCumulVarSoftUpperBound(index, stop.latest_s, 8)

    # Depot windows bound the shift itself for every vehicle.
    for v in range(num_vehicles):
        start = routing.Start(v)
        time_dim.CumulVar(start).SetRange(
            stops[depot].earliest_s, stops[depot].latest_s)
        routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(start))
        routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.End(v)))

    return routing, manager, time_dim

The relationship the dimension enforces is straightforward. For a truck arriving at node $i$ at time $t_i$, every hard window bounds the arrival directly, and travel plus dwell links consecutive stops:

$$e_i \le t_i \le \ell_i \qquad t_j \ge t_i + s_i + \tau_{ij}$$

where $e_i$ and $\ell_i$ are the earliest and latest bounds, $s_i$ the service duration, and $\tau_{ij}$ the travel time between $i$ and $j$. When the truck reaches $i$ before $e_i$, the slack variable absorbs the difference as wait time rather than violating the window. For the exact callback signatures OR-Tools expects, Google’s Vehicle Routing Problem with Time Windows documentation is the canonical reference.

Step 4 — Solve and extract arrivals. Guided local search is the default metaheuristic; bound the search with a time limit so a hard-window-dense instance cannot spin indefinitely.

def solve_time_model(routing, manager, time_dim, stops, seconds=10):
    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    params.time_limit.FromSeconds(seconds)

    solution = routing.SolveWithParameters(params)
    if solution is None:
        raise RuntimeError("time-window constraint set is unsatisfiable")

    routes = []
    for v in range(routing.vehicles()):
        idx, legs = routing.Start(v), []
        while not routing.IsEnd(idx):
            node = manager.IndexToNode(idx)
            arrival = solution.Value(time_dim.CumulVar(idx))
            legs.append({"node": node, "arrival_s": arrival})
            idx = solution.Value(routing.NextVar(idx))
        routes.append({"vehicle": v, "stops": legs})
    return routes

Regulatory Mapping

Every window bound in the model above must trace to a rule an inspector — or a contract manager — can cite. Do not assert hours in prose; pin them to the regulation or ordinance that authorizes the limit so the compliance registry can version them.

The federal driving-time ceilings enter the model as the max_route_time argument and the mandatory rest node, and they are the reason HOS behaves as a rolling hard window on vehicle availability rather than a per-stop bound. Their full binding pattern — on-duty accounting, break insertion, and cycle limits — is defined in the DOT/FMCSA Rule Mapping reference, and the same arrival timestamp the solver emits must reconcile with the EPA e-Manifest declared pickup and receipt times under 40 CFR 262 so a regulated-waste run’s chain of custody holds up. Municipal noise ordinances routinely override the federal baseline for specific street segments; store those as jurisdictional overrides in a compliance registry keyed by segment and resolve the effective window as the intersection of the shift window and any active local restriction.

Validation & Verification

A time window that silently never binds is worse than none — it gives false assurance. Prove it fires with a unit test whose geometry makes an unconstrained solver want to violate a window, then assert every arrival lands inside its bound.

def is_within_window(arrival_s: int, stop: TimedStop) -> bool:
    return stop.earliest_s <= arrival_s <= stop.latest_s


def test_hard_window_forces_wait_or_reject() -> None:
    # Node 2 opens late; a mileage-only solver would visit it first.
    stops = [
        TimedStop(node_id=0, lat=40.0, lon=-83.0,
                  earliest_s=0, latest_s=11 * 3600, service_s=0),        # depot
        TimedStop(node_id=1, lat=40.1, lon=-83.1,
                  earliest_s=0, latest_s=3600, service_s=300),
        TimedStop(node_id=2, lat=40.2, lon=-83.2,
                  earliest_s=7200, latest_s=9000, service_s=300),        # opens at 2h
    ]
    travel_s = [[0, 600, 1200], [600, 0, 600], [1200, 600, 0]]

    routing, manager, time_dim = build_time_model(stops, travel_s, num_vehicles=1)
    routes = solve_time_model(routing, manager, time_dim, stops)

    for leg in routes[0]["stops"]:
        node = leg["node"]
        if node == 0:
            continue
        assert is_within_window(leg["arrival_s"], stops[node]), \
            f"node {node} arrived at {leg['arrival_s']} outside its window"

In production, emit each node’s arrival and its window as structured fields so the assertion above has a logged counterpart. Follow the site-wide JSONFormatter pattern so compliance events land in the audit database as machine-parseable records rather than free text:

import json
import logging


class JSONFormatter(logging.Formatter):
    def format(self, record: logging.LogRecord) -> str:
        payload = {
            "level": record.levelname,
            "event": record.getMessage(),
            "vehicle": getattr(record, "vehicle", None),
            "node": getattr(record, "node", None),
            "arrival_s": getattr(record, "arrival_s", None),
            "earliest_s": getattr(record, "earliest_s", None),
            "latest_s": getattr(record, "latest_s", None),
        }
        return json.dumps(payload, separators=(",", ":"))


logger = logging.getLogger("time_window")
_handler = logging.StreamHandler()
_handler.setFormatter(JSONFormatter())
logger.addHandler(_handler)
logger.setLevel(logging.INFO)

for route in routes:
    for leg in route["stops"]:
        node = leg["node"]
        logger.info(
            "arrival_window_check",
            extra={"vehicle": route["vehicle"], "node": node,
                   "arrival_s": leg["arrival_s"],
                   "earliest_s": stops[node].earliest_s,
                   "latest_s": stops[node].latest_s},
        )

The three log fields an auditor checks are arrival_s, earliest_s, and latest_s: on every hard node the arrival must fall inside the bounds, and every dispatched plan should carry one such record per serviced stop.

Failure Modes & Edge Cases

When the windows cannot all be satisfied, SolveWithParameters returns None — the solver is telling you the constraint set is unsatisfiable, not that it crashed. Never widen a hard window to make an infeasible plan “work”; that trades a citation for a noise complaint. Instead, degrade along a defined ladder.

1. Drop non-compliant nodes rather than violate them. For regulated, biomedical, or hazardous stops that tolerate zero deviation, add a disjunction so the solver may leave a node unserved (at a high penalty) rather than arrive outside its window. The dedicated Solving VRPTW with Strict Pickup Windows guide covers the zero-slack propagation these routes require.

def allow_drop_over_serve(routing, manager, stops, drop_penalty=10_000_000):
    """Let the solver skip a stop it cannot serve in-window instead of violating it."""
    for node, stop in enumerate(stops):
        if node == 0:
            continue
        if stop.hard:  # a missed hard stop is a rescheduled truck, not a fine
            routing.AddDisjunction([manager.NodeToIndex(node)], drop_penalty)

2. Widen only soft windows. If the infeasibility comes from courtesy SLA windows, relax those bounds — never the ordinance or HOS-derived ones — and re-solve before provisioning more trucks.

def solve_with_soft_window_relaxation(stops, travel_s, num_vehicles, max_rounds=3):
    """Escalate by loosening SOFT windows only; hard bounds are never touched."""
    working = [s.model_copy(deep=True) for s in stops]
    for round_no in range(1, max_rounds + 1):
        routing, manager, time_dim = build_time_model(working, travel_s, num_vehicles)
        try:
            return solve_time_model(routing, manager, time_dim, working)
        except RuntimeError:
            widened = 0
            for s in working:
                if not s.hard:
                    s.latest_s = min(s.latest_s + 1800, 11 * 3600)  # +30 min cap
                    widened += 1
            logger.warning(
                "time_window_infeasible",
                extra={"vehicle": None, "node": None, "arrival_s": None,
                       "earliest_s": round_no, "latest_s": widened},
            )
            if widened == 0:
                break  # nothing soft left to relax — the hard set is unsatisfiable
    raise RuntimeError(f"still infeasible after {max_rounds} relaxation rounds")

3. Telemetry drift and gaps. GPS jitter under urban-canyon multipath pushes arrival estimates off by tens of seconds, and a dropped feed leaves the model solving on a stale position. Do not feed a raw or missing coordinate into the matrix; reconciling those gaps before the matrix is built is the job of the Telematics Sensor Data Ingestion pipeline, which smooths trajectories and substitutes a last-known-good position rather than letting the solver ingest a corrupt travel time. When live conditions shift the achievable windows mid-shift, the Dynamic Threshold Tuning layer recalibrates slack and soft-bound penalties from that reconciled telemetry.

4. Circuit-break the search. A window-dense instance can send guided local search into a long unproductive descent. Cap it with the time_limit set in solve_time_model and treat a timeout as infeasibility — hand the plan to the compliance-preserving fallback tier rather than shipping a half-optimized route.

Integration Checklist

Complete every item before a time-window model reaches production dispatch:

• All service stops pass the TimedStop schema; every window has earliest_s <= latest_s and service_s fits inside a hard window.
• Timestamps are normalized to integer seconds from a single shift epoch before entering the solver.
• The transit callback returns deterministic integer seconds including dwell time, validated against depot-to-node baselines.
• Hard windows use CumulVar.SetRange; soft windows use SetCumulVarSoftUpperBound with an explicit penalty.
• max_route_time carries the FMCSA 11-hour driving ceiling and the depot window carries the 14-hour on-duty span.
• Mandatory 30-minute break is modeled as a rest node, not omitted.
• The window-forcing unit test runs in CI and every arrival assertion passes.
• Every dispatched route emits an arrival_window_check record with arrival_s, earliest_s, and latest_s.
• Infeasible solves relax soft windows or drop nodes via disjunction — never widen an ordinance or HOS-derived bound.
• Telemetry-gap routes fall back to a last-known-good position and are flagged for manual review.

FAQ

When should a service window be soft instead of hard?

Only when the window is a courtesy or contractual preference whose breach costs money but not compliance — a commercial SLA target, for example. Noise ordinances, transfer-station gate hours, HOS ceilings, and regulated-waste timing must be hard, because a soft penalty lets the solver knowingly emit an illegal plan when the cost math favors it. Set hard=True for anything an inspector can cite.

Why normalize timestamps to integer seconds from a shift epoch?

OR-Tools dimension arithmetic is integer-only, and carrying wall-clock strings or floating-point minutes into the solver accumulates rounding and timezone drift across thousands of node insertions — enough to flip a borderline window between feasible and infeasible non-deterministically. A single integer epoch keeps every solve reproducible for audit.

What does the solver do when no plan satisfies all hard windows?

SolveWithParameters returns None, which is the correct signal that the constraint set is unsatisfiable. Escalate through the ladder — relax soft windows, then allow high-penalty node drops via disjunction — and log a time_window_infeasible event. Never widen a hard window to force a solution.

How do hours-of-service rules become time windows?

The 11-hour driving ceiling maps to max_route_time on the Time dimension, the 14-hour on-duty window bounds the depot start and end CumulVar, and the mandatory 30-minute break becomes a rest node with a fixed service duration. Because they cap the vehicle rather than a single stop, they behave as a rolling hard window on availability. See the DOT/FMCSA Rule Mapping reference for the full binding pattern.

How is arrival-time slack different from a soft window?

Slack (slack_max) is legitimate wait time the truck absorbs when it arrives before a window opens — it never violates a bound. A soft window, by contrast, permits arrival after the latest bound at a penalty cost. Use slack to model early arrival on hard nodes; use a soft upper bound only for windows you are contractually allowed to overshoot.

Up: VRP Route Optimization Algorithms

Related

• Solving VRPTW with Strict Pickup Windows — zero-slack propagation for regulated and hazardous stops
• OR-Tools Implementation — dimension registration and solver configuration
• Capacity & Weight Limits — payload ceilings that intersect service windows
• Dynamic Threshold Tuning — recalibrating slack and penalties from live telemetry
• DOT/FMCSA Rule Mapping — binding hours-of-service ceilings as hard dimensions