Comparing OR-Tools and Greedy Heuristics for Inspection Routing

12 min read

This guide sits under Optimizing Inspector Route Scheduling with Python, part of the Inspection Scheduling & Field Operations track, and answers the question that decides your whole routing stack: for your fleet size, appointment constraints, and server, should the daily board come from an OR-Tools solver, a greedy nearest-neighbor pass, or a Clarke-Wright savings heuristic?

The choice is not academic. A building department running twelve inspectors against three hundred daily stops on a shared, constrained municipal VM has very different needs from a small township dispatching four inspectors from a laptop. Pick a heavy constraint solver where a heuristic would do and you carry a 60 MB dependency and multi-second solve times you did not need. Pick a greedy pass where windows are tight and you break appointment promises the solver would have kept. This guide compares three approaches on the four axes that actually govern the decision — solution quality, runtime, dependency weight on constrained hardware, and which constraints each can honor — then gives you a decision rule and the failure modes of each.

Decision matrix: OR-Tools vs nearest-neighbor vs Clarke-Wright savings A four-column matrix rating three inspection-routing methods. Columns are solution quality, runtime, dependency weight on constrained municipal servers, and the constraints each method can honor. OR-Tools routing: near-optimal quality, seconds of runtime, a heavy prebuilt wheel, and full support for time windows and workload balance. Nearest-neighbor greedy: rough quality, millisecond runtime, no dependency beyond the standard library, and capacity limits only. Clarke-Wright savings: good quality, fast runtime, a light NumPy dependency, and only weak time-window support. Method Solution quality Runtime Dependency weight Constraints OR-Tools routing / CP-SAT Near-optimal global search Seconds time-budgeted Heavy wheel ~60 MB native Windows + balance, skills Nearest- neighbor Rough 10–25% over Milliseconds O(n²) None stdlib only Capacity only Clarke-Wright savings Good 5–12% over Fast O(n² log n) Light NumPy Weak windows capacity solid

The Decision in One Table

The same comparison in plain text, which is what you paste into an architecture decision record:

Axis OR-Tools routing Nearest-neighbor Clarke-Wright savings
Solution quality Near-optimal (guided local search) Rough, 10–25% over best-known Good, 5–12% over best-known
Runtime (200 stops) 2–10 s, time-budgeted < 50 ms ~200–600 ms
Dependency weight Heavy (~60 MB native wheel) None (standard library) Light (NumPy)
Time windows First-class dimension Not honored Only via post-hoc repair
Workload balance Global span cost None Route-count cap only
Skill/discipline rules Hard AllowedVehicles Manual filter Manual filter
Best fit Tight windows, large fleet Prototype, tiny fleet, fallback Mid-size, loose windows, thin server

When Each One Wins

Reach for OR-Tools when appointment windows are tight, the fleet is large enough that assignment (not just ordering) matters, or discipline and workload-balance constraints are hard requirements. Its routing library models time windows as a native dimension and balances load through a span-cost coefficient, which no heuristic does natively. The cost is a ~60 MB prebuilt wheel and multi-second solves — acceptable for a once-a-morning dispatch run, awkward for a function that must answer in 50 ms.

Reach for nearest-neighbor when you are prototyping, the fleet is tiny, windows are loose, or you need a dependency-free fallback that always produces a board when the solver times out. It is the honest baseline built in the parent guide, and its real production role is exactly that: the safety net behind the solver.

Reach for Clarke-Wright savings when you want most of the solver’s quality on a fraction of the dependency and runtime budget, and your windows are loose enough that a light post-hoc repair pass can fix the few violations. It is the sweet spot for a mid-size township on a shared VM that cannot spare 60 MB and several CPU-seconds per run.

Step 1 — Score a Route So the Comparison Is Fair

Every method must be judged by the same yardstick: total travel minutes plus a penalty for any appointment window it violates. Without a shared scorer you cannot say one method “wins.”

from datetime import time


