Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Kotzabasi Danai

Full record

---

Summary

Η συγκεκριμένη διπλωματική εργασία έχει ως αντικείμενο την υλοποίηση κάποιων μεθόδων δρομολόγησης οχημάτων που χρησιμοποιούνται για τη διανομή των προϊόντων-αγαθών μιας εφοδιαστικής αλυσίδας. Οι μέθοδοι που χρησιμοποιούνται είναι οι κατασκευαστικοί αλγόριθμοι: Άπληστη τυχαιοποιημένη προσαρμοστική αναζήτηση (greedy randomized adaptive procedure ή GRASP) και πλησιέστερος γείτονας (nearest neighbor). Στόχος και των δύο μεθόδων είναι η κατασκευή μιας διαδρομής τέτοιας ώστε να ικανοποιούνται οι ανάγκες των πελατών που ορίζει κάθε φορά το πρόβλημα και να ελαχιστοποιείται το κόστος που προκύπτει από αυτή. Ταυτόχρονα, λαμβάνονται υπόψη περιορισμοί που αφορούν τη δεδομένη χωρητικότητα των οχημάτων και τον προκαθορισμένο χρόνο που κάθε όχημα επιτρέπεται να δαπανήσει στην εξυπηρέτηση. Ακόμα, για το καθορισμό της επιθυμητής διαδρομής δίνονται ως δεδομένα το πλήθος και οι τοποθεσίες των πελατών, η ζήτηση κάθε πελάτη και ο χρόνος εξυπηρέτησής του. Με τη μέθοδο του πλησιέστερου γείτονα, η επιλογή της σειράς εξυπηρέτησης των πελατών καθορίζεται από την απόσταση που απέχουν κάθε φορά οι πελάτες από το όχημα και επιλέγεται αυτός με την ελάχιστη, εφόσον φυσικά τηρούνται οι περιορισμοί που προαναφέρθηκαν. Με τη GRASP, η επιλογή των πελατών γίνεται τυχαία ανάμεσα σε ένα αριθμό πελατών που απέχουν λιγότερο από τη τρέχουσα θέση του οχήματος σε σχέση με τους υπόλοιπους χωρίς απαραίτητα να επιλέγεται ο πλησιέστερος. Και για τους δύο αλγόριθμους ισχύει ότι ένα όχημα ξεκινάει από την αποθήκη, επισκέπτεται τους πελάτες κατά το τρόπο που ορίζει κάθε φορά η μέθοδος, ελέγχοντας ταυτόχρονα τους περιορισμούς. Εάν αυτοί παραβιάζονται τότε το όχημα επιστρέφει στην αποθήκη και ένα νέο όχημα συνεχίζει την εξυπηρέτηση, ενώ οι αλγόριθμοι τερματίζουν όταν όλοι οι πελάτες έχουν εξυπηρετηθεί και τελικά το όχημα επιστρέφει στην αποθήκη. Έπειτα από τη κατασκευή των διαδρομών ακολουθεί η ανταλλαγή δύο τυχαίων πελατών μέσω της μεθόδου 1-1 ανταλλαγής (1-1 exchange). Η μέθοδος αυτή ανήκει στις τεχνικές τοπικής αναζήτησης και χρησιμοποιείται προκειμένου να ελεγχθεί εάν οι αρχικές λύσεις που έχουν κατασκευαστεί προηγουμένως μπορούν να βελτιωθούν περαιτέρω. Τόσο η μέθοδος GRASP όσο και η 1-1 exchange παράγουν τυχαίες λύσεις οι οποίες είναι πιθανό να διαφέρουν από επανάληψη σε επανάληψη γι αυτό και επιλέγουμε να τις επαναλάβουμε παραπάνω φορές συγκρίνοντας κάθε φορά τα αποτελέσματα που επιστρέφουν και επιλέγοντας αυτό που αποδίδει το ελάχιστο κόστος. Η υλοποίηση των παραπάνω μεθόδων πραγματοποιήθηκε στο προγραμματιστικό περιβάλλον MATLAB για ένα πλήθος διαφορετικών επαναλήψεων και δεδομένων προβλήματος ενώ τα αποτελέσματα που επιστρέφουν παρατίθενται και αναλύονται στο τέλος της εργασίας.

Available Files

Services