Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Trimas Dimitrios

Full record

---

Summary

Ο σκοπός αυτής της διπλωματικής εργασίας είναι η επίλυση ενός προβλήματος ταυτόχρονης δρομολόγησης οχημάτων και αποθεματοποίησης με χρήση του αλγορίθμου GRASP (Greedy Randomized Adaptive Search Procedure). Ουσιαστικά πρόκειται για ένα σύνθετο πρόβλημα βελτιστοποίησης κόστους και χρόνου, στο οποίο τον έλεγχο της ανατροφοδότησης, καθώς και της δρομολόγησης την έχει ο προμηθευτής και όχι ο πελάτης. Τέτοιου είδους προβλήματα συναντιόνται για παράδειγμα σε τροφοδοσίες πρατηρίων καυσίμων, καθώς είναι υψίστης σημασίας να μη μείνει χωρίς καύσιμα το πρατήριο αλλά ταυτόχρονα να μην είναι μονίμως πλήρες οι αποθήκες του. Στη συγκεκριμένη εργασία, για την αποθεματοποίηση δε χρησιμοποιείται κάποια συγκεκριμένη πολιτική αποθεματοποίησης. Επιπλέον, υπάρχει συγκεκριμένος αριθμός τροφοδοτικών οχημάτων καθώς και καθορισμένος χρόνος διεκπεραίωσης. Ο αλγόριθμος GRASP που χρησιμοποιείται είναι μια επαναληπτική διαδικασία, με σκοπό την εύρεση προσεγγιστικών λύσεων. Κάθε επανάληψη σημαίνει και πιθανή λύση, ενώ κάθε επανάληψη χωρίζεται σε δύο φάσεις. Στην πρώτη φάση κατασκευάζεται μια άπληστη τυχαιοποιημένη αρχική λύση μέσω χρήσης της “λίστας περιορισμού των υποψηφίων” (restricted canditate list) και στη δεύτερη φάση εφαρμόζεται τοπική αναζήτηση προκειμένου να βελτιωθεί η λύση. Όσον αφορά τη λίστα περιορισμού, περιέχει τους επόμενους πιθανούς προορισμούς από τους οποίους επιλέγεται ο επόμενος προορισμός με τυχαίο τρόπο. Τέλος, κρατάμε σαν λύση το καλύτερο αποτέλεσμα από όλες τις επαναλήψεις.

Available Files

Services