Challenge Traveling Tournament Instances

Last Update: July 31, 2008

Description of the Problem

• "Traveling Tournament Problem: Description and Benchmarks" Short Version for CP 2001
• Longer Version
• "Solving the Traveling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach"" PATAT 2002

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!

NL Instances Description

The rules for the following instances are as follows:

• Double round robin (A at B and B at A): n teams need 2*n-2 slots.
• No more than three consecutive home or three consecutive road games for any team
• No repeaters (A at B, followed immediately by B at A)
• Objective is to minimize distance traveled (assume teams begin in their home city and must return there after the tournament)
• City names are in the order ATL NYM PHI MON FLA PIT CIN CHI STL MIL HOU COL SF SD LA ARI where NLx takes the first x cities.
• Data files contain the distance matrix (square, symmetric).

• NL4. 4 teams. Data set.
  Feasible Solution: 8276
  Lower Bound: 8276

  
  
   ATL  NYM  PHI  MON 
   ---  ---  ---  --- 
    PHI  MON @ATL @NYM
    NYM @ATL  MON @PHI
    MON @PHI  NYM @ATL
   @PHI @MON  ATL  NYM
   @NYM  ATL @MON  PHI
   @MON  PHI @NYM  ATL
  

• NL6. 6 teams. Data set.
  Feasible Solution: 23978 (Trick May 1, 1999), 23916 (Easton May 7, 1999)
  Lower Bound: 22969 (Trick May 1, 1999), 23916 (Easton, September 27, 1999)

  Slot	ATL	NYM	PHI	MON	FLA	PIT
  
  0	FLA	@PIT	@MON	PHI	@ATL	NYM
  1	NYM	@ATL	FLA	@PIT	@PHI	MON
  2	PIT	@FLA	MON	@PHI	NYM	@ATL
  3	@PHI	MON	ATL	@NYM	PIT	@FLA
  4	@MON	FLA	@PIT	ATL	@NYM	PHI
  5	@PIT	@PHI	NYM	FLA	@MON	ATL
  6	PHI	@MON	@ATL	NYM	@PIT	FLA
  7	MON	PIT	@FLA	@ATL	PHI	@NYM
  8	@NYM	ATL	PIT	@FLA	MON	@PHI
  9	@FLA	PHI	@NYM	PIT	ATL	@MON
  
  

   ATL  NYM  PHI  MON  FLA  PIT 
   ---  ---  ---  ---  ---  --- 
   @FLA @PHI  NYM  PIT  ATL @MON
   @PHI  PIT  ATL @FLA  MON @NYM
    MON @FLA  PIT @ATL  NYM @PHI
    NYM @ATL @MON  PHI @PIT  FLA
   @PIT  PHI @NYM  FLA @MON  ATL
   @MON @PIT  FLA  ATL @PHI  NYM
   @NYM  ATL  MON @PHI  PIT @FLA
    PIT  MON @FLA @NYM  PHI @ATL
    PHI  FLA @ATL @PIT @NYM  MON
    FLA @MON @PIT  NYM @ATL  PHI
  

