Challenge Traveling Tournament Instances

Last Update: April 22, 2019

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!

Variants

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

• Non-round robin scheduling proposed by Douglas Moody. In this problem, teams don't play a double round robin but the number of games between them is fixed.
• Relaxed TTP proposed by Renjun Bao and Michael Trick. Here, teams can have one or more "byes" in their schedule.

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; the "unconstrained" entries remove this restriction
• 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)
  Unconstrained Feasible Solution: 19900 (Khelifa, Boughaci, Aimeur, Jan 15 2018)

  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)
  Unconstrained Feasible Solution: 30700 (Khelifa, Boughaci, Aimeur, Jan 15 2018)

  	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), 58831 (Uthus, Riddle, and Guesgen, Feb 11 2009), 59436 (Uthus, Riddle, and Guesgen December 11, 2009)
  Unconstrained feasible solution: 45412 (Khelifa, Boughaci, Aimeur, Jan 15 2018), 45357 (Ben Slimene, Mar 10, 2019), 45309 (Khelifa, Boughaci, Aimeur, April 10, 2019)
• NL12. 12 teams Data set
  Feasible Solution: 143655 (Rottembourg and Laburthe May 2001), 125803 (Cardemil, July 2 2002), 119990 (Dorrepaal July 16, 2002), 119012 (Zhang, August 19 2002), 118955 (Cardemil, November 1 2002), 114153 (Anagnostopoulos, Michel, Van Hentenryck and Vergados January 14, 2003), 113090 (Anagnostopoulos, Michel, Van Hentenryck and Vergados February 26, 2003), 112800 (Anagnostopoulos, Michel, Van Hentenryck and Vergados June 26, 2003), 112684 (Langford February 16, 2004), 112549 (Langford February 27, 2004), 112298 (Langford March 12, 2004), 111248 (Anagnostopoulos, Michel, Van Hentenryck and Vergados 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), 108244 (Uthus, Riddle, and Guesgen, Feb 11 2009), 108629 (Uthus, Riddle, and Guesgen January 6, 2010)
  Unconstrained feasible solution: 79623 (Khelifa, Boughaci, Aimeur, Jan 15 2018)
• 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados January 14, 2003), 190368 (Van Hentenryck February 26, 2003), 190056 (Langford April 22, 2004), 189766 (Anagnostopoulos, Michel, Van Hentenryck and Vergados May 13, 2004), 189759 (Dorrepaal and Chackman, April 13, 2005), 188728 (Van Hentenryck and Vergados, May 18 2006).
  Lower Bound: 182797 (Waalewign August 2001), 183354 (Uthus, Riddle, and Guesgen January 29 2010)
  Unconstrained feasible solution: 125734 (Khelifa, Boughaci, Aimeur, Jan 15 2018)
• 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados January 14, 2003), 273802 (Anagnostopoulos, Michel, Van Hentenryck and Vergados February 26 2003), 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)
  Unconstrained feasible solution: 154623 (Khelifa, Boughaci, Aimeur, Jan 15 2018) [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.

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)

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

• Super4
  Feasible Solution: 63405 (Uthus, Riddle, and Guesgen, Feb 11 2009)
  Lower Bound: 63405 (Uthus, Riddle, and Guesgen, Feb 11 2009)
• Super6
  Feasible Solution: 130365 (Uthus, Riddle, and Guesgen, Feb 11 2009)
  Lower Bound: 130365 (Uthus, Riddle, and Guesgen, Feb 11 2009)
• Super8
  Feasible Solution: 182409 (Uthus, Riddle, and Guesgen, Feb 11 2009)
  Lower Bound: 182409 (Uthus, Riddle, and Guesgen, Feb 11 2009)
• Super10
  Feasible Solution: 316329 (Uthus, Riddle, and Guesgen, Feb 11 2009)
  Lower Bound: 316329 (Uthus, Riddle, and Guesgen, Feb 11 2009)
• Super12
  Feasible Solution: 467267 (Misir, Wauters, Verbeeck, Vanden Berghe, March 30 2009), 465667 (Uthus, Riddle and Guesgen April 29 2009), 463876 (Langford May 8, 2009), 460998 (Shirai and Miyashiro, Jan 29 2016)
  Lower Bound: 367812 (Uthus, Riddle, and Guesgen, Mar 11 2009), 452597 (Uthus, Riddle, and Guesgen June 28 2009), 453860 (Uthus, Riddle, and Guesgen January 6, 2010)
• Super14
  Feasible Solution: 599296 (Misir, Wauters, Verbeeck, Vanden Berghe, March 30 2009), 586435 (Uthus, Riddle and Guesgen April 29 2009), 573669 (Langford May 4, 2009), 571632 (Langford May 15, 2009)
  Lower Bound: 467839 (Uthus, Riddle, and Guesgen, Mar 11 2009),557070 (Uthus, Riddle, and Guesgen June 28 2009), 557354 (Uthus, Riddle, and Guesgen January 29 2010)

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), 598123 (Goerigk, Hoshino, Kawarabayashi, and Westphal, Aug 27, 2013)
  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)

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.