def route_cost(matrix: list[list[int]], route: list[int], stops: list,
               window_penalty: int = 500) -> int:
    """Total travel minutes for one route, plus a stiff penalty per missed window."""
    if not route:
        return 0
    clock = 0                    # running minutes-since-midnight along the route
    node = 0                     # depot
    total_travel = 0
    for stop_idx in route:
        travel = matrix[node][stop_idx + 1]   # +1: node 0 is the depot
        total_travel += travel
        clock = max(clock + travel, _mins(stops[stop_idx].window_open))
        if clock > _mins(stops[stop_idx].window_close):
            total_travel += window_penalty     # late arrival: broken promise
        clock += stops[stop_idx].service_minutes
        node = stop_idx + 1
    return total_travel


def _mins(t: time) -> int:
    return t.hour * 60 + t.minute

Run this over every method’s output on the same day of stops and you have a single, comparable number — travel plus broken-window penalties — that tells you what each approach actually costs your residents and your fleet.

Step 2 — The Clarke-Wright Savings Middle Ground

Clarke-Wright is the method most municipal teams have never tried and most should. It starts with every stop on its own out-and-back route, then greedily merges the two routes whose merge “saves” the most travel — the savings of joining stops i and j is d(depot,i) + d(depot,j) - d(i,j). It needs only NumPy and consistently lands within about ten percent of the solver on capacity-constrained problems.

import numpy as np


def clarke_wright(matrix: list[list[int]], demand_count: int,
                  vehicle_capacity: int) -> list[list[int]]:
    """Savings-based routes. Node 0 is the depot; nodes 1..n map to stops 0..n-1."""
    d = np.array(matrix)
    n = demand_count
    # Savings s(i,j) = d(0,i) + d(0,j) - d(i,j); higher means a better merge.
    savings = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            savings.append((d[0, i] + d[0, j] - d[i, j], i, j))
    savings.sort(reverse=True)                     # merge best savings first

    routes: dict[int, list[int]] = {i: [i] for i in range(1, n + 1)}
    route_of = {i: i for i in range(1, n + 1)}      # node -> route key
    for _, i, j in savings:
        ri, rj = route_of[i], route_of[j]
        if ri == rj:
            continue                                # already in the same route
        left, right = routes[ri], routes[rj]
        # Only merge at endpoints, and only if capacity allows.
        if left[-1] == i and right[0] == j and len(left) + len(right) <= vehicle_capacity:
            merged = left + right
            routes[ri] = merged
            for node in right:
                route_of[node] = ri
            del routes[rj]
    # Return as 0-based stop indices to match the rest of the pipeline.
    return [[node - 1 for node in r] for r in routes.values()]

Clarke-Wright respects capacity natively but not time windows — that is its one real weakness. If your windows are loose (half-day rather than one-hour), a single repair pass that reorders each route by window-open time recovers most feasibility. If your windows are tight, this is the signal to move up to OR-Tools rather than pile repair heuristics on top.

Step 3 — Wrap the Choice Behind One Interface

Do not scatter if use_ortools across the codebase. Expose one plan_routes function that dispatches on a configured strategy, so switching methods — or falling back when the solver times out — is a one-line config change and a testable seam.

from typing import Callable, Literal

Strategy = Literal["ortools", "greedy", "savings"]


def plan_routes(strategy: Strategy, matrix, stops, inspectors, **kw) -> dict[str, list[int]]:
    match strategy:
        case "ortools":
            result = solve_routes(matrix, stops, inspectors,
                                  time_budget_seconds=kw.get("time_budget", 10))
            if result is None:                       # solver gave up under budget
                return nearest_neighbor_routes(matrix, stops, inspectors)  # safe fallback
            return result
        case "savings":
            cap = max(i.max_stops for i in inspectors)
            raw = clarke_wright(matrix, len(stops), cap)
            return {insp.name: route for insp, route in zip(inspectors, raw)}
        case "greedy":
            return nearest_neighbor_routes(matrix, stops, inspectors)

The ortools branch degrading to the greedy baseline is the most important line here: dispatch must never return an empty board because the solver ran out of time on an unusually hard day. The routing internals behind solve_routes and nearest_neighbor_routes are built in the parent guide on optimizing inspector route scheduling; this page only chooses between them.

Parameter and Flag Reference

