How the behavior of ants can help in solving logistics problems

For some time now, man has drawn inspiration from Nature to develop new technologies and solve everyday problems. An example of extensive knowledge was the invention of airplanes inspired by the aerodynamics of birds: still in the 1890s, Otto Lilienthal studied how a heavier-than-air machine, in this case a glider, could obtain lift in a flight. At the beginning of the 1th century, the Wright brothers and Santos Dumont improved the development of such machines, by incorporating greater control over their drivability, enabling multiple maneuvers. [XNUMX]

Let's move now to more unusual examples: did you know that the process of condensation of water droplets on the carapace of the Namibian beetle inspired a prototype to help collect and supply water to arid regions of the planet? Have you ever stopped to think how camouflage techniques for animals such as marine molluscs and chameleons could help in the manufacture of uniforms for the armed forces? Finally, the study of the self-cleaning properties of the blue silk butterfly's wings could serve for the manufacture of paints with the same characteristics, facilitating the removal of dirt. Because these given examples are already under study and/or have already allowed the creation of new products available on the market. [two]

But how could the behavior of animals help in solving problems in the area of ​​logistics? Well then, the exponential growth in the number of viable solutions for some logistical problems can make them difficult to solve when using an optimizing method. As a classic example, we can cite the traveling salesman problem (or TSP – Traveling Salesman Problem), which aims to visit, at a minimum cost (time or distance travelled), a set of customers, departing and returning to the same point. [3]

Figures 1 : Poster created by P&G in 1962 to publicize a contest that would reward whoever determined the best tour route through 33 North American cities. [4]

Note that the vehicle routing problems, which are based on the TSP, are operational level problems, that is, they must be solved routinely by the company and, therefore, are not compatible with a high resolution time. [5] The solution to reconcile time with the necessary frequency of solving the problem is the use of heuristic methods, algorithms that reduce the average time of searching for a solution to the problem, allowing good solutions to be reached, but without the guarantee of its optimality. [6]

And it is at this point that Nature can serve as inspiration for the construction of intelligent algorithms!

Ants are a type of insect that release pheromones along the path they travel. Watch the video that follows, in which the trail of pheromones left by some Argentine ants that, let's say, are in search of food is highlighted. Note that this trail that leads to a “good reward” (in this case, let's say a handful of sugar) tends to intensify over time and attract more and more ants. However, there are a few that still continue to walk random paths.

What if this behavior were incorporated into the construction of a heuristic to search for good solutions to the traveling salesman problem? Let's make a simplified bridge between the behavior of ants and the principles of the algorithm. For more details, we recommend studying the material available in reference [8].

1. Initially, we released the ants into an open environment so that they could start looking for their food; in computational language, simply put, we ask the algorithm to start looking for viable solutions to the proposed problem, following a probabilistic function to decide which edges will be incorporated in its path. This probabilistic function can take into account, for example, the quality of each edge (related to the time or distance to traverse it) and the level of pheromone deposited on each one of them.
2. Let's imagine, now, that a new wave of ants will be released in this same environment. Now, these new ants will be able to orient themselves by the pheromone trail left by the previous wave. In computational language, the next search for solutions will take into account the new pheromone content deposited on each edge, that is, the more ants that have chosen the same edge in the first search, the greater the chances of this edge being chosen by these new ants.
3. However, imagine that there is a more interesting path, which would lead to a larger portion of food, which none of the ants in the first wave were able to capture initially. As the pheromone trail left, despite attracting new ants, does not oblige them to follow it, there may be ants from the new wave that follow a new path (perhaps more attractive) and start to deposit more pheromone on the edges that compose it . Computationally, the importance of the probability function is that new random solutions, which preferentially but not necessarily follow the trails with higher pheromone contents, can be generated and result better than those previously obtained. Thus, the heuristic allows the search not to be “stuck” to a good solution locally, with the search for new solutions that, globally, may be more interesting.

The insights that nature can offer to logistics do not stop there. Ever heard of genetic algorithms? A very interesting subject to be addressed in the future here on the blog.

Sources:

[1] https://super.abril.com.br/tecnologia/quem-afinal-inventou-o-aviao/
[2] https://super.abril.com.br/ciencia/o-manual-incrivel-de-inspiracao-na-natureza/
[3] Ballou, HR Supply Chain/Enterprise Logistics Management – ​​p. 197 – 5. ed. – Bookman, 2007.
[4] http://www.math.uwaterloo.ca/tsp/gallery/igraphics/car54.html
[5] Ballou, HR Supply Chain/Enterprise Logistics Management – ​​p. 53 – 5. ed. – Bookman, 2007.
[6] Ballou, HR Supply Chain/Enterprise Logistics Management – ​​p. 448 – 5. ed. – Bookman, 2007.
[7] https://www.youtube.com/watch?v=tAe3PQdSqzg
[8] http://www.dca.fee.unicamp.br/~lboccato/topico_4.1_IA013_colonia_formigas.pdf