Electric vehicles recharge scheduling with logic-based Benders decomposition

Abstract

Elektrofahrzeuge stellen eine vielversprechende Alternative zu herkömmlichen Fahrzeugen mit Verbrennungsmotor dar und könnten dabei helfen, die gesetzten Klimaschutz- und Energieziele zu erreichen. Der großflächige Umstieg wird jedoch dadurch erschwert, dass sie häufig aufgeladen werden müssen und das Laden relativ lange dauert. Außerdem gibt es noch immer wenige Ladestationen, und auch die begrenzten Netzkapazitäten müssen berücksichtigt werden. Wir betrachten das Problem, einen optimalen Plan für das Aufladen einer Flotte von Elektrofahrzeugen bei mehreren Elektrotankstellen mit begrenzten Ressourcen zu finden. Das Ziel ist, so viele Fahrzeuge wie möglich aufzuladen. Jedes Fahrzeug, das einer Tankstelle zugewiesen wird, benötigt während seines gesamten Aufenthalts einen Parkplatz und soll vor seiner Abfahrt so weit wie möglich aufgeladen werden, wobei ein minimaler Energiebedarf erfüllt werden muss. Die Tankstellen haben nur eine begrenzte Anzahl an Parkplätzen und Ladestationen zur Verfügung, und auch die verfügbare Energie ist beschränkt. Die Ladestationen können mit verschiedenen Raten betrieben werden. Höhere Raten sollten jedoch vermieden werden, da sie die Lebensdauer der Batterien stärker beeinträchtigen. Als Erstes formulieren wir dieses Problem als ein gemischt-ganzzahliges lineares Optimierungsproblem (engl. mixed-integer programming, MIP), was eine Standardmethode für diskrete Optimierungsprobleme darstellt. Des Weiteren wird ein einfacher Greedy-Algorithmus präsentiert, der sehr schnell eine gültige heuristische Lösung findet. Das Kernziel dieser Diplomarbeit ist, eine alternative Lösungsmethode für das Problem zu untersuchen. Die so genannte logikbasierte Benders-Dekomposition löst Optimierungsprobleme iterativ auf Grundlage von systematischem Versuch und Irrtum. Dazu wird das Problem in ein Master- und ein Subproblem zerlegt. Im Masterproblem werden in jeder Iteration einigen der Variablen Versuchswerte zugewiesen. Im Bezug auf diese Zuordnung werden dann im Subproblem optimale Werte für die restlichen Variablen bestimmt. Dieses sollte deutlich einfacher zu lösen sein als das ursprüngliche Problem. Aus der Lösung des Subproblems werden Bedingungen abgeleitet, die in das Masterproblem eingefügt werden, um in der nächsten Iteration bessere Versuchswerte zu bestimmen. Wir formulieren logikbasierte Benders-Algorithmen für zwei verschiedene Dekompositionen des betrachteten Problems. In den Subproblemen der ersten Zerlegung muss nur eine gültige Lösung gefunden werden, während es sich bei der zweiten Dekomposition auch hier um ein Optimierungsproblem handelt. Zusätzlich werden heuristische Beschleunigungsstrategien für die Benders-Algorithmen vorgestellt, bei denen entweder die Master- oder Subprobleme heuristisch gelöst werden. Die Evaluierung der Algorithmen auf zufallsgenerierten Testinstanzen zeigt, dass das MIP-Modell und die erste Zerlegung recht gut funktionieren. Auf Instanzen mit gleichartigen Tankstellen und ausreichend verfügbaren Ressourcen terminiert der Benders-Algorithmus oft schon nach wenigen Iterationen und erzielt deutlich bessere Ergebnisse als das kompakte MIP-Modell. Andererseits hat das MIP-Modell auf Instanzen mit anderen Spezifikationen häufig eine kürzere Laufzeit. Die zweite Dekomposition weist ein relativ schlechtes Verhalten auf. In vielen Fällen findet der Algorithmus keine optimale Lösung innerhalb der vorgegebenen Zeit. Die heuristischen Beschleunigungsversuche führen auf manchen Instanzen zu verbesserten Laufzeiten, bringen für die meisten aber keinen wirklichen Vorteil. Auf den größeren Instanzen kann das MIP-Modell wegen des hohen Speicherbedarfs gar nicht gelöst werden, während man durch die logikbasierten Benders-Algorithmen zumindest Schranken für den optimalen Wert erhält. Der erste Benders-Algorithmus findet sogar für viele der größeren Instanzen eine optimale Lösung.

Electric vehicles represent a promising alternative to traditional internal combustion engine vehicles that might support the attainment of settled climate and energy targets. The widespread adoption of electric vehicles is complicated, however, by their need for frequent recharging and the rather long charging duration. Moreover, charging facilities are still relatively scarce and power constraints imposed by the electric grid have to be respected. We consider the problem of scheduling the recharging of a fleet of electric vehicles at multiple facilities with limited resources. The goal is to recharge as many vehicles as possible. Every vehicle that is scheduled for charging needs a parking spot during the entire time of its stay and shall be recharged as much as possible before departure. Facilities only have a limited number of parking spots and charging machines and a limited amount of power available for charging. Machines can work at several charging rates, but higher ones should be avoided, since they reduce battery lifetime more. First, we formulate this problem as a mixed-integer programming (MIP) model, which is a standard approach for discrete optimization problems. Moreover, a simple greedy heuristic, which quickly finds a feasible solution, is presented. The main objective of this thesis is to investigate an alternative method for solving the problem. The so-called logic-based Benders decomposition solves optimization problems iteratively on basis of systematic trial and error. For this purpose, the problem is decomposed into a master and a subproblem. In every iteration, the master problem assigns trial values to some of the variables. Assuming those fixed, optimal values of the remaining variables are determined in the subproblem, which should be much easier to solve than the original one. From the subproblem solution we deduce constraints that are added to the master problem, in order to obtain better trial values in the next iteration. Logic-based Benders algorithms for two different decompositions of the considered problem are formulated. The subproblems of the first one are mere feasibility problems, while in the second one they are optimization problems as well. Additionally, heuristic boosting strategies are proposed, in which either the master or subproblems are solved heuristically. The evaluation of all algorithms on randomly generated test instances shows that the MIP model and the first decomposition work quite well. On instances with homogeneous facilities and enough resources available, the first Benders algorithm often terminates after a few iterations and achieves far better results than the compact MIP model. On the other hand, the MIP model frequently has a shorter runtime on instances with other specifications. The second decomposition shows a rather bad performance. In many cases, the algorithm does not find an optimal solution within the time limit. Heuristic boosting leads to an improved runtime on some instances, but for most offers no real advantage. Regarding larger instances, the MIP model cannot be solved at all due to high memory requirements, while the logic-based Benders algorithms at least return bounds on the optimal value. The first Benders algorithm even finds an optimal solution on many of the larger instances.