Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή

• Main Author: Στυλιανού, Νικόλαος
• Other Authors: Τσάντας, Νικόλαος
• Format: Thesis
• Language: Greek
• Published: 2013
• Subjects: Πρόβλημα πλανόδιου πωλητή; Travelling Salesman Problem (TSP); 519.64

Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος. Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας και επιστρέφοντας στην αρχική πόλη. Το κύριο πρόβλημά του είναι να βρει τη συντομότερη διαδρομή. Παρουσιάζουμε μια αυτόνομη εισαγωγή σε αλγοριθμικές και υπολογιστικές απόψεις του προβλήματος μαζί με τις θεωρητικές απαραίτητες προϋποθέσεις τους από την σκοπιά της Επιχειρησιακής Έρευνας. Η διπλωματική αποσκοπεί να παρουσιάσει τις διαδικασίες επίλυσης του Προβλήματος του Πλανόδιου Πωλητή ανάλογα με το μέγεθος και τη δομή του. Θεωρητικά αποτελέσματα παρουσιάζονται σε μορφή που να καθιστούν σαφή τη σημασία τους στο σχεδιασμό των προσεγγιστικών αλγόριθμων για αποδεδειγμένα καλές ή/και βέλτιστες λύσεις του Προβλήματος.