Resumo Técnico: Agrupamento Neural Primeiro, Roteamento Depois

Definição do Problema

O artigo aborda o Problema de Roteamento de Veículos com Capacidade (CVRP), um desafio fundamental na logística de última milha, onde uma frota de veículos com capacidade uniforme $Q$ deve atender a um conjunto de clientes com demandas específicas a partir de um depósito central, minimizando a distância total percorrida.

Os autores identificam limitações críticas nas abordagens atuais de Otimização Combinatória Neural (NCO):

1. Gargalos Autoregressivos (AR): Os métodos NCO dominantes constroem soluções token a token, levando a custos de decodificação sequencial, sensibilidade a simetrias espaciais e generalização frágil fora da distribuição (OOD).
2. Desconexão Metodológica: Enquanto o Problema do Caixeiro Viajante (TSP) é puramente uma tarefa de roteamento, o CVRP envolve fundamentalmente um problema de partição (empacotamento de clientes em clusters viáveis de capacidade) acoplado ao roteamento. Os métodos NCO existentes frequentemente tratam o CVRP como uma tarefa de geração de tours, deixando as restrições de capacidade para serem impostas por buscas post-hoc dispendiosas.
3. Desalinhamento de Benchmarks: Os benchmarks padrão reamostram coordenadas de nós de forma independente e identicamente distribuída (i.i.d.), ignorando o suporte geográfico fixo (por exemplo, a rede de ruas de uma cidade) típico da logística real, onde a mesma área é roteada diariamente com demandas variáveis.

Metodologia: Neural CFRS

Os autores propõem o Neural CFRS, o primeiro framework neural puramente não autoregressivo (NAR), de uma única etapa, baseado no paradigma clássico Agrupamento Primeiro-Roteamento Depois (CFRS). Em vez de gerar rotas sequencialmente, o modelo realiza uma atribuição global e diferenciável de clientes para clusters de veículos, após o que os TSPs independentes são resolvidos em paralelo.

A arquitetura opera em três fases:

1. Pré-treinamento e Prior de Suporte Espacial ($\Psi$)

Para abordar a geografia fixa da logística real, os autores pré-treinam um Autoencoder Mascarado Espacial (SMAE) sobre um conjunto fixo de locais potenciais de clientes ($X$).

• O SMAE aprende embeddings invariantes a $E(2)$ (invariantes a translação, rotação e reflexão) reconstruindo distâncias euclidianas pares e conectividade local $k$-NN sem consumir coordenadas absolutas.
• Esses embeddings congelados ($\Psi$) servem como um "vocabulário espacial", permitindo que o modelo a jusante generalize para novas instâncias de demanda no mesmo mapa sem reaprender a geometria.

2. Fase 1: Geração de Sementes

Um Transformador de Sementes (ST) identifica um subconjunto de nós para servir como centros de cluster iniciais ("sementes").

• Ele prevê probabilidades marginais para nós atuarem como sementes e aprende representações contrastivas para agrupar nós semelhantes.
• Uma estratégia de Decodificação Gananciosa Consciente de Capacidade seleciona $K$ sementes (onde $K$ é o tamanho estimado da frota) e empacota gananciosamente nós próximos nessas sementes com base na similaridade contrastiva, garantindo dispersão espacial e viabilidade de capacidade.

3. Fase 2: Atribuição Global via Transporte Ótimo Diferenciável

Um Transformador de Agrupamento (CT) computa distâncias latentes ($\Delta_{ij}$) entre clientes e as sementes selecionadas.

• Relaxação Diferenciável: Para impor restrições globais de capacidade de ponta a ponta, o Problema de Atribuição Capacitado (CAP) discreto é relaxado em um problema contínuo de Transporte Ótimo (OT).
• Algoritmo Sinkhorn-Knopp (SK): O modelo minimiza um objetivo de OT regularizado entrópico, produzindo um plano de transporte contínuo ($\hat{Y}$) que satisfaz as restrições de capacidade. Este plano atua como um substituto diferenciável para a matriz de atribuição discreta.

