旅行商问题（TSP）场景下环赛日程优化Python代码运行时优化咨询

你的代码运行时过长的核心原因是暴力枚举所有路径的TSP解法完全不可行，再加上地理编码、距离计算等环节的低效设计，以下是针对性的优化建议：

1. 彻底替换暴力枚举的TSP核心逻辑 #

原代码中calculate_tsp函数通过permutations枚举所有路径，当赛事数量为27时，总排列数达1.08e28，这是天文级别的计算量，完全无法完成。必须替换为高效的启发式算法：

• 贪心+2-Opt组合：先通过贪心算法快速生成一个较优的初始路径（从任意点出发，每次选择最近的未访问赛事地点），再用2-Opt算法迭代优化路径，时间复杂度为O(n²)，对于27个节点完全可行。
• 使用成熟TSP求解库：直接用Google OR-Tools的TSP求解器，它内置Lin-Kernighan-Helsgaun等高效启发式算法，能在几秒内生成高质量的近似最优解，无需手动实现复杂逻辑。

2. 优化地理编码模块 #

原地理编码存在实例重复创建、多进程缓存失效的问题：

• 复用Geocoder实例：全局创建一个Nominatim实例，不要在geocode函数内每次初始化，减少开销。
• 改用持久化缓存：lru_cache在多进程环境下无法共享缓存，可使用joblib的Memory类将地理编码结果缓存到本地文件，避免重复调用Nominatim API（API有请求频率限制，重复调用会变慢）。
• 处理空坐标：对无法解析的地点补充手动坐标或添加警告，避免后续计算报错。

优化后的地理编码示例：

from geopy.geocoders import Nominatim
from joblib import Memory

# 初始化本地缓存目录
memory = Memory(location="./geocode_cache", verbose=0)
# 全局复用Nominatim实例
geolocator = Nominatim(user_agent="geoapiExercises", timeout=10)

@memory.cache
def geocode(location):
    result = geolocator.geocode(location)
    if result:
        return (result.latitude, result.longitude)
    else:
        print(f"警告：无法解析地点 {location}")
        return (0.0, 0.0)

3. 加速距离矩阵生成 #

用Numpy替代纯Python列表进行向量运算，大幅提升距离计算速度：

import numpy as np

def calculate_distance_matrix(locations_coordinates):
    coords = np.array(locations_coordinates)
    lat1, lon1 = coords[:, 0], coords[:, 1]
    lat2, lon2 = coords[:, 0][:, np.newaxis], coords[:, 1][:, np.newaxis]
    
    # 向量化实现Haversine公式
    dlat = np.radians(lat2 - lat1)
    dlon = np.radians(lon2 - lon1)
    a = np.sin(dlat/2)**2 + np.cos(np.radians(lat1)) * np.cos(np.radians(lat2)) * np.sin(dlon/2)**2
    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))
    R = 6373.0
    return R * c

4. 优化2-Opt算法效率 #

原2-Opt实现存在冗余计算，可通过以下方式优化：

• 计算距离差值而非全路径：交换路径段时，无需重新计算整个路径的总距离，只需减去被替换的两段距离，加上新的两段距离，减少计算量。
• 调整循环范围：减少不必要的迭代，比如跳过相邻节点的交换。

5. 删除冗余代码 #

删除calculate_tsp和calculate_tsp_optimized函数，直接使用贪心+2-Opt或OR-Tools的解法，避免无效计算。

6. 示例：改用OR-Tools的完整流程 #

替换原TSP求解逻辑后，optimal_calendar函数可修改为：

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

def solve_tsp_with_ortools(distance_matrix):
    n = len(distance_matrix)
    manager = pywrapcp.RoutingIndexManager(n, 1, 0)
    routing = pywrapcp.RoutingModel(manager)
    
    def distance_callback(from_index, to_index):
        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)
    
    # 设置求解参数
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    search_parameters.time_limit.seconds = 10  # 设置10秒超时
    
    solution = routing.SolveWithParameters(search_parameters)
    
    if solution:
        path = []
        index = routing.Start(0)
        while not routing.IsEnd(index):
            path.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        total_distance = solution.ObjectiveValue() / 1000
        return path, total_distance
    else:
        return None, float('inf')

def optimal_calendar(calendar):
    locations = [race[1] for race in calendar]
    locations_coordinates = [geocode(loc) for loc in locations]  # 单进程即可，缓存已生效
    
    distance_matrix = calculate_distance_matrix(locations_coordinates)
    
    original_distance = sum(distance_matrix[i][i+1] for i in range(len(locations)-1))
    
    optimal_order, min_distance = solve_tsp_with_ortools(distance_matrix)
    
    optimal_calendar = [calendar[i] for i in optimal_order]
    return optimal_calendar, min_distance, original_distance

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