Formulation and solution methods for locating charging stations and routing of electric vehicles
Authors: Σταμαδιάνος Θεμιστοκλής 
Published: September 2023

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