Solving the Traveling Salesperson Problem in Python/

...

/

Traveling Salesperson Problem: Package

Traveling Salesperson Problem: Package

Learn how to effortlessly conquer TSP with python_tsp.

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.

Press + to interact
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. ...