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.        ]]

这是我得到的结果

Objective: 0 公里车辆 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: {}Kms\n'.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

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

OR-tools returning solution with 0 values

python

or-tools