Αλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το ανοιχτό πρόβλημα δρομολόγησης οχημάτωνΑλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το ανοιχτό πρόβλημα δρομολόγησης οχημάτωνVariable neighborhood search algorithm for the open vehicle routing problem
Διπλωματική Εργασία
Diploma Work
2022-02-222022elΗ παρούσα διπλωματική εργασία υλοποιείται με σκοπό την δημιουργία ενός
μεθευρετικού αλγορίθμου, για την επίλυση του ανοικτού προβλήματος δρομολόγησης οχημάτων (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). Τα αποτελέσματα του αλγορίθμου σε δεκατέσσερις παραλλαγές του προβλήματος, συγκρίνονται με αυτά της βιβλιογραφίας και σχολιάζεται η αποτελεσματικότητα του με βάση την ποιότητα των εξαγόμενων λύσεων, σε σχέση με τις καλύτερες ως τώρα ευρετικές μεθόδους σε πλαίσια απόδοσης, που έχουν δημοσιοποιηθεί.http://creativecommons.org/licenses/by/4.0/Πολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και ΔιοίκησηςPetridis_Anastasios_Dip_2022.pdfChania [Greece]Library of TUC2022-02-22application/pdf1.4 MBfree
Petridis Anastasios
Πετριδης Αναστασιος
Marinakis Ioannis
Μαρινακης Ιωαννης
Marinaki Magdalini
Μαρινακη Μαγδαληνη
Matsatsinis Nikolaos
Ματσατσινης Νικολαος
Kyriakakis Nikolaos-Antonios
Κυριακακης Νικολαος-Αντωνιος
Πολυτεχνείο Κρήτης
Technical University of Crete
Συνδυαστική βελτιστοποίηση
Ανοιχτό πρόβλημα δρομολόγησης οχημάτων
Μεθευρετικοί αλγόριθμοι