Optimizing Electric Vehicle Scheduling with Charging Guarantees using Flow Models with Local Penalties

The rapid growth of electric vehicle fleets in combination with the limited capacities of power grids necessitates coordinated charging strategies. To that end, charging schedules are developed that optimize the overall power drawn from the grid while ensuring that all vehicles receive sufficient energy and technically imposed power limits are respected. Although efficient methods for creating charging schedules have been developed, these solutions do not account for transparency and uncertainty. Specifically, they result in charging schedules that may delay the charging of some vehicles , causing low trust from customers and leading to problems if a vehicle has to depart unexpectedly early. We tackle this problem by developing charging schedules with charging guarantees. For this, we introduce checkpoints at which a certain part of the overall energy demand of the vehicle has to be charged. This increases both trust from the customers and robustness against uncertainty in the departure time. Our solution (called Fulpes) produces a provably optimal solution and is based on modelling the problem as a network flow with local penalties. A real-world use case with about 250 chargers demonstrates the applicability of our approach.