OR-tools求解8万节点TSP能否使用部分距离矩阵？含代码优化及替代方案问询

问题1：OR-tools是否支持基于部分距离矩阵求解TSP #

OR-tools 不强制要求预构建全量距离矩阵，原生支持通过距离回调函数按需计算任意两个节点的距离，完全可以实现部分距离矩阵的逻辑：

• 无需预生成8万×8万的全量矩阵（全量单精度浮点矩阵约占256GB内存，必然触发OOM），可直接在回调中实时计算两点欧氏距离，内存占用仅为存储节点坐标的几十MB。
• 若需预存部分近邻距离（如每个节点的前K个近邻的距离，加速局部搜索），可在回调中先查询预存的近邻表，未命中时再实时计算，OR-tools完全兼容这种自定义逻辑。

问题2：现有代码的优化方案 #

当前代码存在多个可导致运行失败或内存溢出的问题，优化方向如下：

内存与性能优化（解决OOM核心问题） #

• 移除dist_matrix函数的全量距离计算逻辑，直接在OR-tools的距离回调中通过节点坐标实时计算距离，彻底消除全量矩阵的内存占用。
• 用numba加速回调中的距离计算，避免Python原生计算的性能损耗。

代码逻辑修正 #

• 修正缩进错误：当前代码中输入解析、求解后路径计算的逻辑均脱离对应函数作用域，无法正常获取变量。
• 清理冗余导入：移除重复导入的euclidean_distances、namedtuple，以及未使用的scipy.spatial.distance_matrix等模块。
• 补充缺失的length函数：当前代码中计算总路径长度的length函数未定义，需补充两点间距离计算逻辑。
• 移除全局变量依赖：取消or_main中对全局sol变量的使用，直接通过返回值传递求解结果。

求解参数适配（针对8万节点规模） #

• 初始解启发式优先选择NEAREST_NEIGHBOR或CHRISTOFIDES，避免初始解质量过差导致局部搜索收敛慢。
• 保留GUIDED_LOCAL_SEARCH作为局部搜索元启发式，8万节点规模建议求解时间限制设置为300秒以上，可根据可接受的运行时长调整。

优化后的核心代码片段参考（已将英文注释翻译为中文）：

# 补充缺失的两点距离计算函数
def length(p1, p2):
    dx = p1.x - p2.x
    dy = p1.y - p2.y
    return (dx**2 + dy**2)**0.5

def or_main(nodeCount, points):
    from ortools.constraint_solver import routing_enums_pb2
    from ortools.constraint_solver import pywrapcp

    # 创建路由索引管理器，仅传入节点总数，无需距离矩阵
    manager = pywrapcp.RoutingIndexManager(nodeCount, 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)
        dx = points[from_node].x - points[to_node].x
        dy = points[from_node].y - points[to_node].y
        # 返回整数距离（若需浮点精度可调整返回值）
        return int((dx**2 + dy**2)**0.5)

    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.NEAREST_NEIGHBOR
    search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    # 8万节点设置5分钟求解时间
    search_parameters.time_limit.seconds = 300
    search_parameters.log_search = True

    # 求解
    solution = routing.SolveWithParameters(search_parameters)
    if not solution:
        return None
    
    # 提取路径
    index = routing.Start(0)
    plan_output = []
    while not routing.IsEnd(index):
        plan_output.append(manager.IndexToNode(index))
        index = solution.Value(routing.NextVar(index))
    return plan_output

# 主函数入口的打印提示翻译为中文
if __name__ == '__main__':
    import sys
    if len(sys.argv) > 1:
        file_location = sys.argv[1].strip()
        with open(file_location, 'r') as input_data_file:
            input_data = input_data_file.read()
        # 调用solve_it的逻辑补充正确缩进后即可运行
    else:
        print('本测试需要输入文件，请从数据目录选择（例如 python solver.py ./data/tsp_51_1）')

问题3：Python生态下适配8万节点规模的TSP求解器 #

以下求解器均无需预构建全量距离矩阵，可直接传入节点坐标求解，适配大规模欧式TSP任务：

• LKH绑定：封装了当前业界求解大规模TSP效果最优的LKH-3算法，支持十万级以上节点的TSP求解，求解质量远高于OR-tools的默认启发式，内存占用极低。
• pyConcorde：封装了TSP精确求解标杆Concorde的核心逻辑，启发式求解模式可支持十万级节点的快速求解，运行速度快。
• fast-tsp：针对大规模欧式TSP优化的轻量求解器，内置空间分块、近邻截断等优化，适合快速生成高质量可行解。

内容的提问来源于stack exchange，提问作者Asael Bar Ilan