A new approach to solve multiple traveling salesman problems

Abstract

Shortest Path (SP) problem can be used to solve many real world oriented problems such as routing in telecommunication networks, vehicle routing in logistics management and pickup and delivery systems. The SP based multiple traveling salesman problems (mTSPs) are complex and Nondeterministic Polynomial-time hard (NP-hard) combinatorial optimization problems. The nature inspired algorithms such as Artificial Intelligence (AI) heuristics are suitable to such type of problems. This research focuses on solving the mTSPs by using hybrid AI-heuristics techniques. The existing algorithms for Traveling Salesman Problem (TSP) have some limitations. Most of the researchers have solved simple Traveling Salesman Problems (TSPs) by using various approximation algorithms. This research proposes a two/three phase hybrid AI-heuristics for city allocation to salespersons and finding a suitable sequence of different cities through which a salesperson can travel. The main aim is to solve the large sized mTSPs by converting them into simple TSPs using hybrid AI-heuristics. Initially, two stage AI-heuristics is applied and then, three stage AI-heuristics is applied to solve the problem. In the first stage, a well-known k-means clustering algorithm is used to allot different cities to a particular salesperson, where k is the number of clusters or salespersons. The results have proved that the simple clustering like k-means clustering proves to be effective as it is able to group the nodes as clusters in an intelligent manner with reduced convergence time. It is known from the results of mTSP that the three phase hybrid GA provides suitable solutions for large scale problems and hybrid ACO provides suitable solutions for small sized problems. The results indicate that the hybrid nature inspired algorithms are able to solve the mTSPs quite efficiently. Consequently, with the practical application, they can significantly improve the operational efficiency of an organization in its application domain. newline newline newline