Traveling Salesman Problem with Python: Greedy and Brute Force

Last quarter I had to plan a 12-stop delivery loop and the route my gut picked came out 38% longer than the version a small Python script returned in under a second. That gap is the travelling salesman problem (TSP): given a set of cities and the distance between every pair, find the shortest loop that visits each city once and returns to the start.

TSP is NP-hard in general, but two simple methods cover the small and medium cases we actually meet in shipping scripts.

Greedy nearest-neighbour runs in O(n²). Brute force tries every permutation and gives you the true optimum up to about ten cities.

Both fit on a screen. Both run on a laptop.

The problem in one paragraph

Ten Indian cities, one salesman, one loop. The job is to visit every city exactly once and return to the start while minimizing the total distance. The order of visits is the only choice you make.

If you try every permutation of ten cities, you have 9! = 362,880 options and the script finishes in about six seconds.

Twelve cities is 11! ≈ 40 million and the wait is closer to a minute.

Fifteen cities is 14! ≈ 87 billion, and brute force stops being a workable option.

Greedy nearest-neighbour algorithm

Start at any city. Repeatedly jump to the unvisited city closest to where you stand. When every city is visited, close the loop back to the start.

The algorithm picks locally optimal moves and does not look ahead. That keeps the cost to O(n²), because every city picks its nearest neighbour among the rest. The code is short enough to hold in your head.

import math

def distance(c1, c2):
    return math.sqrt((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2)

def tsp_greedy(cities):
    n = len(cities)
    visited = [False] * n
    start = 0
    visited[start] = True
    tour = [start]
    total = 0.0
    current = start
    for _ in range(n - 1):
        nxt = None
        best = float('inf')
        for i in range(n):
            if not visited[i]:
                d = distance(cities[current], cities[i])
                if d < best:
                    best = d
                    nxt = i
        visited[nxt] = True
        tour.append(nxt)
        total += best
        current = nxt
    total += distance(cities[current], cities[start])  # close the loop
    return tour, total

cities = [(2, 4), (1, 8), (7, 1), (8, 5)]
tour, total = tsp_greedy(cities)
print('Tour:', tour)
print('Total distance: {:.4f}'.format(total))

Run it on a 4-city example and the output looks like this:

Output

Tour: [0, 1, 3, 2]
Total distance: 21.6929

Tour indices 0, 1, 3, 2 means we leave city 0, then 1, then 3, then 2, then return to 0. Total distance is 21.69. Greedy is fast and the result is a valid tour, but it is not always optimal.

On random inputs greedy typically lands 10% to 25% above the optimum. That is good enough for sizing a delivery loop and bad enough to mislead a sales dashboard.

Brute force: try every permutation

Brute force is honest. It builds the full distance matrix once, then iterates over every permutation of the city indices, computes each tour length, and keeps the minimum. The complexity is O(n!) for the permutations plus O(n) per tour, which lands at O((n+1)!).

The number of permutations balloons fast, so brute force is a learning tool for small instances, not a production solver. For n=10 the work fits in a few seconds. For n=15 the loop will not finish on your laptop.

import numpy as np
import itertools

def calculate_distance(c1, c2):
    return float(np.linalg.norm(np.array(c1) - np.array(c2)))

def total_route_distance(route, dist):
    total = sum(dist[route[i], route[i + 1]] for i in range(len(route) - 1))
    total += dist[route[-1], route[0]]  # close the loop
    return total

def brute_force_tsp(coords, names):
    n = len(coords)
    dist = np.zeros((n, n))
    for i in range(n):
        for j in range(i, n):
            dist[i, j] = dist[j, i] = calculate_distance(coords[i], coords[j])
    best_d = float('inf')
    best_r = None
    for r in itertools.permutations(range(n)):
        d = total_route_distance(r, dist)
        if d < best_d:
            best_d = d
            best_r = r
    return [names[i] for i in best_r], best_d

# 10 Indian cities
city_names = ['Mumbai', 'Delhi', 'Bangalore', 'Hyderabad', 'Ahmedabad',
              'Chennai', 'Kolkata', 'Surat', 'Pune', 'Jaipur']
np.random.seed(0)
coords = [(int(np.random.randint(1, 100)),
           int(np.random.randint(1, 100))) for _ in city_names]

best_route, best_distance = brute_force_tsp(coords, city_names)
print('Best route:', best_route)
print('Best distance: {:.4f}'.format(best_distance))

On the same ten Indian cities, the script returns a tour of about 230 units:

Output

Best route: ['Mumbai', 'Ahmedabad', 'Pune', 'Jaipur', 'Chennai', 'Delhi', 'Surat', 'Hyderabad', 'Kolkata', 'Bangalore']
Best distance: 229.5617

Two refinements matter in working code.

Fix the start city to 0 and permute the remaining n-1 cities. Rotations of the same loop are equivalent, so dividing the work by n saves genuine time.

Prune with a running lower bound: keep the best distance seen so far and skip permutations whose partial sum already exceeds it.

Greedy vs. brute force

Use greedy when n is large or when you need an answer now. Use brute force when n is small enough that the loop completes in seconds, and you want a number to compare against.

The 4-city greedy result above is 21.69, and the brute-force optimum is 21.69. For n=4 greedy happens to be optimal. On the 10-city case the gap is wider, and the percentage tells you how far greedy is from the truth on your specific input.

Conclusion

TSP in Python is approachable from day one. Nearest-neighbour greedy gives you a fast upper bound. Brute force gives you the true optimum up to about ten cities.

The next step, once you have outgrown both, is the Held-Karp dynamic programming algorithm in O(n² · 2ⁿ), which fits n up to 20 on a workstation. Beyond that, OR-Tools and Lin-Kernighan heuristics are the next stop.