Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/AA1710F1-125E-4304-8690-63623EC614CD | ||
| Year | 2023 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Panagiotis-Minas Minopoulos, "Traveling salesman problem for capacitated boat with pickups, deliveries and draft limits", Diploma Work, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2023 https://doi.org/10.26233/heallink.tuc.96672 | ||
| Appears in Collections |
Στην παρούσα διπλωματική εξετάζεται η βελτιστοποίηση του προβλήματοςτου πλανόδιου πωλητή με παραδώσεις και παραλαβές. Το πρόβλημααναζητάει την βέλτιστη διαδρομή ενός πλοίου με φορτίο που καλείται ναεπισκεφτεί όλα τα λιμάνια και να επιστρέψει στο αρχικό λιμάνι άδειο, κάθε λιμάνιέχει συγκεκριμένα βυθίσματα. Στο σύνολο των λιμανιών υπάρχουν κάποια ταοποία δίνουν ποσότητες αγαθών και άλλα τα οποία ζητάνε αυτές τις ποσότητεςαπό τα συγκεκριμένα λιμάνια, τα πρώτα είναι ο σταθμός προέλευσης και ταδεύτερα ο προορισμός. Μια αναγκαία συνθήκη είναι τα λιμάνια προέλευσης ναεπισκέπτονται πρώτα από τα αντίστοιχα προορισμού. Η χωρητικότητα τουπλοίου είναι περιορισμένη και δεν πρέπει να ξεπεραστεί από το παρόν φορτίοκαθ’ όλη την διάρκεια της διαδρομής. Χρησιμοποιήθηκαν οι μεθευρετικοίαλγόριθμοι ant colony optimization και ant system min max καθώς και οιμέθοδοι τοπικής αναζήτησης 2 opt και 3 opt για έναν σταθερό αριθμόεπαναλήψεων και μυρμηγκιών. Σε ένα πλήθος δεδομένων εφαρμόστηκαν οιπαραπάνω αλγόριθμοι και μέθοδοι έτσι ώστε να διερευνηθεί ποιος είναι οκαταλληλότερος. Στα περισσότερα παραδείγματα ο αλγόριθμος ant system minmax σε συνδυασμό και με τις δυο μεθόδους τοπικής αναζήτησης είχε τακαλύτερα αποτελέσματα, όμως οι χρόνοι εκτέλεσης του ήταν αισθητάμεγαλύτεροι από τους υπόλοιπους αλγόριθμους και οι υπολογιστικές τουανάγκες απαιτητικές.
Copyright © DIAS 2013
