Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

Resumo Técnico: Modelo de Fundação Assistido por Visão para Resolução de Problemas de Roteamento de Veículos Multitarefa

Definição do Problema
Problemas de Roteamento de Veículos (VRP) multitarefa envolvem a otimização de custos de roteamento enquanto satisfazem diversas restrições de clientes, tais como demandas de retorno (B - backhaul), rotas abertas (O - open routes), limites de duração (L - duration limits) e janelas de tempo (TW - time windows). A combinação dessas restrições cria um número exponencial de variantes de VRP (por exemplo, 16 variantes a partir de quatro restrições). Os resolvedores neurais existentes normalmente dependem de modalidades baseadas em grafos, codificando restrições como atributos de nós. No entanto, essas abordagens enfrentam limitações: elas têm dificuldade em aprender relações espaciais complexas e interações de restrições à medida que as tarefas se tornam mais intrincadas, e treinar modelos separados para cada variante é computacionalmente proibitivo. Além disso, os métodos baseados em visão existentes para otimização combinatória têm sido limitados a cenários de tarefa única (ex: TSP) e frequentemente falham em codificar atributos específicos da tarefa, como demandas e janelas de tempo, dentro da representação visual.

Metodologia: Modelo de Fundação Assistido por Visão (VaFM)
Os autores propõem o VaFM, um modelo de fundação que integra modalidades de visão e grafos para resolver 16 variantes diferentes de VRP simultaneamente. A arquitetura consiste em três componentes principais:

1. Geração de Imagem de VRP Multitarefa: Para abordar a falta de representação de restrições nas imagens de VRP existentes, os autores projetam duas imagens de entrada por instância: uma "imagem de demanda" e uma "imagem de janela de tempo (TW)".

   • Codificação Visual: Coordenadas de clientes são mapeadas para índices de pixels. A intensidade da cor do nó representa variáveis contínuas (magnitude da demanda ou duração da janela de tempo).
   • Representação de Restrições: Restrições discretas são codificadas via pistas visuais: Rotas Abertas (O) são indicadas pela inversão da cor do fundo; Limites de Duração (L) são mostrados pela mudança de formas dos nós (retângulos para sinais de mais); Demandas de Retorno (B) usam cores de nós distintas (verde para linehaul, azul para backhaul).
   • Entrada: As duas imagens são concatenadas e processadas por um codificador de visão baseado em CNN (ResNet-18).

2. Módulo de Fusão de Atenção Cruzada Híbrida: Para superar o campo receptivo fixo dos embeddings de patch padrão e acomodar requisitos variados de tarefas, o VaFM emprega um mecanismo de fusão híbrida.

   • Mecanismo: Mapas de características das duas últimas camadas do codificador de visão são extraídos. Os embeddings de patch são derivados desses mapas e alinhados com os embeddings dos nós do grafo.
   • Campo Receptivo Adaptativo: Um mecanismo de atenção cruzada é usado onde os embeddings dos nós atuam como queries e os mapas de características achatados da camada mais profunda atuam como keys e values. Isso permite que o modelo agregue informações globais relevantes (da camada profunda) enquanto retém o contexto local refinado (da camada rasa), criando efetivamente campos receptivos adaptativos para diferentes restrições.

3. Tarefa Auxiliar Consciente de Restrições: Para mitigar o problema da distribuição desequilibrada de pixels (onde restrições como O ou L ocupam mais pixels do que B ou TW, potencialmente fazendo com que o modelo negligencie estas últimas), uma tarefa auxiliar é introduzida.

   • Implementação: Um classificador é anexado ao codificador de visão para prever a presença de cada uma das quatro restrições (O, L, B, TW).
   • Função de Perda: A perda de Entropia Cruzada Binária (BCE) é aplicada a esta tarefa auxiliar, garantindo que o modelo aprenda representações equilibradas para todas as restrições, independentemente de sua proeminência visual.
   • Objetivo de Treinamento: A perda total é uma soma ponderada da perda de Aprendizado por Reforço (RL) para minimização do custo de roteamento e da perda de classificação auxiliar.

Principais Contribuições

• Primeiro Modelo de Fundação Assistido por Visão para VRPs Multitarefa: O trabalho introduz o primeiro framework que combina modalidades de grafo e visão para lidar com múltiplas variantes de V de forma simultânea, indo além dos resolvedores de visão de tarefa única.
• Inovação na Codificação Visual e Fusão: O artigo propõe designs de imagem específicos para codificar diversas restrições e um módulo de fusão de atenção cruzada híbrida que permite campos receptivos adaptativos, abordando as limitações de tamanhos de patch fixos em configurações multitarefa.
• Aprendizado de Restrições Equilibrado: A introdução de uma tarefa auxiliar consciente de restrições com perda BCE evita efetivamente que o modelo negligencie restrições com menos pixels visuais.

Resultados Experimentais
O modelo foi avaliado em 16 variantes de VRP com 50 e 100 nós de clientes, comparando-se com métodos de Estado da Arte (SOTA) incluindo HGS-PyVRP, OR-Tools e vários resolvedores neurais (MTPOMO, MVMoE, RF-MoE-L).

• Desempenho: O VaFM (especificamente a variante VaFM-MoE-L) alcançou o melhor desempenho em 15 de 16 casos para N=50 e 12 de 16 para N=100.
• Restrições Complexas: A lacuna de desempenho entre o VaFM e as bases apenas de grafo aumentou conforme o número de restrições cresceu. Por exemplo, em tarefas com 3 ou 4 restrições, o VaFM mostrou melhorias significativas no gap de otimalidade em comparação com a base RF-MoE-L.
• Generalização: Embora o VaFM tenha mostrado forte generalização zero-shot para escalas maiores (N=200) e combinações de restrições não vistas (mistura de backhaul), ele exibiu certa instabilidade em conjuntos de dados do mundo real e tarefas pesadas em janelas de tempo, sugerindo limitações na discriminação baseada em cores em escalas maiores.
• Eficiência: O VaFM requer um pouco mais de tempo de inferência do que as bases apenas de grafo devido ao ramo de visão, mas permanece significativamente mais rápido que resolvedores heurísticos como o HGS-PyVRP.

Significância e Alegações
O artigo afirma que o VaFM demonstra o potencial de integrar modalidades de visão em resolvedores neurais baseados em grafos para melhorar a representação de problemas de otimização complexos e multiconstraint. Os autores afirmam que sua abordagem captura com sucesso a semântica de nível de patch (distribuições espaciais de demanda e padrões de tempo de serviço) que são difíceis de serem aprendidas por modelos puramente de grafo. Os resultados sugerem que modelos assistidos por visão são particularmente superiores para variantes de VRP com restrições complexas e interativas. No entanto, os autores reconhecem modestamente as limitações, observando que a codificação visual atual (baseada em intensidade de cor única) pode ter dificuldades com a discriminação fina em instâncias de grande escala e que trabalhos futuros são necessários para melhorar a generalização em conjuntos de dados do mundo real e restrições não vistas, potencialmente através de modelos de linguagem de grande escala multimodais.