🤖 AI

Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation

Este artigo apresenta o EvoReal, um framework que aproveita a síntese evolutiva guiada por LLM para gerar instâncias de treinamento estruturalmente realistas e adaptar progressivamente solvers neurais, estreitando significativamente a lacuna de generalização entre dados sintéticos e benchmarks de roteamento do mundo real, como TSPLib e CVRPLib.

Autores originais: Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

Publicado 2026-01-30

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Grande Problema: As "Rodinhas de Apoio" vs. A "Estrada Real"

Imagine que você está ensinando um robô a ser o melhor motorista de entregas do mundo.

A Situação Atual:
Atualmente, ensinamos esses robôs (chamados de Solucionadores Neurais) usando "rodinhas de apoio". Geramos milhões de rotas de entrega falsas em um computador onde as casas estão perfeitamente espaçadas em uma grade organizada, como um tabuleiro de xadrez. O robô fica muito bom em resolver esses quebra-cabeças perfeitos e em formato de grade.

O Problema:
Quando você leva esse robô para o mundo real, ele bate. Cidades reais não são grades. Elas têm aglomerados de casas, estradas sinuosas e padrões estranhos. O robô, treinado apenas em grades perfeitas, fica confuso e cria rotas de entrega terríveis. Isso é chamado de lacuna de generalização. É como ensinar alguém a nadar em uma piscina calma e vazia e, depois, jogá-lo em um oceano tempestuoso com ondas e correntes.

A Solução: EvoReal (O "Simulador Inteligente")

Os autores deste artigo criaram um novo sistema chamado EvoReal. Em vez de apenas jogar o robô no oceano real, eles construíram um "Simulador Inteligente" que ensina o robô a lidar com a tempestade antes de ele sair da piscina.

Veja como funciona, passo a passo:

1. O "Arquiteto" (O LLM)

A equipe usou um Modelo de Linguagem de Grande Escala (LLM) — pense nele como um arquiteto superinteligente e criativo. O trabalho desse arquiteto não é dirigir o caminhão; é projetar os cursos de treinamento.

Normalmente, apenas criamos cursos de treinamento aleatórios. Mas o LLM é solicitado a olhar para mapas de entrega do mundo real (como os famosos benchmarks TSPLib e CVRPLib) e dizer: "Hmm, cidades reais têm estes padrões específicos: algumas áreas são lotadas, outras são espalhadas e algumas têm formas repetitivas."

2. A "Academia Evolutiva" (Evolução do Gerador)

O LLM não projeta apenas um curso; ele executa uma academia evolutiva.

Geração: O LLM escreve código para criar rotas de entrega falsas que parecem exatamente com cidades reais (com aglomerados, lacunas e formas estranhas).
Teste: Ele testa essas rotas falsas no robô.
Reflexão e Melhoria: Se o robô tiver dificuldades com um tipo específico de rota falsa, o LLM analisa o código, diz: "Ah, este gerador não fez os aglomerados serem apertados o suficiente," e reescreve o código para tornar o próximo lote de rotas falsas ainda mais realista.
Resultado: Com o tempo, o LLM evolui um "gerador" que cria dados sintéticos tão realistas que mimetizam estatisticamente o mundo real.

3. O "Treinamento Progressivo" (A Escada)

Depois que o LLM construiu esses cursos de treinamento "Semelhantes ao Mundo Real", o robô não pula direto para o nível mais difícil. Ele sobe uma escada:

Fase 1 (A Ponte): O robô é primeiro treinado nos novos dados sintéticos realistas do LLM. Ele aprende a lidar com aglomerados e padrões irregulares em um ambiente simulado seguro. É como praticar em uma piscina com ondas artificiais.
Fase 2 (O Mundo Real): Quando o robô está confiante, ele recebe uma sessão de treinamento curta e final nos problemas reais de benchmark. Como ele já aprendeu a "vibe" das cidades reais na Fase 1, ele se adapta instantaneamente.

Os Resultados: De "Bom no Xadrez" a "Grão-Mestre da Cidade"

O artigo testou isso em dois conjuntos famosos de problemas de roteamento do mundo real (TSPLib e CVRPLib).

Antes do EvoReal: Os melhores modelos de IA eram como estudantes que estudaram apenas para um tipo específico de prova de matemática. Quando viam um problema do mundo real, suas pontuações caíam significativamente (às vezes 30% ou mais).
Depois do EvoReal: Os modelos treinados com este método tornaram-se incrivelmente fortes.
- Nos benchmarks TSPLib (Caixeiro Viajante), a lacuna entre a solução deles e a solução perfeita encolheu para apenas 1,05%.
- Nos benchmarks CVRPLib (Roteamento de Veículos), a lacuna encolheu para 2,71%.

