Re-Designing the Wheel for Systematic Travelling Salesmen
Abstract
This paper investigates the systematic and complete usage of k-opt permutations with
k = 2 . . . 6 in application to local optimization of symmetric two-dimensional instances up to
107 points. The proposed method utilizes several techniques for accelerating the processing, such that
good tours can be achieved in limited time: candidates selection based on Delaunay triangulation,
precomputation of a sparse distance matrix, two-level data structure, and parallel processing based
on multithreading. The proposed approach finds good tours (excess of 0.72–8.68% over best-known
tour) in a single run within 30 min for instances with more than 105 points and specifically 3.37% for
the largest examined tour containing 107 points. The new method proves to be competitive with a
state-of-the-art approach based on the Lin–Kernigham–Helsgaun method (LKH) when applied to
clustered instances.
Mehr zum Titel
| Titel | Re-Designing the Wheel for Systematic Travelling Salesmen |
|---|---|
| Medien | Algorithms |
| Verlag | MDPI |
| Heft | 2 |
| Band | 2023 |
| ISBN | --- |
| Verfasser/Herausgeber | Prof. Dr.-Ing. habil. Tilo Strutz |
| Seiten | --- |
| Veröffentlichungsdatum | 07.02.2023 |
| Projekttitel | --- |
| Zitation | Strutz, Tilo (2023): Re-Designing the Wheel for Systematic Travelling Salesmen. Algorithms 2023, 91 (2). DOI: 10.3390/a16020091 |