Έρευνα και συγκριτική μελέτη αλγορίθμων δρομολόγησης για οχήματα με υλοποίηση σε εφαρμογή χαρτών

Abstract

Η παρούσα εργασία ασχολείται με τη συγκριτική αξιολόγηση αλγορίθμων δρομολόγησης σε πραγματικά δεδομένα οδικών δικτύων, αξιοποιώντας το OpenStreetMap και τη βιβλιοθήκη GraphHopper. Αναπτύχθηκε μια ολοκληρωμένη εφαρμογή, η οποία επιτρέπει τον καθορισμό διαφορετικών σεναρίων δρομολόγησης, την επιλογή οχημάτων και προφίλ βελτιστοποίησης, καθώς και την εκτέλεση πολλαπλών αλγορίθμων (Dijkstra, A*, Bidirectional Dijkstra, Bidirectional A*). Η αξιολόγηση βασίστηκε σε μετρικές όπως ο χρόνος υπολογισμού, το μήκος και ο χρόνος διαδρομής, καθώς και ο αριθμός εξερευνημένων κόμβων. Τα αποτελέσματα καταδεικνύουν τη σαφή υπεροχή των αλγορίθμων που κάνουν χρήση ευριστικών συναρτήσεων και των διπλής κατεύθυνσης εκδόσεων τους σε σενάρια μεγάλης κλίμακας ή σύνθετης δρομολόγησης, ενώ αναδεικνύουν παράλληλα τις διαφοροποιήσεις μεταξύ διαφορετικών τύπων οχημάτων και κριτηρίων βελτιστοποίησης. Η εργασία συμβάλλει στην κατανόηση των πρακτικών και θεωρητικών πτυχών της αποδοτικότητας των αλγορίθμων δρομολόγησης και προσφέρει ένα επεκτάσιμο εργαλείο πειραματισμού για μελλοντική έρευνα.