Traveling tournament problem

Last updated

The traveling tournament problem (TTP) is a mathematical optimization problem. The question involves scheduling a series of teams such that:

  1. Each team plays every other team twice, once at home and once in the other's stadium.
  2. No team plays the same opponent in two consecutive weeks.
  3. No team plays more than three games in a row at home, or three games in a row on the road.

A matrix is provided of the travel distances between each team's home city. All teams start and end at their own home city, and the goal is to minimize the total travel distance for every team over the course of the whole season. [1]

There have been many papers published on the subject, and a contest exists to find the best solutions for certain specific schedules. [2]

Related Research Articles

<span class="mw-page-title-main">Southeastern Conference</span> Collegiate athletics conference operating primarily in the southeastern United States

The Southeastern Conference (SEC) is an American college athletic conference whose member institutions are located primarily in the South Central and Southeastern United States. Its fourteen members include the flagship public universities of ten states, three additional public land-grant universities, and one private research university. The conference is headquartered in Birmingham, Alabama. The SEC participates in the National Collegiate Athletic Association (NCAA) Division I in sports competitions; for football it is part of the Football Bowl Subdivision (FBS), formerly known as Division I-A.

A sports league is a group of individual athletes, sports teams or clubs who form a league to compete against each other and gain points in a specific sport. At its simplest, it may be a local group of amateur athletes who form teams among themselves and compete on weekends; at its most complex, it can be an international professional league making large amounts of money and involving dozens of teams and thousands of players.

In an organized sports league, a typical season is the portion of one year in which regulated games of the sport are in session: for example, in Major League Baseball the season lasts approximately from the last week of March to the last week of September. In other team sports, like association football or basketball, it is generally from August or September to May although in some countries - such as Northern Europe or East Asia - the season starts in the spring and finishes in autumn, mainly due to weather conditions encountered during the winter.

<span class="mw-page-title-main">Round-robin tournament</span> Type of sports tournament

A round-robin tournament is a competition in which each contestant meets every other participant, usually in turn. A round-robin contrasts with an elimination tournament, in which participants/teams are eliminated after a certain number of losses.

<span class="mw-page-title-main">Exhibition game</span> Sporting event wherein the result has no external impact

An exhibition game is a sporting event whose prize money and impact on the player's or the team's rankings is either zero or otherwise greatly reduced. In team sports, matches of this type are often used to help coaches and managers select and condition players for the competitive matches of a league season or tournament. If the players usually play in different teams in other leagues, exhibition games offer an opportunity for the players to learn to work with each other. The games can be held between separate teams or between parts of the same team.

<span class="mw-page-title-main">Danish Superliga</span> Top division association football league in Denmark

The Danish Superliga is the current Danish football championship tournament, and administered by the Danish Football Association. It is the highest football league in Denmark and is currently contested by 12 teams each year, with two teams relegated.

The Major League Baseball (MLB) season schedule generally consists of 162 games for each of the 30 teams in the American League (AL) and National League (NL), played over approximately six months – a total of 2,430 games, plus the postseason. The regular season runs from late March/early April to late September/early October, followed by the postseason which can run to early November. The season begins with the official Opening Day, and, as of 2018, runs 26½ weeks through the last Sunday of September or first Sunday of October. One or more International Opener games may be scheduled outside the United States or Canada before the official Opening Day. It is possible for a given team to play a maximum of 22 games in the postseason in a given year, provided the team is a wild card and advances to each of the Division Series, Championship Series, and World Series with each series going the distance.

There are a number of formats used in various levels of competition in sports and games to determine an overall champion. Some of the most common are the single elimination, the best-of- series, the total points series more commonly known as on aggregate, and the round-robin tournament.

The selection process for college basketball's NCAA Division I Men's and Women's Basketball Tournaments determine which teams will enter the tournaments and their seedings and matchups in the knockout bracket. Currently, thirty-two (32) teams gain automatic entry through winning their conference's championship. The remaining teams rely on the selection committee to award them an at-large bid in the tournament. The selection process primarily takes place on Selection Sunday and the days leading up to it. Selection Sunday is also when the men's brackets and seeds are released to the public. After beginning in 2022, the women's championship brackets and seeds are also announced on Sunday. Prior to the expansion of the bracket from 64 to 68 teams the women's championship brackets and seeds were announced one day later, on Selection Monday.

