Design and implementation of carpooling matching algorithms

Abstract

Στην παρούσα διπλωματική εργασία έγινε σχεδίαση και υλοποίηση δύο νέων αλγορίθμων που έχουν εφαρμογή στον διαμοιρασμό μετακινήσεων με ιδιωτικά οχήματα. Πιο συγκεκριμένα, εξετάσαμε μια ειδική περίπτωση κατά την οποία, πολλοί επιβάτες και οδηγοί πρόκειται να συνταξιδέψουν σε ένα συγκεκριμένο κοινό προορισμό. Με αυτόν τον τρόπο, επιτυγχάνεται μείωση του κόστους των συμμετεχόντων κατά τη μετακίνηση τους, προσφέρεται ευελιξία στην ώρα και μειώνεται η διάρκεια του ταξιδιού, σε αντίθεση με την περίπτωση που η μετακίνηση γινόταν με μέσα μαζικής μεταφοράς. Επίσης, ο συνεπιβατισμός, όπως ονομάζεται αυτή η διαδικασία, έχει και άλλα πλεονεκτήματα, όπως η μείωση της κίνησης στους δρόμους, αφού άτομα μετακινούνται μαζί αντί μόνοι τους, με συνέπεια έναν θετικό περιβαλλοντικό αντίκτυπο. Σε αυτή την εργασία, προτείνουμε δύο νέους αλγορίθμους που βασίζονται στον δημοφιλή γενετικό αλγόριθμο NSGA-II. Ο σκοπός τους, είναι να ταιριάξουν επιβάτες και οδηγούς που έχουν κοινό προορισμό, μεγιστοποιώντας την χωρητικότητα κάθε οχήματος και ταυτόχρονα ελαχιστοποιώντας την συνολική απόσταση που πρέπει να διανυθεί από τον οδηγό μέχρι τον προορισμό. Εξετάζουμε δύο περιπτώσεις: (α) όταν το πρόβλημα έχει έναν οδηγό και πολλούς επιβάτες και (β) όταν το πρόβλημα έχει πολλούς οδηγούς και πολλούς επιβάτες. Οι δύο αλγόριθμοι που παρουσιάζονται σε αυτή την εργασία έχουν εφαρμογή σε αυτές τις δυο περιπτώσεις και ουσιαστικά αφορούν τροποποιήσεις του γενετικού NSGA-II, ούτως ώστε να επιτύχουμε μεγαλύτερη αποδοτικότητα. Πιο συγκεκριμένα, προτείνουμε: (α) τη χρήση μιας τεχνικής ομαδοποίησης, την εφαρμογή του DBSCAN αλγορίθμου, κατά τη διαδικασία της αρχικοποίησης του αρχικού πληθυσμού (β) έναν νέο γενετικό μηχανισμό δημιουργίας απογόνων που βασίζεται στη χωρική θέση των επιβατών και τέλος, (γ) ένα νέο γενετικό μηχανισμό τροποποίησης των λύσεων που εφαρμόζεται με μία μέθοδο τοπικής αναζήτησης. Επίσης, πραγματοποιήσαμε εκτενή ανάλυση και πειράματα για να διαπιστώσουμε την αποτελεσματικότητα των επιμέρους τροποποιήσεων που προτείνουμε σε αυτούς τους δύο νέους αλγορίθμους αλλά και να εξάγουμε συμπερασμάτα σχετικά με την ποιότητα των λύσεων. Τα αποτελέσματα ήταν ενθαρρυντικά, καθώς οι τροποποιήσεις φαίνεται να επηρεάζουν τις λύσεις προς το καλύτερο. Τέλος, κάναμε και μια μικρή αναφορά στις πιο γνωστές αρχιτεκτονικές που υπάρχουν στη βιβλιογραφία και που αφορούν την αυθεντικοποίηση των χρηστών και τη διασφάλιση της ιδιωτικότητάς τους, όταν πρόκειται να χρησιμοποιήσουν μια τέτοια εφαρμογή διαμοιρασμού μετακινήσεων.