• NL8. 8 teams. Data set.
  Feasible Solution: 41505 (Easton June 4, 1999), 41113 (Easton Jan 27, 2000), 40416 (Cardemil, July 2 2002), 39947 (Zhang, August 19 2002), 39721 (Easton, August 25 2002)
  Lower Bound: 38760 (Trick Dec 15, 2000), 38870 (Easton Jan 2, 2001), 39479 (Easton Feb 26, 2002), 39721 (Irnich and Schrempp, June 24 2008)

  	Atl	Nym	Phi	Mon	Fla	Pit	Cin	Chi
  1	FLA	@PIT	@CIN	CHI	@ATL	NYM	PHI	@MON
  2	PIT	CHI	@FLA	CIN	PHI	@ATL	@MON	@NYM
  3	MON	CIN	CHI	@ATL	PIT	@FLA	@NYM	@PHI
  4	@PIT	@CHI	CIN	@FLA	MON	ATL	@PHI	NYM
  5	@CHI	@CIN	MON	@PHI	@PIT	FLA	NYM	ATL
  6	@CIN	PHI	@NYM	PIT	@CHI	@MON	ATL	FLA
  7	CHI	PIT	@MON	PHI	@CIN	@NYM	FLA	@ATL
  8	CIN	MON	PIT	@NYM	CHI	@PHI	@ATL	@FLA
  9	@MON	@PHI	NYM	ATL	CIN	CHI	@FLA	@PIT
  10	@NYM	ATL	@PIT	FLA	@MON	PHI	@CHI	CIN
  11	@PHI	FLA	ATL	@CHI	@NYM	@CIN	PIT	MON
  12	NYM	@ATL	FLA	@CIN	@PHI	@CHI	MON	PIT
  13	PHI	@FLA	@ATL	@PIT	NYM	MON	CHI	@CIN
  14	@FLA	@MON	@CHI	NYM	ATL	CIN	@PIT	PHI
  

• NL10. 10 teams Data set
  Feasible Solution: 68691 (Rottembourg and Laburthe June 2001), 66369 (Dorrepaal, June 21 2002), 66037 (Cardemil, July 2 2002), 64597 (Zhang August 6, 2002), 61608 (Zhang August 19, 2002), 59583 (Van Hentenryck January 14, 2003), 59436 (Langford, June 13, 2005 solution)
  Lower Bound: 56506 (Waalewijn July 2001), 57500 (Easton June 2002), 57817 (Irnich and Schrempp, June 24 2008)
• NL12. 12 teams Data set
  Feasible Solution: 143655 (Rottembourg and Laburthe May 2001), 138850 (Larichi, Lapierre, and Laporte July 8 2002), 125803 (Cardemil, July 2 2002), 119990 (Dorrepaal July 16, 2002), 119012 (Zhang, August 19 2002), 118955 (Cardemil, November 1 2002), 114153 (Van Hentenryck January 14, 2003), 113090 (Van Hentenryck February 26, 2003), 112800 (Van Hentenryck June 26, 2003), 112684 (Langford February 16, 2004), 112549 (Langford February 27, 2004), 112298 (Langford March 12, 2004), 111248 (Van Hentenryck May 13, 2004), 110729 (Van Hentenryck and Vergados, May 30 2007).
  Lower Bound: 107483 (Waalewign August 2001), 107494 (Melo, Ribeiro, and Urrutia July 15 2006), 107548 (Mitchell, Trick and Waterer July 31 2008).
• NL14. 14 teams Data set
  Feasible Solution: 301113 (Rottembourg and Laburthe June 2001), 262010 (Larichi, Lapierre, Laport July 8 2002), 216108 (Cardemil, July 2 2002), 207075 (Zhang, August 28 2002), 205894 (Cardemil, November 20 2002), 195555 (Van Hentenryck January 14, 2003), 190368 (Van Hentenryck February 26, 2003), 190056 (Langford April 22, 2004), 189766 (Van Hentenryck May 13, 2004), 189759 (Dorrepaal and Chackman, April 13, 2005), 188728 (Van Hentenryck and Vergados, May 18 2006).
  Lower Bound: 182797 (Waalewign August 2001)
• NL16. 16 teams. Data set.
  Feasible Solution: 312623 (Easton January 2002), 308413 (Cardemil, July 2 2002), 301256 (Zhang August 6 2002), 293175 (Zhang, August 28 2002), 284235 (Shen, October 16 2002), 281660 (Shen, January 6 2003) 277766 (Van Hentenryck January 14, 2003), 273802 (Van Hentenryck February 26 2003), 272,902 (Langford, January 16, 2004), 267,194 (Van Hentenryck, June 26, 2003), 263772 (Van Hentenryck and Vergados, May 18 2006), 261687 (Van Hentenryck and Vergados, May 30 2007).
  Lower Bound: 248852 (Easton January 2002), 249477 (Melo, Ribeiro, and Urrutia July 15 2006) [Note: Until December 30, 2000, the instance was slightly incorrect: The NY-ARI distance did not match the ARI-NY distance. This has been corrected.]
