A memetic algorithm for the generalized traveling salesman problem

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

Full description

Saved in:
Bibliographic Details
Published in:Natural computing 2010-03, Vol.9 (1), p.47-60
Main Authors: Gutin, Gregory, Karapetyan, Daniel
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Complex Systems
Computer Science
Evolutionary Biology
Genetic algorithms
Processor Architectures
Theory of Computation
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1567-7818
1572-9796
DOI:10.1007/s11047-009-9111-6