A NEW HEURISTIC ALGORITHM FOR MULTIPLE TRAVELING SALESMAN PROBLEM

Yıl 2017, Cilt: 7 Sayı: 1, 101 - 109, 01.06.2017

F. Nuriyeva G. Kizilates

Öz

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.

Anahtar Kelimeler

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

Kaynakça

• 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.
• 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.
• Dantzig,G., Fulkerson,D., and Johnson,S.M., (1954), Solution of a large-scale traveling salesman prob- lem, Operational Research 2, pp. 393-410.
• Bektas,T., (2006), The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34(3), pp.209-219.
• 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.
• 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.
• 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