Core Architecture & Compliance Mapping for Waste Route Optimization

Municipal waste fleets fail audits for one reason: the routing engine optimized for mileage while treating regulation as an afterthought. A truck that saved four minutes but crossed a load-rated bridge over its axle limit, dispatched a driver past their hours-of-service ceiling, or collected during a residential quiet-hour window does not produce a “slightly worse” route — it produces a citation, a rejected e-manifest, and an incident that a public-records request will surface for years. This is the architecture reference for the people who have to prevent that: waste operations managers who sign off on dispatch plans, logistics engineers who own the solver, and the municipal Python developers who wire the pipeline together. It defines how compliance constraints become part of graph construction rather than a filter bolted on afterward, and how every routing decision emits a verifiable record that survives solver timeouts, sensor dropout, and a hostile audit two years later.

The unifying principle across every section below is determinism. Given the same input matrix, the same constraint configuration, and the same random seed, the pipeline must produce byte-identical output and byte-identical audit hashes. Heuristic experimentation — random restarts, wall-clock-dependent timeouts, floating soft penalties — is the enemy of an auditable system. Everything here is built so that a dispatch decision can be replayed, re-hashed, and defended.

Constraint Architecture: Why Waste Constraints Are Hard, Not Soft

A soft constraint is a preference the solver may violate for a better objective value. A hard constraint is a boundary the solver may never cross, even if the only feasible route is expensive. The defining architectural decision for municipal waste routing is that almost every regulatory constraint is hard. Modeling them as penalties — the academic default — is precisely why academic VRP code fails in production: given enough cost pressure, a penalty-weighted solver will always find a scenario where paying the penalty “wins,” and that scenario is a violation on your compliance record.

The hard-constraint set for a municipal fleet is enumerable and non-negotiable:

• Regulatory collection windows. Commercial and residential zones carry legally binding service windows — early-start noise ordinances, school-zone blackout intervals, and low-emission-corridor timing. These are modeled as Time Window Constraints that reject infeasible arrivals outright rather than pricing them in. A route that arrives at 05:40 in a 07:00-noise-ordinance zone is not a slightly-penalized route; it is an illegal route.
• Gross Vehicle Weight Rating (GVWR). A loaded packer truck must never exceed its rated mass. Because fill accumulates across a route, capacity is a dimension that grows monotonically along the path, not a single check at the depot. This is enforced through Capacity & Weight Limits bound as a cumulative dimension during node insertion.
• Per-axle load limits. GVWR compliance is necessary but not sufficient. A truck can be under its total rating and still overload a single axle or exceed a bridge’s posted rating. Axle distribution is a function of where mass sits in the hopper, so it must be evaluated as fill accumulates.
• Driver Hours of Service (HOS). Federal driving-time and on-duty limits cap how long a route may run and force rest breaks. These are modeled as mandatory dwell nodes and a route-duration ceiling, mapped rule-by-rule in the DOT/FMCSA Rule Mapping reference so each solver parameter traces back to a CFR citation.
• Disposal-facility tipping hours and capacity. Transfer stations and landfills accept loads only during posted hours and up to daily tonnage caps. A route that fills a truck but reaches a closed or capped facility is infeasible, not suboptimal.

Every one of these enters the model through the canonical data contract defined in Route Schema Design. If a constraint value cannot be validated at ingestion — a missing GVWR, a malformed service window, an out-of-range coordinate — the record is rejected at the edge and never reaches the solver. Feeding uncertain data into a deterministic solver produces confidently wrong routes.

The distinction between GVWR and axle compliance is worth making concrete, because operators frequently conflate them. Total mass compliance requires that accumulated payload plus tare stays under the rating:

$$W_{\text{gross}} = W_{\text{tare}} + \sum_{i=1}^{k} m_i \le \text{GVWR}$$

where $m_i$ is the mass collected at the $i$-th stop along the route and $k$ is the number of stops served so far. Axle compliance is stricter: for a two-axle unit with wheelbase $L$ and a load whose center of mass sits distance $d$ ahead of the rear axle, the rear-axle share is

$$W_{\text{rear}} = W_{\text{tare,rear}} + \frac{d}{L}\sum_{i=1}^{k} m_i \le A_{\text{rear}}$$

