Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Αλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το ανοιχτό πρόβλημα δρομολόγησης οχημάτων

Petridis Anastasios

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


URI: http://purl.tuc.gr/dl/dias/A3558959-8BF6-4AE4-BDCB-0BC1E61757FA
Έτος 2022
Τύπος Διπλωματική Εργασία
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά Αναστάσιος Πετρίδης, "Αλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το ανοιχτό πρόβλημα δρομολόγησης οχημάτων", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2022 https://doi.org/10.26233/heallink.tuc.91533
Εμφανίζεται στις Συλλογές

Περίληψη

Η παρούσα διπλωματική εργασία υλοποιείται με σκοπό την δημιουργία ενόςμεθευρετικού αλγορίθμου, για την επίλυση του ανοικτού προβλήματος δρομολόγησης οχημάτων (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). Τα αποτελέσματα του αλγορίθμου σε δεκατέσσερις παραλλαγές του προβλήματος, συγκρίνονται με αυτά της βιβλιογραφίας και σχολιάζεται η αποτελεσματικότητα του με βάση την ποιότητα των εξαγόμενων λύσεων, σε σχέση με τις καλύτερες ως τώρα ευρετικές μεθόδους σε πλαίσια απόδοσης, που έχουν δημοσιοποιηθεί.

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

Υπηρεσίες

Στατιστικά