Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Variable neighborhood search algorithm for the distance-constrained vehicle routing problem

Aggeli Vasiliki

Full record

---

Summary

Λόγω της παγκοσμιοποίησης και των διαρκώς αυξανόμενων απαιτήσεων των πελατών, η βελτίωση της Εφοδιαστικής Αλυσίδας αποτελεί καθοριστικό παράγοντα για την ανταγωνιστικότητα ακόμα και για τη βιωσιμότητα της κάθε επιχείρησης. Ενας από τους στόχους της Εφοδιαστικής είναι η μείωση του κόστους των μεταφορών των προϊόντων και των αποθεμάτων. Η συγκεκριμένη διπλωματική εργασία έχει σαν αντικείμενο το πρόβλημα δρομολόγησης οχημάτων σε περιορισμένη απόσταση (Distance Constrained Vehicle Routing Problem). Ξεκινώντας από μία αποθήκη τα οχήματα μεταφέρουν προϊόντα στους πελάτες πηγαίνοντας κάθε φορά στον πλησιέστερο, ώστε να μην υπάρχει χαμένος χρόνος. Για την περιγραφή του προβλήματος ορίζονται κατάλληλα οι απαραίτητοι περιορισμοί για τον αριθμό και τις τοποθεσίες των πελατών, τον συνολικό χρόνο που έχει τη δυνατότητα να δαπανήσει το φορτηγό στο δρόμο, καθώς και τον χρόνο εξυπηρέτησης του κάθε πελάτη. Αρχικά υλοποιείται ένας απλός αλγόριθμος απληστίας από τον οποίο προκύπτει μία αρχική εφικτή λύση που ικανοποιεί τους περιορισμούς. Στη συνέχεια χρησιμοποιείται ο αλγόριθμος Μεταβλητής Γειτονιάς Αναζήτης (Variable Neighborhood Search Algorithm) με σκοπό τη βελτίωση της λύσης. Γίνεται διερεύνηση της κατάλληλης γειτονιάς αναζήτησης με την εφαρμογή μεθόδων τοπικής αναζήτησης (1-1 exchange, 1-0 relocate, 2-opt). Στην εργασία παρουσιάζεται η υλοποίηση του VNS αλγορίθμου, καθώς και τα αποτελέσματα από τη χρήση των αλγορίθμων. Για την ανάπτυξη του αλγορίθμου χρησιμοποιήθηκε το προγραμματιστικό περιβάλλον της MATLAB. 

Available Files

Services