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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Almpanis Evangelos

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


URI: http://purl.tuc.gr/dl/dias/482AC284-37B9-4234-95CD-A3FC4A87C911
Έτος 2021
Τύπος Διπλωματική Εργασία
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά Ευάγγελος Αλμπάνης, "Μεθευρετικός αλγόριθμος αποδοχής κατωφλίου για το ανοιχτό πρόβλημα δρομολόγησης οχημάτων", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 https://doi.org/10.26233/heallink.tuc.89235
Εμφανίζεται στις Συλλογές

Περίληψη

Σε μια κοινωνία στην οποία ο ανταγωνισμός και οι απαιτήσεις των καταναλωτών συνεχώς αυξάνονται, η μελέτη της εφοδιαστικής αλυσίδας είναι πολύ σημαντική για μια επιχείρηση έτσι ώστε να είναι ανταγωνιστική, πιο αποδοτική και κερδοφόρα. Η παρούσα διπλωματική εργασία ασχολείται με το Ανοιχτό Πρόβλημα Δρομολόγησης Οχημάτων ή OVRP (Open Vehicle Routing Problem). Το συγκεκριμένο πρόβλημα βρίσκει εφαρμογή κυρίως σε εταιρίες στις οποίες δεν χρειάζεται τα οχήματα που χρησιμοποιούνται για τη διανομή να επιστρέφουν στην αποθήκη. Όλα τα οχήματα ξεκινούν από την αποθήκη και πρέπει να εξυπηρετήσουν όλους τους κόμβους (πελάτες) με τη ζήτηση του καθενός χωρίς να παραβιαστούν οι περιορισμοί χωρητικότητας των οχημάτων και μέγιστου χρόνου διαδρομής. Στόχος του προβλήματος είναι η εύρεση λύσης με όσο το δυνατόν λιγότερα οχήματα και την ελαχιστοποίηση της συνολικής απόστασης των διαδρομών. Για την εύρεση των αρχικών εφικτών λύσεων χρησιμοποιείται ο Αλγόριθμος Άπληστης Τυχαιοποιημένης Προσαρμοστικής Αναζήτησης γνωστός και ως GRASP (Greedy Randomized Adaptive Search Procedure). Στη συνέχεια για τη βελτίωση της αρχικής λύσης χρησιμοποιείται ο αλγόριθμος αποδοχής κατωφλίου (Threshold Accepted) σε συνδυασμό με τέσσερεις αλγόριθμους τοπικής αναζήτησης (1-0 relocate, 1-1 exchange, opt , swap). Ο αλγόριθμος εφαρμόζεται σε παραδείγματα της βιβλιογραφίας και γίνεται σύγκριση με τα βέλτιστα αποτελέσματα που έχουν δημοσιευτεί. Για την υλοποίηση του κώδικα χρησιμοποιήθηκε η προγραμματιστική γλώσσα Matlab.

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

Υπηρεσίες

Στατιστικά