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

作者：Bontoux Boris^*; Artigues Christian; Feillet Dominique

来源：Computers & Operations Research, 2010, 37(11): 1844-1852.

DOI：10.1016/j.cor.2009.05.004

• Genetic Algorithm
• Traveling Salesman Problem
• Large neighborhood search

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.

• 出版日期2010-11