• Solution listing from Cardemil July 2, 2002.
• Solution listing from Zhang Xingwen August 6, 2002.
• Solution listing from Zhang Xingwen August 19, 2002.
• Solution listing from Zhang Xingwen August 28, 2002.

  "Van Hentenryck" is Anagnostopoulos, Michel, Van Hentenryck, and Vergados

Brazilian Instance

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

• 24 teams Data Set
  Feasible Solution: 506433 (Urrutia and Ribeiro August 26, 2004) (mirrored), 503158 (Urritia, Ribeiro and Araujo, March 11 2005) (mirrored), 500,756 (Van Hentenryck and Vergados, May 30 2007) (mirrored)

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!

• NFL16 16 teams.
  Feasible Solution: 241973 (Langford, Dec 30 2005), 241264 (Di Gaspero and Schaerf, January 27, 2006), 241214 (Langford, March 13 2006), 238581 (Di Gaspero and Schaerf, March 27, 2006), 237428 (Langford, April 28, 2006), 235930 (Langford, October 10, 2006), 231,483 (Van Hentenryck and Vergados, May 30 2007).
  Lower Bound: 223800 (Melo, Ribeiro, and Urrutia July 15 2006)
• NFL18 18 teams.
  Feasible Solution: 301546 (Di Gaspero and Schaerf, Jan 09 2006), 299192 (Langford, Jan 10 2006), 298705 (Di Gaspero and Schaerf, March 3 2006), 296638 (Langford, April 18 2006), 282,258 (Van Hentenryck and Vergados, May 30 2007).
  Lower Bound: 272834 (Melo, Ribeiro, and Urrutia July 15 2006)
• NFL20 20 teams.
  Feasible Solution: 361878 (Di Gaspero and Schaerf, Jan 09 2006), 353927 (Langford, Jan 10 2006), 352947 (Di Gaspero and Schaerf, Feb 16 2006), 350256 (Langford, April 24, 2006), 346324 (Langford, April 25, 2006), 332041 (Van Hentenryck and Vergados, May 30 2007).
  Lower Bound: 316721 (Melo, Ribeiro, and Urrutia July 15 2006)
• NFL22 22 teams.
  Feasible Solution: 439626 (Di Gaspero and Schaerf, Jan 09 2006), 426977 (Langford, Jan 18, 2006), 418,086 (Urrutia and Ribeiro, January 22 2006), 412812 (Langford, May 12, 2006), 402534 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 378813 (Melo, Ribeiro, and Urrutia July 15 2006)
• NFL24 24 teams.
  Feasible Solution: 499017 (Di Gaspero and Schaerf, Jan 09 2006), 490,528 (Langford, Jan 20, 2006), 467,135 (Urrutia and Ribeiro, January 22 2006), 463,657 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 431,226 (Trick, June 22, 2007)
• NFL26 26 teams. Feasible Solution: 590,497 (Di Gaspero and Schaerf, January 27 2006), 573,596 (Langford, January 27, 2006), 554,670 (Urrutia and Ribeiro, February 10 2006), 551,033 (Langford, June 29 2006), 536,792 (Van Hentenryck and Vergados, May 30 2007).
  Lower Bound: 495,982 (Trick, June 22, 2007)
• NFL28 28 teams. Feasible Solution: 681,197 (Di Gaspero and Schaerf, January 27, 2006), 669,320 (Langford, February 7, 2006), 618,801 (Urrutia and Ribeiro, February 10 2006), 609788 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
  Lower Bound: 560,697 (Trick, June 22, 2007)
• NFL30 30 teams. Feasible Solution: 847,011 (Di Gaspero and Schaerf, January 27 2006), 740,458 (Urrutia and Ribeiro, February 10 2006), 739,697 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
  Lower Bound: 688,875 (Trick, June 22, 2007)
