approximate tsp solver

google_tsp_solver.py

from ortools.constraint_solver import pywrapcp
import numpy as np


def _create_distance_callback(dist_matrix):
    # Create a callback to calculate distances between cities.
    def distance_callback(from_node, to_node):
        return int(dist_matrix[from_node][to_node])
    return distance_callback


def solve_tsp(problem, multiplier=1000.0):
    if len(problem) > 0:
        dist_matrix = np.sqrt(np.square(problem[:, None] - problem[None, :]).sum(axis=-1)) * multiplier
        num_routes = 1
        depot = 0
        chosen_route = []
        routing = pywrapcp.RoutingModel(len(dist_matrix), num_routes, depot)
        search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
        # Create the distance callback.
        dist_callback = _create_distance_callback(dist_matrix)
        routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
        # Solve the problem.
        assignment = routing.SolveWithParameters(search_parameters)
        if assignment:
            # Solution distance.
            # Display the solution.
            # Only one route here; otherwise iterate from 0 to routing.vehicles() - 1
            route_number = 0
            index = routing.Start(route_number)  # Index of the variable for the starting node.
            chosen_route.append(routing.IndexToNode(index))
            while not routing.IsEnd(index):
                # Convert variable indices to node indices in the displayed route.
                index = assignment.Value(routing.NextVar(index))
                chosen_route.append(routing.IndexToNode(index))
            return chosen_route[:-1]
    return []