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

Dit paper introduceert SynthCharge, een parametrische generator die diverse en haalbare EVRPTW-instanties produceert met een screeningmechanisme voor haalbaarheid, waardoor een dynamische benchmarkinfrastructuur ontstaat voor de evaluatie van leer-gebaseerde optimalisatiemethoden.

De kern

Stel je voor dat je een super slimme robotbestuurder wilt trainen om elektrische vrachtwagens door een stad te sturen. Deze robot moet niet alleen de kortste weg vinden, maar ook rekening houden met twee belangrijke dingen: hoeveel batterij de vrachtwagen nog heeft en wanneer hij op tijd bij de klant moet zijn.

Dit is een heel lastig puzzelstukje, genaamd het "EVRPTW"-probleem (een beetje als een ingewikkeld bordspel voor elektrisch vervoer).

Het probleem met bestaande puzzels in de wetenschap is dat ze vaak statisch zijn. Het zijn als oude, vaste kaarten die niet veranderen. Als je een robot traint op één specifieke kaart, kan hij in de echte wereld faalspelen zodra de situatie iets anders is. Bovendien weten we bij die oude puzzels vaak niet eens of ze echt oplosbaar zijn; soms zijn ze gewoon onmogelijk, wat de robot gek maakt.

Hier komt SynthCharge om de hoek kijken.

Wat is SynthCharge?

SynthCharge is geen robot die zelf rijdt. Het is een slimme puzzelbouwer. Het is een computerprogramma dat oneindig veel nieuwe, unieke en realistische routes kan bedenken om robots op te leiden.

Je kunt het vergelijken met een videospel-level-editor, maar dan voor vrachtwagens:

• Je kunt kiezen of de klanten verspreid liggen als sprinkels op een koekje (willekeurig) of in groepjes bij elkaar zitten als huizen in een wijk (geclusterd).
• Je kunt de "batterij-regels" aanpassen: is de batterij groot genoeg om de hele stad te doen, of moet de vrachtwagen vaak stoppen om te laden?
• Je kunt de tijdspanne strakker of ruimer maken: moet de vrachtwagen binnen 10 minuten zijn, of heeft hij een uur de tijd?

De Magische Filter: "Kan dit wel?"

Het coolste aan SynthCharge is zijn veiligheidscontrole.

Stel je voor dat je een nieuwe route bedenkt. SynthCharge kijkt eerst heel snel naar de kaart en zegt: "Hé, die klant zit zo ver weg dat de vrachtwagen er nooit komt zonder te stoppen, en er is geen laadpunt in de buurt. Deze route is onmogelijk."

In dat geval gooit SynthCharge de route direct in de prullenbak en probeert hij het opnieuw. Dit noemen ze feasibility screening (haalbaarheidsfiltering).

• Vroeger: Wetenschappers gaven robots soms onmogelijke puzzels, waardoor de robots dachten dat ze dom waren, terwijl de puzzel gewoon fout was.
• Nu: SynthCharge zorgt ervoor dat elke puzzel die de robot krijgt, op zijn minst theoretisch oplosbaar is. Het is alsof je een bouwmeester bent die eerst checkt of de stenen wel passen voordat je de muur begint te bouwen.

Voor heel kleine puzzels (minder dan 10 klanten) doet het programma zelfs een extra, super-accurate check om 100% zeker te zijn. Voor grotere puzzels gebruikt het een snelle, slimme schatting.

Waarom is dit belangrijk?

Vroeger trainden we robots op een paar vaste kaarten. Dat is als een tennisleraar die je alleen maar laat oefenen op één specifiek veld. Als je dan op een ander veld speelt, met een andere wind, weet je niet of je goed bent.

Met SynthCharge kunnen we de robot trainen op duizenden verschillende situaties:

• Dikke regenbuien (strakke tijdslimieten).
• Een stad met veel heuvels (veel stroomverbruik).
• Klanten die verspreid liggen of in groepjes.

Dit zorgt ervoor dat de robot slimmer en robuuster wordt. Hij leert niet alleen een route uit het hoofd, maar leert hoe je een route bedenkt, ongeacht de situatie.