Setting Applies to Recommended Rationale for permit inspections
time_budget_seconds OR-Tools 5–15 Fits a morning dispatch run; beyond ~15 s quality gains flatten for typical day sizes.
window_penalty scorer 500 Must dwarf a normal inter-stop travel time so a missed window always outweighs a detour.
vehicle_capacity savings / greedy shift ÷ avg visit Cap route length by real shift math, not a round number.
fallback_strategy dispatcher greedy The zero-dependency method that always returns a board when the solver times out.
repair_pass savings sort_by_window Cheap post-merge reorder that recovers loose-window feasibility.
savings_capacity_slack savings 0 Increase only if you accept slightly over-long routes to reduce vehicle count.

Common Failure Patterns and Fixes

Comparing methods on different days

Running OR-Tools on Monday’s stops and greedy on Tuesday’s and concluding one is better is the most common mistake. Freeze one representative day (or several) as a fixture and score every method against the identical input with route_cost. Only then are the numbers comparable.

Greedy declared “good enough” because windows were ignored

Nearest-neighbor looks competitive on total travel precisely because it never checks windows — it is cheap because it skips the hard part. Always score with the window_penalty term included; a greedy route that arrives late to a third of its stops is not cheaper, it is broken.

Clarke-Wright merges into oversized routes

Without the capacity guard in the merge condition, savings will happily fuse two half-day routes into one twelve-hour marathon. Enforce len(left) + len(right) <= vehicle_capacity at every merge, and treat any route exceeding shift length as a hard reject, not a warning.

OR-Tools dependency breaks a constrained deploy

The prebuilt wheel pulls native libraries that occasionally clash on locked-down or older municipal images, and 60 MB matters on a thin VM. If the wheel won’t install cleanly, default to Clarke-Wright — it delivers most of the quality on a NumPy-only footprint — rather than forcing the heavy dependency onto hardware that can’t take it.

Solver timeout silently returns an empty board

If SolveWithParameters returns None under a tight budget and nothing catches it, dispatch gets no routes at all. Always wire the fallback in plan_routes so a timeout degrades to the greedy baseline, and log the timeout with the day’s stop count so you can raise the budget for that size.

Audit and Logging Guidance

Route planning is a decision a resident may later question — “why didn’t the inspector make it in my window?” — so log enough to reconstruct any day’s board. For each dispatch run record the strategy used, the input day (stop IDs, windows, fleet), the per-route travel and the route_cost score, any stops the solver dropped, and whether a fallback fired. Keep these for the state-mandated records-retention period, using the same append-only, hash-chained pattern applied when securing municipal API endpoints for third-party integrations, so a compliance officer can prove the routing was deterministic and unaltered. Log strategy changes with particular care: switching from OR-Tools to a heuristic shifts which appointment promises get kept, and that policy shift should be attributable to a person and a date, not buried in a config diff. When the demand feeding a run arrives in bulk, route it through the shared error handling and retry logic for ingestion pipelines so a malformed stop is quarantined and traceable rather than silently skewing the board.

Frequently Asked Questions

If OR-Tools gives the best routes, why consider anything else?

Because “best routes” is only one axis. OR-Tools carries a heavy native dependency and multi-second solves that a constrained municipal VM or a low-latency endpoint may not tolerate. When windows are loose, Clarke-Wright reaches within about ten percent of optimal on a NumPy-only footprint, and nearest-neighbor is the dependency-free fallback you need anyway. Match the method to the fleet size, the window tightness, and the server — not to a benchmark.

How do I know if my appointment windows are “tight” enough to need OR-Tools?

A practical test: score a Clarke-Wright plan with a window-open sort repair pass, then count the stops whose arrival still misses their window. If that count is near zero on representative days, your windows are loose and the savings heuristic is fine. If a meaningful fraction miss, the windows genuinely constrain the assignment and only a solver that treats them as a first-class dimension will keep those promises.

Can I mix methods across the fleet?

Yes, and it is often the pragmatic answer. Run OR-Tools for the dense, tight-window downtown district where assignment quality pays off, and Clarke-Wright or greedy for a rural fringe where stops are far apart and windows are wide. The single plan_routes interface makes per-district strategy a config value, and the shared scorer keeps the comparison honest across the whole board.