• NFL32 32 teams. Feasible Solution: 1,020,966 (Di Gaspero and Schaerf, January 27 2006), 924,559 (Urrutia and Ribeiro, February 10 2006), 914,620 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
  Lower Bound: 836,031 (Trick, June 22, 2007)

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

• Unconstrained: No limits on length of home/away trips
• Constrained: no more than 3 consecutive home or away

Unless noted, repeaters are not allowed.

• circ4 (constrained)
  Feasible Solution: 20 (Trick May 2001)
  Lower Bound: 20 (Trick May 2001)

     T1  T2  T3  T4
    --- --- --- ---
     T4  T3 @T2 @T1
     T3  T4 @T1 @T2
     T2 @T1 @T4  T3
    @T4 @T3  T2  T1
    @T3 @T4  T1  T2
    @T2  T1  T4 @T3
  

• circ4 (unconstrained, with repeaters)
  Feasible Solution: 20 (Langford, June 24, 2005)
  Lower Bound: 20 (same as constrained)
• circ6 (constrained)
  Feasible Solution: 64 (Trick May 2001)
  Lower Bound: 64 (Trick May 2001)

     T1  T2  T3  T4  T5  T6
    --- --- --- --- --- ---
     T4 @T3  T2 @T1  T6 @T5
     T5  T4 @T6 @T2 @T1  T3
     T3  T5 @T1 @T6 @T2  T4
    @T2  T1  T5  T6 @T3 @T4
     T2 @T1  T6 @T5  T4 @T3
    @T3  T6  T1  T5 @T4 @T2
    @T4  T3 @T2  T1 @T6  T5
    @T5 @T6  T4 @T3  T1  T2
     T6 @T5 @T4  T3  T2 @T1
    @T6 @T4 @T5  T2  T3  T1
  

• circ6 (unconstrained, with repeaters)
  Feasible Solution: 54 (Langford, June 24, 2005)
  Lower Bound: 54 (Irnich and Schrempp, June 24 2008)
• circ6 (unconstrained, without repeaters)
  Feasible Solution: 56 (Langford, July 6, 2005)
  Lower Bound: 56 (Irnich and Schrempp, June 24 2008)
• circ8 (constrained)
  Feasible Solution: 148 (Rottembourg and Laburthe June 2001), 146 (Waalewijn), 136 (Cardemil, July 2 2002), 132 (Zhang, August 28 2002) November 2001)
  Lower Bound: 128 (Trick May 2001), 130 (Irnich and Schrempp, June 24 2008)
• circ8 (unconstrained, with repeaters)
  Feasible Solution: 100 (Langford, June 24, 2005)
  Lower Bound: 92 (Irnich and Schrempp, June 24 2008)
• circ8 (unconstrained, without repeaters)
  Feasible Solution: 102 (Langford, July 6, 2005)
  Lower Bound: 85 (Irnich and Schrempp, June 24 2008)
• circ10(constrained)
  Feasible Solution: 288 (Rottembourg and Laburthe May 2001), 282 (Cardemil, July 2 2002), 280 (Zhang August 6, 2002), 266 (Zhang, August 19 2002), 258 (Shen January 6 2003), 254 (Shen Feb 4 2003), 246 (Zhang January 23 2005), 244 (Schaerf and Di Gaspero Mar 30 2005), 242 (Langford, Jun 15, 2005 solution)
  Lower Bound: 220 (Trick May 2001), 228 (Melo, Ribeiro, and Urrutia July 15 2006)
• circ10 (unconstrained, with repeaters)
  Feasible Solution: 166 (Langford, June 24, 2005)
  Lower Bound:
• circ10 (unconstrained, without repeaters)
  Feasible Solution: 168 (Langford, July 6, 2005)
  Lower Bound:
• circ12 (constrained)
  Feasible Solution: 484 (Cardemil, July 2 2002), 448 (Zhang, August 28, 2002), 446 (Shen January 6 2003), 440 (Van Hentenryck February 26, 2003), 436 (Shen March 11 2003), 420 (Van Hentenryck June 26, 2003), 408 (Zhang January 23 2005), 404 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 384 (Trick May 2001)
