Smart-charging appears to be a mandatory condition to allow electric mobility expansion. The high level of power required to load electrical vehicles, especially on fast load stations, require optimal modulation of this load demand in time. Further, the use of vehicle batteries as energy storage devices and power sources (“Vehicle to Grid” or “V2G”) could significantly improve the flexibility of the electrical system, reduce high-peak of electricity demand and thus generate significant energy savings, while offering customers with various services providing earning money and saving costs opportunities.
Smart-charging requires high-level skills and technologies to optimally manage the electrical system in terms of cost, while satisfying many technical constraints: needs of electric vehicle users, charging/discharging cycles of batteries, limits on available power delivered by the grid, reserves required to guaranty frequency stability, etc. Many of these challenges, take the form of typical Scheduling and Operational Research problems, and, mathematically, of large sized, stochastic, combinatorial optimization problems, many of them known to be NP-hard or NP-complete: travelling salesman, bin-packing, job-shop scheduling, SAT, knapsack, search for maximal cuts or independent sets in graphs etc., or generally as Linear (Mixed) Integer Programs. Consequently, no tractable (polynomial) algorithms are known to solve large instances of these problems exactly and efficiently on conventional computers.
Our main objective is therefore to investigate the pertinence of quantum computing on real instances of smart-charging optimization problems.