Institutional Repository
Technical University of Crete
EN  |  EL

Search

Browse

My Space

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

Frantzeskakis Georgios

Simple record


URIhttp://purl.tuc.gr/dl/dias/C90FAC68-E309-4700-87F1-C6DE604F9E09-
Identifierhttps://doi.org/10.26233/heallink.tuc.63814-
Languageel-
Extent7,2 megabytesel
TitleΜοντελοποίησις και επίλυσις γενικευμένου προβλήματος δρομολόγησης οχημάτων χρήσει αλγορίθμου περιορισμένης αναζήτησηςel
CreatorFrantzeskakis Georgiosen
CreatorΦραντζεσκακης Γεωργιοςel
Contributor [Thesis Supervisor]Marinakis Ioannisen
Contributor [Thesis Supervisor]Μαρινακης Ιωαννηςel
Contributor [Committee Member]Antoniadis Aristomenisen
Contributor [Committee Member]Αντωνιαδης Αριστομενηςel
Contributor [Committee Member]Stavroulakis Georgiosen
Contributor [Committee Member]Σταυρουλακης Γεωργιοςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Production Engineering and Managementen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και Διοίκησηςel
DescriptionΔιπλωματική εργασία, υπεβλήθη την 4η Μαρτίου 2016 εις τον τομέα λήψης αποφάσεων el
Content SummaryΑντικειμενικός σκοπός της επιχειρησιακής ερεύνης αποτελεί η υλοποίηση διαδικασιών και επίτευξης στόχων υπό περιορισμούς πόρων (χρηματικών, πρώτων υλών κ.α) . Στο γενικότερο αυτό πλαίσιο εντάσσεται και η λήψη αποφάσεων πέριξ του προβλήματος διανομής προϊόντων – υπηρεσιών μέσω δρομολόγησης οχημάτων, για μια επιχείρηση ή εν γένει παραγωγική μονάδα. Η επαναστατική χρήση των Η/Υ δύναται να προσφέρει υποστήριξη στα κέντρα αποφάσεων. Καθολική χρήση συγκεκριμένων αλγοριθμικών μεθόδων όπως αυτή της μεθευρετικής αναζήτησης, αλλά και άλλων άπληστων τεχνικών εκ του πρακτέου έχουν αποδειχτεί ως οι πλέον αποτελεσματικότερες. Ο λόγος για αυτό είναι η συνδυαστική αφενός πολυπλοκότητα και αφετέρου η ανάγκη για δυναμική εναλλαγή των αποφάσεων σε πραγματικό χρόνο. Συνέπεια των ανωτέρω είναι ο μονόδρομος για ανάπτυξη ενός ευέλικτου λογισμικού για το πρόβλημα δρομολόγησης οχημάτων με χρονικά παράθυρα (Vehicle Routing Problem with Time Windows - VRPTW), με έμφαση στην ακρίβεια και την ταχύτητα εκτελέσεως. Σύγχρονες γλώσσες προγραμματισμού όπως η Java καθιστούν την προσπάθεια αυτή ακόμα πιο ανταγωνιστική. Στην εργασία ευρέθη μια καινοτόμος αλγοριθμική μεθοδολογία ονόματι « Αναζήτηση μεταφορών με άπληστη αρχικοποιημένη δρομολόγηση – Greedy Initialized Routing Search On Transportations (GIRSOT) ». Η εργασία απαρτίζεται από πέντε κεφάλαια με τη λογική το «διαίρει και βασίλευε» επιχειρείται η λύσις του προβλήματος υπό τη λύση πολλών μικρότερων προβλημάτων, έτσι στο πρώτο κεφάλαιο γίνεται παρουσίαση του προβλήματος, στο δεύτερο προτείνεται ένας καλός αλγόριθμος ομαδοποίησης των πελατών (3-PCC). Στο τρίτο κεφάλαιο γίνεται μια προσπάθεια κατασκευής μιας μεθόδου βελτιστοποίησης επί των δρομολογίων. Το αποτέλεσμα που προκύπτει δεν είναι ούτε απογοητευτικό αλλά και ούτε αρκετό. Στο τέταρτο κεφάλαιο προτείνεται ένας ακόμα αλγόριθμος, ο αλγόριθμος σποράς (seeding algorithm) ο οποίος δίνει στον αλγόριθμο GIRSOT την πολυεναρκτήρια ιδιότητα του. Επόμενο βήμα θα είναι μια ύστατη προσπάθεια μείωσης ακόμα περισσότερο του κόστους, με τη μέθοδο μαζικής ανάθεσης - group relocate. Αν όλες οι ανωτέρω διαδικασίες αποτύχουν εφαρμόζεται η χρονική υποτίμησiς (Devaluation Time Algorithm – BTA), η οποία εξαναγκάζει τη 3-PCC να δώσει νέες αρχικές λύσεις με περισσότερα οχήματα. Τέλος στο κεφάλαιο πέντε επιλέγεται το δείγμα απ’ τα προβλήματα του Solomon n100 και των Gehring & Homberger’s για να δειχθεί η αποτελεσματικότητα του προτεινόμενου αλγορίθμου.el
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by-nc-nd/4.0/en
Date of Item2016-03-04-
Date of Publication2016-
SubjectΕπιχειρησιακή έρευναel
SubjectΠρόβλημα δρομολόγησης οχημάτωνel
Bibliographic CitationΓεώργιος Φραντζεσκάκης, "Μοντελοποίησις και επίλυσις γενικευμένου προβλήματος δρομολόγησης οχημάτων χρήσει αλγορίθμου περιορισμένης αναζήτησης", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2016el

Available Files

Services

Statistics