Algorithm Comparison Page
Algorithm 1
Algorithm 2
Spacefilling Curve
Vertical Strip
Best of Vertical/Horizontal Strip
Fast Recursive Partitioning Alg. (Bentley)
Benchmark Greedy on 196Mhz MIPS
Benchmark Greedy on 500 Mhz Alpha
Benchmark Greedy on 2600 Mhz Intel Xeon
Bentley's Greedy (Multi-Fragment)
Greedy Algorithm (Concorde/MIPS)
Boruvka's Algorithm (Concorde/Sparc)
Boruvka's Algorithm (Concorde/MIPS)
"Quick Boruvka" (Concorde/MIPS)
Nearest Neighbor (Bentley)
Nearest Neighbor (Johnson-McGeogh)
Nearest Neighbor (Concorde)
Double-Ended Nearest Neighbor (Bentley)
Nearest Insertion
Nearest Addition
Nearest Augmented Addition
Cheapest Insertion
Convex Hull, Cheapest Insertion
Convex Hull, Greatest Angle Insertion
Random Insertion
Random Addition
Random Augmented Addition
Farthest Insertion
Farthest Addition
Farthest Augmented Addition
Clarke-Wright Savings Heuristic
Double MST, Greedy Shortcuts
CCA
Karp Partitioning, Max Base Size = 15
Karp Partitioning, Max Base Size = 20
Litke's Clustering Heuristic, Max Base Size = 15
Christofides, Standard Shortcuts
Christofides, Greedy Shortcuts
OneTree-Based Christofides, Greedy Shortcuts (Rohe)
Approximate Christofides, Greedy Shortcuts
Approximate Christofides: Rohe (MST-based)
2-Opt, Concorde-edgegen, 196 Mhz MIPS
2-Opt, 10 Nbrs [JM], 500 Mhz Alpha
2-Opt, 20 Nbrs [JM], 500 Mhz Alpha
2-Opt, 20 Nbrs [JM], 196 Mhz MIPS
2-Opt, 40 Nbrs [JM], 500 Mhz Alpha, Run 1
2-Opt, 40 Nbrs [JM], 500 Mhz Alpha, Run 2
2-Opt (Bentley implementation)
2.5-Opt Concorde-edgegen, 196 Mhz MIPS
2.5-Opt (Bentley implementation)
3-Opt, Concorde-edgegen, 196 Mhz MIPS
3-Opt, 10 Nbrs [JM], 500 Mhz Alpha
3-Opt, 20 Nbrs [JM], 500 Mhz Alpha
3-Opt, 20 Nbrs [JM], 196 Mhz MIPS
3-Opt, 40 Nbrs [JM], 500 Mhz Alpha
3-Opt (Bentley implementation)
Vertex Reinsertion plus Path Reoptimization
2-Hyperopt
3-Hyperopt
4-Hyperopt
GENI, p=10
GENIUS, p=10
Lin-Kernighan (Concorde)
Lin-Kernighan (Applegate-Cook-Rohe)
Lin-Kernighan with HK-Christo Start (Rohe)
Lin-Kernighan, 10 Nbrs [JM], 500 Mhz Alpha
Lin-Kernighan, 20 Nbrs [JM], 500 Mhz Alpha
Lin-Kernighan, 20 Nbrs [JM], 196 Mhz MIPS
Lin-Kernighan, 40 Nbrs [JM], 500 Mhz Alpha
Lin-Kernighan, 40 Nbrs [JM], 196 Mhz MIPS
Lin-Kern., 40 Nbrs, Depth 50 [JM], MIPS
Lin-Kernighan 12 Quad. Nbrs, 550 Mhz Pentium [Neto]
Lin-Kernighan 20+ Quad Nbrs, 550 Mhz Pentium [Neto]
Lin-Kernighan 40+ Quad Nbrs, 550 Mhz Pentium [Neto]
Lin-Kernighan 20+ Quad Nbrs [Neto]
Lin-Kernighan 20+ Quad Nbrs, no cluster comp. [Neto]
Lin-Kernighan 20 Near Nbrs [Neto]
Lin-Kernighan 20 Near Nbrs, no cluster comp. [Neto]
Lin-Kernighan 12 Nbrs, Greedy Starts [NYYY]
Lin-Kernighan 12 Nbrs, Boruvka Starts [NYYY]
Stem-and-Cycle, Random Start
Stem-and-Cycle, Boruvka Start
Zachariasen-Dam Tabu Search: 2-Opt/2-Opt
Zachariasen-Dam Tabu Search: 2-Opt/D-B
Zachariasen-Dam Tabu Search: L-K/L-K
Zachariasen-Dam Tabu Search: L-K/D-B
Zachariasen-Dam Tabu Search: Flower/Flower
Zachariasen-Dam Tabu Search: Flower/D-B
Johnson-McGeoch 2-Opt Based Simulated Annealing
Johnson-McGeoch 2+3-Opt Based Simulated Annealing
Augmented Lin-Kernighan (Buesching)
Helsgaun LK Variant
Helsgaun LK Variant (N/10 iterations)
Helsgaun LK Variant (N iterations)
Iterated 3-Opt [JM] (10N iterations)
Iterated LK [JM] (N/10 iterations)
Iterated LK [JM] (N/sqrt(10) iteration)
Iterated LK [JM] (N iterations)
Iterated LK [JM] (10N iterations)
Iterated LK [JM] (Best of ten N-iterations)
Iterated LK [Neto] N/10-iterations)
Iterated LK [Neto] (N iterations)
Iterated LK [NYYY] (N iterations)
Iterated LK [NYYY] (10N iterations)
Iterated LK [NYYY] (Best of ten N-iterations)
Iterated LK [NYYY] (N iterations, geometric kicks)
Iterated LK [NYYY] (.5N iterations, geometric kicks)
Chained LK [ABCC] on UltraSparc (N iterations)
Chained LK [ABCC] on MIPS (N iterations)
Chained LK [ABCC] on MIPS (10N iterations)
Chained LK [ABCC] on MIPS (Best of ten N-iterations)
Multi-Level Lin-Kernighan (Walshaw)
Multi-Level Helsgaun (Walshaw)
Chained LK [ACR] (10 iterations)
Chained LK [ACR] (100 iterations)
Chained LK [ACR] (1000 iterations)
Chained LK [ACR] (N iterations)
Balas-Simonetti Dynamic Prog. Heuristic, k=6
Balas-Simonetti Dynamic Prog. Heuristic, k=8
Balas-Simonetti Dynamic Prog. Heuristic, k=10
Variable Neighb. Search w/2-Hyperopt (100 iterations)
Variable Neighb. Search w/2-Hyperopt (1000 iterations)
Variable Neighb. Search w/3-Hyperopt (100 iterations)
Variable Neighb. Search w/3-Hyperop (1000 iterations)t
Multi-Level Chained LK (N/10 iterations)
Multi-Level Chained LK (N/2 iterations)
Multi-Level Chained LK (N iterations)
Multi-Level Helsgaun (N/20 iterations)
Multi-Level Helsgaun (N/2 iterations)
Multi-Level Helsgaun (N iterations)
Chained LK Tourmerging, Average of 5 Runs
Chained LK Tourmerging, Best of 5 Runs
Concorde (optimization)
Held-Karp Bounds computed by Concorde
Rohe's Approximate Held-Karp Bounds, slow convergence
Rohe's Approximate Held-Karp Bounds, faster convergence
Rohe's Approximate Held-Karp Bounds, fast convergence
Instance Reading Only (196 Mhz MIPS)
Spacefilling Curve
Vertical Strip
Best of Vertical/Horizontal Strip
Fast Recursive Partitioning Alg. (Bentley)
Benchmark Greedy on 196Mhz MIPS
Benchmark Greedy on 500 Mhz Alpha
Benchmark Greedy on 2600 Mhz Intel Xeon
Bentley's Greedy (Multi-Fragment)
Greedy Algorithm (Concorde/MIPS)
Boruvka's Algorithm (Concorde/Sparc)
Boruvka's Algorithm (Concorde/MIPS)
"Quick Boruvka" (Concorde/MIPS)
Nearest Neighbor (Bentley)
Nearest Neighbor (Johnson-McGeogh)
Nearest Neighbor (Concorde)
Double-Ended Nearest Neighbor (Bentley)
Nearest Insertion
Nearest Addition
Nearest Augmented Addition
Cheapest Insertion
Convex Hull, Cheapest Insertion
Convex Hull, Greatest Angle Insertion
Random Insertion
Random Addition
Random Augmented Addition
Farthest Insertion
Farthest Addition
Farthest Augmented Addition
Clarke-Wright Savings Heuristic
Double MST, Greedy Shortcuts
CCA
Karp Partitioning, Max Base Size = 15
Karp Partitioning, Max Base Size = 20
Litke's Clustering Heuristic, Max Base Size = 15
Christofides, Standard Shortcuts
Christofides, Greedy Shortcuts
OneTree-Based Christofides, Greedy Shortcuts (Rohe)
Approximate Christofides, Greedy Shortcuts
Approximate Christofides: Rohe (MST-based)
2-Opt, Concorde-edgegen, 196 Mhz MIPS
2-Opt, 10 Nbrs [JM], 500 Mhz Alpha
2-Opt, 20 Nbrs [JM], 500 Mhz Alpha
2-Opt, 20 Nbrs [JM], 196 Mhz MIPS
2-Opt, 40 Nbrs [JM], 500 Mhz Alpha, Run 1
2-Opt, 40 Nbrs [JM], 500 Mhz Alpha, Run 2
2-Opt (Bentley implementation)
2.5-Opt Concorde-edgegen, 196 Mhz MIPS
2.5-Opt (Bentley implementation)
3-Opt, Concorde-edgegen, 196 Mhz MIPS
3-Opt, 10 Nbrs [JM], 500 Mhz Alpha
3-Opt, 20 Nbrs [JM], 500 Mhz Alpha
3-Opt, 20 Nbrs [JM], 196 Mhz MIPS
3-Opt, 40 Nbrs [JM], 500 Mhz Alpha
3-Opt (Bentley implementation)
Vertex Reinsertion plus Path Reoptimization
2-Hyperopt
3-Hyperopt
4-Hyperopt
GENI, p=10
GENIUS, p=10
Lin-Kernighan (Concorde)
Lin-Kernighan (Applegate-Cook-Rohe)
Lin-Kernighan with HK-Christo Start (Rohe)
Lin-Kernighan, 10 Nbrs [JM], 500 Mhz Alpha
Lin-Kernighan, 20 Nbrs [JM], 500 Mhz Alpha
Lin-Kernighan, 20 Nbrs [JM], 196 Mhz MIPS
Lin-Kernighan, 40 Nbrs [JM], 500 Mhz Alpha
Lin-Kernighan, 40 Nbrs [JM], 196 Mhz MIPS
Lin-Kern., 40 Nbrs, Depth 50 [JM], MIPS
Lin-Kernighan 12 Quad. Nbrs, 550 Mhz Pentium [Neto]
Lin-Kernighan 20+ Quad Nbrs, 550 Mhz Pentium [Neto]
Lin-Kernighan 40+ Quad Nbrs, 550 Mhz Pentium [Neto]
Lin-Kernighan 20+ Quad Nbrs [Neto]
Lin-Kernighan 20+ Quad Nbrs, no cluster comp. [Neto]
Lin-Kernighan 20 Near Nbrs [Neto]
Lin-Kernighan 20 Near Nbrs, no cluster comp. [Neto]
Lin-Kernighan 12 Nbrs, Greedy Starts [NYYY]
Lin-Kernighan 12 Nbrs, Boruvka Starts [NYYY]
Stem-and-Cycle, Random Start
Stem-and-Cycle, Boruvka Start
Zachariasen-Dam Tabu Search: 2-Opt/2-Opt
Zachariasen-Dam Tabu Search: 2-Opt/D-B
Zachariasen-Dam Tabu Search: L-K/L-K
Zachariasen-Dam Tabu Search: L-K/D-B
Zachariasen-Dam Tabu Search: Flower/Flower
Zachariasen-Dam Tabu Search: Flower/D-B
Johnson-McGeoch 2-Opt Based Simulated Annealing
Johnson-McGeoch 2+3-Opt Based Simulated Annealing
Augmented Lin-Kernighan (Buesching)
Helsgaun LK Variant
Helsgaun LK Variant (N/10 iterations)
Helsgaun LK Variant (N iterations)
Iterated 3-Opt [JM] (10N iterations)
Iterated LK [JM] (N/10 iterations)
Iterated LK [JM] (N/sqrt(10) iteration)
Iterated LK [JM] (N iterations)
Iterated LK [JM] (10N iterations)
Iterated LK [JM] (Best of ten N-iterations)
Iterated LK [Neto] N/10-iterations)
Iterated LK [Neto] (N iterations)
Iterated LK [NYYY] (N iterations)
Iterated LK [NYYY] (10N iterations)
Iterated LK [NYYY] (Best of ten N-iterations)
Iterated LK [NYYY] (N iterations, geometric kicks)
Iterated LK [NYYY] (.5N iterations, geometric kicks)
Chained LK [ABCC] on UltraSparc (N iterations)
Chained LK [ABCC] on MIPS (N iterations)
Chained LK [ABCC] on MIPS (10N iterations)
Chained LK [ABCC] on MIPS (Best of ten N-iterations)
Multi-Level Lin-Kernighan (Walshaw)
Multi-Level Helsgaun (Walshaw)
Chained LK [ACR] (10 iterations)
Chained LK [ACR] (100 iterations)
Chained LK [ACR] (1000 iterations)
Chained LK [ACR] (N iterations)
Balas-Simonetti Dynamic Prog. Heuristic, k=6
Balas-Simonetti Dynamic Prog. Heuristic, k=8
Balas-Simonetti Dynamic Prog. Heuristic, k=10
Variable Neighb. Search w/2-Hyperopt (100 iterations)
Variable Neighb. Search w/2-Hyperopt (1000 iterations)
Variable Neighb. Search w/3-Hyperopt (100 iterations)
Variable Neighb. Search w/3-Hyperop (1000 iterations)t
Multi-Level Chained LK (N/10 iterations)
Multi-Level Chained LK (N/2 iterations)
Multi-Level Chained LK (N iterations)
Multi-Level Helsgaun (N/20 iterations)
Multi-Level Helsgaun (N/2 iterations)
Multi-Level Helsgaun (N iterations)
Chained LK Tourmerging, Average of 5 Runs
Chained LK Tourmerging, Best of 5 Runs
Concorde (optimization)
Optimal Tour Lengths from All Sources
Held-Karp Bounds computed by Concorde
Rohe's Approximate Held-Karp Bounds, slow convergence
Rohe's Approximate Held-Karp Bounds, faster convergence
Rohe's Approximate Held-Karp Bounds, fast convergence
Comparisons between Algorithm 1 and Algorithm 2
Normalized Data
Summary Table
Charts
Include Results for Distance Matrix Instances in Chart?
Yes
No
Results for
Algorithm 1
Algorithm 2
Raw Data
Normalized Data
Summary Table
Charts: Normalize Using Running Time Divisor
1
N
N log N
N log^2 N
N^1.25
N^1.5
N^2
N^2.5
N^3
Only Show Time Chart?
No
Yes
Include Results for Distance Matrix Instances in Chart?
Yes
No
Instance Comparisons
Challenge Homepage
About the Challenge
Download Page
Results Page