vehicle-routing-problem-optimization

Vehicle Routing Problem (VRP) Optimization Skill Guide

This skill standardizes mathematical modeling and programmatic resolution of delivery fleet route optimization using Google OR-Tools constraint programming.

1. CVRPTW Constraint Hierarchy

[ Input Problem Data ]
  |-- Customer Coordinates & Delivery Demands (e.g. packages/weight)
  |-- Service Time Windows [Earliest Arrival, Latest Departure]
  |-- Fleet Vehicle Capacities & Maximum Shift Durations
  |-- Distance / Travel Time Matrix (from OSRM / Google Maps API)
          |
          v
[ Google OR-Tools Routing Model ]
  |-- RoutingIndexManager (Node <-> Index Mapping)
  |-- AddDimension(Distance / Capacity / Time)
  |-- AddDisjunction (Penalized Dropped Visits if overconstrained)
          |
          v (Guided Local Search / Tabu Search)
[ Optimized Multi-Vehicle Dispatch Schedules ]

2. Production Code Implementation (Python / OR-Tools)

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


def create_data_model():
    """Builds sample input data for 4 vehicles and 10 delivery locations."""
    data = {}
    # Time/distance matrix in minutes (10 locations + 1 depot at index 0)
    data["time_matrix"] = [
        [0, 12, 20, 15, 18, 25, 22, 10, 14, 16, 20],
        [12, 0, 10, 8, 15, 18, 20, 14, 16, 12, 18],
        [20, 10, 0, 12, 14, 15, 16, 18, 20, 14, 10],
        [15, 8, 12, 0, 10, 12, 14, 16, 18, 10, 15],
        [18, 15, 14, 10, 0, 8, 10, 12, 14, 16, 18],
        [25, 18, 15, 12, 8, 0, 6, 10, 12, 14, 16],
        [22, 20, 16, 14, 10, 6, 0, 8, 10, 12, 14],
        [10, 14, 18, 16, 12, 10, 8, 0, 6, 8, 10],
        [14, 16, 20, 18, 14, 12, 10, 6, 0, 5, 8],
        [16, 12, 14, 10, 16, 14, 12, 8, 5, 0, 6],
        [20, 18, 10, 15, 18, 16, 14, 10, 8, 6, 0],
    ]
    # Time windows: [earliest_start_min, latest_start_min]
    data["time_windows"] = [
        (0, 480),  # 0: Depot open 8 hours
        (30, 120), # 1
        (60, 180), # 2
        (90, 240), # 3
        (120, 300),# 4
        (150, 360),# 5
        (180, 400),# 6
        (60, 200), # 7
        (120, 300),# 8
        (180, 360),# 9
        (240, 450),# 10
    ]
    # Customer delivery demands (e.g., packages)
    data["demands"] = [0, 1, 2, 1, 3, 2, 1, 2, 1, 2, 1]
    data["vehicle_capacities"] = [8, 8, 8, 8]
    data["num_vehicles"] = 4
    data["depot"] = 0
    return data


def solve_cvrptw():
    data = create_data_model()

    # 1. Routing Index Manager
    manager = pywrapcp.RoutingIndexManager(
        len(data["time_matrix"]),
        data["num_vehicles"],
        data["depot"],
    )
    routing = pywrapcp.RoutingModel(manager)

    # 2. Transit Callback (Travel Time)
    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["time_matrix"][from_node][to_node]

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

    # 3. Add Time Window Dimension
    time_dimension_name = "Time"
    routing.AddDimension(
        transit_callback_index,
        60,   # Allow waiting time up to 60 mins
        480,  # Max vehicle shift 8 hours
        False,# Don't force start cumul to zero
        time_dimension_name,
    )
    time_dimension = routing.GetDimensionOrDie(time_dimension_name)

    # Add time window constraints for each customer
    for location_idx, time_window in enumerate(data["time_windows"]):
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

    # 4. Add Demand / Capacity Dimension
    def demand_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],
        True,  # start cumul to zero
        "Capacity",
    )

    # 5. Search Parameters
    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 = 5

    # Solve
    solution = routing.SolveWithParameters(search_parameters)
    return solution is not None