POPMUSIC for the travelling salesman problem

Taillard, Éric D. (School of Management and Engineering Vaud, HES-SO // University of Applied Sciences Western Switzerland) ; Helsgaun, Keld (Department of Computer Science, Roskilde University, Roskilde, Denmark)

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.


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:
2019-01
Pagination:
10 p.
Published in:
European Journal of Operational Research
Numeration (vol. no.):
2019, vol. 272, no. 2, pp. 420-429
DOI:
ISSN:
0377-2217
Appears in Collection:

Note: The file is under embargo until: 2020-06-23


 Record created 2019-11-26, last modified 2019-12-17

Fulltext:
Download fulltext
PDF

Rate this document:

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