Blazing Fast TSP: Comparing Brute Force and 2-Opt Algorithms

I recently encountered a solicitation on LinkedIn that said, "You have been selected to explain the Traveling Salesman Problem". (TSP). The solicitation turned out to be a way of getting multiple computer science people to solve the same problem, which would then be Darwinized and used by LinkedIn for further promotion. I provided a complete solution, but they would not accept a link, presumably because it takes the user off-site, which is anathema to social media profits. Beware the Machine.

Nonetheless, I thought this would be a good opportunity to demonstrate automatic code generation with a Large Language Model (LLM). So I set about with the following request:

Dear ChatGPT - I appreciate you so much! You have been an honest and faithful helper in coding up demonstrations of various principles in computer science, numerical analysis, computer graphics, and anything I'm interested in. Tonight, I need your help coding up a simple but beautiful demonstration of approaches to solving the Traveling Salesman Problem (TSP). As you know, this famous problem in computer science and operations research is well known for its pathological growth characteristics in time complexity. Nonetheless, we have to solve such problems, even if we cannot be guaranteed the optimal solution. I want you to build a Python demonstration compatible with Google Colab that uses matplotlib to generate approaches to solving TSP. It should run as an interactive demo that I can record off my screen.

While in previous blogs this approach yielded a straightforward generation processes, the more typical route to a working demo with satisfactory appearance is MUCH more circuitous.  One shot solutions are the exception to the rule, this effort required 29 iterations in ChatGPT 3.5 and 10 more in ChatGPT 4! Pressing on:
In the world of computer science and operations research, few problems are as iconic and challenging as the Traveling Salesman Problem (TSP). The TSP asks a simple question with profound implications: given a list of cities and the distances between them, what is the shortest possible route that visits each city exactly once and returns to the original city? Despite its seemingly straightforward nature, the TSP is notorious for its time complexity, which is exponential in the number of cities, making it a fascinating subject for exploration. This kind of complexity is informally called "hockey-stick growth". As each additional city case is processed in a brute force approach, all previous cases are relegated to be of low complexity in comparison.

In this blog post, we embark on a journey through the world of TSP-solving algorithms, focusing on two primary approaches: brute force and 2-opt. We'll delve into the inner workings of these algorithms, explore their strengths and weaknesses, and compare their performance in solving increasingly complex instances of the TSP.

Brute Force: The Traditional Approach

We kick off our exploration with the brute force algorithm, the most straightforward method for solving the TSP. Brute force systematically evaluates every possible permutation of city visitation order, calculating the total distance traveled for each permutation and selecting the shortest route. While conceptually simple, brute force quickly becomes impractical for large numbers of cities due to its exponential time complexity.

import numpy as np

import matplotlib.pyplot as plt

import time

from itertools import permutations

# Function to solve TSP using brute force

def brute_force_tsp(points):

min_dist = float('inf')

max_dist = 0

best_path = None

all_paths = []

start_time = time.time()

for perm in permutations(points):

dist = sum(np.linalg.norm(np.diff(perm, axis=0), axis=1))

all_paths.append(np.array(perm)) # Convert the tuple to a NumPy array

if dist < min_dist:

min_dist = dist

best_path = perm

if dist > max_dist:

max_dist = dist

end_time = time.time()

return best_path, min_dist, max_dist, all_paths, end_time - start_time

2-Opt: A Smarter Solution

Next, we introduce the 2-opt algorithm, a more sophisticated approach that seeks to improve upon the limitations of brute force. 2-opt operates by iteratively swapping pairs of edges in the current solution, aiming to reduce the total distance traveled. Unlike brute force, 2-opt exhibits polynomial time complexity, making it more scalable for larger problem instances. However, 2-opt does not guarantee optimal solutions and may occasionally converge to suboptimal routes.

# Function to solve TSP using 2-opt heuristic

def tsp_2opt(points):

n = len(points)

path = np.arange(n)

improvement = True

best_dist = sum(np.linalg.norm(np.diff(points, axis=0), axis=1))

while improvement:

improvement = False

for i in range(1, n - 1):

for j in range(i + 1, n):

new_path = path.copy()

new_path[i:j] = path[j - 1:i - 1:-1]

