Assigning Vehicles to Depots in OR-Tools

This page solves one specific failure: a truck garaged at the north yard is handed a route that starts at the south yard, because the solver was told there is one depot when the fleet actually spans several.

When a collection operation runs out of more than one yard, the single-depot default of a routing model quietly becomes wrong. Every vehicle in a plain RoutingIndexManager(num_nodes, num_vehicles, depot) is forced to leave from and return to the same node, so a mixed fleet dispersed across three garages gets routes that teleport trucks between yards they never sleep at. Assigning vehicles to depots in OR-Tools means giving the manager two parallel vectors — a start node and an end node for each vehicle — so the solver treats every truck as physically bound to its home yard. This is the fleet-partitioning primitive that the Multi-Depot Routing contract is built on, and it sits directly on top of the solver wiring covered in setting up Google OR-Tools for waste collection.

Environment & Data Prerequisites

The solver is ortools, and the fleet and yard records are modelled with pydantic so a malformed input is rejected before it ever reaches the routing model. pytest is used only for verification.

python -m pip install \
  ortools==9.11.4210 \
  pydantic==2.9.2 \
  pytest==8.2.0

The model reasons over two typed inputs: a list of yards and a list of vehicles. Node indexing is the load-bearing convention — yards occupy the first rows of the distance matrix, and collection stops follow, so a yard’s node is also its matrix row.

Field	Unit / type	Range / rule
`yards[].yard_id`	str	stable, unique per garage
`yards[].node`	int	0-based matrix row; yards occupy rows `0 … len(yards)-1`
`vehicles[].vehicle_id`	str	unique per truck
`vehicles[].home_yard`	str	must equal some `yards[].yard_id`
`vehicles[].capacity_kg`	int	> 0; hopper payload ceiling
`demands[node]`	int, kg	0 at every yard node, > 0 at stops

The single rule that prevents most multi-depot bugs: starts and ends are vehicle-indexed, not yard-indexed. Each vector has exactly num_vehicles entries, and entry v is the matrix node vehicle v departs from and returns to.

Step-by-Step Implementation

Step 1 — Type the fleet and yard inputs

Model the raw configuration with Pydantic so a vehicle pointing at a yard that does not exist fails loudly at parse time rather than as a cryptic index error deep inside the solver.

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


class Yard(BaseModel):
    yard_id: str
    node: int  # 0-based row in the distance matrix


class Vehicle(BaseModel):
    vehicle_id: str
    home_yard: str
    capacity_kg: int

    @field_validator("capacity_kg")
    @classmethod
    def _positive_capacity(cls, v: int) -> int:
        if v <= 0:
            raise ValueError("capacity_kg must be positive")
        return v


class FleetPlan(BaseModel):
    yards: list[Yard]
    vehicles: list[Vehicle]

    @model_validator(mode="after")
    def _yards_resolve(self) -> "FleetPlan":
        known = {y.yard_id for y in self.yards}
        for veh in self.vehicles:
            if veh.home_yard not in known:
                raise ValueError(f"{veh.vehicle_id} home_yard '{veh.home_yard}' is not a defined yard")
        return self

Step 2 — Build the per-vehicle starts and ends vectors

This is the core of depot binding. Resolve each vehicle’s home_yard string to its yard node, in vehicle order, into two aligned lists. Because a truck sleeps where it garages, starts and ends are identical here — but keeping them as separate vectors is what lets you later model a truck that ends its shift at a transfer station instead of its yard.

def build_depot_vectors(plan: FleetPlan) -> tuple[list[int], list[int]]:
    node_of_yard = {y.yard_id: y.node for y in plan.yards}
    starts = [node_of_yard[v.home_yard] for v in plan.vehicles]
    ends = [node_of_yard[v.home_yard] for v in plan.vehicles]
    assert len(starts) == len(ends) == len(plan.vehicles)
    return starts, ends

Step 3 — Construct the manager and routing model

