A Water Flow-Like Algorithm for the Travelling Salesman Problem

The water flow-like algorithm (WFA) is a relatively new metaheuristic that performs well on the object grouping problem encountered in combinatorial optimization. This paper presents a WFA for solving the travelling salesman problem (TSP) as a graph-based problem. The performance of the WFA on the TSP is evaluated using 23 TSP benchmark datasets and by comparing it with previous algorithms. The experimental results show that the proposed WFA found better solutions in terms of the average solution and the percentage deviation of the average solution from the best-known solution. 1. Introduction The travelling salesman problem (TSP) is a classic combinatorial optimization problem (COP), which was introduced many years ago in 1985 [1]. The TSP searches for the shortest path among a set of cities with known distances between pairs of cities to find the route solution. The route solution can be articulated as a complete graph with a set of vertices, which is a set of edges weighted by the distance between two vertices (cities), to find the shortest route by visiting each city exactly once and returning to the original city. Numerous approaches have been proposed and have obtained good solutions. However, they vary in terms of complexity and efficiency and in being able to solve the TSP at various levels of complexity and size (small, medium, and large). Earlier studies use linear programming Dantzig et al. [2], dynamic formulation Held and Karp [3], branch and bound [4], and branch and cut [1], but their ability is limited to small problems (less than 40 cities). Later, artificial intelligent approaches were proved to have the ability to solve more complex problems; one of these approaches, the self-organized neural network [5–7], was later expanded as a metaheuristic. A metaheuristic can optimize a complex problem by searching through many candidate solutions with few or no assumptions about the problem being solved and without any guarantee of finding the optimal solution. Some metaheuristics use either a single solution-based approach (e.g. tabu search (TS) and simulated annealing (SA)) or a population-based approach (e.g. genetic algorithm (GA)) [8–10], while others use swarm intelligence (e.g. ant colony optimization (ACO)) [11], and recently, hybrid metaheuristics have been proposed [7, 12]. The results show that hybrid metaheuristics can produce the best result using 23 benchmark TSP datasets. Recently, a new metaheuristic algorithm known as the water flow-like algorithm (WFA) has been proposed [13]. The algorithm is inspired by water flowing from