RRNCO: Towards Real-World Routing with Neural Combinatorial Optimization

O artigo apresenta o RRNCO, uma nova arquitetura de Otimização Combinatória Neural que supera a lacuna sim-to-real em problemas de roteamento de veículos ao integrar características do mundo real, como matrizes de custo assimétricas e variáveis de distância e duração, através de inovações como Embedding de Nó Adaptativo e Viés Neural Adaptativo, validadas em um novo benchmark baseado em dados reais de 100 cidades.

O essencial

Imagine que você é o gerente de uma enorme empresa de entregas. Você tem 100 caminhões e milhares de pacotes para entregar em uma cidade gigante. O seu objetivo é simples: entregar tudo o mais rápido possível, gastando o mínimo de combustível.

Mas aqui está o problema: o mundo real é caótico.

A maioria dos computadores e algoritmos inteligentes que tentam resolver esse problema hoje em dia foram treinados em "mundos de fantasia". Eles imaginam que as cidades são feitas de círculos perfeitos, onde a distância do ponto A ao B é a mesma que do B ao A, como se você pudesse voar em linha reta sobre os prédios.

No mundo real, isso não existe.

• Você pode ir do ponto A ao B em 5 minutos, mas voltar do B ao A pode levar 20 minutos porque há um semáforo, uma rua de mão única ou um engarrafamento.
• O GPS pode dizer que a distância é 2 km, mas o tempo de viagem muda dependendo se é hora de pico ou se está chovendo.

Os algoritmos antigos falham porque eles não entendem essa "bagunça" do mundo real. É como tentar ensinar alguém a dirigir em uma pista de corrida perfeita e, de repente, soltá-lo no trânsito de São Paulo ou Nova York. Ele vai se perder.

A Solução: O "RRNCO" (O Motorista Inteligente)

Os autores deste artigo criaram um novo sistema chamado RRNCO. Pense nele como um motorista virtual superinteligente que não apenas olha para o mapa, mas "sente" o trânsito.

Eles fizeram duas coisas principais para criar esse motorista:

1. O "Óculos de Visão Mista" (Adaptive Node Embedding)

Imagine que você está dirigindo. Você olha para o GPS (que mostra a distância em linha reta) e também olha pela janela (que mostra o trânsito real, buracos, obras).
O RRNCO tem um mecanismo que funde essas duas visões. Ele não ignora a distância matemática, mas dá um peso enorme ao que está acontecendo na estrada de verdade. Ele aprende a dizer: "Ok, o mapa diz que é perto, mas a estrada está cheia, então vou pegar um caminho diferente."

2. O "Instinto de Trânsito" (Neural Adaptive Bias)

Esta é a parte mais genial. A maioria dos sistemas só olha para a distância. O RRNCO olha para três coisas ao mesmo tempo:

1. Distância: Quão longe é?
2. Tempo: Quanto tempo leva? (Que pode ser diferente de ida e volta).
3. Direção: Para onde estamos virando? (Virar à esquerda pode ser mais rápido que à direita, mesmo que a distância seja a mesma).

É como se o motorista tivesse um "instinto" que aprendeu com milhões de viagens reais. Ele sabe que, em certas ruas, virar à direita é sempre um pesadelo, mesmo que pareça a rota mais curta no papel.

O Grande Laboratório: 100 Cidades Reais

Para treinar esse "motorista", os autores não usaram mapas de fantasia. Eles criaram um laboratório gigante com dados reais de 100 cidades diferentes ao redor do mundo (de Nova York a Tóquio, de Lagos a Sydney).

Eles usaram dados reais de ruas, pontes, túneis e tráfego para criar milhões de cenários de entrega. Foi como se eles tivessem colocado o algoritmo para dirigir em todas essas cidades ao mesmo tempo, aprendendo com os erros e acertos do mundo real, e não de um simulador de videogame.

O Resultado: Quem Ganhou a Corrida?

Quando testaram esse novo sistema contra os melhores algoritmos tradicionais e outras inteligências artificiais:

