Αλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το ανοιχτό πρόβλημα δρομολόγησης οχημάτωνΑλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το ανοιχτό πρόβλημα δρομολόγησης οχημάτων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 Συνδυαστική βελτιστοποίηση Ανοιχτό πρόβλημα δρομολόγησης οχημάτων Μεθευρετικοί αλγόριθμοι