{'fraction_non_alphanumeric': 0.024773413897280966, 'fraction_numerical': 0.002416918429003021, 'mean_word_length': 6.016949152542373, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Simulated Annealing Based Local Search for Sport Scheduling Problems

Sport Scheduling is an important area of Combinatorial Optimization of great practical and theoretical significance, that features some extremely challenging optimization problems. This thesis focuses on two important sport scheduling problems: the Break Minimization Problem (which arises in scheduling European soccer leagues) and the Traveling Tournament Problem (TTP), proposed by Easton, Nemhauser, and Trick (2001), which captures the essence of scheduling Major League Baseball in the United States. For the TTP, no exact solution has been found for most benchmarks, even by employing state-of-the-art combinatorial optimization tools. In this thesis, we develop two sophisticated simulated annealing schemes, BMSA and TTSA, and successfully apply them to Break Minimization and TTP, respectively, improving the best-known solutions to most benchmarks proposed in the literature. Then we embed TTSA in an original population-based framework featuring diversification and intensification, to significantly improve most TTSA results. The main contributions of this thesis are the following: we show that, contrary to common belief, Local Search is an effective method for Sport Scheduling; we design a sophisticated neighborhood that captures the problem's special structure; we successfully adapt tabu search ideas such as strategic oscillation, intensification and diversification into simulated annealing; and, we develop advanced local search schemes with original modelings and sophisticated metaheuristics, that produce the best currently known solutions on most benchmarks.