Practical Algorithms with Guaranteed Approximation Ratio for Traveling Tournament Problem with Maximum Tour Length 2

The traveling tournament problem (TTP) is a hard but interesting sports scheduling problem inspired by Major League Baseball, which is to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams ( n is even). In this paper, we consider TTP-2 (i.e., TTP under the constraint that at most two consecutive home games or away games are allowed for each team). In this paper, we propose practical algorithms for TTP-2 with improved approximation ratios. Because of the different structural properties of the problem, all known algorithms for TTP-2 are different for n /2 being odd and even, and our algorithms are also different for these two cases. For even n /2, our approximation ratio is 1 + 3 / n , improving the previous result of 1 + 4 / n . For odd n /2, our approximation ratio is 1 + 5 / n , improving the previous result of 3 / 2 + 6 / n . In practice, our algorithms are easy to implement. Experiments on well-known benchmark sets show that our algorithms beat previously known solutions for all instances with an average improvement of 5.66%.