• Os antigos: Ficaram confusos com as ruas de mão única e os tempos variáveis, entregando pacotes mais devagar e gastando mais combustível.
• O RRNCO: Foi muito mais rápido e eficiente. Ele encontrou rotas que os humanos e os computadores antigos não conseguiam ver.

Além disso, eles testaram em situações de trânsito imprevisível (como acidentes ou chuvas fortes). Enquanto os sistemas tradicionais travavam ou demoravam horas para calcular uma rota, o RRNCO ajustou o curso em frações de segundo, mantendo todas as entregas no prazo.

Resumo em uma Analogia

• Os algoritmos antigos são como um turista que usa um mapa de papel de 1990: sabe onde as ruas estão, mas não sabe que a rua principal foi fechada ou que o trânsito está parado.
• O RRNCO é como um motorista de aplicativo local que conhece cada atalho, sabe exatamente qual rua evitar na hora do rush e consegue prever o trânsito antes mesmo de chegar lá.

Conclusão:
Este trabalho é um passo gigante para levar a inteligência artificial da "teoria perfeita" para a "prática real". Agora, temos uma ferramenta que pode ajudar empresas de logística a economizar bilhões de dólares e reduzir a poluição, simplesmente entendendo que o mundo real não é feito de círculos perfeitos, mas de ruas complexas e cheias de surpresas.

E o melhor? Eles liberaram o código e os dados de graça para que qualquer pessoa possa usar e melhorar essa tecnologia.

Resumo técnico

Título: RRNCO: Rumo ao Roteamento no Mundo Real com Otimização Combinatória Neural

1. O Problema: A Lacuna Sim-to-Real no VRP

O artigo identifica uma barreira crítica na aplicação prática da Otimização Combinatória Neural (NCO) para Problemas de Roteamento de Veículos (VRP): a lacuna entre simulação e realidade (sim-to-real gap).

• Limitações Atuais: A maioria das pesquisas em NCO utiliza dados sintéticos simplificados baseados em distâncias euclidianas simétricas ($d_{ij} = d_{ji}$).
• Complexidade do Mundo Real: Redes viárias reais apresentam assimetrias (devido a ruas de mão única, restrições de giro, tráfego) e múltiplas modalidades de custo correlacionadas (distância, duração/tempo de viagem e ângulos direcionais).
• Falha Arquitetural: As arquiteturas atuais, baseadas em Transformers focados em nós, não conseguem incorporar eficientemente características de arestas ricas (matrizes de custo assimétricas) e estruturais, limitando sua aplicabilidade em logística real.

2. Metodologia: A Arquitetura RRNCO

Os autores propõem o RRNCO (Real-World Routing NCO), uma nova arquitetura neural projetada especificamente para lidar com a complexidade topológica e assimétrica do roteamento real. O modelo utiliza um framework encoder-decoder com duas inovações principais:

A. Adaptive Node Embedding (ANE) - Incorporação Adaptativa de Nós

• Objetivo: Fundir coordenadas espaciais com informações de distância assimétrica de forma eficiente.
• Mecanismo:
  • Em vez de processar a matriz de distância completa (o que seria computacionalmente caro), o ANE utiliza uma amostragem seletiva baseada em probabilidade (inversamente proporcional à distância) para capturar as relações mais relevantes.
  • Emprega um mecanismo de Gating Contextual (aprendido via MLP) para ponderar dinamicamente a importância das características baseadas em coordenadas versus as baseadas em distância para cada nó.
  • Gera embeddings duplos (linha e coluna) para capturar relações assimétricas, seguindo a lógica de modelos anteriores como MatNet, mas com integração mais rica de dados.

B. Neural Adaptive Bias (NAB) - Viés Adaptativo Neural

• Objetivo: Modelar conjuntamente múltiplas fontes de informação assimétrica (distância, duração e ângulos) dentro do mecanismo de atenção.
• Inovação: Substitui os vieses heurísticos manuais (como os usados no AAFM anterior) por um mecanismo aprendível.
• Funcionamento:
  • Processa três matrizes de entrada: Distância ($D$), Duração ($T$) e Ângulo Direcional ($\Phi$).
  • Utiliza um mecanismo de Gating Multi-Canal com normalização softmax para fundir essas representações heterogêneas em uma matriz de viés adaptativa ($A$).
  • Este viés $A$ é injetado no Adaptation Attention Free Module (AAFM), guiando o modelo a capturar padrões complexos de roteamento que dependem da interação entre tempo, distância e direção.

