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)! ("n minus 1 factorial," meaning (n-1) × (n-2) × ... × 2 × 1). We fix the starting city, since a loop through the same cities is the same loop wherever you start, and try every ordering of the rest. (Each route also gets counted twice, once in each direction, but halving a number this big barely helps.)

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.perf_counter()
    _, best_dist = brute_force_tsp(cities)
    elapsed = time.perf_counter() - start
    print(f"{n} cities: {math.factorial(n-1):>10,} routes, "
          f"best = {best_dist:.1f}, time = {elapsed:.3f}s")

# 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 (the cities are random, so your distances and times will differ):

5 cities:         24 routes, best = 231.3, time = 0.000s
8 cities:      5,040 routes, best = 233.3, time = 0.011s
10 cities:    362,880 routes, best = 309.1, time = 0.918s

--- 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 nearly 4,000 years. For 25, about 20 billion years — 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.perf_counter()
_, greedy_15 = nearest_neighbor_tsp(cities_15)
elapsed = time.perf_counter() - start
print(f"15 cities (greedy): distance = {greedy_15:.1f}, time = {elapsed:.4f}s")
print("  Brute force would take days — greedy took a fraction of a second.")

Output (the timing will vary; the distances are fixed by random.seed(42)):

10 cities:
  Optimal (brute force): 264.1
  Greedy (nearest neighbor): 294.7
  Greedy is 11.6% longer than optimal

15 cities (greedy): distance = 367.7, time = 0.0000s
  Brute force would take days — greedy took a fraction of a second.

Here the greedy route is about 12% longer than optimal. For cities scattered at random, nearest neighbor averages roughly 25% longer than the best route; on carefully arranged "trap" layouts it can be far worse. 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 route burns a bit more fuel per trip, but it 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 one has found an algorithm that gets the exact solution in polynomial time (like O(n²) or O(n³)), and most computer scientists suspect none exists. For NP-hard problems, the practical approach is usually:

1. Solve it exactly if n is small enough. Plain brute force tops out around 10–12 cities; smarter exact methods such as dynamic programming (the Held–Karp algorithm, O(n² · 2ⁿ)) push that into the twenties.
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)

NP-hard doesn't mean hopeless, either. Specialized solvers combine clever math with massive computing power: in 2006 the Concorde solver found a provably optimal tour through 85,900 points, after more than 136 CPU-years of computation. For everyday software, though, options 2 and 3 are usually the sensible ones.

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. Suppose 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 "multi-start" 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?