CP-SAT vs. Guided Local Search for Large Waste Fleets

This page answers one recurring architecture decision: when a municipal collection network outgrows a toy model, do you formulate it for the OR-Tools CP-SAT solver and pay for an optimality proof, or hand it to the Routing library’s guided local search and buy scale and speed instead?

Both engines ship in the same ortools wheel, both are used across the OR-Tools Implementation sub-system, and both can return a legal plan for the constraint architecture described in VRP Route Optimization Algorithms. They are not interchangeable. CP-SAT is a constraint-integer-programming solver that will prove a plan is the cheapest one possible — but its arc-variable model grows quadratically and stalls on dense networks well before a metropolitan fleet size. Guided local search (GLS) is a metaheuristic inside the Routing library that never proves anything, yet it holds thousands of stops in memory and improves a feasible plan under a fixed time budget. Picking wrong is expensive in both directions: a CP-SAT model that never returns leaves dispatch with no plan, and a GLS run with no stopping criterion pins a worker forever.

Environment & Data Prerequisites

Both solvers come from the same pinned install, so there is nothing extra to add for CP-SAT:

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

The comparison runs on one shared instance — a depot plus eight bins served by two 700 kg trucks — so the two engines see identical geometry and demand. Weight is carried in whole kilograms and distance in whole metres as int, because CP-SAT rejects floating-point coefficients outright and the Routing library’s integer arithmetic drifts otherwise.

The decision at a glance

The short rule: reach for CP-SAT when the instance is small enough to prove and the proof has value — a contested cross-jurisdictional zone, a weekly master plan, a sub-problem you will reuse thousands of times. Reach for GLS for everything that must return a good plan now at fleet scale. The rest of this page runs both on the same eight-bin instance so the trade-off is concrete rather than asserted.

Step-by-Step Implementation

Step 1 — One shared instance and distance matrix

Both solvers must reason over identical numbers or the comparison proves nothing. The matrix uses an equirectangular approximation with cosine-latitude correction — accurate for a dense city grid and integer-valued for both engines.

from __future__ import annotations
from dataclasses import dataclass
import math
import time


@dataclass(frozen=True)
class Stop:
    stop_id: str
    lat: float
    lon: float
    demand_kg: int


FLEET_INSTANCE: list[Stop] = [
    Stop("DEPOT",  40.7128, -74.0060,   0),
    Stop("BIN_01", 40.7180, -74.0020, 120),
    Stop("BIN_02", 40.7205, -74.0110, 140),
    Stop("BIN_03", 40.7090, -74.0150, 160),
    Stop("BIN_04", 40.7060, -74.0030, 110),
    Stop("BIN_05", 40.7220, -73.9950, 180),
    Stop("BIN_06", 40.7040, -74.0120, 130),
    Stop("BIN_07", 40.7155, -73.9980, 150),
    Stop("BIN_08", 40.7100, -74.0075, 170),
]
NUM_VEHICLES = 2
CAPACITY_KG = 700


def build_distance_matrix(stops: list[Stop]) -> list[list[int]]:
    n = len(stops)
    d = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            mean_lat = math.radians((stops[i].lat + stops[j].lat) / 2)
            dlat = stops[i].lat - stops[j].lat
            dlon = (stops[i].lon - stops[j].lon) * math.cos(mean_lat)
            d[i][j] = int(111_320 * math.hypot(dlat, dlon))
    return d

Step 2 — The guided local search solve

GLS lives in the Routing library. You register the arc-cost callback, attach a zero-slack capacity dimension exactly as the Capacity & Weight Limits sub-system documents, then set the GUIDED_LOCAL_SEARCH metaheuristic. The critical parameter is the stopping criterion: a time_limit bounds wall clock, and a solution_limit makes the run reproducible across machines of differing speed because GLS itself carries no random seed — it is a deterministic descent that only varies in how far it gets before you stop it.

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def solve_gls(stops, dist, num_vehicles, capacity,
              time_limit_s: int = 5) -> dict | None:
    n = len(stops)
    manager = pywrapcp.RoutingIndexManager(n, num_vehicles, 0)
    routing = pywrapcp.RoutingModel(manager)

    transit = routing.RegisterTransitCallback(
        lambda a, b: dist[manager.IndexToNode(a)][manager.IndexToNode(b)]
    )
    routing.SetArcCostEvaluatorOfAllVehicles(transit)

    demands = [s.demand_kg for s in stops]
    demand_cb = routing.RegisterUnaryTransitCallback(
        lambda a: demands[manager.IndexToNode(a)]
    )
    routing.AddDimensionWithVehicleCapacity(
        demand_cb, 0, [capacity] * num_vehicles, True, "Payload"
    )

    p = pywrapcp.DefaultRoutingSearchParameters()
    p.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    p.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    p.time_limit.FromSeconds(time_limit_s)
    p.solution_limit = 200          # deterministic stopping criterion

    t0 = time.perf_counter()
    sol = routing.SolveWithParameters(p)
    elapsed = time.perf_counter() - t0
    if sol is None:
        return None

    routes = []
    for v in range(num_vehicles):
        idx, r = routing.Start(v), []
        while not routing.IsEnd(idx):
            r.append(stops[manager.IndexToNode(idx)].stop_id)
            idx = sol.Value(routing.NextVar(idx))
        routes.append(r)
    return {"engine": "gls", "objective": sol.ObjectiveValue(),
            "routes": routes, "solve_s": round(elapsed, 3)}

