Variable neighborhood search (VNS) is a framework for building heuristics based upon systematic changes of neighborhoods both in a local search phase, to find a local minimum, and in a perturbation phase to escape from the large valley. In this chapter, we provide an overview of different VNS variants and describe how they can be used to solve some variants of the Traveling salesman problem. More precisely, we present different neighborhood structures that may be exploited, and show how they can be organized within variable neighborhood descent and variable neighborhood search heuristics. Finally, we provide insights on the performance of different VNS methodologies applied to two variants of theinebreak Traveling~salesman~problem.