As already mentioned in this blog, integer linear programming is often not useful in the real world to find the optimal solution to routing problems.
One of the most common metaheuristic techniques to solve this problem is known as Ant Colony Optimisation (ACO).
The ant colony technique was introduced by Marco Dorigo in 1992, and it is based on ant behaviours when they leave the ant nest to look for food. Ants deposit pheromones wherever they go, so that whenever an ant leaves the nest looking for food, it has a higher probability of choosing trails covered by more ants earlier, in other words, trails with higher amounts of pheromones.
The ant colony algorithm slightly modifies this behaviour, expecting each ant to calculate a complete route to deposit pheromones. This way, in each iteration of the algorithm, every ant will have to choose which unvisited node will be visited next, based on its position and the amount of pheromones deposited in the trails. Thus, the probability of an ant “k” choosing trail “xy” is:
Where τ(xy) is the amount of pheromone deposited in trail xy , η(xy) represents the appropriateness of choosing trail xy (generally defined as 1/distance(xy)), α represents a parameter that gives weight to the amount of pheromones deposited in each trail and β represents the influence parameter of η(xy) .
As shown with this metaheuristic technique, the convergence and advantage of the solution found is the parameter function to be chosen by the user which, in general, can be different for each problem.
Once each ant has completed a route, that is, it has found a feasible solution, the amount of pheromones in each trail is update
Where τ(xy) is the amount of pheromones deposited in trail xy, ρ is a parameter showing pheromone evaporation in each trail and Δτ(xy) represents pheromones deposited by each ant in the trails they have covered. Typically, the pheromones deposited by each ant in each trail is Q/L(k) if they have transited the trail and 0 otherwise, where Q is a constant and L(k) represents the total space covered by the ant in its circuit.
There are several differentiating characteristics of the algorithm, such as the number of ants or the number and position of the ant nests. Also common are extensions of the case presented:
Elitist Ant System (EAS): In each pheromone deposit, the total best solution found to date also deposits pheromones along its path.
Max-Min Ant System (MMAS): There is a range in the amount of pheromone to be deposited [τmin,τmax], and only the best solution obtained in each iteration deposits pheromones. All the trails start with pheromone initialized to τmax, and when it has evaporated and reaches the value τmin, it is reinitialized to τmax.
Rank-based Ant System (ASrank): Solutions are classified by advantage, and the amount of pheromone deposited is proportional to that value, so that the ants that have found a better solution deposit a greater amount of pheromone in their trails.