The integration of Unmanned Aircraft Systems (UAS) into civil airspace is one of the most challenging problems for the automation of the Controlled Airspace, and the optimization of the UAS route is a key step for this process. In this paper, we optimize the planning phase of a UAS mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the UAS route depends on the air traffic and on the avoidance manoeuvre used to prevent possible conflicts. Two Air Traffic Management techniques, i.e., rerouting and holding, are modelled in order to maintain a minimum separation between the UAS and the piloted aircraft. Heuristic algorithms are proposed for the solution of the considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA). A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem (TDTSP), which allows holdings at mission way points, is proposed for solving the TDTSPPCA, and applied to the UAS route planning phase to minimize the total operational cost. Another formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and compared with the first one. Finally, computa- tional experiments on real-world air traffic data from Milano Linate Terminal Manoeuvring are reported to evaluate the performance of the proposed models and of the heuristic algorithms.
Article
View The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace