COMPASS: Ordered Clustered Routing at 100K Scale

COMPASS: O Algoritmo Brasileiro que Redefine a Roteirização em Larga Escala

No coração da logística moderna — seja para entregar um pacote em São Paulo, otimizar rotas de ônibus em Belo Horizonte ou gerenciar cadeias de suprimentos globais — existe um problema matemático que assombra empresas e pesquisadores há décadas: como visitar centenas de milhares de pontos na ordem correta, agrupados em clusters, sem desperdiçar tempo, combustível ou dinheiro?

Esse desafio tem nome técnico: Problema do Caixeiro Viajante com Clusters Ordenados (OCTSP). E, até agora, as soluções disponíveis no mercado engasgavam quando o número de nós passava de alguns milhares. Uma nova pesquisa, porém, apresenta o algoritmo COMPASS, capaz de escalar para 100 mil nós sintéticos e 28,5 mil nós reais de e-commerce — um recorde absoluto para distâncias assimétricas.

O que é o OCTSP e por que sua empresa deveria se importar?

Imagine que você precisa visitar 50 cidades, mas cada cidade tem bairros que devem ser percorridos em uma ordem específica. Além disso, a ordem entre as cidades também importa. Esse é o OCTSP: um caixeiro viajante que, antes de partir, precisa respeitar uma sequência de clusters (agrupamentos) de pontos.

O instinto comum — e até hoje usado por muitos sistemas de roteirização — é otimizar cada cluster de forma independente, como se fossem ilhas isoladas. O problema é que isso ignora as dependências não-locais: a melhor rota dentro de um cluster pode arruinar a rota global se não considerar o que vem antes e depois. É como planejar uma viagem de carro otimizando apenas cada trecho entre pedágios, sem olhar o mapa completo.

Como o COMPASS resolve o quebra-cabeça

O COMPASS não é apenas mais um algoritmo de força bruta. Ele combina três ideias poderosas:

• Busca com aprendizado acelerado: em vez de testar todas as combinações possíveis (o que levaria séculos), o COMPASS usa técnicas de aprendizado de máquina para guiar a busca por rotas promissoras.
• Orquestração de sub-solvers paralelos: o algoritmo divide o problema em partes e resolve cada uma em paralelo, como uma equipe de entregadores que trabalha simultaneamente em regiões diferentes, mas compartilhando informações.
• Estrutura clusterizada: em vez de tratar 100 mil nós de uma vez, o COMPASS explora o fato de que os pontos estão agrupados. Isso reduz o tempo de processamento de forma