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

Abstract

The dissertation focuses on planning tourist routes by optimizing vehicle routing problems using specially designed algorithmic frameworks. Routing problems simulate the planning of visits between points of interest (POIs) of a travel destination. An important designing factor is the duration of the trip, which limits the possibility to visit every point of interest available in the examined area. When forming individual tourist routes, a subset of the available points is selected, contributing more to the visitor's satisfaction, taking into account his respective preferences. Thus, different scenarios of route planning were considered, taking into account different problems and visitors, i.e., an individual or a group. Initially, in the case of an individual, the optimal route planning at points of interest was conducted, considering that his preference at each point of interest has been declared in advance using discrete values, by optimizing the Capacitated Team Orienteering Problem (CTOP) and the Prize-Collecting Vehicle Routing Problem (PCVRP). An appropriate algorithmic framework, the Distance Related Differential Evolution (DRDE) algorithm, was designed to optimize CTOP. The results of the DRDE method were compared with the optimal values ​​of the reference literature references, highlighting the effectiveness and competitiveness of the proposed method. For the optimization of PCVRP, the Firefly Algorithm based on Coordinates (FACR) is proposed. The proposed FACR algorithm is compared in solving the reference examples of the PCVRP literature with the proposed DRDE, of whom it prevails.If the visitor examines different or conflicting criteria for planning his tourist routes, multi-objective problems are used, such as the Multi-Objective Prize-Collecting Vehicle Routing Problem (MO-PCVRP)). Solving such problems does not lead to a single optimal solution but to a subset of the best solutions that cannot be compared with each other. For this reason, an interactive framework based on the proposed Preference-Guided Firefly Algorithm (PGFA), utilized the novel FACR, is proposed. Through which, the visitor states his preference and directs the search, using methods of analytical synthetic approach. The experiments showed that the proposed interactive method successfully directs the search in the solution spaces according to the visitor's preferences. Finally, the scenario of planning tourist routes for a group of tourists was studied, considering that its members have different preferences but want to travel together. The present dissertation proposes using a method that incorporates elements of Game Theory and algorithmic optimization to propose tourist routes that cover the different preferences and satisfy all team members. Specifically, the repetitive simulation of the n-Person Battle of the Sexes (n-BOS) game is used, imitating (through agents) the interaction of the members of the tourist team. The final visiting route results from solving the proposed n-Person Prize-Collecting Vehicle Routing Problem (n-PCVRP), and it is optimized through the novel Firefly Algorithm based on Coordinates and Distances (Firefly Algorithm based on Coordinates and Distance (FACRD)). This algorithmic framework incorporates specially designed heuristic techniques for constructing and improving solutions, utilizing a new encoding/decoding method. The proposed algorithm delivers feasible and effective solutions that are in line with the group's preferences.

Στη παρούσα διδακτορική διατριβή μελετήθηκε ο σχεδιασμός τουριστικών διαδρομών, ως αποτέλεσμα της επίλυσης προβλημάτων δρομολόγησης οχημάτων κάνοντας χρήση ειδικά σχεδιασμένων αλγοριθμικών πλαισίων. Θεωρείται ότι τα προβλήματα δρομολόγησης οχημάτων της βιβλιογραφίας μπορούν να χρησιμοποιηθούν (ως έχει ή παραλλαγμένα) στο σχεδιασμό διαδρομών ανάμεσα στα σημεία ενδιαφέροντος (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)). Σε αυτό το αλγοριθμικό πλαίσιο ενσωματώνονται ειδικά σχεδιασμένες ευρετικές τεχνικές κατασκευής και βελτίωσης των λύσεων, ενώ χρησιμοποιείται μία νέα μέθοδος κωδικοποίησης/αποκωδικοποίησης. Ο προτεινόμενος αλγόριθμος αποδίδει εφικτές και αποτελεσματικές λύσεις που συνάδουν με τις προτιμήσεις της ομάδας.