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

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

Abstract

As electric vehicle (EV) adoption accelerates, the demand on fixed charging infrastructure increases. Vehicle-to-Vehicle Charging (V2VC) offers a decentralized alternative where EVs share energy directly. This paper formalizes the V2VC optimization problem, proves its NP-completeness, and introduces the Restricted-V2VC (R-V2VC) heuristic. By limiting each vehicle to a single charging interaction, R-V2VC reduces the problem complexity from billions of variables to thousands, enabling near-optimal fleet coordination in real-time.

Introduction

Traditional charging models rely on Grid-to-Vehicle (G2VC) processes. However, modern EVs with bidirectional charging capabilities allow for a more flexible V2VC paradigm. The core challenge lies in coordination: determining the optimal meeting points and times for energy transfer within a fleet while ensuring all vehicles meet their delivery or travel schedules. This represents a complex routing and scheduling problem that has lacked a formal optimization framework until now.

Methods

The research presents a three-tiered approach to solving the V2VC coordination problem.

The Time-Space Network Model

The foundation is a nonlinear objective integer constrained model based on a Time-Space Network Graph. This graph maps vehicle locations across discrete time intervals, accounting for movement, energy consumption, and transfers.

Time-space network graph showing EV paths and V2VC meeting points.

Complexity and the R-V2VC Heuristic

The authors formally prove that the general V2VC optimization problem is NP-Complete via a reduction from the 3SAT problem. To overcome the resulting exponential growth in computation time, they propose the Restricted-V2VC (R-V2VC) heuristic. By constraining each EV to at most one V2VC action (giving or receiving), the problem is transformed into a bipartite graph structure. This structure allows the use of totally unimodular constraint matrices, enabling efficient polynomial-time solutions.

Experimental Evaluation

The models were evaluated using synthetic benchmarks:

  • Scalability Benchmarks (B1–B11): Problems with up to 120 EVs and 160 nodes to test computational limits.
  • Quality Benchmarks (Q1–Q6): Smaller scenarios to compare heuristic performance against exact mathematical optima.

Key Results and Insights

The study reveals that V2VC can significantly alter routing topology by making previously "stranded" routes viable through peer-to-peer energy transfers.

Scalability and Efficiency

The most dramatic result is the reduction in problem size. In a scenario with 120 EVs, the original exact model required over 2.5 billion variables, exceeding the memory capacity of standard solvers. The R-V2VC heuristic reduced this to just 2,234 variables, maintaining sublinear growth in solution time.

Comparison of variable counts between the original model and the R-V2VC heuristic.

Optimality

Despite the "one-action" restriction, R-V2VC consistently found optimal or near-optimal solutions in smaller test cases. This suggests that the trade-off between flexibility and computational speed is highly favorable for real-world fleet management.

Conclusion

While the current R-V2VC heuristic is limited to one charging action per vehicle—potentially failing in extreme "charging deserts"—it provides a robust foundation for real-time coordination. Future work will explore rolling time horizons for dynamic dispatching and k-indexed heuristics to allow for multiple charging interactions per journey.

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