solve_routing_problem

Solve vehicle routing problems (TSP/VRP) with optimal route planning.

Find optimal routes for vehicles visiting locations. Supports single-vehicle TSP, multi-vehicle VRP with capacity constraints, and multiple optimization objectives.

Args: locations: List of locations to visit, each with: - id: Unique identifier (required) - coordinates: (x, y) tuple for Euclidean distance (optional if distance_matrix provided) - demand: Load to pick up at this location (default 0) - service_time: Time spent at location in minutes (default 0) vehicles: List of vehicles (optional, defaults to single vehicle if omitted): - id: Vehicle identifier (required) - capacity: Maximum load capacity (default unlimited) - start_location: Starting location ID (required) - cost_per_distance: Cost per unit distance (default 1.0) - fixed_cost: Fixed cost if vehicle is used (default 0.0) distance_matrix: Optional distance matrix [i][j] = distance from location i to j. If omitted, uses Euclidean distance from coordinates. objective: Optimization goal (default "minimize_distance"): - "minimize_distance": Shortest total route length - "minimize_time": Shortest total time (distance + service times) - "minimize_cost": Lowest total cost (fixed + distance costs) - "minimize_vehicles": Use fewest vehicles possible max_time_ms: Solver time limit in milliseconds (default 60000)

Returns: SolveRoutingProblemResponse with: - status: OPTIMAL, FEASIBLE, or INFEASIBLE - routes: List of routes, each with vehicle_id, sequence of location IDs, total_distance, load_timeline - total_distance: Sum of all route distances - total_cost: Total cost across all routes - vehicles_used: Number of vehicles actually used - explanation: Human-readable summary

Tips for LLMs: - TSP (single vehicle): Omit vehicles parameter or provide one vehicle - VRP (multiple vehicles): Provide multiple vehicles with capacity limits - Capacity constraints: Set demand per location and capacity per vehicle - Use coordinates for geographic routing (automatically calculates distances) - Use distance_matrix when you have pre-computed distances or non-Euclidean metrics - minimize_vehicles: When you want to use as few vehicles as possible - minimize_cost: When vehicles have different costs (e.g., small truck vs large truck) - First location in route sequence is always the start location - Routes automatically return to start location (depot)

Example - Simple TSP: response = await solve_routing_problem( locations=[ {"id": "warehouse", "coordinates": (0, 0)}, {"id": "store_A", "coordinates": (10, 5)}, {"id": "store_B", "coordinates": (5, 10)}, ] ) # Single vehicle visits all locations, returns to warehouse

Example - Multi-Vehicle VRP: response = await solve_routing_problem( locations=[ {"id": "depot", "coordinates": (0, 0), "demand": 0}, {"id": "customer_1", "coordinates": (10, 5), "demand": 15}, {"id": "customer_2", "coordinates": (5, 10), "demand": 20}, {"id": "customer_3", "coordinates": (15, 15), "demand": 25}, ], vehicles=[ {"id": "truck_1", "capacity": 50, "start_location": "depot"}, {"id": "truck_2", "capacity": 40, "start_location": "depot"}, ], objective="minimize_distance" ) # Returns optimal routes respecting capacity limits

Example - Minimize Fleet Size: response = await solve_routing_problem( locations=[...], # 10 customers vehicles=[ {"id": "truck_1", "capacity": 100, "start_location": "depot"}, {"id": "truck_2", "capacity": 100, "start_location": "depot"}, {"id": "truck_3", "capacity": 100, "start_location": "depot"}, ], objective="minimize_vehicles" ) # Uses minimum number of trucks needed to serve all customers