Ortools Routing Modeling

OR-Tools Routing Modeling

Use this skill for vehicle-routing models built with ortools.constraint_solver.pywrapcp.RoutingModel.

Modeling Flow

1. Normalize integer data and map external nodes to routing-manager nodes.
2. Build transit, cost, and demand matrices or vectors before registering callbacks.
3. Add time and capacity dimensions, including vehicle start/end ranges and span limits.
4. Add problem-specific visits, time windows, optional-node penalties, and pairing constraints.
5. Solve with an internal time limit, extract ordered routes, then audit them independently before reporting.

Data And Indexing

• Convert travel times, service times, demands, and time bounds to integers before registering callbacks or transit matrices. Avoid floats and NaN; OR-Tools can silently treat bad values as usable arcs.
• Assert that matrix dimensions, node counts, vehicle counts, and declared record counts agree before building the model. Shape mistakes often produce plausible but meaningless routes.
• Keep a clear distinction between external node IDs, routing manager node IDs, and internal routing indices. Convert with manager.NodeToIndex(node) and manager.IndexToNode(index).
• When vehicles need distinct starts or ends but the input has shared depots, copy the depot into one internal start node and one internal end node per vehicle. Prefer these internal depot copies over reusing the same shared depot node for every vehicle, then map the copies back to the shared external depot IDs when reporting.
• A common cloned-depot layout is: solver job nodes first, then one start depot per vehicle, then one end depot per vehicle. External shared depot IDs can be stripped from the job matrix and restored only when reporting.
• Treat negative, missing, or sentinel travel times as invalid arcs. Either forbid them with explicit constraints or give them a prohibitive transit cost and reject any final route that uses them. Choose invalid-arc sentinels large enough to dominate feasible legs, but small enough to avoid integer overflow when service times and route spans are added.
• For static integer data, prefer precomputed RegisterTransitMatrix and RegisterUnaryTransitVector calls over Python callbacks. Routing callbacks are called very often during local search and can consume solve time on large instances.

When an input matrix has one shared start depot and one shared end depot, but the routing model needs one start and end node per vehicle, build an internal matrix with cloned depots:

def clone_depots_matrix(external, job_nodes, num_vehicles, start_depot, end_depot, invalid_cost):
    num_jobs = len(job_nodes)
    start_nodes = list(range(num_jobs, num_jobs + num_vehicles))
    end_nodes = list(range(num_jobs + num_vehicles, num_jobs + 2 * num_vehicles))
    matrix = [[invalid_cost] * (num_jobs + 2 * num_vehicles) for _ in range(num_jobs + 2 * num_vehicles)]

    for i, ext_i in enumerate(job_nodes):
        for j, ext_j in enumerate(job_nodes):
            matrix[i][j] = external[ext_i][ext_j]
        for end in end_nodes:
            matrix[i][end] = external[ext_i][end_depot]

    for start in start_nodes:
        for j, ext_j in enumerate(job_nodes):
            matrix[start][j] = external[start_depot][ext_j]
    for vehicle in range(num_vehicles):
        matrix[start_nodes[vehicle]][end_nodes[vehicle]] = 0
    return matrix, start_nodes, end_nodes

Dimensions

• Put travel time plus service time at the departing node in the time transit. Then Time.CumulVar(index) is the arrival or service-start time, and departure is arrival + service_time.
• Derive the time horizon from the data, including latest time windows, service time, travel time, and slack. Avoid arbitrary horizons that are too tight for waiting/service or so large that invalid-arc penalties become usable.
• Choose fix_start_cumul_to_zero deliberately. Use False when vehicle start times or shifts may vary; use start time windows or allowed start values instead.
• Set each vehicle start/end cumul through routing.Start(vehicle) and routing.End(vehicle), especially when depots are cloned or shared.
• If shifts may start from a discrete menu, apply allowed values to each vehicle start cumul after setting its broad time-window range.
• Use span upper bounds for route-duration or shift-length limits.
• For capacity, use a unary demand callback and no slack. With OR-Tools dimensions, the load cumul at a node often represents load before applying that node's demand, so audit route loads from the ordered node sequence when checking or exporting a solution.

Apply ordinary visit time windows directly to the node's time cumul:

for node, (window_low, window_high) in time_windows.items():
    index = manager.NodeToIndex(node)
    time_dim.CumulVar(index).SetRange(int(window_low), int(window_high))

For top-of-hour shift starts inside an operating window, generate the allowed start values and apply them to each vehicle start cumul:

def possible_shift_start_times(operating_window, shift_duration, step_minutes=60):
    start, end = operating_window
    return [
        minute
        for minute in range(0, 24 * 60 + 1, step_minutes)
        if start <= minute <= end - shift_duration
    ]

shift_starts = possible_shift_start_times(operating_window, shift_duration)
for vehicle in range(num_vehicles):
    time_dim.CumulVar(routing.Start(vehicle)).SetRange(*operating_window)
    time_dim.CumulVar(routing.End(vehicle)).SetRange(*operating_window)
    time_dim.CumulVar(routing.Start(vehicle)).SetValues(shift_starts)
    time_dim.SetSpanUpperBoundForVehicle(shift_duration, vehicle)
    routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.Start(vehicle)))
    routing.AddVariableMaximizedByFinalizer(time_dim.CumulVar(routing.End(vehicle)))

Optional Visits And Objectives

• Use AddDisjunction for optional nodes and choose penalties so the primary objective dominates secondary route costs.
• If optional visits are part of the model, scale skip penalties so they reflect the stated priority relative to travel or duration costs.
• When the public objective is to maximize served visits or jobs, model that as large skip penalties, then add a small positive arc cost such as travel time or travel-plus-service time as a secondary tie-breaker. A purely zero-cost served-route objective can give local search too little gradient to improve route structure.
• Keep the skip penalty very large: one additional served job should dominate any plausible secondary travel or service-time difference.
• You can use separate callbacks for optimization cost and time feasibility. The time dimension should enforce travel and service propagation, while the arc-cost callback can use scaled travel or travel-plus-service costs for search guidance.