A Memetic Algorithm for the Generalized Traveling Salesman Problem

Abstract

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.

15 pages, to appear in Natural Computing, Springer, available online: http://www.springerlink.com/content/5v4568l492272865/?p=e1779dd02e4d4cbfa49d0d27b19b929f&pi=13

Cited by in corpus (12)

• Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem
• Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem
• An Integrated Approach to Goal Selection in Mobile Robot Exploration
• Generalized Traveling Salesman Problem Reduction Algorithms
• Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem
• A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem
• A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem
• A Unifying Survey of Reinforced, Sensitive and Stigmergic Agent-Based Approaches for E-GTSP
• An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem
• Combining Monte-Carlo and Hyper-heuristic methods for the Multi-mode Resource-constrained Multi-project Scheduling Problem
• A Carbon Aware Ant Colony System (CAACS)
• Design, Evaluation and Analysis of Combinatorial Optimization Heuristic Algorithms