Solving the traveling tournament problem with iterative‐deepening A*

This work presents an iterative‐deepening A^* (IDA^*) based approach to the traveling tournament problem (TTP). The TTP is a combinatorial optimization problem which abstracts the Major League Baseball schedule. IDA^* is able to find optimal solutions to this problem, with performance improvements coming from the incorporation of various past concepts including disjoint pattern databases, symmetry breaking, and parallelization along with new ideas of subtree skipping, forced deepening, and elite paths to help to reduce the search space. The results of this work show that an IDA^* based approach can find known optimal solutions to most TTP instances much faster than past approaches. More importantly, it has been able to optimally solve two larger instances that have been unsolved since the problem’s introduction in 2001. In addition, a new problem set called GALAXY is introduced, using a 3D space to create a challenging problem set.