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

Il paper presenta SynthCharge, un generatore parametrico di istanze per il problema di routing dei veicoli elettrici con finestre temporali che, attraverso un processo di screening di fattibilità e una configurazione adattiva delle stazioni di ricarica, fornisce un'infrastruttura dinamica e verificabile per valutare modelli di ottimizzazione basati sull'apprendimento.

L'essenziale

Immagina di dover organizzare la consegna di 100 pacchi in una città usando un furgone elettrico. Sembra semplice, vero? Ma c'è un problema: il furgone ha una batteria che si scarica, e devi decidere quando e dove fermarti a ricaricare, tutto rispettando gli orari di apertura dei negozi (le "finestre temporali").

Se sbagli un calcolo, il furgone rimane a metà strada senza energia, o arriva troppo tardi. È un puzzle matematico molto difficile.

Gli scienziati che studiano come risolvere questi problemi con l'intelligenza artificiale (AI) hanno un grosso ostacolo: mancano le "palestre" giuste per allenare le loro macchine. I vecchi set di dati erano come vecchi libri di esercizi: fissi, limitati e a volte con errori nascosti (puzzle che in realtà non avevano soluzione).

Ecco dove entra in gioco SynthCharge.

Cos'è SynthCharge? (Il "Chef" dei Puzzle)

Pensa a SynthCharge non come a un risolutore di problemi, ma come a un chef che crea nuovi piatti ogni volta. È un generatore automatico di scenari per il trasporto elettrico.

Ecco come funziona, usando delle analogie semplici:

1. Crea il Territorio (La Città):
   Invece di usare sempre la stessa mappa, SynthCharge disegna città diverse ogni volta. A volte i negozi sono sparsi a caso (come stelle nel cielo), a volte sono raggruppati in quartieri (come marmo in un blocco), o un mix dei due. Questo serve a testare se l'AI è brava a navigare in situazioni diverse.

2. Regola la Batteria (Il Carburante):
   Qui sta il trucco intelligente. Se i negozi sono molto distanti tra loro, SynthCharge non ti dà una batteria piccola e ti dice "buona fortuna". Invece, adatta la batteria alla distanza. Se la città è grande, la batteria è più grande. Se è piccola, la batteria è più piccola. In questo modo, il puzzle è sempre "giocabile" ma non troppo facile. È come se il gioco si regolasse automaticamente sulla tua abilità.

3. Posiziona le Colonnine (I Rifugi):
   Le colonnine di ricarica non sono messe a caso. SynthCharge le posiziona come dei salvagenti in un mare di distanza. Se due negozi sono troppo lontani per essere raggiunti senza fermarsi, SynthCharge "lancia" una colonnina esattamente nel punto giusto per permettere al furgone di passare.

4. Il Controllo di Sicurezza (Il Filtro):
   Prima di darti il puzzle, SynthCharge fa un controllo rapido. Immagina un vigile che guarda la mappa e dice: "Ehi, questo negozio è così lontano che nemmeno un super-furgone potrebbe arrivarci". Se il puzzle è impossibile, lo scarta e ne crea un altro. Questo assicura che ogni scenario che l'AI studia sia reale e risolvibile.

Perché è importante?

Fino a oggi, gli scienziati allenavano le loro intelligenze artificiali su un set di dati vecchio e fisso. Era come allenare un calciatore solo su un campo di terra battuta. Quando poi il calciatore doveva giocare su erba o sotto la pioggia (situazioni reali diverse), falliva.

Con SynthCharge, possiamo:

• Allenare l'AI su tutto: Possiamo creare migliaia di scenari diversi (pioggia, sole, città grandi, città piccole) per rendere l'AI più robusta.
• Testare la verità: Sappiamo esattamente quali scenari sono risolvibili e quali no, perché il generatore lo sa.
• Confrontare equamente: Tutti possono usare gli stessi "puzzle" generati al volo per vedere chi ha l'algoritmo migliore.

In sintesi

SynthCharge è come una macchina del tempo per i problemi di consegna. Non risolve il problema per te, ma crea infinite versioni diverse e controllate del problema, pulite e pronte all'uso. Questo permette agli ingegneri di costruire sistemi di trasporto più intelligenti, efficienti e pronti per il futuro, assicurandosi che le loro intelligenze artificiali non si perdano mai per strada.

È uno strumento fondamentale per rendere la logistica elettrica non solo possibile, ma anche affidabile.

Sommario tecnico

1. Il Problema: EVRPTW e Limitazioni degli Attuali Benchmark

Il Problema di Instradamento dei Veicoli Elettrici con Finestre Temporali (EVRPTW) è un'estensione del classico VRPTW che introduce vincoli critici legati alla capacità della batteria e alle decisioni di ricarica. La transizione verso metodi di ottimizzazione basati sull'apprendimento (come il Reinforcement Learning) per risolvere questi problemi è ostacolata da due fattori principali:

• Mancanza di dati dinamici: I dataset di benchmark esistenti sono spesso statici, finiti e privi di una verifica rigorosa della fattibilità.
• Scarsa generalizzazione: I modelli neurali addestrati su distribuzioni fisse tendono a degradare quando affrontano cambiamenti nella struttura spaziale, nella dimensione del problema o nei parametri dei vincoli (shift di distribuzione).

Esiste quindi un bisogno urgente di un'infrastruttura di benchmarking che permetta la generazione controllata di istanze, la verifica esplicita della fattibilità e la valutazione della robustezza dei modelli sotto variazioni sistematiche delle caratteristiche del problema.

2. Metodologia: SynthCharge

