Ευρεστικοί αλγόριθμοι και εφαρμογές επίλυσης του προβλήματος περιπλανώμενου πωλητή και ανάθεση εργασιών

Abstract

Στη παρούσα πτυχιακή εργασία κάνουμε μια εισαγωγή στη θεωρία των Heuristic αλγορίθμων οι οποίοι βρίσκουν εφαρμογή σε πολλά απλά καθημερινά προβλήματα. Επειδή ο χρόνος που χρειάζεται να υπολογίσουμε τη βέλτιστη διαδρομή στο πρόβλημα του περιπλανώμενου πωλητή αλλά και άλλα προβλήματα διαδρομών (ένα κλασικό παράδειγμα είναι η περισυλλογή σκουπιδιών από τους κάδους απορριμμάτων), είναι απαγορευτικός ειδικά όταν μιλάμε για 15 συνδυασμούς και πάνω (η τάξη μεγέθους είναι ανάλογη του 2n), θα πρέπει να χαλαρώσουμε τους περιορισμούς μας και να υπολογίσουμε μόνο τις περιπτώσεις όπου θα μας δώσουν μια ικανοποιητική λύση. Η λύση δεν θα είναι ενδεχομένως βέλτιστη, αλλά θα είναι κοντά στη βέλτιστη με αμελητέα σχεδόν από τη βέλτιστη απόκλιση. Το πρόβλημα του περιπλανώμενου πωλητή είναι από τα πλέον γνωστά. Σύμφωνα με αυτό ζητάμε ποια είναι η ελάχιστη διαδρομή που θα πρέπει να ακολουθήσουμε ώστε να περάσουμε ξεκινώντας από τη πόλη αφετηρία (αρχικός κόμβος), να περάσουμε μια φορά από όλες τις πόλεις (όλους τους κόμβους του δικτύου) και όλα αυτά με το ελάχιστο κόστος. Τέλος το πρόβλημα του αλγορίθμου Branch and Bound βρίσκει εφαρμογή σε προβλήματα βελτιστοποίησης και συγκεκριμένα σε προβλήματα ανάθεσης εργασιών με το ελάχιστο δυνατό κόστος. Όπως και στο προηγούμενο πρόβλημα και σε αυτή τη περίπτωση περιγράφετε το πρόβλημα.

In this thesis we make an introduction to the theory of Heuristic algorithms that find application to many simple daily problems. Since the time we need to calculate the optimal route to the problem of the vendor but also other route problems (a classic example is garbage collection from garbage bins) is particularly prohibitive when talking about 15 combinations and above (the order of magnitude is proportional of 2n), we should relax our constraints and only count the cases where they will give us a satisfactory solution. The solution will probably not be optimal, but it will be close to optimal with almost negligible optimal deviation. The problem of TSP is one of the most known. According to this, we ask for the minimum route we should take to get started from the starting point of the city (starting node), passing once from all the cities (all nodes in the network) and all at the minimum cost. Finally, the problem of the Branch and Bound algorithm applies to optimization problems and in particular to problems of assigning work at the lowest possible cost. Just as in the previous problem and in this case you describe the problem.