Library to solve the Traveling Salesperson Problem in pure Python.
Project description
pythontsp is a library written in pure Python for solving typical Traveling Salesperson Problems (TSP). It can work with symmetric and asymmetric versions.
Installation
pip install pythontsp
Examples
Given a distance matrix as a numpy array, it is easy to compute a Hamiltonian path with least cost. For instance, to use a Dynamic Programming method:
import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming
distance_matrix = np.array([
[0, 5, 4, 10],
[5, 0, 8, 5],
[4, 8, 0, 3],
[10, 5, 3, 0]
])
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)
The solution will be [0, 1, 3, 2], with total distance 17. Notice it is always a closed path, so after node 2 we go back to 0.
To solve the same problem with a metaheuristic method:
from python_tsp.heuristics import solve_tsp_simulated_annealing
permutation, distance = solve_tsp_simulated_annealing(distance_matrix)
Keep in mind that, being a metaheuristic, the solution may vary from execution to execution, and there is no guarantee of optimality. However, it may be a way faster alternative in larger instances.
If you with for an open TSP version (it is not required to go back to the origin), just set all elements of the first column of the distance matrix to zero:
distance_matrix[:, 0] = 0
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)
and in this case we obtain [0, 2, 3, 1], with distance 12. Notice that in this case the distance matrix is actually asymmetric, and the methods here are applicable as well.
The previous examples assumed you already had a distance matrix. If that is not the case, the distances module has prepared some functions to compute an Euclidean distance matrix or a Great Circle Distance.
For example, if you have an array where each row has the latitude and longitude of a point,
import numpy as np
from python_tsp.distances import great_circle_distance_matrix
sources = np.array([
[ 40.73024833, 73.79440675],
[ 41.47362495, 73.92783272],
[ 41.26591 , 73.21026228],
[ 41.3249908 , 73.507788 ]
])
distance_matrix = great_circle_distance_matrix(sources)
See the project’s repository for more examples and a list of available methods.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for python_tsp0.4.0py3noneany.whl
Algorithm  Hash digest  

SHA256  261e755102464154964320f9bd48494490278e010da35d01c29fe1fbc04a9827 

MD5  3e239666b6475430750e8c77d110540e 

BLAKE2b256  6b48865289cba47b9f519e8fe4bcc1888aa687ad6bec6d674809d3e9cac6663c 