Skip to main content

Simple library to solve the Traveling Salesperson Problem in pure Python.

Project description

python-tsp is a library written in pure Python for solving typical Traveling Salesperson Problems (TSP).

Installation

pip install python-tsp

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.

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

python_tsp-0.1.0.tar.gz (10.4 kB view hashes)

Uploaded Source

Built Distribution

python_tsp-0.1.0-py3-none-any.whl (12.8 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page