A Parallel Variable Neighborhood Search Approach for Solving the Traveling Salesman Problem

Abstract: This paper presents a parallel Variable Neighborhood Search (pVNS) algorithm for solving instances of the Traveling Salesman Problem (TSP). pVSN uses two parallelization levels in order to reach near-optimal solutions for TSP instances. This parallel approach is evaluated by means of an experimental multi-clusters of computers in which the nodes in each cluster uses several threads for calculating the path cost of a candidate solution and a message passing based communication scheme between two clusters is implemented for sharing their solutions. The results obtained indicate that the use of this parallelization scheme leads to an execution time reduction of the VNS method and one near optimal solution is reached due to a best exploitation of the solution space.