Σύγκριση διαφορετικών μεθόδων επίλυσης του προβλήματος του Πλανόδιου Πωλητή (Travelling Salesman Problem - TSP): βελτιστοποίηση διαδρομών απορριμματοφόρων δήμου Μυτιλήνης

Abstract

Στόχος της εκπονηθείσας εργασίας, είναι η επίλυση του «Προβλήματος του Πλανόδιου Πωλητή (Travelling Salesman Problem -TSP)», μέσω της δημιουργίας κωδίκων στη γλώσσα προγραμματισμού Pyhton με τέσσερεις διαφορετικές μεθόδους - αλγορίθμους [Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), Ant Colony (ACO)], για την αποκομιδή των αστικών απορριμμάτων από τους κάδους του Δήμου Μυτιλήνης. Η σύγκριση των αποτελεσμάτων των ως άνω μεθόδων σε ακρίβεια και χρόνο εκτέλεσης, καθώς και η δημιουργία νέου κώδικα, ο οποίος επιλύει το TSP για τις διαδρομές των απορριμματοφόρων στον προαναφερθέντα Δήμο. Τα δεδομένα που χρησιμοποιήθηκαν με στόχο την σύγκριση των αλγορίθμων είναι δύο αρχεία με πραγματικές συντεταγμένες. Το πρώτο αρχείο αποτελείται από πόλεις – πρωτεύουσες χωρών ανα τον κόσμο, ενώ το δεύτερο από τους κάδους αστικών απορριμμάτων και τον Σταθμό Μεταφόρτωσης Απορριμμάτων (ΣΜΑ) του Δήμου Μυτιλήνης. Επιπροσθέτως, ο τελευταίος κώδικας, ο οποίος επιλύει το TSP για τις διαδρομές των απορριμματοφόρων, έχει δημιουργηθεί με βάση τον Γραμμικό Προγραμματισμό και χρησιμοποιεί ως δεδομένα τα εξής τρία αρχεία: α) το Οδικό Δίκτυο, β) τους κάδους και γ) τον ΣΜΑ του Δήμου Μυτιλήνης. Όλα τα αποτελέσματα της εργασίας και οι συγκρίσεις των αλγορίθμων, παρουσιάζονται με πίνακες και γραφήματα που προέκυψαν από τους δημιουργηθέντες κώδικες. Τέλος, τα αποτελέσματα της βελτιστοποίησης απεικονίζονται σε χάρτες οι οποίοι δημιουργήθηκαν στο λογισμικό ArcGIS.