RADAR: Learning to Route with Asymmetry-aware DistAnce Representations

O artigo apresenta o RADAR, um framework neural escalável que utiliza decomposição em valores singulares (SVD) e normalização Sinkhorn para permitir que solucionadores de problemas de roteamento de veículos lidem eficazmente com distâncias assimétricas, superando os métodos existentes em generalização e desempenho.

O essencial

Imagine que você é um gerente de entregas em uma cidade grande. Sua missão é enviar caminhões para entregar pacotes em vários endereços, voltando ao depósito no final, gastando o mínimo de combustível possível. Isso é o Problema de Roteamento de Veículos (VRP).

No mundo real, as coisas não são tão simples quanto em um mapa de videogame onde "o caminho mais curto é uma linha reta". Na vida real, existem ruas de mão única, trânsito que vai mais rápido em uma direção do que na outra, e obras que bloqueiam o retorno. Isso cria um cenário assimétrico: ir do ponto A ao B pode custar 10 minutos, mas voltar do B para o A pode custar 30 minutos.

A maioria dos "cérebros de computador" (Inteligência Artificial) que tentam resolver esse problema hoje em dia foram treinados em mundos perfeitos e simétricos, como um tabuleiro de xadrez. Quando eles tentam lidar com o caos das ruas reais (as assimetrias), eles se confundem e fazem planos ruins.

É aqui que entra o RADAR, o novo método apresentado neste artigo. Vamos explicar como ele funciona usando analogias simples:

1. O Problema: O Mapa Cego

Imagine que você tem um mapa de uma cidade, mas ele só mostra distâncias em linha reta (como se você pudesse voar). Se você tentar usar esse mapa para dirigir em ruas de mão única, você vai se perder.
Os computadores antigos tentavam "adivinhar" a direção olhando apenas para o ponto de partida. Eles diziam: "Ok, vou para o ponto A". Mas eles não entendiam que o ponto A tem uma "personalidade" diferente quando você chega nele (entrar) versus quando você sai dele (sair). Eles tratavam o ponto A como se fosse o mesmo em todas as direções, o que é um erro grave em cidades reais.

2. A Solução do RADAR: Dois Superpoderes

O RADAR resolve isso com duas técnicas principais, que chamaremos de O Espelho Mágico e O Balanço Perfeito.

A. O Espelho Mágico (Inicialização SVD)

Antes de começar a planejar a rota, o RADAR olha para todo o mapa de custos (a matriz de distâncias) e usa uma técnica matemática chamada Decomposição em Valores Singulares (SVD).

• A Analogia: Imagine que cada rua tem um "espelho". Quando você olha para o espelho de um lado, você vê a vista de quem está chegando; do outro lado, a vista de quem está saindo.
• Como funciona: O RADAR quebra o mapa complexo em duas partes: uma que representa quem sai de um lugar e outra que representa quem chega nele. Em vez de dar ao caminhoneiro um ponto cego, o RADAR lhe dá óculos especiais que mostram claramente: "Atenção! Sair daqui é fácil, mas entrar aqui é difícil". Isso cria uma "memória" inicial muito forte sobre a direção das ruas antes mesmo de o computador começar a calcular a rota.

B. O Balanço Perfeito (Normalização Sinkhorn)

Depois de ter os óculos especiais, o computador precisa decidir qual rua tomar a seguir. Normalmente, os computadores usam uma regra chamada "Softmax", que é como escolher o caminho mais popular entre os vizinhos imediatos.

• O Problema do Softmax: É como se você estivesse em uma festa e só olhasse para quem está gritando mais alto perto de você. Você ignora quem está gritando do outro lado da sala. Em ruas de mão única, isso é perigoso. Você pode escolher uma rua porque ela parece boa para você, mas sem perceber que ela está bloqueada para quem vem de trás.
• A Solução do RADAR (Sinkhorn): O RADAR troca essa regra por uma chamada Normalização Sinkhorn.
• A Analogia: Imagine um jogo de "cabo de guerra" ou um sistema de balanças. O RADAR não olha apenas para o que o caminhão "A" pensa sobre o caminhão "B". Ele também olha para o que o caminhão "B" pensa sobre o "A" e como o "B" se relaciona com todo o resto da cidade. Ele equilibra a atenção em duas direções ao mesmo tempo.
  • Se você está indo do A para o B, o RADAR pergunta: "O B é um bom destino para você?" E também: "O B é um bom ponto de partida para os outros?"
  • Isso garante que a decisão não seja baseada apenas no que está "perto", mas em como todo o sistema de ruas está conectado. É como ter um radar que vê o fluxo de tráfego em toda a cidade, não apenas no seu espelho retrovisor.

