# TSP problem using Google's OR tools

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()


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.