0
$\begingroup$

This is the Travelling Salesperson Problem code from Google's OR tools. I used a simple instance that is defined in the data dictionary and has optimal value (sum of Euclidean distances) of 36.26 for the path [0, 2, 4, 1, 3,0]. However, the solution outputs 34, an integer value that is not correct and it makes me doubt whether if it doesn't know the actual objective value it is doing the optimization correctly. It is using the rounded integer distances rather than the actual floating point values even though I set the distance matrix to contain floating point values. How do I get the correct floating point output?

"""Simple Travelling Salesperson Problem (TSP) on a circuit board."""

import math
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def compute_euclidean_distance_matrix(locations):
    """Creates callback to return distance between points."""
    distances = {}
    for from_counter, from_node in enumerate(locations):
        distances[from_counter] = {}
        for to_counter, to_node in enumerate(locations):
            if from_counter == to_counter:
                distances[from_counter][to_counter] = 0
            else:
                # Euclidean distance
                distances[from_counter][to_counter] = ((
                    math.hypot((from_node[0] - to_node[0]),
                               (from_node[1] - to_node[1]))))
                
#                 distances[from_counter][to_counter] = ((from_node[0] - to_node[0])**2 + 
#                                (from_node[1] - to_node[1])**2)**0.5 
                
    return distances 

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print('Objective: {}'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route:\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 += 'Objective: {}m\n'.format(route_distance)


def main():
    """Entry point of the program."""
    # Instantiate the data problem. 
    data = {'locations': [(1,2), (12,3), (4.5,5), (4,1), (18,6)], 'num_vehicles': 1, 'depot': 0}
    
    print('data: ', data)
    
    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['locations']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    distance_matrix = compute_euclidean_distance_matrix(data['locations'])
    
    print('distance_matrix: ', distance_matrix)
    
    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 distance_matrix[from_node][to_node]

    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)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution)


if __name__ == '__main__':
    main()
$\endgroup$

2 Answers 2

2
$\begingroup$

The solver is integral, and python silently rounds all distances to the nearest integer.

see The note in the guide

$\endgroup$
2
$\begingroup$

Indeed, OrTools does not take into account floating point values for the distance matrix, and automatically performs rounding, as you suspected.

One way around this is to artificially multiply all distances by $100$ (considering your precision is $2$ decimals), and then divide your objective function value by $100$ at the end.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.