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

The paper introduces SynthCharge, a parametric generator that creates diverse, feasibility-screened Electric Vehicle Routing Problem with Time Windows (EVRPTW) instances to provide a dynamic benchmarking infrastructure for evaluating learning-based optimization models.

The Gist

Imagine you are the manager of a fleet of electric delivery trucks. Your job is to get packages to hundreds of customers, but there's a catch: your trucks run on batteries, they have strict delivery time windows, and they need to stop at charging stations to refuel. This is the Electric Vehicle Routing Problem with Time Windows (EVRPTW).

Solving this puzzle is incredibly hard. If you get it wrong, a truck might run out of juice in the middle of nowhere, or arrive too late for a customer.

For years, researchers trying to teach computers (using AI) how to solve this have been stuck with a major problem: The test questions were broken or boring. Existing datasets were like a static textbook with only 20 fixed problems. They didn't change, they didn't get harder, and sometimes, the problems were actually impossible to solve, but no one knew it. This made it hard to tell if a new AI was actually smart or just lucky.

Enter SynthCharge.

What is SynthCharge?

Think of SynthCharge not as a solver, but as a high-tech "Video Game Level Generator" for delivery trucks.

Instead of giving you a single, static map, SynthCharge is a machine that can instantly create thousands of unique delivery scenarios. It can make the city layout random, clustered (like neighborhoods), or a mix. It can make the time windows tight (like "deliver this in 5 minutes!") or loose. It can even adjust the battery size and the location of charging stations on the fly.

The "Feasibility Screening" (The Bouncer)

The coolest part of SynthCharge is its Feasibility Screening.

Imagine you are a bouncer at a club. Before you let anyone in, you check their ID. If they look too young or are clearly drunk, you send them home immediately. You don't waste time trying to get them a drink if they aren't allowed in.

SynthCharge does the same thing for delivery routes:

1. The Quick Check (Stage 1): It looks at the map and asks, "Is this even possible?" For example, if a customer is 100 miles away but the truck only has a 50-mile battery, SynthCharge says, "Nope, this is impossible," and throws the scenario in the trash. It does this in a split second.
2. The Deep Dive (Stage 2): For very small, simple maps, it runs a super-precise math check to be 100% sure a route exists.

Why is this important?
Before SynthCharge, researchers were training AI on a mix of "solvable" and "impossible" problems. It's like teaching a student to drive by putting them in a car with no brakes. SynthCharge filters out the broken cars first, so the AI only learns from scenarios that are actually possible to solve.

How It Works (The Recipe)

SynthCharge mixes ingredients to create a new "level":

• The Map: It draws the city. It can make customers scattered like stars (Random), bunched up like ants in a hill (Clustered), or a mix.
• The Battery: It doesn't just pick a random battery size. It looks at how spread out the customers are. If the customers are far apart, it gives the truck a bigger battery. If they are close, a smaller one. This keeps the game fair and challenging.
• The Charging Stations: It doesn't just drop charging stations randomly. It places them strategically, like gas stations on a highway, ensuring that no matter where the truck goes, it can reach a charger before running out of power.

Why Should We Care?

This tool is a game-changer for Artificial Intelligence.

Right now, AI models for routing are like students who memorize the answers to a specific test. If you give them a slightly different test, they fail. Because SynthCharge can generate infinite variations of the problem, it forces AI to learn the principles of routing, not just memorize answers.

It allows researchers to ask: "Does this AI work if the city is crowded? What if the time windows are super tight? What if the batteries are small?"

The Bottom Line

SynthCharge is a tool that builds a massive, diverse, and verified playground for electric delivery trucks. It ensures that when we test new AI drivers, we aren't testing them on broken maps. It helps us build smarter, more reliable logistics systems for the future of electric transportation, ensuring that when the AI says, "I can deliver this," it actually means it.

Technical Summary

1. Problem Statement

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) extends the classical VRPTW by incorporating battery capacity constraints and decisions regarding where and when to recharge. While exact and hybrid optimization methods exist, their high computational costs limit real-time application, driving a shift toward learning-based routing methods (e.g., Reinforcement Learning, Neural Combinatorial Optimization).

