Applying K-means Clustering and Genetic Algorithm for Solving MTSP
In this paper, a new algorithm is designed to solve Multiple Traveling Salesman Problem (MTSP) that avoiding the path intersection among the traveling salesmen. There are three objectives in this problem including the shortest path of every salesman, the
- PDF / 345,084 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 355 Views
School of Computer Science, Wuhan University of Science and Technology, Wuhan 430081, China [email protected] 2 Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System, Wuhan 430081, China 3 School of Information Engineering, China University of Geosciences, Beijing 100083, China
Abstract. In this paper, a new algorithm is designed to solve Multiple Traveling Salesman Problem (MTSP) that avoiding the path intersection among the traveling salesmen. There are three objectives in this problem including the shortest path of every salesman, the balance of each salesmans task and avoiding the crosses of each routes. We combine the K-means algorithm and genetic algorithm. K-means algorithm is designed to divide all points into several subsets and choose the start city for the genetic algorithm, and then using GA to process every subsets in parallel. This method not only achieve these multiple objectives, but also use much less time, since we have divided all the points into several parts and make them calculated at the same time. Keywords: MTSP · K-means · Genetic algorithm · Parallel computing
1
Introduction
Over the years, there have been a lot of researches on multiple traveling salesman problem (MTSP), but they are all about vehicle path on the road [1]. If the way of transportation becomes unmanned aerial vehicle (UAV), there is a problem needed to consider. The path intersections of traveling salesman should be avoided, that can avoid collisions of UAV. UAV can be applied to military and civil fields, such as reconnaissance and surveillance in war, extinguishing fire, spraying pesticides and delivering goods. At present, the researches on MTSP have rarely mentioned the problem of avoiding crosses of paths. Applying these algorithms to UAV delivery will cause collisions. Moreover, most genetic algorithms for MTSP set some virtual points in order to translate MTSP to TSP [4,5]. But, if the scale of cities is large, the efficiency of the algorithm will decrease rapidly [6]. There have been many attempts to use GAs for clustering, it is also observed that these methods search faster than some of the other evolutionary algorithms c Springer Nature Singapore Pte Ltd. 2016 M. Gong et al. (Eds.): BIC-TA 2016, Part II, CCIS 682, pp. 278–284, 2016. DOI: 10.1007/978-981-10-3614-9 34
Applying K-means Clustering and Genetic Algorithm for Solving MTSP
279
used for clustering [7]. The searching capability of genetic algorithms is exploited in order to search for appropriate cluster centers in the feature space such that a similarity metric of the resulting clusters is optimized [8]. There also have been attempt to use parallel method for TSP in order to increase efficiency [9]. Over the years, varieties of intelligent algorithms have been introduced: Neural Networks [10–12], genetic algorithm, clustering. Artificial neural network algorithm is a kind of pattern matching algorithm which simulates biological neural network and genetic algorithm simulates the processing of biologica
Data Loading...