• circ12 (unconstrained, with repeaters)
  Feasible Solution: 248 (Langford, June 24, 2005)
  Lower Bound:
• circ12 (unconstrained, without repeaters)
  Feasible Solution: 250 (Langford, July 6, 2005)
  Lower Bound:
• circ14 (constrained)
  Feasible Solution: 768 (Cardemil, July 2 2002), 752 (Zhang, August 6, 2002), 712 (Zhang, August 19 2002), 686 (Shen, Jan 21 2003), 682 (Van Hentenryck February 26, 2003), 670 (Van Hentenryck May 13, 2004), 654 (Zhang January 23 2005), 632 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 588 (Trick May 2001)
• circ14 (unconstrained, with repeaters)
  Feasible Solution: 344 (Langford, June 24, 2005)
  Lower Bound:
• circ14 (unconstrained, without repeaters)
  Feasible Solution: 346 (Langford, July 6, 2005)
  Lower Bound:
• circ16 (constrained)
  Feasible Solution: 1120 (Cardemil, July 2 2002), 1044 (Zhang, August 28 2002), 984 (Shen, October 16 2002), 976 (Van Hentenryck June 26, 2003), 928 (Zhang January 23 2005), 916 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 832 (Trick May 2001), 846 (Melo, Ribeiro, and Urrutia July 15 2006)
• circ16 (unconstrained, with repeaters)
  Feasible Solution: 462 (Langford, June 24, 2005)
  Lower Bound:
• circ16 (unconstrained, without repeaters)
  Feasible Solution: 464 (Langford, July 6, 2005)
  Lower Bound:
• circ18 (constrained)
  Feasible Solution: 1638 (Cardemil, July 2 2002), 1558 (Zhang, August 6, 2002), 1442 (Zhang, August 28 2002), 1420 (Van Hentenryck February 26 2003), 1398 (Urrutia and Ribeiro, January 21, 2004); 1364 (Urrutia and Ribeiro, April 30, 2004), 1358 (Urrutia and Ribeiro, September 17, 2004), 1356 (Zhang January 23 2005), 1308 (Urritia, Ribeiro and Araujo, March 11 2005), 1306 (Urrutia and Ribeiro, May 12 2005), 1304 (Van Hentenryck and Vergados, May 18 2006), 1294 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 1188 (Trick May 2001)
• circ18 (unconstrained, with repeaters)
  Feasible Solution: 614 (Langford, June 24, 2005), 596 (Langford, June 29, 2005)
  Lower Bound:
• circ18 (unconstrained, without repeaters)
  Feasible Solution: 590 (Langford, July 6, 2005)
  Lower Bound:
• circ20 (constrained)
  Feasible Solution: 2218 (Cardemil, July 2 2002), 2098 (Zhang, August 6, 2002), 1990 (Zhang, August 28 2002), 1954 (Shen, Jan 21 2003), 1936 (Shen Feb 4 2003), 1908 (Van Hentenryck February 26 2003), 1898 (Urrutia and Ribeiro, January 21, 2004), 1882 (Urrutia and Ribeiro, April 30, 2004), 1842 (Zhang January 23 2005), 1760 (Van Hentenryck and Vergados, May 18 2006), 1732 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 1600 (Melo, Ribeiro, and Urrutia July 15 2006)
• circ20 (unconstrained, with repeaters)
  Feasible Solution: 760 (Langford, June 24, 2005), 756 (Langford, June 29, 2005)
  Lower Bound:
• circ20 (unconstrained, without repeaters)
  Feasible Solution: 762 (Langford, July 6, 2005)
  Lower Bound:
• Solution listing from Cardemil July 2, 2002.
• Solution listing from Zhang Xingwen August 6, 2002.
• Solution listing from Zhang Xingwen August 19, 2002.
• Solution listing from Zhang Xingwen August 28, 2002.
• Solution listing from Glenn Langford June 24, 2005 for unconstrained instances.

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.

