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.

more

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 2023-02-07
Projekttitel ---
Zitation Strutz, Tilo (2023): Re-Designing the Wheel for Systematic Travelling Salesmen. Algorithms 2023, 91 (2). DOI: 10.3390/a16020091