Please use this identifier to cite or link to this item:
Title: Προσεγγίζοντας το πρόβλημα του πλανόδιου πωλητή
Authors: Στυλιανού, Νικόλαος
Issue Date: 2013-10-11
Keywords: Πρόβλημα πλανόδιου πωλητή
Keywords (translated): Travelling Salesman Problem (TSP)
Abstract: Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος. Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας και επιστρέφοντας στην αρχική πόλη. Το κύριο πρόβλημά του είναι να βρει τη συντομότερη διαδρομή. Παρουσιάζουμε μια αυτόνομη εισαγωγή σε αλγοριθμικές και υπολογιστικές απόψεις του προβλήματος μαζί με τις θεωρητικές απαραίτητες προϋποθέσεις τους από την σκοπιά της Επιχειρησιακής Έρευνας. Η διπλωματική αποσκοπεί να παρουσιάσει τις διαδικασίες επίλυσης του Προβλήματος του Πλανόδιου Πωλητή ανάλογα με το μέγεθος και τη δομή του. Θεωρητικά αποτελέσματα παρουσιάζονται σε μορφή που να καθιστούν σαφή τη σημασία τους στο σχεδιασμό των προσεγγιστικών αλγόριθμων για αποδεδειγμένα καλές ή/και βέλτιστες λύσεις του Προβλήματος.
Abstract (translated): In this thesis, at short, we present the Travelling Salesman Problem with approximations algorithms, some practical applications and related problems of the main problem. A travelling salesman wants to visit each of a set of towns exactly once starting from and returning to his home town. One of his problems is to find the shortest such trip. We present a self-contained introduction into algorithmic and computational aspects of the TSP along with their theoretical prerequisites as seen from the point of view of an operations researcher who wants to solve practical instances. This thesis is intended to be a guideline of the reader confronted with the question of how to attack a TSP instance depending on its size, its structural properties. Theoretical results are presented in a form which make clear their importance in the design of algorithms for approximate but provably good, and optimal solutions of the TSP.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
diplomatiki_Nikolas_Stylianou.pdf1.87 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.