Multi-Depot Routing for Municipal Waste Fleets

A single-depot routing model quietly assumes every truck leaves from and returns to the same yard. The moment a city runs two collection garages, a maintenance annex, and an organics facility on the far side of a river, that assumption starts fabricating routes that no dispatcher would ever run: a roll-off tasked from the north yard is sent to service a zone twenty minutes past the south yard’s own trucks, the distance matrix silently blends travel costs between yards that share no crews, and one garage ends the shift with nine trucks out while another sits at three. The plan looks optimal to the solver because the solver was never told the yards are different places with different fleets. The failure surfaces as deadhead mileage nobody budgeted, a franchise-boundary complaint from a neighboring jurisdiction, and a yard whose parking capacity is overrun at 5 a.m.

This page is the multi-depot sub-system of the VRP Route Optimization Algorithms pipeline. It shows how to bind each vehicle to a specific start and end yard through the per-vehicle index vectors OR-Tools exposes on RoutingIndexManager, how to keep a heterogeneous fleet’s capacity ceilings attached to the right trucks across yards, how to model a secondary-depot fallback when a home yard overflows, and how to read per-yard trucks-out and deadhead straight off the solution. Every code block is complete and pasteable into a Python 3.10+ dispatch worker. For the mechanics of wiring the manager itself, the deep dive on assigning vehicles to depots in OR-Tools carries the index-vector details to their conclusion.

Prerequisites

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

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

Before any vehicle is bound to a yard, three things must pass a typed schema: the depots themselves, the vehicle classes and their home yard, and the collection zones each truck may serve. The single most damaging class of bug in multi-depot modeling is an off-by-one node index — a vehicle whose home_depot points at a node that is not actually a depot — so validate the relationships up front rather than discovering them as an infeasible solve. The Depot, VehicleClass, and CollectionZone models below mirror the ServiceNode conventions used across the OR-Tools Implementation guide.

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

# Depot node ids occupy the low indices [0, num_depots) of the node list;
# service stops follow. Keeping depots contiguous at the front makes the
# start/end index vectors trivial to reason about and to audit.


class Depot(BaseModel):
    depot_id: int = Field(ge=0)
    name: str
    lat: float = Field(ge=-90.0, le=90.0)
    lon: float = Field(ge=-180.0, le=180.0)
    parking_slots: int = Field(gt=0)  # max trucks this yard can stage at once


class VehicleClass(BaseModel):
    name: str
    count: int = Field(ge=0)
    payload_capacity_kg: int = Field(gt=0)   # GVWR minus tare
    home_depot: int = Field(ge=0)            # index into the depot list
    can_borrow: bool = True                  # eligible for secondary-depot lending


class CollectionZone(BaseModel):
    zone_id: int
    jurisdiction: str                        # franchise boundary owner
    stop_ids: list[int]
    primary_depot: int = Field(ge=0)

    @field_validator("stop_ids")
    @classmethod
    def non_empty(cls, v: list[int]) -> list[int]:
        if not v:
            raise ValueError("A collection zone must contain at least one stop.")
        return v


class FleetPlan(BaseModel):
    depots: list[Depot]
    vehicles: list[VehicleClass]
    zones: list[CollectionZone]

    @model_validator(mode="after")
    def depot_indices_resolve(self) -> "FleetPlan":
        valid = {d.depot_id for d in self.depots}
        for vc in self.vehicles:
            if vc.home_depot not in valid:
                raise ValueError(f"{vc.name} home_depot {vc.home_depot} is not a depot")
        for z in self.zones:
            if z.primary_depot not in valid:
                raise ValueError(f"zone {z.zone_id} primary_depot is not a depot")
        return self

Rejecting an unresolved home_depot at validation time is what prevents the classic multi-yard failure: a truck silently anchored to node 0 (the default depot) when its garage is node 2, producing a route that deadheads across the whole service area before it collects a single bin.

Core Implementation

