dc.contributor.advisor | Κωνσταντόπουλος, Χαράλαμπος | |
dc.contributor.author | Καψιώτης, Ευστάθιος | |
dc.date.accessioned | 2023-05-16T10:13:26Z | |
dc.date.available | 2023-05-16T10:13:26Z | |
dc.date.issued | 2022-12 | |
dc.identifier.uri | https://dione.lib.unipi.gr/xmlui/handle/unipi/15404 | |
dc.identifier.uri | http://dx.doi.org/10.26267/unipi_dione/2826 | |
dc.description.abstract | Η τρέχουσα εργασία μελετά εκτενώς το Πρόβλημα Ομαδικού Προσανατολισμού με Χρονικά Παράθυρα, το οποίο αποτελεί επέκταση του Προβλήματος Προσανατολισμού. Το Πρόβλημα Προσανατολισμού ανήκει στα NP-hard προβλήματα, κάτι που το κάνει αδύνατο να λυθεί σε πολυωνυμικό χρόνο για μεγάλα δεδομένα εισόδου. Για το λόγο αυτό, η χρήση ευρετικών και προσεγγιστικών αλγορίθμων καθίσταται αναγκαία για την εύρεση ικανοποιητικών λύσεων σε μικρό χρονικό διάστημα. Για το Πρόβλημα Προσανατολισμού έχουν ήδη υλοποιηθεί αρκετοί αλγόριθμοι, ένας από τους οποίους είναι και ο αλγόριθμος Επαναλαμβανόμενης Τοπικής Αναζήτησης (ILS). Σκοπός της παρούσας εργασίας είναι να μειώσει το χρόνο εκτέλεσης του ILS, διαχωρίζοντας το γράφημα του προβλήματος με ικανοποιητικό τρόπο, εφαρμόζοντας μια διαχωρισμένη Τοπική Αναζήτηση στα επιμέρους υπο-γραφήματα, και αντιμετωπίζοντας τα προβλήματα που προκύπτουν από αυτόν τον διαχωρισμό. Τα πειραματικά αποτελέσματα δείχνουν τη μείωση του χρόνου εκτέλεσης του αλγορίθμου ειδικά σε παραδείγματα με μεγάλα δεδομένα εισόδου, με αντίκτυπο όμως τη μείωση της βαθμολογίας των λύσεων. Παρ’ όλα αυτά, έχουν γίνει βήματα για τη διατήρηση των λύσεων σε ικανοποιητικό επίπεδο, ενώ υπάρχουν και περαιτέρω περιθώρια βελτίωσης. | el |
dc.format.extent | 80 | el |
dc.language.iso | el | el |
dc.publisher | Πανεπιστήμιο Πειραιώς | el |
dc.rights | Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/gr/ | * |
dc.title | Διαχωρισμένη τοπική αναζήτηση για το πρόβλημα ομαδικού προσανατολισμού με χρονικά παράθυρα | el |
dc.title.alternative | Partitioned local search for the team orienteering problem with time windows | el |
dc.type | Master Thesis | el |
dc.contributor.department | Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής | el |
dc.description.abstractEN | The current work extensively studies the Team Orienteering Problem with Time Windows, which is an extension of the Orienteering Problem. The Orienteering Problem belongs to NP-hard problems, which makes it impossible to solve in polynomial time for large input data. For this reason, the use of heuristic and approximate algorithms becomes necessary to find satisfactory solutions in a short period of time. Several algorithms have already been implemented for the Orienteering Problem, one of which is the Iterated Local Search (ILS) algorithm. The purpose of this paper is to reduce the execution time of ILS by partitioning the problem graph in a satisfactory way, applying a partitioned Local Search to the individual sub-graphs, and dealing with the problems arising from this partitioning. The experimental results show the reduction of the execution time of the algorithm especially in examples with large input data, but with the impact of the reduction of the score of the solutions. Nevertheless, steps have been taken to maintain the solutions at a satisfactory level, while there is also room for further improvement. | el |
dc.contributor.master | Προηγμένα Συστήματα Πληροφορικής | el |
dc.subject.keyword | ILS | el |
dc.subject.keyword | NP-hard | el |
dc.date.defense | 2022-12 | |