We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Solving the traveling tournament problem with iterative-deepening A.
- Authors
Uthus, David; Riddle, Patricia; Guesgen, Hans
- Abstract
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.
- Subjects
ITERATIVE methods (Mathematics); MAJOR League Baseball (Organization); BASEBALL tournaments; HEURISTIC; MATHEMATICAL optimization
- Publication
Journal of Scheduling, 2012, Vol 15, Issue 5, p601
- ISSN
1094-6136
- Publication type
Article
- DOI
10.1007/s10951-011-0237-x