A Comparison between Heuristic and Meta-Heuristic Methods for Solving the Multiple Traveling Salesman Problem

Authors: San Nah Sze, Wei King Tiong

Abstract:

The multiple traveling salesman problem (mTSP) can be used to model many practical problems. The mTSP is more complicated than the traveling salesman problem (TSP) because it requires determining which cities to assign to each salesman, as well as the optimal ordering of the cities within each salesman's tour. Previous studies proposed that Genetic Algorithm (GA), Integer Programming (IP) and several neural network (NN) approaches could be used to solve mTSP. This paper compared the results for mTSP, solved with Genetic Algorithm (GA) and Nearest Neighbor Algorithm (NNA). The number of cities is clustered into a few groups using k-means clustering technique. The number of groups depends on the number of salesman. Then, each group is solved with NNA and GA as an independent TSP. It is found that k-means clustering and NNA are superior to GA in terms of performance (evaluated by fitness function) and computing time.

Keywords: Multiple Traveling Salesman Problem, GeneticAlgorithm, Nearest Neighbor Algorithm, k-Means Clustering.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059677

References:

[1] E. Carter and C. T. Ragsdale, ''A new approach to solving the multiple traveling salesperson problem using genetic algorithms,'' European Journal of Operational Research, vol. 174, pp. 246-257, 2005.
[2] T. Bektas, ''The multiple traveling salesman problem: an overview of the formulations and solution procedures,'' Omega, vol. 34, pp. 209-219, 2006.
[3] M. Matteucci. (2006, October 18). A Tutorial on Clustering Algorithms
[Online]. Available: http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/kmeans.html,
[4] S. N. Sze, ''Study on Genetic Algorithms and Heuristic Method for Solving Traveling Salesman Problem,'' M.S. dissertation, Faculty of Science, Universiti Teknologi Malaysia, Johor, Malaysia, 2004.