我有这个功能来寻找最佳路线:
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'}
不难看出
A -> B -> C -> D
比结果更好。我缺少任何配置吗?或者这就是 ortool 的工作原理,并不总能找到最短的解决方案?
我不是 ortool 方面的专家,所以可能有些事情我忽略了。
中转回调必须返回一个
int64_t
,否则你的浮点值将导致未定义的行为。 (编者:在 Python 和 C++ 之间的 SWIG 桥中,Python's floating
值转换为 int64_t
)。
参考:
路由
RegisterTransitCallback()
声明:RoutingTransitCallback
的类型定义:在您的示例中,您可以将所有值乘以 10 以获得整数值,然后在打印/显示函数中将它们除以 10...
第一个答案我发现我们的工具不能很好地处理浮点数,使用整数它可以找到最佳路线。不确定,但在这种情况下它对我有用。