POPMUSIC for the Travelling Salesman Problem

Eric Taillard, Keld Helsgaun

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstract

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.
OriginalsprogEngelsk
TidsskriftEuropean Journal of Operational Research
Vol/bind272
Udgave nummer2
Sider (fra-til)420-429
ISSN0377-2217
DOI
StatusUdgivet - 16 jan. 2019

Citer dette