Estudo comparativo de ACO, Dijkstra e NN para eficiência de roteamento em redes de coleta de resíduos

Por que rotas de lixo mais inteligentes importam

Por trás de cada caminhão de lixo que passa pela sua rua há um quebra-cabeça complexo: como visitar muitos recipientes e bairros gastando o mínimo possível de deslocamento. Com as cidades gerando bilhões de toneladas de resíduos e os custos de combustível e as emissões em alta, mesmo pequenas melhorias no roteamento podem economizar dinheiro, reduzir poluição e aliviar o tráfego. Este artigo faz uma pergunta prática para cidades modernas: entre três abordagens populares para calcular rotas para caminhões de lixo, qual realmente funciona melhor quando as redes crescem e ficam mais movimentadas?

Três maneiras de encontrar um caminho

O estudo compara três famílias de métodos de roteamento, cada uma espelhando um estilo diferente de tomada de decisão. A primeira, chamada Otimização por Colônia de Formigas (ACO), inspira-se em como formigas reais depositam e seguem trilhas de feromônio: caminhos promissores são reforçados ao longo do tempo, enquanto os mais fracos enfraquecem. A segunda, o algoritmo de Dijkstra, é uma receita matemática clássica que sempre encontra o caminho mais curto em uma rede quando as condições são fixas e conhecidas. A terceira, o método do Vizinho Mais Próximo, imita um palpite humano rápido: de onde você está agora, simplesmente vá até o ponto não visitado mais próximo e repita. Todos os três são aplicados ao mesmo tipo de mapa urbano abstrato, onde cruzamentos e pontos de coleta de resíduos são representados como nós conectados por vias com custos que refletem distância e congestionamento.

Construindo cidades virtuais para testar as ideias

Em vez de depender de uma cidade em particular, os autores constroem redes viárias sintéticas que se assemelham a layouts urbanos típicos. Essas redes são esparsas, com cada ponto conectado a apenas alguns outros, e incluem uma variedade de tamanhos de 10 até mais de 50 localidades para imitar desde pequenos distritos até zonas urbanas consideráveis. Segmentos de estrada carregam custos "ponderados por congestionamento", de modo que vias mais movimentadas ou mais longas são efetivamente mais caras de usar. Em cada um desses mapas virtuais, os três algoritmos recebem a tarefa de encontrar caminhos de baixo custo entre um ponto de início e um ponto final escolhidos. Para manter a comparação justa, todos usam a mesma estrutura de custos subjacente, e os métodos mais aleatórios são executados muitas vezes para que os pesquisadores possam medir tanto o desempenho médio quanto sua variabilidade.

O que os testes diretos revelam

Os resultados mostram um padrão claro. Em redes pequenas, médias e grandes, o ACO consistentemente descobre rotas com o menor custo total médio. Suas formigas exploram, aprendem com a experiência e gradualmente se concentram em caminhos mais baratos, o que se mostra especialmente valioso à medida que as redes aumentam e os custos das vias se tornam mais desiguais. O algoritmo de Dijkstra é extremamente estável: dado o mesmo mapa e custos, ele sempre retorna o mesmo caminho, com muito pouca variação nos resultados. Contudo, quando custos ponderados por congestionamento e configurações mais complexas são considerados, suas rotas ficam um pouco mais caras que as encontradas por um ACO bem ajustado. O método do Vizinho Mais Próximo é o mais rápido para executar, mas tem o pior desempenho: ao sempre perseguir o ponto mais próximo seguinte, tende a ignorar atalhos mais inteligentes de longo prazo e produz as rotas mais caras e mais inconsistentes.

Verificando que as diferenças são reais

Para garantir que essas lacunas de desempenho não sejam meras coincidências de variação aleatória, os autores usam uma ferramenta estatística conhecida como teste de postos sinalizados de Wilcoxon. Esse teste compara resultados pareados dos algoritmos nas mesmas instâncias de rede sem assumir que os dados seguem uma curva em forma de sino. Em todo tamanho de rede estudado, o teste indica que as economias de custo do ACO sobre Dijkstra e o Vizinho Mais Próximo são estatisticamente significativas e não acidentais. Ao mesmo tempo, medidas de dispersão mostram o trade-off entre estabilidade e flexibilidade: os caminhos de Dijkstra praticamente não variam, enquanto os resultados do ACO mudam ligeiramente entre execuções à medida que ele explora alternativas antes de se estabilizar perto das melhores rotas.

O que isso significa para as ruas da cidade

Para gestores urbanos, a mensagem do artigo é ao mesmo tempo prática e intuitiva. Se a rede viária é pequena e as condições são relativamente estáveis, um método clássico de caminho mais curto como Dijkstra é simples e confiável. Quando as redes são maiores e o congestionamento ou outros custos variam no espaço, uma abordagem inspirada em formigas pode extrair rotas notavelmente mais baratas, mesmo que exija mais esforço computacional nos bastidores. A estratégia rápida e improvisada do Vizinho Mais Próximo, embora tentadora pela velocidade, deixa consistentemente dinheiro e combustível na mesa. No conjunto, o estudo oferece um guia testado: escolha métodos determinísticos para cenários pequenos e previsíveis, mas prefira otimização adaptativa baseada em enxames ao planejar uma coleta de resíduos econômica e escalável em cidades modernas e em crescimento.

Citação: Anitha, R., Parthiban, A. Comparative study of ACO, dijkstra, and NN for routing efficiency in waste collection networks. Sci Rep 16, 13346 (2026). https://doi.org/10.1038/s41598-026-42866-5

Palavras-chave: coleta de resíduos urbanos, otimização de rotas, otimização por colônia de formigas, algoritmos de caminho mais curto, logística de cidades inteligentes