Αλγόριθμοι Για Γραφήματα Εναλλακτικών Διαδρομών Σε Οδικά Δίκτυα : Επισκόπηση Και Αξιολόγηση

Abstract

Στις μέρες μας, οι μετακινήσεις έχουν αποκτήσει μεγάλη σημασία. Οι άνθρωποι ταξιδεύουν καθημερινά είτε για τις δουλειές τους είτε για λόγους αναψυχής με αποτέλεσμα οι μετακινήσεις να αποτελούν ένα σημαντικό μέρος της ζωής τους. Αν και οι πρώτοι αλγόριθμοι, που έλυναν τέτοιου είδους προβλήματα, όπως ο Dijkstra και ο Bellman-Ford είναι αρκετά παλιοί, οι νέες συνθήκες απαιτούν πιο αποδοτικές λύσεις λαμβάνοντας ταυτόχρονα υπόψη ποικίλες παραμέτρους όπως τις προτιμήσεις των οδηγών, τις περιβαλλοντικές συνθήκες, τις οικονομικές συγκυρίες, την κυκλοφοριακή συμφόρηση και πολλά άλλα.Κάτω από αυτές τις νέες απαιτήσεις, το algorithmic engineering δείχνει τα τελευταία χρόνια μεγάλο ενδιαφέρον σχετικά με την εύρεση και το σχεδιασμό διαδρομών, αναπτύσσοντας νέες αλγοριθμικές μεθόδους οι οποίες λύνουν πιο εξεζητημένες εκδοχές του προβλήματος εύρεσης βέλτιστης διαδρομής. Για παράδειγμα, ερευνητές έχουν αναπτύξει τεχνικές επιτάχυνσης του Dijkstra με τις οποίες καταφέρνουν να υπολογίσουν ερωτήματα μεταξύ αφετηρίας-προορισμού σε μεγάλης κλίμακας δίκτυα με πολύ μικρή χρονική πολυπλοκότητα ή έχουν εισάγει την έννοια εύρεσης διαδρομών με συνδυασμό των μέσων μαζικής μεταφοράς κλπ.Σε αυτή τη διπλωματική εργασία, επικεντρωνόμαστε σε μία παραλλαγή του προβλήματος εύρεσης συντομότερης διαδρομής η οποία έχει στόχο να εντοπίζει πολλαπλές εναλλακτικές διαδρομές από μία αφετηρία σε έναν προορισμό, πέραν της βέλτιστης. Η έρευνα πάνω σε αυτό το αντικείμενο είναι ιδιαίτερα σημαντική μιας και ο υπολογισμός ενός συνόλου εναλλακτικών διαδρομών είναι πολύ χρήσιμος σε πληθώρα περιπτώσεων. Για παράδειγμα, η αποφυγή διοδίων, η αυξανόμενη εμφάνιση κυκλοφοριακών προβλημάτων, η προτίμηση ενός οδηγού να αποφεύγει κακόφημους δρόμους αποτελούν λίγες περιπτώσεις όπου ο υπολογισμός μιας μοναδικής διαδρομής δεν επαρκεί.Συνεπώς, στην εργασία αυτή, παρουσιάζουμε τη μέθοδο του plateau (plateau method) η οποία αποτελεί μία σημαντική προσέγγιση σε αυτό το πεδίο ενδιαφέροντος και βασίζεται στην εύρεση μονοπατιών οι κόμβοι των οποίων έχουν σταθερές αποστάσεις από την αφετηρία και τον προορισμό (plateaux). Αναλύουμε βήμα προς βήμα όλα τα στάδια του αλγορίθμου, κατανοούμε τη μεθοδολογία και κάνουμε τη δική μας υλοποίηση σε C++. Στη συνέχεια, συνδυάζουμε το plateau με τον αλγόριθμο penalty ο οποίος, όπως δηλώνει και το όνομά του, εισάγει κάποια ποινή (= επιπλέον βάρος) στις ακμές των εναλλακτικών που ήδη έχουν υπολογιστεί. Εκτός από αυτές τις δύο υλοποιήσεις, στόχος μας επίσης είναι να αξιολογήσουμε τις υποψήφιες εναλλακτικές που προκύπτουν ώστε να διαλέξουμε τις καλύτερες. Η υπεροχή της κάθε εναλλακτικής εξετάζεται με βάση κάποια συγκεκριμένα κριτήρια. Αυτά τα κριτήρια εξετάζουν την ποιότητα των plateaux, το ποσοστό των κοινών τμημάτων των εναλλακτικών, το μέσο μήκος τους συγκριτικά με το βέλτιστο, την τοπική βελτιστότητα. Αυτά τα κριτήρια επίσης ενσωματώνονται στις υλοποιήσεις μας σε C++. Τέλος, για να εξετάσουμε την αποδοτικότητα αυτών των αλγορίθμων, εκτελούμε πειράματα για διάφορες τιμές των παραμέτρων, σε οδικά δίκτυα μεγάλης κλίμακας, εξάγουμε στατιστικά αποτελέσματα και βγάζουμε συμπεράσματα.