3. Os Resultados: Por que isso importa?

Os autores testaram o RADAR em:

1. Cenários Fictícios: Cidades geradas por computador com ruas de mão única complexas.
2. Cenários Reais: Dados de cidades reais (como as de RRNCO), com tráfego real e topografia complexa.

O Resultado?
O RADAR foi muito melhor do que os melhores métodos anteriores.

• Ele encontrou rotas mais curtas (economizando combustível e tempo).
• Ele funcionou bem mesmo quando o tamanho da cidade aumentava (de 100 para 1000 pontos), algo que os outros métodos falhavam em fazer.
• Ele se adaptou a diferentes tipos de problemas, desde entregas simples até entregas com janelas de tempo (você só pode entregar entre 14h e 16h).

Resumo Final

Pense no RADAR como um GPS de última geração que não apenas sabe onde você está, mas entende a "personalidade" de cada rua (se é de mão única, se é rápida de ida e lenta de volta) e equilibra suas decisões olhando para o todo, não apenas para o vizinho mais próximo.

Enquanto os outros computadores tentavam resolver o problema de roteamento como se fosse um jogo de tabuleiro simétrico, o RADAR aprendeu a dirigir no trânsito real, caótico e cheio de regras de mão única, entregando resultados mais rápidos, baratos e inteligentes.

Resumo técnico

Resumo Técnico: RADAR

1. O Problema

O Problema de Roteamento de Veículos (VRP) é um problema clássico de otimização combinatória NP-difícil. Embora solucionadores neurais recentes tenham alcançado alto desempenho em VRPs, a maioria deles assume distâncias euclidianas simétricas (onde a distância de A para B é igual à de B para A) e depende de coordenadas espaciais como entrada.

No entanto, cenários do mundo real (como tráfego urbano, ruas de mão única e congestionamentos dependentes do tempo) introduzem assimetrias significativas. Nesses casos, apenas uma matriz de distâncias assimétrica está disponível, e as coordenadas podem não existir ou não serem suficientes para capturar a topologia real.

• Desafio Principal: Como codificar eficazmente a estrutura relacional de matrizes de distância assimétricas em embeddings de nós que sejam compactos, generalizáveis e capazes de capturar tanto a assimetria estática (na entrada) quanto a dinâmica (durante o aprendizado)?
• Limitações Atuais: Métodos anteriores que codificam matrizes diretamente frequentemente falham em criar embeddings compactos ou generalizam mal para instâncias de grande escala. Outros métodos que usam inicializações "desinformadas" (como vetores aleatórios ou one-hot) introduzem ruído semântico e não capturam a estrutura global.

2. Metodologia: RADAR

O RADAR (Learning to Route with Asymmetry-aware DistAnce Representations) é um framework neural escalável que aprimora solucionadores existentes de VRP para lidar com entradas assimétricas. A abordagem trata a assimetria em duas frentes:

A. Assimetria Estática: Inicialização Baseada em SVD
Para capturar a estrutura direcional global da matriz de custos antes mesmo do início do raciocínio relacional, o RADAR propõe uma nova estratégia de inicialização:

• Decomposição em Valores Singulares (SVD): A matriz de distância assimétrica $D$ é decomposta em $D \approx U_k \Sigma_k V_k^T$.
• Embeddings de Origem e Destino: Os vetores singulares à esquerda ($U_k$) representam os nós como origens (saída), e os vetores à direita ($V_k$) representam os nós como destinos (entrada).
• Construção do Embedding: O embedding inicial do nó é formado pela concatenação das componentes esquerda e direita ponderadas pelos valores singulares ($X = [U_k\sqrt{\Sigma_k} | V_k\sqrt{\Sigma_k}]$).
• Definição de "Assimetria-Consciente": O papel define formalmente que um embedding é "assimetria-consciente" se puder reconstruir a matriz de distância original através de transformações lineares distintas para as interações de entrada e saída. A SVD truncada (top-k) garante que o modelo comece com representações que já codificam a direcionalidade global, melhorando a generalização para tamanhos de instância não vistos durante o treinamento.