Step 3 — The CP-SAT formulation on the same instance

CP-SAT has no routing dimensions; you model the vehicle routing problem yourself with arc booleans. Each customer gets exactly one incoming and one outgoing arc, the depot emits and absorbs one arc per vehicle, and a per-node load variable both enforces capacity and eliminates subtours: any cycle that skips the depot would need a strictly increasing load around it, which is impossible. The objective is the summed arc distance — the same quantity GLS minimizes.

from ortools.sat.python import cp_model


def solve_cpsat(stops, dist, num_vehicles, capacity,
                time_limit_s: int = 5, workers: int = 8) -> dict | None:
    n, depot = len(stops), 0
    model = cp_model.CpModel()

    x = {(i, j): model.NewBoolVar(f"x_{i}_{j}")
         for i in range(n) for j in range(n) if i != j}

    for j in range(1, n):                       # each customer: one in, one out
        model.AddExactlyOne(x[i, j] for i in range(n) if i != j)
        model.AddExactlyOne(x[j, i] for i in range(n) if i != j)
    model.Add(sum(x[depot, j] for j in range(1, n)) == num_vehicles)
    model.Add(sum(x[i, depot] for i in range(1, n)) == num_vehicles)

    load = [model.NewIntVar(0, capacity, f"load_{i}") for i in range(n)]
    model.Add(load[depot] == 0)
    for i in range(1, n):
        model.Add(load[i] >= stops[i].demand_kg)
    for i in range(n):                          # MTZ load lift: capacity + subtour cut
        for j in range(1, n):
            if i != j:
                model.Add(load[j] >= load[i] + stops[j].demand_kg).OnlyEnforceIf(x[i, j])

    model.Minimize(sum(dist[i][j] * x[i, j]
                       for i in range(n) for j in range(n) if i != j))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit_s
    solver.parameters.num_search_workers = workers
    solver.parameters.random_seed = 42
    t0 = time.perf_counter()
    status = solver.Solve(model)
    elapsed = time.perf_counter() - t0
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None

    succ = {i: j for i in range(n) for j in range(n)
            if i != j and solver.Value(x[i, j])}
    routes = []
    for s in (j for j in range(1, n) if solver.Value(x[depot, j])):
        r, cur = ["DEPOT"], s
        while cur != depot:
            r.append(stops[cur].stop_id)
            cur = succ[cur]
        routes.append(r)
    return {"engine": "cpsat", "objective": int(solver.ObjectiveValue()),
            "status": solver.StatusName(status), "routes": routes,
            "solve_s": round(elapsed, 3)}

Step 4 — Run both and compare

Run the two engines on the identical matrix and print the objective and wall-clock cost side by side.

if __name__ == "__main__":
    dist = build_distance_matrix(FLEET_INSTANCE)
    gls = solve_gls(FLEET_INSTANCE, dist, NUM_VEHICLES, CAPACITY_KG)
    cpsat = solve_cpsat(FLEET_INSTANCE, dist, NUM_VEHICLES, CAPACITY_KG)
    for plan in (gls, cpsat):
        print(plan["engine"], "obj", plan["objective"], "t", plan["solve_s"], "s")

Output & Interpretation

On this eight-bin instance the two engines return the same total distance — CP-SAT proves it is the optimum, GLS reaches it without knowing it did:

{
  "gls":   {"objective": 7184, "solve_s": 0.069, "proof": "none"},
  "cpsat": {"objective": 7184, "status": "OPTIMAL", "solve_s": 0.011},
  "verdict": "identical objective; CP-SAT certifies 7184 is minimal, GLS matches without a certificate"
}

