VRPTW Routing › Implementation in Google OR-Tools
Machine Learning from ScratchAll chapters VRPTW Routing › Implementation in Google OR-ToolsOne section · Sections in this chapter5 / 8 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Now that we understand the mathematical formulation and have worked through a manual example, let's see how to implement VRPTW using Google OR-Tools. This implementation translates our mathematical constraints into code, allowing the solver to automatically find optimal or near-optimal solutions.
From Mathematics to Code: Mapping Constraints
OR-Tools uses a constraint programming approach that implements our mathematical formulation through "dimensions" and "callbacks." Each constraint from our formulation maps to specific OR-Tools constructs:
- Routing decisions (): Handled automatically by the routing model's internal variables
- Time tracking (): Implemented through a "Time" dimension
- Capacity constraints: Implemented through a "Capacity" dimension
- Time windows: Set as bounds on the Time dimension
- Flow conservation: Enforced automatically by the routing model structure
Let's build the implementation step by step, connecting each code section to its corresponding mathematical concept.
We'll implement VRPTW step by step, starting with the data model and then building the solver configuration. This approach helps understand how each component maps to the mathematical formulation.
def create_data_model():
"""Create the data for the VRPTW problem.
This function defines all the problem parameters that correspond to
the mathematical formulation's input data.
"""
data = {}
# Distance matrix (travel times in minutes)
# This corresponds to t_{ij} in our formulation
data["distance_matrix"] = [
[0, 2, 3, 4, 5, 6], # Depot
[2, 0, 2, 3, 4, 5], # Customer 1
[3, 2, 0, 2, 3, 4], # Customer 2
[4, 3, 2, 0, 2, 3], # Customer 3
[5, 4, 3, 2, 0, 2], # Customer 4
[6, 5, 4, 3, 2, 0], # Customer 5
]
# Time windows [earliest, latest] in minutes from start
# This corresponds to [a_i, b_i] in our formulation
data["time_windows"] = [
(0, 480), # Depot: 8-hour workday
(60, 180), # Customer 1: 1-3 hours
(120, 240), # Customer 2: 2-4 hours
(180, 300), # Customer 3: 3-5 hours
(240, 360), # Customer 4: 4-6 hours
(300, 420), # Customer 5: 5-7 hours
]
# Demands - corresponds to d_i in our formulation
data["demands"] = [0, 2, 3, 1, 2, 3] # Depot has 0 demand
# Vehicle data - corresponds to Q_k and K in our formulation
data["vehicle_capacities"] = [8, 8] # Two vehicles with capacity 8
data["num_vehicles"] = 2
# Service times - corresponds to s_i in our formulation
data["service_times"] = [0, 10, 15, 10, 15, 10] # Depot has 0 service time
return dataNow we'll create the solver function that implements all the constraints from our mathematical formulation:
def solve_vrptw():
"""Solve the VRPTW problem using OR-Tools.
This function implements the complete mathematical formulation,
translating each constraint into OR-Tools constructs.
"""
# Create data model (all our parameters)
data = create_data_model()
# Step 1: Create routing index manager
# This sets up the node indexing system (V = {0, 1, ..., n})
# and vehicle indexing (K = {1, 2, ..., m})
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), # Number of nodes |V|
data["num_vehicles"], # Number of vehicles |K|
0, # Depot is at index 0
)
# Step 2: Create routing model
# This initializes the constraint programming model that will
# manage our decision variables x_{ijk}
routing = pywrapcp.RoutingModel(manager)
# Step 3: Define the objective function
# This implements: min Σ_{k∈K} Σ_{(i,j)∈A} c_{ij} x_{ijk}
def distance_callback(from_index, to_index):
"""Callback that returns the cost of traveling from one node to another.
This corresponds to c_{ij} in our objective function.
OR-Tools will call this function to evaluate arc costs.
"""
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["distance_matrix"][from_node][to_node]
# Register the callback and set it as the arc cost evaluator
# This tells OR-Tools to minimize total travel cost
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Step 4: Add capacity constraints (Constraint 2)
# This implements: Σ_{i∈V\{0}} d_i Σ_{j≠i} x_{ijk} ≤ Q_k
def demand_callback(from_index):
"""Callback that returns the demand at a node.
This corresponds to d_i in our capacity constraint.
"""
from_node = manager.IndexToNode(from_index)
return data["demands"][from_node]
# Register demand callback and add capacity dimension
# This creates a cumulative dimension that tracks total demand
# along each route and enforces the capacity limit Q_k
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback
)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack (no buffer)
data["vehicle_capacities"], # Q_k: maximum capacity per vehicle
True, # start cumul to zero (vehicles start empty)
"Capacity", # dimension name for reference
)
# Step 5: Add time dimension and constraints (Constraints 4 and 5)
# This implements the time tracking w_{ik} and enforces:
# - a_i ≤ w_{ik} ≤ b_i (time windows)
# - w_{ik} + s_i + t_{ij} ≤ w_{jk} when x_{ijk} = 1 (precedence)
def time_callback(from_index, to_index):
"""Callback that returns the time to travel from one node to another.
This accounts for both travel time t_{ij} and service time s_i,
implementing the temporal logic: arrival_time + service + travel = next_arrival
"""
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
travel_time = data["distance_matrix"][from_node][to_node] # t_{ij}
service_time = data["service_times"][from_node] # s_i
return travel_time + service_time
# Register time callback and add time dimension
# This creates a cumulative dimension that tracks arrival times w_{ik}
time_callback_index = routing.RegisterTransitCallback(time_callback)
routing.AddDimension(
time_callback_index,
480, # allow waiting time (vehicles can wait if they arrive early)
480, # maximum time per vehicle (8-hour workday)
False, # don't force start cumul to zero (vehicles can start at different times)
"Time", # dimension name
)
# Get the time dimension to set time window constraints
time_dimension = routing.GetDimensionOrDie("Time")
# Step 6: Set time window bounds (Constraint 4)
# This implements: a_i ≤ w_{ik} ≤ b_i for all locations
for location_idx, time_window in enumerate(data["time_windows"]):
index = manager.NodeToIndex(location_idx)
# SetRange enforces the time window bounds
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Step 7: Set depot time windows for vehicles
# Vehicles must start and end within depot hours
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][0][0], # earliest start
data["time_windows"][0][1], # latest end
)
# Note: Constraint 1 (each customer visited once) and Constraint 3 (flow conservation)
# are automatically enforced by OR-Tools' routing model structure.
# Constraint 5 (temporal precedence) is handled by the time dimension's
# cumulative logic combined with the time_callback.
# Constraint 6 (binary variables) is inherent in the routing model.
# Step 8: Configure search strategy
# OR-Tools uses heuristics and local search to find good solutions
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
# Step 9: Solve the problem
# This is where OR-Tools explores the solution space, checking
# all constraints and minimizing the objective function
solution = routing.SolveWithParameters(search_parameters)
return solution, routing, manager, dataNow let's solve the problem and extract the solution:
# Solve the problem
solution, routing, manager, data = solve_vrptw()
# Extract route information
routes = []
route_distances = []
total_distance = 0
if solution:
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
route = []
route_distance = 0
# Follow the route by reading NextVar values
# This traces which arcs have x_{ijk} = 1
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route.append(node_index)
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
route.append(manager.IndexToNode(index))
routes.append(route)
route_distances.append(route_distance)
total_distance += route_distance
objective_value = solution.ObjectiveValue()
else:
objective_value = None
routes = []
route_distances = []
total_distance = 0Display the solution results:
Solution found!
Objective value (total distance): 21
Routes:
Vehicle 1: Depot -> C3 -> C4 -> C5 -> Depot
Distance: 14, Load: 6/8
Vehicle 2: Depot -> C1 -> C2 -> Depot
Distance: 7, Load: 5/8
Summary:
Total distance: 21
Vehicles used: 2/2
Customers served: 5The objective value represents the sum of all arc costs used in the routes, corresponding to our mathematical objective function . The solution assigns customers to vehicles such that all capacity constraints are satisfied (each vehicle carries at most 8 units of demand) and all time windows are respected. Finding a feasible solution confirms that all constraints can be satisfied simultaneously for this problem instance.
Let's visualize the solution to see how vehicles are assigned to customers:
def visualize_solution(solution, routing, manager, data, routes):
"""Visualize the VRPTW solution.
This visualization displays the routes found by the solver,
showing which arcs are used (where x_{ijk} = 1) and how
vehicles are assigned to customers.
"""
use_mls_style()
fig, ax = plt.subplots(1, 1, figsize=(7.2, 4.8))
# Customer locations (simplified 2D coordinates for visualization)
locations = [
(0, 0), # Depot
(2, 3), # Customer 1
(4, 1), # Customer 2
(6, 4), # Customer 3
(8, 2), # Customer 4
(10, 5), # Customer 5
]
# Plot depot
ax.scatter(
locations[0][0],
locations[0][1],
c=PALETTE["coral"],
edgecolors=PALETTE["ink"],
linewidths=0.8,
s=120,
marker="s",
label="Depot",
zorder=5,
)
# Plot customers
for i in range(1, len(locations)):
ax.scatter(
locations[i][0],
locations[i][1],
c=PALETTE["primary"],
edgecolors=PALETTE["ink"],
linewidths=0.6,
s=64,
label=f"Customer {i}" if i == 1 else "",
)
# Draw routes
colors = [PALETTE["teal"], PALETTE["amber"], PALETTE["purple"]]
for vehicle_id, route in enumerate(routes):
color = colors[vehicle_id]
for i in range(len(route) - 1):
start_pos = locations[route[i]]
end_pos = locations[route[i + 1]]
ax.plot(
[start_pos[0], end_pos[0]],
[start_pos[1], end_pos[1]],
color=color,
linewidth=3,
alpha=0.8,
label=f"Vehicle {vehicle_id + 1}" if i == 0 else "",
)
# Add arrow
mid_x = (start_pos[0] + end_pos[0]) / 2
mid_y = (start_pos[1] + end_pos[1]) / 2
dx = end_pos[0] - start_pos[0]
dy = end_pos[1] - start_pos[1]
ax.arrow(
mid_x,
mid_y,
dx * 0.1,
dy * 0.1,
head_width=0.2,
head_length=0.2,
fc=color,
ec=color,
alpha=0.8,
)
# Add customer labels
for i, (x, y) in enumerate(locations[1:], 1):
ax.annotate(
f"C{i}",
(x, y),
xytext=(5, 5),
textcoords="offset points",
fontsize=9,
color=PALETTE["ink"],
bbox=dict(
boxstyle="round,pad=0.25",
facecolor=PALETTE["paper"],
edgecolor=PALETTE["grid"],
alpha=0.9,
),
)
ax.set_xlabel("X Coordinate")
ax.set_ylabel("Y Coordinate")
ax.set_title("VRPTW Solution Visualization")
ax.legend()
polish_axes(ax)
fig.subplots_adjust(left=0.10, right=0.98, bottom=0.12, top=0.90)
plt.show()
# Visualize the solution
if solution:
visualize_solution(solution, routing, manager, data, routes)
The visualization shows how vehicles are assigned to serve customers. Each colored line represents a vehicle's route, starting and ending at the depot (red square). The routes minimize total travel distance while respecting capacity constraints and time windows. Customers appearing on the same colored path are served by a single vehicle.
Alternative Implementation: Custom Heuristic
While OR-Tools uses sophisticated constraint programming to find optimal or near-optimal solutions, it's instructive to implement a simple greedy heuristic. This approach makes decisions sequentially rather than exploring the full solution space, and it helps illustrate how the constraints guide decision-making. The heuristic doesn't explicitly solve for all variables simultaneously; instead, it builds routes incrementally, checking constraints as it goes. This is much faster but may not find optimal solutions.
The heuristic still respects the same constraints: each customer is visited exactly once (by construction), capacity limits are checked before adding customers, time windows are verified before assignment, and temporal logic is maintained through arrival time tracking.
def greedy_vrptw_heuristic(data):
"""Simple greedy heuristic for VRPTW.
This heuristic builds routes incrementally by choosing the
closest feasible customer at each step. It implements all major constraints
but uses a greedy strategy rather than global optimization.
Key insight: vehicles can WAIT if they arrive early at a customer.
The arrival time becomes max(travel_arrival, window_start).
"""
num_vehicles = data["num_vehicles"]
num_customers = len(data["distance_matrix"]) - 1
vehicle_capacities = data["vehicle_capacities"] # Q_k
demands = data["demands"] # d_i (includes depot at index 0)
time_windows = data["time_windows"] # [a_i, b_i] (includes depot)
service_times = data["service_times"] # s_i
distances = data["distance_matrix"] # t_{ij} (also used as travel times)
depot_close = time_windows[0][1] # Latest return time to depot
# Initialize routes and tracking variables
routes = [[] for _ in range(num_vehicles)]
route_capacities = [0] * num_vehicles # Cumulative demand (Constraint 2)
route_current_times = [0] * num_vehicles # Current time for each vehicle
unvisited = list(range(1, num_customers + 1)) # Customers not yet assigned
# Greedy assignment: repeatedly find the best customer-vehicle pair
while unvisited:
best_vehicle = None
best_customer = None
best_cost = float("inf")
best_arrival_time = None
for vehicle_id in range(num_vehicles):
# Skip vehicles at capacity
if route_capacities[vehicle_id] >= vehicle_capacities[vehicle_id]:
continue
for customer in unvisited:
# Constraint 2: Check capacity feasibility
if (
route_capacities[vehicle_id] + demands[customer]
> vehicle_capacities[vehicle_id]
):
continue
# Calculate arrival time at this customer
current_pos = (
0 if not routes[vehicle_id] else routes[vehicle_id][-1]
)
current_time = route_current_times[vehicle_id]
travel_time = distances[current_pos][customer]
earliest_arrival = current_time + travel_time
# If we arrive early, we wait until window opens
actual_arrival = max(
earliest_arrival, time_windows[customer][0]
)
# Constraint 4: Check if we can arrive before window closes
if actual_arrival > time_windows[customer][1]:
continue
# Check if we can return to depot on time after serving this customer
departure_time = actual_arrival + service_times[customer]
return_time = departure_time + distances[customer][0]
if return_time > depot_close:
continue
# Greedy choice: prefer closer customers (lower travel cost)
cost = travel_time
if cost < best_cost:
best_cost = cost
best_vehicle = vehicle_id
best_customer = customer
best_arrival_time = actual_arrival
if best_vehicle is not None:
# Add customer to route
routes[best_vehicle].append(best_customer)
route_capacities[best_vehicle] += demands[best_customer]
# Update time: arrival + service time = ready for next customer
route_current_times[best_vehicle] = (
best_arrival_time + service_times[best_customer]
)
unvisited.remove(best_customer)
else:
break # No feasible assignment found
return routes, unvisited
# Test the heuristic with the same data as OR-Tools
data_heuristic = create_data_model()
heuristic_routes, unserved = greedy_vrptw_heuristic(data_heuristic)
# Calculate route statistics
heuristic_route_strings = []
heuristic_total_customers = 0
heuristic_total_distance = 0
for i, route in enumerate(heuristic_routes):
if route:
# Calculate total distance for this route
route_distance = data_heuristic["distance_matrix"][0][
route[0]
] # Depot to first
for j in range(len(route) - 1):
route_distance += data_heuristic["distance_matrix"][route[j]][
route[j + 1]
]
route_distance += data_heuristic["distance_matrix"][route[-1]][
0
] # Last to depot
route_str = f"Depot -> {' -> '.join([f'C{c}' for c in route])} -> Depot"
heuristic_route_strings.append(
(i + 1, route_str, len(route), route_distance)
)
heuristic_total_customers += len(route)
heuristic_total_distance += route_distance
else:
heuristic_route_strings.append((i + 1, "No customers assigned", 0, 0))Display the heuristic solution and compare with OR-Tools:
Greedy Heuristic Solution:
--------------------------------------------------
Vehicle 1: Depot -> C1 -> C2 -> C3 -> C4 -> Depot
(customers: 4, distance: 13)
Vehicle 2: Depot -> C5 -> Depot
(customers: 1, distance: 12)
Summary:
Customers served: 5/5
Total distance: 25
Comparison with OR-Tools:
OR-Tools distance: 21
Heuristic distance: 25
Optimality gap: 19.0%The greedy heuristic builds routes incrementally by always choosing the nearest feasible customer. The key insight is that vehicles can wait if they arrive before a time window opens, so early arrival doesn't disqualify a customer. At each step, the algorithm checks: (1) capacity constraints, (2) time window feasibility, and (3) whether the vehicle can return to the depot on time after serving the customer.
Comparing the heuristic to OR-Tools reveals the cost of greedy decision-making. The heuristic finds a feasible solution quickly but typically produces routes that are longer than optimal. This is because locally optimal choices (picking the nearest customer) don't always lead to globally optimal solutions. OR-Tools explores the full solution space using constraint propagation and metaheuristics, finding better route combinations that the greedy approach misses.
Key Parameters
Below are the main parameters that affect how the VRPTW solver works and performs.
-
first_solution_strategy: Heuristic for generating the initial solution.PATH_CHEAPEST_ARC(default) builds routes by selecting the cheapest arc at each step.SAVINGSuses Clarke-Wright savings algorithm.CHRISTOFIDESuses Christofides algorithm for TSP components. -
local_search_metaheuristic: Metaheuristic for improving the initial solution.GUIDED_LOCAL_SEARCH(recommended) balances exploration and exploitation.TABU_SEARCHavoids revisiting solutions.SIMULATED_ANNEALINGprobabilistically accepts worse solutions to escape local optima. -
time_limit.seconds: Maximum solver time (default: unlimited). Use 30-60 seconds for 50-100 customers, 2-5 minutes for larger problems, 10-30 seconds for real-time dispatch. -
vehicle_capacities: List of capacity limits per vehicle. Supports homogeneous (all same) or heterogeneous fleets. Total capacity must exceed total customer demand. -
distance_matrix: Travel times or distances between all locations. Use actual road network values rather than Euclidean distances. Should be symmetric for undirected problems. -
time_windows: Tuples(earliest, latest)defining for each location. Depot window defines operational hours. Customer windows must be reachable from depot. -
service_times: Duration spent at each location (excluding travel). Use realistic estimates. Underestimating causes downstream time window violations. Depot service time is typically 0. -
demands: Demand at each location. Depot has demand 0. Total demand should be less than total vehicle capacity with margin.
Key Methods
The following are the most commonly used methods for working with OR-Tools routing models.
-
RoutingIndexManager(num_nodes, num_vehicles, depot): Creates an index manager mapping between node indices and routing indices. The depot (typically 0) is start/end point for all routes. -
RoutingModel(manager): Creates the main routing model that manages decision variables and constraints. -
RegisterTransitCallback(callback): Registers a binary callback returning cost/time to travel between two nodes. Used for distance and time dimensions. -
RegisterUnaryTransitCallback(callback): Registers a unary callback for single-node operations like demand pickup. Used for capacity dimensions. -
AddDimension(callback, slack_max, capacity, fix_start_cumul_to_zero, name): Adds a cumulative dimension (time, capacity) to the model. The callback defines accumulation; slack_max and capacity define bounds. -
AddDimensionWithVehicleCapacity(callback, slack, capacities, fix_start_cumul_to_zero, name): LikeAddDimensionbut with per-vehicle capacity limits. Use for heterogeneous fleets. -
SolveWithParameters(search_parameters): Solves the problem with specified search parameters. Returns solution object orNoneif infeasible. -
solution.ObjectiveValue(): Returns the objective value (total cost) of the solution: . -
solution.Value(routing.NextVar(index)): Returns the next node in the route. Use to trace complete routes for each vehicle.