A fleet where every vehicle is identical and everything starts from one depot is the textbook problem and almost never the real one. Real fleets have vans and artics with different capacities, two or three depots, and stops that would be nice to serve but are not obligatory. All three are expressible in OR-Tools without leaving the standard model, and this page covers how — as part of vehicle routing problem solvers and fleet dispatch within Routing API Automation & Fleet Integration.

The recurring surprise is that these constraints interact. Adding a depot can make a time-windowed problem easier; adding a vehicle can make it infeasible. Neither is a bug, and both are easier to reason about once the mechanism is visible.

When to use this approach

Model capacity explicitly when the fleet is heterogeneous or the goods are dense enough to bind. Model multiple depots when vehicles genuinely start from different places — not when they merely pass through several. Use disjunctions when the business would rather serve most stops well than all stops badly, which is most parcel and grocery work and almost no pharmaceutical or industrial work.

Skip capacity entirely when it never binds. A dimension the solver never has to respect still costs search time, and a fleet delivering documents has no meaningful weight constraint.

Two depots, three vehicle classes, one stop set A northern depot fields two vans and a southern depot fields a rigid truck. Their reachable territories overlap in the middle, so the solver chooses which depot serves the contested stops based on capacity and shift length rather than on distance alone. Overlapping territories are where multi-depot models earn their keep north depot — 2 vans, 800 kg each south depot — 1 rigid, 7 200 kg contested stops The solver assigns the contested stops on total cost, so a heavy pallet goes south even when the north depot is nearer.

Implementation

Multiple depots are expressed at construction time, through the index manager rather than through any depot-specific API.

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


def build_multi_depot(matrix, starts: list[int], ends: list[int]):
    """One start and one end index per vehicle — they need not be equal."""
    assert len(starts) == len(ends), "one start and one end per vehicle"
    manager = pywrapcp.RoutingIndexManager(len(matrix), len(starts), starts, ends)
    routing = pywrapcp.RoutingModel(manager)

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

    routing.SetArcCostEvaluatorOfAllVehicles(
        routing.RegisterTransitCallback(transit)
    )
    return manager, routing

Because starts and ends are independent lists, this same call covers one-way and relay operations — a vehicle that begins at a depot and ends at a driver’s home base is just an entry where starts[v] != ends[v].

Capacity is a dimension whose increment is the demand at the node being left:

# requires: ortools (pip install ortools)
def add_capacity_dimension(routing, manager, demands: list[int],
                           capacities: list[int], name: str = "Capacity") -> None:
    """Per-vehicle capacity; no slack, because load cannot be waited out."""
    def demand(from_index: int) -> int:
        return int(demands[manager.IndexToNode(from_index)])

    idx = routing.RegisterUnaryTransitCallback(demand)
    routing.AddDimensionWithVehicleCapacity(
        idx,
        0,            # slack
        capacities,   # one entry per vehicle
        True,         # start cumulative at zero
        name,
    )

Calling this twice with different demand lists and capacities gives independent weight and volume constraints over the same routes, which is the right model whenever the fleet carries mixed goods. The two rarely bind at the same time, and which one binds flips with the manifest.

Optional stops are priced rather than permitted:

# requires: ortools (pip install ortools)
def make_stops_optional(routing, manager, optional_nodes: list[int],
                        penalty: int) -> None:
    """A disjunction lets the solver drop a stop at a stated cost."""
    for node in optional_nodes:
        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

The penalty is what makes this useful and what makes it dangerous. Set it below the cost of serving the stop and the solver drops it every time; set it far above and the disjunction has no effect and you have paid search time for nothing. Several times the longest arc in the matrix is a defensible starting point, tuned against what a missed delivery actually costs.

Key parameters and tuning

Parameter Recommended value Notes
Capacity slack 0 Load cannot be shed by waiting; slack here hides over-capacity plans
Capacity dimensions 1–2 Weight and volume; a third is rarely binding and costs search time
Disjunction penalty 3–10× the longest arc Below the serving cost, everything is dropped; far above, it does nothing
Starts and ends explicit lists Equal values give the classic single-depot model as a special case
Empty-route handling allow Forcing every vehicle to be used produces worse plans on light days
Vehicle count slightly above need Too few is infeasible; far too many slows search without improving quality
Fixed vehicle cost set where fleets are hired Makes the solver prefer fewer vehicles when marginal use is expensive

Integration points

With the time dimension. Capacity and time interact through feasibility only, but the interaction is strong. Splitting a route to respect capacity adds a depot return, which consumes time and can push later stops outside their windows. If a model becomes infeasible after capacities are added, the binding constraint is usually time — see modelling time windows in OR-Tools VRP.

With the matrix. A multi-depot model needs every depot in the matrix, and depot-to-depot rows matter for relay operations. Omitting them is easy to do when the matrix is built from the stop manifest alone, and produces unreachable-pair costs on exactly the arcs a relay plan needs — see feeding a travel-time matrix into OR-Tools.

With EV constraints. Capacity and battery range are different dimensions, and modelling energy as a capacity dimension does not work because energy is recovered on descents. Solve the routing problem with weight and volume, then repair energy separately with inserting charging stops in route optimization.

Which capacity binds depends on the manifest Load is plotted along a route for two dimensions. On a bulky lightweight manifest the volume dimension reaches its capacity at the seventh stop while weight is still at a third of its limit, so volume is the binding constraint and a weight-only model would over-plan the route. Accumulated load along one route — bulky lightweight manifest capacity depot stop 7 stop 14 capacity limit, both dimensions volume — binds at stop 7 weight — never binds on this manifest A weight-only model would assign all fourteen stops to this vehicle and produce a plan the loader cannot physically execute. Which line binds flips with the manifest, which is why both dimensions belong in the model rather than whichever bound last week. Solve time as constraints accumulate A 120-stop distance-only problem solves in four seconds. Adding capacity takes it to nine, time windows to twenty-six, and a second depot with optional stops to thirty-eight — still within a typical dispatch budget. Effect of adding constraints to one 120-stop problem distance only solves in 4 s + capacity 9 s + time windows 26 s + two depots, disjunctions 38 s — still inside budget Time windows are the expensive constraint by a wide margin, because they interact with every other decision in the model. Add constraints one at a time when building a model; a solve that suddenly jumps from seconds to minutes identifies its own cause that way.

Validation checklist

  • Both capacity dimensions are re-derived from the plan. Sum demands along each route independently of the solver and compare against the vehicle’s limits. Trusting the solver’s own cumulative values hides mis-specified callbacks.
  • Every vehicle’s start and end appear in the matrix. A depot missing from the matrix shows up as an unreachable-pair cost on the arcs a relay plan needs, not as an error.
  • An empty route is legal. Confirm the model solves on a light day where one vehicle is not needed. If it does not, a depot window or a fixed cost is forcing use.
  • Disjunction penalties bind in the right direction. Halve the penalty and confirm more stops drop; double it and confirm fewer do. If neither changes the plan, the penalty is far outside the range where it matters.
  • Adding a depot does not silently reassign everything. Compare plans before and after. Large-scale reassignment is legitimate, but dispatchers need to know it happened rather than discover it in the field.