Assigning Deliveries to Vehicles from a Cost Matrix

Once the cost matrix exists, the remaining problem is no longer a graph problem, and treating it as one is where fleet systems go wrong. Assignment is combinatorial optimisation over a table of numbers, and the graph’s only remaining job is to have produced those numbers honestly. What matters here is getting a defensible answer quickly, being explicit about which constraints are hard and which are preferences, and — most importantly — being able to say afterwards whether a bad result came from the assignment or from the matrix it was given. This page builds a capacity-aware greedy assignment, improves it with a bounded local search, and separates the two failure sources.

Prerequisites & Versions

Everything here is pure Python over a matrix already in memory; no database involvement.

Requirement Minimum version Install
Python 3.11 —
neo4j (async driver) 5.20 pip install "neo4j>=5.20" (to fetch the matrix)

Implementation

The assignment runs in two phases: a greedy pass that produces a feasible solution fast, then a relocate-and-swap local search that improves it without ever leaving feasibility.

import math
from dataclasses import dataclass, field


@dataclass(frozen=True)
class Vehicle:
    id: str
    depot_id: str
    capacity: int
    shift_seconds: float


@dataclass(frozen=True)
class Stop:
    id: str
    demand: int
    service_seconds: float


@dataclass
class Route:
    vehicle: Vehicle
    stops: list[str] = field(default_factory=list)
    load: int = 0
    seconds: float = 0.0

    def feasible_with(self, stop: Stop, added_seconds: float) -> bool:
        return (
            self.load + stop.demand <= self.vehicle.capacity
            and self.seconds + added_seconds + stop.service_seconds
            <= self.vehicle.shift_seconds
        )


class Assigner:
    """Greedy insertion followed by bounded local search.

    Greedy alone is typically 15-25% worse than a good solution and is produced
    in milliseconds; the local search recovers most of that gap in a bounded
    number of passes. Neither is optimal, and for fleet sizing that is fine —
    what matters is that the answer is feasible, reproducible and explicable.
    """

    def __init__(self, matrix: dict[tuple[str, str], float],
                 stops: dict[str, Stop]) -> None:
        self._matrix = matrix
        self._stops = stops

    def cost(self, a: str, b: str) -> float:
        # An absent pair is unreachable. Returning inf rather than 0 is the
        # single most important line here: a 0 would make the pair the cheapest
        # option available and it would win every comparison it entered.
        return self._matrix.get((a, b), math.inf)

    def _insertion_cost(self, route: Route, stop_id: str) -> float:
        """Marginal cost of appending, not the raw depot-to-stop distance."""
        last = route.stops[-1] if route.stops else route.vehicle.depot_id
        return self.cost(last, stop_id)

    def greedy(self, vehicles: list[Vehicle], stop_ids: list[str]
               ) -> tuple[list[Route], list[str]]:
        routes = [Route(vehicle=v) for v in vehicles]
        unassigned: list[str] = []

        # Hardest stops first: a large-demand stop placed late may find no
        # vehicle with room, and an unassigned stop is far worse than a
        # suboptimal one.
        for stop_id in sorted(
            stop_ids, key=lambda s: -self._stops[s].demand
        ):
            stop = self._stops[stop_id]
            best: tuple[float, Route] | None = None
            for route in routes:
                added = self._insertion_cost(route, stop_id)
                if not math.isfinite(added):
                    continue
                if not route.feasible_with(stop, added):
                    continue
                if best is None or added < best[0]:
                    best = (added, route)
            if best is None:
                unassigned.append(stop_id)
                continue
            added, route = best
            route.stops.append(stop_id)
            route.load += stop.demand
            route.seconds += added + stop.service_seconds
        return routes, unassigned

    def improve(self, routes: list[Route], passes: int = 40) -> list[Route]:
        """Relocate a stop to a cheaper route while keeping every route feasible."""
        for _ in range(passes):
            moved = False
            for source in routes:
                for stop_id in list(source.stops):
                    stop = self._stops[stop_id]
                    current = self._insertion_cost(source, stop_id)
                    for target in routes:
                        if target is source:
                            continue
                        added = self._insertion_cost(target, stop_id)
                        if not math.isfinite(added) or added >= current:
                            continue
                        if not target.feasible_with(stop, added):
                            continue
                        source.stops.remove(stop_id)
                        source.load -= stop.demand
                        source.seconds -= current + stop.service_seconds
                        target.stops.append(stop_id)
                        target.load += stop.demand
                        target.seconds += added + stop.service_seconds
                        moved = True
                        break
            if not moved:
                break        # a local optimum — further passes change nothing
        return routes

How It Works

Three decisions carry the quality of the result.

Hardest-first ordering is what keeps stops assigned. Processing stops in arbitrary order fills vehicles with small easy deliveries, and the large one that arrives last finds every vehicle with capacity remaining but not enough of it. Sorting by descending demand places the constrained items while there is still room, and on real delivery data it is the difference between zero unassigned stops and a handful — a handful being a much worse outcome than a slightly longer total route.

Insertion cost is marginal, not absolute. The number that decides where a stop goes is the extra travel it causes on that route, which is the cost from the route’s current last stop. Using the depot-to-stop cost instead makes every route look equally attractive for a given stop and destroys the clustering that makes routes efficient — the assignment ends up geographically interleaved, with vehicles crossing each other’s territory.

