Practical Algorithms with Guaranteed Approximation Ratio for TTP with Maximum Tour Length Two

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. We propose practical algorithms for TTP-2 with improved approximation ratios. Due to the different structural properties of the problem, all known algorithms for TTP-2 are different for $n\mathrm{/}2$ being odd and even, and our algorithms are also different for these two cases. For even $n\mathrm{/}2$, our approximation ratio is $1+3\mathrm{/}n$, improving the previous result of $1+4\mathrm{/}n$. For odd $n\mathrm{/}2$, our approximation ratio is $1+5\mathrm{/}n$, improving the previous result of $3\mathrm{/}2+6\mathrm{/}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\mathrm{\%}$.