• galaxy4.txt
  Feasible Solution: 416 (Uthus, Riddle, and Guesgen June 28, 2009)
  Lower Bound: 416 (Uthus, Riddle, and Guesgen June 28, 2009)
• galaxy6.txt
  Feasible Solution: 1365 (Uthus, Riddle, and Guesgen June 28, 2009)
  Lower Bound: 1365 (Uthus, Riddle, and Guesgen June 28, 2009)
• galaxy8.txt
  Feasible Solution: 2373 (Uthus, Riddle, and Guesgen June 28, 2009)
  Lower Bound: 2373 (Uthus, Riddle, and Guesgen June 28, 2009)
• galaxy10.txt
  Feasible Solution: 4554 (Uthus, Riddle, and Guesgen June 28, 2009), 4535 (Langford July 28, 2009)
  Lower Bound: 4443 (Uthus, Riddle, and Guesgen June 28, 2009), 4535 (Uthus, Riddle, and Guesgen December 25, 2009).
• galaxy12.txt
  Feasible Solution: 7357 (Uthus, Riddle, and Guesgen June 28, 2009), 7197 (Langford July 28, 2009)
  Lower Bound: 7034 (Uthus, Riddle, and Guesgen January 6, 2010).
• galaxy14.txt
  Feasible Solution: 11412 (Uthus, Riddle, and Guesgen June 28, 2009), 11047 (Langford August 1, 2009), 10918 (Langford September 14, 2009)
  Lower Bound: 10255 (Uthus, Riddle, and Guesgen January 29, 2010)
• galaxy16.txt
  Feasible Solution: 16023 (Uthus, Riddle, and Guesgen June 28, 2009), 15099 (Langford August 4, 2009), 14982 (Langford September 20, 2009), 14900 (Langford April 6, 2010)
  Lower Bound: 13619 (independent)
• galaxy18.txt
  Feasible Solution: 22467 (Uthus, Riddle, and Guesgen June 28, 2009), 21571 (Langford September 22, 2009), 21310 (Langford December 18 2009), 20907 (Langford March 13 2010), 20845 (Hirano, Abe and Imahori May 21, 2018)
  Lower Bound: 19050 (independent)
• galaxy20.txt
  Feasible Solution: 29050 (Uthus, Riddle, and Guesgen June 28, 2009), 26855 (Langford September 25, 2009), 26450 (Langford December 27, 2009), 26289 (Langford March 18, 2010).
  Lower Bound: 23738 (independent)
• galaxy22.txt
  Feasible Solution: 39025 (Uthus, Riddle, and Guesgen June 28, 2009), 37821 (Langford September 25, 2009), 36296 (Langford January 2, 2010), 36152 (Langford March 7, 2010), 35767 (Westphal August 23, 2010), 35516 (Hosoe and Imahori, March 9, 2011), 35467 (Goerigk and Westphal, Feb 9, 2012), 35095 (Hoshino and Kawarabayashi, September 28, 2012), 35014 (Hoshino and Kawarbayashi, November 29, 2012), 33901 (Goerigk, Hoshino, Kawarabayashi, and Westphal, Aug 27, 2013)
  Lower Bound: 31461 (independent)
• galaxy24.txt
  Feasible Solution: 51056 (Uthus, Riddle, and Guesgen June 28, 2009), 48967 (Langford October 2 2009), 48434 (Langford January 11, 2010), 45910 (Westphal August 23, 2010), 45728 (Hosoe and Imahori, March 9, 2011), 45671 (Goerigk and Westphal, December 23, 2011), 45610 (Goerigk and Westphal, Feb 9, 2012), 45554 (Hosoe and Imahori, Feb 24, 2012), 44647 (Abe and Imahori, February 1, 2018), 44526 (Hirano, Abe and Imahori May 21, 2018)
  Lower Bound: 41287 (independent)
• galaxy26.txt
  Feasible Solution: 66334 (Uthus, Riddle, and Guesgen June 28, 2009), 63493 (Langford October 4 2009), 62613 (Langford January 22, 2010), 60962 (Westphal August 23, 2010), 59871 (Goerigk and Westphal, December 23, 2011), 58968 (Goerigk and Westphal, Feb 9, 2012)
  Lower Bound: 53802 (independent)
• galaxy28.txt
  Feasible Solution: 87109 (Uthus, Riddle, and Guesgen June 28, 2009), 83911 (Langford October 4, 2009), 81911 (Langford February 16, 2010), 77577 (Westphal August 23, 2010), 77381 (Goerigk and Westphal, December 23, 2011), 77214 (Goerigk and Westphal, Feb 9, 2012), 77090 (Hosoe and Imahori, Feb 24, 2012), 76749 (Hoshino and Kawarabayashi, September 28, 2012), 76518 (Hoshino and Kawarbayashi, November 29, 2012), 75276 (Goerigk, Hoshino, Kawarabayashi, and Westphal, Aug 27, 2013)
  Lower Bound: 69992 (independent)
