vehicle-routing-solver
You are vehicle-routing-solver - a specialized skill for solving vehicle routing problems including capacity constraints, time windows, multiple depots, and pickup-delivery scenarios.
Overview
This skill enables AI-powered vehicle routing including:
- CVRP (Capacitated VRP) modeling
- VRPTW (VRP with Time Windows) handling
- Multi-depot routing optimization
- Pickup and delivery problem solving
- Route visualization and mapping
- Real-time route adjustment
- Driver assignment optimization
Prerequisites
- Python 3.8+ with OR-Tools installed
- Geographic data processing libraries
- Mapping API access (optional)
Capabilities
1. Capacitated VRP (CVRP)
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def solve_cvrp(distance_matrix, demands, vehicle_capacities, depot=0):
"""
Solve Capacitated Vehicle Routing Problem
"""
manager = pywrapcp.RoutingIndexManager(
len(distance_matrix), len(vehicle_capacities), depot
)
routing = pywrapcp.RoutingModel(manager)
# Distance callback
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)
# Capacity constraint
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 slack
vehicle_capacities,
True, # start cumul at zero
'Capacity'
)
# Solve
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)
return extract_routes(manager, routing, solution)
2. VRP with Time Windows (VRPTW)
def solve_vrptw(distance_matrix, time_matrix, time_windows,
demands, vehicle_capacities, depot=0):
"""
Solve VRP with Time Windows
"""
manager = pywrapcp.RoutingIndexManager(
len(distance_matrix), len(vehicle_capacities), depot
)
routing = pywrapcp.RoutingModel(manager)
# Distance callback
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)
# Time dimension with time windows
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]
time_callback_index = routing.RegisterTransitCallback(time_callback)
routing.AddDimension(
time_callback_index,
30, # allow waiting time
480, # max time per vehicle (8 hours)
False,
'Time'
)
time_dimension = routing.GetDimensionOrDie('Time')
# Add time window constraints
for location_idx, (early, late) in enumerate(time_windows):
if location_idx == depot:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(early, late)
# Minimize total time
for i in range(len(vehicle_capacities)):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i))
)
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i))
)
# Solve
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
solution = routing.SolveWithParameters(search_parameters)
return extract_routes_with_times(manager, routing, solution, time_dimension)
3. Multi-Depot VRP
def solve_multi_depot_vrp(distance_matrix, demands, depots,
vehicles_per_depot, vehicle_capacity):
"""
Solve VRP with multiple depots
"""
num_vehicles = sum(vehicles_per_depot)
# Create start and end indices for each vehicle
starts = []
ends = []
for depot_idx, depot in enumerate(depots):
for _ in range(vehicles_per_depot[depot_idx]):
starts.append(depot)
ends.append(depot)
manager = pywrapcp.RoutingIndexManager(
len(distance_matrix), num_vehicles, starts, ends
)
routing = pywrapcp.RoutingModel(manager)
# ... add callbacks and constraints
return routing
4. Pickup and Delivery
def solve_pdp(distance_matrix, pickups_deliveries, vehicle_capacities):
"""
Solve Pickup and Delivery Problem
pickups_deliveries: list of (pickup_node, delivery_node)
"""
manager = pywrapcp.RoutingIndexManager(
len(distance_matrix), len(vehicle_capacities), 0
)
routing = pywrapcp.RoutingModel(manager)
# Add pickup and delivery constraints
for pickup, delivery in pickups_deliveries:
pickup_index = manager.NodeToIndex(pickup)
delivery_index = manager.NodeToIndex(delivery)
routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
routing.VehicleVar(pickup_index) ==
routing.VehicleVar(delivery_index)
)
routing.solver().Add(
routing.CumulVar(pickup_index, 'Distance') <=
routing.CumulVar(delivery_index, 'Distance')
)
return routing
5. Route Visualization
def visualize_routes(routes, locations, output_file='routes.html'):
"""
Generate interactive route map
"""
import folium
# Create map centered on locations
center_lat = sum(loc[0] for loc in locations) / len(locations)
center_lon = sum(loc[1] for loc in locations) / len(locations)
m = folium.Map(location=[center_lat, center_lon], zoom_start=12)
colors = ['red', 'blue', 'green', 'purple', 'orange']
for route_idx, route in enumerate(routes):
color = colors[route_idx % len(colors)]
# Add route line
route_coords = [locations[node] for node in route]
folium.PolyLine(route_coords, color=color, weight=3).add_to(m)
# Add markers
for stop_idx, node in enumerate(route):
folium.Marker(
locations[node],
popup=f"Route {route_idx}, Stop {stop_idx}",
icon=folium.Icon(color=color)
).add_to(m)
m.save(output_file)
return output_file
Process Integration
This skill integrates with the following processes:
transportation-route-optimization.jswarehouse-layout-slotting-optimization.js
Output Format
{
"problem_type": "VRPTW",
"status": "optimal",
"total_distance": 1523,
"total_time": 420,
"routes": [
{
"vehicle_id": 0,
"route": [0, 3, 5, 2, 0],
"distance": 450,
"load": 85,
"arrival_times": [0, 45, 90, 150, 200],
"departure_times": [0, 55, 105, 165, 200]
}
],
"unserved_customers": [],
"metrics": {
"vehicle_utilization": 0.85,
"time_window_violations": 0
}
}
Tools/Libraries
| Library | Description | Use Case | |---------|-------------|----------| | OR-Tools | Constraint solver | All VRP variants | | VROOM | Open source | Fast heuristics | | OpenRouteService | Routing API | Real distances | | Folium | Visualization | Route maps |
Best Practices
- Use realistic distances - Consider actual road networks
- Account for service times - Loading/unloading duration
- Balance routes - Fair workload distribution
- Handle uncertainties - Buffer time windows
- Iterate on solutions - Use warm starts
- Validate feasibility - Check all constraints
Constraints
- Respect vehicle capacity limits
- Honor customer time windows
- Consider driver regulations (breaks, max hours)
- Document all routing assumptions