Ο χρονοπρογραμματισμός αθλητικών αγώνων είναι ένα δύσκολο πρόβλημα που συγκαταλέγεται συνήθως στην οικογένεια των NP-hard προβλημάτων. Το πρόβλημα αφορά στην δημιουργία ενός ωρολογίου προγράμματος αθλητικών αγώνων που να ικανοποιεί πλήρως ένα σύνολο από δομικούς και ισχυρούς περιορισμούς, ενώ παράλληλα πρέπει να ελαχιστοποιεί το κόστος παραβίασης μιας σειράς από ασθενείς περιορισμούς. Οι δομικοί και οι ισχυροί περιορισμοί ενός προβλήματος χρονοπρογραμματισμού είναι απαραίτητο να ικανοποιούνται πάντα, ενώ οι ασθενείς περιορισμοί είναι επιθυμητό, αλλά όχι απαραίτητο.

Ο χρονοπρογραμματισμός αθλητικών αγώνων είναι ένα υπολογιστικά πολύ απαιτητικό πρόβλημα. Δεν υπάρχει μέχρι σήμερα κάποιος γνωστός και αποδοτικός τρόπος εύρεσης μίας βέλτιστης λύσης του προβλήματος. Εξαιτίας της ιδιαίτερης φύσης και πολυπλοκότητάς του, συνήθως επιστρατεύονται ευρετικές και μεταευρετικές όπως οι Γενετικοί Αλγόριθμοι, ο αλγόριθμος Simulated Annealing (SA), ο αλγόριθμος Tabu Search κ.ά. για την εύρεση μιας καλής και αποδοτικής λύσης σε λογικά πλαίσια χρόνου.

Στην παρούσα εργασία επιχειρείται η αποδοτική επίλυση του προβλήματος χρονοπρογραμματισμού αθλητικών αγώνων με την βοήθεια του υβριδικού αλγορίθμου CP-PSO, ο οποίος βασίζεται στον αλγόριθμο υπολογιστικής νοημοσύνης, Particle Swarm Optimization (PSO) και σε μηχανισμούς Constraint Programming (CP). Ο υβριδικός αλγόριθμος που προτείνουμε επιμερίζει την διαδικασία επίλυσης του προβλήματος σε δύο φάσεις: την φάση ικανοποιησιμότητας (Satisfiability) και την φάση βελτιστοποίησης
(Optimization). Στην πρώτη φάση, υιοθετείται ένα τροποποιημένο μοντέλο που βασίζεται στον αλγόριθμο ανοικτού κώδικα της Google, CP-SAT με την βοήθεια του οποίου παράγεται ένα σύνολο από αρχικά (κανονικά ή εφικτά) σωματίδια. Τα σωματίδια αυτά αποτελούν τα δεδομένα της δεύτερης φάσης, όπου ένα βελτιωμένο μοντέλο PSO εξερευνά τον χώρο αναζήτησης εφαρμόζοντας στρατηγική SA, και τα αποτελέσματα της εξερεύνησης αυτής βελτιώνονται με έναν τροποποιημένο μηχανισμό Hill Climbing.

Ο υβριδικός αλγόριθμος CP-PSO εφαρμόστηκε στα δημοσιευμένα προβλήματα του διαγωνισμού ITC2021 που αποτελεί την καλύτερη βάση δεδομένων προβλημάτων χρονοπρογραμματισμού αθλητικών αγώνων. Παρά την μεγάλη υπολογιστική δυσκολία των προβλημάτων αυτών και τους περιορισμένους υπολογιστικούς πόρους που είχαμε στην διάθεσή μας, ο αλγόριθμος CP-PSO κατάφερε να επιτύχει καλά αποτελέσματα.

The Sports Timetabling Problem (STP) is a challenging problem that is often classified as a NP-hard problem. The STP problem involves creating a timetable for organizing matches in a sports league that fully satisfies a set of structural and hard constraints, while minimizing the cost of violation of a series of soft constraints. The structural and hard constraints of a STP problem must always be satisfied, whereas the soft constraints are desirable but not necessary.

The STP problem is a computationally intensive problem. There is no known efficient way for finding an optimal solution to this problem so far. Due to its unique nature and complexity, heuristic and metaheuristic methods such as Genetic Algorithms, Simulated Annealing (SA), Tabu Search, etc., are usually employed to find a good and efficient solution within a reasonable amount of time.

In this work, we approach efficiently the STP problem with the help of the hybrid CP-PSO algorithm, using Computational Intelligence Particle Swarm Optimization (PSO) and Constraint Programming (CP) heuristic. The proposed hybrid algorithm divides the problem-solving process into two phases: the satisfiability phase and the optimization phase. In the first phase, an advanced model based on Google's open-source OR-Tools, CP-SAT, is used for obtaining a set of initial (canonical or feasible) particles. These particles will be the initial data of the second phase, where an advanced PSO model explores the search space implementing a SA scheme. The output of the exploration and exploitation derived is getting improved with the means of a modified Hill Climbing mechanism.

The CP-PSO hybrid algorithm is tested to the published instances of the ITC2021 competition, which represents the best, well-known database of sports timetabling instances. Despite the significant computational difficulty of these problems and the limited computational resources we had available, the CP-PSO algorithm managed to achieve good results.