• galaxy30.txt
  Feasible Solution: 110237 (Uthus, Riddle, and Guesgen June 28, 2009), 104551 (Langford October 24, 2009), 101774 (Langford March 7, 2010), 96979 (Westphal August 23, 2010), 96765 (Hosoe and Imahori, March 9, 2011), 96712 (Goerigk and Westphal, December 23, 2011), 96710 (Goerigk and Westphal, Feb 9, 2012), 96580 (Hosoe and Imahori, Feb 24, 2012), 95334 (Abe and Imahori, February 1, 2018), 95158 (Hirano, Abe and Imahori May 21, 2018)
  Lower Bound: 88831 (independent)
• galaxy32.txt
  Feasible Solution: 136253 (Uthus, Riddle, and Guesgen June 28, 2009), 127488 (Langford October 27, 2009), 123510 (Langford April 6, 2010), 120683 (Westphal August 23, 2010), 120021 (Goerigk and Westphal, December 23, 2011), 119996 (Goerigk and Westphal, Feb 9, 2012), 119749 (Abe and Imahori, February 1, 2018), 119665 (Hirano, Abe and Imahori May 21, 2018)
  Lower Bound: 108374 (independent)
• galaxy34.txt
  Feasible Solution: 168721 (Uthus, Riddle, and Guesgen June 28, 2009), 162390 (Langford October 27, 2009), 153530 (Langford May 9, 2010), 147835 (Westphal August 23, 2010), 147742 (Hosoe and Imahori, March 9, 2011), 146982 (Goerigk and Westphal, December 23, 2011), 147612 (Goerigk and Westphal, Feb 9, 2012), 146792 (Hosoe and Imahori, Feb 24, 2012), 145165 (Hoshino and Kawarbayashi, November 29, 2012), 143298 (Goerigk, Hoshino, Kawarabayashi, and Westphal, Aug 27, 2013)
  Lower Bound: 133976 (independent)
• galaxy36.txt
  Feasible Solution: 207117 (Uthus, Riddle, and Guesgen June 28, 2009), 187180 (Langford November 24 2009), 177090 (Langford July 3, 2010), 173827 (Westphal August 23, 2010), 173640 (Hosoe and Imahori, March 9, 2011), 173532 (Goerigk and Westphal, Feb 9, 2012), 173458 (Hosoe and Imahori, Feb 24, 2012), 171846 (Abe and Imahori, February 1, 2018), 169387 (Hirano, Abe and Imahori May 21, 2018)
  Lower Bound: 158549 (independent)
• galaxy38.txt
  Feasible Solution: 253279 (Uthus, Riddle, and Guesgen June 28, 2009), 227778 (Langford November 24 2009), 214546 (Langford, July 3, 2010), 210787 (Westphal August 23, 2010), 209463 (Hosoe and Imahori, March 9, 2011), 205725 (Goerigk and Westphal, December 23, 2011), 204980 (Goerigk and Westphal, Feb 9, 2012)
  Lower Bound: 189126 (independent)
• galaxy40.txt
  Feasible Solution: 304689 (Uthus, Riddle, and Guesgen June 28, 2009), 281082 (Langford November 24, 2009), 258899 (Langford July 3 2010), 249230 (Westphal August 23, 2010), 249002 (Hosoe and Imahori, March 9, 2011), 247207 (Goerigk and Westphal, December 23, 2011), 247017 (Goerigk and Westphal, Feb 9, 2012), 245052 (Hoshino and Kawarbayashi, November 29, 2012), 241908 (Goerigk, Hoshino, Kawarabayashi, and Westphal, Aug 27, 2013)
  Lower Bound: 226820 (independent)

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), 132 (Uthus, Riddle, and Guesgen, Feb 11 2009)
• circ8 (unconstrained, with repeaters)
  Feasible Solution: 100 (Langford, June 24, 2005)
  Lower Bound: 92 (Irnich and Schrempp, June 24 2008), 100 (Gschwind and Irnich April 19, 2010).
• circ8 (unconstrained, without repeaters)
  Feasible Solution: 102 (Langford, July 6, 2005)
  Lower Bound: 85 (Irnich and Schrempp, June 24 2008), 102 (Gschwind and Irnich April 19, 2010).
• 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), 237 (Uthus, Riddle, and Guesgen, Feb 11 2009), 242 (Uthus, Riddle, and Guesgen December 11, 2009)
• 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados February 26, 2003), 436 (Shen March 11 2003), 420 (Anagnostopoulos, Michel, Van Hentenryck and Vergados June 26, 2003), 408 (Zhang January 23 2005), 404 (Van Hentenryck and Vergados, May 30 2007)
  Lower Bound: 384 (Trick May 2001), 388 (Uthus, Riddle, and Guesgen January 6, 2010)
• 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados February 26, 2003), 670 (Anagnostopoulos, Michel, Van Hentenryck and Vergados 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados 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 (Anagnostopoulos, Michel, Van Hentenryck and Vergados 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). Unconstrained: 494
• 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). Unconstrained: 587

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.