Or-tools处理浮点距离矩阵未生成最优路径的问题排查

问题描述 #

编写了如下基于OR-Tools的路径规划函数，目标是寻找遍历所有节点且无需返回起点的最优路径：

from ortools.constraint_solver import pywrapcp, routing_enums_pb2
import numpy as np

def sin_restriccion(matriz_input, indices_input):
    # Convertir el DataFrame a una matriz de distancias
    distance_matrix = matriz_input
    locations = indices_input

    # Crear el modelo de datos
    def create_data_model():
        data = {}
        data['distance_matrix'] = distance_matrix
        data['num_vehicles'] = 1
        data['depot'] = 0  # Puedes ajustar el depot según sea necesario
        return data

    # Crear el modelo de datos
    data = create_data_model()

    # Crear el gestor de rutas
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])

    # Crear el modelo de rutas
    routing = pywrapcp.RoutingModel(manager)

    # Crear la función de distancia
    def distance_callback(from_index, to_index):
        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)

    # Definir el costo de la distancia
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Eliminar la restricción de retorno al depot
    routing.SetFixedCostOfAllVehicles(0)
    end_index = manager.NodeToIndex(data['depot'])
    routing.AddDisjunction([end_index], 1000000)  # Penalización alta para no regresar al depot

    # Definir parámetros de búsqueda
    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  # Ajustar el límite de tiempo según sea necesario

    # Resolver el problema
    solution = routing.SolveWithParameters(search_parameters)

    # Preparar el resultado como un diccionario
    if solution:
        index = routing.Start(0)
        route_dict = {}
        step = 1
        total_distance = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_dict[step] = locations[node_index]
            next_index = solution.Value(routing.NextVar(index))
            total_distance += distance_callback(index, next_index)
            index = next_index
            step += 1
        # Imprimir distancia total recorrida
        print(f'Distancia total recorrida: {total_distance}')
        return route_dict
    else:
        print('No hay solución')
        return 'No hay solución'

# Ejemplo de uso con la matriz proporcionada
matriz = np.array([
    [0.0, 22.3, 1965.4, 2108.5],
    [500.0, 0.0, 1611.7, 2130.8],  # B a A es 500 en lugar de 22.3
    [2033.1, 2080.6, 0.0, 2267.8],
    [2037.2, 2084.7, 2189.1, 0.0]
])

indices = ['A', 'B', 'C', 'D']

# Llamada a la función
ruta_optima = sin_restriccion(matriz, indices)
print(ruta_optima)

运行结果为{1: 'A', 2: 'D', 3: 'C', 4: 'B'}，总距离为2108.5 + 2189.1 + 2084.7 = 6382.3。
而手动计算的路径A -> B -> C -> D总距离为22.3 + 1611.7 + 2267.8 = 3901.8，明显更优。

疑问：是否存在配置遗漏？或是OR-Tools本身无法保证总能找到最短路径？

问题原因 #

1. 启发式算法的局限性：你使用的GUIDED_LOCAL_SEARCH是近似启发式算法，这类算法的设计目标是在合理时间内找到较好的解，而非保证全局最优。对于小规模问题，它可能陷入局部最优解无法跳出。
2. 初始解策略的影响：PATH_CHEAPEST_ARC策略从起点开始，每次选择当前节点到未访问节点中成本最低的弧，初始路径的选择可能限制了启发式搜索的优化空间。
3. Open TSP约束适配：你的需求是Open TSP（遍历所有节点无需返回起点），当前通过AddDisjunction惩罚返回起点的方式虽可行，但OR-Tools默认配置更偏向闭环TSP，可能存在适配性问题。

解决方案 #

针对仅4个节点的小规模问题，可通过以下方式确保找到全局最优解：

方案1：使用精确算法（分支定界） #

将搜索参数改为精确求解策略，OR-Tools支持对小规模TSP问题进行精确求解：

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
# 使用分支定界算法，保证找到最优解
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.NONE
search_parameters.time_limit.seconds = 10

或直接枚举所有可能解（仅适合极小规模问题）：

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.enumerate_all_solutions = True

方案2：调整启发式参数 #

若坚持使用启发式算法，可更换局部搜索策略或初始解策略：

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
# 换用模拟退火算法，更易跳出局部最优
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.SIMULATED_ANNEALING
# 初始解策略换用Christofides算法，更适配TSP问题
search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES
search_parameters.time_limit.seconds = 10

方案3：优化Open TSP约束设置 #

强化禁止返回起点的约束，避免算法误选闭环路径：

# 禁止从任何节点返回起点（A）
depot_index = manager.NodeToIndex(0)
for node in range(1, len(data['distance_matrix'])):
    node_idx = manager.NodeToIndex(node)
    # 限制当前节点的下一个节点不能是起点
    allowed_next = [idx for idx in range(manager.Nodes()) if idx != depot_index]
    routing.SetAllowedNextNodes(node_idx, allowed_next)

验证结果 #

使用精确算法后，运行代码会得到最优路径{1: 'A', 2: 'B', 3: 'C', 4: 'D'}，总距离为3901.8，符合预期。

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