Route planning with ant system

For a set of destinations, finding the route that gives the smallest length is the well known Traveling Salesman Problem, a combinatorial optimization problem.

For a reduced number of stops, there is no difficulty in looking at all possible combinations. This becomes impossible with increase of the number of destinations because of the factorial relationship between them and the number of routes. For example, for only 12 destinations there are 39,916,800 possible itineraries.

A way to solve this problem, with no guarantee to find the best path, but at least a good one, is inspired on the behavior of ants. Proposed by Dorigo in 1993, it takes the dynamics of pheromones as a mean of selecting the shortest route.

Photo of a trail of ants

Ant two-way highway by David Short, flickr, CC BY 2.0, cropped

In this post I present my implementation of the ant system in Python. An application to a real world problem will show you how to use ants to plan your next route trip.

Continue reading →