Συντάχθηκε 17-02-2022 11:38
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 18/02/2022 12:00
Λήξη: 18/02/2022 13:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
ΣΧΟΛΗ ΜΗΧΑΝΙΚΩΝ ΠΑΡΑΓΩΓΗΣ ΚΑΙ ΔΙΟΙΚΗΣΗΣ
Ονοματεπώνυμο: Αναστάσιος Πετρίδης
Αριθμός Μητρώου: 2016010023
Θέμα
Τίτλος στα Ελληνικά: Αλγόριθμος Μεταβλητής Γειτονιάς Αναζήτησης για το Ανοιχτό Πρόβλημα Δρομολόγησης Οχημάτων
Τίτλος στα Αγγλικά: Variable Neighborhood Search Algorithm for the Open Vehicle Routing Problem
Επιτροπή:
Επιβλέπων: Μαρινάκης Ιωάννης, Αν. Καθηγητής
Πρώτο Μέλος: Μαρινάκη Μαγδαληνή, Ε.ΔΙ.Π
Δεύτερο Μέλος: Ματσατσίνης Νικόλαος, Καθηγητής
Περίληψη της εργασίας στα Ελληνικά: Η παρούσα διπλωματική εργασία υλοποιείται με σκοπό την δημιουργία ενός μεθευρετικού αλγορίθμου, για την επίλυση του ανοικτού προβλήματος δρομολόγησης οχημάτων (Open Vehicle Routing Problem). Στη συγκεκριμένη παραλλαγή του διαδεδομένου πλέον στο χώρο της συνδυαστικής βελτιστοποίησης προβλήματος δρομολόγησης οχημάτων (Vehicle Routing Problem), σκοπό αποτελεί αρχικά η ελαχιστοποίηση του αριθμού των οχημάτων διανομής και της συνολικής απόστασης που διανύεται από αυτά. Με αφετηρία την αποθήκη, κάθε όχημα επισκέπτεται και εξυπηρετεί ένα αριθμό διαφορετικών πελατών χωρίς να επιστρέφει σε αυτή μετά το πέρας της διαδρομής του. Οι περιορισμοί του προβλήματος ορίζουν πως η χωρητικότητα των οχημάτων δεν πρέπει να παραβιάζεται από συνολική ζήτηση που καλύπτεται από αυτά, ενώ παράλληλα η επιμέρους ζήτηση κάθε πελάτη να καλύπτεται πλήρως από ένα μόνο όχημα. Τέλος, σε διαφορετικές εκδοχές του προβλήματος, εφαρμόζεται άνω φράγμα στο συνολικό χρόνο της διαδρομής των οχημάτων.
Η δημιουργία των αρχικών λύσεων πραγματοποιείται με τη χρήση του αλγορίθμου των εξοικονομήσεων των Clarke & Wright (CW), ενώ η βελτιστοποίηση τους, μέσω μεθευρετικής διαδικασίας στην οποία εφαρμόζεται ένας αλγόριθμος μεταβλητής γειτονιάς αναζήτησης (VNS). Η δημιουργία γειτονικών λύσεων πραγματοποιείται με τη χρήση αλγορίθμων τοπικής αναζήτησης (2-Opt, 1-1 Exchange, 1-0 Relocate, 2-1 Exchange, 2-2 Exchange, 2-0 Relocate, 3-3 Exchange). Τα αποτελέσματα του αλγορίθμου σε δεκατέσσερις παραλλαγές του προβλήματος, συγκρίνονται με αυτά της βιβλιογραφίας και σχολιάζεται η αποτελεσματικότητα του με βάση την ποιότητα των εξαγόμενων λύσεων, σε σχέση με τις καλύτερες ως τώρα ευρετικές μεθόδους σε πλαίσια απόδοσης, που έχουν δημοσιοποιηθεί.
Ημερομηνία Εξέτασης
Ημέρα/Μήνας/Έτος: Παρασκευή 18/2/2022
Ώρα: 12:00
Χώρος Εξέτασης
Αίθουσα: https://tuc-gr.zoom.us/j/95141018329?pwd=RjdJcXdlRkc4S2dPbmZ5OEhUSE5HQT09
Meeting ID: 951 4101 8329
Password: 602335
Κτίριο: ………………………………………