Samenvatting in één zin

SynthCharge is een puzzelfabriek die zorgt dat elke route die hij bedenkt, haalbaar is, zodat we elektrische vrachtwagens kunnen trainen om in elke denkbare situatie op de wereld veilig en op tijd te rijden.

Het is de basis voor een toekomst waarin onze bezorgrobots niet vastlopen in de file of doodgaan aan een lege batterij, omdat ze getraind zijn op de allerbeste, gevarieerde en realistische scenario's.

Technische samenvatting

Probleemstelling

Het Elektrische Voertuig Routeerprobleem met Tijdvensters (EVRPTW) is een uitbreiding van het klassieke VRPTW waarbij batterijcapaciteitsbeperkingen en beslissingen over het opladen (waar en wanneer) worden geïntegreerd. Hoewel er bestaande benchmark-datasets zijn, lijken deze vaak statisch, gebaseerd op eindige verzamelingen, en missen ze vaak verifieerbare haalbaarheid (feasibility). Dit beperkt de reproduceerbare evaluatie van nieuwe, op leren gebaseerde (learning-based) routing-modellen.

De belangrijkste uitdagingen zijn:

1. Generalisatieproblemen: Modellen getraind op een vaste verdeling van instanties presteren vaak slecht bij verschuivingen in ruimtelijke structuur, probleemgrootte of constraint-parameters.
2. Gebrek aan controle: Bestaande benchmarks bieden beperkte parametrische controle over ruimtelijke spreiding, klantgrootte en energier regimes.
3. Haalbaarheid: Veel gegenereerde instanties zijn structureel onoplosbaar (bijv. klanten die onbereikbaar zijn binnen de batterijrange), wat de evaluatie van algoritmen verstoort.

Methodologie: SynthCharge

De auteurs introduceren SynthCharge, een volledig parametrische generator voor EVRPTW-instanties. Het doel is om diverse, haalbaarheids-geteste instanties te genereren met controleerbare ruimtelijke, temporele en energetische kenmerken.

Kerncomponenten van de generator:

1. Ruimtelijke Topologie:

   • Genereert knooppunten (depot, klanten, laadstations) binnen een eenheidsvierkant $[0, 1]^2$.
   • Ondersteunt drie ruimtelijke families, geïnspireerd op Solomon's VRPTW:
     • Random (R): Klanten willekeurig verdeeld.
     • Clustered (C): Klanten gegroepeerd rond willekeurige centra.
     • Mixed (RC): Een combinatie van beide.
   • Het depot kan centraal, willekeurig of door de gebruiker gespecificeerd zijn.

2. Oplade-infrastructuur (Range-Aware):

   • Laadstations worden niet op vaste templates geplaatst, maar via bereik-bewuste regels gebaseerd op de maximale reikwijdte $R$ van het voertuig.
   • Regels plaatsen stations bij klanten die ver uit elkaar liggen of ver van het depot, zodat de reikwijdte niet wordt overschreden.
   • Het depot fungeert altijd als een laadlocatie.

3. Adaptieve Energie- en Serviceparameters:

   • Batterijcapaciteit: Wordt adaptief geschaald op basis van de ruimtelijke spreiding van de klanten (maximale afstand tussen klanten). Dit voorkomt dat instanties triviaal haalbaar of onmogelijk zijn bij het vergroten van de probleemgrootte.
   • Vraag en Tijdvensters: Klantvragen en service-tijden worden gestandaardiseerd. Tijdvensters worden gegenereerd met een breedteparameter $\phi$ (breed, medium, strak).

4. Tweestaps Haalbaarheids Screening (Feasibility Screening):
   Om de kwaliteit van de dataset te garanderen, wordt elke gegenereerde instantie gefilterd:

   • Fase 1 (Structurele Screening): Een snelle, lineaire check die voorwaarde-voorwaarde controleert:
     • Elke klant moet binnen bereik ($R$) van het depot of een laadstation liggen.
     • De terugreis naar het depot moet binnen het tijdvenster passen.
     • Er moet een laadstation bereikbaar zijn voor elke klant.
     • Instanties die hierin falen, worden direct verworpen en opnieuw gegenereerd.
   • Fase 2 (Exacte MILP Verificatie): Voor kleine instanties ($N \leq 10$) wordt een exacte Mixed Integer Linear Programming (MILP) solver gebruikt om te verifiëren of er daadwerkelijk een geldige route bestaat. Voor grotere instanties ($N > 10$) wordt alleen Fase 1 gebruikt vanwege de rekentijd.