The multi-depot overload of RoutingIndexManager takes (num_nodes, num_vehicles, starts, ends). Passing the two vectors instead of a single depot integer is the entire difference between a single-yard and a multi-yard model.

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def build_model(plan: FleetPlan, matrix: list[list[int]]):
    num_nodes = len(matrix)
    num_vehicles = len(plan.vehicles)
    starts, ends = build_depot_vectors(plan)

    manager = pywrapcp.RoutingIndexManager(num_nodes, num_vehicles, starts, ends)
    routing = pywrapcp.RoutingModel(manager)

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

    transit_idx = routing.RegisterTransitCallback(distance_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)
    return manager, routing

Step 4 — Register capacity as a dimension

Each truck’s hopper is finite, so demand is registered as a capacity dimension with a per-vehicle limit. This is the same capacity primitive covered in handling truck capacity constraints in Python; here it also proves a yard is not over-subscribed by the trucks bound to it.

def add_capacity(routing, manager, plan: FleetPlan, demands: list[int]) -> None:
    def demand_cb(from_index: int) -> int:
        return demands[manager.IndexToNode(from_index)]

    demand_idx = routing.RegisterUnaryTransitCallback(demand_cb)
    routing.AddDimensionWithVehicleCapacity(
        demand_idx,
        0,                                       # zero slack; no in-route buffer
        [v.capacity_kg for v in plan.vehicles],  # per-vehicle ceilings, vehicle-indexed
        True,                                    # start cumul at zero at each yard
        "Load",
    )

Step 5 — Solve and serialize the per-yard assignment

Solve with guided local search, then walk each vehicle’s route back through the manager to confirm — from the solution itself — that it opened and closed at its bound yard.

def solve_and_assign(plan: FleetPlan, matrix: list[list[int]], demands: list[int]) -> dict:
    manager, routing = build_model(plan, matrix)
    add_capacity(routing, manager, plan, demands)

    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(5)

    solution = routing.SolveWithParameters(params)
    if solution is None:
        raise RuntimeError("no feasible multi-depot assignment found")

    node_to_yard = {y.node: y.yard_id for y in plan.yards}
    bindings = []
    for v, veh in enumerate(plan.vehicles):
        start_node = manager.IndexToNode(routing.Start(v))
        end_index = routing.End(v)
        end_node = manager.IndexToNode(end_index)
        route, idx = [], routing.Start(v)
        while not routing.IsEnd(idx):
            route.append(manager.IndexToNode(idx))
            idx = solution.Value(routing.NextVar(idx))
        route.append(end_node)
        bindings.append({
            "vehicle_id": veh.vehicle_id,
            "bound_yard": veh.home_yard,
            "start_node": start_node,
            "end_node": end_node,
            "start_yard": node_to_yard.get(start_node),
            "end_yard": node_to_yard.get(end_node),
            "route_nodes": route,
        })
    return {"objective_m": solution.ObjectiveValue(), "assignments": bindings}

Compliance Output

The assignment serializes to one audit record per solve. Its purpose is not routing efficiency but accountability: it proves, from the solved plan, that every truck was dispatched from and returned to the yard it is licensed and insured to operate from.

{
  "objective_m": 48210,
  "assignments": [
    {
      "vehicle_id": "T-101",
      "bound_yard": "north-yard",
      "start_node": 0,
      "end_node": 0,
      "start_yard": "north-yard",
      "end_yard": "north-yard",
      "route_nodes": [0, 4, 6, 3, 0]
    },
    {
      "vehicle_id": "T-204",
      "bound_yard": "south-yard",
      "start_node": 1,
      "end_node": 1,
      "start_yard": "south-yard",
      "end_yard": "south-yard",
      "route_nodes": [1, 15, 18, 1]
    }
  ]
}

Each field earns its place in the audit trail:

bound_yard — the yard the vehicle was declared to belong to in the input plan; it is the expectation the record is checked against.
start_yard / end_yard — the yard resolved from the solved route’s first and last nodes. When these match bound_yard, the record is self-proving: the plan honoured the binding. A mismatch is a hard compliance failure, not a warning.
start_node / end_node — the raw matrix rows, retained so the record can be re-derived against a re-hashed distance matrix without re-solving.
route_nodes — the ordered node sequence, which downstream DOT/FMCSA rule mapping uses to attribute drive time to the correct terminal for hours-of-service accounting, since a driver’s shift legally begins at the yard they report to.

