Formulation and solution methods for locating charging stations and routing of electric vehicles

Abstract

The ”electrification” of transport is one of the key features of the future of transport. As legislation becomes more and more stringent in terms of greenhouse gas emissions, the pressure to introduce ’green’ technologies in the transport sector is increasing. Electric vehicles are one of the most direct ways of achieving this. The introduction of electric vehicles requires a special effort, as they are called upon to face a transport system based exclusively on fossil fuels, with the possibility of refuelling in every corner of the planet and at high speed. Many companies have introduced or are about to introduce electric vehicles into their vehicle fleet and in order to manage them better, new algorithms must be developed that take into account the visits to charging stations, the effect of the vehicle load, the distance that the electric vehicles can travel, the charging rate of the batteries for correct completion of the vehicle routes and all the problems that arise based on the above. Consequently, the Electric Vehicle Routing Problem is an important new problem, crucial for the success of the integration of electric vehicles in the supply chain. The new problems presented by electric vehicles stem from the use of batteries and electric motors, as opposed to a conventional diesel vehicle. At the current level of development of energy storage technology, it is not possible to achieve the energy density of fossil fuels. As a result, the required charging frequency increases. This parameter alone would probably not be a problem for a conventional vehicle, but for an electric vehicle it is very important, as the charging time is much longer than the refuelling time of a conventional vehicle. This adds to the cost, given the driver’s waiting time to charge the vehicle. An additional level of difficulty is introduced by the fact that charging stations are required for electric vehicles. Such charging stations for electric vehicles are not as frequently found as petrol stations. The installation of new charging stations will be a very important parameter for the successful use of electric vehicles since new charging stations will have to be set up. The placement of these stations is extremely important to reduce the cost of vehicle travel, as stations located off the vehicle’s route will contribute to the increase in costs. On the other hand, adding new charging stations without careful prior study will be a waste of resources, not only resources to set up the stations but also the resources that vehicles will waste in getting to these stations. One option to consider is to use existing stations and add chargers to them, but the long charging times will become a cause of congestion. An aspect of the Electric Vehicle Routing Problem that should be studied concerns a problem with a fleet of identical electric vehicles with limited battery capacity and space, while considering various strategies for managing charging periods, which can be either single or multiple, full or partial charging. The purpose of solving this problem is to create feasible solutions to the above problem with minimum cumulative cost and minimum number of vehicles. The addition of service time windows would be interesting to explore. The aim of the research is not to develop or improve vehicles or related technologies, but to successfully manage a set of such vehicles and minimise costs. The solution to this problem is complex as it involves solving and optimising not a simple Vehicle Routing Problem, but a problem with the additional constraints arising from the nature of electric vehicles. The additional difficulty concerns the intermediate stops that a vehicle may have to make at a charging station and the incorporation of realistic parameters for its solution. The aim is to represent the problem as realistically as possible. For the solution, both metaheuristic and nature inspired algorithms will be implemented. These algorithms will either be based on pre-existing techniques that have already been tested on similar problems or will be completely new techniques and algorithms that can be applied to a wide range of Vehicle Routing Problems, such as those studied in this thesis.