Because the collected mass sits in the hopper (behind the cab), the rear axle saturates well before the gross rating does. A model that checks only $W_{\text{gross}}$ will happily plan a legal-by-GVWR route that is illegal by rear-axle load. Both must be bound as separate cumulative dimensions.

Core Algorithmic Pattern: Binding Compliance Into Graph Construction

The algorithmic core is a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), solved with Google OR-Tools using constraint programming (CP-SAT) and guided local search as the metaheuristic. The full solver setup — environment isolation, callback signatures, and search parameters — lives in the OR-Tools Implementation reference and its parent, the VRP Route Optimization Algorithms architecture. What matters at the architecture level is the constraint binding pattern: the discipline of registering every regulatory limit as a dimension or hard callback before the first solve iteration runs, so infeasibility is impossible by construction rather than caught by inspection.

The pattern below shows the binding sequence — distance callback, cumulative capacity dimension, time-window dimension, and an HOS route-duration ceiling — all registered against the routing model before SolveWithParameters is ever called. Note the custom JSONFormatter; Python’s standard logging module has no built-in JSON formatter, so a custom one is required for structured audit output, and this pattern is used site-wide.

import json
import logging
from dataclasses import dataclass
from ortools.constraint_solver import routing_enums_pb2, pywrapcp


class JSONFormatter(logging.Formatter):
    """Custom JSON formatter — the standard logging module has no built-in JSONFormatter."""
    def format(self, record):
        log_obj = {
            "timestamp": self.formatTime(record),
            "level": record.levelname,
            "message": record.getMessage(),
        }
        log_obj.update({k: v for k, v in record.__dict__.items()
                        if k not in logging.LogRecord.__dict__ and not k.startswith("_")})
        return json.dumps(log_obj)


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


@dataclass(frozen=True)
class FleetModel:
    num_vehicles: int
    depot: int
    gvwr_kg: list[int]           # per-vehicle gross rating
    axle_limit_kg: list[int]     # per-vehicle rear-axle limit
    hos_seconds: list[int]       # per-vehicle max on-duty seconds
    demands_kg: list[int]        # per-stop collected mass
    service_windows: list[tuple[int, int]]  # per-stop (open, close) seconds


