The Traveling Tourist Hall of Fame

These are the best reported tours of the following problem instances. The data sets and problem instances are defined on the data set page. Some notes are given below describing the progress on finding good tours and on establishing lower bounds for the instances.

Fastest Tours

Tours marked with * are claimed to be optimal.

Southern Railway (India)
1. (Size 12) 1 day 21 hours 15 minutes south-tour.12 * TBM
2. (Size 18) 3 days 5 hours 20 minutes south-tour.18 * TBM
3. (Size 25) 7 days 11 hours 40 minutes south-tour.25 * Saito
4. (Size 36) 9 days 11 hours 40 minutes south-tour.36 TBM
5. (Size 49) 14 days 21 hours 15 minutes south-tour.49 MS
6. (Size 66) 15 days 1 hours 25 minutes south-tour.66 MS
7. (Size 75) 15 days 9 hours 30 minutes south-tour.75 MS
USA Complete
1. (Size 10) 10 days 17 hours 43 minutes usa-tour.10 * BS
2. (Size 12) 10 days 16 hours 57 minutes usa-tour.12 * HSS
3. (Size 15) 12 days 6 hours 32 minutes usa-tour.15 *
4. (Size 20) 13 days 18 hours 42 minutes usa-tour.20 PS
USA Sparse
1. (Size 25) 15 days 18 hours 27 minutes usa-tour.25 MS
2. (Size 30) 15 days 13 hours 46 minutes usa-tour.30 MS
3. (Size 35) 20 days 8 hours 49 minutes usa-tour.35 MS
4. (Size 40) 19 days 22 hours 42 minutes usa-tour.40 MS
5. (Size 45) 21 days 2 hours 48 minutes usa-tour.45 MS
6. (Size 50) 21 days 20 hours 29 minutes usa-tour.50 MS
7. (Size 60) 23 days 1 hours 55 minutes usa-tour.60 MS
8. (Size 80) 28 days 14 hours 26 minutes usa-tour.80 HM
9. (Size 100) 35 days 0 hours 53 minutes usa-tour.100 HM
10. (Size 128) 39 days 14 hours 36 minutes usa-tour.128 HM
UK Sparse
1. (Size 25) 7 days 20 hours 1 minutes uk-tour.25 MS
2. (Size 50)10 days 12 hours 55 minutes uk-tour.50 MS
3. (Size 75)15 days 6 hours 2 minutes uk-tour.75 MS
4. (Size 100) 22 days 4 hours 43 minutes uk-tour.100 HM
5. (Size 150) 30 days 5 hours 21 minutes uk-tour.150 MS
6. (Size 200)35 days 0 hours 34 minutes uk-tour.200 HM
7. (Size 284) 52 days 4 hours 7 minutes uk-tour.284 HM
Meshes
1. (Size 9) 8 days 23 hours 21 minutes mesh-tour.3
2. (Size 16) 8 days 23 hours 55 minutes mesh-tour.4 HM
3. (Size 25) 10 days 17 hours 8 minutes mesh-tour.5 * HSS
4. (Size 36) 13 days 12 hours 56 minutes mesh-tour.6 MS
5. (Size 49) 15 days 7 hours 3 minutes mesh-tour.7 MS
6. (Size 64) 18 days 11 hours 39 minutes mesh-tour.8 MS
7. (Size 81) 21 days 5 hours 34 minutes mesh-tour.9 MS
8. (Size 100)25 days 21 hours 38 minutes mesh-tour.10 HM
Triangles
1. (Size 6) 6 days 7 hours 3 minutes tri-tour.3 *
2. (Size 10) 7 days 5 hours 34 minutes tri-tour.4 *
3. (Size 15) 8 days 19 hours 19 minutes tri-tour.5 *
4. (Size 21) 9 days 20 hours 13 minutes tri-tour.6 * HSS
5. (Size 28)10 days 16 hours 50 minutes tri-tour.7 TBM
6. (Size 36) 12 days 6 hours 51 minutes tri-tour.8 MS
7. (Size 45) 14 days 7 hours 24 minutes tri-tour.9 MS
8. (Size 55) 17 days 9 hours 3 minutes tri-tour.10 MS
9. (Size 66) 18 days 6 hours 19 minutes tri-tour.11 MS
10. (Size 78) 19 days 8 hours 36 minutes tri-tour.12 MS

Notes

3/10/96

Hong-Montomgery parasitic algorithm improves the big instances.

2/23/96

Hee-Saito genetic algorithm improves almost all tours.

2/22/96

Additional improved tours found by greedy algorithm.

2/19/96

The Popovic-Shade Simulated Annealing algorithm improves on many existing tours.
Further improvement of the greedy algorithm by BTM - superior to Simulated Annealing in a few cases.

2/14/96

Branch and Bound establishes optimal tours for south.12, south.18, and south.25.

2/13/96

Local brute force improvement gives a better bound on uk.100.
I improved the BLM result on south.49 by running their tour through a local-improvement algorithm. Running the progam showtour on the result suggests that there is still much room for improvement!

2/12/96

The Baer-Lim-Michalowski randomized greedy algorithms gives improved tours of the Southern Railway. The algorithm randomly chooses a neighbor to extend the path to. The results are the best of a number of trials.

2/11/96

The Baker-Secosky greedy algorithms establishes good upper bounds for almost all instances.

1/24/96

Branch and bound solve usa.15, mesh.5, and tri.6 (and some smaller instances). The branch and bound uses a best-first search, coupled with a hashing technique to reduce duplicate tree traversals.

1/24/96

The bound on uk-sch.100 improved to 24 days 8 hours 57 minutes with a genetic algorithm (run time ~ 12 minutes (Pentium 90 MHz)).

1/24/96

A greedy algorithm visits uk-sch.100 in 28 days 1 hour 40 minutes. (My guess is the algorithm extends the path to the closest unvisited city.)

1/16/96

I've updated the solution of usa.15 to give the result of a branch and bound search. The search terminated itself after visiting 1,000,000 nodes. This is not necessarily the best tour of the data set.

1/2/96

Since a tour is going to traverse at least one edge leaving every vertex, we can get a very weak lower bound by adding up the minimum duration edges adjacent to each vertex. These are the current lower bounds. The upper and lower bounds are within a factor of 100 of each other!

12/30/95

All of the tours were generated with a really dumb algorithm. The algorithm would repeatedly extend the path to an unvistited city until all cities were visited. No attempt was made to choose good routes. Running showtour on some of the tours will show that there has to be lots of room for improvement!

Tourists

HSS: Meng-hee Heng, Jonathan Shakes, and Yasushi Saito

BS: Marla Baker and Jason Secosky

HM: Eddie Hong and Andy Montgomery

TBM: Tiam Lim, Jeremy Baer, Brian Michalowski

NMP: Jonathan Nowitz, Denise Pinnel, Zack Mason

PS: Jovan Popovic and Jonathan Shade