Ant colony optimisation for the travelling salesman problem

The problem

Given the distances between every pair of cities, find the shortest closed tour that visits each city exactly once. The coursework supplied instances from 12 to 535 cities and required a valid tour and its length for each, produced within a strict time limit. Exact search is hopeless at that scale, so this is a job for heuristics.

Approach: the Ant System

Ant colony optimisation mimics how ants converge on short paths by laying down pheromone.

• Each ant builds a tour city by city, choosing the next city with probability proportional to τ^α · η^β, where τ is the pheromone on that edge and η = 1 / distance (α = 1, β = 2), using roulette-wheel selection.
• After every iteration, the pheromone on all edges evaporates by 10%, and each ant deposits 1 / (its tour length) on the edges it used, so short tours reinforce themselves.
• The search runs 175 ants for up to 500 iterations, stops at a 58-second budget, and keeps the best tour seen.

Results

Every output is a valid closed tour that visits each city exactly once, which I verified again for this write-up. Best tour lengths found:

• 12 cities: 56
• 17 cities: 1,444
• 21 cities: 2,649
• 26 cities: 1,610
• 42 cities: 1,420
• 48 cities: 12,634
• 58 cities: 26,248
• 175 cities: 22,947
• 180 cities: 4,650
• 535 cities: 54,046

Each instance has its own distance scale, so lengths aren't comparable from one instance to the next.