Search⌘ K
AI Features
Home
Courses
Solving the Traveling Salesperson Problem in Python

Traveling Salesperson Problem: Package

Explore different algorithms and Python packages for solving the Traveling Salesperson Problem, including brute force, dynamic programming, and heuristic local search. Understand how to compute various distance matrices using tools like geopy and OSRM, and compare their performance and accuracy on small and larger datasets.

We'll cover the following...

We’ve utilized numerous Python libraries to execute different functions with minimal lines of code, such as geopy for distance calculations. It would be advantageous if there was a package that could solve TSP, wouldn’t it? Fortunately, there is such a package.

The python_tsp library

The python_tsp library contains algorithms and tools for the solution of TSP and related problems. It provides a variety of algorithms, from the classic brute force to more modern approaches such as genetic algorithms.

To reduce the computation time, we’ll run all code widgets for only five stores. The distances module has some functions to calculate euclidean_distance_matrix.

Python 3.8
import pandas as pd
import numpy as np 
# Import the distance function
from python_tsp.distances import euclidean_distance_matrix
df = pd.read_csv('MoscowMcD.csv')
df = df[df["Store"].isin(["StoreA","StoreB","StoreC","StoreD","StoreE"])]
# Define the sources and destinations
sources=df[['lat','lon']].to_numpy()
destinations=df[['lat','lon']].to_numpy()
# Calculate the distance matrix
distance_matrix = euclidean_distance_matrix(sources, destinations)
# Print the distance matrix
print(distance_matrix)

The results here are similar to the ones we got with SciPy. While Euclidean distance doesn’t reflect the true geographical distance, it can still be used as a heuristic. It’s simple and computationally efficient and can be a legitimate fast approach to determining the nearest store.

The ...