A linearithmic heuristic for the travelling salesman problem

Taillard, Éric D. (School of Management and Engineering Vaud, HES-SO // University of Applied Sciences Western Switzerland)

The method has been tested on instances with billions of cities. For a lot of problem instances of the literature, a few dozens of runs are able to generate a very high proportion of the edges of the best solutions known. This characteristic is exploited in a new release of the Helsgaun’s implementation of the Lin-Kernighan heuristic (LKH) that is also able to produce rapidly extremely good solutions for non-Euclidean instances. The practical limits of the proposed method are discussed on a new type of problem instances arising in a manufacturing process, especially in 3D extrusion printing.


Keywords:
Article Type:
scientifique
Faculty:
Ingénierie et Architecture
School:
HEIG-VD
Institute:
IICT - Institut des Technologies de l'Information et de la Communication
Date:
2021-05
Pagination:
22 p.
Published in:
European Journal of Operational Research
Numeration (vol. no.):
2021
DOI:
ISSN:
03772217
Appears in Collection:

Note: The file is under embargo until: 2023-05-29


 Record created 2021-07-13, last modified 2021-07-16

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)