Resolvendo o problema de múltiplos caixeiros viajantes com caminhos fechados e múltiplos depósitos usando k-means++ hierárquico e redes neurais combinatórias

Rotas mais inteligentes para muitos motoristas

De vans de encomendas a drones de entrega e comboios de socorro em desastres, planejadores frequentemente enfrentam um enigma: como vários veículos partindo de locais diferentes podem compartilhar a tarefa de visitar centenas ou milhares de pontos sem desperdiçar combustível ou tempo? Este artigo apresenta uma nova forma de dividir e vencer esse problema, combinando um truque clássico de clusterização com uma rede neural moderna para que computadores possam traçar rotas eficientes em segundos em vez de minutos ou horas.

O desafio de muitos depósitos e muitos motoristas

O estudo aborda uma versão exigente do famoso problema do caixeiro viajante, onde em vez de um viajante há muitos, cada um começando e terminando em sua própria base. Juntos, eles devem visitar cada cidade exatamente uma vez, mantendo a distância total o mais curta possível. Essa configuração imita tarefas como coordenar frotas de caminhões, grupos de robôs ou drones aéreos que compartilham o trabalho sobre uma região. Como o número de combinações de rotas possíveis explode conforme aumentam cidades e motoristas, métodos exatos tornam-se lentos demais, e métodos tradicionais de busca por tentativa e erro frequentemente enfrentam dificuldades ou precisam trocar qualidade de solução por velocidade.

Limites da busca clássica e da divisão simples

Por anos, engenheiros recorreram a “metaheurísticas” como algoritmos genéticos, buscas inspiradas em colônias de formigas e enxames de partículas. Essas técnicas imitam processos naturais para explorar muitos candidatos a rota e aprimorá-los gradualmente. Podem ser flexíveis, mas têm duas grandes desvantagens: não oferecem garantias firmes sobre quão boa é a solução e podem ser muito lentas para mapas grandes, especialmente quando cada nova tarefa exige reiniciar a busca. Uma aceleração popular é primeiro agrupar as cidades em regiões usando ferramentas como k-means e então resolver um problema menor dentro de cada cluster. Embora essa estratégia de dividir-para-resolver ajude, a qualidade final ainda é limitada pelo método de busca subjacente, e buscar rotas melhores geralmente implica pagar com tempos de execução ainda maiores.

Treinar uma rede para roteirizar e depois ajudá-la a escalar

Nos últimos anos surgiu uma ideia diferente: treinar uma rede neural para produzir boas rotas diretamente. Após aprender com muitos exemplos de disposições de cidades, tal rede pode propor um circuito completo em uma única passagem direta, muito como um modelo de linguagem escreve uma frase. Esses solucionadores neurais funcionam impressionantemente bem em problemas de um só motorista de tamanho moderado, mas tropeçam quando solicitados a coordenar muitos motoristas ou quando o conjunto de cidades é muito maior do que o visto no treinamento. O movimento-chave dos autores é encapsular esse solucionador neural dentro de um processo cuidadoso em duas etapas que transforma uma tarefa enorme e multi-motorista em muitos subproblemas menores e familiares que a rede pode manejar confortavelmente.

Como funciona o método em duas fases

O método proposto, chamado KHC-NCN, começa usando uma versão aprimorada do k-means para atribuir cidades a diferentes depósitos e motoristas. Se uma região resultante contiver cidades demais para o solucionador neural lidar de forma confiável, o método divide automaticamente essa região em partes menores, cada uma com tamanho próximo ao que a rede viu durante o treinamento. As coordenadas em cada pedaço são escaladas para um quadrado padrão para que se assemelhem ainda mais aos dados de treinamento. A rede neural então produz uma rota para cada pequeno pedaço. Finalmente, uma etapa de fusão costura essas subrotas em um único laço para cada motorista, usando regras geométricas simples para conectar as partes onde isso acrescenta a menor distância extra.

Velocidade e qualidade em mapas de referência reais

Os autores testam seu método em uma ampla coleção de mapas padrão de um conjunto de referência público amplamente usado em pesquisas de roteirização. Eles comparam contra várias técnicas de busca estabelecidas e contra tanto um solucionador artesanal de ponta quanto outra abordagem neural. Em 44 casos de teste com diferentes tamanhos de mapas e números de motoristas, o método deles encontra rotas totais mais curtas em quase três quartos dos casos enquanto também é dramaticamente mais rápido, muitas vezes por ordens de magnitude. Ele se mantém especialmente bem conforme o número de cidades sobe para centenas ou milhares, onde muitas abordagens clássicas desaceleram ou entregam rotas mais fracas.

O que isso significa para roteirização no mundo real

Em termos simples, o estudo mostra que deixar uma rede neural rápida lidar com muitos pequenos problemas bem conformados pode superar gastar muito tempo em um único problema enorme. Ao agrupar cidades de um modo que respeite a zona de conforto da rede e depois combinar de forma inteligente as respostas parciais, o método entrega rotas que são tanto curtas quanto rápidas de calcular. Para aplicações como logística, planejamento multi-robô e resposta a emergências, isso aponta para uma maneira prática de obter planos de rota quase em tempo real que fazem melhor uso de veículos e energia do que muitas ferramentas existentes.

Citação: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Palavras-chave: roteirização de veículos, redes neurais, clusterização, otimização, logística