OR-Tools Routing

Solve complex vehicle routing problems using Google OR-Tools optimization library.

Installation

pip install ortools

Quick Start

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_routing_model(distance_matrix, num_vehicles, depot):
    """Create a basic VRP routing model."""
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), num_vehicles, depot
    )
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    return manager, routing

Common Patterns

Capacitated VRP (CVRP)

def add_capacity_constraint(routing, manager, demands, vehicle_capacities):
    """Add capacity constraints to routing model."""
    def demand_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return demands[from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        vehicle_capacities,  # vehicle maximum capacities
        True,  # start cumul to zero
        'Capacity'
    )

VRP with Time Windows (VRPTW)

def add_time_windows(routing, manager, time_matrix, time_windows):
    """Add time window constraints."""
    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return time_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.AddDimension(
        transit_callback_index,
        30,  # allow waiting time
        3600,  # maximum time per vehicle
        False,  # don't force start cumul to zero
        'Time'
    )

    time_dimension = routing.GetDimensionOrDie('Time')
    for location_idx, (start, end) in enumerate(time_windows):
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(start, end)

Solving and Extracting Solution

def solve_vrp(routing, manager, search_parameters=None):
    """Solve the VRP and extract routes."""
    if search_parameters is None:
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
        )
        search_parameters.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
        )
        search_parameters.time_limit.seconds = 30

    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        routes = []
        for vehicle_id in range(routing.vehicles()):
            route = []
            index = routing.Start(vehicle_id)
            while not routing.IsEnd(index):
                route.append(manager.IndexToNode(index))
                index = solution.Value(routing.NextVar(index))
            route.append(manager.IndexToNode(index))
            routes.append(route)
        return routes
    return None

Search Strategies

# First solution strategies
FirstSolutionStrategy.AUTOMATIC
FirstSolutionStrategy.PATH_CHEAPEST_ARC
FirstSolutionStrategy.SAVINGS
FirstSolutionStrategy.CHRISTOFIDES

# Local search metaheuristics
LocalSearchMetaheuristic.AUTOMATIC
LocalSearchMetaheuristic.GREEDY_DESCENT
LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
LocalSearchMetaheuristic.SIMULATED_ANNEALING
LocalSearchMetaheuristic.TABU_SEARCH