Traveling Salesman Problem (TSP): Firefly Algorithm

Traveling Salesman Problem (TSP) is one of combinatorial optimization problems. X TSP is NP-hard problem which defined as a set of cities and each city should be visited once with minimum tour length. This paper solved this problem using Firefly Algorithm (FA) and k-means clustering by three steps: cluster the nodes, finding optimal path in each cluster and connect the clusters. The first step is to divide all nodes into sub-problems using k-means clustering, the second step is to use FA to find optimal path in each cluster, finally connect all clusters and find the path between them. The experimental results show that FA with k-means clustering has better results than ant colony algorithm using clustering and FA in most of instances.
Keywords— Traveling Salesman Problem; Firefly Algorithm; k-means Clustering; NP-hard Problem
I. …show more content…
INTRODUCTION
Traveling Salesman Problem (TSP) is a classical combinatorial optimization problem, easy to describe but hard to solve. TSP consists of salesman and N cities, the goal of this problem is to visit each city by the salesman once with minimum tour length. The challenge in TSP is to find the route that has minimum distance. TSP can be presented via complete graph as follows: G = (V, E). Where V is the set of vertices which is equal to the number of cities and E is the set of edges between cities, each edge assigned the distance between any two cities