Because bound_yard and the resolved start_yard/end_yard are stored side by side, an auditor can verify depot compliance from the record alone — no re-solve, and no trust in the solver’s internals, required.

Verification

The test proves the property that matters: every vehicle starts and ends at exactly its assigned yard, and a vehicle pointed at a non-existent yard is rejected before solving.

import pytest
from pydantic import ValidationError


def _fixture() -> tuple[FleetPlan, list[list[int]], list[int]]:
    plan = FleetPlan(
        yards=[Yard(yard_id="north-yard", node=0), Yard(yard_id="south-yard", node=1)],
        vehicles=[
            Vehicle(vehicle_id="T-101", home_yard="north-yard", capacity_kg=9000),
            Vehicle(vehicle_id="T-204", home_yard="south-yard", capacity_kg=9000),
        ],
    )
    # nodes: 0=north yard, 1=south yard, 2..4 = stops
    matrix = [
        [0, 30, 12, 18, 20],
        [30, 0, 25, 14, 16],
        [12, 25, 0, 10, 11],
        [18, 14, 10, 0, 9],
        [20, 16, 11, 9, 0],
    ]
    demands = [0, 0, 800, 600, 700]
    return plan, matrix, demands


def test_each_vehicle_starts_and_ends_at_its_yard():
    plan, matrix, demands = _fixture()
    result = solve_and_assign(plan, matrix, demands)
    for a in result["assignments"]:
        assert a["start_yard"] == a["bound_yard"]
        assert a["end_yard"] == a["bound_yard"]
        assert a["route_nodes"][0] == a["start_node"]
        assert a["route_nodes"][-1] == a["end_node"]


def test_unknown_home_yard_is_rejected():
    with pytest.raises(ValidationError):
        FleetPlan(
            yards=[Yard(yard_id="north-yard", node=0)],
            vehicles=[Vehicle(vehicle_id="T-999", home_yard="west-yard", capacity_kg=9000)],
        )

Common Errors

Check failed: starts.size() == vehicles (2 vs 3) — the starts (or ends) vector length does not equal num_vehicles. Root cause: building the vector from the yards list instead of the vehicles list, so a two-yard fleet of three trucks produces two starts. Fix: derive both vectors by iterating plan.vehicles in order, exactly as build_depot_vectors does, and assert len(starts) == len(ends) == num_vehicles before constructing the manager.

Check failed: 0 <= node && node < nodes_ (or an IndexError resolving a yard node) — a depot vector holds a node that is not a valid matrix row. Root cause: a yard node numbered past the matrix, usually because stops were placed before yards so the yard indices drifted. Fix: pin yards to the first rows of the matrix (0 … len(yards)-1) and keep demands[node] == 0 for every yard node.

RuntimeError: no feasible multi-depot assignment found — the solver returns None. Root cause: one yard’s trucks cannot absorb the demand assigned to their side, so the capacity dimension is infeasible for that partition even though total fleet capacity looks sufficient in aggregate. Fix: check per-yard load balance before solving — sum the demand reachable only through each yard against the summed capacity_kg of the trucks bound to it — and rebalance vehicles across yards rather than raising the global time limit.

FAQ

Why keep starts and ends as two vectors if they are identical for a home yard?

Because they are not always identical. A truck may garage at one yard but end its shift by tipping at a transfer station, or a night-shift vehicle may start where the day shift parked it. Modelling start and end as separate vectors from the outset means that change is a one-line edit to ends, not a restructuring of the manager.

Can two vehicles share the same start node?

Yes. Multiple trucks bound to the same yard simply repeat that yard’s node in the starts vector. The vector is vehicle-indexed, so a five-truck north yard contributes the same node five times, once per vehicle, and the solver treats them as independent routes that happen to share an origin.

Up: Multi-Depot Routing

Multi-Depot Routing — the fleet-partitioning contract this depot binding implements.
Setting up Google OR-Tools for Waste Collection — the base solver wiring the manager and model sit on.
Handling Truck Capacity Constraints in Python — the capacity dimension registered in Step 4.
Distance Matrix Construction — where the matrix whose first rows are the yards comes from.