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

Abstract

Η τρέχουσα εργασία μελετά εκτενώς το Πρόβλημα Ομαδικού Προσανατολισμού με Χρονικά Παράθυρα, το οποίο αποτελεί επέκταση του Προβλήματος Προσανατολισμού. Το Πρόβλημα Προσανατολισμού ανήκει στα NP-hard προβλήματα, κάτι που το κάνει αδύνατο να λυθεί σε πολυωνυμικό χρόνο για μεγάλα δεδομένα εισόδου. Για το λόγο αυτό, η χρήση ευρετικών και προσεγγιστικών αλγορίθμων καθίσταται αναγκαία για την εύρεση ικανοποιητικών λύσεων σε μικρό χρονικό διάστημα. Για το Πρόβλημα Προσανατολισμού έχουν ήδη υλοποιηθεί αρκετοί αλγόριθμοι, ένας από τους οποίους είναι και ο αλγόριθμος Επαναλαμβανόμενης Τοπικής Αναζήτησης (ILS). Σκοπός της παρούσας εργασίας είναι να μειώσει το χρόνο εκτέλεσης του ILS, διαχωρίζοντας το γράφημα του προβλήματος με ικανοποιητικό τρόπο, εφαρμόζοντας μια διαχωρισμένη Τοπική Αναζήτηση στα επιμέρους υπο-γραφήματα, και αντιμετωπίζοντας τα προβλήματα που προκύπτουν από αυτόν τον διαχωρισμό. Τα πειραματικά αποτελέσματα δείχνουν τη μείωση του χρόνου εκτέλεσης του αλγορίθμου ειδικά σε παραδείγματα με μεγάλα δεδομένα εισόδου, με αντίκτυπο όμως τη μείωση της βαθμολογίας των λύσεων. Παρ’ όλα αυτά, έχουν γίνει βήματα για τη διατήρηση των λύσεων σε ικανοποιητικό επίπεδο, ενώ υπάρχουν και περαιτέρω περιθώρια βελτίωσης.