The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound

The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound

Jingyang Zhao, Mingyu Xiao

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 4206-4212. https://doi.org/10.24963/ijcai.2021/578

The Traveling Tournament Problem is a well-known benchmark problem in tournament timetabling, which asks us to design a schedule of home/away games of n teams (n is even) under some feasibility requirements such that the total traveling distance of all the n teams is minimized. In this paper, we study TTP-2, the traveling tournament problem where at most two consecutive home games or away games are allowed, and give an effective algorithm for n/2 being odd. Experiments on the well-known benchmark sets show that we can beat previously known solutions for all instances with n/2 being odd by an average improvement of 2.66%. Furthermore, we improve the theoretical approximation ratio from 3/2+O(1/n) to 1+O(1/n) for n/2 being odd, answering a challenging open problem in this area.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Scheduling
Planning and Scheduling: Theoretical Foundations of Planning