Scheduling the charging of electric vehicles with SOC-dependent maximum charging power

Abstract

In dieser Arbeit betrachten wir die Aufgabe der Erstellung eines Ladeplans für eine Fahrzeugflotte aus der Perspektive einer Elektroladestation. Der Ladeplan soll, unter der Annahme von zeitabhängigen Strompreisen, die gesamten Ladekosten minimieren. Dabei soll auch die zeitliche Verfügbarkeit jedes Fahrzeugs, der Ladestand jedes Fahrzeugsund die maximale Ladeleistung der Ladestation berücksichtigt werden. Ein besonderer Schwerpunkt liegt dabei auf der maximalen Ladeleistung eines Fahrzeugs, die durch eineladestandsabhängige Funktion limitiert wird. Dieser Aspekt des Problems ist besonders für das Schnellladen von Fahrzeugen relevant. Da die präsentierten Modelle auf einem diskretisierten Zeithorizont basieren, ist es möglich, dass die vorgeschriebene maximale Ladeleistung eines Fahrzeugs zu Beginn eines Zeitschritts nicht während des gesamten Zeitschritts gehalten werden kann. Wir werdenuns dieser Problematik widmen, indem wir die exakte maximale Energie berechnen, die innerhalb eines Zeitschritts geladen werden kann. Außerdem werden wir auch untere und obere Schranken für diese maximale Energie herleiten. Wir werden verschiedene (gemischt-ganzzahlig) lineare Programme einführen, um das Scheduling-Problem zu lösen. Für eine der Formulierungen zeigen wir, wie man mit Hilfe eines Schnittebenenverfahrens herausragende Laufzeiten erreichen kann. Weiters sehen wir uns den Fall an, bei dem die Ladeleistungsfunktion nicht konkav ist und führen eine Formulierung ein, die stückweise lineare, nicht-konkave Ladeleistungskurven annimmt. Wir verbessern die Laufzeit dieser Formulierung auf einigen Instanzen, indem wir einen Branch-and-Cut-Ansatz anwenden. Außerdem sehen wir uns zwei gemischt-ganzzahlig lineare Formulierungen an, die das Laden ausschließlich in diskreten Energiewerten erlauben. Anhand selbst erstellter Probleminstanzen werden alle vorgestellten Ansätze experimentell untersucht. Zusätzlich führen wir Experimente in einem model based predictive control scenario durch, das üblicherweise in der Praxis zum Einsatz kommt. Es stellt sich heraus, dass das Problem effizient durch lineare Programmierung gelöst werden kann, wenn die Ladeleistungsfunktion der Fahrzeuge konkav und stückweise linear ist. Die Situation ist wesentlich schwieriger für allgemeine stückweise lineare Funktionen. Hier werden deutlich höhere Laufzeiten erwartet, um einen optimalen Ladeplan zu erstellen, da ganzzahlige Variablen in den entsprechenden Modellen notwendig sind. Durch die Approximation der tatsächlichen Ladeleistungsfunktion mit einer konkaven Funktion können wir die besseren Laufzeiten des speziellen linearen Programms ausnutzen. Jedoch können dabei Ladepläne erstellt werden, die in der Praxis nicht durchführbar sind, da Fahrzeuge ihren gewünschten Zielladestand nicht erreichen. Wir werden diesen Fehler quantifizieren und feststellen, dass dieser in der Praxis vernachlässigbar ist. Schlussendlich werden wir den Leser bei der Auswahl des passenden Problemlösungsmodells unterstützen und Ratschläge für die Wahl von Problemlösungsparametern geben.

We consider the task of finding a charging schedule for a vehicle fleet from the perspective of an electric vehicle charging station. The schedule must minimize the overall charging costs under time-dependent electricity costs while respecting each vehicle's temporal availability, its state of charge, as well as the charging station's maximum charging power. A special focus is put on the aspect that each vehicle's maximum charging power is limited by a function that depends on the vehicle's state of charge, which is particularly important for fast-charging. Since our presented models are based on a discretized time horizon, a vehicle's maximum charging power may decrease within a single time step. We will show how to deal with this issue by providing an exact derivation for the maximum charging energy of a single time step, as well as lower and upper bounds. We introduce different (mixed-integer) linear programming formulations to solve the scheduling problem. For one of the formulations we show how to achieve outstanding runtime performance with a cutting plane technique. Also, we consider the case that the maximum charging power function is non-concave by proposing a formulation that can handle piecewise linear, non-concave charging power functions. We enhance its runtime on some instances by applying a branch-and-cut technique. Furthermore two formulations that allow charging in discrete energy units only are considered and their respective linear programming relaxations are compared. All introduced techniques are experimentally evaluated on benchmark instances, which are partly based on real-world data. We conduct experiments for a model based predictive control scenario, which is typically deployed in practice. It turns out that the problem can be efficiently solved by means of linear programming in case the vehicles' maximum charging power functions are concave and piecewise linear. The situation is remarkably more difficult for general piecewise linear functions where one can expect much higher runtimes for finding an optimal charging schedule, as integral variables are needed in the respective models. By approximation of the maximum charging power with a concave function, we can utilize the performance benefits of a specialized linear programming formulation. By doing so, the charging schedule may be practically infeasible, since vehicles might not reach their specified target state of charge. We will quantify this error and see that it is negligible in practice. Finally, we will guide the reader on the selection of an appropriate model and give advice how to choose certain problem solving parameters.