Solving the Traveling Salesperson Problem in Python/

...

/

Brute Force

Brute Force

Apply the brute force approach to solve TSP.

We'll cover the following...

Brute force in coding is a method of problem-solving that involves systematically trying every possible combination of inputs until the correct solution is found. It’s often used in cryptography and password cracking, where the goal is to guess a password or key by trying every possible combination of characters. We’ll use it to solve TSP. It’s not the most efficient solution, but it’s easy to understand and, therefore, a good start.

How many stores should we dare take? Let’s be cautious and start with five stores.

Press + to interact
import pandas as pd
df = pd.read_csv('MoscowMcD.csv')
df = df[df["Store"].isin(["StoreA","StoreB","StoreC","StoreD","StoreE"])]
print(df)

Distance matrix

For these stores, we create a distance matrix.

Press + to interact
import geopy.distance
import pandas as pd
import numpy as np
df = pd.read_csv('MoscowMcD.csv')
df['geom'] = list(zip(df['lat'], df['lon']))
df=df.set_index("Store")
# Square matrix called matrix is created with the same number of rows and columns as df and filled with zeros
matrix = pd.DataFrame( 
np.zeros((df.shape[0], df.shape[0])),
index=df.index, columns=df.index
)
# Get_distance is defined, which takes a column of matrix as input. For each row in the column, the function retrieves the corresponding 'geom' tuple from df
def get_distance(col):
    end = df.loc[col.name, 'geom']
    # Use the geopy library to compute the distance between this tuple and all the other tuples in df. The resulting distances are returned as a pandas Series
    return df['geom'].apply(geopy.distance.distance,args=(end,),
    # Use .apply(lambda x: int(x.km)) to format distances
    ellipsoid='WGS-84').apply(lambda x: round(float(x.km), 2)) 
# The apply method is used to apply get_distance to each column of the matrix, producing a DataFrame of pairwise distances called distances
distances = matrix.apply(get_distance, axis=1).T 
print(distances)

A distance matrix is a matrix where the value at row i and column j is the distance between node i and node j. This matrix contains the distances between all pairs of nodes. Please note that the direction is not important in this case, as the distance from StoreB (row 1) to StoreA (column 0) and vice versa from StoreA (row 0) to StoreB (column 1) is ...