Font Size:

The Linear Distance Traveling Tournament Problem

Last modified: 2012-07-14

#### Abstract

We introduce a linear distance relaxation of the n-team Traveling Tournament Problem (TTP), a simple yet powerful heuristic that temporarily "assumes"' the n teams are located on a straight line, thereby reducing the

*n*(*n*–1)/2 pairwise distance parameters to just*n*–1 variables. The modified problem then becomes easier to analyze, from which we determine an approximate solution for the actual instance on*n*teams. We present combinatorial techniques to solve the Linear Distance TTP (LD-TTP) for*n*= 4 and*n*= 6, without any use of computing, generating the complete set of optimal distances regardless of where the*n*teams are located. We show that there are only 295 non-isomorphic schedules that can be a solution to the 6-team LD-TTP, and demonstrate that in*all*previously-solved benchmark TTP instances on 6 teams, the distance-optimal schedule appears in this list of 295, even when the six teams are arranged in a circle or located in three-dimensional space. We then extend the LD-TTP to multiple rounds, and apply our theory to produce a nearly-optimal regular-season schedule for the Nippon Pro Baseball league in Japan. We conclude the paper by generalizing our theory to the*n*-team LD-TTP, producing a feasible schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution.
Full Text:
PDF