Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

The equality generalized traveling salesman problem (E-GTSP) is an extension of the traveling salesman problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit every cluster exactly once. It is well known that any instance of E-GTSP can be transformed into a standard asymmetric instance of the TSP, and therefore solved with a TSP solver. This paper evaluates the performance of the state-of-the art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed E-GTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a well-known library of benchmark instances, GTSPLIB, could be solved to optimality in a reasonable time. In addition, it was possible to solve a series of new very-large-scale instances with up to 17,180 clusters and 85,900 vertices. Optima for these instances are not known but it is conjectured that LKH has been able to find solutions of a very high quality. The program’s performance has also been evaluated on a large number of instances generated by transforming arc routing problem instances into E-GTSP instances. The program is free of charge for academic and non-commercial use and can be downloaded in source code.
OriginalsprogEngelsk
TidsskriftMathematical Programming Computation
Vol/bind7
Udgave nummer3
Sider (fra-til)269-287
Antal sider19
ISSN1867-2949
DOI
StatusUdgivet - sep. 2015

Citer dette

@article{c2506f95b9244af38e52792f329ef1db,
title = "Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm",
abstract = "The equality generalized traveling salesman problem (E-GTSP) is an extension of the traveling salesman problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit every cluster exactly once. It is well known that any instance of E-GTSP can be transformed into a standard asymmetric instance of the TSP, and therefore solved with a TSP solver. This paper evaluates the performance of the state-of-the art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed E-GTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a well-known library of benchmark instances, GTSPLIB, could be solved to optimality in a reasonable time. In addition, it was possible to solve a series of new very-large-scale instances with up to 17,180 clusters and 85,900 vertices. Optima for these instances are not known but it is conjectured that LKH has been able to find solutions of a very high quality. The program’s performance has also been evaluated on a large number of instances generated by transforming arc routing problem instances into E-GTSP instances. The program is free of charge for academic and non-commercial use and can be downloaded in source code.",
author = "Keld Helsgaun",
note = "The developed software is free of charge for academic and non-commercial use and can be downloaded in source code together with an extended version of GTSPLIB and current best g-tours for these instances via http://www.ruc.dk/~keld/research/GLKH/",
year = "2015",
month = "9",
doi = "10.1007/s12532-015-0080-8",
language = "English",
volume = "7",
pages = "269--287",
journal = "Mathematical Programming Computation",
issn = "1867-2949",
publisher = "Physica-Verlag",
number = "3",

}

Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm. / Helsgaun, Keld.

I: Mathematical Programming Computation, Bind 7, Nr. 3, 09.2015, s. 269-287.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm

AU - Helsgaun, Keld

N1 - The developed software is free of charge for academic and non-commercial use and can be downloaded in source code together with an extended version of GTSPLIB and current best g-tours for these instances via http://www.ruc.dk/~keld/research/GLKH/

PY - 2015/9

Y1 - 2015/9

N2 - The equality generalized traveling salesman problem (E-GTSP) is an extension of the traveling salesman problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit every cluster exactly once. It is well known that any instance of E-GTSP can be transformed into a standard asymmetric instance of the TSP, and therefore solved with a TSP solver. This paper evaluates the performance of the state-of-the art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed E-GTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a well-known library of benchmark instances, GTSPLIB, could be solved to optimality in a reasonable time. In addition, it was possible to solve a series of new very-large-scale instances with up to 17,180 clusters and 85,900 vertices. Optima for these instances are not known but it is conjectured that LKH has been able to find solutions of a very high quality. The program’s performance has also been evaluated on a large number of instances generated by transforming arc routing problem instances into E-GTSP instances. The program is free of charge for academic and non-commercial use and can be downloaded in source code.

AB - The equality generalized traveling salesman problem (E-GTSP) is an extension of the traveling salesman problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit every cluster exactly once. It is well known that any instance of E-GTSP can be transformed into a standard asymmetric instance of the TSP, and therefore solved with a TSP solver. This paper evaluates the performance of the state-of-the art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed E-GTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a well-known library of benchmark instances, GTSPLIB, could be solved to optimality in a reasonable time. In addition, it was possible to solve a series of new very-large-scale instances with up to 17,180 clusters and 85,900 vertices. Optima for these instances are not known but it is conjectured that LKH has been able to find solutions of a very high quality. The program’s performance has also been evaluated on a large number of instances generated by transforming arc routing problem instances into E-GTSP instances. The program is free of charge for academic and non-commercial use and can be downloaded in source code.

UR - http://www.akira.ruc.dk/~keld/research/GLKH/

U2 - 10.1007/s12532-015-0080-8

DO - 10.1007/s12532-015-0080-8

M3 - Journal article

VL - 7

SP - 269

EP - 287

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

SN - 1867-2949

IS - 3

ER -