Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/07500743-D748-48DE-87F9-D80A9BF03F8B | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.90586 | - |
| Language | en | - |
| Extent | 98 pages | en |
| Extent | 3.7 megabytes | en |
| Title | Preferences-Aware social ridesharing | en |
| Title | Εκμετάλλευση προτιμήσεων επιβατών για την επίλυση του προβλήματος του κοινωνικού διαμοιρασμού δρομολογίων | el |
| Creator | Pagkalos Emmanouil | en |
| Creator | Παγκαλος Εμμανουηλ | el |
| Contributor [Thesis Supervisor] | Chalkiadakis Georgios | en |
| Contributor [Thesis Supervisor] | Χαλκιαδακης Γεωργιος | el |
| Contributor [Committee Member] | Lagoudakis Michail | en |
| Contributor [Committee Member] | Λαγουδακης Μιχαηλ | el |
| Contributor [Committee Member] | Partsinevelos Panagiotis | en |
| Contributor [Committee Member] | Παρτσινεβελος Παναγιωτης | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | 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 |
| Content Summary | Το Ridesharing είναι μια συγκεκριμενοποίηση της λεγόμενης οικονομίας διαμοιρασμού στον τομέα των μετακινήσεων. Η χρήση του Ridesharing επιτρέπει την μεταφορά ατόμων με οχήματα που ανήκουν και οδηγούνται από άλλους (πιθανώς) ιδιώτες, προκειμένου οι εμπλεκόμενοι αφενός να μειώσουν το κόστος μετακίνησής τους, και αφετέρου να απολαύσουν ενδεχομένως μια πιο ευχάριστη διαδρομή σε σύγκριση με αυτές που προσφέρονται από εναλλακτικά μέσα μεταφοράς. Παρά τα προβαλλόμενα πλεονεκτήματά του, λ.χ. από την άποψη της αυξημένης κοινωνικοποίησης των εμπλεκόμενων καθώς και των δυνητικά τεράστιων θετικών περιβαλλοντικών επιπτώσεών του (λόγω μείωσης της ανάγκης για ιδιόκτητα μέσα μεταφοράς), το Ridesharing δεν έχει αποκτήσει ακόμη μεγάλη δημοτικότητα. Κατά πάσα πιθανότητα, για να συμβεί αυτό το Ridesharing πρέπει να προσφέρει μια σαφώς πιο ευχάριστη σε σχέση με άλλες εμπειρία μετακίνησης σε όσους το χρησιμοποιούν. Στην παρούσα διπλωματική εργασία, προσεγγίζουμε το πρόβλημα Ridesharing μέσω λύσεων Τεχνητής Νοημοσύνης προερχόμενων κατά κύριο λόγο από τα πεδία των Πολυπρακτορικών Συστημάτων, της Θεωρίας Γράφων, και της Θεωρίας Παιγνίων. ΄Ενα κομβικής σημασίας στοιχείο στην προσέγγισή μας είναι ότι, για πρώτη φορά στη βιβλιογραφία, λαμβάνουμε υπόψη τις προτιμήσεις των εμπλεκομένων σχετικά με τα χαρακτηριστικά των συνεπιβατών τους. Αυτό είναι σημαντικό καθώς είναι αναμενόμενο η κάλυψη τέτοιων προτιμήσεων να αυξήσει σημαντικά το συνολικό επίπεδο ικανοποίησης των συμμετεχόντων από την υπηρεσία. Η διπλωματική μας εργασία προσφέρει ένα αρχικό αλλά πλήρες πλαίσιο για κοινή χρήση προτιμήσεων στο Ridesharing. Αρχικά χρησιμοποιούμε την έννοια των υπεργράφων, προκειμένου να δημιουργήσουμε μια αρχική ομαδοποίηση των πρακτόρων λαμβάνοντας υπόψη τις περιοχές όπου κινούνται. Στη συνέχεια, χρησιμοποιούμε έναν άπληστο αλγόριθμο και έναν αλγόριθμο διακλάδωσης και δέσμευσης για να διανείμουμε τους πράκτορες σε οχήματα, με στόχο (α) να διατηρήσουμε τις παρακάμψεις των οδηγών σε όσο το δυνατόν χαμηλότερα επίπεδα και, ταυτόχρονα, (β) να ικανοποιήσουμε τις εκφρασμένες προτιμήσεις των πρακτόρων στο μέγιστο δυνατό βαθμό. Επιπλέον, προτείνουμε ένα σύστημα επιμερισμού του κόστους, για να αποζημιώσουμε τους οδηγούς για τη συμμετοχή τους στο πρόγραμμα και το επιπλέον κόστος που αυτή συνεπάγεται, και για να μειώσουμε τα έξοδά τους σε σχέση με τη μη συμμετοχή τους και άρα να δημιουργήσουμε κίνητρα συμμετοχής. Μελετήσαμε συστηματικά την απόδοση του προτεινόμενου πλαισίου Ridesharing μέσω σεναρίων προσομοίωσης που εκτελούνται σε χάρτες των τεσσάρων κύριων πόλεων της Κρήτης: το Ηράκλειο, τα Χανιά, το Ρέθυμνο και τον ΄Αγιο Νικόλαο. Τα αποτελέσματά μας δείχνουν ότι (α) η προσέγγισή μας έχει υψηλή αποτελεσματικότητα όσον αφορά την κάλυψη των αναγκών μετακίνησης των εν δυνάμει επιβατών (που δεν διαθέτουν όχημα) · (β) ταυτόχρονα, η μέση επιπλέον απόσταση που πρέπει να διανύσουν οι οδηγοί για να προσφέρουν τις υπηρεσίες τους στους επιβάτες διατηρείται σε αποδεκτά επίπεδα · (γ) τα κόστη που πληρώνουν οι οδηγοί είναι σημαντικά μειωμένα σε σχέση με τα κόστη τους όταν δεν συμμετέχουν στην υπηρεσία Ridesharing · και (δ) οι προτιμήσεις των πρακτόρων ικανοποιούνται σε μεγάλο βαθμό, γεγονός το οποίο αναμφισβήτητα βελτιώνει ολόκληρη την εμπειρία χρήσης του Ridesharing . Αξιοσημείωτα, τα αποτελέσματα προσομοίωσης είναι ιδιαίτερα ενθαρρυντικά για σενάρια με πολύ χαμηλότερη ιδιοκτησία οχήματος από την τρέχουσα (χαμηλό ποσοστό οδηγών), υπογραμμίζοντας έτσι τις δυνατότητες που ανοίγει η χρήση Ridesharing σε έναν μελλοντικό, πιο πράσινο, σε μεγάλο βαθμό χωρίς ιδιόκτητα οχήματα κόσμο. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by-sa/4.0/ | en |
| Date of Item | 2021-10-15 | - |
| Date of Publication | 2021 | - |
| Subject | Multiagent systems | en |
| Subject | Artificial intelligence | en |
| Bibliographic Citation | Emmanouil Pagkalos, "Preferences-Aware social ridesharing", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2021 | en |
| Bibliographic Citation | Εμμανουήλ Πάγκαλος, "Εκμετάλλευση προτιμήσεων επιβατών για την επίλυση του προβλήματος του κοινωνικού διαμοιρασμού δρομολογίων", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 | el |
Copyright © DIAS 2013
