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.
Recommended: Connected Health: Exploring IoT Solutions for Healthcare Transformation
Recommended: Delivery Route Optimization using Python: A Step-by-Step Guide
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.
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.
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!
Recommended: Backtracking Line Search Algorithm for Unconstrained Optimization
Recommended: Large integer handling in Python (optimization)
