Vehicle Routing Problem Solvers and Fleet Dispatch

A routing engine answers “how long from A to B”. Dispatch needs the answer to a much harder question: given eighty stops, six vehicles, delivery windows, vehicle capacities and two depots, which vehicle visits which stops in what order. That is the vehicle routing problem, and it consumes the travel-time matrix that the rest of Routing API Automation & Fleet Integration exists to produce — specifically the output of async route matrix automation.

The solver is not the hard part. Google’s OR-Tools handles the search well and its API is stable. What goes wrong is the modelling: dimensions that quietly over-constrain, a matrix in the wrong units, or a search limit chosen by feel rather than by the dispatch deadline. This page covers the modelling, because that is where dispatch systems actually fail.

Prerequisites

Libraries. ortools for the solver and numpy for the matrix handling. Nothing else is required, though pandas makes the stop manifest easier to manage.

pip install ortools>=9.8 numpy>=1.24 pandas>=2.0

A travel-time matrix in integer seconds. Produced by the engine, not by straight-line distance, and square across every location including depots. Building it at scale is covered in chunking large origin-destination matrices.

A stop manifest with service times. The time spent at each stop is frequently larger than the driving time between adjacent stops in dense urban work, and omitting it produces plans that are impossible in practice.

A realistic vehicle definition. Capacity, start and end location, and a shift window. A fleet where every vehicle is identical is a special case, not the normal one.

Conceptual architecture

The solver’s model is built from four pieces that stack: an index manager translating between your location ids and the solver’s internal indices, a transit callback giving the cost of every arc, one or more dimensions accumulating a quantity along a route, and search parameters governing how long to look.

Dimensions are the concept worth understanding properly, because almost every modelling bug lives in one. A dimension is a quantity that accumulates as a vehicle traverses its route — load, elapsed time, distance — with a per-arc increment, a capacity, and a slack allowance. Time windows are expressed by constraining the time dimension’s value at each node. Capacity is a dimension whose increment is the demand at each stop and whose capacity is the vehicle’s.

The subtlety is slack. A time dimension with zero slack forbids waiting, which means a vehicle arriving early at a stop with a later window has no legal action and the whole problem becomes infeasible. Since arriving early is extremely common, a time dimension almost always needs generous slack.

Step-by-step implementation

1. Build the model skeleton

# requires: ortools, numpy (pip install ortools numpy)
import numpy as np
from ortools.constraint_solver import routing_enums_pb2, pywrapcp


def build_model(matrix: np.ndarray, num_vehicles: int, depot: int = 0):
    """Index manager, routing model, and the arc-cost callback."""
    assert matrix.dtype.kind in "iu", "matrix must be integer seconds"
    assert matrix.shape[0] == matrix.shape[1], "matrix must be square"

    manager = pywrapcp.RoutingIndexManager(len(matrix), num_vehicles, depot)
    routing = pywrapcp.RoutingModel(manager)

    def transit(from_index: int, to_index: int) -> int:
        # Solver indices are not location indices — always translate
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        return int(matrix[i][j])

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

IndexToNode is not optional decoration. The solver’s internal index space differs from your location indexing as soon as there is more than one vehicle, because start and end nodes are duplicated per vehicle. Indexing the matrix directly with a solver index appears to work on single-vehicle problems and produces silently wrong costs the moment a second vehicle is added.

2. Add the capacity dimension

# requires: ortools (pip install ortools)
def add_capacity(routing, manager, demands: list[int], capacities: list[int]) -> None:
    """Load accumulates at each stop and must never exceed vehicle capacity."""
    def demand(from_index: int) -> int:
        return demands[manager.IndexToNode(from_index)]

    demand_idx = routing.RegisterUnaryTransitCallback(demand)
    routing.AddDimensionWithVehicleCapacity(
        demand_idx,
        0,             # no slack — you cannot "wait" to shed load
        capacities,    # one capacity per vehicle
        True,          # start cumulative at zero
        "Capacity",
    )

Capacity takes zero slack because load is not something a vehicle can wait out. Time is the opposite case, which is why the two dimensions look similar and behave differently.

3. Add the time dimension with windows

# requires: ortools (pip install ortools)
def add_time_windows(routing, manager, matrix, service_s: list[int],
                     windows: list[tuple[int, int]], depot: int = 0,
                     horizon_s: int = 12 * 3600) -> None:
    """Elapsed time accumulates as travel plus service; windows constrain it."""
    def travel_plus_service(from_index: int, to_index: int) -> int:
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        # Service at the origin belongs to the arc leaving it
        return int(matrix[i][j]) + service_s[i]

    idx = routing.RegisterTransitCallback(travel_plus_service)
    routing.AddDimension(idx, horizon_s, horizon_s, False, "Time")
    time_dim = routing.GetDimensionOrDie("Time")

    for node, (open_s, close_s) in enumerate(windows):
        if node == depot:
            continue
        var = time_dim.CumulVar(manager.NodeToIndex(node))
        var.SetRange(open_s, close_s)

    # Depot windows are set per vehicle, on its own start and end index
    for v in range(routing.vehicles()):
        time_dim.CumulVar(routing.Start(v)).SetRange(*windows[depot])
        routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.Start(v)))
        routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.End(v)))