The Regional Four Day Competition, formerly known as Shell Shield and Carib Beer Cup, is the first-class cricket competition in the West Indies. It is administered by the Cricket West Indies. In the 2013-2014 season the winner of the tournament was awarded the WICB President's Trophy while the winners of the knockout competition were awarded the George Headley/Everton Weekes trophy. In a few previous seasons the winners of the tournament were awarded the Headley/Weekes trophy. From the 2017–18, the Competition had been sponsored by Digicel and was known as the Digicel Four Day Championship. Since 2019-20, the competition has been known as the West Indies Championship.

The season structure of the National Hockey League (NHL) is divided into the pre-season, regular season, and the Stanley Cup playoffs. In the pre-season, which is generally held during the last two weeks of September, each team plays several not-for-the-record exhibition games. In the regular season, which generally runs from early October through early April, teams play 82 games which determine their standings. The three highest-placed teams in each division and two wild card teams per conference enter the playoff elimination tournament to determine the Stanley Cup champion.

The Eastern Australian Football League is an Australian rules football competition in the Eastern United States of America and a division of the United States Australian Football League.

<span class="mw-page-title-main">Venezuelan Professional Baseball League</span> Venezuelan national professional baseball sports league

The Venezuelan Professional Baseball League or Liga Venezolana de Béisbol Profesional (LVBP) is the professional baseball league in Venezuela. The league's champion takes part in the Caribbean Series each year.

The National Football League preseason is the period each year during which NFL teams play several not-for-the-record exhibition games before the actual "regular" season starts. Beginning with the featured Pro Football Hall of Fame game in early August, three weekends of exhibition games are played in the NFL to date. The start of the preseason is intrinsically tied to the last week of training camp.

The National Football League (NFL) regular season begins on the weekend following the first Monday of September and ends in early January, after which that season's playoffs tournament begins. It consists of 272 games, with each of the NFL's 32 teams playing 17 games during an 18-week period with one "bye" week off.

The Yellow Sea Cup, is an annual rugby union competition currently involving clubs from four cities in China and South Korea.

The 1998 NCAA Division III men's ice hockey tournament was the culmination of the 1997–98 season, the 15th such tournament in NCAA history. It concluded with Middlebury defeating Wisconsin-Stevens Point in the championship game 2-1. All Quarterfinals matchups were held at home team venues, while all succeeding games were played in Plattsburgh, New York.

The 1999 NCAA Division III Men's Ice Hockey Tournament was the culmination of the 1998–99 season, the 16th such tournament in NCAA history. It concluded with Middlebury defeating Wisconsin-Superior in the championship game 5-0. All Quarterfinals matchups were held at home team venues, while all succeeding games were played in Norwich, Vermont.

<span class="mw-page-title-main">2021 MPBL Invitational</span>

The 2021 MPBL Invitational, officially known as the Chooks-to-Go MPBL Invitational powered by TM for sponsorship reasons, was an invitational tournament that served as a prelude to the 2022 MPBL season. It commenced on December 11, 2021 and ended on December 23, 2021.

<span class="mw-page-title-main">Impact of the COVID-19 pandemic on baseball</span>

The COVID-19 pandemic has caused disruption to baseball across the world, mirroring its impact across all sports. Leagues across the world experienced delayed starts, cancelled seasons, limited or no fan attendance, game postponements, and other restrictions in 2020 and 2021. Most leagues, including Major League Baseball, began to transition back to a normal schedule with fan attendance in 2021. Since then, few leagues have widespread restrictions in place, but players may still miss time if they contract the virus.

References

  1. "Solving the Traveling Tournament Problem" (PDF).
  2. "Challenge Traveling Tournament Problems". mat.gsia.cmu.edu. Retrieved 2018-06-18.