Multiple depots in OR-Tools are not a special model — they are a pair of per-vehicle index vectors. Instead of the three-argument RoutingIndexManager(num_nodes, num_vehicles, depot) used for a single yard, you pass starts and ends: two lists, one entry per vehicle, naming the node each truck begins and finishes at. Building those vectors correctly, and binding each vehicle’s capacity to the same ordinal position, is the whole job.

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def flatten_fleet(plan: FleetPlan) -> tuple[list[int], list[int], list[int]]:
    """Expand vehicle classes into per-vehicle starts, ends, and capacities.

    Every truck starts and ends at its own home yard, so `starts == ends`.
    The three lists are index-aligned: vehicle v's capacity is capacities[v],
    its start is starts[v], and its end is ends[v].
    """
    starts: list[int] = []
    capacities: list[int] = []
    for vc in plan.vehicles:
        for _ in range(vc.count):
            starts.append(vc.home_depot)      # node index of the home yard
            capacities.append(vc.payload_capacity_kg)
    ends = list(starts)                       # same-yard return
    if not starts:
        raise ValueError("Fleet is empty; cannot build a multi-depot model.")
    return starts, ends, capacities


def build_multidepot_model(
    plan: FleetPlan,
    demands_kg: list[int],
    time_matrix: list[list[int]],
) -> tuple[pywrapcp.RoutingModel, pywrapcp.RoutingIndexManager, list[int], list[int]]:
    """Bind each vehicle to its start/end yard and attach a per-vehicle capacity."""
    starts, ends, capacities = flatten_fleet(plan)
    num_nodes = len(demands_kg)
    num_vehicles = len(starts)

    # Four-argument manager: per-vehicle start and end nodes, not a single depot.
    manager = pywrapcp.RoutingIndexManager(num_nodes, num_vehicles, starts, ends)
    routing = pywrapcp.RoutingModel(manager)

    def time_callback(from_index: int, to_index: int) -> int:
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        return time_matrix[i][j]

    transit_idx = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

    def demand_callback(from_index: int) -> int:
        return demands_kg[manager.IndexToNode(from_index)]

    demand_idx = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_idx,
        0,                 # zero slack: the payload ceiling is hard
        capacities,        # per-vehicle, keyed to the same ordinal as starts/ends
        True,
        "Payload",
    )
    return routing, manager, starts, capacities

Two details make or break the model. First, starts and ends are index-aligned with capacities: vehicle v’s home yard, return yard, and payload ceiling all live at position v, so a rear-loader based at Yard A can never be scored against a roll-off’s tonnage. This is the same per-vehicle capacity vector the Capacity & Weight Limits dimension relies on, now indexed by yard rather than a flat fleet. Second, because every entry of ends equals its starts entry, the solver is forced to return each truck to the yard it left — a same-yard-return constraint expressed purely through the index vectors, with no extra constraint object required.

Once solved, per-yard accounting falls straight out of the solution because every route’s first and last nodes are known depots. There is no separate reconciliation pass:

from math import radians, sin, cos, asin, sqrt


def haversine_km(lat1: float, lon1: float, lat2: float, lon2: float) -> float:
    r = 6371.0
    dlat, dlon = radians(lat2 - lat1), radians(lon2 - lon1)
    a = sin(dlat / 2) ** 2 + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlon / 2) ** 2
    return 2 * r * asin(sqrt(a))


def solve_and_read_yards(plan, demands_kg, time_matrix, coords):
    routing, manager, starts, capacities = build_multidepot_model(
        plan, demands_kg, time_matrix
    )
    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(20)

    solution = routing.SolveWithParameters(params)
    if solution is None:
        raise RuntimeError("No feasible multi-depot plan under current constraints.")

    # Aggregate trucks-out and deadhead (depot->first-stop leg) per yard.
    yard_stats: dict[int, dict] = {d.depot_id: {"trucks_out": 0, "deadhead_km": 0.0}
                                   for d in plan.depots}
    for v in range(routing.vehicles()):
        start = routing.Start(v)
        if routing.IsEnd(solution.Value(routing.NextVar(start))):
            continue  # vehicle never left its yard
        home = starts[v]
        first_stop = manager.IndexToNode(solution.Value(routing.NextVar(start)))
        yard_stats[home]["trucks_out"] += 1
        yard_stats[home]["deadhead_km"] += haversine_km(
            coords[home][0], coords[home][1],
            coords[first_stop][0], coords[first_stop][1],
        )
    return yard_stats

