New Variable Neighborhood Search Structure for Travelling Salesman Problems

Abstract

In the traveling salesman problem, there are a collection of cities and travel cost between each pair of them. The aim is to find the minimum cost way of visiting all cities and returning to the starting point. This kind of problem is deceptive and one of the most intensely studied problems in computational mathematics. No effective solution method is known for the general case. Variable Neighborhood Search (VNS) is a recent metaheuristic for solving combinatorial and global optimization problems whose basic idea is systematic change of neighborhood within a local search. Its development has been rapid, with several dozen papers already published or to appear. Many extensions have been made, mainly to allow solution of large problem instances. In most of them, an effort has been made to keep the simplicity of the basic scheme. In this study, variable neighborhood search structure as a metaheuristic optimization technique and neighborhood approximation is developed. K-opt neighborhood structure is generated. This new structure’s solvability in benchmark and symmetric traveling salesman problem instances is tested, and results are listed.