Discrete Mayfly Algorithm for Spherical Asymmetric Traveling Salesman Problem

The asymmetric traveling salesman problem (ATSP), as a branch of the traveling salesman problem, aims to find a group of circuits when a salesman travels all cities at the minimum cost and returns to the starting city under the condition of different round-trip costs between the two cities. Mayfly algorithm (MA) is a swarm-based metaheuristic algorithm, which has been applied to many fields successfully. In this paper, we arrange all cities on the sphere. A discrete mayfly algorithm (DMA) for solving spherical asymmetric traveling salesman problem is proposed. The algorithm applies inver-over operator, crossover operator and 3-opt operator to simplify the parameters of the algorithm, enrich the diversity of the population and enhance the local search ability. By experimenting, analyzing and comparing the effects of DMA and other metaheuristic algorithms in twelve scales, this study proves that the proposed algorithm is superior to others for the spherical ATSP, especially in high-dimensional cases.