A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is one of the most popularCombinatorial Optimization Problem. It is well solicited for the large variety ofapplications that it can solve, but also for its difficulty to find optimal solutions. Oneof the variants of the TSP is the Generalized TSP (GTSP), where the TSP isconsidered as a special case which makes the GTSP harder to solve. We propose inthis paper a new memetic algorithm based on the well-known Breakout Local Search(BLS) metaheuristic to provide good solutions for GTSP instances. Our approach iscompetitive compared to other recent memetic algorithms proposed for the GTSPand gives at the same time some improvements to BLS to reduce its runtime.Keywords: Generalized Travelling Salesman Problem, Breakout Local Search,Memetic Algorithms, Iterated Local Search