Planning the charging of an electric vehicle with a minimum run-time constraint

With the recent changes in energy production and energy consumption comes a need for change in the management strategy for the electricity grid. One of the changes in consumption is caused by the increase in the number of Electric Vehicles (EV's) in need of charging. The charging behaviour of EV's has been extensively studied in literature, and efficient algorithms to calculate optimal charging schemes have been developed. This thesis introduces a new constraint for a single-device EV charging model, namely the constraint of a minimum run-time. We present both a discrete model with a minimum run-time constraint, and two potential continuous charging models, of which one is selected. For the discrete problem we develop a dynamic programming algorithm, based on another algorithm found in existing literature. We then analyse the structure of the continuous problem, and a derived result is used to develop an exact algorithm for this problem as well. This algorithm is found to be rather inefficient in terms of speed and memory-usage. Therefore, we proceed to use the same structure of the problem to design a local search approximation method. We utilize several properties of the specific problem we consider here to improve the efficiency of the local search algorithm. This results in a fast polynomial-time algorithm for the continuous problem.