SynthCharge: An Electric Vehicle Routing Instance Generator with Feasibility Screening to Enable Learning-Based Optimization and Benchmarking

O artigo apresenta o SynthCharge, um gerador paramétrico de instâncias do problema de roteamento de veículos elétricos com janelas de tempo que produz cenários diversos e verificados quanto à viabilidade, oferecendo uma infraestrutura dinâmica essencial para o benchmarking e avaliação de modelos de otimização baseados em aprendizado.

O essencial

Imagine que você é o gerente de uma frota de caminhões elétricos que precisam entregar pacotes em uma cidade. O desafio é duplo: você precisa entregar tudo dentro de um horário específico (janelas de tempo) e, ao mesmo tempo, garantir que os caminhões não fiquem sem bateria no meio do caminho.

Este problema é chamado de EVRPTW (Problema de Roteamento de Veículos Elétricos com Janelas de Tempo). Resolver isso na vida real é difícil, e para criar inteligência artificial (IA) que aprenda a fazer isso sozinha, os cientistas precisam de muitos "exercícios" ou exemplos para treinar o cérebro da máquina.

O problema é que os exercícios antigos eram como quebra-cabeças estáticos e repetitivos. Às vezes, eles eram tão fáceis que qualquer um ganhava, ou tão impossíveis que ninguém conseguia resolver, e não havia como saber se o exercício estava "quebrado" antes de começar.

É aqui que entra o SynthCharge, a ferramenta apresentada neste artigo.

O Que é o SynthCharge? (O "Chef de Cozinha" de Exercícios)

Pense no SynthCharge como um chef de cozinha robótico que não serve apenas um prato fixo, mas cria um cardápio infinito e personalizado de desafios de entrega.

Aqui está como ele funciona, usando analogias simples:

1. Criando o Cenário (A Cidade)

Em vez de usar mapas antigos e fixos, o SynthCharge desenha cidades novas a cada vez:

• Cidades Aleatórias: Como uma cidade onde as casas estão espalhadas sem padrão (como uma festa onde os convidados se misturam).
• Cidades Agrupadas: Como bairros onde as casas ficam muito juntas (como um condomínio fechado).
• Cidades Mistas: Uma combinação dos dois.

2. A Regra da Bateria (O Combustível)

A parte mais inteligente é como ele lida com a energia. Em muitos sistemas antigos, a bateria era definida de forma aleatória, o que podia criar situações ridículas (como um caminhão com bateria para ir até a Lua, ou bateria para ir apenas até o portão).

O SynthCharge usa uma regra de "olho clínico":

• Se a cidade é grande e as casas estão longe, ele automaticamente dá uma bateria maior para o caminhão.
• Se a cidade é pequena, ele ajusta a bateria para ser menor.
• Ele também coloca postos de recarga (como pontos de recarga de celular) em lugares estratégicos, garantindo que o caminhão nunca fique "preso" sem energia, mas também não tenha energia sobrando demais.

3. O Grande Filtro (O "Porteiro" da Férias)

Antes de entregar o exercício para a IA treinar, o SynthCharge faz uma verificação rápida, como um porteiro rigoroso:

• Ele pergunta: "Será que é fisicamente possível entregar esse pacote sem ficar sem bateria?"
• Se a resposta for "Não, é impossível", ele joga esse exercício fora e cria outro.
• Para exercícios pequenos, ele até usa um "supercomputador" para garantir matematicamente que a solução existe.

Isso é crucial porque ensina a IA a lidar com problemas reais e possíveis, e não com erros de lógica que só confundem o aprendizado.

Por que isso é importante? (O Treino de um Atleta)

Imagine tentar treinar um atleta olímpico para correr uma maratona.

• O jeito antigo: Você o colocava para correr sempre no mesmo parque, com a mesma distância e o mesmo clima. Ele ficaria ótimo naquele parque, mas se o dia da corrida fosse na praia ou na neve, ele falharia.
• O jeito SynthCharge: Você cria uma academia virtual com infinitas pistas: algumas com areia, outras com gelo, algumas curtas e íngremes, outras longas e planas. O atleta (a IA) aprende a se adaptar a qualquer situação.

O artigo mostra que, ao usar o SynthCharge, podemos testar se a inteligência artificial é realmente inteligente ou se ela apenas "decoreu" os exercícios antigos.

Resumo da Ópera

O SynthCharge é uma ferramenta que gera exercícios de entrega elétrica inteligentes, variados e verificados.

• Não é um solucionador: Ele não resolve o problema para você.
• É um gerador de testes: Ele cria o "campo de batalha" onde as novas inteligências artificiais podem ser testadas de forma justa e rigorosa.

Isso ajuda a garantir que, no futuro, quando usarmos caminhões elétricos autônomos para entregar nossa pizza ou remédios, eles não fiquem perdidos ou sem bateria, porque foram treinados em milhões de cenários diferentes e realistas criados por essa ferramenta.

Resumo técnico

Resumo Técnico: SynthCharge

1. O Problema

O Problema de Roteamento de Veículos Elétricos com Janelas de Tempo (EVRPTW) é uma extensão complexa do clássico VRPTW, incorporando restrições de capacidade da bateria e decisões sobre onde e quando recarregar.

• Limitações Atuais: Os conjuntos de dados de referência (benchmarks) existentes são frequentemente estáticos, limitados em tamanho e carecem de verificação explícita de viabilidade. Isso restringe a avaliação reprodutível de modelos de otimização baseados em aprendizado (como Redes Neurais e Aprendizado por Reforço).
• Desafio da Generalização: Modelos treinados em distribuições fixas de instâncias tendem a degradar seu desempenho quando enfrentam mudanças na estrutura espacial, tamanho do problema ou parâmetros de restrição (mudança de distribuição).
• Necessidade: Há uma demanda crítica por uma infraestrutura de benchmark dinâmica que permita a variação sistemática de características estruturais (geometria, janelas de tempo, capacidade energética) e garanta a viabilidade das instâncias geradas.