The interpretation is the whole point. At this size CP-SAT is both faster and stronger: it returns a proven 7184 in milliseconds, so nothing GLS can do beats it. That relationship inverts as the network grows — the CP-SAT model holds one boolean per ordered pair, so at a few hundred stops the arc count explodes and the solver spends its whole budget without closing the optimality gap, while GLS keeps improving a feasible plan in bounded memory. This is exactly why full-fleet daily dispatch runs on GLS and why CP-SAT is reserved for small, high-value sub-problems — a proof is only worth having when you can actually get it. The objective each engine reports feeds the same hashed compliance manifest, so a proof: OPTIMAL record and a proof: none record are distinguishable to an auditor reconciling plan cost against Dynamic Threshold Tuning history. Which engine even builds the matrix is a separate axis, covered in OR-Tools vs. OSRM vs. Valhalla for Matrix Precomputation.

Verification

The tests prove three properties that make the comparison trustworthy: both engines return a feasible plan that visits every bin exactly once, and GLS is reproducible under a fixed stopping criterion.

def _served(plan) -> set[str]:
    return {s for r in plan["routes"] for s in r if s != "DEPOT"}


ALL_BINS = {s.stop_id for s in FLEET_INSTANCE if s.stop_id != "DEPOT"}


def test_both_engines_return_feasible_plans():
    dist = build_distance_matrix(FLEET_INSTANCE)
    gls = solve_gls(FLEET_INSTANCE, dist, NUM_VEHICLES, CAPACITY_KG)
    cpsat = solve_cpsat(FLEET_INSTANCE, dist, NUM_VEHICLES, CAPACITY_KG)
    assert gls is not None and cpsat is not None
    assert _served(gls) == ALL_BINS      # every bin served once
    assert _served(cpsat) == ALL_BINS
    assert cpsat["status"] == "OPTIMAL"  # small instance is provable


def test_gls_is_deterministic_under_fixed_limit():
    dist = build_distance_matrix(FLEET_INSTANCE)
    first = solve_gls(FLEET_INSTANCE, dist, NUM_VEHICLES, CAPACITY_KG)
    second = solve_gls(FLEET_INSTANCE, dist, NUM_VEHICLES, CAPACITY_KG)
    assert first["objective"] == second["objective"]
    assert first["routes"] == second["routes"]

Common Errors

CP-SAT returns UNKNOWN and solve_cpsat yields None. Root cause: the arc model is too large for the time budget — at a few hundred stops the $n^2$ booleans and the MTZ load lifts overwhelm the solver, so it never reaches OPTIMAL or even FEASIBLE before max_time_in_seconds. Fix: keep CP-SAT for sub-problems under a couple hundred nodes, raise max_time_in_seconds only if the instance is genuinely provable, and route full-fleet dispatch through GLS instead of forcing a proof the model cannot deliver.

A GLS worker hangs and never returns. Root cause: no stopping criterion — with neither time_limit nor solution_limit set, guided local search keeps searching for improvements indefinitely and pins the process. Fix: always set p.time_limit.FromSeconds(...), and add p.solution_limit when you need the run reproducible across machines, exactly as Step 2 does. The first-solution result is a valid fallback if refinement has not converged.

TypeError: NotImplemented / Not an integer when building the CP-SAT objective. Root cause: a non-integer cost in the matrix — a float distance or a numpy.float64 weight — passed as a coefficient. CP-SAT is an integer solver and rejects fractional coefficients, unlike GLS which silently truncates them. Fix: cast every distance and demand to int at matrix-build time (as build_distance_matrix does with int(...)), carrying metres and kilograms as whole units rather than floats.

FAQ

If CP-SAT is faster and proves optimality here, why ever use GLS?

Because this instance is tiny. CP-SAT’s advantage evaporates as the network grows: its model has one boolean per ordered node pair, so memory and search both scale with the square of the stop count and it stalls without closing the gap at a few hundred stops. GLS holds thousands of stops and keeps improving a feasible plan under a fixed budget. Use CP-SAT where a proof is attainable and valuable; use GLS where you need a good plan at fleet scale on a deadline.

Is CP-SAT deterministic across runs?

Only conditionally. Run to a proven optimum, the objective is unique and reproducible. On a timeout with several search workers, CP-SAT explores in parallel and the returned incumbent can differ between runs. Set num_search_workers = 1 for a fully deterministic search, or accept that only the proven-optimal objective — not a truncated incumbent — is reproducible.

Does guided local search have a random seed to pin?

No. The Routing library’s guided local search is a deterministic descent with no random component, so identical input and an identical stopping criterion yield an identical plan. The only variability is how many improvement steps fit inside a wall-clock time_limit; pin a solution_limit (or an iteration cap) for byte-identical results across machines of different speed.

Up: OR-Tools Implementation

Related

• OR-Tools Implementation — the solver-integration sub-system both engines plug into
• Setting Up Google OR-Tools for Waste Collection — the pinned environment both solvers share
• Dynamic Threshold Tuning — calibrating the GLS time and solution budgets from telemetry
• OR-Tools vs. OSRM vs. Valhalla for Matrix Precomputation — where the shared distance matrix comes from