Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Kotzabasi Danai

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/51FFD8E4-B1E6-4799-8DBA-2AE7424F7234-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.62493-
Γλώσσαel-
Μέγεθος2,6 megabytesen
ΤίτλοςΕπίλυση του προβλήματος δρομολόγησης οχημάτων με χρήση της διαδικασίας άπληστη τυχαιοποιημένη προσαρμοστική αναζήτησηel
ΔημιουργόςKotzabasi Danaien
ΔημιουργόςΚοτζαμπαση Δαναηel
Συντελεστής [Επιβλέπων Καθηγητής]Marinakis Ioannisen
Συντελεστής [Επιβλέπων Καθηγητής]Μαρινακης Ιωαννηςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Marinaki Magdalinien
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μαρινακη Μαγδαληνηel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Tsafarakis Steliosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Τσαφαρακης Στελιοςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Production Engineering and Managementen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και Διοίκησηςel
ΠερίληψηΗ συγκεκριμένη διπλωματική εργασία έχει ως αντικείμενο την υλοποίηση κάποιων μεθόδων δρομολόγησης οχημάτων που χρησιμοποιούνται για τη διανομή των προϊόντων-αγαθών μιας εφοδιαστικής αλυσίδας. Οι μέθοδοι που χρησιμοποιούνται είναι οι κατασκευαστικοί αλγόριθμοι: Άπληστη τυχαιοποιημένη προσαρμοστική αναζήτηση (greedy randomized adaptive procedure ή GRASP) και πλησιέστερος γείτονας (nearest neighbor). Στόχος και των δύο μεθόδων είναι η κατασκευή μιας διαδρομής τέτοιας ώστε να ικανοποιούνται οι ανάγκες των πελατών που ορίζει κάθε φορά το πρόβλημα και να ελαχιστοποιείται το κόστος που προκύπτει από αυτή. Ταυτόχρονα, λαμβάνονται υπόψη περιορισμοί που αφορούν τη δεδομένη χωρητικότητα των οχημάτων και τον προκαθορισμένο χρόνο που κάθε όχημα επιτρέπεται να δαπανήσει στην εξυπηρέτηση. Ακόμα, για το καθορισμό της επιθυμητής διαδρομής δίνονται ως δεδομένα το πλήθος και οι τοποθεσίες των πελατών, η ζήτηση κάθε πελάτη και ο χρόνος εξυπηρέτησής του. Με τη μέθοδο του πλησιέστερου γείτονα, η επιλογή της σειράς εξυπηρέτησης των πελατών καθορίζεται από την απόσταση που απέχουν κάθε φορά οι πελάτες από το όχημα και επιλέγεται αυτός με την ελάχιστη, εφόσον φυσικά τηρούνται οι περιορισμοί που προαναφέρθηκαν. Με τη GRASP, η επιλογή των πελατών γίνεται τυχαία ανάμεσα σε ένα αριθμό πελατών που απέχουν λιγότερο από τη τρέχουσα θέση του οχήματος σε σχέση με τους υπόλοιπους χωρίς απαραίτητα να επιλέγεται ο πλησιέστερος. Και για τους δύο αλγόριθμους ισχύει ότι ένα όχημα ξεκινάει από την αποθήκη, επισκέπτεται τους πελάτες κατά το τρόπο που ορίζει κάθε φορά η μέθοδος, ελέγχοντας ταυτόχρονα τους περιορισμούς. Εάν αυτοί παραβιάζονται τότε το όχημα επιστρέφει στην αποθήκη και ένα νέο όχημα συνεχίζει την εξυπηρέτηση, ενώ οι αλγόριθμοι τερματίζουν όταν όλοι οι πελάτες έχουν εξυπηρετηθεί και τελικά το όχημα επιστρέφει στην αποθήκη. Έπειτα από τη κατασκευή των διαδρομών ακολουθεί η ανταλλαγή δύο τυχαίων πελατών μέσω της μεθόδου 1-1 ανταλλαγής (1-1 exchange). Η μέθοδος αυτή ανήκει στις τεχνικές τοπικής αναζήτησης και χρησιμοποιείται προκειμένου να ελεγχθεί εάν οι αρχικές λύσεις που έχουν κατασκευαστεί προηγουμένως μπορούν να βελτιωθούν περαιτέρω. Τόσο η μέθοδος GRASP όσο και η 1-1 exchange παράγουν τυχαίες λύσεις οι οποίες είναι πιθανό να διαφέρουν από επανάληψη σε επανάληψη γι αυτό και επιλέγουμε να τις επαναλάβουμε παραπάνω φορές συγκρίνοντας κάθε φορά τα αποτελέσματα που επιστρέφουν και επιλέγοντας αυτό που αποδίδει το ελάχιστο κόστος. Η υλοποίηση των παραπάνω μεθόδων πραγματοποιήθηκε στο προγραμματιστικό περιβάλλον MATLAB για ένα πλήθος διαφορετικών επαναλήψεων και δεδομένων προβλήματος ενώ τα αποτελέσματα που επιστρέφουν παρατίθενται και αναλύονται στο τέλος της εργασίας.el
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-12-07-
Ημερομηνία Δημοσίευσης2015-
Θεματική ΚατηγορίαΠρόβλημα δρομολόγησηςel
Βιβλιογραφική ΑναφοράΔανάη Κοτζαμπάση, "Επίλυση του προβλήματος δρομολόγησης οχημάτων με χρήση της διαδικασίας άπληστη τυχαιοποιημένη προσαρμοστική αναζήτηση", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2015el

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

Υπηρεσίες

Στατιστικά