The deadhead_km figure — the unproductive depot-to-first-stop leg summed per yard — is the number that exposes a bad depot assignment. If one yard’s deadhead balloons, a truck is being sent to a zone another yard should own, which is exactly the cross-yard contamination a single-depot model hides. Feeding those time_matrix values from a correct road-network build is the responsibility of the Distance Matrix Construction layer, and the ceilings each yard’s trucks carry can be shifted at runtime by Dynamic Threshold Tuning when seasonal density swings load one garage harder than another. Where multi-yard collection intersects tight municipal set-out hours, the arrival dimension from Time Window Constraints is bound with the same per-vehicle indexing shown here.

Regulatory Mapping

Depot assignment is not only an efficiency question — which yard a truck runs from, and which jurisdiction’s streets it crosses, are governed by franchise ordinances and interstate weight rules that an inspector can cite. Do not encode these as prose assumptions; pin each to its source so the compliance registry can version them.

The franchise boundary is the constraint most often missed. A CollectionZone.jurisdiction field exists precisely so a secondary-depot fallback can be gated: a truck may only borrow into a zone whose jurisdiction its yard is franchised to serve. When a borrowed truck does cross a boundary — permitted under a mutual-aid or interlocal agreement — the transfer must remain reconcilable with the DOT/FMCSA rule mapping hours-of-service records and, for regulated streams, the EPA e-Manifest declaration under 40 CFR 262, so the transporter recorded on the manifest matches the yard that actually dispatched the truck. Store franchise boundaries and any active mutual-aid overrides as jurisdictional entries in a compliance registry keyed by zone, and resolve the effective set of yards eligible for a zone as the intersection of the franchised yard and any borrowing agreement in force.

Validation & Verification

A multi-depot model that silently routes every truck from node 0 will still return a feasible plan — it will just be a single-depot plan wearing a multi-yard costume. Prove the binding actually holds with a test that asserts each vehicle starts and ends at its declared home yard, and that a zone whose demand exceeds its home fleet triggers a borrow rather than an infeasible solve.

def test_vehicles_return_to_home_yard() -> None:
    # Two yards (nodes 0, 1); four stops (nodes 2..5). Yard A owns one truck,
    # Yard B owns one truck. Demand is small enough that each stays home.
    plan = FleetPlan(
        depots=[
            Depot(depot_id=0, name="Yard A", lat=40.00, lon=-83.00, parking_slots=5),
            Depot(depot_id=1, name="Yard B", lat=40.30, lon=-83.40, parking_slots=5),
        ],
        vehicles=[
            VehicleClass(name="A_loader", count=1, payload_capacity_kg=10_000, home_depot=0),
            VehicleClass(name="B_loader", count=1, payload_capacity_kg=10_000, home_depot=1),
        ],
        zones=[
            CollectionZone(zone_id=1, jurisdiction="north", stop_ids=[2, 3], primary_depot=0),
            CollectionZone(zone_id=2, jurisdiction="south", stop_ids=[4, 5], primary_depot=1),
        ],
    )
    demands = [0, 0, 2_000, 2_000, 2_000, 2_000]
    coords = [(40.00, -83.00), (40.30, -83.40), (40.05, -83.05),
              (40.08, -83.02), (40.28, -83.42), (40.31, -83.38)]
    # Symmetric integer-second matrix built from Haversine for the test.
    n = len(coords)
    tm = [[int(haversine_km(*coords[i], *coords[j]) / 30.0 * 3600) for j in range(n)]
          for i in range(n)]

    routing, manager, starts, caps = build_multidepot_model(plan, demands, tm)
    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    params.time_limit.FromSeconds(5)
    sol = routing.SolveWithParameters(params)
    assert sol is not None, "expected a feasible two-yard plan"

    for v in range(routing.vehicles()):
        start_node = manager.IndexToNode(routing.Start(v))
        end_node = manager.IndexToNode(routing.End(v))
        assert start_node == starts[v], "vehicle did not start at its home yard"
        assert end_node == starts[v], "vehicle did not return to its home yard"

