Electric vehicles recharge scheduling with time windows

Abstract

Die Ladeoptimierung Elektroautos wird in der nahen Zukunft ein immer wichtigeres Problem, wegen der hohen Energiemengen die in kürzester Zeit über das Stromnetz fliessen müssen. Ohne die Flexibilität bei der Aufladung zu nutzen besteht die Gefahr die vorhandene Netzinfrastruktur zu bestimmten Tageszeiten (Spitzenlast) zu überlasten. Das in dieser Arbeit behandelte Ladeoptimierungsproblem ist ein Teil des Systems, das innerhalb des KOFLA-Projektes entwickelt und von FFG2 finanziert wurde. Ziel des Projekts ist die Benutzer von Elektrofahrzeugen zu unterstützen, die besten öffentlichen Ladestationen zu finden (in der Nähe, günstig und schnell). Das Optimierungsproblem, das in dieser Arbeit als Electric Vehicles Recharge Scheduling with Time Windows (EVRSTW) bezeichnet wird, ist eng mit den Problemen der Ablaufobtimierung (scheduling) mit Ressourcen-Restriktionen verbunden. EVRSTW gehört der Klasse von NP-kompletten Problemen, was bedeutet, dass die exakten Methoden nicht in der Lage sind große Probleminstanzen in vernünftiger Zeit zu lösen. In einer realen Umgebung, in der der Benutzer sofort wissen muß, ob seine Ladeanforderung akzeptiert wird, sollten Algorithmen mit begrenzter Laufzeit eine (auch suboptimale) Lösung liefern können. Diese Diplomarbeit untersucht die möglichen heuristischen Ansätze für das EVRSTW-Problem. Zuerst definieren wir die greedy Heuristik, welche eine sofortige Aufladung nach plug-in bewirkt. Da diese Heuristik schlechte Ergebnisse nachweist widmen wir uns der local ratio Technik, welche der Natur unseres Problems angepasst wird. Da diese Methode immer noch viele Ladeanforderungen ablehnt, suchen wir nach weiteren Heuristiken. Basierend auf der lokalen Suche, wählen wir schließlich die min-conflicts Heuristik (MCH) und definieren eine passende Nachbarschaftsrelation zwischen Lösungen. Wir vergleichen die drei heuristischen Methoden nach den vielfältigen Kriterien der Evaluierung, wie z. B. nach dem gesamten Profit, der Laufzeit und Anzahl der abgelehnten Aktivitäten. Die Experimente werden mit einem Satz von generischen Probleminstanzen geführt. Diese zeigen, dass nur die MCH Methode es schafft, zulässige Lösungen zu generieren, indem sie die sämtlichen Aktivitäten erfolgreich einplant. Wir analysieren ihre Performanz und Qualität der Lösungen sowohl in dem offline Modus, wenn alle Aktivitäten auf einmal bekannt werden, und in online Modus, wenn die Aktivitäten als Ereignisse einzeln eintreffen und der Ablaufplan in der Zeit gerollt und permanent aktualisiert wird. Im Vergleich mit der exakten Methode (CPLEX Solver) zeigen wir, dass die Laufzeiten der MCH Methode bedeutsam kurzer sind - weniger als 200 Millisekunden gegen 25+ Minuten im Extremfall, und das bei einer akzeptabler Lösungsqualität von 75% bis 93% vom Optimum. Dadurch ist die MCH Methode ein guter Kandidat für die Anwendung in Onlinemodus, und kann im Ladestation-Controller eingebaut werden. Schließlich untersuchen wir den Einfluss von Fehlern bei der Abschätzung der Parkdauer und zeigen dass diese die Lösungsqualität ziemlich verschlechtern.

The problem of scheduling the recharge operations of electric vehicles (EVs) is one we will inevitably face in the near future. An important aspect to consider is the impact that increasing number of EVs, with their frequent need for recharge, would have on the current electric grid infrastructure and how we can avoid overloading the grid at certain periods of the day. The EV recharge scheduling task is a part of the system developed within the FFG-funded KOFLA project, which has the goal of helping EV users to find the best opportunity for recharging (nearby, cheap and fast). The optimization problem identified in this work as Electric Vehicles Recharge Scheduling with Time Windows (EVRSTW) is closely related to the resource allocation and resource-constrained scheduling problems. EVRSTW, in its special case, belongs to the class of NP-complete problems, meaning that exact methods are usually unable to cope with large problem instances in reasonable time, and display unpredictable runtimes. In order to build a real world dynamic system based on user requests and almost immediate system responses, we need to find methods which can operate within a short, bounded execution time. This thesis investigates possible heuristic approaches to solving the EVRSTW problem. We first model a greedy heuristic, to simulate a "dumb", plugin-and-charge-immediately, approach. Since it performs poorly, we turn to the local ratio technique, tailored to our problem specification. This method still rejects some of the activities (EV recharge requests) which need to be scheduled, so we search for a new approach. Finally, we design a local search method based on the min-conflicts heuristic, along with defining an appropriate neighborhood relation. We evaluate the three heuristic methods on a set of generic problem instances, according to multiple evaluation criteria, such as total profit, runtime, and number of unscheduled activities. The experiments show that only the MCH manages to generate feasible solutions, i.e. to schedule all of the activities. We analyze its performance on two different EV models and in two running modes of the system: a) offline, where all activities are presented at once and the schedule is built "from scratch"; and b) online, where activities arrive one by one and the schedule is built incrementally. Comparing the min-conflicts heuristic against the exact method (CPLEX solver), we find that its runtimes are significantly shorter - in terms of less than 200 milliseconds versus 25+ minutes in the extreme case, with an acceptable solution quality of 75% to 93% of the optima. This makes the MCH a good candidate for application in the online environment, which we turn into reality by incorporating it within a charging station controller. We evaluate its performance in this new setting and show that the parking period prediction error has a significant impact on the solution quality.