A NEW HEURISTIC ALGORITHM FOR MULTIPLE TRAVELING SALESMAN PROBLEM

F. NURIYEVA, G. KIZILATES

[PDF]

Abstract

The Multiple Traveling Salesman Problem (mTSP) is a combinatorial optimization problem in NP-hard class. The mTSP aims to acquire the minimum cost for traveling a given set of cities by assigning each of them to a different salesman in order to create m number of tours. This paper presents a new heuristic algorithm based on the shortest path algorithm to find a solution for the mTSP. The proposed method has been programmed in C language and its performance analysis has been carried out on the library instances. The computational results show the efficiency of this method.

Keywords

multiple traveling salesman problem, heuristic algorithms, shortest path algorithm, insertion heuristic, graph theory.