A VNS metaheuristic for solving the aircraft conflict detection and resolution problem by performing turn changes

Abstract

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 conflict situations between them are avoided. A conflict situation arises if two or more aircraft violate the safety distances that they must maintain in flight. In this paper we propose a Variable Neighborhood Search approach for solving the CDR by turn changes. This metaheuristic compares favorably with previous best known methods for solving the Mixed Integer Nonlinear Programming (MINLP) model proposed elsewhere. It is worth pointing out the astonishingly short time in which the first feasible solution is obtained. This is crucial for this specific problem, where a response must be provided almost in real time if it is to be useful in a real-life problem. A comparative study between the performance of the new approach, a state-of-the-art MINLP solver and our Sequential Integer Linear Optimization approach proposed elsewhere is reported, using a testbed of instances with up to 25 aircraft.