Resumo Técnico: Aprendizado com Previsão (MnLP)

Declaração do Problema

Problemas de Roteamento de Veículos (VRPs), incluindo o Problema do Caixeiro Viajante (TSP) e o Problema de Roteamento de Veículos com Capacidade (CVRP), são desafios NP-difíceis prevalentes em logística e planejamento industrial. Embora políticas de roteamento neural, particularmente aquelas baseadas em arquiteturas Transformer, tenham surgido como alternativas eficientes às heurísticas tradicionais, os paradigmas de treinamento atuais enfrentam uma limitação fundamental.

A maioria das abordagens de aprendizado supervisionado (SL) para roteamento neural depende da previsão do próximo nó. Neste paradigma, o modelo é treinado para prever apenas o nó imediato seguinte em uma rota com base no estado atual. Os autores argumentam que essa abordagem leva a tomada de decisões míopes. Como a construção de soluções para VRP é uma tarefa de planejamento de longo horizonte envolvendo centenas ou milhares de nós, otimizar apenas para o próximo passo imediato falha em capturar o contexto de longo alcance necessário para a optimalidade global. Isso resulta em acúmulo de erros e uma tendência a estabilizar em ótimos locais, particularmente à medida que os tamanhos dos problemas aumentam.

Metodologia: Previsão com Antecipação Multi-Nó (MnLP)

Para abordar a miopia da previsão padrão do próximo nó, o artigo propõe a Previsão com Antecipação Multi-Nó (MnLP), uma estratégia de treinamento inovadora que expande o paradigma de aprendizado supervisionado.

Conceito Central

O MnLP introduz um mecanismo onde o modelo é treinado para prever múltiplos nós futuros simultaneamente (por exemplo, os próximos $K$ nós) além do nó imediato seguinte. Isso é alcançado por meio de módulos MnLP causais e descartáveis que operam exclusivamente durante a fase de treinamento.

Arquitetura

O framework proposto baseia-se no modelo Codificador Leve e Decodificador Pesado (LEHD):

1. Codificador Compartilhado: Um codificador leve processa características brutas dos nós (por exemplo, coordenadas) em embeddings de nós.
2. Decodificador Principal: Prevê o nó imediato seguinte ($x_t$) usando mecanismos de atenção padrão.
3. Módulos MnLP: Uma série de $K$ módulos auxiliares ($k=1, \dots, K$) é adicionada.
   • Cadeia Causal: O $k$-ésimo módulo prevê o nó no passo $t+k$ ($x_{t+k}$). Ele recebe informações contextuais do módulo $(k-1)$ e do embedding de verdade fundamental do nó no passo $t+k-1$. Isso impõe uma cadeia causal onde previsões para passos futuros dependem da sequência de passos anteriores.
   • Viabilidade: Os módulos respeitam as restrições do problema (por exemplo, nós não visitados para TSP, restrições de capacidade para CVRP) mascarando nós inviáveis nos logits de saída.
   • Descartável: Crucialmente, esses módulos MnLP são removidos durante a inferência. Apenas a cabeça principal de próximo nó é utilizada, garantindo zero sobrecarga computacional adicional no momento do teste.

Objetivo de Treinamento

A perda de treinamento é uma soma ponderada da perda da tarefa principal e das perdas auxiliares de antecipação:
$$\mathcal{L} = \mathcal{L}_{\text{main}} + \gamma \mathcal{L}_{\text{MnLP}}$$
Onde:

• $\mathcal{L}_{\text{main}}$ é a perda de entropia cruzada padrão para previsão do próximo nó.
• $\mathcal{L}_{\text{MnLP}}$ é a perda média de entropia cruzada através dos $K$ módulos de antecipação.
• $\gamma$ é um hiperparâmetro que controla o peso da supervisão auxiliar, que é aumentado linearmente durante um período de aquecimento para evitar que a tarefa auxiliar domine o treinamento inicial.

Essa supervisão multi-profundidade atua como um regularizador, incentivando o codificador a aprender representações que capturam dependências de longo alcance e melhorando a atribuição de crédito através da sequência.

Contribuições Principais

1. Design Arquitetural Inovador: A introdução de módulos MnLP que permitem previsão multi-etapa durante o treinamento sem alterar a arquitetura de inferência ou adicionar latência no momento da inferência.
2. Supervisão Auxiliar Multi-Profundidade: Uma estratégia de treinamento que guia o modelo a antecipar decisões futuras além do próximo passo imediato, mitigando efetivamente o viés de exposição e o comportamento míope.
3. Validação Empírica: Experimentos extensivos demonstrando que o MnLP aprimora a generalização através de diferentes tamanhos de problemas, distribuições e benchmarks do mundo real.

Resultados Experimentais

Os autores avaliaram o MnLP em instâncias de TSP e CVRP de tamanhos variados (100 a 1000 nós) e distribuições (uniforme, rotação, explosão e benchmarks do mundo real como TSPLib e CVRPLib).

• Ganhos de Desempenho: O MnLP superou consistentemente o modelo LEHD de base. Por exemplo, no TSP com 1000 nós, a lacuna de optimalidade melhorou de 3,563% (LEHD) para 2,852% (MnLP), uma melhoria relativa de 20%.
• Generalização: O método demonstrou superior generalização cruzada de tamanho e cruzada de distribuição. Em instâncias de grande escala ($n=1000$), a lacuna de desempenho entre MnLP e as bases aumentou, sugerindo que o mecanismo de antecipação é particularmente eficaz para planejamento complexo de longo horizonte.
• Benchmarks do Mundo Real: O MnLP alcançou resultados state-of-the-art entre políticas neurais no TSPLib e CVRPLib, superando outras estratégias de treinamento avançadas como POMO (baseada em RL) e SA-DABL (SL com aumento).
• Eficiência: Como os módulos MnLP são descartados na inferência, o método mantém a mesma velocidade de inferência que o modelo LEHD de base.

Significado e Alegações

O artigo afirma que o MnLP aborda um gargalo crítico na otimização combinatória neural: a incapacidade da previsão padrão do próximo nó de capturar sinais de planejamento de longo horizonte. Ao injetar compreensão contextual de longo alcance no processo de treinamento sem comprometer a eficiência da inferência, o MnLP oferece uma maneira escalável e eficaz de aprimorar políticas de roteamento neural.

Os autores posicionam o MnLP como uma estratégia de treinamento generalizável que pode ser integrada perfeitamente a diversas arquiteturas neurais. Eles argumentam que o sucesso do MnLP valida a hipótese de que a supervisão multi-etapa é essencial para treinar políticas neurais robustas capazes de resolver problemas de roteamento complexos e de grande escala, fechando a lacuna entre tomada de decisão local e optimalidade global.