Efficient assignment of flight levels: a variable neighbourhood search approach
提出一种基于变邻域搜索的元启发式方法，在规划阶段分配飞行高度层以消除冲突，使超过97%的航班获得理想或接近理想的高度层，减少延误、成本和排放。
Air traffic management (ATM) is a complex process that includes objectives such as minimising delays, costs, and environmental impacts, with safety being a top priority. Growth in air traffic over the past few decades has increased the complexity of this process. In European airspace, ATM is more crucial because of the high traffic density. A key aspect of this management strategy is the allocation of flight levels in the planning phase to avoid conflicts before takeoff. Therefore, a model is required for the allocation of flight levels in the planning phase to eliminate all conflicts and meet objectives such as minimising cost and emissions. In the absence of conflicts, planning delays in takeoff are avoided and in-flight corrective manoeuvres (such as changes in altitude or speed during flights) are reduced, reducing the workload of the controller. This study proposed a method based on a metaheuristic variable neighbourhood search (VNS) strategy on a multistart framework. Various experiments with simulated instances demonstrated that this method improves the results obtained using commercial software. In addition, tests based on real data (both in Europe and Spain) showed satisfactory results in terms of economics and sustainability.PRACTITIONER SUMMARYIn Europe, air traffic management (ATM) is an increasingly complex task due to high traffic density and the increase in traffic in recent decades. An important aspect of this traffic management is the allocation of altitude levels to different flights during planning. The main objective is to avoid conflicts, i.e., to prevent two flights from passing through the same point at the same time. Conflicts that are not avoided in the planning phase must be avoided later through operations such as takeoff delays or corrective manoeuvres during flight, changes in direction, altitude, speed, etc. All these types of manoeuvres increase the pressure and workload on control systems. On the other hand, from an economic and ecological point of view, it is important that each flight is assigned its “ideal level” (i.e., the level where it consumes the least fuel and produces the least emissions) or at least a level close to the ideal. The article proposes and describes a method for assigning flight levels which, based on tests using real data (in Spain and Europe), manages to avoid all conflicts and assign ideal or near-ideal flight levels to over 97% of flights, even in scenarios with a high ratio of conflict potential. In short, the proposed method can improve ATM in such important aspects as increased safety, reduced stress on control systems, reduced costs, and reduced emissions.