In production, emit the per-yard read as a structured record so the assertion above has a logged counterpart an auditor can query. Follow the site-wide JSONFormatter pattern, with fields distinct to depot accounting:

import json
import logging


class JSONFormatter(logging.Formatter):
    def format(self, record: logging.LogRecord) -> str:
        payload = {
            "level": record.levelname,
            "event": record.getMessage(),
            "depot_id": getattr(record, "depot_id", None),
            "depot_name": getattr(record, "depot_name", None),
            "trucks_out": getattr(record, "trucks_out", None),
            "deadhead_km": getattr(record, "deadhead_km", None),
            "borrowed_in": getattr(record, "borrowed_in", None),
        }
        return json.dumps(payload, separators=(",", ":"))


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

for depot in plan.depots:
    stats = yard_stats[depot.depot_id]
    logger.info(
        "yard_utilization",
        extra={"depot_id": depot.depot_id, "depot_name": depot.name,
               "trucks_out": stats["trucks_out"],
               "deadhead_km": round(stats["deadhead_km"], 2),
               "borrowed_in": stats.get("borrowed_in", 0)},
    )

The two fields an auditor reconciles are trucks_out against each yard’s parking_slots (a yard can never dispatch more trucks than it stages) and deadhead_km as a running efficiency signal. Every dispatched plan should carry one yard_utilization record per depot.

Failure Modes & Edge Cases

Multi-depot models fail in ways single-depot models cannot, because now a plan can be geometrically feasible yet operationally wrong. Each mode below has a deterministic response.

1. Infeasible depot assignment. A vehicle bound to a yard that cannot reach its assigned zone within the fleet’s other hard limits makes SolveWithParameters return None. Never fix this by re-anchoring the truck to node 0 — that reintroduces the single-depot bug. Detect it and escalate through borrowing.

2. Orphaned zone. A zone whose only franchised yard has no available truck must not be silently dropped. Model each stop as droppable with a large penalty (a disjunction) so the solver reports which stops it could not serve rather than returning infeasible, then surface those stops for a borrow decision.

3. Yard capacity overflow → secondary-depot borrowing. When a zone’s demand exceeds its home yard’s fleet, lend a can_borrow vehicle from the nearest adjacent yard that is franchised (or holds a mutual-aid agreement) for the zone’s jurisdiction — cheaper and boundary-safe compared with dispatching a distant reserve.

def solve_with_secondary_depot(plan: FleetPlan, demands_kg, time_matrix, coords,
                               max_borrows: int = 2):
    """Escalate an infeasible/over-capacity yard by borrowing an adjacent
    yard's eligible truck — never by re-anchoring a truck to a wrong yard."""
    working = plan.model_copy(deep=True)
    for attempt in range(max_borrows + 1):
        try:
            return solve_and_read_yards(working, demands_kg, time_matrix, coords)
        except RuntimeError:
            # Find the most-loaded zone and an adjacent lender eligible for it.
            overloaded = max(working.zones,
                             key=lambda z: sum(demands_kg[s] for s in z.stop_ids))
            lender = _nearest_eligible_lender(working, overloaded, coords)
            if lender is None:
                logger.warning("no_eligible_lender",
                               extra={"depot_id": overloaded.primary_depot})
                break
            # Add one borrowed truck homed at the LENDER yard (boundary-safe:
            # it still returns to its own yard, it just services the zone).
            lender.count += 1
            logger.warning("secondary_depot_borrow",
                           extra={"depot_id": lender.home_depot,
                                  "borrowed_in": overloaded.zone_id})
    raise RuntimeError(f"Still infeasible after {max_borrows} borrow rounds.")


