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

Abstract: 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
Date: 2020-09-25
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:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2020.pdf First version, 2020 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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 ().