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/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\%$.
翻译:旅行锦标赛(TTP)是一个困难但有趣的体育日程安排问题,是由主要联盟棒球引发的,即设计一个双轮轮式日程安排,让每对球队在对方的场地里玩一个游戏,最大限度地减少所有球队的距离(美元甚至偶数 ) 。 在本文中,我们考虑TTP-2,即TTP-2,限制下每个球队最多连续两场家庭游戏或离场游戏都允许使用。我们建议了TTP-2的实用算法,并改进了近似率。由于问题的结构性质不同,TTP-2的所有已知算法都不同,美元两美元之间甚至不同,而我们的算法也不同。即使美元/2美元,我们的近似比率也是1+3/n美元,改进了先前的1+4/n美元。对于奇差2美元,我们的近似比率是1+5/n美元,改进了先前的3/2+6/n美元。在实践中,我们的算法是容易执行的。在众所周知的基准组合上实验显示,我们的平均算法是5美元。