new_dist = sum(np.linalg.norm(np.diff(points[new_path], axis=0), axis=1))

if new_dist < best_dist:

best_dist = new_dist

path = new_path

improvement = True

break

if improvement:

break

return path, best_dist, improvement

Comparative Analysis: Brute Force vs. 2-Opt

With both algorithms in hand, we conduct a comparative analysis to evaluate their performance across various TSP instances. We examine factors such as execution time, solution quality, and scalability, shedding light on the trade-offs between computational efficiency and solution optimality. 

Conclusion: Navigating the TSP Landscape

In conclusion, our exploration of the Traveling Salesman Problem has provided valuable insights into the world of combinatorial optimization. While brute force offers a straightforward and reliable method for finding optimal solutions, its computational demands prove prohibitive for larger problem sizes. In contrast, 2-opt presents a more scalable alternative, leveraging heuristic techniques to efficiently explore solution space. By understanding the nuances of each approach, practitioners can navigate the TSP landscape with confidence, selecting the most appropriate algorithm for their specific requirements.

Join us on this journey as we unravel the complexities of the Traveling Salesman Problem, uncovering the algorithms and strategies that drive computational optimization in the digital age.

The remaining source code is below, it can be run in Google Colab for free!
But beware, it slows down significantly for more than about 8 cities!

# Test cases (number of cities)

test_cases = range(2, 8)

brute_force_runtimes = []

brute_force_shortest_distances = []

brute_force_longest_distances = []

num_paths = []

# Combined demonstration

plt.figure(figsize=(14, 12), facecolor='#99CC99')

for idx, num_points in enumerate(test_cases, start=1):

points = np.random.rand(num_points, 2)

# Solve TSP using brute force approach

best_path_brute_force, min_dist_brute_force, max_dist_brute_force, all_paths_brute_force, brute_force_runtime = brute_force_tsp(points)

brute_force_runtimes.append(brute_force_runtime)

brute_force_shortest_distances.append(min_dist_brute_force)

brute_force_longest_distances.append(max_dist_brute_force)

num_paths.append(len(all_paths_brute_force))

# Plot all attempted paths for brute force

plt.subplot(4, len(test_cases), idx)

for path in all_paths_brute_force:

path_list = path.tolist()

plt.plot(np.append([point[0] for point in path_list], path_list[0][0]),

np.append([point[1] for point in path_list], path_list[0][1]),

color='black', linestyle='-', linewidth=0.5, alpha=0.5)

plt.scatter(points[:,0], points[:,1], color='red', zorder=2)

plt.title(f'Brute Force\nCities: {num_points}\nShortest: {min_dist_brute_force:.2f}\nLongest: {max_dist_brute_force:.2f}', backgroundcolor='#99CC99')

# Solve TSP using 2-opt approach

best_path_2opt, min_dist_2opt, _ = tsp_2opt(points)

# Plot 2-opt path

plt.subplot(4, len(test_cases), len(test_cases) + idx)

plt.plot(np.append(points[best_path_2opt, 0], points[best_path_2opt[0], 0]),

np.append(points[best_path_2opt, 1], points[best_path_2opt[0], 1]),

color='red', linestyle='-', linewidth=1, zorder=3)

plt.scatter(points[:,0], points[:,1], color='red', zorder=2)

plt.title(f'2-Opt\nDistance: {min_dist_2opt:.2f}', backgroundcolor='#99CC99')

plt.tight_layout()

plt.show()

plt.figure(figsize=(7,6), facecolor='#99CC99')

# Plot number of paths as a function of the number of cities

plt.subplot(2, 1, 1)

plt.plot(test_cases, num_paths, marker='o', color='green')

plt.xlabel('Number of Cities')

plt.ylabel('Number of Paths')

plt.title('Number of Paths vs. Number of Cities', backgroundcolor='#99CC99')

# Plot summary graphs

plt.subplot(2, 1, 2)

plt.plot(test_cases, brute_force_runtimes, label='Brute Force', marker='o')

plt.xlabel('Number of Cities')

plt.ylabel('Time (seconds)')

plt.title('Execution Time Comparison', backgroundcolor='#99CC99')

plt.legend()

plt.tight_layout()

plt.show()