Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

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

Minopoulos Panagiotis-Minas

Πλήρης Εγγραφή

---

Περίληψη

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

Διαθέσιμα αρχεία

Υπηρεσίες