A NEW HEURISTIC ALGORITHM FOR MULTIPLE TRAVELING SALESMAN PROBLEM

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.

References

1. Lawler,E., Lenstra,J., Kan,A., and Shmoys,D., (1985), The traveling salesman problem: a guided tour of combinatorial optimization, Chichester, Wiley, 11, pp.201-209.
2. Kara,I. and Bektas,T., (2006), Integer linear programming formulations of multiple salesman problems and its variations, European Journal of Operational Research, 174(3), pp.1449-1458.
3. Dantzig,G., Fulkerson,D., and Johnson,S.M., (1954), Solution of a large-scale traveling salesman prob- lem, Operational Research 2, pp. 393-410.
4. Bektas,T., (2006), The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34(3), pp.209-219.
5. Matai,R., Singh,P.S., and Mittal,L.M., (2010), Traveling salesman problem: An overview of applica- tions, formulations, and solution approaches, traveling salesman problem, theory and applications, pp.1-24.
6. Averbakh,I., Lebedev,V., and Tsurkov,V., (2008), Nash equilibria solutions in the competitive sales- men problem on a network, Applied and Computational Mathematics, An International Journal, 7(1), pp.54-65.
7. Park,Y., (2001), A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines, Int. Journal of Productions Econ., 73(2), pp.175-188. [8] Traveling salesman problem and related problems library doi: http://www.iwr.uni