# Traveling Salesman Problem on TSP Overall scales 20-1000

Source: [Traveling Salesman Problem on TSP Overall scales 20-1000](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-overall-scales-20-1000>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-05-11T08:41:07.671Z

Evaluation of algorithms solving the Traveling Salesman Problem across various instance sizes ranging from 20 to 1000 nodes, reporting the Average Gap.

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

| Scope | Recorded value |
| --- | --- |
| Task | Traveling Salesman Problem |
| Dataset (including any stated split) | TSP Overall scales 20-1000 |
| Metric | Average Gap |
| Unit | PERCENT |
| Direction | Lower is better |
| Results loaded | 11 of 11 |
| Coverage | All results currently returned for this benchmark |

Evaluation settings may differ between results. The original papers and recorded configurations are needed to establish comparability. A shared metric name alone does not establish an identical protocol.

## Metrics

- [Average Gap](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-overall-scales-20-1000.md?metric=Average%20Gap>): Lower is better; unit: PERCENT.

## Recorded results

| Method | Average Gap | Result date | Report paper |
| --- | --- | --- | --- |
| HMACE | 0.387 | Not recorded | 6a01625bdbc836b87d822ee4 |
| CORAL | 0.431 | Not recorded | 6a01625bdbc836b87d822ee4 |
| EoH | 0.467 | Not recorded | 6a01625bdbc836b87d822ee4 |
| OR-Tools | 2.01 | Not recorded | 6a01625bdbc836b87d822ee4 |
| MoH | 11.792 | Not recorded | 6a01625bdbc836b87d822ee4 |
| MCTS-AHD | 12.568 | Not recorded | 6a01625bdbc836b87d822ee4 |
| ReEvo | 13.343 | Not recorded | 6a01625bdbc836b87d822ee4 |
| HSEvo | 13.379 | Not recorded | 6a01625bdbc836b87d822ee4 |
| EoH | 13.42 | Not recorded | 6a01625bdbc836b87d822ee4 |
| Funsearch | 16.165 | Not recorded | 6a01625bdbc836b87d822ee4 |
| Nearest Neighbor | 23.873 | Not recorded | 6a01625bdbc836b87d822ee4 |

### HMACE

Average Gap: 0.387. Result ID: 6a01960b47f34ce924e37c8b.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"true"}. This record does not assert independent reproduction.

### CORAL

Average Gap: 0.431. Result ID: 6a01960b47f34ce924e37c8a.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69cf497d0636e5bf4afcd9d6.md>)

[Implementation](<https://github.com/Human-Agent-Society/CORAL>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"true"}. This record does not assert independent reproduction.

### EoH

Average Gap: 0.467. Result ID: 6a01960b47f34ce924e37c89.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa73651e209131cea5c311.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"true"}. This record does not assert independent reproduction.

### OR-Tools

Average Gap: 2.01. Result ID: 6a01960b47f34ce924e37c81.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### MoH

Average Gap: 11.792. Result ID: 6a01960b47f34ce924e37c88.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa78e11e209131cea7af99.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### MCTS-AHD

Average Gap: 12.568. Result ID: 6a01960b47f34ce924e37c87.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa76c31e209131cea6ed8f.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### ReEvo

Average Gap: 13.343. Result ID: 6a01960b47f34ce924e37c85.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa75371e209131cea667f9.md>)

[Implementation](<https://github.com/ai4co/LLM-as-HH>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### HSEvo

Average Gap: 13.379. Result ID: 6a01960b47f34ce924e37c86.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa764a1e209131cea6c29c.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### EoH

Average Gap: 13.42. Result ID: 6a01960b47f34ce924e37c84.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa73651e209131cea5c311.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### Funsearch

Average Gap: 16.165. Result ID: 6a01960b47f34ce924e37c83.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

### Nearest Neighbor

Average Gap: 23.873. Result ID: 6a01960b47f34ce924e37c82.

[Reporting paper](<https://www.sota2.com/research/paper/6a01625bdbc836b87d822ee4.md>)

Recorded evaluation configuration: {"GPT-5.4 Evaluation":"false"}. This record does not assert independent reproduction.

Page 1 of 1. This is an index page, not the full collection.