ACCOUNTING FOR AIRCRAFT LIMITATIONS IN ROUTE SEARCH ON GRAPH
M. Yu. Petrov, L. V. Vishnyakova · Vestnik komp iuternykh i informatsionnykh tekhnologii · 2025
Building a flight route is one of the main task, which must be solved before using an aircraft. The most common ways to set a route is to specify a set of points. Graph pathfinding algorithms such as Dijkstra's algorithm or A* are an extremely common means of solving this kind of problem. Not every arbitrary set of points is a valid route because aircraft may have technical limitations. Because of this, basic graph algorithms can sometimes produce incorrect routes. The purpose of this work is to demonstrate the described problem, as well as an algorithm for solving it. This paper presents two options for solving this problem. Both solutions are based on transferring constraints into the search graph structure. The first solution involves a complete reconstruction of the graph in which all invalid transitions are discarded. While the second solution involves a local reconstruction of the graph. Both solution allow using standard path-finding algorithms on new graph without any restrictions. The problem and its solution are demonstrated in the task of finding a flight route at the minimum altitude. The main technical limitation in the example is the minimum turning radius. The optimized function is the minimum flight altitude. The route is searched on a Digital Elevation Map. A Digital Elevation Map is a type of geospatial data that represents the terrain or topography of an area in a digital format. It typically consists of a gridded array of elevations at regular intervals, where each cell contains the height value above sea level for that specific location. The example demonstrates how the minimum turning radius changes the optimal route.