Scalable implementation of the travelling salesman problem in Python

Question

I have (let's say) a 100 points. I want to generate a path between them, the shorter, the better. This is the Travelling salesperson problem. Since the TSP is NP-hard, I am satisfied with not finding a global solution. I method which gives a solution quickly & scales well.

Generate example points:

import numpy as np
points = np.random.RandomState(42).rand(100,2)

Generate distance matrix, where the i,j entry contains distance between point[i] and point[j]. Using this answer:

z = np.array([[complex(*c) for c in points]]) # notice the [[ ... ]]
distance_matrix = abs(z.T-z)

How do I continue, to find a shortest path, with at least locally minimal pathlength?

---

Some related questions:

This thread: Travelling Salesman in scipy provides code for finding a solution to the TSP. It works in an iterative way though, so if the number of points to visit is large, the script does not produce a solution in reasonable times.

This thread: How to solve the Cumulative Traveling Salesman Problem using or-tools in python? does not have a code answer, and is not focused on classical TSP.

This thread: Optimizing a Traveling Salesman Algorithm (Time Traveler Algorithm) provides iterative solutions to the problem (which means bad scaling)

Answer 1

This is a examples based on simulated annealing (pip install frigidum). It is most likely slower than other solutions. I expect the posted Google OR to be better, but since it is a different approach might be of interest (albeit for learning/education).

import numpy as np
import frigidum

from frigidum.examples import tsp

points = np.random.RandomState(42).rand(100,2)

tsp.nodes = points
tsp.nodes_count = points.shape[0]

z = np.array([[complex(*c) for c in points]]) # notice the [[ ... ]]
distance_matrix = abs(z.T-z)

tsp.dist_eu = distance_matrix

We can use the following Simulated Annealing scheme (<30 seconds); (to get a better solution, get alpha closer to .999, and/or increate repeats with cost of longer calculation)

local_opt = frigidum.sa(random_start=tsp.random_start,
           objective_function=tsp.objective_function,
           neighbours=[tsp.euclidian_bomb_and_fix, tsp.euclidian_nuke_and_fix, tsp.route_bomb_and_fix, tsp.route_nuke_and_fix, tsp.random_disconnect_vertices_and_fix],
           copy_state=frigidum.annealing.naked,
           T_start=5,
           alpha=.8,
           T_stop=0.001,
           repeats=10**2,
           post_annealing = tsp.local_search_2opt)

local_opt is a tuple with its first element being the solution, and second element the objective value (route length). The the end it will output statistics and the minimum found; (this is not the one plotted).

(Local) Minimum Objective Value Found: 
   7.46016765

I used zabop plot code to plot the solution;

import matplotlib.pyplot as plt

plt.scatter(points[:,0],points[:,1])

route = local_opt[0]
for a, b in zip(route[:-1],route[1:]):
    x = points[[a,b]].T[0]
    y = points[[a,b]].T[1]
    plt.plot(x, y,c='r',zorder=-1)
plt.gca().set_aspect('equal')

https://i.sstatic.net/bNfdA.jpg

Answer 2

tl;dr : YMMV, but I had the best experience with tsp-solver2.

A number of Python TSP solvers can be installed through pip, just search for either "TSP" or "salesman" on Pypi.org.

Unless you’re looking for a particular algorithm, choosing the right one without a benchmark isn’t quite easy (although many projects lack documentation, which helps filtering).

I tried a few of them, here is my experience.

Note that for my usecase it is usually straightforward to check for the optimal solution, since I need to reorder geocoordinates along a path, generally quite simple and limited to a few hundreds of points.

Timings don’t make sense by themselves and are only provided for mutual comparison, for a 100 points sample.

ortools

Quite verbose to use and didn’t work out of the box, so I didn’t insist.

tsp-c

Raised libstdc++ conflicts I could not solve since I am not an admin on my Dataiku instance.

python-tsp

As of today, provides two exact solvers and two metaheuristic methods :

• brute force : didn’t try ;
• dynamic programming : supposed to be faster but used too much memory for me, and was quite slow anyway ;
• simulated annealing : quite fast (> 10 s), but didn’t find the optimal path ;
• local search : much faster (~1 s), but also failed to find the optimal path.

Usage :

#from python_tsp.exact import solve_tsp_brute_force as solve_tsp
#from python_tsp.exact import solve_tsp_dynamic_programming as solve_tsp
#from python_tsp.heuristics import solve_tsp_simulated_annealing as solve_tsp
from python_tsp.heuristics import solve_tsp_local_search as solve_tsp
permutation, distance = solve_tsp(distances)

fast-tsp

Uses a local solver. Blazing fast (~100 ms), but very bad results. Needs the distances as integers.

Usage :

import fast_tsp
tour = fast_tsp.find_tour(distances)

tsp-solver2

As often, trust the most humble ones. The project is titled "Suboptimal TSP Solver" and its README is full of warnings about not being tuned for performance and providing suboptimal solutions, yet in my use case it was even faster than fast-tsp (~20 ms) and the one to find the optimal solutions (didn’t fail a single of my paths).

It uses a greedy algorithm followed by optimization (see homepage for details).

Usage :

from tsp_solver.greedy import solve_tsp
path = solve_tsp(distances)

Note that these solvers require a matrix of distances between points. For geocoordinates points, one can create it easily with

from sklearn.metrics.pairwise import haversine_distances
distances = haversine_distances(df[["latitude","longitude"]].apply(np.deg2rad))
distances *= 6371

(Beware that Scikit-Learn’s haversine_distances expects radians and doesn’t take into account the Earth radius…)