Como o comportamento de formigas pode ajudar na resolução de problemas de logística

Há tempos, o homem tira inspiração da Natureza para desenvolver novas tecnologias e resolver problemas cotidianos. Um exemplo de amplo conhecimento foi a invenção de aviões inspirados na aerodinâmica de aves: ainda na década de 1890, Otto Lilienthal estudou como uma máquina mais pesada que o ar, no caso um planador, poderia obter sustentação em um voo. No início do século XX, os irmãos Wright e Santos Dumont aprimoraram o desenvolvimento de tais máquinas, ao incorporar um maior controle sobre sua dirigibilidade, viabilizando múltiplas manobras. [1]

Vamos partir agora para exemplos mais inusitados: você sabia que o processo de condensação de gotículas de água na carapaça do besouro-da-namíbia inspirou um protótipo para auxiliar na coleta e fornecimento de água para regiões áridas do planeta? Já parou para pensar como as técnicas de camuflagem de animais como moluscos marinhos e camaleões poderiam auxiliar na fabricação de uniformes para as forças armadas? Por fim, o estudo das propriedades autolimpantes das asas da borboleta-seda-azul poderia servir para a fabricação de tintas com as mesmas características, facilitando a remoção da sujeira. Pois estes exemplos dados já estão em estudo e/ou já permitiram a criação de novos produtos disponíveis no mercado. [2]

Mas como o comportamento de animais poderia auxiliar na resolução de problemas na área de logística? Pois bem, o crescimento exponencial do número de soluções viáveis em alguns problemas logísticos pode torná-los de difícil resolução ao se utilizar um método otimizante. Como exemplo clássico, podemos citar o problema do caixeiro viajante (ou TSP – Travelling Salesman Problem), que tem por objetivo visitar, a um mínimo custo (tempo ou distância percorrida), um conjunto de clientes, partindo e retornando a um mesmo ponto. [3]

Figuras 1 : Pôster criado pela P&G em 1962 para divulgar um concurso que premiaria quem determinasse o melhor roteiro de visitas passando por 33 cidades norte-americanas. [4]

Note que os problemas de roteirização de veículos, que têm por base o TSP, são problemas de nível operacional, ou seja, devem ser resolvidos rotineiramente pela empresa e, portanto, não são compatíveis com um tempo de resolução elevado. [5] A solução para compatibilizar o tempo com a frequência necessária de resolução do problema é a utilização de métodos heurísticos, algoritmos que permitem reduzir o tempo médio de busca de uma solução do problema, permitindo que sejam alcançadas boas soluções, porém sem a garantia de sua otimalidade. [6]

E é nesse ponto que a Natureza pode servir de inspiração para a construção de algoritmos inteligentes!

As formigas são um tipo de inseto que libera feromônios ao longo do caminho que percorre. Observe o vídeo que segue, no qual é destacada a trilha de feromônios deixada por algumas formigas-argentinas que, suponhamos, estão em busca de um alimento. Note que esta trilha que leva a uma “boa recompensa” (no caso, vamos supor um punhado de açúcar) tende a se intensificar com o passar do tempo e atrair cada vez mais formigas. Entretanto, existem algumas poucas que ainda continuam percorrendo caminhos aleatórios.

 

E se este comportamento fosse incorporado à construção de uma heurística de busca de boas soluções no problema do caixeiro viajante? Vamos fazer uma ponte simplificada entre o comportamento das formigas e os princípios do algoritmo. Para maiores detalhes, recomendamos estudar o material disponível na referência [8].

  1. Inicialmente, soltamos as formigas em um ambiente aberto para que elas comecem a buscar o seu alimento; em linguagem computacional, simplificadamente, solicitamos que o algoritmo comece a buscar soluções viáveis ao problema proposto, seguindo uma função probabilística para decidir quais arestas serão incorporadas no seu caminho. Esta função probabilística pode levar em consideração, por exemplo, a qualidade de cada aresta (relacionada ao tempo ou distância para percorrê-la) e o nível de feromônio depositado em cada uma delas.
  2. Vamos imaginar, agora, que uma nova leva de formigas será solta neste mesmo ambiente. Agora, estas novas formigas já poderão se orientar pela trilha de feromônios deixada pela leva anterior. Em linguagem computacional, a próxima busca de soluções levará em consideração o novo teor de feromônio depositado em cada aresta, ou seja, quanto mais formigas tiverem escolhido uma mesma aresta na primeira busca, maiores as chances desta aresta ser escolhida por estas novas formigas.
  3. Porém, imagine que existe um caminho mais interessante, que levaria a uma porção maior de alimento, que nenhuma das formigas da primeira leva conseguiu captar inicialmente. Como a trilha de feromônio deixada, apesar de atrair as novas formigas, não as obriga a segui-la, poderá haver formigas da nova leva que sigam por um novo caminho (porventura mais atrativo) e passem a depositar mais feromônio nas arestas que o compõem. Computacionalmente, a importância da função de probabilidade é que novas soluções aleatórias, que preferencialmente mas não necessariamente seguem as trilhas com maiores teores de feromônios, podem ser geradas e resultarem melhores que as já obtidas anteriormente. Assim, a heurística permite que a busca não fique “presa” a uma boa solução localmente, havendo a procura de novas soluções que, globalmente, podem ser mais interessantes.

Os insights que a natureza pode oferecer à logística não param por aí. Já ouviu falar em algoritmos genéticos? Um assunto bem interessante a ser abordado futuramente aqui no blog.

Fontes:

[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, R. H. Gerenciamento da cadeia de suprimentos/logística empresarial – p. 197 – 5. ed. – Bookman, 2007.
[4] http://www.math.uwaterloo.ca/tsp/gallery/igraphics/car54.html
[5] Ballou, R. H. Gerenciamento da cadeia de suprimentos/logística empresarial – p. 53 – 5. ed. – Bookman, 2007.
[6] Ballou, R. H. Gerenciamento da cadeia de suprimentos/logística empresarial – 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