Case Study: The Traveling Salesperson — When Good Enough Is Good Enough

The Scenario

A regional delivery company, QuickRoute Logistics, manages daily deliveries across 15 cities in the Midwest. Every morning, their dispatcher needs to plan a route that visits all 15 cities and returns to the warehouse — minimizing total driving distance to save fuel and time.

This is a version of the Traveling Salesperson Problem (TSP), one of the most famous problems in computer science. It sounds simple: find the shortest route through n cities. But the simplicity is deceptive.

The Brute-Force Approach

The obvious strategy is brute force: try every possible route, calculate the total distance of each, and pick the shortest one.

How many routes are there? For n cities, the number of possible orderings is (n-1)! (factorial) — we fix the starting city and permute the rest.

import math
import time
from itertools import permutations
import random

def total_distance(route: list[tuple[float, float]]) -> float:
    """Calculate total distance of a route (returns to start)."""
    dist = 0.0
    for i in range(len(route)):
        x1, y1 = route[i]
        x2, y2 = route[(i + 1) % len(route)]
        dist += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return dist

def brute_force_tsp(cities: list[tuple[float, float]]) -> tuple[list, float]:
    """Find shortest route by trying all permutations. O(n!)."""
    best_route = None
    best_distance = float("inf")

    # Fix first city, permute the rest
    first = cities[0]
    rest = cities[1:]

    for perm in permutations(rest):
        route = [first] + list(perm)
        dist = total_distance(route)
        if dist < best_distance:
            best_distance = dist
            best_route = route

    return best_route, best_distance

# Test with small numbers of cities
for n in [5, 8, 10]:
    cities = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(n)]

    start = time.time()
    if n <= 10:
        _, best_dist = brute_force_tsp(cities)
        elapsed = time.time() - start
        print(f"{n} cities: {math.factorial(n-1):>10,} routes, "
              f"best = {best_dist:.1f}, time = {elapsed:.3f}s")
    else:
        print(f"{n} cities: {math.factorial(n-1):>10,} routes — too slow!")

# Show the scale of the problem
print("\n--- Route counts by number of cities ---")
for n in [5, 10, 15, 20, 25]:
    routes = math.factorial(n - 1)
    print(f"  {n:2d} cities: {routes:>25,} routes")

Output (approximate):

5 cities:         24 routes, best = 198.3, time = 0.000s
8 cities:      5,040 routes, best = 247.1, time = 0.015s
10 cities:   362,880 routes, best = 231.5, time = 1.127s

--- Route counts by number of cities ---
   5 cities:                       24 routes
  10 cities:                  362,880 routes
  15 cities:           87,178,291,200 routes
  20 cities:  121,645,100,408,832,000 routes
  25 cities: 620,448,401,733,239,439,360,000 routes

For 15 cities — QuickRoute's actual problem — brute force would need to evaluate 87 billion routes. Even at a million routes per second, that's over 24 hours. For 20 cities, it's millions of years. For 25, longer than the age of the universe.

This is what computer scientists call a combinatorial explosion: the problem size grows factorially, making exact solutions impractical beyond tiny inputs.

The Greedy Approach: Nearest Neighbor

Since brute force is hopeless for 15+ cities, QuickRoute's developer tries a greedy algorithm: at each city, go to the nearest unvisited city.

def nearest_neighbor_tsp(cities: list[tuple[float, float]]) -> tuple[list, float]:
    """Greedy TSP: always go to the nearest unvisited city. O(n²)."""
    unvisited = list(cities)
    route = [unvisited.pop(0)]  # start at first city

    while unvisited:
        current = route[-1]
        # Find nearest unvisited city
        nearest = min(unvisited, key=lambda c: math.sqrt(
            (c[0] - current[0]) ** 2 + (c[1] - current[1]) ** 2
        ))
        route.append(nearest)
        unvisited.remove(nearest)

    return route, total_distance(route)

# Compare on 10 cities (where we can still run brute force)
random.seed(42)
cities_10 = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(10)]

_, optimal_dist = brute_force_tsp(cities_10)
_, greedy_dist = nearest_neighbor_tsp(cities_10)

print(f"10 cities:")
print(f"  Optimal (brute force): {optimal_dist:.1f}")
print(f"  Greedy (nearest neighbor): {greedy_dist:.1f}")
print(f"  Greedy is {(greedy_dist / optimal_dist - 1) * 100:.1f}% longer than optimal")

# Now solve 15 cities — only greedy is feasible
print()
cities_15 = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(15)]
start = time.time()
_, greedy_15 = nearest_neighbor_tsp(cities_15)
elapsed = time.time() - start
print(f"15 cities (greedy): distance = {greedy_15:.1f}, time = {elapsed:.4f}s")
print("  Brute force would take hours — greedy took a fraction of a second.")

Output (approximate):

10 cities:
  Optimal (brute force): 296.4
  Greedy (nearest neighbor): 331.7
  Greedy is 11.9% longer than optimal

15 cities (greedy): distance = 398.2, time = 0.0003s
  Brute force would take hours — greedy took a fraction of a second.

The greedy route is about 10-25% longer than optimal (this varies with the specific city layout). For QuickRoute, that means maybe 30 extra miles on a 250-mile route. Is that acceptable? It depends on the business context.

When "Good Enough" Is Good Enough

QuickRoute's dispatcher considers the trade-off:

The greedy solution saves the company less fuel per trip but can be computed instantly. Since routes change daily (different deliveries, traffic, new customers), spending hours computing the perfect route for yesterday's deliveries is pointless.

The Deeper Lesson

The Traveling Salesperson Problem is NP-hard — a class of problems for which no known algorithm can find the exact solution in polynomial time (like O(n²) or O(n³)). For NP-hard problems, the practical approach is usually:

1. Use brute force if n is small enough (up to ~15-20 for TSP)
2. Use a heuristic (like greedy nearest neighbor) that gives a good-but-not-perfect answer quickly
3. Use a more sophisticated approximation (like 2-opt, simulated annealing, or genetic algorithms — topics for an algorithms course)

The most important skill isn't knowing the perfect algorithm. It's knowing when perfect is necessary and when good enough will do.

Discussion Questions

1. QuickRoute's greedy route is ~15% longer than optimal. Under what business conditions would this be unacceptable? When would it be perfectly fine?

2. The brute-force approach is O(n!) — even worse than O(2ⁿ). At what value of n does this become impractical on a modern computer that can evaluate 1 billion routes per second?

3. The greedy nearest-neighbor heuristic sometimes produces very bad routes (e.g., it might cross the same area twice). Can you think of a way to improve the greedy solution without going all the way to brute force? (Hint: what if you tried the greedy approach starting from each city and picked the best result?)

4. Many real-world optimization problems (scheduling, routing, resource allocation) are NP-hard. How should this influence software development decisions? Should developers always aim for optimal solutions?

Mini-Project

Implement a "random restart" improvement: run the nearest-neighbor heuristic starting from each city (n starts), and keep the best route. This is O(n³) — much slower than single greedy but much faster than brute force. Compare its solution quality to single-start greedy on 15-20 cities. How much improvement do you see?