B. Assimetria Dinâmica: Normalização Sinkhorn
Durante a codificação (encoder), a atenção padrão (Softmax) normaliza apenas as linhas, focando no contexto local do nó de origem e ignorando como o nó de destino interage com o resto do grafo.

• Substituição do Softmax: O RADAR substitui o Softmax por Normalização Sinkhorn.
• Mecanismo: A normalização Sinkhorn itera para normalizar simultaneamente linhas e colunas da matriz de atenção, tornando-a duplamente estocástica.
• Benefício: Isso impõe um fluxo bidirecional equilibrado. A pontuação de atenção entre $i$ e $j$ passa a refletir não apenas o contexto local de $i$, mas também a estrutura de vizinhança de $j$ em relação ao grafo inteiro. Isso permite capturar dependências direcionais globais que o Softmax padrão perde em cenários assimétricos.

3. Contribuições Principais

1. Avanço na Aplicabilidade Real: Investigação e solução eficaz de solucionadores neurais para VRPs sob matrizes de distância assimétricas realistas, superando a dependência de coordenadas euclidianas.
2. Inovação de Inicialização (SVD): Introdução de um esquema de inicialização baseado em SVD que captura relações direcionais globais, demonstrando superior generalização em diferentes tamanhos de instância (in-distribution e out-of-distribution).
3. Inovação de Atenção (Sinkhorn): Demonstração de que a normalização Sinkhorn traz ganhos substanciais ao capturar o contexto completo de vizinhança de ambos os nós interagentes, essencial para assimetria.
4. Avaliação Abrangente: Avaliação em 17 variantes sintéticas de VRP assimétrico e 3 conjuntos de dados do mundo real, superando consistentemente os baselines mais fortes (incluindo métodos tradicionais como LKH e HGS, e solucionadores neurais como MatNet, ICAM e ReLD).

4. Resultados Experimentais

Os experimentos foram conduzidos em GPUs NVIDIA RTX 3090, cobrindo instâncias sintéticas (ATSP e ACVRP) e dados reais (RRNCO).

• Desempenho em ATSP e ACVRP Sintéticos:
  • O RADAR alcançou os menores valores de objetivo e lacunas de otimalidade (gap) entre todos os métodos baseados em aprendizado.
  • Em instâncias de 1000 nós (ATSP1000), o RADAR manteve uma lacuna de apenas 4.13%, enquanto outros métodos neurais sofreram degradação severa (ex: gaps de >30% ou falha de generalização).
  • No ACVRP200, o RADAR superou até mesmo o solver tradicional LKH (com 1000 iterações).
• Aprendizado Multitarefa: Em um cenário com 16 variantes de VRP assimétrico, o RADAR obteve a menor lacuna média (1.33%) entre todos os métodos neurais, superando o RouteFinder e suas variantes.
• Dados do Mundo Real: Em benchmarks reais (ATSP, ACVRP e ACVRPTW), o RADAR superou consistentemente o estado da arte neural (RRNCO, MatNet) e métodos tradicionais (OR-Tools), mantendo gaps baixos em distribuições dentro e fora do conjunto de treinamento.
• Análise de Assimetria: O RADAR demonstrou robustez crescente à medida que o nível de assimetria aumentava (violação da desigualdade triangular), enquanto métodos com inicialização desinformada degradavam rapidamente.
• Eficiência: A etapa de SVD é computacionalmente leve e não se torna um gargalo em grande escala. A normalização Sinkhorn adiciona um custo marginal, mas melhora significativamente a convergência e a qualidade final.

5. Significado e Impacto

O trabalho RADAR preenche uma lacuna crítica entre a pesquisa de otimização combinatória neural e a aplicação prática. Ao demonstrar que é possível lidar com matrizes de distância puras (sem coordenadas) e assimetrias complexas sem sacrificar a escalabilidade, o RADAR torna os solucionadores neurais viáveis para cenários logísticos reais, como entregas urbanas com tráfego unidirecional.

A combinação de inicialização estruturada (SVD) e atenção balanceada (Sinkhorn) oferece um novo paradigma para modelagem de grafos direcionais em otimização, sugerindo que a incorporação correta de sinais de aresta (edge signals) na inicialização e no mecanismo de atenção é fundamental para a generalização em problemas de roteamento assimétrico. O código e os dados estão disponíveis publicamente, facilitando a reprodução e adoção pela comunidade.