Balancing the Traveling Tournament Problem for Weekday and Weekend Games

Richard Hoshino, Ken-ichi KawarabayashiIAAI 2013 · DOI

TL;DR

This paper tackles the complex sports scheduling problem for the Nippon Professional Baseball (NPB) Central League by adapting the Traveling Tournament Problem (TTP). They introduce novel constraints to balance weekday/weekend games and successfully apply a graph-theoretic shortest-path algorithm to generate an optimal schedule that significantly reduces team travel distance.

What Problem Does This Paper Address?

Scheduling professional sports leagues is a computationally challenging task, often framed as the Traveling Tournament Problem (TTP). The TTP aims to create a double round-robin schedule that minimizes the total distance traveled by all teams. While the standard TTP is NP-complete, real-world leagues like Japan's Nippon Professional Baseball (NPB) have additional, complex constraints. This paper focuses on the NPB Central League, which has specific requirements beyond minimizing travel, most notably a "revenue-balancing" rule. This rule mandates that each team play an equal number of home and away games on both weekdays and weekends. This is crucial because weekday games often have lower attendance than weekend games, and an equitable distribution of weekend home games is essential for fairness and revenue. The authors aim to solve this variant of the TTP for the NPB Central League, generating a schedule that satisfies these stringent conditions while still minimizing travel.

Methods

The authors extend the standard TTP by incorporating several new constraints specific to the NPB. These include:

  • Each-round condition: Each pair of teams plays exactly once per round, with matches in consecutive rounds occurring at different venues.
  • Diff-two condition: The absolute difference between a team's home and away sets played up to any point in the season must not exceed two.
  • At-most-two condition: No team can have a home stand or road trip lasting more than two consecutive sets.
  • Weekday-weekend condition: This is the core novel constraint, requiring a specific distribution of weekend/weekday home/away games across different blocks of the season, ultimately aiming for a (10, 10, 10, 10) four-tuple for each team over the entire season.

To solve this, they adapt a shortest-path algorithm. They model the problem as a directed graph where vertices represent possible "blocks" (multi-set schedules) and edges represent the concatenation of these blocks. Dijkstra's algorithm is then used to find the shortest path from a source to a sink node, which corresponds to the optimal schedule. A key innovation is the use of a "concatenation matrix" to efficiently check the feasibility of joining two blocks without violating constraints, and to assign weights to the graph edges based on travel distances. They also detail how they handle the weekday-weekend constraint by partitioning blocks and running Dijkstra's algorithm multiple times.

Datasets

The primary dataset used is the distance matrix for the six teams in the NPB Central League. This matrix, provided in Table 1, details the distances between the home stadiums of each team. This is a standard input for TTP-related problems. The paper also implicitly uses the official 2012 NPB Central League schedule as a baseline for comparison.

Key Insights and Ideas

  • The "revenue-balancing" constraint is critical: The paper highlights that real-world sports scheduling involves more than just minimizing travel; equitable distribution of attractive game slots (like weekend home games) is paramount for financial and competitive fairness.
  • Graph theory is a powerful tool for complex scheduling: By transforming the scheduling problem into a shortest-path problem on a carefully constructed graph, the authors demonstrate a systematic way to find optimal solutions even with numerous constraints.
  • Block concatenation is key to multi-round scheduling: The concept of pre-computing feasible "blocks" of games and then finding optimal ways to concatenate them is an elegant approach to building longer tournament schedules.
  • Trade-offs between constraints and travel distance: The paper clearly shows that stricter constraints, like the weekday-weekend balancing rule, can increase the total travel distance compared to a schedule that only optimizes for distance.

Key Results

The paper successfully generated the official 2013 NPB Central League schedule. This schedule required a total team travel distance of 66,122 kilometers. This represents a significant reduction of over 6,000 kilometers compared to the 2012 schedule, which had a travel distance of 86,364 kilometers. Additionally, the new schedule required 12 fewer trips. The generated schedule satisfied all seven league-wide constraints, including the challenging weekday-weekend balancing rule.

Limitations and Future Work

The authors acknowledge that while their generated schedule is theoretically optimal under the defined constraints, the actual NPB Central League schedule for 2013 had to incorporate additional "hard constraints" (47 in total) related to stadium availability and team preferences. These additional constraints led to a schedule with more violations of the "at-most-two" condition (specifically, two 3-set home stands and five 3-set road trips) and a slightly higher travel distance (80,006 km) than their theoretically best proposal.

Future work could involve exploring how to scale these methods to larger leagues, such as Major League Baseball with its recent realignment into 15-team leagues. The authors also express a desire to continue partnering with the NPB to optimize future seasons, aiming for further economic and environmental benefits.

Summary updated

BibTeX
@inproceedings{hoshino2013balancing,
  author = {Richard Hoshino and Ken-ichi Kawarabayashi},
  title = {{Balancing the Traveling Tournament Problem for Weekday and Weekend Games}},
  booktitle = {IAAI},
  year = {2013},
  doi = {10.1609/aaai.v27i2.18994},
}
Figure