• Unconstrained: No limits on length of home/away trips. Urrutia and Ribeiro show that the optimal in this case (mirrored, non-mirrored, with repeaters and/or without repeaters) is n^2 +n/2 -1. I list these values after the constrained values.
• Constrained: no more than 3 consecutive home or away

• CON4 4 teams. UB: 17 (Urrutia and Ribeiro, August 26, 2004), LB: 17 (Rasmussen and Trick, May 24 2005) Unconstrained: 17
• CON6 6 teams. UB: 48 (Urrutia and Ribeiro, August 26, 2004), 43 (Schaerf and Di Gaspero, Jan 15 2005). LB: 43 (Rasmussen and Trick, May 24, 2005) Unconstrained: 38
• CON8 8 teams. UB: 80 (Urrutia and Ribeiro, August 26, 2004). LB: 80 (Rasmussen and Trick, May 24, 2005) Unconstrained: 67
• CON10 10 teams. UB: 130 (Urrutia and Ribeiro, August 26, 2004), 124 (Schaerf and Di Gaspero, Jan 15, 2005). LB: 124 (Rasmussen and Trick, May 24, 2005) Unconstrained: 104
• CON12 12 teams. UB: 192 (Urrutia and Ribeiro, August 26, 2004), 182 (Schaerf and Di Gaspero, Jan 15, 2005), 181 (Schaerf and Di Gaspero, Mar 30 2005). LB: 181 (Rasmussen and Trick, May 24, 2005) Unconstrained: 149
• CON14 14 teams. UB: 256 (Urrutia and Ribeiro, August 26, 2004), 253 (Schaerf and Di Gaspero, Jan 15, 2005), 252 (Schaerf and Di Gaspero, Mar 30, 2005). LB: 252 (Rasmussen and Trick, May 24, 2005) Unconstrained: 202
• CON16 16 teams. UB: 342 (Urrutia and Ribeiro, August 26, 2004), 331 (Schaerf and Di Gaspero, Jan 15, 2005), 329 (Schaerf and Di Gaspero, Mar 30 2005), 327 (Rasmussen and Trick, May 24 2005). LB: 327 (Rasmussen and Trick, May 24, 2005) Constrained: 263
• CON18 18 teams. UB: 434 (Urrutia and Ribeiro, August 26, 2004), 423 (Schaerf and Di Gaspero, Jan 15, 2005), 419 (Schaerf and Di Gaspero, Mar 30 2005), 418 (Schaerf and Di Gaspero, June 24, 2005), 417 (Van Hentenryck and Vergados, May 18 2006). LB: 414 (Fujiwara, Imahori, Matsui, and Miyashiro July 8 2006). Unconstrained: 332
• CON20 20 teams. UB: 526 (Urrutia and Ribeiro, August 26, 2004), 525 (Schaerf and Di Gaspero, Jan 15, 2005), 522 (Schaerf and Di Gaspero, Mar 30, 2005), 521 (Schaerf and Di Gaspero, July 18, 2005), 520 (Van Hentenryck and Vergados, May 18 2006). LB: 520 (Fujiwara, Imahori, Matsui, and Miyashiro July 8 2006).Unconstrained: 409
• CON22 22 teams. UB: 632 (Schaerf and Di Gaspero, Oct 4, 2005), 628 (Van Hentenryck and Vergados, May 18 2006), 626 (Fujiwara, Imahori, Matsui, and Miyashiro July 8 2006). LB: 626 (Fujiwara, Imahori, Matsui, and Miyashiro July 8 2006).
• CON24 24 teams. UB: 757 (Schaerf and Di Gaspero, Oct 4, 2005), 750 (Van Hentenryck and Vergados, May 18 2006), 749 (Van Hentenryck and Vergados, May 30 2007). LB: 744 (Fujiwara, Imahori, Matsui, and Miyashiro July 8 2006).

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.