Gli autori presentano SynthCharge, un generatore parametrico completo per istanze EVRPTW. A differenza dei generatori statici, SynthCharge integra la geometria dell'istanza con la scalabilità adattiva delle capacità energetiche e il posizionamento consapevole della gamma (range-aware) delle stazioni di ricarica.

Componenti Chiave del Generatore:

• Generazione Topologica Spaziale: Le coordinate dei nodi (deposito, clienti, stazioni) sono generate all'interno di un quadrato unitario $[0, 1]^2$. Supporta tre famiglie spaziali ispirate a Solomon:
  • Random (R): Distribuzione uniforme.
  • Clustered (C): Distribuzione gaussiana attorno a centri di cluster.
  • Mixed (RC): Una combinazione delle due.
• Infrastruttura di Ricarica Adattiva: Le stazioni di ricarica non sono posizionate su template fissi, ma secondo regole geometriche basate sulla portata massima del veicolo ($R$). Vengono inserite stazioni candidate per garantire la raggiungibilità tra clienti distanti o tra clienti e deposito, filtrando poi per ridondanza.
• Scalabilità Energetica Geometrica: La capacità della batteria ($B$) non è fissa, ma viene adattata in funzione della dispersione spaziale dell'istanza (distanza massima tra clienti). Questo evita che le istanze siano banalmente fattibili o sistematicamente irrisolvibili al variare della dimensione o della dispersione.
• Finestre Temporali: Vengono generate con una larghezza relativa ($\phi$) rispetto all'orizzonte temporale, permettendo regimi da "ampi" a "stretti".

Processo di Screening della Fattibilità (Due Stadi):

Per garantire la validità strutturale, SynthCharge applica un filtro in due fasi:

1. Screening Strutturale (Lineare): Controlli deterministici rapidi per eliminare istanze con violazioni ovvie (es. clienti irraggiungibili entro la portata della batteria, impossibilità di rientro al deposito entro l'orizzonte temporale). Questo stadio è applicato a tutte le istanze.
2. Verifica Esatta (MILP): Per istanze piccole ($N \le 10$), viene eseguito un solver esatto di Programmazione Lineare Intera Mista (MILP) per verificare l'esistenza di un percorso fattibile che soddisfi tutti i vincoli (flusso, finestre temporali, dinamica dell'energia).

3. Contributi Chiave

• Generatore Parametrico Dinamico: SynthCharge permette di variare sistematicamente la topologia spaziale, la scala dei clienti (da 5 a 500, con esperimenti su 5-100), la strettezza delle finestre temporali e i regimi energetici.
• Metadati di Fattibilità Espliciti: Ogni istanza generata è accompagnata da metadati che ne attestano lo stato di fattibilità, ottenuti tramite screening strutturale e, se applicabile, verifica MILP. Questo risolve il problema della "scatola nera" nei benchmark attuali.
• Infrastruttura per la Valutazione della Generalizzazione: Fornisce un ambiente controllato per testare la robustezza dei modelli di ottimizzazione basati su dati (neurali) contro shift di distribuzione, un requisito fondamentale per l'ottimizzazione combinatoria neurale.
• Riproducibilità: Utilizza generatori di numeri casuali con seed fissi per garantire che le istanze siano riproducibili e documentate con metadati JSON completi.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su istanze da 5 a 100 clienti, variando le combinazioni spaziali (R, C, RC) e temporali (ampio, medio, stretto).

• Tassi di Accettazione ($\gamma$): Il tasso di istanze che superano lo screening di fattibilità varia significativamente in base al regime.
  • Le finestre temporali più strette riducono il tasso di accettazione, specialmente nelle configurazioni Clustered.
  • I tassi medi di accettazione si attestano intorno al 40-47%, indicando che il filtro rimuove una porzione significativa di istanze irrealizzabili, rendendo il benchmark più rigoroso.
• Efficienza di Generazione:
  • Per $N \le 10$, il tempo di generazione è leggermente superiore (circa 0.10s) a causa della verifica MILP.
  • Per $N > 10$, il tempo crolla a meno di 0.01s poiché viene utilizzato solo lo screening strutturale lineare. Questo rende il generatore adatto alla creazione di grandi volumi di dati per l'addestramento.
• Validazione Empirica: L'uso di un meta-euristico di base (Variable Neighborhood Search/Tabu Search) ha dimostrato che il 100% delle istanze filtrate come "fattibili" dallo screening strutturale è effettivamente risolvibile, confermando l'efficacia del filtro.
• Impatto dei Vincoli: L'aumento della strettezza delle finestre temporali e la dispersione spaziale portano a un aumento monotono della distanza media percorsa e del numero di veicoli necessari (flotta).

5. Significato e Conclusioni

SynthCharge rappresenta un passo avanti significativo verso standard moderni per i benchmark nel campo dei sistemi di trasporto intelligenti (ITS) e dell'ottimizzazione combinatoria.

• Per la Ricerca sull'Apprendimento: Offre la possibilità di valutare come i modelli neurali generalizzano al di là della distribuzione di addestramento, affrontando il problema della generalizzazione omni-dimensionale.
• Trasparenza e Affidabilità: Introduce una cultura della "documentazione dei dati" (simile ai "Datasheets for Datasets"), fornendo metriche chiare sulla affidabilità dei dati generati.
• Limitazioni e Futuro: Attualmente limitato a geometrie euclidee, un singolo deposito e ricariche complete lineari. Il lavoro futuro prevede l'estensione a reti stradali reali, dinamiche temporali, ricarica parziale e configurazioni multi-deposito.

In sintesi, SynthCharge non è un algoritmo di risoluzione, ma un'infrastruttura di benchmarking essenziale per lo sviluppo e la validazione rigorosa di futuri algoritmi di routing per veicoli elettrici, sia tradizionali che basati sull'intelligenza artificiale.