Challenge Traveling Tournament Instances

Last Update: September 16, 2013

Description of the Problem

Better solutions?

If you have a better solution for any instance on this page, please email it to me. Please include the schedule (in any reasonable format).

Luca Di Gaspero and Andrea Schaerf have a validator of solutions. Please use it to confirm your solutions before you submit them!

Variants

A number of researchers have developed variants of the Traveling Tournament Problem. Here are a few for which I am recording best solutions:

NL Instances Description

The rules for the following instances are as follows:

Brazilian Instance

This instance uses cities in the 2003 Brazilian soccer championship, with 24 teams (contributed by Sebastian Urrutia).

Super Instances (added March 11, 2009)

These instances, submitted by Dave Uthus, are from the Super 14 Rugby League, composed of teams from New Zealand, Australia, and South Africa. List of team acronyms: BFN AKL CAN PRE HLM SYD JOH CHC BRI DUR DUN PER CPT WLG

NFL Instances (added December 9, 2005)

These instances, based on teams in the National Football League, provide larger instances for experimentation. Here are the Names for the 32 team instance. Smaller instances are just the first entries in the 32 team instance. Here is a Map of the 32 team instance. Thanks to Sean Forman for his TSP Generator that makes generating these instances very, very easy!

Galaxy Instances (added July 22, 2009)

These instances use the three dimensional distances that arise from taking distances between stars (in light years). Names are given based on the constellation the star appears in (the galaxy instances take the initial entries in the file corresponding the instance size). Instances created by Dave Uthus. Thanks to Miyashiro and Imahori for the independent lower bounds.

Circular Distance Instances

One aspect of the hardness of this problem is the embedded traveling salesman aspects. To explore this effect, "circular distance" matrices have a trivial, unique TSP solution. Number the n nodes 0..n-1. The distance between i and j, for i>j is min {i-j,j-i+n}. The optimal tour is 0..n-1. What is the optimal TTP for

Unless noted, repeaters are not allowed.

Constant Distance Matrix

What if the distance is simpler still? Suppose the distance between all cities is 1. Now the goal is simply to minimize the number of trips. Repeaters are not allowed.

Mirrored Instances

One common practical requirement in scheduling a double round robin schedule is to "mirror" the schedule: if A plays at B in the first half of the schedule, then B plays at A in the corresponding slot in the second half. The instances above can be used for this problem.

Links