Abstract:
This thesis looks at the Traveling Tournament Problem (TTP) from the sports scheduling literature. It presents two approaches to this problem: a metaheuristic Ant Colony Optimization (ACO) approach to nd good solutions in a reasonable time frame and a heuristic search Iterative-Deepening-A* (IDA*) approach to nd optimal solutions. The rst approach combines ACO with constraint processing techniques in order to handle the hard constraints of the TTP. The key component is creating a framework which uses forward-checking and con ict-directed backjumping to handle the constraints while using ACO for choosing the values. This is further improved by introducing new ideas of unsafe backjumping and pattern matching for constraint propagation while incorporating an old concept of ant restarts. This approach has been found to improve on past ACO approaches to the TTP and showed results which are more competitive with state-of-theart metaheuristic approaches. The second approach presents a parallel version of IDA*, combining past concepts of tree decomposition and node ordering with a new idea of subtree skipping. This new idea allows for parts of the search tree to be skipped for some iterations while still guaranteeing optimality for the nal solution that is found. Two additional ideas are presented. The rst, called forced deepening, helps to reduce node expansion when applying IDA*-like algorithms on real-world distance problems. The second, called elite paths, helps to both improve the performance of forced deepening while also allowing for the optimal solution to be found faster during the nal iteration of IDA*. The results of applying this new approach to the TTP shows that it is state-of-the-art, nding known optimal solutions in a fraction of the time of past approaches and nding new optimal solutions to some unsolved problem instances.