The aircraft Conflict Detection and Resolution (CDR) problem in air traffic management consists of finding a new configuration for a set of aircraft such that their conflict situations are avoided. A conflict situation occurs if two or more aircraft violate the safety distances that they have to keep during the flight. A geometric construction is used in order to detect the conflict situations between each pair of aircraft under consideration. In this paper we propose a VNS approach for solving the CDR by turn changes based on the reformulation of the problem as an unconstrained one by an exterior penalty function method. The first improvement local search and the shaking operator consist of changing direction of the aircraft by a given parameter and moving several aircraft at once by a random parameter based on the k-value of the VNS approach, respectively. This metaheuristic compares favourably with previous best known methods. It is worth to point out the astonishing time required to obtain the first feasible solution, which is crucial for this specific problem whose response time should be almost in real time in order to be useful in a real-life problem. A comparative study with up to 25 aircraft is presented.