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

Abstract

Στην εργασία αυτή παρουσιάζεται το πρόβλημα του Περιοδεύοντος Πωλητή (Traveling Sales man Problem, TSP) και οι προσεγγιστικοί αλγόριθμοι επίλυσης του. Το πρόβλημα συνίσταται στην προσπάθεια εύρεσης της οικονομικότερης – άριστης περιοδείας, που πρέπει να ακολουθήσει ένας περιοδεύων πωλητής, ώστε να επισκεφθεί κάθε πόλη, ενός συνόλου πόλεων, ακριβώς μια φορά και να επιστέψει στην αρχική πόλη. Η επίλυση του προβλήματος έχει αποδειχτεί πολύ δύσκολη και το πρόβλημα κατηγοριοποιείται στα NP-Πλήρη (Np-Complete) προβλήματα, καθώς για μεγάλο αριθμό πόλεων ο χρόνος που απαιτείται για όλους τους υπολογισμούς είναι κυριολεκτικά ασύλληπτος. Η εργασία ξεκινά με την ιστορική παρουσίαση του προβλήματος και των εφαρμογών του. Ακολουθεί παρουσίαση της πολυπλοκότητας του προβλήματος και των διάφορων παραλλαγών του. Στην συνέχεια παρουσιάζονται οι ακριβείς (exact) αλγόριθμοι επίλυσης του TSP οι οποίοι υπολογίζουν πάντα την άριστη λύση του προβλήματος αλλά αποδίδουν ικανοποιητικά μόνο σε προβλήματα λίγων πόλεων. Κατόπιν παρουσιάζονται οι ευρετικοί (heuristics) αλγόριθμοι, οι οποίοι δίνουν αποδεδειγμένα λύσεις που προσεγγίζουν την άριστη σε πολύ μικρότερο χρόνο και ανάλογα με την τεχνική που χρησιμοποιούν κατηγοριοποιούνται σε Κατασκευαστικούς και Βελτιωτικούς. Στη συνέχεια παρουσιάζονται οι προσεγγιστικοί αλγόριθμοι σταθερού λόγου προσέγγισης και τέλος τα Προσεγγιστικά Σχήματα Πολυωνυμικού Χρόνου (Polynomial Time Approximation Scheme, PTAS) για το πρόβλημα του Ευκλείδειου-TSP.