4. Fase 3: Decodificação OR

O plano de transporte contínuo $\hat{Y}$ guia um solver exato de Programação Mista Inteira (MIP) para recuperar os clusters discretos finais.

• Esparsificação: O modelo usa limiares de confiança para fixar atribuições de alta confiança (Atribuição Rígida) ou podar arestas de baixa probabilidade (Esparsificação Guiada por Sinkhorn).
• Isso reduz drasticamente o espaço de busca para o solver exato, que então resolve os subproblemas restantes como TSPs independentes usando solvers prontos (por exemplo, LKH-3).

Contribuições Principais

1. Framework Não Autoregressivo: Introduz o primeiro solver neural puramente NAR para CVRP que contorna gargalos de decodificação sequencial ao enquadrar o problema como uma tarefa de partição global.
2. Restrições de Capacidade Diferenciáveis: Desenvolve uma camada diferenciável de ponta a ponta inovadora usando Transporte Ótimo regularizado entrópico para impor restrições de capacidade da frota, fechando a lacuna entre atribuição neural e programação inteira exata.
3. Abstração de Simetria: Fornece garantias teóricas formais de que a arquitetura abstrai intrinsecamente as simetrias espaciais $E(2)$, permutação inter-rotas e simetrias de travessia intra-rotas por construção, eliminando a necessidade de aumento de dados dispendioso.
4. Prior de Suporte Espacial: Demonstra que alavancar um vocabulário espacial pré-treinado em geografia fixa permite eficiência extrema de parâmetros e escalabilidade zero-shot para tamanhos de problema grandes.

Resultados Experimentais

O framework foi avaliado tanto em configurações operacionais de capacidade constante (geografia fixa) quanto em benchmarks padrão (coordenadas i.i.d.).

• Generalização Zero-Shot: O Neural CFRS escala robustamente para instâncias fora da distribuição de até $N=1000$ clientes.
  • Sob uma configuração de capacidade constante ($Q=50$), alcança uma lacuna de otimalidade de < 4% em instâncias de $N=1000$ em menos de 30 segundos.
  • Notavelmente, uma arquitetura ultra-leve de camada única (682K parâmetros) mantém uma lacuna aproximada de 5% nessa escala, desafiando a noção de que arquiteturas profundas são necessárias para roteamento em grande escala.
• Benchmarks Padrão: No benchmark CVRP100 padrão, a variante de decodificação exata alcança uma lacuna de otimalidade de 2,73%, superando baselines autoregressivas gananciosas (por exemplo, POMO, BQ, LEHD) e competindo com heurísticas clássicas.
• Eficiência: O método elimina completamente a dependência de busca local post-hoc para o agrupamento inicial, confiando, em vez disso, na capacidade do modelo neural de guiar o solver exato.

Significado e Alegações

O artigo argumenta que o Neural CFRS representa uma mudança estrutural na NCO para problemas de roteamento:

• Alinhamento com Pontos Fortes de Aprendizado Profundo: Aproveita a capacidade do aprendizado profundo de aprender similaridade e atribuição sobre contexto global, em vez de forçá-lo a construir tours sequenciais longos.
• Viabilidade no Mundo Real: Ao respeitar suportes espaciais fixos e capacidades constantes, o framework alinha-se ao regime amortizado e sensível à latência da logística real, oferecendo um caminho viável para roteamento diário em áreas de serviço estáticas.
• Mudança de Paradigma: Os resultados sugerem que o ajuste específico da tarefa (por exemplo, pré-treinamento em suporte espacial) pode produzir resultados state-of-the-art sem ajuste fino extensivo, e que arquiteturas simples e rasas podem ser altamente eficazes quando acopladas aos vieses indutivos corretos (decomposição CFRS e priores espaciais).

Os autores concluem que, embora o framework desempenhe de forma competitiva, trabalhos futuros devem focar em melhorar a escalabilidade zero-shot para instâncias ainda maiores e refinar a capacidade do modelo de equilibrar a utilização de capacidade com eficiência espacial em casos extremos.