An interactive visualisation of two very different approaches to solving the Travelling Salesman Problem (TSP) using p5.js.
The application lets you compare:
- Heap's Algorithm – an exact brute-force solution that evaluates every possible tour.
- Ant Colony Optimisation (ACO) – a swarm intelligence heuristic inspired by the behaviour of real ants.
The goal of the project is to expand on the ideas I learned in the AI Search module at university.
- Generates every unique permutation of the towns
- Guarantees the optimal solution
- Adjustable number of towns (4–11)
- Displays the shortest tour found
Because the number of permutations grows factorially (O(n!)), the algorithm quickly becomes impractical as the number of towns increases.
- Simulates multiple ants constructing tours
- Uses pheromone trails and distance heuristics to bias future paths
- Visualises pheromone intensity across the graph
- Continuously improves the best tour over successive iterations
- Adjustable problem size (10–60 towns)
Unlike the brute-force approach, ACO does not guarantee the optimal solution, but it can produce very good solutions for much larger problem sizes.
Simply open index.html in a modern web browser or with the VS Code Live Server extension.
- HTML5
- CSS3
- JavaScript
- p5.js
The Ant Colony Optimisation visualisation was inspired by Sebastian Lague's excellent video on slime moulds and ant colony behaviour, which explores how simple local rules can produce surprisingly effective global path-finding behaviour.
Video:
Sebastian Lague — Coding Adventure: Ant and Slime Simulations
Although this project applies the idea specifically to the Travelling Salesman Problem, the visual inspiration and swarm-based concepts came directly from that video.
--
Heap, B. R. (1963).
Permutations by Interchanges.
The Computer Journal, 6(3), 293–298.
https://doi.org/10.1093/comjnl/6.3.293
Dorigo, M., Maniezzo, V., & Colorni, A. (1996).
Ant System: Optimization by a Colony of Cooperating Agents.
IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26(1), 29–41.
https://doi.org/10.1109/3477.484436
Lague, S.
Coding Adventure: Ant and Slime Simulations.
YouTube.
https://www.youtube.com/watch?v=X-iSQQgOd1A
This implementation is intended as an educational visualisation rather than a research-grade optimisation library. The ACO implementation follows the core ideas of the original Ant System algorithm—pheromone evaporation, probabilistic path construction, and pheromone reinforcement—while keeping the code concise and easy to understand.