OR-Tools求解TSP返回次优解，如何获取最优路径？

一、TSP求解结果不符合预期（返回90而非80） #

可能原因与调整方案 #

• 搜索策略与参数限制：当前使用AUTOMATIC初始启发式和GUIDED_LOCAL_SEARCH元启发式，且时间限制30秒，可能未探索到全局最优解。可尝试以下调整：
  1. 更换初始解策略：改用CHRISTOFIDES（TSP专用经典启发式）或PATH_CHEAPEST_ARC（贪心选最低成本弧），替代AUTOMATIC。
  2. 调整元启发式：换成SIMULATED_ANNEALING或TABU_SEARCH，帮助跳出局部最优陷阱。
  3. 延长时间限制：若问题规模不大，将时间限制设为60秒以上，给求解器足够时间遍历解空间。
  4. 验证成本计算：确认distance_callback正确映射矩阵索引，避免因索引转换错误导致成本计算偏差。

修改后的关键代码片段 #

# 调整搜索参数部分
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
# 更换为CHRISTOFIDES初始解策略
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES)
# 改用模拟退火元启发式
search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.SIMULATED_ANNEALING)
# 延长时间限制到60秒
search_parameters.time_limit.seconds = 60
# 可选：限制解数量，确保优先找到最优解
search_parameters.solution_limit = 1

二、MIP解固定二进制变量后LP连续变量变化（解不唯一） #

问题本质与解决方法 #

当MIP存在多个最优解时，SCIP返回的是其中一组最优解；固定二进制变量后，LP可能存在多组连续变量最优解，GLOP会返回另一组。若要获取多组最优解，可尝试：

• 设置求解器寻找多解：在SCIP参数中启用多解搜索：

  from ortools.linear_solver import pywraplp
  solver = pywraplp.Solver.CreateSolver('SCIP')
  # 最多寻找10个最优解
  solver.SetParameter('limits/solutions', 10)
  # 关闭预解，避免合并等价解（可选）
  solver.SetParameter('presolving/maxrounds', 0)
  

• 微小扰动目标函数：给连续变量的目标系数添加极小扰动（比如乘以1+1e-6），在不改变最优性的前提下，引导求解器找到不同的连续变量解。

• 枚举LP最优解：若LP存在多组最优解，可通过求解器的GetNextSolution()方法迭代获取不同解，或分析对偶间隙确认最优性后，枚举基可行解。

原TSP完整代码（已标注关键修改） #

# Bibliotecas
from __future__ import print_function
import math
import pandas as pd
import scipy.spatial as sp
import numpy as np
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# Início matriz de distâncias
R = int(input("Adicione o número de linhas:"))
C = int(input("Adicione o número de colunas:"))
print('Adicione a matriz de distâncias com os conteúdos separados por um espaço simples')
 
# Início matriz
entries = list(map(int, input().split()))
matrix = np.array(entries).reshape(R, C)
print(matrix)
# Fim matriz de distâncias

# TSP ínicio
def create_data_model():
    data = {}
    data['distance_matrix'] = matrix
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

def print_solution(manager, routing, solution):
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)

def main():
    """Entry point of the program."""
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    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.CHRISTOFIDES)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.SIMULATED_ANNEALING)
    search_parameters.time_limit.seconds = 60
    search_parameters.solution_limit = 1

    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(manager, routing, solution)

if __name__ == '__main__':
    main()

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