Media Coverage
August 2010
Ant Colony Optimisation
A couple of months ago we discussed a way of optimising picking in a warehouse that was based on observations of how ants move food to their nests. In this month’s column I would like to focus on another optimisation method inspired by observations of ant colonies.
There is a new approach being used to solve many kinds of optimisation problems called Ant Colony Optimisation (ACO). The idea behind ACO is quite simple but it has been used to find good solutions for many difficult problems in logistics including the Travelling Salesman Problem, vehicle routing problems, job shop scheduling and more.
Have you ever wondered why ants seem to move in such a precise, regimented way? To the casual observer, ants march – with seemingly little co-ordination – down extremely narrow paths and directly to whatever food has been left unattended. However, if you’re (un)fortunate enough to be around a colony of ants and have a biscuit that won’t go amiss, drop it and observe.
What you’ll find is that a few curious ants will likely stumble across it in a very haphazard fashion and, having bit off a chunk, will return to the colony victoriously on individual paths. You’ll see more ants come out, some following a similar path used by the first pioneers, others taking varying routes which may or may not cross paths with other ants.
But – remarkably – in a very short period of time, the ants are all merging into a single path, seemingly undistinguishable from the others. A few minutes later, they’re the orderly unit of industrious workers we’ve become accustomed to.
.png)
Figure of ACO in motion (source: Wikipedia)
What just happened? Pheromones. Ants leave pheromones wherever they go, and are similarly attracted to these pheromones. They use this to communicate in various ways, but it serves another important purpose. As the paths cross and match, certain sections of the paths – usually the ones easier to traverse - become more attractive to others. The ants are drawn to these pheromones and thereby increase the strength of these paths as other paths’ “scent” grow more faint.
This is an example of a self-organised system – the individual ants react collectively to positive feedback (strong pheromones) and negative feedback (weak pheromones) from the system. In this way, no single ant need know the best way to a piece of food – it merely needs to find a way, and the system will ensure that eventually, the shortest route is chosen.
ACO is proving to be a fruitful area of development and research for routing and scheduling. A recent case study involves a Texas gas company who have – according to reports – saved an annual estimated $20 million by taking their routes, customers and fleet and placing them into an ACO model.
If you’re interested in seeing ACO at work on the Travelling Salesmen Problem, you can check out the following link: http://ems.eit.uni-kl.de/index.php?id=156. As usual, if you have any comments or questions please contact me at david@opsi.co.za.