POPMUSIC for the Travelling Salesman Problem

Keld Helsgaun, Eric Taillard

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
SprogEngelsk
TidsskriftEuropean Journal of Operational Research
Vol/bind471
Udgave nummer2
Sider420-429
Antal sider30
ISSN0377-2217
DOI
StatusUdgivet - 16 jan. 2019

Emneord

    Citer dette

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

    I: European Journal of Operational Research, Bind 471, Nr. 2, 16.01.2019, s. 420-429.

    Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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 -