Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver

Publikation: Bog/antologi/afhandling/rapportRapportForskning

Resumé

This report describes an enhancement of the Lin-Kernighan-Helsgaun TSP solver (LKH) for fast generation of candidate sets for very-large scale traveling salesman problems. Its implementation is based on a metaheuristic called POPMUSIC. The enhancement makes it possible to generate high-quality candidate sets in almost linear time, even for non-geometric instances.
OriginalsprogEngelsk
Udgivelses stedRoskilde
ForlagRoskilde Universitet
Antal sider13
StatusUdgivet - 18 jul. 2018

Emneord

    Citer dette

    @book{bc9216b473f144c0a93447a9e0201b1c,
    title = "Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver",
    abstract = "This report describes an enhancement of the Lin-Kernighan-Helsgaun TSP solver (LKH) for fast generation of candidate sets for very-large scale traveling salesman problems. Its implementation is based on a metaheuristic called POPMUSIC. The enhancement makes it possible to generate high-quality candidate sets in almost linear time, even for non-geometric instances.",
    keywords = "Traveling salesman problem, Lin-Kernighan, POPMUSIC, Candidate set generation, TSP",
    author = "Keld Helsgaun",
    year = "2018",
    month = "7",
    day = "18",
    language = "English",
    publisher = "Roskilde Universitet",

    }

    Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver. / Helsgaun, Keld.

    Roskilde : Roskilde Universitet, 2018. 13 s.

    Publikation: Bog/antologi/afhandling/rapportRapportForskning

    TY - RPRT

    T1 - Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver

    AU - Helsgaun, Keld

    PY - 2018/7/18

    Y1 - 2018/7/18

    N2 - This report describes an enhancement of the Lin-Kernighan-Helsgaun TSP solver (LKH) for fast generation of candidate sets for very-large scale traveling salesman problems. Its implementation is based on a metaheuristic called POPMUSIC. The enhancement makes it possible to generate high-quality candidate sets in almost linear time, even for non-geometric instances.

    AB - This report describes an enhancement of the Lin-Kernighan-Helsgaun TSP solver (LKH) for fast generation of candidate sets for very-large scale traveling salesman problems. Its implementation is based on a metaheuristic called POPMUSIC. The enhancement makes it possible to generate high-quality candidate sets in almost linear time, even for non-geometric instances.

    KW - Traveling salesman problem

    KW - Lin-Kernighan

    KW - POPMUSIC

    KW - Candidate set generation

    KW - TSP

    M3 - Report

    BT - Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver

    PB - Roskilde Universitet

    CY - Roskilde

    ER -