Challenge Traveling Tournament Instances
Last Update: February 2, 2020
IMPORTANT NOTICE
There is a more extensive repository of Sports Scheduling instances and results at RobinX. The Traveling Tournament Problem also appears there. The statement of "best results" should be identical between the two sites, but RobinX is more extensive (and doesn't look like a 2001 website, like this one does).
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:
- 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
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), 44762 (Ben Sliméne, July 20, 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), 79312 (Ben Sliméne, July 20, 2019)
- 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), 125416 (Ben Sliméne, July 20, 2019)
- 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), 154566 (Ben Sliméne, September 3, 2019)
[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), 630 (Frohner, Neumann, and Raidl, Nov 27, 2019)
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), 910 (Frohner, Neumann, and Raidl, Nov 27, 2019)
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