Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

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

Kokkinaki Maria

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

---

Περίληψη

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

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

Υπηρεσίες