Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Greedy randomized adaptive search procedure for the time dependent vehicle routing problem

Nasoulis Stamatios

Full record

---

Summary

Τα τελευταία χρόνια παρατηρείται έντονα η τάση των επιχειρήσεων να επενδύσουν στη Διαχείριση της Εφοδιαστικής Αλυσίδας. Πράγματι, η Διαχείριση της Εφοδιαστικής Αλυσίδας, ή εν συντομία τα Logistics, αποτελούν πλέον βασικό πυλώνα στον στρατηγικό σχεδιασμό των επιχειρήσεων κι όχι άδικα. Η βελτιστοποίηση των μεταφορών και των αποθεμάτων έχει πάψει να θεωρείται απλώς ένα ανταγωνιστικό πλεονέκτημα, αφού πλέον αποτελεί επιτακτική ανάγκη για τη βιωσιμότητα των επιχειρήσεων. Η παρούσα διπλωματική εργασία πραγματεύεται ένα από τα σημαντικότερα προβλήματα της Εφοδιαστικής Αλυσίδας, αυτό της δρομολόγησης οχημάτων. Πιο συγκεκριμένα, πρόκειται για τοΧρονικώς Εξαρτώμενο Πρόβλημα Δρομολόγησης Οχημάτων (Time Dependent Vehicle Routing Problem), το οποίο προσπαθεί να προσεγγίσει ρεαλιστικά μία πραγματική κατάσταση με στόχο τη βελτιστοποίηση του κόστους. Με την έννοια πραγματική κατάσταση νοούνται όλες εκείνες οι παράμετροι που ενδέχεται να επηρεάσουν τον τρόπο και τους χρόνους των μεταφορών, όπως για παράδειγμα η κυκλοφοριακή συμφόρηση ή η κατάσταση του οδικού δικτύου. Γι' αυτό, οι χρόνοι μετάβασης εξαρτώνται από τη χρονική στιγμή της ημέρας κατά την οποία πραγματοποιείται μία μεταφορά, καθώς η μέρα χωρίζεται στα κατάλληλα χρονικά διαστήματα. Έπειτα, ο αλγόριθμος, που χρησιμοποιείται για την επίλυση του προβλήματος, είναι ο GRASP (Greedy Randomized Adaptive Search Procedure). Ο GRASP πρόκειται για μία επαναληπτική διαδικασία, η οποία αποτελείται από δύο φάσεις. Στην πρώτη φάση κατασκευάζεται μία πιθανή λύση μέσω μίας τυχαιοποιημένης συνάρτησης απληστίας. Η συνάρτηση, αυτή, σε κάθε επανάληψη επιλέγει τυχαία τον επόμενο πελάτη προς εξυπηρέτηση μέσα από μία λίστα περιορισμένων υποψηφίων (Restricted Candidate List). Στη δεύτερη φάση, η λύση που κατασκευάστηκε, ακολουθεί μία διαδικασία τοπικής αναζήτησης, προκειμένου να βελτιωθεί το συνολικό της κόστος. Εν τέλει, συγκρίνοντας όλες τις πιθανές λύσεις που κατασκευάστηκαν, προκύπτει το τελικό αποτέλεσμα. Δηλαδή, η βέλτιστη λύση μαζί με το αντίστοιχο κόστος.

Available Files

Services