Open AccessImplementation of K-Means and crossover ant colony optimization algorithm on multiple traveling salesman problem
Author(s) -
N Kusumahardhini,
Gatot Fatwanto Hertono,
Bevina D. Handari
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1442/1/012035
Subject(s) - travelling salesman problem , crossover , ant colony optimization algorithms , mathematical optimization , generalization , computer science , bottleneck traveling salesman problem , mathematics , 2 opt , algorithm , artificial intelligence , mathematical analysis
Multiple Traveling Salesman Problem (MTSP) is a generalization of the Traveling Salesman Problem (TSP). MTSP is an optimization problem to find the minimum total distance of m salesmen tours to visit several cities in which each city is only visited exactly by one salesman, starting from origin city called depot and return to depot after the tour is completed. In this paper, K-Means and Crossover Ant Colony Optimization (ACO) are used to solve MTSP. The implementation is observed on three datasets from TSPLIB with 2, 3, 4, and 8 salesmen. Analysis of results using K-Means and Crossover ACO will be compared. The effect of selecting a city as depot on the total travel distance of tour will also be analyzed.