A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem

A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem

0.00 Avg rating0 Votes
Article ID: iaor20123257
Volume: 37
Issue: 11
Start Page Number: 1844
End Page Number: 1852
Publication Date: Nov 2010
Journal: Computers and Operations Research
Authors: , ,
Keywords: combinatorial optimization
Abstract:

The Generalized Traveling Salesman Problem (GTSP) is a generalization of the well‐known Traveling Salesman Problem (TSP), in which the set of cities is divided into mutually exclusive clusters. The objective of the GTSP consists in visiting each cluster exactly once in a tour, while minimizing the sum of the routing costs. This paper addresses the solution of the GTSP using a Memetic Algorithm. The originality of our approach rests on the crossover procedure that uses a large neighborhood search. This algorithm is compared with other algorithms on a set of 54 standard test problems with up to 217 clusters and 1084 cities. Results demonstrate the efficiency of our algorithm in both solution quality and computation time.

Reviews

Required fields are marked *. Your email address will not be published.