Συντάχθηκε 11-10-2021 09:43
Τόπος: Η παρουσίαση θα γίνει με τηλεδιάσκεψη
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 15/10/2021 10:00
Λήξη: 15/10/2021 11:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΕΜΜΑΝΟΥΗΛ ΠΑΓΚΑΛΟΣ
θέμα
Εκμετάλλευση Προτιμήσεων Επιβατών για την Επίλυση του Προβλήματος του Κοινωνικού Διαμοιρασμού Δρομολογίων
Preferences-Aware Social Ridesharing
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Αναπληρωτής Καθηγητής Παναγιώτης Παρτσινέβελος (Σχολή ΜΗΧΟΠ)
Περίληψη
Το Ridesharing είναι μια συγκεκριμενοποίηση της λεγόμενης οικονομίας διαμοιρασμού στον τομέα των μετακινήσεων. Η χρήση του Ridesharing επιτρέπει την μεταφορά ατόμων με οχήματα που ανήκουν και οδηγούνται από άλλους (πιθανώς) ιδιώτες, προκειμένου οι εμπλεκόμενοι αφενός να μειώσουν το κόστος μετακίνησής τους, και αφετέρου να απολαύσουν ενδεχομένως μια πιο ευχάριστη διαδρομή σε σύγκριση με αυτές που προσφέρονται από εναλλακτικά μέσα μεταφοράς. Παρά τα προβαλλόμενα πλεονεκτήματά του, λ.χ. από την άποψη της αυξημένης κοινωνικοποίησης των εμπλεκόμενων καθώς και των δυνητικά τεράστιων θετικών περιβαλλοντικών επιπτώσεών του (λόγω μείωσης της ανάγκης για ιδιόκτητα μέσα μεταφοράς), το Ridesharing δεν έχει αποκτήσει ακόμη μεγάλη δημοτικότητα. Κατά πάσα πιθανότητα, για να συμβεί αυτό το Ridesharing πρέπει να προσφέρει μια σαφώς πιο ευχάριστη σε σχέση με άλλες εμπειρία μετακίνησης σε όσους το χρησιμοποιούν. Στην παρούσα διπλωματική εργασία, προσεγγίζουμε το πρόβλημα Ridesharing μέσω λύσεων Τεχνητής Νοημοσύνης προερχόμενων κατά κύριο λόγο από τα πεδία των Πολυπρακτορικών Συστημάτων, της Θεωρίας Γράφων, και της Θεωρίας Παιγνίων. ΄Ενα κομβικής σημασίας στοιχείο στην προσέγγισή μας είναι ότι, για πρώτη φορά στη βιβλιογραφία, λαμβάνουμε υπόψη τις προτιμήσεις των εμπλεκομένων σχετικά με τα χαρακτηριστικά των συνεπιβατών τους. Αυτό είναι σημαντικό καθώς είναι αναμενόμενο η κάλυψη τέτοιων προτιμήσεων να αυξήσει σημαντικά το συνολικό επίπεδο ικανοποίησης των συμμετεχόντων από την υπηρεσία. Η διπλωματική μας εργασία προσφέρει ένα αρχικό αλλά πλήρες πλαίσιο για κοινή χρήση προτιμήσεων στο Ridesharing. Αρχικά χρησιμοποιούμε την έννοια των υπεργράφων, προκειμένου να δημιουργήσουμε μια αρχική ομαδοποίηση των πρακτόρων λαμβάνοντας υπόψη τις περιοχές όπου κινούνται. Στη συνέχεια, χρησιμοποιούμε έναν άπληστο αλγόριθμο και έναν αλγόριθμο διακλάδωσης και δέσμευσης για να διανείμουμε τους πράκτορες σε οχήματα, με στόχο (α) να διατηρήσουμε τις παρακάμψεις των οδηγών σε όσο το δυνατόν χαμηλότερα επίπεδα και, ταυτόχρονα, (β) να ικανοποιήσουμε τις εκφρασμένες προτιμήσεις των πρακτόρων στο μέγιστο δυνατό βαθμό. Επιπλέον, προτείνουμε ένα σύστημα επιμερισμού του κόστους, για να αποζημιώσουμε τους οδηγούς για τη συμμετοχή τους στο πρόγραμμα και το επιπλέον κόστος που αυτή συνεπάγεται, και για να μειώσουμε τα έξοδά τους σε σχέση με τη μη συμμετοχή τους και άρα να δημιουργήσουμε κίνητρα συμμετοχής. Μελετήσαμε συστηματικά την απόδοση του προτεινόμενου πλαισίου Ridesharing μέσω σεναρίων προσομοίωσης που εκτελούνται σε χάρτες των τεσσάρων κύριων πόλεων της Κρήτης: το Ηράκλειο, τα Χανιά, το Ρέθυμνο και τον ΄Αγιο Νικόλαο. Τα αποτελέσματά μας δείχνουν ότι (α) η προσέγγισή μας έχει υψηλή αποτελεσματικότητα όσον αφορά την κάλυψη των αναγκών μετακίνησης των εν δυνάμει επιβατών (που δεν διαθέτουν όχημα) · (β) ταυτόχρονα, η μέση επιπλέον απόσταση που πρέπει να διανύσουν οι οδηγοί για να προσφέρουν τις υπηρεσίες τους στους επιβάτες διατηρείται σε αποδεκτά επίπεδα · (γ) τα κόστη που πληρώνουν οι οδηγοί είναι σημαντικά μειωμένα σε σχέση με τα κόστη τους όταν δεν συμμετέχουν στην υπηρεσία Ridesharing · και (δ) οι προτιμήσεις των πρακτόρων ικανοποιούνται σε μεγάλο βαθμό, γεγονός το οποίο αναμφισβήτητα βελτιώνει ολόκληρη την εμπειρία χρήσης του Ridesharing . Αξιοσημείωτα, τα αποτελέσματα προσομοίωσης είναι ιδιαίτερα ενθαρρυντικά για σενάρια με πολύ χαμηλότερη ιδιοκτησία οχήματος από την τρέχουσα (χαμηλό ποσοστό οδηγών), υπογραμμίζοντας έτσι τις δυνατότητες που ανοίγει η χρήση Ridesharing σε έναν μελλοντικό, πιο πράσινο, σε μεγάλο βαθμό χωρίς ιδιόκτητα οχήματα κόσμο.
Abstract
Ridesharing is a shared-economy transportation paradigm, in which people can catch rides in vehicles that are (possibly) privately owned and driven by others, in order to reduce transportation costs and possibly enjoy a more pleasant ride when compared to those offered by alternative means of transportation. Despite its touted advantages, e.g. in terms of increased socialization and potentially huge positive environmental impact, Ridesharing has not gained much popularity yet. Arguably, for this to happen Ridesharing needs to offer a clearly more-pleasant-than-others transportation experience to people who use it. In this thesis, we approach the Ridesharing problem via Artificial Intelligence solution concepts originating primarily in the Multiagent Systems, graph-theoretic, and game-theoretic research literature; and, importantly, we take into consideration the riders’ (agents) preferences about attributes of their co-riders. Taking into account such preferences, bears the potential to greatly impact positively the participants’ satisfaction. Our thesis offers an initial but complete framework for preferences-aware Ridesharing. We first employ the concept of a hypergraph to the set of agents, in order to create an initial clustering given the areas where they move. We then use a greedy algorithm and a branch and bound algorithm in order to distribute the agents into vehicles with the aim of (a) maintaining the drivers’ detours to as low levels as possible; and, at the same time, (b) satisfying most of the expressed agents’ preferences. Furthermore, we put forward a cost-sharing scheme to compensate drivers for their participation in the scheme and the extra costs this entails, and to create incentives for participation via overall drivers’ costs reduction. We studied systematically the performance of our Ridesharing framework via simulation scenarios run on maps of the four main cities of Crete: Heraklion, Chania, Rethymno, and Agios Nikolaos. Our results show that (a) our approach has high effectiveness in terms of covering the transportation needs of the (non-driving) commuters; (b) at the same time, the average extra distance that drivers need to cover when offering their services to passengers is kept to acceptable levels; (c) the costs of the drivers are substantially reduced when compared to their costs when not participating in Ridesharing; and (d) the agents’ preferences are satisfied to a large degree, a fact which arguably improves their whole Ridesharing experience. Notably, our simulation results are particularly encouraging for scenarios with much-lower-than-current vehicle ownership (drivers’ percentage), thus underscoring the potential of Ridesharing in a future, greener, largely free of privately owned vehicles world.
Meeting ID: 988 7479 1102
Password: 453973
