Optimization

Comparing Traveling Salesperson Solvers

Source Code

The source code is on GitHub.

Preliminaries

• Each benchmark uses a sample size of 30.
• Implementations follow the standard algorithms described in the linked references unless stated otherwise.
• Assertions verify that every returned tour is valid.

---

Traveling Salesman Problem

Problem Description and Motivation

Given nodes $X = \{x_1, \ldots, x_n\}$ and weighted edges $E = \{(x_i, x_j, d_{i,j}) \mid x_i, x_j \in X\}$, where $d_{i,j}$ is the distance between two nodes, find the shortest tour that visits every node and returns to $x_1$. In these tests, $max(d_{i,j}) = \alpha$ remains fixed, so adding nodes increases density instead of expanding the area.

A delivery route is the familiar example. A shorter tour can reduce fuel use and driver time. In practice, the edge cost could include travel time, traffic, tolls, or other constraints instead of straight-line distance.

The first thought would be to just take $X$ and try every permutation of elements until you find the shortest path. However, this would result in having to check

$n! = n \cdot(n - 1) \ldots 1$

possible tours. Since $11!$ is about 40 million and $13!$ exceeds 6 billion, exhaustive search becomes impractical quickly. The traveling salesperson problem is NP-hard, so larger instances generally require pruning or approximate heuristics.

Why Use a Heuristic?

If exhaustive search is too slow, random selection is an obvious baseline. The chart below compares random tours with the simplest informed rule, choosing the closest unvisited node.

As the number of nodes grows, random selection produces much longer tours than nearest neighbor. Even a cheap heuristic uses the distance information far better than chance.

Possible Heuristics

• Branch and Bound

  This is an exact algorithm that prunes paths if they go above the best distance found so far. If many partial tours remain competitive, the search approaches brute force. Better lower bounds can prune more paths, but worst-case performance remains exponential.

• Nearest Neighbor

  Nearest neighbor repeatedly selects the closest unvisited node, then returns to the start. It is fast and provides a useful initial tour for more expensive heuristics, although a locally cheap edge can force an expensive choice later.

• Ant System

  The ant system is a learning heuristic inspired by how ants reinforce useful routes. Given a collection of nodes $X$ the corresponding weighted edges also have a value representing the amount of "pheromone" present: $E = \{ (x_i, x_j, (d_{i,j}, p_{i, j})| \space x_i, x_j \in X\}$. Each Ant Each ant deposits pheromone on the edges it selects, with shorter tours receiving more reinforcement. The next node is chosen with a function $H(p,d)$ that uses both pheromone and distance. Across iterations, strong routes become more likely while pheromone evaporation keeps the search from locking in immediately.

• Simulated Annealing

  Simulated annealing searches the space of tours while minimizing total distance. It always accepts a better tour and may accept a worse one according to a decaying temperature parameter. Early acceptance of worse states helps the search escape local minima. This implementation selects a random tour segment and either reverses it in place or splices it into another position.

Comparison vs Exact

Brute force and branch and bound become impractical around 12 nodes in this benchmark, while the heuristics remain fast. Simulated annealing found the exact solution in every small test, though that result does not guarantee an exact solution on larger instances.

Heuristic Comparison

The ant system finds shorter tours than nearest neighbor, but its runtime roughly doubles for every 10 additional nodes in this range. Simulated annealing scales close to linearly on the medium tests and produces the lowest error of the three heuristics. Nearest neighbor remains the cheapest option when speed matters more than tour quality.

Simulated Annealing at Scale

Using 50 to 500 Nodes

Simulated annealing remains competitive from 50 to 500 nodes. Runtime grows gradually while the solution error stays below the other tested heuristics. The method also transfers to other problems that can define a state transition and an objective function, though its performance depends on the neighborhood, cooling schedule, and stopping rule.