However, current research faces a critical bottleneck: generalization. Models trained on fixed benchmark datasets often degrade when exposed to shifts in spatial structure, problem size, or constraint parameters. Existing benchmark suites (e.g., extensions of Solomon's VRPTW) are:

• Static and Finite: They lack parametric control to systematically vary instance characteristics.
• Lacking Feasibility Verification: They often do not provide verified feasibility labels, making it difficult to distinguish between model failure and instance infeasibility.
• Homogeneous: They do not sufficiently capture the diversity of real-world operational regimes.

The paper argues for a new benchmark infrastructure that supports controlled, reproducible evaluation across varying spatial, temporal, and energy constraints.

2. Methodology: SynthCharge Generator

The authors introduce SynthCharge, a fully parametric instance generator designed to produce diverse, feasibility-screened EVRPTW instances. The methodology is structured as follows:

A. Instance Generation Parameters

• Spatial Topology: Generates nodes within a unit square $[0, 1]^2$ using three families inspired by Solomon's structures:
  • Random (R): Uniform distribution.
  • Clustered (C): Gaussian distributions around cluster centers.
  • Mixed (RC): A combination of both.
• Charging Infrastructure: Unlike static templates, station placement is range-aware. Stations are dynamically inserted based on vehicle travel range ($R$) to ensure:
  • Customer-Customer Reachability: If two customers are far apart ($d_{ij} > 0.8R$), a station is placed near the midpoint.
  • Customer-Depot Reachability: If a customer is far from the depot ($d_{0i} > 0.7R$), a station is placed along the ray to ensure return capability.
• Energy Scaling: Battery capacity ($B$) is scaled adaptively based on the maximum pairwise customer distance ($d_{max}$) to ensure instances are energy-constrained but generally reachable.
• Time Windows: Defined by a planning horizon $H$ and a width fraction $\phi$, allowing for "wide," "medium," and "tight" regimes.

B. Two-Stage Feasibility Screening

To guarantee structural validity, SynthCharge employs a rigorous screening process:

1. Stage 1: Linear-Time Structural Screening: Applies deterministic necessary conditions to filter out trivially unsolvable instances. Checks include:
   • Energy Reachability: Every customer must be within range $R$ of a depot or station.
   • Depot Return: Customers must be able to return to the depot within the time horizon.
   • Station Accessibility: Every customer must have at least one reachable charging station.
2. Stage 2: Exact MILP Verification: For small instances ($N \le 10$), an exact Mixed Integer Linear Programming (MILP) solver verifies the existence of a feasible route satisfying flow conservation, time windows, and energy dynamics. For $N > 10$, only Stage 1 is used to maintain computational efficiency.

C. Output and Reproducibility

• Generates instances with full metadata (JSON logs) recording parameters and feasibility status.
• Supports batch generation and includes an interactive GUI for real-time visualization.
• Uses fixed random seeds to ensure exact reproducibility.

3. Key Contributions

1. Parametric Generator: A tool that generates EVRPTW instances across a continuous spectrum of spatial, temporal, and energy regimes, moving beyond static datasets.
2. Feasibility Screening: A systematic approach to filter infeasible instances, providing a "ground truth" for learning-based models. This prevents models from learning to solve impossible problems.
3. Geometry-Aware Energy Scaling: Links energy constraints directly to spatial dispersion, preventing trivial feasibility or systematic infeasibility as instance size changes.
4. Benchmark Infrastructure: Positions the tool not as a solver, but as an infrastructure to evaluate the robustness and generalization of neural routing models under distribution shifts.

4. Experimental Results

The authors evaluated SynthCharge on instances ranging from 5 to 100 customers across various spatiotemporal regimes.

• Acceptance Rates ($\gamma$):
  • The generator successfully filtered out a significant portion of infeasible instances.
  • Clustered (C) regimes showed lower acceptance rates (approx. 37–39%) compared to Random (R) and Mixed (RC) regimes, particularly under tight time windows.
  • Tighter time windows generally reduced acceptance in clustered environments.
• Generation Efficiency:
  • Small Instances ($N \le 10$): Mean generation time is ~0.10s (due to expensive MILP verification).
  • Large Instances ($N > 10$): Time drops drastically to < 0.01s because only the linear Stage 1 screening is applied. This allows for high-volume data generation suitable for training deep learning models.
• Empirical Validation:
  • A baseline Variable Neighborhood Search (VNS) metaheuristic solved 100% of the generated instances (after screening), confirming that the structural screening effectively correlates with actual routing feasibility.
  • Experiments confirmed that tightening time windows and increasing spatial dispersion monotonically increase the required fleet size and total travel distance.

5. Significance and Future Work

Significance:
SynthCharge addresses a critical gap in the field of Neural Combinatorial Optimization (NCO). By providing a mechanism to systematically vary instance characteristics and verify feasibility, it enables researchers to:

• Test the omni-generalization capabilities of learning-based models.
• Move beyond "overfitting" to specific static datasets.
• Conduct reproducible comparisons of algorithms under controlled constraint regimes.

Limitations & Future Work:

• Scope: Currently limited to single-depot, Euclidean distances, and deterministic travel times.
• Charging Models: Assumes linear consumption and full recharges; does not yet model partial recharging or non-linear charging curves.
• Future Directions: The authors plan to extend the generator to multi-depot settings, time-dependent travel, stochastic dynamics, and integration with real-world road network geometries. They also aim to release standardized datasets and protocols to the community.