• circ4 20 Urrutia and Ribeiro, April 30, 2004;
• circ6 72 Urrutia and Ribeiro, April 30, 2004;
• circ8 140 Urrutia and Ribeiro, July 16, 2003; Lower Bound: 140 (Cheung April 15 2007)
• circ10 280 Urrutia and Ribeiro, July 16, 2003; 276 Urrutia and Ribeiro, Jan 10, 2005; 272 Urritia, Ribeiro and Araujo, March 11, 2005; LB: 240 Urrutia and Ribeiro May 12 2005.
• circ12 460 Urrutia and Ribeiro, July 16, 2003; 456, Urrutia and Ribeiro, January 21, 2004, 432 (Van Hentenryck and Vergados, May 18 2006)
• circ14 716 Urrutia and Ribeiro, July 16, 2003; 714, Urrutia and Ribeiro, January 21, 2004; 696 Van Hentenryck and Vergados, May 18 2006, 672 (Van Hentenryck and Vergados, May 30 2007). Lower Bound: 590 (Urrutia and Ribeiro, June 14, 2006)
• circ16 1062 Urrutia and Ribeiro, July 16, 2003; 1046, Urrutia and Ribeiro, January 21, 2004; 1004, Urrutia and Ribeiro April 30, 2004; 990, Urrutia and Ribeiro September 17, 2004; 984 Urritia, Ribeiro and Araujo, March 11 2005; 980 Urrutia and Ribeiro, May 12 2005; 978 Urrutia and Ribeiro December 19 2005; 968 Van Hentenryck and Vergados, May 18 2006. LB: 876 (Melo, Ribeiro, and Urrutia July 15 2006)
• circ18 1450 Urrutia and Ribeiro, July 16, 2003; 1398, Urrutia and Ribeiro, January 21, 2004; 1364 Urrutia and Ribeiro April 30, 2004; 1358 Urrutia and Ribeiro September 17, 2004; 1308 Urritia, Ribeiro and Araujo, March 11 2005; 1306, Urrutia and Ribeiro, May 12, 2005
• circ20 1996 Urrutia and Ribeiro, July 16, 2003; 1898, Urrutia and Ribeiro, January 21, 2004; 1882, Urrutia and Ribeiro April 30, 2004, 1852 (Van Hentenryck and Vergados, May 18 2006)
• nl4 8276 Urrutia and Ribeiro, April 30, 2004;
• nl4 26588 Urrutia and Ribeiro, April 30, 2004;
• nl8 41928 Urrutia and Ribeiro, July 16, 2003; Lower Bound 41928 (Cheung April 15 2007)
• nl10 64976 Urrutia and Ribeiro, July 16, 2003; 64024, Urrutia and Ribeiro, January 21, 2004; 63832, Urrutia and Ribeiro April 30, 2004; LB: 58190, Urrutia and Ribeiro May 12, 2005, 58277 (Melo, Ribeiro, and Urrutia July 15 2006), 58769 (Cheung April 3 2008)
• nl12 120696 Urrutia and Ribeiro, July 16, 2003; 120655, Urrutia and Ribeiro, January 21, 2004, 119608 (Van Hentenryck and Vergados, May 18 2006). LB: 110519 (Melo, Ribeiro, and Urrutia July 15 2006), 111064 (Cheung April 3 2008)
• nl14 209084 Urrutia and Ribeiro, July 16, 2003; 208086, Urrutia and Ribeiro, January 21, 2004, 199363 (Van Hentenryck and Vergados, May 18 2006). LB: 182996 (Melo, Ribeiro, and Urrutia July 15 2006), 183631 (Cheung April 3 2008)
• nl16 295693 Urrutia and Ribeiro, July 16, 2003; 293645, Urrutia and Ribeiro, January 21, 2004; 285614, Urrutia and Ribeiro, April 30, 2004; 281161 Urrutia and Ribeiro, September 17, 2004; 280174 Urritia, Ribeiro and Araujo March 11 2005; 279618 Urrutia and Ribeiro May 12, 2005, 279077 (Van Hentenryck and Vergados, May 18 2006), 278,305 (Van Hentenryck and Vergados, May 30 2007) LB: 253957 (Melo, Ribeiro, and Urrutia July 15 2006), 254242 (Cheung April 3 2008)
• nfl16 251,289 (Urrutia and Ribeiro, January 22 2006), 248,818 (Van Hentenryck and Vergados, May 30 2007). LB:228251 (Melo, Ribeiro, and Urrutia July 15 2006), 228446 (Cheung April 3 2008)
• nfl18 299,903 (Urrutia and Ribeiro, January 22 2006), 299,134 (Araujo, Urrutia, and Ribeiro, June 21, 2007). LB: 276395 (Melo, Ribeiro, and Urrutia July 15 2006), 276519 (Cheung April 3 2008)
• nfl20 359,748 (Urrutia and Ribeiro, January 22 2006). LB: 316727 (Cheung April 3 2008)
• nfl22 418,086 (Urrutia and Ribeiro, January 22 2006), 418,022 (Araujo, Urrutia, and Ribeiro, June 21, 2007). LB: 384001 (Cheung April 3 2008)
• nfl24 467,135 (Urrutia and Ribeiro, January 22 2006), 465,863 (Van Hentenryck and Vergados, May 30 2007), 465,491 (Araujo, Urrutia, and Ribeiro, June 21, 2007). LB: 434598 (Cheung April 3 2008)
• nfl26 554,670 (Urrutia and Ribeiro, February 10 2006), 548,643 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
• nfl28 618,801 (Urrutia and Ribeiro, February 10 2006), 609788 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
• nfl30 740,458 (Urrutia and Ribeiro, February 10 2006), 739,697 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
• nfl32 924,559 (Urrutia and Ribeiro, February 10 2006), 914,620 (Araujo, Urrutia, and Ribeiro, June 21, 2007)
• CON4 4 teams. UB: 17 (Urrutia and Ribeiro, August 26, 2004). LB (mirror): 17 (Urrutia and Ribeiro, August 26, 2004)
• CON6 6 teams. UB: 48 (Urrutia and Ribeiro, August 26, 2004). LB (mirror): 48 (Urrutia and Ribeiro, August 26, 2004)
• CON8 8 teams. UB: 80 (Urrutia and Ribeiro, August 26, 2004). LB (mirror): 80 (Urrutia and Ribeiro, August 26, 2004)
• CON10 10 teams. UB: 130 (Urrutia and Ribeiro, August 26, 2004). LB (mirror): 130 (Urrutia and Ribeiro, August 26, 2004)
• CON12 12 teams. UB: 192 (Urrutia and Ribeiro, August 26, 2004). LB (mirror): 192 (Urrutia and Ribeiro, August 26, 2004)
• CON14 14 teams. UB: 256 (Urrutia and Ribeiro, August 26, 2004), 253 (Rasmussen and Trick, May 24, 2005). LB (mirror): 252 (Urrutia and Ribeiro, August 26, 2004), 253 (Rasmussen and Trick, May 24, 2005)
• CON16 16 teams. UB: 342 (Urrutia and Ribeiro, August 26, 2004). LB (mirror): 342 (Urrutia and Ribeiro, August 26, 2004)
• CON18 18 teams. UB: 434 (Urrutia and Ribeiro, August 26, 2004), 432 (Rasmussen and Trick, May 24, 2005). LB (mirror): 432 (Urrutia and Ribeiro, August 26, 2004)
• CON20 20 teams. UB: 526 (Urrutia and Ribeiro, August 26, 2004), 524 (Urrutia and Ribeiro December 19 2005), 522 (Van Hentenryck and Vergados, May 18 2006). LB (mirror): 520 (Urrutia and Ribeiro, August 26, 2004)
• CON22 22 teams. UB: 650 (Rasmussen and Trick July 20, 2005) LB: 650
• CON24 24 teams. UB: 768 (Rasmussen and Trick July 20, 2005), LB: 768

Links

• See the Traveling Tournament Java Program by Onno Waalewijn.