AgentSkillsCN

traveling-salesman-solver

当用户需要为多个地点规划最优的游览顺序，以最大限度地缩短总行程距离或总耗时时，该技能会分析距离矩阵，求解旅行商问题（TSP）。它会评估各地点的排列组合，找出一条能够遍历所有点的最短路线。触发条件包括“最优路线”“遍历所有点的最短路径”“最佳游览顺序”，或当需要对包含多个停靠点的路线进行优化时。

SKILL.md
--- frontmatter
name: traveling-salesman-solver
description: When the user needs to find the optimal visiting order for multiple locations to minimize total travel distance or time, this skill analyzes distance matrices to solve the Traveling Salesman Problem (TSP). It evaluates permutations of locations to identify the shortest route that visits all points. Triggers include 'optimal route', 'shortest path visiting all', 'best visiting order', or when route optimization with multiple stops is required.

Instructions

Core Workflow

  1. •Identify Locations & Starting Point: Determine the user's starting location and the list of all destinations that must be visited. Extract these from user request or provided files (e.g., recommendation.md).
  2. •Geocode Locations: Obtain precise coordinates for all locations using mapping tools (maps_geocode, maps_search_places).
  3. •Build Distance Matrix: Calculate pairwise walking (or specified mode) distances and times between all locations using maps_distance_matrix.
  4. •Solve TSP: Analyze the distance matrix to find the permutation of destinations that minimizes total travel distance/time from the starting point. For small sets (n ≤ 7), manual permutation analysis is acceptable. For larger sets, use the provided tsp_solver.py script.
  5. •Generate Detailed Route: For each leg of the optimal route, fetch turn-by-turn walking directions using maps_directions.
  6. •Format & Deliver Output: Compile the final route plan into the user's requested format (e.g., JSON matching a template like format.json). Save the file and present a clear summary.

Key Considerations

  • •Clarify Constraints: Confirm with the user if the route must start/end at specific points, and if visiting time at locations matters (usually it doesn't for pure TSP).
  • •Handle Proximity: Treat very close locations (e.g., statue and building entrance) as separate stops if the user requires it, even if it slightly increases calculated distance.
  • •Validation: After writing the output file, read it back to verify its contents and structure.
  • •Assumptions: The skill assumes travel cost is symmetric and based on network distance/time (walking by default). Real-world constraints like one-way streets are handled by the mapping API.