solve_traveling_salesman_problem
Find the shortest route to visit all specified locations, optimizing travel distance for logistics and planning.
Instructions
Solve Traveling Salesman Problem (TSP) to find the shortest route visiting all locations.
Args:
locations: List of location dictionaries with name and coordinates
distance_matrix: Optional pre-calculated distance matrix
start_location: Index of starting location (default: 0)
return_to_start: Whether to return to starting location (default: True)
time_limit_seconds: Maximum solving time in seconds (default: 30.0)
Returns:
Optimization result with route and total distance
Input Schema
TableJSON Schema
| Name | Required | Description | Default |
|---|---|---|---|
| locations | Yes | ||
| distance_matrix | No | ||
| start_location | No | ||
| return_to_start | No | ||
| time_limit_seconds | No |
Implementation Reference
- The MCP tool handler function 'solve_traveling_salesman_problem' that wraps input data into TSPInput schema, calls the core solver, and returns the result as dict.
@mcp.tool() def solve_traveling_salesman_problem( locations: list[dict[str, Any]], distance_matrix: list[list[float]] | None = None, start_location: int = 0, return_to_start: bool = True, time_limit_seconds: float = 30.0, ) -> dict[str, Any]: """Solve Traveling Salesman Problem (TSP) to find the shortest route visiting all locations. Args: locations: List of location dictionaries with name and coordinates distance_matrix: Optional pre-calculated distance matrix start_location: Index of starting location (default: 0) return_to_start: Whether to return to starting location (default: True) time_limit_seconds: Maximum solving time in seconds (default: 30.0) Returns: Optimization result with route and total distance """ input_data = { "locations": locations, "distance_matrix": distance_matrix, "start_location": start_location, "return_to_start": return_to_start, "time_limit_seconds": time_limit_seconds, } result = solve_traveling_salesman(input_data) result_dict: dict[str, Any] = result.model_dump() return result_dict - Core helper function implementing the TSP algorithm using OR-Tools constraint solver, handling distance matrix, routing model, and solution extraction.
@with_resource_limits(timeout_seconds=120.0, estimated_memory_mb=150.0) def solve_traveling_salesman(input_data: dict[str, Any]) -> OptimizationResult: """Solve Traveling Salesman Problem using OR-Tools. Args: input_data: TSP problem specification Returns: OptimizationResult with route and total distance """ 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 tsp_input = TSPInput(**input_data) locations = tsp_input.locations n_locations = len(locations) if n_locations < 2: return OptimizationResult( status=OptimizationStatus.ERROR, error_message="At least 2 locations required for TSP", execution_time=time.time() - start_time, ) # Get or calculate distance matrix if tsp_input.distance_matrix: distance_matrix = tsp_input.distance_matrix if len(distance_matrix) != n_locations or any( len(row) != n_locations for row in distance_matrix ): return OptimizationResult( status=OptimizationStatus.ERROR, error_message="Distance matrix dimensions don't match number of locations", execution_time=time.time() - start_time, ) else: distance_matrix = calculate_distance_matrix(locations) # type: ignore # Create routing model manager = pywrapcp.RoutingIndexManager(n_locations, 1, tsp_input.start_location) 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) # Scale for integer transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 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(tsp_input.time_limit_seconds) # Solve solution = routing.SolveWithParameters(search_parameters) if solution: # Extract route route = [] total_distance = 0.0 index = routing.Start(0) while not routing.IsEnd(index): node = manager.IndexToNode(index) route.append( { "location": locations[node].name, "index": node, "coordinates": { "lat": locations[node].lat, "lng": locations[node].lng, "x": locations[node].x, "y": locations[node].y, }, } ) 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) total_distance += distance_matrix[from_node][to_node] # Add final location if returning to start if tsp_input.return_to_start: final_node = manager.IndexToNode(index) route.append( { "location": locations[final_node].name, "index": final_node, "coordinates": { "lat": locations[final_node].lat, "lng": locations[final_node].lng, "x": locations[final_node].x, "y": locations[final_node].y, }, } ) # Add distance back to start if len(route) > 1: last_node = route[-2]["index"] start_node = route[-1]["index"] total_distance += distance_matrix[last_node][start_node] execution_time = time.time() - start_time return OptimizationResult( status=OptimizationStatus.OPTIMAL, objective_value=total_distance, variables={ "route": route, "total_distance": total_distance, "num_locations": len(route), }, execution_time=execution_time, solver_info={ "solver_name": "OR-Tools Routing", "search_strategy": "PATH_CHEAPEST_ARC", }, ) 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"TSP solving error: {str(e)}", execution_time=time.time() - start_time, ) - Pydantic model defining the input schema for TSP, including locations list, optional distance matrix, start location, etc., with validation.
class TSPInput(BaseModel): """Input schema for Traveling Salesman Problem.""" locations: list[Location] distance_matrix: list[list[float]] | None = None start_location: int = Field(default=0, ge=0) return_to_start: bool = True time_limit_seconds: float = Field(default=30.0, ge=0) @field_validator("start_location") @classmethod def validate_start_location(cls, v: int, info: ValidationInfo) -> int: if info.data and "locations" in info.data and v >= len(info.data["locations"]): raise ValueError("start_location must be a valid location index") return v - Pydantic model for individual locations used in TSP/VRP inputs, supporting lat/lng or x/y coordinates.
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)Registration call in the main MCP server setup that adds the solve_traveling_salesman_problem tool via register_routing_tools.
register_routing_tools(mcp)