Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

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

Kokkinaki Maria

Full record


URI: http://purl.tuc.gr/dl/dias/24DFBCFE-925B-4ED2-B923-F6A97F568AC0
Year 2020
Type of Item Diploma Work
License
Details
Bibliographic Citation Μαρία Κοκκινάκη, "Μεθευρετικός αλγόριθμος για το πρόβλημα δρομολόγησης οχημάτων με παράδοση και παραλαβή προϊόντων και χρονικούς περιορισμούς ", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2020 https://doi.org/10.26233/heallink.tuc.86255
Appears in Collections

Summary

Στη παρούσα διπλωματική εργασία επιλύεται το πρόβλημα δρομολόγησης οχημάτων με παράδοση και παραλαβή και χρονικούς περιορισμούς (Vehicle Routing Problem with Pickup, Delivery and Time Windows). Δεδομένου ενός αριθμού πελατών που πρέπει να εξυπηρετηθούν και ενός συγκεκριμένου πλήθους οχημάτων τα οποία είναι διαθέσιμα ζητείται η σχεδίαση διαδρομών καθώς και η ελαχιστοποίηση του κόστους των διαδρομών υπό συγκεκριμένους περιορισμούς. Τα οχήματα θα ξεκινάνε από την αποθήκη και μετά το πέρας της κάθε διαδρομής θα επιστρέφουν σε αυτή. Κύρια μέθοδος επίλυσης του προβλήματος αποτελεί η διαδικασία τυχαιοποιημένης άπληστης τυχαιοποιημένης προσαρμοστικής αναζήτησης (Greedy Randomized Adaptive SearchProcedure (GRASP)), η οποία χρησιμοποιείται για την εύρεση ενός συνόλου αρχικών λύσεων. Μια δεύτερη μέθοδος δημιουργίας αρχικών λύσεων, η οποία θα χρησιμοποιηθεί για τη σύγκριση των αποτελεσμάτων της με τη μέθοδο GRASP, είναι η μέθοδος του πλησιέστερου γείτονα. Για την βελτίωση των αρχικών λύσεων χρησιμοποιήθηκαν οι αλγόριθμοι τοπικής αναζήτησης (1-0 relocate, 1-1 exchange, 2-0 opt). Το πρόβλημα επιλύθηκε σε περιβάλλον MATLAB και εφαρμόστηκε σε παραδείγματα με γνωστό αριθμό διαδρομών και βέλτιστο κόστος διαδρομών. Τέλος παρουσιάζονται συγκριτικοί πίνακες των δύο μεθόδων με τα βέλτιστα αποτελέσματα καθώς και γραφικές αναπαραστάσεις των καλύτερων λύσεων.

Available Files

Services

Statistics