OR工具返回0值的解决方案

Question

我正试图用OR工具解决TSP问题，但当更改距离矩阵以挖掘时，结果为0。

这是我用来运行代码的距离矩阵。

data['distance_matrix'] = [[0.         0.40133922 0.58308059 0.44763244 0.59232887 0.13190757
0.5562759  0.12633011 0.78330022 0.17998744]
[0.40133922 0.         0.55530878 0.12847738 0.20445115 0.27022701
0.30111459 0.52368492 0.44647366 0.27820636]
[0.58308059 0.55530878 0.         0.68351728 0.56187331 0.55400228
0.33387128 0.67251728 0.52304621 0.43480849]
[0.44763244 0.12847738 0.68351728 0.         0.26454783 0.31920079
0.41996521 0.5580511  0.52643066 0.36789118]
[0.59232887 0.20445115 0.56187331 0.26454783 0.         0.46525396
0.23296919 0.71765895 0.26265452 0.44149353]
[0.13190757 0.27022701 0.55400228 0.31920079 0.46525396 0.
0.45765072 0.25362887 0.67092774 0.11976824]
[0.5562759  0.30111459 0.33387128 0.41996521 0.23296919 0.45765072
0.         0.67900157 0.24463744 0.37723255]
[0.12633011 0.52368492 0.67251728 0.5580511  0.71765895 0.25362887
0.67900157 0.         0.90875577 0.30180013]
[0.78330022 0.44647366 0.52304621 0.52643066 0.26265452 0.67092774
0.24463744 0.90875577 0.         0.60904638]
[0.17998744 0.27820636 0.43480849 0.36789118 0.44149353 0.11976824
0.37723255 0.30180013 0.60904638 0.        ]]

这就是我得到的结果

目标：0 Kms车辆0的路线：0->9->8->7->6->5->4->3->2->1->0路线距离：0Kms

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = distance_matrix
data['num_vehicles'] = 1
data['depot'] = 0
return data
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print('Objective: {} Kms'.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))
plan_output += 'Route distance: {}Kmsn'.format(route_distance)
print(plan_output)
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model
routing = pywrapcp.RoutingModel(manager)
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
# Create and register a transit callback.
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
if solution:
print_solution(manager,routing,solution)
print(solution.ObjectiveValue())
else:
print('No Solution')

Answer 1

解算器是积分的，python静默地将所有距离值四舍五入为0。

您应该用一个常数因子(例如1000(缩放所有内容，然后四舍五入为整数。

请参阅官方指南上的注释：https://developers.google.com/optimization/routing/tsp