A salesman must visit a set of cities exactly once and return home, minimizing total travel distance. This deceptively simple puzzle—the Traveling Salesman Problem (TSP)—has haunted mathematicians, computer scientists, and logistics planners for nearly two centuries. It remains one of the most studied problems in computational optimization.

Historical Origins

The TSP’s roots trace to the 1830s, when Irish mathematician William Rowan Hamilton and British mathematician Thomas Kirkman studied related mathematical problems involving traversing graph vertices. Hamilton created the “Icosian Game” in 1857, a puzzle requiring players to find paths visiting each vertex of a dodecahedron exactly once.

The problem as we know it crystallized in the 1930s. Karl Menger studied the “messenger problem” in Vienna, and Hassler Whitney at Princeton coined the name “Traveling Salesman Problem.” The 1940s brought the first serious computational attacks when mathematicians at RAND Corporation, including George Dantzig and Delbert Ray Fulkerson, began developing solution methods.

In 1954, Dantzig, Fulkerson, and Selmer Johnson solved a 49-city instance optimally—a remarkable achievement for the era. Their cutting-plane method laid groundwork for integer programming. By the 1970s, the TSP had become the canonical example of NP-hard problems, meaning no known algorithm can solve all instances efficiently.

Why It Matters

The TSP’s significance extends far beyond academic curiosity:

Logistics and Transportation: Delivery companies, from postal services to Amazon, solve TSP variants daily. FedEx and UPS route thousands of vehicles through millions of potential paths. Even small improvements translate to massive fuel savings.

Manufacturing: Circuit board drilling, where a machine must visit thousands of holes in optimal order, is a direct TSP application. Chip fabrication uses similar routing for wire placement.

DNA Sequencing: Genome assembly involves finding optimal orderings of DNA fragments—structurally identical to TSP.

Telescope Scheduling: Astronomical surveys must observe targets across the sky efficiently, minimizing slew time between observations.

The TSP belongs to the NP-hard complexity class. For n cities, there are (n-1)!/2 possible routes. Ten cities yield 181,440 routes—tractable by brute force. Twenty cities produce over 60 quadrillion routes. Fifty cities exceed the number of atoms in the observable universe.

This exponential explosion means exact solutions become impractical beyond a few dozen cities. Real-world applications with thousands of locations require approximation methods.

Genetic Algorithms: Evolution as Optimizer

Genetic algorithms (GAs) apply biological evolution principles to optimization. A population of candidate solutions evolves through selection, crossover, and mutation, gradually improving over generations.

For TSP:

  • Individual: A sequence of cities representing a tour
  • Fitness: Total tour distance (lower is better)
  • Selection: Better solutions reproduce more frequently
  • Crossover: Combine routes from two parent solutions
  • Mutation: Randomly swap cities within a route

GAs don’t guarantee optimal solutions but often find excellent approximations quickly—making them practical for large instances where exact methods fail.

Solving TSP with Python and DEAP

DEAP (Distributed Evolutionary Algorithms in Python) provides a flexible framework for implementing genetic algorithms. The library includes an official TSP example that demonstrates the core concepts. Here’s an adapted version solving a 20-city TSP:

import random
import numpy as np
from deap import algorithms, base, creator, tools

# Generate 20 random cities as (x, y) coordinates
NUM_CITIES = 20
random.seed(42)
CITIES = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(NUM_CITIES)]

def distance(city1, city2):
    """Euclidean distance between two cities."""
    return np.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)

# Precompute distance matrix
DISTANCE_MATRIX = [[distance(CITIES[i], CITIES[j])
                    for j in range(NUM_CITIES)]
                   for i in range(NUM_CITIES)]

def evaluate(individual):
    """Calculate total tour distance."""
    total = DISTANCE_MATRIX[individual[-1]][individual[0]]  # Return to start
    for i in range(len(individual) - 1):
        total += DISTANCE_MATRIX[individual[i]][individual[i + 1]]
    return (total,)  # Must return tuple

# DEAP setup
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))  # Minimize
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()

# Individual: random permutation of city indices
toolbox.register("indices", random.sample, range(NUM_CITIES), NUM_CITIES)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Genetic operators
toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxOrdered)  # Order crossover preserves city visits
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

def main():
    random.seed(42)

    # Create population
    pop = toolbox.population(n=300)

    # Track best solution
    hof = tools.HallOfFame(1)

    # Statistics
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("min", np.min)
    stats.register("avg", np.mean)

    # Run evolution
    pop, log = algorithms.eaSimple(
        pop, toolbox,
        cxpb=0.7,      # Crossover probability
        mutpb=0.2,     # Mutation probability
        ngen=100,      # Generations
        stats=stats,
        halloffame=hof,
        verbose=True
    )

    best = hof[0]
    print(f"\nBest tour distance: {evaluate(best)[0]:.2f}")
    print(f"Best route: {best}")

    return pop, log, hof

if __name__ == "__main__":
    main()

Key Implementation Details

Order Crossover (cxOrdered): Standard crossover would produce invalid tours with duplicate or missing cities. Order crossover preserves visit sequences from parents while maintaining valid permutations.

Shuffle Mutation (mutShuffleIndexes): Swaps cities within a tour with probability 0.05 per position. This local modification explores neighboring solutions.

Tournament Selection: Randomly samples three individuals and picks the fittest. Balances selection pressure with diversity.

Running this code typically converges to within 5-10% of optimal for 20 cities within seconds. Larger instances may require parameter tuning or advanced techniques like island models or local search hybridization.

Beyond Basic GAs

Modern TSP solvers combine multiple techniques:

  • Lin-Kernighan heuristic: Local search that swaps edge sequences
  • Ant Colony Optimization: Probabilistic technique inspired by ant pheromone trails
  • Simulated Annealing: Accepts worse solutions with decreasing probability
  • Branch and Bound: Exact method pruning infeasible regions

The current record for proven optimal TSP solution stands at 85,900 cities, achieved in 2006 after years of computation. Practical applications typically use heuristics that find solutions within 1-2% of optimal.

Conclusion

The Traveling Salesman Problem bridges pure mathematics and practical engineering. Its simple statement belies profound computational complexity. While we can’t efficiently solve it exactly for large instances, approximation methods like genetic algorithms provide useful solutions for real-world applications.

The TSP reminds us that some problems resist elegant solutions. Progress comes not from breakthroughs but from accumulating clever techniques—each shaving percentages off tour lengths, each saving fuel, time, and resources at scale.

For logistics companies routing millions of packages, those percentages translate to billions of dollars. The salesman’s ancient puzzle remains urgently relevant.