Vehicle-to-Vehicle Charging: Model, Complexity, and Heuristics

Cláudio Gomes, João Paulo Fernandes, Gabriel Falcão, Soummya Kar, Sridhar Tayur

TL;DR

This paper introduces a formal optimization framework for Vehicle-to-Vehicle Charging (V2VC), a technology that allows electric vehicles (EVs) to share power directly. The authors prove that optimizing these charging interactions is a computational nightmare (NP-Complete) but propose a clever heuristic, R-V2VC, that simplifies the problem into a solvable format, achieving near-optimal results with sublinear growth in computation time.

What Problem Does This Paper Address?

As EVs become mainstream, the strain on the electricity grid grows. While we usually think of charging as a "Grid-to-Vehicle" (G2VC) process, new models like the Ford F-150 Lightning and Tesla Cybertruck support bidirectional charging.

The challenge is coordination. Imagine a fleet of delivery EVs: some are running low on battery, while others have a surplus. Instead of every low-battery vehicle taking a time-consuming detour to a fixed charging station, they could meet a "helper" vehicle along their route. However, figuring out who should meet whom, where, and when—while still ensuring everyone reaches their destination on time—is an incredibly complex routing and scheduling problem that hasn't been formally modeled in the context of fleet optimization until now.

Methods

The researchers tackled the problem in three stages:

  1. The Full Model: They developed a nonlinear objective integer constrained model. It uses a Time-Space Network Graph, which maps out not just where vehicles are, but where they are at specific points in time. This allows the model to account for movement, energy consumption during travel, and discrete energy transfers during meetings.
  2. Complexity Proof: They formally proved that the V2VC optimization problem is NP-Complete by reducing it from the 3SAT problem (a classic hard problem in logic). This means that as the number of vehicles and locations grows, the time needed to find an exact solution explodes exponentially.
  3. The R-V2VC Heuristic: To make the model practical, they introduced "Restricted-V2VC." By adding a constraint that each EV can perform at most one V2VC action (either giving or receiving a charge) during its journey, they were able to represent the problem as a bipartite graph. This specific structure results in a "totally unimodular" constraint matrix, which is a mathematical "cheat code" that allows complex integer problems to be solved efficiently in polynomial time.

Datasets

The authors did not use a pre-existing real-world dataset. Instead, they created two sets of synthetic benchmarks to evaluate their models:

  • Scenarios B1–B11: Increasingly large problems (up to 120 EVs and 160 nodes) used to test how the solution time scales.
  • Scenarios Q1–Q6: Smaller, controlled problems used to compare the quality of the heuristic's solution against the absolute mathematical optimum.

Key Insights and Ideas

  • V2VC as a Routing Constraint: The paper treats energy not just as a fuel, but as a transferable resource that changes the topology of the routing problem. A vehicle that would have been "stranded" in a traditional model becomes "viable" if a meeting can be scheduled.
  • The Power of Restriction: The most significant "aha moment" is that by limiting vehicles to a single charging interaction, the problem's complexity collapses from NP-Complete to P (polynomial time). This trade-off—sacrificing a bit of flexibility for massive gains in speed—is what makes the system viable for real-time fleet management.
  • Grid Relief: The model demonstrates that V2VC can act as a buffer for the grid, effectively moving energy around the network via the vehicles themselves rather than relying solely on fixed infrastructure.

Key Results

  • Scalability: The original exact model "exploded" in complexity. For a scenario with 120 EVs, the original model required over 2.5 billion variables, causing standard solvers (like Gurobi) to crash due to memory limits. In contrast, the R-V2VC heuristic handled the same problem with only 2,234 variables.
  • Speed: R-V2VC showed sublinear growth in solution time. Even as problem sizes increased, the time to find a solution remained in the millisecond range.
  • Optimality: In the smaller test cases where an exact solution was possible, R-V2VC consistently found the optimal or near-optimal solution, proving that the "one-action" restriction doesn't significantly hurt performance in typical scenarios.

Limitations and Future Work

The primary limitation is the core assumption of the heuristic: one V2VC action per vehicle. In extreme scenarios—such as a very long-haul route through a "charging desert"—a vehicle might realistically need to be charged by multiple peers to reach its destination. The current heuristic would mark such a route as "infeasible."

The authors suggest two main paths for future research:

  1. Rolling Time Horizons: Adapting the model so vehicles can enter and leave the system dynamically (real-time dispatching).
  2. k-indexed Heuristics: Expanding the heuristic to allow for k charging actions (e.g., allowing up to 2 or 3 charges), which would bridge the gap between the current fast heuristic and the slow, full model.

Summary updated

BibTeX
@inproceedings{gomes2024vehicle,
  author = {Cláudio Gomes and João Paulo Fernandes and Gabriel Falcão and Soummya Kar and Sridhar Tayur},
  title = {{Vehicle-to-Vehicle Charging: Model, Complexity, and Heuristics}},
  booktitle = {Smartgridcomm},
  year = {2024},
  doi = {10.1109/smartgridcomm60555.2024.10738086},
}
Figure