Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912957110157312 |
|---|---|
| author | Soulignac, Francisco J. |
| author_facet | Soulignac, Francisco J. |
| contents | We propose a simple and exact method for the Traveling Salesman Problem with Time Windows and Makespan objective (\TSPTW-M) that solves all instances of the classical benchmark with $50$ or more customers in less than ten seconds each. Applying this algorithm as an off-the-shelf method, we also solve all but one of these instances for the Duration objective. Our main conclusion is that these instances alone are no longer representative for evaluating the TSPTW-M and its Duration variant: their structure can be exploited to yield results that seem outstanding at first glance. Additionally, caution is advised when designing hard training sets for machine learning algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01064 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows Soulignac, Francisco J. Data Structures and Algorithms Discrete Mathematics We propose a simple and exact method for the Traveling Salesman Problem with Time Windows and Makespan objective (\TSPTW-M) that solves all instances of the classical benchmark with $50$ or more customers in less than ten seconds each. Applying this algorithm as an off-the-shelf method, we also solve all but one of these instances for the Duration objective. Our main conclusion is that these instances alone are no longer representative for evaluating the TSPTW-M and its Duration variant: their structure can be exploited to yield results that seem outstanding at first glance. Additionally, caution is advised when designing hard training sets for machine learning algorithms. |
| title | Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2512.01064 |