Hard optimisation problems for smart-charging of electric vehicles

Electric mobility stands out as a fast-growing sector in Europe which could contribute to the resolution of some major environmental and public health problems, thanks to the reductions in fine particle and greenhouse gas emissions it achieve.


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.

Watch the presentation of this use case at Teratec Forum

(in French)
Our website uses cookies to give you the most optimal experience online by: measuring our audience, understanding how our webpages are viewed and improving consequently the way our website works, providing you with relevant and personalized marketing content. You have full control over what you want to activate. You can accept the cookies by clicking on the “Accept all cookies” button or customize your choices by selecting the cookies you want to activate. You can also decline all cookies by clicking on the “Decline all cookies” button. Please find more information on our use of cookies and how to withdraw at any time your consent on our privacy policy.
Accept all cookies
Decline all cookies
Privacy Policy