Μελέτη νέου αλγόριθμου για την επίλυση του «προβλήματος του περιοδεύοντος πωλητή» και η προσέγγιση του πολυκριτηριακού προβλήματος - Βαρελλάς-Ουζουνόπουλος, Ιωάννης (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Χημικών Μηχανικών, 2014)
Η παρούσα διπλωματική καταρχήν έχει ως σκοπό την εφαρμογή μιας νέας μοντελοποίησης στο «πρόβλημα του περιοδεύοντος πωλητή» (TSP). Επίσης μελετάται η πολυκριτηριακή εκδοχή του προβλήματος χρησιμοποιώντας τη μέθοδο Augmecon. Στην πρώτη ενότητα λοιπόν εξετάζεται ο καινοτόμος αλγόριθμος των Vassiliadis S.V., Pogiatzis T. από τη Σχολή Χημικών Μηχανικών & Βιοτεχνολογίας του Πανεπιστημίου του Cambridge. Επιδίωξαν την ανάπτυξη της μοντελοποίησης των Millar H., Cyrus P., που ανήκει στην κατηγορία ακέραιου προγραμματισμού (Integer Programming IP), μειώνοντας αισθητά τους περιορισμούς της από Ο(N3) σε Ο(Ν2log2N). Αυτό επετεύχθη με την εισαγωγή, για πρώτη φορά, ενός δυαδικού δέντρου απεικόνισης των θέσεων στη διαδρομή. Για κάθε θέση της κλειστής διαδρομής αντιστοιχεί μια δυαδική αλληλουχία μέσω της οποίας γίνεται η κατανομή κάθε πόλης στην αντίστοιχη θέση της διαδρομής. Εν συνεχεία εφαρμόζεται η μοντελοποίηση αυτή, καθώς επίσης και οι αλγόριθμοι των Millar H., Cyrus P., και δύο βασικές μοντελοποιήσεις των Miller C.E., Tucker A.W. και Zemlin R.A (MTZ) και των Gravish B., Graves S.C (GG), για την επίλυση μονοκριτηριακών προβλημάτων TSP ώστε να γίνει σύγκριση ανάμεσα στην ταχύτητα επίλυσης του TSP από κάθε αλγόριθμο. Ακολούθως εξετάζεται η κατά Lagrange αποσύνθεση της νέας μοντελοποίησης, η βασική αρχή της οποίας είναι η διαίρεση του προβλήματος σε μικρότερα προβλήματα και η επίλυσή τους ξεχωριστά, με σκοπό να εξάγουμε ένα κάτω όριο που προσεγγίζει τη λύση του προβλήματος αντί να επιλύσουμε το συνολικό πρόβλημα ερευνώντας τη βέλτιστη λύση, που απαιτεί πολύ μεγαλύτερο χρόνο επίλυσης. Στη δεύτερη ενότητα μελετάται η εισαγωγή ενός δεύτερου πίνακα κόστους στο πρόβλημα του περιοδεύοντος πωλητή, κάνοντας το πρόβλημα πολυκριτηριακό, με δυο δηλαδή αντικειμενικές συναρτήσεις αντί για μια. Αναζητείται λοιπόν όχι η βέλτιστη λύση, αλλά η κατά Pareto άριστη λύση. Εξετάζεται η μέθοδος Augmecon των Mavrotas, Florios από τη Σχολή Χημικών Μηχανικών του ΕΜΠ η οποία ανήκει στις «μη εξαντλητικές μεθόδους» και μάλιστα είναι «μέθοδος περιορισμών», δηλαδή βελτιστοποιείται η μια αντικειμενική συνάρτηση ενώ η άλλη συμμετέχει ως περιορισμός. Τέλος προσαρμόζονται οι μοντελοποιήσεις GG και ΜΤΖ στην Augmecon για την επίλυση πολυκριτηριακών TSP και την εύρεση των καμπυλών Pareto καθώς και τη σύγκριση του χρόνου επίλυσης ανάμεσα σε GG και ΜΤΖ. Η επίλυση των μοντέλων έγινε με τον επιλυτή CPLEX και χρησιμοποιήθηκε για αυτό το σκοπό το λογισμικό GAMS.