Data Pattern Pro

Mathematical programming / Routing and scheduling

Vehicle Routing Problem (VRP)

Route a fleet of capacity-constrained vehicles to serve a set of customers at minimum cost — the workhorse formulation behind most delivery networks.

Note Advanced

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

Multiple vehicles, each with limited capacity, need to serve a set of customers with known demand, starting and ending at a depot, at minimum total distance/cost. Add time windows, multiple depots, or pickup-and-delivery pairs and you get the many VRP variants used in practice.

When to use it

Last-mile delivery, field service dispatch, school bus routing — any problem where the core question is “which vehicle visits which stops, in what order.”

Formulation

Binary x_ijk = 1 if vehicle k travels directly from i to j. Continuous u_i tracks cumulative load for capacity tracking (a variant of the MTZ subtour trick from TSP):

minimize   sum(c_ij * x_ijk)
subject to:
  each customer visited exactly once by exactly one vehicle
  each vehicle route starts and ends at the depot
  u_j >= u_i + d_j - Q * (1 - x_ijk)     # capacity + subtour elimination combined
  u_i <= Q                                # vehicle capacity

Code sketch

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

manager = pywrapcp.RoutingIndexManager(len(distance_matrix), num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

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

demand_idx = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_idx, 0, vehicle_capacities, True, "Capacity"
)

search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
)
search_params.time_limit.FromSeconds(30)
solution = routing.SolveWithParameters(search_params)

Pitfalls

  • Exact MILP formulations of VRP are only practical for small instances (dozens of stops). Production systems almost always use metaheuristics or a routing library (OR-Tools, VRPy) with a time-boxed search — don’t chase provable optimality when “good enough in 30 seconds” is what the business needs.
  • If travel times are uncertain (traffic, weather), a deterministic VRP solution can look great on paper and fail in practice — that’s when it’s worth layering in buffers or a two-stage stochastic view of travel time.
  • Time windows turn this into VRPTW and add another dimension of constraints — model them as a scheduling dimension on top of the routing dimension, not as ad hoc penalty terms.