A Lição Principal:
O artigo afirma que, ao usar um LLM para evoluir melhores dados de treinamento (em vez de apenas evoluir o próprio robô), eles preencheram a lacuna entre o falso e o real. O robô aprendeu a generalizar porque foi treinado em dados "falsos" que pareciam exatamente com dados "reais".

Analogia de Resumo

Jeito Antigo: Ensinar um piloto a voar em um simulador sem vento e, depois, enviá-lo para dentro de um furacão.
Jeito EvoReal: Usar uma IA para projetar um simulador que replica perfeitamente a turbulência, a tesoura de vento e as tempestades de um furacão. O piloto treina neste simulador hiper-realista e, depois, entra no avião real e voa perfeitamente.

O artigo prova que a geração de melhores dados de treinamento (guiada por IA) é uma maneira mais poderosa de consertar esses robôs do que apenas ajustar os próprios robôs.

Resumo Técnico: Unindo Problemas de Roteamento Sintéticos e Reais via Geração de Instâncias Guiada por LLM e Adaptação Progressiva

Declaração do Problema

Métodos de Otimização Combinatória Neural (NCO) alcançaram desempenho de estado da arte em Problemas de Roteamento de Veículos (VRPs) sintéticos, particularmente aqueles com nós distribuídos uniformemente. No entanto, um lacuna de generalização significativa persiste quando esses modelos são aplicados a cenários de roteamento do mundo real, como os encontrados nos benchmarks TSPLib e CVRPLib. Os solvers neurais existentes lutam para se adaptar aos padrões estruturais heterogêneos e não uniformes inerentes aos conjuntos de dados autênticos. Embora os Grandes Modelos de Linguagem (LLMs) tenham mostrado promessa ao evoluir heurísticas e resolver Problemas de Otimização Combinatória (COPs) diretamente, eles frequentemente falham em lidar com instâncias de médio a grande porte (ex: >50 nós) devido a limitações de contexto e problemas de coerência no processamento de descrições textuais estendidas. Consequentemente, há uma necessidade de um framework que preencha a lacuna de distribuição entre os dados de treinamento sintéticos e os benchmarks do mundo real sem exigir mudanças arquiteturais nos solvers ou depender apenas de ajuste fino direto, que frequentemente produz melhorias limitadas.

Metodologia: EvoReal

Os autores propõem o EvoReal, um framework centrado em dados que utiliza LLMs para evoluir geradores de dados em vez de resolver os problemas de roteamento diretamente. O framework consiste em dois componentes primários: um módulo de evolução de instâncias guiado por LLM e uma estratégia de ajuste fino progressivo.

1. Síntese de Instâncias Evolutiva Guiada por LLM

Em vez de solicitar que os LLMs resolvam instâncias de TSP ou CVRP, o EvoReal solicita que eles gerem geradores de dados baseados em código que produzam instâncias sintéticas mimetizando distribuições do mundo real.

Representação do Gerador: Cada gerador é definido por uma descrição de função, uma implementação de código (baseada em PyTorch) e uma pontuação de aptidão (fitness score).
Alinhamento Estrutural: O processo evolutivo visa minimizar a divergência entre a distribuição sintética gerada pelo LLM ( $D(h_\phi(Z))$ ) e a distribuição real alvo ( $D_{real}$ ). A divergência é medida via métricas de aproximação, especificamente o gap de otimalidade médio em um conjunto de validação.
Modularização e Categorização: Para capturar diversos padrões estruturais, o conjunto de validação (TSPLib/CVRPLib) é segmentado em categorias baseadas em características estatísticas:
- Energia FFT: Mede a periodicidade global ou repetitividade.
- Razão NN (Coeficiente de Variação): Mede a variação nas distâncias de vizinho mais próximo para distinguir entre layouts em grade, aleatórios ou agrupados.
- Com base nessas métias, as instâncias são categorizadas em tipos (ex: S1 para estruturas repetitivas, S2 para estruturas tipo grade/fracamente agrupadas, S3 para agregações locais). Geradores especializados são evoluídos para cada categoria.
Processo Evolutivo: O framework adapta a abordagem ReEvo (Reflective Evolution) com modificações específicas:
- Seleção Baseada em Ranking: Seleciona descendentes com base no ranking de aptidão para acelerar a convergência.
- Seleção Retardada: A seleção ocorre após o cruzamento e mutação para evitar a eliminação prematura de candidatos diversos.
- Mecanismos de Reflexão: Utiliza reflexão de curto prazo (comparando pares de pais) e reflexão de longo prazo (destilando insights para guiar a mutação) para refinar iterativamente os geradores.

2. Estratégia de Ajuste Fino Progressivo

Uma vez identificados os geradores ideais, os solvers neurais pré-treinados (POMO e LEHD) passam por um processo de ajuste fino progressivo em duas fases para preencher a lacuna sintético-real:

