Artificial intelligence methods for the management of electric vehicles in the smart grid

Abstract

The electrification of transport, via the extensive use of Electric Vehicles (EVs) is seen as one of the main pathways to achieve significant reductions in CO2 emissions. To control the activities of EVs will demand algorithms that can solve problems that involve many heterogeneous entities, each one having its own goals, needs and incentives, while they will operate in highly dynamic environments and having to deal with several uncertainties. Artificial intelligence techniques have been proven efficient in solving such problems. In the first part of this thesis, we provide a survey of the literature to identify the main research problems and describe the commonalities and key differences in the approaches. Later, we study the problem of allocating EVs to charging stations and scheduling their charging. In doing so, we develop three different approaches: 1) We develop offline and online solutions that treat EV users as self-interested agents that aim to maximize their profit and minimize the impact on their schedule. We formulate the problem of the optimal EV to charging station allocation as a Mixed Integer Programming (MIP) one and we propose two pricing mechanisms. 2) We apply dynamic pricing techniques to balance EV demand across a set of charging stations. 3) We apply agent-based negotiation techniques between the stations and EVs in order to service EVs when the MIP problem is initially unsolvable. Later, we study a setting where EVs can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of serviced customers, or the total EV utilization. We initially characterize the optimization problem as a max-flow problem. We then model and solve the EV-to-trip scheduling problem offline and optimally using MIP techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP and a greedy heuristic algorithm for larger problems. Moreover, we develop a tabu search-based local search technique to further improve the solution of the non-optimal algorithms. In addition, we study the problem of the efficient charging and dis-charging of EVs at a charging station level. Initially, we formulate the problem as a MIP one and we solve it optimally assuming full knowledge of EV demand and energy generation. Later, we propose an online algorithm that iteratively calls the offline one and copes with unknown future interruptions by arriving EVs and with the inability to predict accurately renewable energy production. Finally, we present a tool and a Java library for the efficient simulation of the charging of large numbers of EVs. In this vein, EVLibSim is a tool for the simulation of EV activities at a charging station level. EVLibSim unifies EVLib's primary functions such as the charging and dis-charging of batteries, battery swapping, as well as parking/inductive charging. EVLib is a Java library that provides a simple, yet efficient framework for the management of several EV activities, at a charging station level, within a smart grid.

