Traveling Salesman Problem with Python: Greedy and Brute Force

Just imagine yourself as a delivery courier. You have to deliver multiple parcels to many different spots. You also aim to minimize the fuel costs and time of traveling to maximize profit. This generally creates confusion about where to deliver parcels first and which routes to take.

In this article, we will learn about the famous problem of Travelling Salesman. We will solve this issue using Python programming language. We will also try to plot the best route to be taken and calculate the minimum distance to be traveled.

Solving the Traveling Salesman Problem with Python

The problem statement is that a salesman has to travel to the Indian cities of Mumbai, Delhi, Bangalore, Hyderabad, Ahmedabad, Chennai, Kolkata, Surat, Pune, and Jaipur to sell some products.

The objective of the problem is to minimize the total distance travelled by the salesman.

This describes our problem statement. Now let’s move on to how to solve this problem using Python programming language.

We will look at two ways of solving the problem – using the Greedy algorithm and the Brute Force method ( this method is the most preferred one as it provides more optimal solutions ).

Example Usage and Visualization of the Greedy Algorithm

Let us look at the code of the Simple Greedy algorithm.

import matplotlib.pyplot as plt

def distance(city1, city2):
  # Replace this with your distance calculation function (e.g., Euclidean distance)
  x1, y1 = city1
  x2, y2 = city2
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5

def tsp(cities):
  visited = [False] * len(cities)
  current_city = 0

  tour = []
  total_distance = 0

  for _ in range(len(cities)):
    visited[current_city] = True
    tour.append(current_city)

    next_city = None
    min_distance = float('inf')  # Represents positive infinity

    for i in range(len(cities)):
      if visited[i]:
        continue

      d = distance(cities[current_city], cities[i])
      if d < min_distance:
        min_distance = d
        next_city = i

    current_city = next_city
    total_distance += min_distance

  return tour, total_distance

# Example usage
cities = [(2, 4), (1, 8), (7, 1), (8, 5)]

tour, total_distance = tsp(cities)

print("Tour:", tour)
print("Total Distance:", total_distance)

# Plotting
x_coords = [cities[i][0] for i in tour]
y_coords = [cities[i][1] for i in tour]
x_coords.append(x_coords[0])  # Close the loop for plotting
y_coords.append(y_coords[0])

plt.plot(x_coords, y_coords)
plt.scatter(x_coords, y_coords, s=50, color='red')  # Plot cities as red dots
plt.title("Traveling Salesman Problem - Greedy Algorithm")
plt.show()

In the above example, we randomly input some coordinates and calculated the best route. Let us look at the output of this method.

Travelling Salesman Greedy Algorithm Output

Thus, according to the Greedy algorithm, we will travel to city 1 first, and cities 1,3,2 after that.

Brute Force Approach to the Traveling Salesman Problem

Let us look at the code of the Brute Force Method.

import numpy as np
import itertools
import matplotlib.pyplot as plt

def calculate_distance(city1, city2):
    return np.linalg.norm(np.array(city1) - np.array(city2))

def total_distance(route, distances):
    total = 0
    for i in range(len(route) - 1):
        total += distances[route[i], route[i+1]]
    total += distances[route[-1], route[0]]  # Complete the loop
    return total

def brute_force_tsp(coords, city_names):
    n = len(coords)
    distances = np.zeros((n, n))
    for i in range(n):
        for j in range(i, n):
            distances[i, j] = distances[j, i] = calculate_distance(coords[i], coords[j])

    min_distance = float('inf')
    min_route = None

    for route in itertools.permutations(range(n)):
        distance = total_distance(route, distances)
        if distance < min_distance:
            min_distance = distance
            min_route = route

    min_route_names = [city_names[i] for i in min_route]
    return min_route_names, min_distance

# Generate random city coordinates and city names
np.random.seed(0)
city_names = ['Mumbai', 'Delhi', 'Bangalore', 'Hyderabad', 'Ahmedabad', 'Chennai', 'Kolkata', 'Surat', 'Pune', 'Jaipur']
num_cities = len(city_names)
coords_list = [(np.random.randint(1, 100), np.random.randint(1, 100)) for _ in range(num_cities)]

# Solve TSP using brute force
best_route, best_distance = brute_force_tsp(coords_list, city_names)

print('Best Route:', best_route)
print('Best Distance:', best_distance)

# Plot the cities and the route
plt.figure(figsize=(8, 6))
plt.scatter(*zip(*coords_list), color='blue')
for i, city in enumerate(coords_list):
    plt.text(city[0], city[1], city_names[i], fontsize=12)
for i in range(len(best_route) - 1):
    city1 = coords_list[city_names.index(best_route[i])]
    city2 = coords_list[city_names.index(best_route[i+1])]
    plt.plot([city1[0], city2[0]], [city1[1], city2[1]], color='red', linewidth=1)
plt.plot([coords_list[city_names.index(best_route[-1])][0], coords_list[city_names.index(best_route[0])][0]],
         [coords_list[city_names.index(best_route[-1])][1], coords_list[city_names.index(best_route[0])][1]], color='red', linewidth=1)  # Complete the loop
plt.title('Brute Force TSP - Best Route')
plt.xlabel('X Coordinate')
plt.ylabel('Y Coordinate')
plt.grid(True)
plt.show()

Let us look at the output of the Brute Force method.

Brute Force Method Output

Thus, according to the Brute force method, the minimum distance is approximately 230 units.

Greedy Algorithm vs. Brute Force Method

The difference between the Greedy algorithm and the Brute Force method is that the Greedy algorithm builds up the solution step by step whereas in the Brute Force method, all the permutations of the solution are found and then the solution with minimum distance is selected.

Conclusion

Here you go! Now you know the Travelling Salesman Problem and how to solve it using Python. In this article, you learned about two methods of approach i.e. Greedy algorithm and Travelling Salesman problem.

Hope you enjoyed reading it!