Experimental Study of a Hybrid Genetic Algorithm for the Multiple Travelling Salesman Problem. (27th October 2020)

• Record Type: Journal Article
• Authors: Al-Furhud, Maha Ata; Ahmed, Zakir Hussain
• Other Names: Dulikravich George S. Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2020(2020)
• Publication Date: 2020-10-27
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2020/3431420
• Languages: English
• ISSNs: 1024-123X

Abstract

Abstract : 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.