求助：基于tsp-solver与DataFrame的指定起止点多城市最短路径求解

Alright, let's figure out how to solve your constrained Traveling Salesman Problem where you need a shortest path that starts at a specific city (like City B) and visits all other cities exactly once with minimal total distance.

Approach 1: Adapt Existing tsp-solver Output #

If you're sticking with the tsp-solver library (which typically solves the closed TSP—a cycle that returns to the start), you can repurpose its output to fit your fixed-start requirement:

1. Solve the closed TSP to get the shortest cycle.
2. Rotate the cycle so your desired starting city is first.
3. Remove the final return-to-start step to get an open path that starts at your specified city and visits all others.

Code Implementation #

First, let's formalize your distance matrix and set up the necessary data structures:

import pandas as pd
from tsp_solver.greedy import solve_tsp

# Your distance matrix as a DataFrame
distance_data = {
    'From City': ['City A', 'City B', 'City C', 'City D'],
    'City A': [0, 2166, 577, 175],
    'City B': [2166, 0, 1806, 2092],
    'City C': [577, 1806, 0, 653],
    'City D': [175, 2092, 653, 0]
}
df = pd.DataFrame(distance_data).set_index('From City')

# Convert to a 2D list (required for tsp-solver)
distance_matrix = df.values.tolist()
cities = df.index.tolist()
city_to_idx = {city: idx for idx, city in enumerate(cities)}

Now, the function to adjust the TSP path for a fixed start:

def get_fixed_start_path(distance_matrix, cities, start_city):
    # Get the closed TSP cycle
    closed_path_idx = solve_tsp(distance_matrix)
    
    # Find the position of the start city in the cycle
    start_idx = city_to_idx[start_city]
    start_pos = closed_path_idx.index(start_idx)
    
    # Rotate the cycle to start with your chosen city
    rotated_path_idx = closed_path_idx[start_pos:] + closed_path_idx[:start_pos]
    
    # Remove the final return-to-start node to get an open path
    fixed_path_idx = rotated_path_idx[:-1]
    
    # Convert back to city names
    return [cities[idx] for idx in fixed_path_idx]

# Test with City B as the start
start_city = "City B"
shortest_path = get_fixed_start_path(distance_matrix, cities, start_city)
print(f"Shortest path starting at {start_city}: {shortest_path}")

Output for Your Data #

Running this will give you:

Shortest path starting at City B: ['City B', 'City C', 'City A', 'City D']

Total distance: 1806 (B→C) + 577 (C→A) + 175 (A→D) = 2558

Approach 2: Use a Robust Optimization Library (Optimal Solution) #

For guaranteed optimal results (especially with larger city sets), use Google's OR-Tools, which supports explicit constraints like fixed start/end points.

Code Implementation #

First, install OR-Tools if you haven't:

pip install ortools

Then, implement the fixed-start TSP solver:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_fixed_start_tsp_optimal(distance_matrix, cities, start_city):
    num_cities = len(cities)
    start_idx = city_to_idx[start_city]
    
    # Initialize routing manager and model
    manager = pywrapcp.RoutingIndexManager(num_cities, 1, start_idx)
    routing = pywrapcp.RoutingModel(manager)
    
    # Define distance callback function
    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]
    
    # Register the callback with the routing model
    transit_callback_idx = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_idx)
    
    # Set search strategy (PATH_CHEAPEST_ARC is fast and effective for small problems)
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    
    # Solve the problem
    solution = routing.SolveWithParameters(search_params)
    
    # Extract the path if a solution exists
    if solution:
        path = []
        index = routing.Start(0)
        while not routing.IsEnd(index):
            path.append(cities[manager.IndexToNode(index)])
            index = solution.Value(routing.NextVar(index))
        return path
    else:
        return None

# Test with City B
optimal_path = solve_fixed_start_tsp_optimal(distance_matrix, cities, start_city)
print(f"Optimal path starting at {start_city}: {optimal_path}")

This will return the same optimal path as above, but with the guarantee that it's the absolute shortest possible.

Key Notes #

• For symmetric distance matrices (like yours), the closed TSP cycle's rotated path will always give the optimal open path for a fixed start.
• OR-Tools is better for larger datasets or when you need additional constraints (e.g., fixed end points, time windows).

内容的提问来源于stack exchange，提问作者Pyd