Experimental Study of a Hybrid Genetic Algorithm for the Multiple Travelling Salesman Problem

Abstract EN

The multiple travelling salesman problem (MTSP), an extension of the well-known travelling salesman problem (TSP), is studied here.

In MTSP, starting from a depot, multiple salesmen require to visit all cities so that each city is required to be visited only once by one salesman only.

It is NP-hard and is more complex than the usual TSP.

So, exact optimal solutions can be obtained for smaller sized problem instances only.

For large-sized problem instances, it is essential to apply heuristic algorithms, and amongst them, genetic algorithm is identified to be successfully deal with such complex optimization problems.

So, we propose a hybrid genetic algorithm (HGA) that uses sequential constructive crossover, a local search approach along with an immigration technique to find high-quality solution to the MTSP.

Then our proposed HGA is compared against some state-of-the-art algorithms by solving some TSPLIB symmetric instances of several sizes with various number of salesmen.

Our experimental investigation demonstrates that the HGA is one of the best algorithms.