def _nearest_eligible_lender(plan, zone, coords):
    """Nearest yard that can_borrow and is franchised for the zone's jurisdiction."""
    home_xy = coords[zone.primary_depot]
    candidates = [
        vc for vc in plan.vehicles
        if vc.can_borrow and vc.home_depot != zone.primary_depot
    ]
    if not candidates:
        return None
    return min(candidates,
               key=lambda vc: haversine_km(*coords[vc.home_depot], *home_xy))

4. Cross-yard matrix contamination. If one shared distance matrix mixes intra-yard and inter-yard costs without the depots as explicit nodes, deadhead figures become meaningless. Keep every depot as its own node in the matrix and let the per-vehicle starts/ends do the binding — never approximate a second yard by offsetting costs. The clean coordinates that keep those matrix nodes correct come from the telematics sensor data ingestion pipeline before the matrix is ever built.

Integration Checklist

Complete every item before a multi-depot model reaches production dispatch:

• Every depot is an explicit node at the front of the node list; depot count and indices are fixed and versioned.
• FleetPlan validation passes — every vehicle home_depot and every zone primary_depot resolves to a real depot.
• The manager is built with per-vehicle starts and ends vectors, not a single scalar depot.
• starts, ends, and capacities are index-aligned per vehicle; ends == starts enforces same-yard return.
• Each zone carries a jurisdiction, and secondary-depot borrowing is gated on franchise or mutual-aid eligibility.
• The home-yard return unit test runs in CI and both start/end assertions pass.
• Every dispatched plan emits one yard_utilization record per depot with trucks_out, deadhead_km, and borrowed_in.
• trucks_out is checked against each yard’s parking_slots; overflow escalates to borrowing, never to a wrong-yard anchor.
• Orphaned zones are modeled as droppable disjunctions and surfaced, never silently skipped.

FAQ

How does OR-Tools actually represent multiple depots?

There is no separate multi-depot model. You pass two per-vehicle vectors — starts and ends — to RoutingIndexManager(num_nodes, num_vehicles, starts, ends) instead of a single depot index. Each vehicle then begins at starts[v] and finishes at ends[v]. Setting ends[v] == starts[v] for every vehicle forces same-yard return without any extra constraint object.

Why keep depots as the low node indices?

Keeping every depot contiguous at the front of the node list (indices 0..num_depots-1) makes the start/end vectors trivial to build and to audit — a reviewer can see at a glance that a home_depot of 2 is a real yard and not a service stop. It also keeps the distance matrix’s depot rows and columns in a predictable block, which matters when you read deadhead legs back out.

When should a truck borrow into another yard's zone instead of adding a reserve?

Borrow when an adjacent, franchise-eligible yard has spare capacity closer to the overloaded zone than any reserve you would otherwise provision. A borrowed truck still starts and ends at its own yard, so its deadhead is bounded and its franchise/manifest continuity stays intact. Add a fresh reserve only when no eligible lender exists within a reasonable deadhead.

How do I stop one shared matrix from contaminating per-yard costs?

Model every depot as its own node in the distance matrix and let the per-vehicle starts/ends do the binding. Never approximate a second yard by adding an offset to another yard’s costs — that blends the two and makes deadhead accounting meaningless. Correct per-yard deadhead requires each yard to be a distinct, real node.

What happens to a zone no yard can serve on a given day?

Model each of its stops as a droppable node with a large disjunction penalty so the solver returns a feasible plan that explicitly leaves those stops unserved, rather than returning None. The dropped stops are then surfaced for a secondary-depot borrow or a next-day carryover decision — an auditable outcome instead of a silent skip.

Up: VRP Route Optimization Algorithms

Related

• Assigning Vehicles to Depots in OR-Tools — the start/end index-vector mechanics in depth
• Capacity & Weight Limits — the per-vehicle payload dimension bound per yard
• Distance Matrix Construction — keeping each depot a distinct matrix node
• Time Window Constraints — arrival windows bound with the same per-vehicle indexing
• OR-Tools Implementation — dimension registration and solver configuration