2. Metodologia: SynthCharge

O SynthCharge é um gerador de instâncias EVRPTW totalmente paramétrico projetado para criar dados sintéticos diversificados, viáveis e escaláveis.

A. Geração de Topologia Espacial

• As instâncias são geradas em um quadrado unitário $[0, 1]^2$.
• Suporta três famílias espaciais inspiradas nas estruturas de Solomon:
  1. Aleatória (R): Coordenadas amostradas uniformemente.
  2. Agrupada (C): Coordenadas geradas a partir de distribuições Gaussianas isotrópicas em torno de centros de cluster.
  3. Mista (RC): Combinação controlada das duas anteriores.
• O depósito pode ser central, aleatório ou especificado pelo usuário.

B. Infraestrutura de Recarga Inteligente

• Ao contrário de templates fixos, as estações de recarga são posicionadas usando regras conscientes do alcance (range-aware).
• Estações candidatas são inseridas para garantir a conectividade entre clientes distantes e entre clientes e o depósito, baseando-se no alcance máximo do veículo ($R$).
• Um processo de filtragem remove redundâncias e garante que as estações não estejam sobrepostas a clientes.

C. Escalonamento Adaptativo de Energia

• A capacidade da bateria ($B$) e o alcance máximo ($R$) são escalados adaptativamente com base na geometria da instância (ex: distância máxima entre clientes).
• Isso evita que instâncias sejam trivialmente viáveis ou sistematicamente inviáveis apenas devido ao tamanho ou dispersão espacial.

D. Processo de Triagem de Viabilidade (Feasibility Screening)
Para garantir a validade estrutural, o SynthCharge utiliza um processo de duas etapas:

1. Triagem Estrutural (Linear): Aplica verificações determinísticas rápidas para rejeitar instâncias com violações óbvias (ex: cliente inacessível dentro do alcance da bateria, impossibilidade de retorno ao depósito dentro do horizonte de tempo).
2. Verificação Exata (MILP): Para instâncias pequenas ($N \le 10$), utiliza um Programador Linear Inteiro Misto (MILP) para verificar a existência de uma rota viável que satisfaça todas as restrições de fluxo, tempo e energia.

E. Interface e Saída

• O sistema inclui uma GUI interativa para configuração de parâmetros.
• Exporta instâncias em arquivos .txt padronizados, acompanhados de logs de metadados JSON que registram a configuração completa e o status de viabilidade, assegurando reprodutibilidade.

3. Contribuições Principais

1. Gerador Paramétrico Dinâmico: Diferente de benchmarks estáticos, o SynthCharge permite a variação controlada de topologia espacial, regime de janelas de tempo (amplo, médio, apertado) e escalas de clientes (de 5 a 500).
2. Filtragem de Viabilidade Integrada: A introdução de um processo de triagem sistemática que elimina instâncias estruturalmente inválidas antes do uso, garantindo que os dados de treinamento e teste sejam de alta qualidade.
3. Metadados e Reprodutibilidade: Cada instância gerada vem com metadados completos (taxa de aceitação, parâmetros de geração), alinhando-se com as melhores práticas de transparência em ciência de dados ("Datasheets for Datasets").
4. Suporte à Avaliação de Generalização: Permite testar a robustez de algoritmos de otimização sob diferentes regimes de distribuição, essencial para o desenvolvimento de métodos de aprendizado de máquina em logística.

4. Resultados Experimentais

Os experimentos foram realizados em um workstation de alto desempenho, gerando milhares de instâncias para tamanhos de $N=5$ a $N=100$.

• Taxa de Aceitação ($\gamma$):
  • A taxa de aceitação variou significativamente dependendo do regime espacial e temporal.
  • Janelas de tempo mais apertadas reduziram a aceitação, especialmente em configurações agrupadas (Clustered).
  • Em média, a taxa de aceitação ficou entre 37% e 47%, indicando que a filtragem de viabilidade é um processo não trivial e necessário.
• Eficiência de Geração:
  • O tempo de geração por instância aceita é extremamente rápido.
  • Para $N \le 10$, o tempo é de ~0,1s (incluindo verificação MILP).
  • Para $N > 10$, o tempo cai para < 0,01s, pois apenas a triagem estrutural linear é aplicada.
• Validação Prática:
  • Uma metaheurística de busca (VNS/Tabu Search) foi aplicada em todas as instâncias geradas.
  • 100% das instâncias que passaram pela triagem do SynthCharge foram resolvidas com sucesso, confirmando que a triagem estrutural é um forte indicador de viabilidade real de roteamento.
• Impacto das Restrições:
  • O estudo mostrou que o apertamento das janelas de tempo e a dispersão espacial aumentam monotonicamente a distância percorrida e o tamanho da frota necessária.

5. Significado e Conclusão

O SynthCharge preenche uma lacuna crítica na pesquisa de logística sustentável e otimização combinatória. Ao fornecer uma infraestrutura de benchmark que combina geração controlada, validação explícita e transparência de dados, ele permite:

• A avaliação rigorosa e reprodutível de novos algoritmos de roteamento.
• O estudo da generalização de modelos de aprendizado de máquina sob mudanças de distribuição.
• A superação da dependência de conjuntos de dados estáticos e limitados.

Embora as limitações atuais incluam a restrição da verificação exata a instâncias pequenas e o uso de geometria euclidiana simples, o SynthCharge estabelece um novo padrão para a criação de benchmarks em sistemas de transporte inteligentes (ITS), com planos futuros para incluir múltiplos depósitos, curvas de recarga não lineares e redes viárias reais.