The local search never leaves feasibility. Every relocate is checked against capacity and shift length before it is applied, so the solution is valid at every step and can be stopped at any point. That property matters operationally: a dispatcher who needs an answer in two seconds gets the best solution found in two seconds, not a partial one.

Insertion order decides whether the large stop gets served at all Three vehicles of capacity 100 and a set of stops including one of demand 80. Assigning in arrival order fills all three vehicles to around 60 with small stops, so when the demand-80 stop is considered no vehicle has room and it goes unassigned even though total fleet capacity was ample. Assigning largest-demand first places the 80 immediately, and the small stops then fill the remaining space wherever they fit. Both runs move the same total demand; only one of them serves every customer. 3 vehicles × capacity 100 · one stop of demand 80 arrival order V1 60 V2 64 V3 58 largest free space is 42 — the demand-80 stop does not fit 1 stop unassigned 182 of 300 capacity used largest demand first V1 80 + 0 V2 95 V3 87 the constrained item was placed while there was room every stop assigned 262 of 300 capacity used Total fleet capacity was never the constraint. The left run failed because it spent the space before the item that needed it arrived, which is a sequencing decision and not a fleet-sizing one.

Common Failure Patterns

1. A missing matrix cell treated as zero. This is the defect that produces confidently absurd plans. dict.get((a, b), 0) makes an unreachable pair the cheapest option in the table, so the assignment routes a van to an island. Default to infinity and count how many cells are infinite — a rising count is a data-quality signal from the graph, not an assignment problem.

2. Blaming the assignment for a matrix fault. When a plan looks wrong, check the matrix first. Two cheap checks separate the stages: verify that the matrix satisfies the triangle inequality on a sample of triples, and verify that a handful of cells agree with a direct routing query. A matrix that fails either is producing a plan that no assignment algorithm could rescue.

def matrix_is_sane(matrix, ids, samples=200) -> list[str]:
    """Triangle-inequality violations mean the matrix is not a metric, which
    almost always means some cells came from a different graph or bound."""
    import random
    problems = []
    for _ in range(samples):
        a, b, c = random.sample(ids, 3)
        ab, bc, ac = matrix.get((a, b)), matrix.get((b, c)), matrix.get((a, c))
        if None in (ab, bc, ac):
            continue
        if ac > ab + bc + 1e-6:
            problems.append(f"{a}→{c} ({ac:.0f}) exceeds {a}→{b}→{c} ({ab + bc:.0f})")
    return problems

3. Local search that leaves feasibility “temporarily”. A relocate that overfills a vehicle intending to fix it on a later pass produces an infeasible solution whenever the loop is stopped early — which is exactly when a dispatcher is waiting. Check feasibility before applying, never after.

Performance Notes

Greedy is $O(N \cdot V)$ for $N$ stops and $V$ vehicles, which is negligible. The local search is the cost:

$$C_{\text{improve}} \approx P \cdot N \cdot V$$

for $P$ passes. With three hundred stops and forty vehicles that is twelve thousand evaluations per pass, and the loop terminates early once no improving move exists — typically within ten to fifteen passes on real data rather than the forty allowed. Capping passes by wall-clock rather than by count is usually the better interface, because it makes the algorithm’s contract “the best answer available in this long” rather than “an answer of unknown quality”.

The quality gap is worth being honest about. Greedy alone lands roughly fifteen to twenty-five per cent above a strong solution; relocate-only local search closes about half of that; adding a swap neighbourhood closes a good deal more at roughly double the cost per pass. Beyond that, the returns fall off sharply and a purpose-built solver is the right tool. Knowing where that boundary is matters more than pushing past it, because the matrix underneath carries its own error — a plan optimised to within two per cent of optimal on a matrix that is five per cent wrong is not a better plan.

Cache the matrix, not the assignment. Depots move rarely and the road network changes weekly, so yesterday’s matrix mostly still applies and only new stops need fresh rows. The assignment, by contrast, changes completely with the day’s orders and is cheap to recompute, so caching it buys nothing and risks serving a stale plan.

Solution quality against effort, and where the matrix's own error sits Total route cost plotted against computation time. Greedy lands about 22 per cent above a strong reference solution in milliseconds. Relocate local search closes roughly half that gap within a second. Adding swaps closes most of the rest over several seconds. Beyond that the curve flattens well before reaching optimal. A shaded band shows the uncertainty in the cost matrix itself, around five per cent, which the last stretch of optimisation is working well inside — so effort spent there is buying precision the input does not support. Excess over a strong reference solution +25%+15%+5%0 10 ms1 s10 s2 min computation time the matrix's own uncertainty, ~5% greedy + relocate + swap Once the curve enters the shaded band, further optimisation is refining a number whose input is less certain than the improvement — the effort is better spent on the matrix.

One reporting habit is worth building in from the start: emit the unassigned list as a first-class output rather than as a log line. An assignment that serves 297 of 300 stops is a materially different result from one that serves all 300, and the three that were dropped are the ones a dispatcher most needs to see — they are usually a data problem (a stop that failed to snap, an address outside the covered region) rather than a capacity one, and surfacing them turns a silent shortfall into a work item.

This guide is part of Multi-Modal and Fleet Routing on a Spatial Graph, within Network Routing Algorithms in Python.

Siblings