5. Output en Metadata:

   • SynthCharge genereert bestanden in gestandaardiseerde .txt-formaten.
   • Elke instantie wordt vergezeld van een JSON-metadata-log met alle parameters en de status van de haalbaarheid, wat volledige reproduceerbaarheid garandeert.

Belangrijkste Bijdragen

1. Parametrische Generator: Een tool die systematische variatie toelaat in ruimtelijke structuur, klantgrootte (5 tot 500 klanten), tijdvenster-dichtheid en energier regimes.
2. Geometrie-Gecombineerde Schaling: Energiecapaciteit en laadstationplaatsing zijn gekoppeld aan de ruimtelijke spreiding, wat zorgt voor realistischere en minder triviale problemen.
3. Haalbaarheids-Filtering: Een geautomatiseerd proces dat structureel onoplosbare instanties verwijdert, wat essentieel is voor het trainen van betrouwbare ML-modellen.
4. Benchmark Infrastructuur: SynthCharge positioneert zich niet als een solver, maar als een infrastructuur om de robuustheid van neurale routing-methoden te testen onder verschillende distributieveranderingen.

Resultaten en Experimentele Evaluatie

De auteurs hebben de generator geëvalueerd op een workstation met een Intel i7-processor.

• Acceptatiepercentages ($\gamma$):
  • Er werden 2.475 instanties gegenereerd over verschillende combinaties van ruimtelijke families (R, C, RC) en tijdvenster-regimes (breed, medium, strak).
  • De acceptatiepercentages varieerden sterk (ongeveer 37% tot 47%), afhankelijk van de regio. Strakkere tijdvensters en cluster-verdelingen leidden tot lagere acceptatiepercentages, wat aantoont dat de filtering niet triviaal is.
• Genereer-efficiëntie:
  • Voor kleine instanties ($N \leq 10$) duurt het genereren ongeveer 0,06 - 0,10 seconden (door de dure MILP-verificatie).
  • Voor grotere instanties ($N > 10$) daalt de tijd drastisch naar $< 0,01$ seconden, omdat alleen de snelle structurele screening wordt toegepast.
  • Dit maakt SynthCharge geschikt voor het genereren van grote datasets voor training.
• Empirische Validatie:
  • Een metaheuristische solver (Variable Neighborhood Search/Tabu Search) kon 100% van de gefilterde instanties oplossen. Dit bevestigt dat de structurele screening (Fase 1) sterk correleert met werkelijke routeerbaarheid.
  • Strakkere tijdvensters en verspreidere ruimtelijke patronen leidden tot een toename in de benodigde vlootgrootte en de totale afgelegde afstand.

Betekenis en Conclusie

SynthCharge vult een cruciale lacune in de literatuur voor het Elektrische Voertuig Routeerprobleem. Door de afhankelijkheid van statische, eindige benchmarks te doorbreken, stelt het onderzoekers in staat om:

• De generalisatie van op leren gebaseerde modellen (zoals Reinforcement Learning) systematisch te testen onder verschillende distributieveranderingen.
• Reproduceerbare vergelijkingen te maken met transparante haalbaarheidschecks.
• De impact van distributieschiftingen (bijv. van willekeurig naar geclusterd, of van strakke naar ruime tijdvensters) op de modelprestaties te kwantificeren.

Hoewel de huidige versie beperkt is tot Euclidische afstanden, één depot en lineaire laadprofielen, vormt het een fundamentele stap naar robuustere, datagedreven logistieke optimalisatie voor duurzame vervoerssystemen. Toekomstig werk zal zich richten op multi-depot scenario's, niet-lineaire laadcurves en realistische wegnetwerken.