The travelling salesperson problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" Optimal solutions are computationally difficult or infeasible given enough cities, and developing methods to find close to optimal solutions is a common exercise in computer science.

​

We implemented a version of an ant colony algorithm  which approximates a solution. It does this by simulating the behavior of an ant colony. In a real colony, ants traverse routes between food sources and the nest, depositing pheromone. Other ants follow routes with higher concentrations of pheromone. Pheromone decays naturally over time.

​

Our approach finds good solutions relatively quickly. A disadvantage is the difficulty in determining good coefficients for ideal ant behavior and pheromone decay rate, even perhaps as a function of city amounts. We ran extensive permutations to maximize effectiveness.

​

Code repository and full report