K-means Clustering Algorithm and Meta-heuristics for Multiple Traveling Salesman Problems

R. Nallusamy*, K. Duraiswamy**, R. Dhanalaksmi***, P. Parthiban****
* Professor, Department of Computer Science and Engineering, K.S. Rangasamy College of Technology, Tiruchengode.
** Dean (Academic), K.S. Rangasamy College of Technology, Tiruchengode.
*** D-Link India Ltd, Bangalore.
**** Lecturer, Department of Production Engineering, National Institute of Technology, Tiruchirappalli.
Periodicity:October - December'2009
DOI : https://doi.org/10.26634/jse.4.2.1069

Abstract

This paper deals with generating of an optimized route for multiple Travelling Salesman Problem (mTSP). We used a methodology of clustering the given cities depending upon the number of salesman and each cluster is allotted to a salesman. “K- Means clustering” algorithm has been used for easy clustering of the cities. In this way the mTSP has been converted into TSP which is simple in computation compared to mTSP. After clustering, an optimized route is generated for each salesman in his allotted cluster. Once the clustering had been done and after the cities were allocated to the various salesmen, each cluster/tour was taken as an individual Traveling Salesman problem (TSP) and the steps of Genetic Algorithm(GA) were applied to the cluster and iterated to obtain the most optimal value of the distance after convergence takes place. Now every cluster was again solved as a TSP by applying the Ant Colony Optimization (ACO) algorithm to determine the optimal distance value. The algorithms were simulated and executed in “MATLAB” software. After the application of both the heuristic techniques, it was found that the Ant Colony Optimization algorithm gave a better result and a more optimal tour for small size mTSPs in short computational time than Genetic Algorithm due to the extensive search and constructive nature of the algorithm.

Keywords

Multiple Travelling Salesman Problem, K-means Clustering, Genetic Algorithm, Ant Colony Optimization Combinatorial Optimization.

How to Cite this Article?

R. Nallusamy, K. Duraiswamy , R. Dhanalaksmi and P. Parthiban (2009). K-means Clustering Algorithm and Meta-heuristics for Multiple Traveling Salesman Problems, i-manager’s Journal on Software Engineering, 4(2),16-32. https://doi.org/10.26634/jse.4.2.1069

References

[1]. A.E. Rizzoli, R. Montemanni , E. Lucibello (2007), L.M Gambardella, “Ant Colony Optimization for real world vehicle routing problems”, Swarm Intelligence, Springer New York, Vol. 1, No. 2, pp 135-151 December.
[2]. Allan Larsen (2000), A study material, The Dynamic Vehicle Routing Problem, IMM.
[3]. Anderberg, M.R. (1973), Cluster analysis for applications, Academic press, New York.
[4]. Arthur .E. Carter, Cliff. T. Ragsdale (2006), “A New Approach to solving the Multiple Travelling Salesman Problem using Genetic Algorithm”, European Journal of operational research, Vol. 175, No.1, pp. 246-257.
[5]. Bektas, T. (2005), “The multiple traveling salesman problem: an overview of formulations and solution procedures” Omega, In Press, Corrected Proof, Available online www.sciencedirect.com.
[6]. Bellmore, M. and Hong, S. (1974), “Transformation of multisalesmen problem to the standard traveling salesman problem”, Journal of the Association Computer Machinery, Vol. 21, pp.500-550
[7]. Bezalel, G. and Kizhanathan, S. (1986), “An optimal solution method for large-scale multiple traveling salesmen problems”, Operations Research, Vol. 34, No. 5, pp.698-718.
[8]. Buthainah Fahran, Al-Dulaimi and Hamsa (2008), A. Ali, “Enhanced Travelling Salesman Problem solving by Genetic Algorithm Technique”, World Academy of Science, Engg. and Tech.,pp.297-301.
[9]. David S Johnson (2001), “Travelling Salesman Problem”, DIMACS Implementation Challenge, AT&T.
[10]. Ding Chao, Cheng ye, He Miao (2007), “Two level genetic algorithm for clustered Travelling Salesman Problem with Application in large scale TSPs”, Tsinghua Science and technology, Vol. 12, No. 4, pp.459-465, August.
[11]. Gilbert, K.C. and Hofstra, R.B. (1992), “A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem”, Decision Sciences, Vol. 23, pp.250-259.
[12]. Goldberg, D.E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley, Reading, MA.
[13]. Hannes Schabauer, Erich Schikuta, Thomas Weishaupl (2005), “Solving Very Large Travelling Salesman Problems by SOM parallelization on cluster architecture”, PDCAT: pp.954-958.
[14]. Hoffman K, P. M. (1996). "Traveling Salesman Problem." Encyclopedia of Operations Research, pp.76- 83.
[15]. Holland, J. (1975), Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA.
[16]. Jan.M.Weiner and Thora Tenbrink (2008), “Travelling Salesman Problem: The Human Case”, KI: Themenheft KI und Kognition, 1/08, pp.18-22.
[17]. Jean-Yves Potvin (1996), “Genetic Algorithm for the Travelling Salesman Problem” Annals of Operations Research, pp.339-370.
[18]. Jorg Homberger and Hermann Gehring (2005), “A Two phase hybrid meta-Heuristics for the vehicle routing problem with time windows”, European Journal of Operational Research, 162(1), pp.220-238.
[19]. Klaus Meer (2007), “Simulated Annealing Versus Metropolis for a TSP instance” Information Processing Letters, Vol.104, No. 6, pp.216-219, December.
[20]. Langdon, W.B., and Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag, Heidelberg.
[21]. Lin, S. (1965), “Computer solutions of the traveling salesman problem”. The Bell System, Technical Journal, Vol. 44, pp.2245-2269.
[22]. Marce Turkensteen, Diptesh Ghosh, Boris Goldengorin, Gerard Sierksma (2008), “Tolerance Based Branch and Branch Algorithm for the ATSP”, European Journal of Operational Research, Vol. 189, No. 3, pp.775- 788, September.
[23]. Max Manfrin, Maurro Birattari, Thomas Stutzle, and Margo Darigo (2006), “Parellel Ant Colony Optimization for Travelling Salesman Problem”, ANTS Workshop: pp 224-234.
[24]. Pan Junjie and Wang Dingwei (2006), “An Ant Colony Optimization Problem for Multiple Travelling salesman Problem”, First International Conference on Innovative Computing, Information and Control, Vol. 1, pp. 210-213.
[25]. Sait, S.M., and Youssef (1999), H. “Iterative Computer algorithms with Applications in Engineering: Solving Combinatorial Optimization Problems”, IEEE Computer Society, Los Alamitos, CA.
[26]. Snezana Mitrovic-Minic and Ramesh Krishnamurti (2006), “Multiple Travelling salesman Problem with time windows: bounds for Minimum Number of vehicles based on the precedence graph”, Operations Research Letters, Accepted for publication.
[27]. Tolga Bektashave (2006), “The Multiple Travelling Salesman Problem: An Overview of formulations and solution procedures”, Omega Vol. 34, No. 3, pp.209-219, June.
[28]. Voudouris, C. and E. Tsang (1999), "Guided Local Search and Its Application to the Traveling Salesman Problem." European Journal of Operational Research, Vol.113, No. 2, pp.469-499.
[29]. Yoshiyuki Nakamichi, Takaya Arita (2001), “Diversity control in Ant Colony Optimization”, Proceedings of the Inaugural Workshop on Artificial Life AL'01, pp.70-78.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.