New models for the Mirrored Traveling Tournament Problem

The Mirrored Traveling Tournament Problem (mTTP) is a challenging combinatorial optimization problem which consists in generating a timetable for sports tournaments with two half series, what is equivalent to a double round-robin timetable problem. The distance traveled by the teams should be minimized in the final timetable, and a new objective is to minimize the longest distance traveled, named MinMaxTTP. It is proposed an integer programming formulation to the mTTP and two models with dynamic constraints to its solution. Both models are based on the detection of independent sets on conflict graphs, whose use has not been reported in the literature about the problem. Real data benchmarks from a baseball tournament are used in the experiments carried out.

► An IP formulation for Mirrored Traveling Tournament Problem based on the detection of independent sets is proposed. ► Conflict graphs, where adjacencies indicate matches that cannot occur at the same time are used. ► To the best of our knowledge, this concept had not been reported in works related to the Traveling Tournament Problem. ► Two models were proposed, with different objectives, the second is not found in the previous literature. ► Different strategies for accelerating the solution of the models are presented.