The second argument to AddDimension is the slack, and setting it to the horizon is what permits waiting. Setting it to zero is the single most common cause of an inexplicably infeasible model.

Note also that the depot’s window is applied to each vehicle’s start and end index rather than to the depot node. The depot node does not exist in the solver’s index space once vehicles have their own start and end nodes, so applying a range to it silently does nothing.

4. Choose search parameters

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


def search_params(seconds: int = 30):
    """A first solution, then guided local search until the deadline."""
    p = pywrapcp.DefaultRoutingSearchParameters()
    p.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
    )
    p.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    p.time_limit.FromSeconds(seconds)
    p.log_search = False
    return p

PARALLEL_CHEAPEST_INSERTION finds a feasible starting point quickly on time-windowed problems where the default savings heuristic often struggles. Guided local search is then what actually produces the quality — without a metaheuristic the solver returns the first solution and stops, which on a realistic problem is typically fifteen to thirty percent worse.

One modelling decision sits above all the parameters: what the objective actually optimises. OR-Tools minimises the sum of arc costs, so if the arc cost is travel time the solver minimises total fleet driving time — which is not the same as minimising the latest finish, nor the same as balancing work evenly between drivers. A plan that finishes one vehicle at 11:00 and another at 18:00 can have a lower total than one where both finish at 15:00, and the solver will prefer it.

Where balance matters, express it rather than hoping for it. A span cost on the time dimension penalises the difference between a vehicle’s start and end, which pushes the solver toward routes of similar length. A global span cost coefficient does the same across the fleet. Both are single calls on the dimension, and both change the character of the output far more than any amount of search tuning. Dispatchers notice imbalance immediately and rarely accept “it was cheaper” as an explanation, so it is worth deciding this deliberately at the point the model is built rather than after the first week of complaints.

Configuration reference

Production optimization and scaling

Cluster before solving. A single solve over four hundred stops is far slower and rarely better than partitioning geographically into four solves of one hundred. Real fleets are already partitioned by territory, and respecting that structure both speeds the solve and produces plans dispatchers recognise.

Reuse the matrix across solves. Travel times between the same stops do not change between the morning and afternoon runs unless the traffic layer did. Cache the matrix keyed on the location set plus a time bucket, as covered in caching and invalidating travel-time matrices, and the matrix stops being the dominant cost.

Warm-start from yesterday. Delivery manifests are highly correlated day to day. Supplying the previous day’s assignment as an initial solution gives guided local search a much better starting point than any construction heuristic, and it makes the plans stable — dispatchers distrust a system that reorders familiar routes for a two-minute gain.

Make the time limit a deadline, not a budget. Run the solve asynchronously with a hard wall-clock stop tied to when dispatch must go out. The solver returns its best solution so far, which is always usable.

Solve energy separately. Adding an energy dimension across the whole search is expensive and rarely worth it. Solve the routing problem, then repair the sparse violations with the insertion approach in inserting charging stops in route optimization.

Validation and testing

A VRP solution is easy to check and easy to trust wrongly. The checks that matter verify the plan against the same matrix the solver used, and then against reality.

# requires: numpy (pip install numpy)
import numpy as np


def audit_solution(routes: list[list[int]], matrix: np.ndarray,
                   demands: list[int], capacities: list[int],
                   windows: list[tuple[int, int]], service_s: list[int]) -> dict:
    """Re-derive every constraint from the plan rather than trusting the solver."""
    issues, total = [], 0
    for v, route in enumerate(routes):
        t, load = windows[route[0]][0], 0
        for a, b in zip(route, route[1:]):
            load += demands[a]
            if load > capacities[v]:
                issues.append(f"vehicle {v} over capacity at node {a}")
            t += int(matrix[a][b]) + service_s[a]
            total += int(matrix[a][b])
            open_s, close_s = windows[b]
            t = max(t, open_s)          # waiting is legal
            if t > close_s:
                issues.append(f"vehicle {v} misses window at node {b}")
    return {"total_travel_s": total, "issues": issues}

Re-deriving rather than reading the solver’s own dimension values is the point. If the model is mis-specified, the solver’s values are internally consistent and wrong; an independent audit against the raw matrix catches exactly that class of defect.

Troubleshooting

Related

• Async route matrix automation — computing the travel-time matrix this solver consumes
• Feeding a travel-time matrix into OR-Tools — unit handling, integer conversion, and the unreachable-pair problem
• Modelling time windows in OR-Tools VRP — slack, waiting, and depot windows in detail
• Capacity and multi-depot constraints in fleet dispatch — heterogeneous fleets, multiple starts and ends, and optional visits
• Inserting charging stops in route optimization — repairing energy violations after the routing problem is solved