Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

Συνάθροιση προτιμήσεων για το πρόβλημα κοινωνικού διαμοιρασμού διαδρομών

Asproudi Antigoni

Πλήρης Εγγραφή

---

Περίληψη

Οι παραδοσιακές προσεγγίσεις στο ridesharing (ή αλλιώς διαμερισμό διαδρομών) περιλαμβάνουν την ομαδοποίηση οδηγών και επιβατών βάσει των δρομολογίων και των χρονοδιαγραμμάτων τους. Ο στόχος είναι να μοιραστεί το κόστος της διαδρομής, ελαχιστοποιώντας παράλληλα τις καθυστερήσεις και την επιπλέον αύξηση της απόστασης που καλύπτει ο οδηγός κατά την εξυπηρέτηση των επιβατών. Αποτελεί μία ευέλικτη και οικονομική εναλλακτική λύση στα παραδοσιακά μέσα μεταφοράς, προσφέροντας οφέλη φιλικά για το περιβάλλον και την αντιμετώπιση της κυκλοφοριακής συμφόρησης, καθώς με τη χρήση του ridesharingαπό περισσότερα άτομα, μειώνεται ο αριθμός των οχημάτων στους δρόμους.Σε αυτή τη διπλωματική εργασία, προσεγγίζουμε το πρόβλημα του ridesharing λαμβάνοντας υπόψη κριτήρια που έχουν να κάνουν τόσο με την τοποθεσία, όσο και με τις προτιμήσεις των πρακτόρων σχετικά με τα χαρακτηριστικά των συνεπιβατών τους. Αυτό συμπεριλαμβάνει και την ομαδοποίηση μεταξύ επιβατών, εφαρμόζοντας συνάθροιση προτιμήσεων μεταξύ τους, προκειμένου να επιλεχθούν αυτοί που θα μοιραστούν το ίδιο όχημα. Η ικανοποίηση των προτιμήσεων είναι ένα σημαντικό κομμάτι της δουλειάς μας, καθώς συμβάλλει στο να έχουν όλοι μια καλύτερη εμπειρία ταξιδιού, αλλά και να αισθάνονται οι επιβάτες ασφαλείς, λαμβάνοντας υπόψη τις προτιμήσεις τους σχετικά με τους συνεπιβάτες τους.Βασισμένη στην Θεωρία Παιγνίων, η προσέγγισή μας παράγει core-stable ζευγάρια οδηγών-επιβατών και kernel-stable κατανομή κόστους του ταξιδιού. Με τη χρήση υπεργράφων, γίνεται εντοπισμός επιβατών που μετακινούνται στην ίδια περιοχή με τον οδηγό, ενώ διεξάγοντας πειράματα που περιλαμβάνουν παραλλαγές στο σχήμα της περιοχής από την οποία ο οδηγός μπορεί να εξυπηρετήσει επιβάτες, αξιολογούμε την επίδρασή της στην επιπλέον απόσταση που αυτός θα πρέπει να καλύψει. Με τη χρήση του αλγορίθμου Gale-Shapley, “ταιριάζουμε” οδηγούς με επιβάτες, εξασφαλίζοντας ότι τα αποτελέσματα βρίσκονται στον πυρήνα (core). Για τον σχεδιασμό της τελικής διαδρομής, εφαρμόζουμε έναν αλγόριθμο Branch and Bound για τον εντοπισμό μιας καλής ακολουθίας στάσεων που πρέπει να κάνει ο οδηγός για να ελαχιστοποιήσει το κόστος του ταξιδιού. Ο αλγόριθμος του Dijkstra συνδέει αυτές τις στάσεις για να δημιουργήσει την τελική διαδρομή. Στη συνέχεια, το κόστος του ταξιδιού μοιράζεται δίκαια μεταξύ των επιβατών κάθε οχήματος, χρησιμοποιώντας την παιγνιοθεωρητική έννοια χαρακτηρισμού σταθερότητας συνασπισμών “kernel”. Η απόδοση της δουλειάς μας ελέγχεται με τη διεξαγωγή προσομοιώσεων στην πόλη των Χανίων, για ένα εύρος από 800 έως 2500 πράκτορες, όπου το 35% αυτών είναι οδηγοί. Τα αποτελέσματα υποδηλώνουν ότι η υλοποίησή μας ξεπερνά σε επιδόσεις προηγούμενη δουλειά πάνω στο αντικείμενο, όσον αφορά την ικανοποίηση των προτιμήσεων. Επιπλέον, συνδυάζει αποτελεσματικά τους πράκτορες, τοποθετώντας περίπου τρεις ανά όχημα, υποθέτοντας μέγιστη χωρητικότητα τεσσάρων επιβατών, συμβάλλοντας με αυτό τον τρόπο στη μείωση του όγκου των οχημάτων στους δρόμους. Τέλος, η αύξηση της επιπλέον απόστασης που καλύπτει ο οδηγός προκειμένου να εξυπηρετήσει τους επιβάτες διατηρείται σε αποδεχτά επίπεδα, ενώ το κόστος διαδρομής του οδηγού μειώνεται.

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

Υπηρεσίες