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.
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.
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