Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Traveling salesman problem for capacitated boat with pickups, deliveries and draft limits

Minopoulos Panagiotis-Minas

Full record


URI: http://purl.tuc.gr/dl/dias/AA1710F1-125E-4304-8690-63623EC614CD
Year 2023
Type of Item Diploma Work
License
Details
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

Summary

Στην παρούσα διπλωματική εξετάζεται η βελτιστοποίηση του προβλήματοςτου πλανόδιου πωλητή με παραδώσεις και παραλαβές. Το πρόβλημααναζητάει την βέλτιστη διαδρομή ενός πλοίου με φορτίο που καλείται ναεπισκεφτεί όλα τα λιμάνια και να επιστρέψει στο αρχικό λιμάνι άδειο, κάθε λιμάνιέχει συγκεκριμένα βυθίσματα. Στο σύνολο των λιμανιών υπάρχουν κάποια ταοποία δίνουν ποσότητες αγαθών και άλλα τα οποία ζητάνε αυτές τις ποσότητεςαπό τα συγκεκριμένα λιμάνια, τα πρώτα είναι ο σταθμός προέλευσης και ταδεύτερα ο προορισμός. Μια αναγκαία συνθήκη είναι τα λιμάνια προέλευσης ναεπισκέπτονται πρώτα από τα αντίστοιχα προορισμού. Η χωρητικότητα τουπλοίου είναι περιορισμένη και δεν πρέπει να ξεπεραστεί από το παρόν φορτίοκαθ’ όλη την διάρκεια της διαδρομής. Χρησιμοποιήθηκαν οι μεθευρετικοίαλγόριθμοι ant colony optimization και ant system min max καθώς και οιμέθοδοι τοπικής αναζήτησης 2 opt και 3 opt για έναν σταθερό αριθμόεπαναλήψεων και μυρμηγκιών. Σε ένα πλήθος δεδομένων εφαρμόστηκαν οιπαραπάνω αλγόριθμοι και μέθοδοι έτσι ώστε να διερευνηθεί ποιος είναι οκαταλληλότερος. Στα περισσότερα παραδείγματα ο αλγόριθμος ant system minmax σε συνδυασμό και με τις δυο μεθόδους τοπικής αναζήτησης είχε τακαλύτερα αποτελέσματα, όμως οι χρόνοι εκτέλεσης του ήταν αισθητάμεγαλύτεροι από τους υπόλοιπους αλγόριθμους και οι υπολογιστικές τουανάγκες απαιτητικές.

Available Files

Services

Statistics