Research Repository

A memetic algorithm for the generalized traveling salesman problem

Gutin, G and Karapetyan, D (2010) 'A memetic algorithm for the generalized traveling salesman problem.' Natural Computing, 9 (1). 47 - 60. ISSN 1567-7818

0804.0722v3.pdf - Accepted Version

Download (188kB) | Preview


The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances. © 2009 Springer Science+Business Media B.V.

Item Type: Article
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 24 May 2018 12:22
Last Modified: 30 Jan 2019 16:20

Actions (login required)

View Item View Item