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