Η «ηλεκτρικοποίηση» των μεταφορών είναι ένα από τα βασικά χαρακτηριστικά του μέλλοντος των μεταφορών. Καθώς η νομοθεσία γίνεται όλο και πιο αυστηρή όσο αφορά τα εκπεμπόμενα αέρια του θερμοκηπίου, αυξάνεται και η πίεση για την εισαγωγή «πράσινων» τεχνολογιών στον τομέα των μεταφορών. Τα ηλεκτρικά οχήματα αποτελούν έναν από τους πιο άμεσους τρόπους επίτευξης του σκοπού αυτού. Η εισαγωγή ηλεκτρικών οχημάτων απαιτεί ιδιαίτερη προσπάθεια, καθώς καλείτε να αντιμετωπίσει ένα σύστημα μεταφορών που βασίζεται κατ’ αποκλειστικότητα στα ορυκτά καύσιμα, με δυνατότητα ανεφοδιασμού σε κάθε γωνία του πλανήτη και μάλιστα ταχύτατα. Πολλές επιχειρήσεις έχουν εισάγει ή πρόκειται να εισάγουν ηλεκτρικά οχήματα στον στόλο οχημάτων τους και για την καλύτερη διαχείριση αυτών, θα πρέπει να αναπτυχθούν νέοι αλγόριθμοι που να λαμβάνουν υπόψη τις επισκέψεις στους σταθμούς φόρτισης, την επίδραση που έχει το φορτίο του οχήματος απόσταση που μπορεί να διανύσει το ηλεκτρικό όχημα, το ποσοστό φόρτισης των μπαταριών για ορθή ολοκλήρωση των διαδρομών των οχημάτων αλλά και όλα τα προβλήματα που προκύπτουν με βάση τα παραπάνω. Κατά συνέπεια, το Πρόβλημα Δρομολόγησης Ηλεκτρικών Οχημάτων, αποτελεί ένα σημαντικό νέο πρόβλημα, καταλυτικής σημασίας για την επιτυχία της ενσωμάτωσης των ηλεκτρικών οχημάτων στην εφοδιαστική αλυσίδα. Τα νέα προβλήματα που παρουσιάζουν τα ηλεκτρικά οχήματα, προέρχονται από την χρήση μπαταριών και ηλεκτροκινητήρων, σε αντίθεση με ένα συμβατικό πετρελαιοκίνητο όχημα. Στο σημερινό επίπεδο εξέλιξης των τεχνολογιών που αφορούν την αποθήκευση ενέργειας, δεν είναι εφικτή η επίτευξη της ενεργειακής πυκνότητας των ορυκτών καυσίμων. Ως αποτέλεσμα αυξάνεται η απαιτούμενη συχνότητα φόρτισης. Αυτή η παράμετρος από μόνη της, πιθανά δεν θα ήταν πρόβλημα για ένα συμβατικό όχημα, αλλά για ένα ηλεκτρικό όχημα είναι πολύ σημαντική, καθώς ο χρόνος φόρτισης υπερβαίνει κατά πολύ τον χρόνο ανεφοδιασμού ενός συμβατικού οχήματος. Το γεγονός αυτό προσθέτει επιπλέον κόστος, δεδομένης της αναμονής του οδηγού για την φόρτιση του οχήματος. Ένα επιπλέον επίπεδο δυσκολίας εισάγεται από το γεγονός πως απαιτείται η χρήση σταθμών φόρτισης για τα ηλεκτρικά οχήματα. Τέτοιοι σταθμοί φόρτισης ηλεκτρικών οχημάτων δεν βρίσκονται τόσο συχνά όσο τα πρατήρια υγρών καυσίμων. Η τοποθέτηση νέων σταθμών φόρτισης θα είναι πολύ σημαντική παράμετρος για την πετυχημένη χρήση ηλεκτρικών οχημάτων αφού θα πρέπει να δημιουργηθούν εκ νέου σταθμοί φόρτισης. Η τοποθέτηση των σταθμών αυτών είναι εξαιρετικής σημασίας για την μείωση του κόστους διαδρομής των οχημάτων, καθώς σταθμοί που βρίσκονται εκτός πορείας του οχήματος θα συνεισφέρουν στην αύξηση του κόστους. Από την άλλη, η προσθήκη νέων σταθμών φόρτισης δίχως προσεκτική προηγούμενη μελέτη θα είναι σπατάλη πόρων, όχι μόνο πόρων για την δημιουργία των σταθμών αλλά και των πόρων που θα σπαταλούν τα οχήματα για την μετάβαση στους σταθμούς αυτούς. Ένα από τα ενδεχόμενα προς εξέταση είναι η χρήση των ήδη υπαρχόντων πρατηρίων και την προσθήκη φορτιστών σε αυτών, όμως οι μεγάλοι χρόνοι φόρτισης θα γίνουν αιτία συμφόρησης. Μια έκφανση του Προβλήματος Δρομολόγησης Ηλεκτρικών Οχημάτων που θα πρέπει να μελετηθεί αφορά ένα πρόβλημα με στόλο όμοιων ηλεκτρικών οχημάτων με περιορισμένη χωρητικότητα μπαταρίας και χώρου, εξετάζοντας ταυτόχρονα διάφορες στρατηγικές διαχείρισης των περιόδων φόρτισης, οι οποίες θα μπορούν να είναι είτε μεμονωμένες είτε πολλαπλές, είτε πλήρεις είτε μερικές φορτίσεις. Ο σκοπός της λύσης αυτού του προβλήματος είναι η δημιουργία εφικτών λύσεων για το παραπάνω πρόβλημα με το ελάχιστο αθροιστικό κόστος και τα ελάχιστα οχήματα. Η προσθήκη χρονικών παραθύρων εξυπηρέτησης θα ήταν ενδιαφέρον να εξερευνηθεί. Σκοπός της έρευνας δεν είναι η ανάπτυξη ή βελτίωση οχημάτων ή των σχετικών τεχνολογιών, αλλά η επιτυχημένη διαχείριση ενός συνόλου τέτοιων οχημάτων και η ελαχιστοποίηση του κόστους. Η λύση του προβλήματος αυτού, είναι σύνθετη καθώς αφορά την λύση και την βελτιστοποίηση όχι ενός απλού Προβλήματος Δρομολόγησης Οχημάτων, αλλά ενός προβλήματος με τους πρόσθετους περιορισμούς που προκύπτουν από την φύση των ηλεκτρικών οχημάτων. Η επιπλέον δυσκολία αφορά τις ενδιάμεσες στάσεις που πιθανά θα πρέπει να πραγματοποιήσει ένα όχημα σε σταθμό φόρτισης και την ενσωμάτωση ρεαλιστικών παραμέτρων για την λύση του. Στόχος είναι η όσο πιο ρεαλιστική αναπαράσταση του προβλήματος. Για την επίλυση, θα υλοποιηθούν μεθευρετικοί και μη αλγόριθμοι. Οι αλγόριθμοι αυτοί είτε θα βασίζονται σε προϋπάρχουσες τεχνικές που έχουν ήδη δοκιμαστεί σε αντίστοιχα προβλήματα είτε θα είναι εντελώς νέες τεχνικές και αλγόριθμοι που θα μπορούν να εφαρμοστούν σε μεγάλο εύρος Προβλημάτων Δρομολόγησης Οχημάτων, όπως αυτά που μελετώνται σε αυτή την διδακτορική διατριβή.