A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914657252409344 |
|---|---|
| author | Ammann, Sabrina C. L. Ostermann, Birte Stiller, Sebastian de Wolff, Timo |
| author_facet | Ammann, Sabrina C. L. Ostermann, Birte Stiller, Sebastian de Wolff, Timo |
| contents | The Traveling Salesman Problem (TSP) is one of the most extensively researched and widely applied combinatorial optimization problems. It is NP-hard even in the symmetric and metric case. Building upon elaborate research, state-of-the-art exact solvers such as CONCORDE can solve TSP instances with several ten thousand vertices. A key ingredient for these integer programming approaches are fast heuristics to find a good initial solution, in particular the Lin-Kernighan-Helsgaun (LKH) heuristic. For instances with few hundred vertices heuristics like LKH often find an optimal solution. In this work we develop variations of LKH that perform significantly better on large instances. LKH repeatedly improves an initially random tour by exchanging edges along alternating circles. Thereby, it respects several criteria designed to quickly find alternating circles that give a feasible improvement of the tour. Among those criteria, the positive gain criterion stayed mostly untouched in previous research. It requires that, while constructing an alternating circle, the total gain has to be positive after each pair of edges. We relax this criterion carefully leading to improvement steps hitherto undiscovered by LKH. We confirm this improvement experimentally via extensive simulations on various benchmark libraries for TSP. Our computational study shows that for large instances our method is on average 13% faster than the latest version of LKH. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16149 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion Ammann, Sabrina C. L. Ostermann, Birte Stiller, Sebastian de Wolff, Timo Optimization and Control Discrete Mathematics Data Structures and Algorithms Combinatorics 68W25, 68W40, 90-04, 90-05, 90C27, 90C59 The Traveling Salesman Problem (TSP) is one of the most extensively researched and widely applied combinatorial optimization problems. It is NP-hard even in the symmetric and metric case. Building upon elaborate research, state-of-the-art exact solvers such as CONCORDE can solve TSP instances with several ten thousand vertices. A key ingredient for these integer programming approaches are fast heuristics to find a good initial solution, in particular the Lin-Kernighan-Helsgaun (LKH) heuristic. For instances with few hundred vertices heuristics like LKH often find an optimal solution. In this work we develop variations of LKH that perform significantly better on large instances. LKH repeatedly improves an initially random tour by exchanging edges along alternating circles. Thereby, it respects several criteria designed to quickly find alternating circles that give a feasible improvement of the tour. Among those criteria, the positive gain criterion stayed mostly untouched in previous research. It requires that, while constructing an alternating circle, the total gain has to be positive after each pair of edges. We relax this criterion carefully leading to improvement steps hitherto undiscovered by LKH. We confirm this improvement experimentally via extensive simulations on various benchmark libraries for TSP. Our computational study shows that for large instances our method is on average 13% faster than the latest version of LKH. |
| title | A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion |
| topic | Optimization and Control Discrete Mathematics Data Structures and Algorithms Combinatorics 68W25, 68W40, 90-04, 90-05, 90C27, 90C59 |
| url | https://arxiv.org/abs/2401.16149 |