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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Rigakis Manousos

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/E3AFE3FC-C992-483F-BC64-D4F7A5245AF4-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.90800-
Γλώσσαel-
Μέγεθος3,76 megabytesen
Μέγεθος145 σελίδεςel
ΤίτλοςΜοντελοποίηση προβλημάτων βελτιστοποίησης με χρήση θεωρίας παιγνίων και επίλυση τους μέσω μεθευρετικών αλγορίθμωνel
ΤίτλοςFormulation of optimization problems using game theory and application of metaheuristic algorithms for their solutionen
ΔημιουργόςRigakis Manousosen
ΔημιουργόςΡηγακης Μανουσοςel
Συντελεστής [Επιβλέπων Καθηγητής]Marinakis Ioannisen
Συντελεστής [Επιβλέπων Καθηγητής]Μαρινακης Ιωαννηςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Matsatsinis Nikolaosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ματσατσινης Νικολαοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Stavroulakis Georgiosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σταυρουλακης Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Mygdalas Athanasiosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μυγδαλας Αθανασιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σιφαλέρας, Άγγελοςen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Δούνιας, Γεώργιος Δen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σαχαρίδης Γεώργιος el
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Production Engineering and Managementen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και Διοίκησηςel
ΠεριγραφήΔιδακτορική Διατριβήel
ΠερίληψηΣτη παρούσα διδακτορική διατριβή μελετήθηκε ο σχεδιασμός τουριστικών διαδρομών, ως αποτέλεσμα της επίλυσης προβλημάτων δρομολόγησης οχημάτων κάνοντας χρήση ειδικά σχεδιασμένων αλγοριθμικών πλαισίων. Θεωρείται ότι τα προβλήματα δρομολόγησης οχημάτων της βιβλιογραφίας μπορούν να χρησιμοποιηθούν (ως έχει ή παραλλαγμένα) στο σχεδιασμό διαδρομών ανάμεσα στα σημεία ενδιαφέροντος (POIs) ενός ταξιδιωτικού προορισμού. Σημαντικός παράγοντας της δρομολόγησης είναι η πεπερασμένη διάρκεια του ταξιδιού, το οποίο πρακτικά σημαίνει ότι δεν είναι δυνατή η επίσκεψη κάθε σημείου ενδιαφέροντος. Συνεπώς, κατά το σχηματισμό εξατομικευμένων τουριστικών διαδρομών γίνεται η επιλογή ενός υποσυνόλου από τα διαθέσιμα σημεία, τα οποία συμβάλουν περισσότερο στην ικανοποίηση του χρήστη, λαμβάνοντας υπόψιν τις αντίστοιχες προτιμήσεις του. Έτσι, εξετάστηκαν διαφορετικά σενάρια λαμβάνοντας υπόψη ένα άτομο ή μία ομάδα ατόμων και τις αντίστοιχες προτιμήσεις τους. Αρχικά, στη περίπτωση ενός ατόμου, εξετάστηκε ο βέλτιστος σχεδιασμός διαδρομών στα σημεία ενδιαφέροντος θεωρώντας ότι η προτίμηση του σε κάθε σημείο ενδιαφέροντος έχει εκ των προτέρων δηλωθεί με τη χρήση διακριτών τιμών. Για το σκοπό αυτό, επιλέχθηκε το Πρόβλημα Προσανατολισμού Ομάδας με Περιορισμένη Χωρητικότητα (Capacitated Team Orienteering Problem (CTOP)) και το Πρόβλημα Δρομολόγησης Οχημάτων Συλλογής Βραβείου (Prize-Collecting Vehicle Routing Problem (PCVRP)). Για τη βελτιστοποίηση του CTOP σχεδιάστηκε ένα κατάλληλο αλγοριθμικό πλαίσιο, ο αλγόριθμος της Διαφορικής Εξέλιξης Σχετιζόμενη με τις Αποστάσεις (Distance Related Differential Evolution (DRDE)). Τα αποτελέσματα της μεθόδου DRDE συγκρίθηκαν με τις βέλτιστες τιμές των παραδειγμάτων αναφοράς της βιβλιογραφίας, αναδεικνύοντας την αποτελεσματικότητα και ανταγωνιστικότητα της προτεινόμενης μεθόδου. Για τη βελτιστοποίηση του PCVRP προτείνεται ο Αλγόριθμος της Πυγολαμπίδας βασισμένος στις Συντεταγμένες (Firefly Algorithm based on Coordinates (FACR)). Ο προτεινόμενος αλγόριθμος FACR συγκρίνεται στην επίλυση των παραδειγμάτων αναφοράς της βιβλιογραφίας του PCVRP, με τον προτεινόμενο DRDE, του οποίου και υπερισχύει. Στην περίπτωση, που ο επισκέπτης εξετάζει παράλληλα διαφορετικά ή αντικρουόμενα κριτήρια σχεδιασμού των τουριστικών διαδρομών του, γίνεται χρήση πολυ-αντικειμενικών προβλημάτων, όπως το Πολυ-αντικειμενικό Πρόβλημα Δρομολόγησης Οχημάτων Συλλογής Βραβείου (Multi-Objective Prize-Collecting Vehicle Routing Problem (MO-PCVRP)). Η επίλυση τέτοιων προβλημάτων δεν οδηγεί σε μία μοναδική βέλτιστη λύση, αλλά σε ένα υποσύνολο των καλύτερων λύσεων που δεν μπορούν να συγκριθούν μεταξύ τους. Για αυτό το λόγο, προτείνεται ένα αλληλεπιδραστικό πλαίσιο που βασίζεται στον προτεινόμενο Αλγόριθμο της Πυγολαμπίδας με Καθοδήγηση Προτιμήσεων (Preference-Guided Firefly Algorithm (PGFA)), ο οποίος βασίζεται στον προτεινόμενο FACR. Μέσα από το οποίο, ο επισκέπτης δηλώνει τη προτίμηση του και κατευθύνει την αναζήτηση, κάνοντας χρήση μεθόδων αναλυτικής συνθετικής προσέγγισης. Τα υπολογιστικά πειράματα, έδειξαν ότι η προτεινόμενη αλληλεπιδραστική μέθοδος κατευθύνει επιτυχώς την αναζήτηση στο χώρο λύσεων σύμφωνα με τις προτιμήσεις του επισκέπτη. Τέλος, μελετήθηκε και το σενάριο σχεδιασμού τουριστικών διαδρομών για μία ομάδα ατόμων, θεωρώντας ότι τα μέλη της έχουν διαφορετικές ή αντικρουόμενες προτιμήσεις, όμως επιθυμούν να ταξιδέψουν μαζί. Στη παρούσα διατριβή προτείνεται η χρήση μίας μεθόδου που ενσωματώνει στοιχεία της Θεωρίας Παιγνίων και της αλγοριθμικής βελτιστοποίησης, με στόχο την πρόταση τουριστικών διαδρομών που να καλύπτουν τις διαφορετικές προτιμήσεις και να ικανοποιούνται όλα τα μέλη της ομάδας. Συγκεκριμένα, χρησιμοποιείται η επαναληπτική προσομοίωση του παιγνίου n-Ατόμων Μάχη των Φύλων (n-Person Battle of the Sexes (n-BOS)), προσομοιώνοντας (μέσω πρακτόρων) την αλληλεπίδραση των μελών της ομάδας τουριστών. Ενώ, η διαδρομή με τα σημεία ενδιαφέροντος προκύπτει από την επίλυση του προτεινόμενου Προβλήματος Δρομολόγησης Οχημάτων Συλλογής Βραβείου n Ατόμων (n-Person Prize-Collecting Vehicle Routing Problem (n-PCVRP)), η οποία βελτιστοποιείται μέσω του ειδικά σχεδιασμένου Αλγόριθμου της Πυγολαμπίδας βασισμένος στις Συντεταγμένες και Αποστάσεις (Fireflly Algorithm based on Coordinates and Distance (FACRD)). Σε αυτό το αλγοριθμικό πλαίσιο ενσωματώνονται ειδικά σχεδιασμένες ευρετικές τεχνικές κατασκευής και βελτίωσης των λύσεων, ενώ χρησιμοποιείται μία νέα μέθοδος κωδικοποίησης/αποκωδικοποίησης. Ο προτεινόμενος αλγόριθμος αποδίδει εφικτές και αποτελεσματικές λύσεις που συνάδουν με τις προτιμήσεις της ομάδας. el
ΤύποςΔιδακτορική Διατριβήel
ΤύποςDoctoral Dissertationen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by-nc-nd/4.0/en
Ημερομηνία2021-11-05-
Ημερομηνία Δημοσίευσης2021-
Θεματική ΚατηγορίαΔρομολόγηση οχημάτωνel
Θεματική ΚατηγορίαΘεωρία παιγνίωνel
Θεματική ΚατηγορίαΒέλτιστος σχεδιασμός τουριστικών διαδρομώνel
Βιβλιογραφική ΑναφοράΜανούσος Ρηγάκης, "Μοντελοποίηση προβλημάτων βελτιστοποίησης με χρήση θεωρίας παιγνίων και επίλυση τους μέσω μεθευρετικών αλγορίθμων", Διδακτορική Διατριβή, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el
Βιβλιογραφική ΑναφοράManousos Rigakis, "Formulation of optimization problems using game theory and application of metaheuristic algorithms for their solution", Doctoral Dissertation, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2021en

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

Υπηρεσίες

Στατιστικά