Η εκτεταμένη χρήση ηλεκτρικών οχημάτων θεωρείται ως ένας βασικός τρόπος για την μείωση των εκπομπών διοξειδίου του άνθρακα. Ο έλεγχος της εκτεταμένης χρήσης των ηλεκτρικών οχημάτων απαιτεί αλγορίθμους που μπορούν να λύσουν προβλήματα που περιλαμβάνουν πολλές οντότητες που η κάθε μια έχει τους δικούς της στόχους, περιορισμούς και απαιτήσεις. Αυτοί οι αλγόριθμοι λειτουργούν σε ένα ιδιαίτερα δυναμικό περιβάλλον και συμβάλουν στη διαχείριση της αβεβαιότητας. Διάφορες μέθοδοι τεχνητής νοημοσύνης έχουν αποδειχθεί αποτελεσματικές στην επίλυση τέτοιων προβλημάτων. Στο πρώτο κομμάτι αυτής της διατριβής, παρουσιάζουμε την βιβλιογραφική ανασκόπηση, μέσω της οποίας εντοπίστηκαν τα βασικά ερευνητικά προβλήματα καθώς και οι ομοιότητες και διαφορές στις προτεινόμενες λύσεις. Στην συνέχεια μελετούμε το πρόβλημα της ανάθεσης οχημάτων σε σταθμούς φόρτισης και του χρονοπρογραμματισμού της φόρτισης αυτών. Σ ’αυτά τα πλαίσια εξετάστηκαν τρεις προσεγγίσεις: 1) Το πρόβλημα μοντελοποιείται ως πρόβλημα μικτού γραμμικού προγραμματισμού και προτείνονται δύο μηχανισμοί τιμολόγησης: Ο πρώτος είναι σταθερής τιμής, ενώ ο δεύτερος βασίζεται στον γνωστό μηχανισμό Vickrey-Clark-Groves. 2) Χρησιμοποιούμε τεχνικές δυναμικής τιμολόγησης με σκοπό την ισοκατανομή των οχημάτων στο σύνολο των σταθμών φόρτισης. 3) Χρησιμοποιούμε τεχνικές διαπραγμάτευσης μεταξύ πρακτόρων στην περίπτωση που κάποιο όχημα δεν μπορεί να εξυπηρετηθεί σύμφωνα με τις αρχικές του προτιμήσεις. Έπειτα, μελετούμε το πρόβλημα του προγραμματισμού της κίνησης και φόρτισης ηλεκτρικών οχημάτων σε ένα σύστημα κοινόχρηστων οχημάτων. Στόχος του συστήματος είναι, είτε η μεγιστοποίηση του αριθμού των χρηστών που εξυπηρετούνται, ή η μεγιστοποίηση του συνολικού χρόνου χρήσης των οχημάτων. Για να επιτευχθεί αυτό, αρχικά μοντελοποιούμε το πρόβλημα ως πρόβλημα μέγιστης ροής. Στην συνέχεια επιλύουμε το πρόβλημα του χρονοπρογραμματισμού της εκτέλεσης των ταξιδιών και της ανάθεσης οχημάτων σε κάθε ένα. Αρχικά το λύνουμε βέλτιστα με μικτό γραμμικό προγραμματισμό και παρατηρούμε ότι η λύση είναι χρηστική για μικρά ή μεσαία προβλήματα. Με αυτό το δεδομένο αναπτύσσουμε και άλλους μη βέλτιστους αλγορίθμους και πιο συγκεκριμένα έναν που καλεί σταδιακά τον βέλτιστο για κάθε όχημα για μεσαία ως μεγάλα προβλήματα και έναν άπληστο ευρετικό για πολύ μεγάλα προβλήματα. Επιπρόσθετα, αναπτύσσουμε έναν tabu-search αλγόριθμο τοπικής αναζήτησης ο οποίος βελτιώνει την απόδοση των μη βέλτιστων αλγορίθμων. Οι αλγόριθμοι μελετώνται σε σενάρια που περιλαμβάνουν είτε αλλαγή μπαταρίας, ή τυπική φόρτιση της μπαταρίας. Στη συνέχεια μελετούμε το πρόβλημα του χρονοπρογραμματισμού της αποφόρτισης ηλεκτρικών οχημάτων σε ένα σύστημα μεταφοράς ενέργειας από το όχημα στο δίκτυο, αλλά και από όχημα σε όχημα. Θεωρείται ότι ο σταθμός φόρτισης/αποφόρτισης διαθέτει ενέργεια από ανανεώσιμες πηγές και λύνεται το πρόβλημα τόσο στατικά, όσο και δυναμικά επιδιώκοντας να μεγιστοποιηθεί η χρησιμοποίηση της διαθέσιμης ενέργειας από ανανεώσιμες πηγές και να ελαχιστοποιηθεί το κόστος για τα οχήματα. Επιπροσθέτως, παρουσιάζουμε και έναν δυναμικό αλγόριθμο ο οποίος καλεί σταδιακά τον βέλτιστο, όπου σε αυτήν την περίπτωση θεωρείται ότι υπάρχει αβεβαιότητα σχετικά με την μελλοντική ζήτηση από την πλευρά των οχημάτων, αλλά και την παραγωγή ενέργειας από ανανεώσιμες πηγές. Τέλος, παρουσιάζουμε μια βιβλιοθήκη σε Java η οποία ονομάζεται EVLib και υποστηρίζει πολλές από τις λειτουργίες των οχημάτων σε επίπεδο σταθμού φόρτισης. Επιπλέον, υλοποιούμε ένα εργαλείο προσομοίωσης το οποίο ονομάζεται EVLibSim, βασίζεται στην EVLib και προσφέρει ένα γραφικό περιβάλλον για την μοντελοποίηση και προσομοίωση λειτουργιών των οχημάτων σε επίπεδο σταθμού φόρτισης.