Εύρεση εναλλακτικών διαδρομών με διαφορετικά χαρακτηριστικά σε οδικά δίκτυα
Loading...
Date
2026-02-25
Authors
Γιαννακούρος, Πέτρος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Η παρούσα διπλωματική εργασία ασχολείται με το πρόβλημα της εύρεσης εναλλακτικώνδιαδρομών σε οδικά δίκτυα, με έμφαση στην ποικιλία (diversity) των προτεινόμενωνδιαδρομών. Ενώ οι περισσότερες κλασικές προσεγγίσεις περιορίζονται στην εύρεση τηςσυντομότερης διαδρομής, οι σύγχρονες εφαρμογές πλοήγησης απαιτούν τη διάθεσηπολλαπλών επιλογών που να είναι αφενός συγκρίσιμες σε μήκος ή χρόνο, αφετέρου ουσιωδώςδιαφορετικές. Στο πλαίσιο αυτό μελετάται το πρόβλημα εύρεσης των k πιο διαφοροποιημένωνσχεδόν συντομότερων διαδρομών (k Most Diverse Near-Shortest Paths, kMDNSP), το οποίοείναι υπολογιστικά δύσκολο (NP-hard). Υλοποιούνται δύο αλγόριθμοι από τη βιβλιογραφία, οDIRECT και ο PENALTY, σε γλώσσα C++ με χρήση της βιβλιοθήκης LEDA, καιαξιολογούνται σε δεδομένα οδικών δικτύων. Ο δείκτης ποικιλίας βασίζεται στην (βαρύνουσα)απόσταση Jaccard μεταξύ συνόλων ακμών. Τα πειραματικά αποτελέσματα δείχνουν ότι ο PENALTY παράγει διαδρομές με υψηλότερη ποικιλία αλλά με αυξημένο χρόνο εκτέλεσης,ενώ ο DIRECT είναι ταχύτερος αλλά με μικρότερη ποικιλία. Τέλος, συζητούνται τα πλεονεκτήματα και οι περιορισμοί κάθε μεθόδου, καθώς και προοπτικές βελτίωσης.
Description
Keywords
Εναλλακτικές διαδρομές, Οδικά δίκτυα, Σχεδόν συντομότερες διαδρομές, Ποικιλία διαδρομών, Αλγόριθμοι γραφημάτων, Ευρετικοί αλγόριθμοι