Institutional Repository
Technical University of Crete
EN  |  EL

Search

Browse

My Space

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

Almpanis Evangelos

Full record


URI: http://purl.tuc.gr/dl/dias/482AC284-37B9-4234-95CD-A3FC4A87C911
Year 2021
Type of Item Diploma Work
License
Details
Bibliographic Citation Ευάγγελος Αλμπάνης, "Μεθευρετικός αλγόριθμος αποδοχής κατωφλίου για το ανοιχτό πρόβλημα δρομολόγησης οχημάτων", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 https://doi.org/10.26233/heallink.tuc.89235
Appears in Collections

Summary

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

Available Files

Services

Statistics