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