Fase Um (Adaptação Estrutural): O modelo é ajustado finamente em dados sintéticos de larga escala gerados pelos geradores evoluídos e guiados por LLM. Esta fase expõe o modelo a diversos padrões estruturais do estilo TSPLib (distribuições mistas de S1, S2, S3) sem modificar a arquitetura do modelo. O objetivo é alinhar as representações internas do modelo com os priors estruturais dos dados do mundo real.
Fase Dois (Adaptação Direta): O modelo, agora adaptado a diversas estruturas, é submetido a um ajuste fino direto em instâncias reais de benchmark (TSPLib/CVRPLib). Esta fase permite que o modelo transite de tarefas sintéticas "fáceis" para casos reais "difíceis", estreitando efetivamente a lacuna de desempenho final.

Principais Contribuições

Framework EvoReal: A introdução de um novo framework que utiliza LLMs para evoluir geradores de dados em vez de solvers. Esta abordagem sintetiza instâncias de VRP estruturalmente realistas que mimetizam estatisticamente as distribuições do mundo real, abordando a causa raiz da lacuna de generalização.
Estratégia de Ajuste Fino Progressivo: Uma estratégia de adaptação de duas fases que primeiro alinha os solvers neurais com distribuições diversas evoluídas por LLM e, em seguida, os refina em dados reais de benchmark. Isso permite uma adaptação de domínio eficaz sem mudanças arquiteturais, superando o ajuste fino direto apenas em dados reais.
Desempenho de Estado da Arte: O framework demonstra melhorias significativas na generalização através de uma ampla gama de escalas de problemas nos benchmarks TSPLib e CVRPLib, alcançando novos resultados de estado da arte para solvers neurais.

Resultados Experimentais

Os autores avaliaram o EvoReal em 70 problemas TSPLib e 100 problemas CVRPLib SetX, comparando-o com solvers clássicos (Concorde, LKH-3, ORTools) e vários baselines neurais (POMO, LEHD, SGBS, CNF, etc.).

Desempenho TSPLib:
- LEHD (nosso) com 50 iterações RRC alcançou um gap de otimalidade geral de 1,05% no TSPLib, superando significativamente outros métodos baseados em aprendizado e aproximando-se do Concorde.
- POMO (nosso) reduziu o gap geral para 11,59%, uma melhoria substancial sobre o POMO pré-treinado (26,66%).
- O método mostrou força particular em instâncias de larga escala (1000–5000 nós), onde solvers neurais tradicionais tipicamente degradam significativamente.
Desempenho CVRPLib:
- LEHD (nosso) alcançou um gap geral de 2,71% no CVRPLib SetX, superando todos os outros solvers neurais e permanecendo competitivo com o ORTools.
- A estratégia de ajuste fino progressivo reduziu notavelmente a disparidade de desempenho entre instâncias pequenas e grandes.
Estudos de Ablação:
- A remoção de qualquer uma das fases (Fase 1 ou Fase 2) da estratégia de ajuste fino resultou em desempenho degradado, confirmando a necessidade da abordagem progressiva.
- A comparação de geradores evoluídos contra geradores de distribuição ingênuos (Gaussiana, Beta, etc.) mostrou que os geradores evoluídos por LLM alcançaram consistentemente menores gaps de otimalidade, validando sua capacidade de capturar características estruturais complexas.
- O framework provou ser robusto entre diferentes LLMs, com o OpenAI o3 produzindo o melhor desempenho de gerador.

Significância e Alegações

O artigo afirma que o EvoReal preenche com sucesso a lacuna de generalização entre problemas de roteamento sintéticos e do mundo real ao mudar o foco de evoluir solvers para evoluir distribuições de dados. Os autores enfatizam que sua abordagem:

Automatiza a Descoberta: Permite a descoberta automatizada de geradores de dados que se alinham com os priors estruturais do mundo real, uma tarefa difícil de alcançar com o design manual de heurísticas.
Eficiência: Alcança esses ganhos sem exigir o retreinamento custoso do zero ou modificações arquiteturais em solvers neurais de estado da arte existentes.
Escalabilidade: O método é eficaz em uma ampla gama de tamanhos de problema, abordando especificamente a degradação de solvers neurais em instâncias de larga escala, onde eles anteriormente falhavam em generalizar.
Superioridade sobre o Ajuste Fino Direto: Os resultados demonstram que adaptar modelos via distribuições sintéticas evoluídas (Fase 1) antes do ajuste fino direto (Fase 2) produz melhor generalização do que o ajuste fino direto em dados reais, sugerindo que o "currículo" de adaptação estrutural é crítico para a robustez.

Os autores concluem que este pipeline de adaptação baseado em geradores oferece uma direção promissora para aumentar a aplicabilidade prática dos métodos de NCO em cenários reais de logística e transporte.