C. Geração de Dados e Treinamento

• O modelo é treinado usando Reinforcement Learning (RL) (gradiente de política com baseline POMO).
• A arquitetura permite a construção sequencial de soluções (autoregressiva), garantindo a viabilidade das restrições durante a geração.

3. Contribuições Chave

1. Arquitetura RRNCO: Um modelo NCO nativo capaz de lidar com assimetrias e múltiplas modalidades de custo (distância, tempo, ângulo) através do ANE e NAB.
2. Novo Benchmark de Mundo Real: Criação de um conjunto de dados abrangente e de código aberto baseado em dados de 100 cidades diversas ao redor do mundo.
   • Utiliza o OpenStreetMap e o motor de roteamento OSRM para gerar matrizes de distância e duração assimétricas reais.
   • Permite a geração online ilimitada de instâncias para treinamento de agentes de RL.
3. Resultados Empíricos de Ponta: Demonstração de desempenho superior em instâncias realistas, superando tanto métodos tradicionais quanto outras abordagens neurais.
4. Reprodutibilidade: Disponibilização completa do código, gerador de dados e modelos pré-treinados.

4. Resultados Experimentais

Os experimentos foram conduzidos em três variantes de VRP: ATSP (Problema do Caixeiro Viajante Assimétrico), ACVRP (VRP com Capacidade Assimétrica) e ACVRPTW (com Janelas de Tempo).

• Desempenho Geral: O RRNCO alcançou o estado da arte (SOTA) em todas as tarefas, superando métodos tradicionais (LKH3, PyVRP, OR-Tools) e outras redes neurais (POMO, MatNet, GOAL, AAFM).
• Qualidade da Solução: Em instâncias de distribuição (In-Distribution), o RRNCO obteve um gap de apenas 1.80% em relação à melhor solução conhecida (LKH3) para ATSP, enquanto métodos puramente neurais anteriores apresentavam gaps superiores a 30-40%.
• Generalização (Out-of-Distribution): O modelo demonstrou robustez significativa ao testar em cidades não vistas durante o treinamento e em distribuições de clusters diferentes, mantendo gaps baixos (ex: ~2.25% em OOD para ATSP).
• Eficiência: O tempo de inferência é extremamente rápido (segundos), comparável a outros métodos neurais e muito superior aos solvers tradicionais que levam horas.
• Cenários Estocásticos: Em testes com o benchmark SMTVRP (Problema de Roteamento Estocástico Multi-período Dependente do Tempo), o RRNCO (com extensão Multi-Snapshot NAB) manteve 100% de viabilidade e zero violações de janela de tempo, superando o OR-Tools, que falhou em encontrar soluções viáveis para 75,8% das instâncias dentro do limite de tempo.

5. Significado e Impacto

O trabalho representa um avanço crucial na transição da Otimização Combinatória Neural de ambientes acadêmicos sintéticos para aplicações logísticas reais.

• Ponte Sim-to-Real: Ao introduzir dados assimétricos reais e uma arquitetura capaz de processá-los, o RRNCO valida que redes neurais podem ser viáveis para logística complexa.
• Padrão de Dados: O novo dataset de 100 cidades estabelece um novo padrão para avaliação justa de solvers NCO, forçando a comunidade a considerar a complexidade do mundo real (trânsito, mão única, etc.).
• Aplicabilidade Prática: A capacidade de resolver problemas com restrições de tempo e capacidade em tempo real, com alta generalização, sugere que solvers neurais podem ser integrados em sistemas de logística para economizar custos operacionais e reduzir impactos ambientais.

Em resumo, o RRNCO não é apenas uma melhoria incremental, mas uma mudança de paradigma que alinha a modelagem neural com a realidade física e operacional das redes de transporte globais.