O problema do Caixeiro-Viajante em Excel

Imagine que você é um vendedor que precisa passar por vários clientes em diferentes cidades. Você tem um mapa que mostra as cidades e as distâncias entre elas. Você quer visitar todas as cidades, visitar os clientes e voltar para casa no menor tempo possível. Mas você não sabe qual é a melhor ordem para visitar as cidades, porque existem muitas possibilidades.

Por exemplo, se você tem 4 cidades para visitar, você pode fazer 24 rotas diferentes. Se você tem 5 cidades, você pode fazer 120 rotas diferentes. Se você tem 10 cidades, você pode fazer 3.628.800 rotas diferentes! Isso é muito difícil de comparar, não é?

Esse é o problema do caixeiro viajante: encontrar a rota mais curta para visitar todas as cidades e voltar para casa. Esse problema é importante para muitas empresas que precisam planejar a logística: motoristas, pilotos, entregadores, etc.

Vamos comparar 3 técnicas de resolução deste.

1) Busca cega: como o próprio nome dá uma dica, é uma busca sem considerar nenhuma informação prévia sobre o problema. Em outras palavras, puro chute!

Por exemplo, tenho 5 cidades, e escolho aleatoriamente a rota a seguir.
2–5–3–1–4

Outra solução possível: 2–5–4–1–3

Não é um método muito esperto — note que as cidades 1 e 2 são próximas, mas como a rota é aleatória, ela vai de 2 a 3.

2) Cidade mais próxima. Ora, que tal usar uma heurística? Ir sempre para a cidade mais próxima? É o que o ser humano faria.
No mesmo caso das 5 cidades acima, ótimo, vou chegar numa boa solução com esta técnica.

Porém, o que acontece se eu aumentar o número de cidades?

Com 18 cidades, o método guloso (esse de pegar o melhor imediato) mostra situação estranha: há momentos em que a rota chega a “becos sem saída”, e obriga o pobre viajante a percorrer uma distância enorme para compensar (como da cidade 3 para a 8, ou da cidade 10 para 13).

3) Metaheurística: uma metaheurística evolutiva pode fugir dos mínimos locais do método guloso.

Uma metaheurística possível é a seguinte:

• Para cada cidade, liste as cidades mais próximas não visitadas
• Escolha aleatoriamente uma das cidades, sendo que as de menor distância terão mais chance de serem escolhidas
• Tire a cidade já visitada da lista
• Prossiga até o final

Há diversas metaheurísticas inspiradas na natureza. Uma delas é a da Otimização por Colônia de Formigas.
Uma característica da colônia de formigas é colocar um feromônio no caminho para buscar comida. Se muitas formigas forem por este caminho, o feromônio é mais forte, senão, ele vai se apagando.

Podemos adaptar o algoritmo para considerar o feromônio. Se, numa dada interação, a rota foi da cidade 1 para a cidade 15, o peso da ligação 1–15 aumenta um pouco para ser escolhido na próxima interação, senão, há um fator de esquecimento para ir diminuindo o peso.

Utilizando metaheurísticas, chegamos a uma solução melhor, para as mesmas 18 cidades anteriores.

O problema do Caixeiro-Viajante é difícil (NP-hard), de modo que não é muito simples achar boas soluções quando o número de cidades aumenta. Além disso, metaheurísticas não garantem o ótimo global, apenas uma solução boa.

Para 60 cidades, utilizando o método guloso:

Para as mesmas 60 cidades, utilizando o método evolutivo:

Foi um pouquinho melhor, com FO de 2748 (contra 2824 do guloso), porém, não muito melhor, ainda dá para melhorar bem o algoritmo utilizado.

O arquivo Excel para download no link ( https://1drv.ms/x/s!Aumr1P3FaK7jsmTBb2yFLRs35JnT?e=rcyjQP)
implementa as três técnicas de otimização mostradas. É necessário ativar macros.

O problema do Caixeiro Viajante tem sido bastante estudado na literatura, com inúmeros métodos, benchmarks e também competições, como a abaixo, que pedia ao leitor encontrar a menor distância para percorrer 50 cidades americanas.

Originally published at https://ideiasesquecidas.com on December 5, 2023.