def build_constrained_model(fleet: FleetModel, time_matrix, dist_matrix, axle_ratio: float):
    """Register every regulatory limit as a hard dimension BEFORE solving."""
    mgr = pywrapcp.RoutingIndexManager(len(dist_matrix), fleet.num_vehicles, fleet.depot)
    routing = pywrapcp.RoutingModel(mgr)

    # --- distance / objective callback ---
    def dist_cb(i, j):
        return dist_matrix[mgr.IndexToNode(i)][mgr.IndexToNode(j)]
    dist_idx = routing.RegisterTransitCallback(dist_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(dist_idx)

    # --- GVWR as a cumulative capacity dimension (hard, per vehicle) ---
    def demand_cb(i):
        return fleet.demands_kg[mgr.IndexToNode(i)]
    demand_idx = routing.RegisterUnaryTransitCallback(demand_cb)
    routing.AddDimensionWithVehicleCapacity(
        demand_idx, 0, fleet.gvwr_kg, True, "Weight")

    # --- rear-axle load as a SEPARATE cumulative dimension (hard) ---
    def axle_cb(i):
        return int(fleet.demands_kg[mgr.IndexToNode(i)] * axle_ratio)
    axle_idx = routing.RegisterUnaryTransitCallback(axle_cb)
    routing.AddDimensionWithVehicleCapacity(
        axle_idx, 0, fleet.axle_limit_kg, True, "Axle")

    # --- time-window dimension with HOS route-duration ceiling ---
    def time_cb(i, j):
        return time_matrix[mgr.IndexToNode(i)][mgr.IndexToNode(j)]
    time_idx = routing.RegisterTransitCallback(time_cb)
    max_hos = max(fleet.hos_seconds)
    routing.AddDimension(time_idx, 3600, max_hos, False, "Time")
    time_dim = routing.GetDimensionOrDie("Time")

    for node, (open_s, close_s) in enumerate(fleet.service_windows):
        index = mgr.NodeToIndex(node)
        time_dim.CumulVar(index).SetRange(open_s, close_s)  # HARD window

    # per-vehicle HOS ceiling on the end node
    for v in range(fleet.num_vehicles):
        end = routing.End(v)
        time_dim.CumulVar(end).SetMax(fleet.hos_seconds[v])

    logger.info("model built", extra={
        "vehicles": fleet.num_vehicles,
        "nodes": len(dist_matrix),
        "dimensions": ["Weight", "Axle", "Time"],
    })
    return mgr, routing

The True flag on each AddDimensionWithVehicleCapacity call forces the cumulative value to start at zero and never exceed the per-vehicle capacity — that is what makes GVWR and axle limits hard. The SetRange on each time-window CumulVar makes arrival outside the legal window infeasible, not merely penalized. If the solver returns None, no legal route exists under the current data, and the correct response is to invoke the fallback tier described below — never to relax a regulatory dimension.

Fleet & Depot Distribution

Single-depot assumptions collapse the moment a municipality runs more than one yard or operates specialized equipment pools. Real fleets are heterogeneous: rear-loaders for residential routes, front-loaders for commercial dumpsters, roll-off trucks for construction containers, and vacuum units for organics — each with distinct GVWR, axle geometry, and depot assignment. Modeling them as one interchangeable vehicle class produces plans that are infeasible on the ground even when the solver reports success.

Multi-depot assignment binds each vehicle to a primary start-and-return facility at model initialization, with explicit secondary-depot fallbacks for maintenance routing, emergency offload, and seasonal equipment swaps. The routing manager accepts per-vehicle start and end indices, so the depot topology is expressed directly rather than approximated:

def build_multi_depot_manager(num_nodes: int, starts: list[int], ends: list[int]):
    """Per-vehicle start/end nodes model heterogeneous yards without a shared depot."""
    assert len(starts) == len(ends), "each vehicle needs an explicit start and end yard"
    mgr = pywrapcp.RoutingIndexManager(num_nodes, len(starts), starts, ends)
    return pywrapcp.RoutingModel(mgr)

Vehicle-type heterogeneity is expressed through the per-vehicle capacity vectors already shown (gvwr_kg, axle_limit_kg, hos_seconds) — OR-Tools evaluates each vehicle against its own limits, so a front-loader and a roll-off truck can share one model without cross-contaminating constraints. Yard utilization accounting then falls out of the solution: summing accumulated Weight-dimension values per depot at route end gives per-yard throughput, which feeds capacity planning and prevents overcommitting a yard’s tipping-floor or fueling capacity. Assigning a route to the wrong equipment class — a residential rear-loader to a commercial dumpster it physically cannot lift — is caught here, at assignment time, rather than at 6 a.m. on the curb.

Dynamic Calibration & Telemetry Integration

Static solver parameters degrade the moment reality diverges from the schedule. Collection density shifts seasonally, weather events reshape service patterns, and bin fill rates drift as neighborhoods change. The architecture treats solver inputs as live values derived from field telemetry rather than constants baked into a YAML file. Raw GPS, CAN-bus, and IoT bin-sensor streams arrive through the Telematics & Sensor Data Ingestion pipeline, which normalizes, timestamps, and validates them before any value reaches the matrix builder.

Three telemetry channels feed the solver directly. Live bin fill levels — parsed and reconciled by the Bin Sensor API Sync layer — replace static demand estimates with measured mass, tightening the capacity dimension. Vehicle position, sampled through disciplined GPS Polling Strategies that avoid provider rate limits, updates the travel-time matrix so re-dispatch reflects actual road conditions. And solver search parameters themselves — search depth, neighborhood limits, and timeout budgets — are adjusted by Dynamic Threshold Tuning based on observed solve times and constraint-violation rates rather than guesswork.

Live data is never trusted blindly. Every telemetry value passes the Schema Validation Pipelines gate, and the matrix builder must define behavior for the case that always eventually happens: a gap. When a bin sensor goes dark or a truck enters a cellular dead zone, the pipeline must not stall and must not propagate a null into the solver. It falls back to a historical baseline and flags the estimate so the audit record reflects that the value was inferred, not measured:

from dataclasses import dataclass


@dataclass(frozen=True)
class DemandReading:
    stop_id: str
    measured_kg: int | None
    baseline_kg: int
    source: str  # "sensor" | "baseline"


def resolve_demand(stop_id: str, measured_kg: int | None, baseline_kg: int) -> DemandReading:
    """Never feed a null into the solver — fall back to baseline and mark the source."""
    if measured_kg is None or measured_kg < 0:
        return DemandReading(stop_id, None, baseline_kg, source="baseline")
    return DemandReading(stop_id, measured_kg, baseline_kg, source="sensor")

The source field is not cosmetic. It travels into the compliance record so that any later dispute over a route can distinguish decisions made on measured data from decisions made on inference — a distinction auditors care about and dispatchers need when defending a plan.

Immutable Compliance Logging

A route that cannot be proven compliant is not compliant. The architecture treats every dispatch as an evidentiary artifact: before the plan leaves the system, it is hashed together with the exact constraint configuration that produced it, and that hash anchors an append-only, tamper-evident log. Because the solver is deterministic, the hash is reproducible — an auditor can re-run the same inputs and confirm the same digest, which turns “trust us” into “verify it yourself.”

The hash covers both the input matrix and the constraint config, because a route is only meaningful relative to the rules it was solved under. A record that logs the output path but not the GVWR, windows, and HOS limits in force proves nothing. The signing and key-rotation discipline around these records — who may write, who may read, how keys rotate — is governed by the Security & Access Boundaries framework, which also enforces tenant isolation so one municipality’s telemetry never leaks into another’s audit trail.

import hashlib
import json
import time


def compliance_hash(dist_matrix, constraint_config: dict) -> str:
    """Deterministic digest over BOTH the input matrix and the constraint config."""
    canonical = json.dumps(
        {"matrix": dist_matrix, "constraints": constraint_config},
        sort_keys=True, separators=(",", ":"),
    )
    return hashlib.sha256(canonical.encode("utf-8")).hexdigest()


def build_audit_record(route_id: str, vehicle_id: str, path: list[int],
                       dist_matrix, constraint_config: dict,
                       prev_hash: str) -> dict:
    """Append-only, hash-chained compliance record with DOT/FMCSA/EPA fields."""
    payload_hash = compliance_hash(dist_matrix, constraint_config)
    record = {
        "route_id": route_id,
        "vehicle_id": vehicle_id,
        "path": path,
        "input_hash": payload_hash,
        "prev_hash": prev_hash,               # hash-chain link
        "hos_ceiling_seconds": constraint_config["hos_seconds"],  # 49 CFR 395
        "gvwr_kg": constraint_config["gvwr_kg"],                  # 49 CFR 393
        "epa_manifest_id": constraint_config.get("manifest_id"),  # EPA Form 8700-22
        "waste_stream_code": constraint_config.get("waste_stream_code"),
        "generated_at": time.time(),
    }
    record["chain_hash"] = hashlib.sha256(
        (prev_hash + payload_hash).encode("utf-8")).hexdigest()
    return record

Each record carries the fields an inspector actually asks for: the HOS ceiling that governed the plan (49 CFR Part 395), the GVWR the plan respected (49 CFR Part 393), and, for regulated waste, the EPA hazardous-waste manifest identifier (EPA Form 8700-22) and stream code. The exact field-level structure for state e-manifest submission is defined in the JSON Schema for Municipal Disposal Tracking. The prev_hash/chain_hash linkage makes the log tamper-evident: altering any historical record breaks every hash after it, so silent edits are detectable by anyone holding the chain.

Failure Modes & Production Gotchas

Production routing breaks in a small number of predictable ways. Each has a concrete mitigation, and the architecture’s job is to convert every one of them from an outage into a known, logged operational state.

Infeasible constraint sets. When no route satisfies every hard constraint, SolveWithParameters returns None. The wrong response is to relax a regulatory dimension until something solves; the right response is to transition to a precomputed backup plan and flag the infeasibility for review. This branch is the entry point to the Fallback Routing Logic state machine.

def solve_or_fallback(routing, search_params, fallback_tier: dict, route_id: str):
    solution = routing.SolveWithParameters(search_params)
    if solution is None:
        logger.error("infeasible constraint set", extra={
            "route_id": route_id, "action": "fallback", "tier": "precomputed"})
        return fallback_tier[route_id]        # never relax a hard rule to force a solve
    return solution

Solver timeouts. Guided local search can exceed its latency budget on a hard instance. Bound it with an explicit time limit so the worker never blocks a dispatch window; a partial-but-feasible solution beats an unbounded search.

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_params.time_limit.FromSeconds(30)      # hard wall on solve time
search_params.log_search = False              # deterministic, quiet runs

GPS drift. Coordinates near dense urban canyons scatter, snapping stops to the wrong parcel and corrupting the distance matrix. Reject readings outside valid ranges or beyond a plausible jump distance before they reach the builder — the full validator pattern lives in Validating GPS Coordinates in Python.

def is_plausible_fix(lat: float, lon: float, prev, max_jump_m: float = 500.0) -> bool:
    if not (-90.0 <= lat <= 90.0 and -180.0 <= lon <= 180.0):
        return False
    if prev is None:
        return True
    # cheap planar guard against teleport-style drift between consecutive fixes
    dlat = (lat - prev[0]) * 111_320
    dlon = (lon - prev[1]) * 111_320
    return (dlat * dlat + dlon * dlon) ** 0.5 <= max_jump_m

Memory bottlenecks during matrix construction. A dense distance matrix is $O(n^2)$; at several thousand stops it exhausts memory during peak dispatch. The mitigation is chunked, sparse construction, covered next.

Performance & Scalability

Matrix construction, not the solve, is where large fleets run out of memory. A 5,000-stop dense float64 matrix is roughly 200 MB before the solver allocates anything; at 10,000 stops it is 800 MB, and several concurrent workers will trigger the OOM killer during the morning dispatch spike. Three techniques keep it bounded.

Chunked computation builds the matrix in row blocks so peak working-set stays flat regardless of fleet size:

import gc
import numpy as np


def build_matrix_chunked(coords: np.ndarray, chunk: int = 512) -> np.ndarray:
    """Row-blocked Haversine matrix — bounds peak memory and triggers GC per block."""
    n = len(coords)
    out = np.zeros((n, n), dtype=np.float32)     # float32 halves the footprint
    lat = np.radians(coords[:, 0])
    lon = np.radians(coords[:, 1])
    for start in range(0, n, chunk):
        end = min(start + chunk, n)
        dlat = lat[start:end, None] - lat[None, :]
        dlon = lon[start:end, None] - lon[None, :]
        a = np.sin(dlat / 2) ** 2 + (
            np.cos(lat[start:end, None]) * np.cos(lat[None, :]) * np.sin(dlon / 2) ** 2)
        out[start:end] = 6_371_000 * 2 * np.arcsin(np.sqrt(a))
        del dlat, dlon, a
        gc.collect()                              # release block temporaries eagerly
    return out

The Haversine great-circle distance underlying that block is

$$d = 2r \arcsin\!\left(\sqrt{\sin^2\!\frac{\Delta\varphi}{2} + \cos\varphi_1 \cos\varphi_2 \sin^2\!\frac{\Delta\lambda}{2}}\right)$$

with earth radius $r = 6{,}371{,}000$ m, latitudes $\varphi_1,\varphi_2$, and deltas $\Delta\varphi,\Delta\lambda$ in radians.

Sparse representation exploits the fact that most stop pairs are irrelevant — a stop is only ever routed to nearby neighbors. Keeping the $k$ nearest edges per node collapses an $O(n^2)$ dense matrix to $O(nk)$, which for $k \approx 20$ is a hundredfold reduction at 2,000 stops and is what makes 10,000-stop instances tractable at all. GC discipline matters because NumPy block temporaries are large and short-lived; an explicit gc.collect() per chunk keeps resident memory flat instead of sawtoothing toward the OOM threshold.

Concrete targets for a single worker on commodity hardware: routes up to ~500 stops should build-and-solve in under a second and belong to real-time re-dispatch; 500–2,000 stops in the low seconds, suitable for interactive planning; 2,000–10,000 stops require chunked-sparse construction and a bounded solve budget, and belong to overnight batch generation of the fallback tier. Beyond 10,000 stops the correct move is geographic partitioning into per-zone sub-problems solved in parallel, then reconciled — a single monolithic matrix at that scale is an anti-pattern regardless of available RAM.

Related

• Route Schema Design — the canonical data contract every constraint value must pass before it reaches the solver.
• DOT/FMCSA Rule Mapping — how federal mandates translate into hard solver dimensions with CFR citations.
• Security & Access Boundaries — signing, key rotation, and tenant isolation for the audit chain.
• Fallback Routing Logic — the degradation state machine invoked on infeasibility or solver timeout.
• VRP Route Optimization Algorithms — the solver architecture this reference builds its constraint bindings on.

Up: Route Optimization Home