A novel discrete particle swarm optimization algorithm for the travelling salesman problems

Abstract

There are Optimization Problems that are too complex to be solved efficiently by deterministic methods. For these problems, where deterministic methods have proven to be inefficient, if not completely unusable, it is common to use approximate methods, that is, optimization methods that solve the problems quickly, regardless of their size or complexity, even if they do not guarantee optimal solutions. In other words, methods that find "acceptable" solutions, efficiently. One particular type of approximate method, which is particularly effective in complex problems, are metaheuristics. Particle Swarm Optimization is a population-based metaheuristic, which has been particularly successful. In order to broaden the application and overcome the limitation of Particle Swarm Optimization, a discrete version of the metaheuristics is proposed. The Discrete Particle Swarm Optimization, DPSO, will change the PSO algorithm so it can be applied to discrete optimization problems. This alteration will focus on the velocity update equation. The DPSO was tested in an instance of the Traveling Salesman Problem, att48, 48 points problems proposed by Padberg and Rinaldi, which showed some promising results.