Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Minopoulos Panagiotis-Minas

Full record

---

Summary

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

Available Files

Services