solve_vehicle_routing_problem
Optimize routes for multiple vehicles to efficiently serve multiple locations with capacity constraints.
Instructions
Solve Vehicle Routing Problem (VRP) to optimize routes for multiple vehicles.
Args:
locations: List of location dictionaries with name, coordinates, and demand
vehicles: List of vehicle dictionaries with capacity constraints
distance_matrix: Optional pre-calculated distance matrix
time_matrix: Optional pre-calculated time matrix
depot: Index of depot location (default: 0)
time_limit_seconds: Maximum solving time in seconds (default: 30.0)
Returns:
Optimization result with routes for all vehicles
Input Schema
TableJSON Schema
| Name | Required | Description | Default |
|---|---|---|---|
| locations | Yes | ||
| vehicles | Yes | ||
| distance_matrix | No | ||
| time_matrix | No | ||
| depot | No | ||
| time_limit_seconds | No |
Implementation Reference
- The @mcp.tool() decorated handler function for 'solve_vehicle_routing_problem' that validates input, calls the core VRP solver, and returns the result as a dictionary.def solve_vehicle_routing_problem( locations: list[dict[str, Any]], vehicles: list[dict[str, Any]], distance_matrix: list[list[float]] | None = None, time_matrix: list[list[int]] | None = None, depot: int = 0, time_limit_seconds: float = 30.0, ) -> dict[str, Any]: """Solve Vehicle Routing Problem (VRP) to optimize routes for multiple vehicles. Args: locations: List of location dictionaries with name, coordinates, and demand vehicles: List of vehicle dictionaries with capacity constraints distance_matrix: Optional pre-calculated distance matrix time_matrix: Optional pre-calculated time matrix depot: Index of depot location (default: 0) time_limit_seconds: Maximum solving time in seconds (default: 30.0) Returns: Optimization result with routes for all vehicles """ input_data = { "locations": locations, "vehicles": vehicles, "distance_matrix": distance_matrix, "time_matrix": time_matrix, "depot": depot, "time_limit_seconds": time_limit_seconds, } result = solve_vehicle_routing(input_data) result_dict: dict[str, Any] = result.model_dump() return result_dict
- Core helper function implementing the Vehicle Routing Problem solver using OR-Tools constraint programming solver. Handles model creation, constraints, solving, and result extraction.@with_resource_limits(timeout_seconds=180.0, estimated_memory_mb=150.0) def solve_vehicle_routing(input_data: dict[str, Any]) -> OptimizationResult: """Solve Vehicle Routing Problem using OR-Tools. Args: input_data: VRP problem specification Returns: OptimizationResult with routes for all vehicles """ if not ORTOOLS_AVAILABLE: return OptimizationResult( status=OptimizationStatus.ERROR, objective_value=None, variables={}, execution_time=0.0, error_message="OR-Tools is not available. Please install it with 'pip install ortools'", ) start_time = time.time() try: # Parse and validate input vrp_input = VRPInput(**input_data) locations = vrp_input.locations vehicles = vrp_input.vehicles n_locations = len(locations) n_vehicles = len(vehicles) if n_locations < 2: return OptimizationResult( status=OptimizationStatus.ERROR, error_message="At least 2 locations required for VRP", execution_time=time.time() - start_time, ) if n_vehicles < 1: return OptimizationResult( status=OptimizationStatus.ERROR, error_message="At least 1 vehicle required for VRP", execution_time=time.time() - start_time, ) # Get or calculate distance matrix if vrp_input.distance_matrix: distance_matrix = vrp_input.distance_matrix else: distance_matrix = calculate_distance_matrix(locations) # type: ignore # Create routing model manager = pywrapcp.RoutingIndexManager(n_locations, n_vehicles, vrp_input.depot) routing = pywrapcp.RoutingModel(manager) # Create distance callback def distance_callback(from_index: int, to_index: int) -> int: from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return int(distance_matrix[from_node][to_node] * 1000) transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add capacity constraints demands = [int(loc.demand) for loc in locations] def demand_callback(from_index: int) -> int: from_node = manager.IndexToNode(from_index) return int(demands[from_node]) demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) # Set vehicle capacities vehicle_capacities = [int(vehicle.capacity) for vehicle in vehicles] routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack vehicle_capacities, # vehicle maximum capacities True, # start cumul to zero "Capacity", ) # Set search parameters search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) search_parameters.time_limit.seconds = int(vrp_input.time_limit_seconds) # Solve solution = routing.SolveWithParameters(search_parameters) if solution: # Extract routes for all vehicles routes = [] total_distance = 0.0 total_load = 0.0 for vehicle_id in range(n_vehicles): route = [] route_distance = 0.0 route_load = 0.0 index = routing.Start(vehicle_id) while not routing.IsEnd(index): node = manager.IndexToNode(index) route.append( { "location": locations[node].name, "index": node, "demand": locations[node].demand, "coordinates": { "lat": locations[node].lat, "lng": locations[node].lng, "x": locations[node].x, "y": locations[node].y, }, } ) route_load += locations[node].demand previous_index = index index = solution.Value(routing.NextVar(index)) if not routing.IsEnd(index): from_node = manager.IndexToNode(previous_index) to_node = manager.IndexToNode(index) route_distance += distance_matrix[from_node][to_node] # Add return to depot if route: depot_node = manager.IndexToNode(routing.End(vehicle_id)) if route[-1]["index"] != depot_node: route.append( { "location": locations[depot_node].name, "index": depot_node, "demand": locations[depot_node].demand, "coordinates": { "lat": locations[depot_node].lat, "lng": locations[depot_node].lng, "x": locations[depot_node].x, "y": locations[depot_node].y, }, } ) # Add distance back to depot last_node = route[-2]["index"] route_distance += distance_matrix[last_node][depot_node] if len(route) > 1: # Only include routes with actual stops routes.append( { "vehicle_id": vehicle_id, "route": route, "distance": route_distance, "load": route_load, "capacity": vehicles[vehicle_id].capacity, "utilization": route_load / vehicles[vehicle_id].capacity if vehicles[vehicle_id].capacity > 0 else 0, } ) total_distance += route_distance total_load += route_load execution_time = time.time() - start_time return OptimizationResult( status=OptimizationStatus.OPTIMAL, objective_value=total_distance, variables={ "routes": routes, "total_distance": total_distance, "total_load": total_load, "num_vehicles_used": len(routes), "num_locations_served": sum( len(route_data["route"]) - 1 # type: ignore[misc,arg-type] for route_data in routes if isinstance(route_data, dict) and "route" in route_data ), # Exclude depot returns }, execution_time=execution_time, solver_info={ "solver_name": "OR-Tools Routing", "search_strategy": "PATH_CHEAPEST_ARC", "vehicles_available": n_vehicles, }, ) else: return OptimizationResult( status=OptimizationStatus.INFEASIBLE, error_message="No solution found within time limit", execution_time=time.time() - start_time, ) except Exception as e: return OptimizationResult( status=OptimizationStatus.ERROR, error_message=f"VRP solving error: {str(e)}", execution_time=time.time() - start_time, )
- Pydantic BaseModel schema defining the input structure and validation for the VRP tool, including locations, vehicles, matrices, and depot validation.class VRPInput(BaseModel): """Input schema for Vehicle Routing Problem.""" locations: list[Location] vehicles: list[Vehicle] distance_matrix: list[list[float]] | None = None time_matrix: list[list[int]] | None = None depot: int = Field(default=0, ge=0) time_limit_seconds: float = Field(default=30.0, ge=0) @field_validator("depot") @classmethod def validate_depot(cls, v: int, info: ValidationInfo) -> int: if info.data and "locations" in info.data and v >= len(info.data["locations"]): raise ValueError("depot must be a valid location index") return v
- Supporting Pydantic schema for individual locations used in VRP input, with coordinates, demand, and time window validation.class Location(BaseModel): """Location with coordinates and optional properties.""" name: str lat: float | None = None lng: float | None = None x: float | None = None y: float | None = None demand: float = Field(default=0.0, ge=0) time_window: tuple[int, int] | None = None service_time: int = Field(default=0, ge=0) @field_validator("time_window") @classmethod def validate_time_window(cls, v: tuple[int, int] | None) -> tuple[int, int] | None: if v is not None and v[0] >= v[1]: raise ValueError("Time window start must be before end") return v
- src/mcp_optimizer/mcp_server.py:141-141 (registration)Invocation of the register_routing_tools function during MCP server creation, which registers the solve_vehicle_routing_problem tool.register_routing_tools(mcp)