Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Εκμετάλλευση προτιμήσεων επιβατών για την επίλυση του προβλήματος του κοινωνικού διαμοιρασμού δρομολογίων

Pagkalos Emmanouil

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/07500743-D748-48DE-87F9-D80A9BF03F8B-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.90586-
Γλώσσαen-
Μέγεθος98 pagesen
Μέγεθος3.7 megabytesen
ΤίτλοςPreferences-Aware social ridesharingen
ΤίτλοςΕκμετάλλευση προτιμήσεων επιβατών για την επίλυση του προβλήματος του κοινωνικού διαμοιρασμού δρομολογίωνel
ΔημιουργόςPagkalos Emmanouilen
ΔημιουργόςΠαγκαλος Εμμανουηλel
Συντελεστής [Επιβλέπων Καθηγητής]Chalkiadakis Georgiosen
Συντελεστής [Επιβλέπων Καθηγητής]Χαλκιαδακης Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Lagoudakis Michailen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Λαγουδακης Μιχαηλel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Partsinevelos Panagiotisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Παρτσινεβελος Παναγιωτηςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Περίληψη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.en
ΠερίληψηΤο Ridesharing είναι μια συγκεκριμενοποίηση της λεγόμενης οικονομίας διαμοιρασμού στον τομέα των μετακινήσεων. Η χρήση του Ridesharing επιτρέπει την μεταφορά ατόμων με οχήματα που ανήκουν και οδηγούνται από άλλους (πιθανώς) ιδιώτες, προκειμένου οι εμπλεκόμενοι αφενός να μειώσουν το κόστος μετακίνησής τους, και αφετέρου να απολαύσουν ενδεχομένως μια πιο ευχάριστη διαδρομή σε σύγκριση με αυτές που προσφέρονται από εναλλακτικά μέσα μεταφοράς. Παρά τα προβαλλόμενα πλεονεκτήματά του, λ.χ. από την άποψη της αυξημένης κοινωνικοποίησης των εμπλεκόμενων καθώς και των δυνητικά τεράστιων θετικών περιβαλλοντικών επιπτώσεών του (λόγω μείωσης της ανάγκης για ιδιόκτητα μέσα μεταφοράς), το Ridesharing δεν έχει αποκτήσει ακόμη μεγάλη δημοτικότητα. Κατά πάσα πιθανότητα, για να συμβεί αυτό το Ridesharing πρέπει να προσφέρει μια σαφώς πιο ευχάριστη σε σχέση με άλλες εμπειρία μετακίνησης σε όσους το χρησιμοποιούν. Στην παρούσα διπλωματική εργασία, προσεγγίζουμε το πρόβλημα Ridesharing μέσω λύσεων Τεχνητής Νοημοσύνης προερχόμενων κατά κύριο λόγο από τα πεδία των Πολυπρακτορικών Συστημάτων, της Θεωρίας Γράφων, και της Θεωρίας Παιγνίων. ΄Ενα κομβικής σημασίας στοιχείο στην προσέγγισή μας είναι ότι, για πρώτη φορά στη βιβλιογραφία, λαμβάνουμε υπόψη τις προτιμήσεις των εμπλεκομένων σχετικά με τα χαρακτηριστικά των συνεπιβατών τους. Αυτό είναι σημαντικό καθώς είναι αναμενόμενο η κάλυψη τέτοιων προτιμήσεων να αυξήσει σημαντικά το συνολικό επίπεδο ικανοποίησης των συμμετεχόντων από την υπηρεσία. Η διπλωματική μας εργασία προσφέρει ένα αρχικό αλλά πλήρες πλαίσιο για κοινή χρήση προτιμήσεων στο Ridesharing. Αρχικά χρησιμοποιούμε την έννοια των υπεργράφων, προκειμένου να δημιουργήσουμε μια αρχική ομαδοποίηση των πρακτόρων λαμβάνοντας υπόψη τις περιοχές όπου κινούνται. Στη συνέχεια, χρησιμοποιούμε έναν άπληστο αλγόριθμο και έναν αλγόριθμο διακλάδωσης και δέσμευσης για να διανείμουμε τους πράκτορες σε οχήματα, με στόχο (α) να διατηρήσουμε τις παρακάμψεις των οδηγών σε όσο το δυνατόν χαμηλότερα επίπεδα και, ταυτόχρονα, (β) να ικανοποιήσουμε τις εκφρασμένες προτιμήσεις των πρακτόρων στο μέγιστο δυνατό βαθμό. Επιπλέον, προτείνουμε ένα σύστημα επιμερισμού του κόστους, για να αποζημιώσουμε τους οδηγούς για τη συμμετοχή τους στο πρόγραμμα και το επιπλέον κόστος που αυτή συνεπάγεται, και για να μειώσουμε τα έξοδά τους σε σχέση με τη μη συμμετοχή τους και άρα να δημιουργήσουμε κίνητρα συμμετοχής. Μελετήσαμε συστηματικά την απόδοση του προτεινόμενου πλαισίου Ridesharing μέσω σεναρίων προσομοίωσης που εκτελούνται σε χάρτες των τεσσάρων κύριων πόλεων της Κρήτης: το Ηράκλειο, τα Χανιά, το Ρέθυμνο και τον ΄Αγιο Νικόλαο. Τα αποτελέσματά μας δείχνουν ότι (α) η προσέγγισή μας έχει υψηλή αποτελεσματικότητα όσον αφορά την κάλυψη των αναγκών μετακίνησης των εν δυνάμει επιβατών (που δεν διαθέτουν όχημα) · (β) ταυτόχρονα, η μέση επιπλέον απόσταση που πρέπει να διανύσουν οι οδηγοί για να προσφέρουν τις υπηρεσίες τους στους επιβάτες διατηρείται σε αποδεκτά επίπεδα · (γ) τα κόστη που πληρώνουν οι οδηγοί είναι σημαντικά μειωμένα σε σχέση με τα κόστη τους όταν δεν συμμετέχουν στην υπηρεσία Ridesharing · και (δ) οι προτιμήσεις των πρακτόρων ικανοποιούνται σε μεγάλο βαθμό, γεγονός το οποίο αναμφισβήτητα βελτιώνει ολόκληρη την εμπειρία χρήσης του Ridesharing . Αξιοσημείωτα, τα αποτελέσματα προσομοίωσης είναι ιδιαίτερα ενθαρρυντικά για σενάρια με πολύ χαμηλότερη ιδιοκτησία οχήματος από την τρέχουσα (χαμηλό ποσοστό οδηγών), υπογραμμίζοντας έτσι τις δυνατότητες που ανοίγει η χρήση Ridesharing σε έναν μελλοντικό, πιο πράσινο, σε μεγάλο βαθμό χωρίς ιδιόκτητα οχήματα κόσμο.el
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by-sa/4.0/en
Ημερομηνία2021-10-15-
Ημερομηνία Δημοσίευσης2021-
Θεματική Κατηγορία Multiagent systemsen
Θεματική ΚατηγορίαArtificial intelligenceen
Βιβλιογραφική ΑναφοράEmmanouil Pagkalos, "Preferences-Aware social ridesharing", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2021en
Βιβλιογραφική ΑναφοράΕμμανουήλ Πάγκαλος, "Εκμετάλλευση προτιμήσεων επιβατών για την επίλυση του προβλήματος του κοινωνικού διαμοιρασμού δρομολογίων", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά