A novel hybrid approach for solving the multiple traveling salesmen problem

Abstract EN

The multiple Travelling Salesmen Problem (mTSP) is one of the most popular and import- ant operational research problems.

It is a problem where n salesmen have to visit m cities such that each salesman has to visit at least one aty and all the aties should be visited exactly once, starting and ending at one specific city.

In this paper a new hybrid approach called AQOptGA is proposed to sotve the mTSP.

AQOptGA is a combination of three algonthms: Modified Ant Colony, 2-Opt and Genetic Algonthm.

Ant Colony-based algonthm is used to generate solutions on which the 2-Opt edge »change algonthm is applied to enhance the obtained solutions.

A Genetic Algonthm is then used to again improve the quality of the solutions.

The reason behind combining the above-mentioned algonthms is to exploit their strengths in both global and local searches.

The proposed approach is evaluated using vanous data instances from standard benchmarks.

Using the TSPLIB benchmarks for large-sced instances, AC20ptGA shows better results than M-GELS, the current best known approach.

For medium and small-sced data instances, AC20ptGA shows better results than other approaches and comparable results to M-GELS.

Using the MTSP benchmarks (MTSP-51, MTSP-100 and MTSP-1S0), AC20ptGA outperforms other methods for number of salesmen less than 10 and is competitive with NMACO (BKS) for 10 salesmen.