National and Kapodistrian University of Athens
Μελέτη και αξιολόγηση αλγορίθμων δρομολόγησης βασισμένων σε Πίνακες Αποστάσεων
Abstract
dc:descriptionΣτην παρούσα εργασία μελετάται η ανάπτυξη και αξιολόγηση ενός συστήματος δημιουργίας δρομολογίων για διανομείς, βασισμένου στο πρόβλημα του πλανόδιου πωλητή (TSP). Στόχος είναι η εύρεση αποδοτικών διαδρομών μεταξύ πολλών σημείων, με χρήση πίνακα διαδρο-μών (route matrix). Υλοποιήθηκαν διάφοροι απλοί ευρετικοί αλγόριθμοι επίλυσης του TSP και συγκρίθηκαν μεταξύ τους ως προς την συνολική απόσταση της διαδρομής και το χρόνο εκτέλεσης. Επιπλέον, αξιολογήθηκε η επίδοση των αλγορίθμων με δύο τύπους route matrix: ευκλείδειων αποστάσεων και βασισμένο σε πραγματικά δεδομένα μέσω του συστήματος GraphHopper. Τα αποτελέσματα έδειξαν ότι ο αλγόριθμος “nearest neighbor to last” με ευκλείδειες αποστάσεις αποτελεί την πιο αποδοτική λύση, ειδικά όταν απαιτείται γρήγορη δημιουργία του πίνακα διαδρομών.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Γκίκας Αναστάσιος
- Gkikas Anastasios
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:3476022