Research Repository

Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

Karapetyan, D and Gutin, G (2012) 'Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem.' European Journal of Operational Research, 219 (2). 234 - 251. ISSN 0377-2217

[img]
Preview
Text
1005.5525v4.pdf - Accepted Version

Download (464kB) | Preview

Abstract

The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically.

Item Type: Article
Uncontrolled Keywords: Heuristics, Local search, Neighborhood, Generalized traveling salesman problem, Combinatorial optimization
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 24 May 2018 11:56
Last Modified: 24 May 2018 12:15
URI: http://repository.essex.ac.uk/id/eprint/22071

Actions (login required)

View Item View Item