Solving the Traveling Tournament Problem by Packing Three-Vertex Paths

Marc Goerigk, Richard Hoshino, Ken-ichi Kawarabayashi, Stephan WestphalAAAI 2014 · DOI

Abstract

The Traveling Tournament Problem (TTP) is a complex combinatorial optimization challenge that seeks to minimize total travel distance in a double round-robin tournament under strict operational constraints. This paper presents a novel three-phase algorithm that leverages graph-theoretic $P_3$-packings to construct highly efficient initial schedules. By grouping teams into geographically close triplets, the method outperforms traditional Hamiltonian cycle-based approaches. Experimental results demonstrate that this strategy breaks long-standing records, including a 14-year-old benchmark for the NFL28 dataset.

Introduction

The Traveling Tournament Problem (TTP) is a notoriously difficult challenge in sports scheduling, combining the complexity of the Traveling Salesman Problem (TSP) with the rigid constraints of tournament logistics. It is classified as "strongly NP-hard," meaning that finding optimal solutions for even moderately sized leagues can require immense computational resources.

A valid TTP schedule for $n$ teams must satisfy three primary constraints:

  1. Each-venue: Every team plays every other team twice—once at home and once away.
  2. At-most-three: No team can play more than three consecutive home games or three consecutive away games.
  3. No-repeat: A team cannot play the same opponent in two consecutive rounds.

Historically, researchers have approached TTP by using "canonical" schedules based on Hamiltonian cycles—single loops that connect all teams in a league. However, these cycles are optimized for a single long journey, which often conflicts with the "at-most-three" constraint that limits the length of road trips.

The Core Innovation: From Loops to Triplets

The fundamental insight of this research is that the "at-most-three" constraint creates a natural "sweet spot" for groups of three teams. Instead of trying to fit a tournament into a single Hamiltonian cycle, the authors propose using $P_3$-packings—a set of vertex-disjoint paths of length three.

Traditional TTP approaches often rely on Hamiltonian cycles, which create long, single-loop travel paths that may not align with game constraints.

By grouping teams into triplets that are geographically proximal, the algorithm can design road trips that specifically target these clusters. This maximizes travel efficiency within the allowed three-game window. The authors demonstrate that the total weight of an optimal $P_3$-packing is typically significantly less than two-thirds the weight of an optimal Hamiltonian cycle, providing a much more efficient foundation for the final schedule.

The proposed P3-packing approach groups teams into efficient triplets, significantly reducing the base travel distance for road trips.

Methodology

The researchers developed a three-phase algorithm to translate the $P_3$-packing concept into a world-record-breaking schedule:

Phase 1: $P_3$-Packing Construction

The algorithm begins by finding an optimal $P_3$-packing for the given set of teams. It then uses a constructive method to expand a smaller "seed" tournament into a full schedule. This phase is designed to ensure that the majority of road trips consist of games against teams within the same $P_3$ cluster.

Phase 2: Pairwise-Swapping

Once an initial schedule is generated, a local search heuristic is applied. This phase involves swapping the roles of different teams (e.g., swapping Team A's entire season schedule with Team B's) to identify immediate opportunities for distance reduction without violating the core TTP constraints.

Phase 3: Hybrid Heuristic

The final refinement uses a sophisticated hybrid algorithm that combines Tabu Search with Integer Programming. Tabu Search explores the vast neighborhood of possible schedules to avoid local optima, while Integer Programming (utilizing solvers like Gurobi) is used to find the mathematically optimal home/away patterns for a fixed set of matchups.

Experimental Results

The algorithm was benchmarked against two major datasets: the "Galaxy" instances (teams represented as exoplanets in 3D space) and the "NFL28" dataset (based on 28 real-world NFL teams).

The results were definitive. The $P_3$-based approach established new "best-known" upper bounds for five major instances:

  • Galaxy22, 28, 34, and 40: The method achieved improvements of 2% to 4% over previous state-of-the-art results.
  • NFL28: The team achieved a new record of 589,123, shattering the previous record of 609,788 that had stood since 2007.

Conclusion and Future Work

This research proves that the initial structure of a tournament schedule—the "starting point"—is critical to the final outcome. By moving from Hamiltonian cycles to $P_3$-packings, the authors provided the hybrid heuristic with a superior foundation that led to multiple world records.

A current limitation of the constructive method is that it is optimized for instances where the number of teams $n$ follows the formula $n = 6m - 2$ (or $n \equiv 4 \pmod 6$). Future work will focus on generalizing $P_3$-packing constructions for all values of $n$, particularly $n \equiv 0$ and $n \equiv 2 \pmod 6$, to ensure the method can be applied to any professional sports league.

Summary updated

BibTeX
@inproceedings{goerigk2014solving,
  author = {Marc Goerigk and Richard Hoshino and Ken-ichi Kawarabayashi and Stephan Westphal},
  title = {{Solving the Traveling Tournament Problem by Packing Three-Vertex Paths}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9031},
}
Figure