• Energy Research

This work considers the problem of planning how a fleet of shared electric vehicles is charged and used for serving a set of reservations. While exact approaches can be used to efficiently solve small to medium-sized instances of this problem, heuristic approaches have been demonstrated to be superior in larger instances. The present work proposes a large neighborhood search approach for solving this problem, which employs a mixed integer linear programming-based repair operator. Three variants of the approach using different destroy operators are evaluated on large instances of the problem. The experimental results show that the proposed approach significantly outperforms earlier state-of-the-art methods on this benchmark set by obtaining solutions with up to 8.5% better objective values.

The aim of this work is to schedule the charging of electric vehicles (EVs) at a single charging station such that the temporal availability of each EV as well as the maximum available power at the station are considered. The total costs for charging the vehicles should be minimized w.r.t. time-dependent electricity costs. A particular challenge investigated in this work is that the maximum power at which a vehicle can be charged is dependent on the current state of charge (SOC) of the vehicle. Such a consideration is particularly relevant in the case of fast charging. Considering this aspect for a discretized time horizon is not trivial, as the maximum charging power of an EV may also change in between time steps. To deal with this issue, we instead consider the energy by which an EV can be charged within a time step. For this purpose, we show how to derive the maximum charging energy in an exact as well as an approximate way. Moreover, we propose two methods for solving the scheduling problem. The first is a cutting plane method utilizing a convex hull of the, in general, nonconcave SOC–power curves. The second method is based on a piecewise linearization of the SOC–energy curve and is effectively solved by branch-and-cut. The proposed approaches are evaluated on benchmark instances, which are partly based on real-world data. To deal with EVs arriving at different times as well as charging costs changing over time, a model-based predictive control strategy is usually applied in such cases. Hence, we also experimentally evaluate the performance of our approaches for such a strategy. The results show that optimally solving problems with general piecewise linear maximum power functions requires high computation times. However, problems with concave, piecewise linear maximum charging power functions can efficiently be dealt with by means of linear programming. Approximating an EV’s maximum charging power with a concave function may result in practically infeasible solutions, due to vehicles potentially not reaching their specified target SOC. However, our results show that this error is negligible in practice.