New Neighborhoods and an Iterated Local Search Algorithm for the Generalized Traveling Salesman Problem
Jeanette Schmidt () and
Stefan Irnich ()
Additional contact information
Jeanette Schmidt: Johannes Gutenberg University
Stefan Irnich: Johannes Gutenberg University
No 2020, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
The generalized traveling salesman problem (GTSP) is the problem of finding a cost-minimal cycle in a clustered graph so that exactly one vertex of every cluster is contained in the cycle. We introduce three new GTSP neighborhoods that allow the simultaneous permutation of the sequence of the clusters and the selection of vertices from each cluster. The three neighborhoods and some known neighborhoods from the literature are combined into a simple but effective iterated local search (ILS) for the GTSP. The simplicity of the ILS consists in its straightforward random neighborhood selection within the local search and an ordinary record-to-record ILS acceptance criterion. The computational experiments on four symmetric standard GTSP libraries show that, with some small refinements, the ILS can compete with state-of-the-art algorithms, although it is simple in structure and less involved to code compared to many other metaheuristics.
Keywords: traveling salesman; generalized traveling salesman problem; iterated local search; variable neighborhood descent (search for similar items in EconPapers)
Pages: 23 pages
New Economics Papers: this item is included in nep-cmp and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2020.pdf First version, 2020 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:2020
Access Statistics for this paper
More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().