
Solving a traveling salesman problem using meta-heuristics
Author(s) -
Anahita Sabagh Nejad,
Gábor Fazekas
Publication year - 2022
Publication title -
iaes international journal of artificial intelligence
Language(s) - English
Resource type - Journals
eISSN - 2252-8938
pISSN - 2089-4872
DOI - 10.11591/ijai.v11.i1.pp41-49
Subject(s) - travelling salesman problem , computer science , 2 opt , cluster analysis , heuristics , mathematical optimization , christofides algorithm , path (computing) , traveling purchaser problem , algorithm , mathematics , artificial intelligence , programming language
In this article, we have introduced an advanced new method of solving a traveling salesman problem (TSP) with the whale optimization algorithm (WOA), and K-means which is a partitioning-based algorithm used in clustering. The whale optimization algorithm first was introduced in 2016 and later used to solve a TSP problem. In the TSP problem, finding the best path, which is the path with the lowest value in the fitness function, has always been difficult and time-consuming. In our algorithm, we want to find the best tour by combining it with K-means which is a clustering method. In other words, we want to divide our problem into smaller parts called clusters, and then we join the clusters based on their distances. To do this, the WOA algorithm, TSP, and K-means must be combined. Separately, the WOA-TSP algorithm which is an unclustered algorithm is also implemented to be compared with the proposed algorithm. The results are shown through some figures and tables, which prove the effectiveness of this new method.