POPMUSIC for the Travelling Salesman Problem

Keld Helsgaun, Eric Taillard

Research output: Contribution to journalJournal articleResearchpeer-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.
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.
LanguageEnglish
JournalEuropean Journal of Operational Research
Volume471
Issue number2
Pages420-429
Number of pages30
ISSN0377-2217
DOIs
StatePublished - 16 Jan 2019

Keywords

  • Travelling Salesman
  • Local Search
  • POPMUSIC
  • Large-Scale Optimization
  • Metaheuristics

Cite this

@article{2c255c1f7b4544df81b1c2fd9082d550,
title = "POPMUSIC for the Travelling Salesman Problem",
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.",
keywords = "Travelling Salesman, Local Search, POPMUSIC, Large-Scale Optimization, Metaheuristics",
author = "Keld Helsgaun and Eric Taillard",
year = "2019",
month = "1",
day = "16",
doi = "doi.org/10.1016/j.ejor.2018.06.039",
language = "English",
volume = "471",
pages = "420--429",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier BV",
number = "2",

}

POPMUSIC for the Travelling Salesman Problem. / Helsgaun, Keld; Taillard, Eric.

In: European Journal of Operational Research, Vol. 471, No. 2, 16.01.2019, p. 420-429.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - POPMUSIC for the Travelling Salesman Problem

AU - Helsgaun,Keld

AU - Taillard,Eric

PY - 2019/1/16

Y1 - 2019/1/16

N2 - 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.

AB - 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.

KW - Travelling Salesman

KW - Local Search

KW - POPMUSIC

KW - Large-Scale Optimization

KW - Metaheuristics

U2 - doi.org/10.1016/j.ejor.2018.06.039

DO - doi.org/10.1016/j.ejor.2018.06.039

M3 - Journal article

VL - 471

SP - 420

EP - 429

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -