Solving Crew Routing with OR-Tools

Outage restoration is a routing problem with teeth: a fleet of crews, each with distinct qualifications and a bounded shift, must visit a churning set of work orders that carry their own access windows, service durations, and hard precedence constraints from the switching plan. Solving that by hand, or by a greedy nearest-neighbor loop, breaks down the moment two constraints interact — a splice crew that must reach a hospital feeder before its notification window closes, but only after a switching crew has isolated the section. This is a capacitated vehicle-routing problem with time windows (CVRPTW), and it is exactly the class of problem that Google OR-Tools’ constraint-programming routing library was built to solve. This page builds a complete, runnable solver that consumes the work orders produced by the crew dispatch and route optimization pipeline and returns structured, arrival-timed routes.

The solver here is the optimization core that the dispatch loop calls on every re-solve. Its inputs are the scored work orders derived from the outage impact set, and its precedence constraints come from the switching-order dependencies rooted in valve and isolator mapping. The whole model sits under the outage routing and impact automation discipline, and its output is what dispatch publishes to the field.

Environment Prerequisites

Pin the following before building the model. OR-Tools’ routing API is stable across recent releases, but its behavior around time-window slack and disjunction penalties has changed, so version discipline matters.

• Python runtime: Python 3.11 in an isolated environment (python -m venv .venv or a dedicated conda env), so solver parameters stay reproducible across dispatch nodes.
• OR-Tools: ortools>=9.8, installed with pip install ortools. The routing library lives under ortools.constraint_solver; confirm the import with python -c "from ortools.constraint_solver import pywrapcp".
• A travel-time matrix in integer units. OR-Tools routing works in integers, so express travel and service times in whole seconds or whole minutes. Build the matrix from a real road-network service that reflects current closures, not straight-line distance.
• Typed crew and work-order inputs. Each crew needs a home depot index, a shift window, and a skill set; each work order needs a location, a service duration, an access window, a required skill, and any precedence links. These arrive from the dispatch assembly stage rather than being typed here.
• A consistent time origin. Express every window against one event-time zero (for example seconds since the shift start), so the solver’s cumulative time dimension is directly comparable to the SLA clocks upstream.
• A solver time budget. Set a wall-clock limit (a few seconds during a storm) and a first-solution plus local-search strategy, because proving optimality on a large storm model is neither necessary nor affordable.

Schema-Aware Model Validation Protocol — Run Before the Solve

Most OR-Tools “no solution found” results are not solver failures; they are infeasible models. Work this ordered checklist before every solve; the earliest item is the most frequent culprit.

1. Confirm window feasibility per node. For each work order, verify that at least one crew can leave its depot, travel to the node, and arrive before the window closes. A node whose window shuts before any crew can reach it makes the entire model infeasible unless it is made droppable with a penalty.
2. Check skill coverage. Every required skill must be held by at least one on-shift crew. An order demanding a qualification no crew holds is unsatisfiable; either flag it for mutual-aid escalation or model it as a penalized disjunction rather than a hard visit.
3. Validate the matrix shape and units. The travel matrix must be square over depot + work-order nodes, integer-valued, and in the same unit as the service durations and window bounds. A matrix in minutes mixed with windows in seconds silently produces nonsense routes.
4. Detect precedence cycles. Precedence pairs (switch before repair) must form a DAG. A cycle, or a pair referencing a node not in the model, will over-constrain the solver into infeasibility — resolve it in the switching-order graph first.
5. Right-size capacity. The per-crew workload cap (a demand dimension) must be large enough that a feasible assignment exists across the fleet. Too tight a cap starves crews and drops work; too loose defeats the balancing the dimension is there to provide.

Minimal Reproducible Implementation

The following builds a CVRPTW with OR-Tools’ RoutingModel. It constructs the index manager over the depot and work-order nodes, registers a transit callback that adds service time to travel time, applies a time-window dimension, forbids skill-mismatched visits, adds a per-crew capacity dimension, and reads each vehicle’s route with arrival times into a structured result. It is self-contained and runnable as written.

from dataclasses import dataclass, field
from typing import Optional
import logging

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")


@dataclass(frozen=True)
class Crew:
    """A field crew with a depot, a shift window, and a set of skills."""
    name: str
    depot: int                      # node index the crew starts and ends at
    skills: frozenset[str]
    shift_start: int                # seconds from time origin
    shift_end: int


@dataclass(frozen=True)
class Order:
    """A work order located at a node, with an access window and a skill."""
    wo_id: str
    node: int                       # index into the travel matrix
    service_s: int                  # on-site duration, seconds
    skill: str
    ready: int                      # earliest service time, seconds
    due: int                        # latest service time, seconds


