# Traveling Salesman Problem on TSP Uniform-500

Source: [Traveling Salesman Problem on TSP Uniform-500](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-uniform-500>)

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

Data updated: 2026-05-08T10:09:25.503Z

Evaluation of algorithms solving the Traveling Salesman Problem on the TSP Uniform-500 instances, reporting the performance gap percentage.

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 Uniform-500 |
| Metric | Performance Gap (%) |
| Unit | PERCENT |
| Direction | Lower is better |
| Results loaded | 14 of 14 |
| 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

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

## Recorded results

| Method | Performance Gap (%) | Result date | Report paper |
| --- | --- | --- | --- |
| ReEvo TD & BU | 8.07 | Not recorded | 69fd6e175497b3b670c8942c |
| EoH-S | 8.97 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo TD & BU | 9.22 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo TD | 10.19 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo BU | 10.83 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo TD & BU | 11.02 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo TD & BU | 11.67 | Not recorded | 69fd6e175497b3b670c8942c |
| EoH-S | 11.77 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo TD | 12.14 | Not recorded | 69fd6e175497b3b670c8942c |
| EoH-S | 12.7 | Not recorded | 69fd6e175497b3b670c8942c |
| EoH-S | 12.83 | Not recorded | 69fd6e175497b3b670c8942c |
| ReEvo BU | 13.1 | Not recorded | 69fd6e175497b3b670c8942c |
| DIFUSCO + LS | 14.04 | Not recorded | 69fd6e175497b3b670c8942c |
| POMO | 16.26 | Not recorded | 69fd6e175497b3b670c8942c |

### ReEvo TD & BU

Performance Gap (%): 8.07. Result ID: 69fdb64f47f34ce924e133bf.

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

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

Recorded evaluation configuration: {"Type":"Black-Box","Variant":"Edge","Setting":"Multi-task"}. This record does not assert independent reproduction.

### EoH-S

Performance Gap (%): 8.97. Result ID: 69fdb64f47f34ce924e133be.

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

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

Recorded evaluation configuration: {"Type":"Black-Box","Variant":"Edge","Setting":"Multi-task"}. This record does not assert independent reproduction.

### ReEvo TD & BU

Performance Gap (%): 9.22. Result ID: 69fdb64f47f34ce924e133bb.

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Edge","Setting":"Multi-task"}. This record does not assert independent reproduction.

### ReEvo TD

Performance Gap (%): 10.19. Result ID: 69fdb64f47f34ce924e133b9.

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Edge","Setting":"Single-task"}. This record does not assert independent reproduction.

### ReEvo BU

Performance Gap (%): 10.83. Result ID: 69fdb64f47f34ce924e133b8.

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

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Edge","Setting":"Single-task"}. This record does not assert independent reproduction.

### ReEvo TD & BU

Performance Gap (%): 11.02. Result ID: 69fdb64f47f34ce924e133b6.

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Node","Setting":"Multi-task"}. This record does not assert independent reproduction.

### ReEvo TD & BU

Performance Gap (%): 11.67. Result ID: 69fdb64f47f34ce924e133bd.

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

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

Recorded evaluation configuration: {"Type":"Black-Box","Variant":"Node","Setting":"Multi-task"}. This record does not assert independent reproduction.

### EoH-S

Performance Gap (%): 11.77. Result ID: 69fdb64f47f34ce924e133bc.

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

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

Recorded evaluation configuration: {"Type":"Black-Box","Variant":"Node","Setting":"Multi-task"}. This record does not assert independent reproduction.

### ReEvo TD

Performance Gap (%): 12.14. Result ID: 69fdb64f47f34ce924e133b4.

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Node","Setting":"Single-task"}. This record does not assert independent reproduction.

### EoH-S

Performance Gap (%): 12.7. Result ID: 69fdb64f47f34ce924e133b5.

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Node","Setting":"Multi-task"}. This record does not assert independent reproduction.

### EoH-S

Performance Gap (%): 12.83. Result ID: 69fdb64f47f34ce924e133ba.

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Edge","Setting":"Multi-task"}. This record does not assert independent reproduction.

### ReEvo BU

Performance Gap (%): 13.1. Result ID: 69fdb64f47f34ce924e133b3.

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

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

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Node","Setting":"Single-task"}. This record does not assert independent reproduction.

### DIFUSCO + LS

Performance Gap (%): 14.04. Result ID: 69fdb64f47f34ce924e133b7.

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

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

[Implementation](<https://github.com/Edward-Sun/DIFUSCO>)

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Edge","Setting":"Single-task"}. This record does not assert independent reproduction.

### POMO

Performance Gap (%): 16.26. Result ID: 69fdb64f47f34ce924e133b2.

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

Recorded evaluation configuration: {"Type":"White-Box","Variant":"Node","Setting":"Single-task"}. This record does not assert independent reproduction.

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