@dataclass
class RouteStop:
    wo_id: str
    node: int
    arrival_s: int


@dataclass
class SolveResult:
    routes: dict[str, list[RouteStop]] = field(default_factory=dict)
    dropped: list[str] = field(default_factory=list)
    objective: Optional[int] = None
    status: str = "UNSOLVED"


def solve_crew_routing(
    matrix: list[list[int]],
    crews: list[Crew],
    orders: list[Order],
    time_budget_s: int = 5,
) -> SolveResult:
    """Solve outage crew routing as a CVRPTW and return arrival-timed routes.

    `matrix[i][j]` is integer travel seconds between node i and node j; node 0..k
    are order/depot nodes shared with the Order.node and Crew.depot indices.
    Orders that cannot be served are made droppable with a large penalty so the
    solver returns a feasible plan instead of failing outright.
    """
    n_nodes = len(matrix)
    n_vehicles = len(crews)
    depots = [c.depot for c in crews]

    manager = pywrapcp.RoutingIndexManager(n_nodes, n_vehicles, depots, depots)
    routing = pywrapcp.RoutingModel(manager)

    order_by_node = {o.node: o for o in orders}
    service_of = {o.node: o.service_s for o in orders}

    # Arc cost: travel time + service time at the destination node.
    def transit_cb(from_index: int, to_index: int) -> int:
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        return matrix[i][j] + service_of.get(j, 0)

    transit_idx = routing.RegisterTransitCallback(transit_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

    # Time dimension: horizon large enough for the longest shift.
    horizon = max(c.shift_end for c in crews)
    routing.AddDimension(
        transit_idx,
        horizon,      # slack: allow waiting for a window to open
        horizon,      # capacity: upper bound on cumulative time
        False,        # do not force start cumul to zero (shift windows apply)
        "Time",
    )
    time_dim = routing.GetDimensionOrDie("Time")

    # Per-order access/SLA windows.
    for o in orders:
        idx = manager.NodeToIndex(o.node)
        time_dim.CumulVar(idx).SetRange(o.ready, o.due)

    # Per-crew shift windows at route start and end.
    for v, crew in enumerate(crews):
        start = routing.Start(v)
        end = routing.End(v)
        time_dim.CumulVar(start).SetRange(crew.shift_start, crew.shift_end)
        time_dim.CumulVar(end).SetRange(crew.shift_start, crew.shift_end)

    # Capacity dimension: cap the number of orders per crew (one unit each).
    def demand_cb(from_index: int) -> int:
        node = manager.IndexToNode(from_index)
        return 1 if node in order_by_node else 0

    demand_idx = routing.RegisterUnaryTransitCallback(demand_cb)
    per_crew_cap = -(-len(orders) // n_vehicles) + 2  # ceil share + slack
    routing.AddDimensionWithVehicleCapacity(
        demand_idx, 0, [per_crew_cap] * n_vehicles, True, "Load"
    )

    # Skill constraints: forbid a crew from serving orders it cannot work.
    for o in orders:
        idx = manager.NodeToIndex(o.node)
        allowed = [v for v, c in enumerate(crews) if o.skill in c.skills]
        if not allowed:
            logging.warning("no crew holds skill %r for %s", o.skill, o.wo_id)
        routing.SetAllowedVehiclesForIndex(allowed, idx)
        # Make the order droppable so an infeasible node does not sink the solve.
        routing.AddDisjunction([idx], 1_000_000)

    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    params.time_limit.FromSeconds(time_budget_s)

    solution = routing.SolveWithParameters(params)
    result = SolveResult()
    if solution is None:
        result.status = "INFEASIBLE"
        logging.error("no feasible routing solution within budget")
        return result

    result.status = "OK"
    result.objective = solution.ObjectiveValue()
    served: set[int] = set()
    for v, crew in enumerate(crews):
        index = routing.Start(v)
        stops: list[RouteStop] = []
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            if node in order_by_node:
                arrival = solution.Value(time_dim.CumulVar(index))
                stops.append(RouteStop(order_by_node[node].wo_id, node, arrival))
                served.add(node)
            index = solution.Value(routing.NextVar(index))
        result.routes[crew.name] = stops

    result.dropped = [o.wo_id for o in orders if o.node not in served]
    return result


if __name__ == "__main__":
    # 0 = depot; 1..4 = work-order nodes. Travel seconds (symmetric).
    travel = [
        [0, 600, 900, 1200, 800],
        [600, 0, 500, 700, 650],
        [900, 500, 0, 400, 600],
        [1200, 700, 400, 0, 500],
        [800, 650, 600, 500, 0],
    ]
    fleet = [
        Crew("switching-1", 0, frozenset({"switching"}), 0, 28800),
        Crew("cable-1", 0, frozenset({"cable-splice", "switching"}), 0, 28800),
    ]
    work = [
        Order("SW-01", 1, 900, "switching", 0, 7200),
        Order("SW-02", 2, 900, "switching", 0, 10800),
        Order("RP-07", 3, 5400, "cable-splice", 1800, 21600),
        Order("RP-09", 4, 7200, "cable-splice", 0, 9000),  # critical, tight window
    ]
    outcome = solve_crew_routing(travel, fleet, work, time_budget_s=3)
    print("status:", outcome.status, "| objective:", outcome.objective)
    for crew_name, stops in outcome.routes.items():
        seq = ", ".join(f"{s.wo_id}@{s.arrival_s}s" for s in stops)
        print(f"{crew_name}: {seq or '(idle)'}")
    if outcome.dropped:
        print("dropped:", outcome.dropped)

Two modeling choices carry most of the weight. The transit callback folds service time into the arc cost, so the cumulative time dimension reads as true arrival time rather than pure travel — that is what lets the per-order window constraints mean “served within the window” instead of merely “reached.” And every order is wrapped in a AddDisjunction with a large penalty, which makes it droppable: if a work order genuinely cannot be served within its window by any qualified crew, the solver drops it (and reports it in dropped) rather than declaring the whole model infeasible and returning nothing. During a storm, a plan that serves ninety of a hundred orders and flags ten for escalation is vastly more useful than no plan at all.

Precedence — a switch that must be operated before a repair downstream of it — is added as an explicit constraint on the time dimension when the two nodes are known: time_dim.CumulVar(switch_idx) <= time_dim.CumulVar(repair_idx) via routing.solver().Add(...). Keep the precedence set to the pairs that genuinely gate safety; over-constraining the model is the fastest route to spurious infeasibility, which is why the switching-order graph is topologically validated upstream before its edges become solver constraints.

Production Deployment Pattern

Promoting the solver from a script to a dispatch control means wrapping it in the operational discipline the rest of the outage pipeline already enforces.

1. Call it as a pure function on every re-solve. The dispatch loop invokes solve_crew_routing with the current matrix, roster, and scored orders whenever an input changes. Because it is deterministic given its inputs and a fixed seed, the resulting plan can be diffed against the previous one rather than reconstructed by a dispatcher.
2. Bound and warm-start the search. Keep time_budget_s to a few seconds during active events, and pass the previous solution as an initial route with routing.ReadAssignmentFromRoutes so each solve improves the standing plan instead of rediscovering it from scratch.
3. Feed a live travel matrix, staged not live-queried. Refresh the road-network matrix on its own cadence into a staging store, exactly as any data ingestion pipeline for utility assets stages and validates inputs, and never call a routing service inside the solve loop.
4. Publish with idempotent, retried writes. Push each RouteStop to the CRM and mobile workforce over REST, keyed by work-order id so a re-solve updates an assignment rather than duplicating it, and wrap the write in bounded exponential backoff so a transient endpoint failure retries instead of dropping a crew’s plan.
5. Version the solver configuration and log every solve. Keep first-solution strategy, metaheuristic, penalties, and time budget under version control and deployed through CI/CD; log the objective, the served and dropped orders, and the triggering change for each cycle so the plan is auditable.

Conclusion

Modeling outage restoration as a CVRPTW turns crew dispatch into a repeatable computation rather than a wall-board improvisation. OR-Tools supplies the constraint engine: a transit callback that captures travel plus service, a time dimension that enforces access and SLA windows, per-node vehicle restrictions that respect crew skills, a capacity dimension that balances load, and droppable disjunctions that keep a partial storm plan feasible. The structured, arrival-timed result plugs straight into the dispatch handoff, and because the whole solve is a pure function of its inputs it re-runs cleanly as the storm changes. The natural next refinement is to tune the disjunction penalties per criticality tier so the solver never drops a hospital feeder before a residential lateral.

Related

• Up to the parent topic: Crew Dispatch & Route Optimization
• Up to the section: Outage Routing & Impact Automation
• Prioritizing Restoration with SAIDI/SAIFI Scoring — the scores that weight the orders this solver routes.
• Impact Analysis & Affected-Customer Tracing — where the work orders and their customer counts originate.
• Valve & Isolator Mapping Strategies — the barrier states behind the precedence constraints.

For authoritative reference, consult the OR-Tools routing documentation and the Python dataclasses reference.