The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace
Furini, Fabio; Persiani, Carlo Alfredo; Toth, Paolo (2016), The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace, Transportation Research Part B: Methodological, 90, p. 38-55. 10.1016/j.trb.2016.04.009
TypeArticle accepté pour publication ou publié
Journal nameTransportation Research Part B: Methodological
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Persiani, Carlo Alfredo
D.E.I. - University of Bologna.
Abstract (EN)The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone 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 drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.
Subjects / KeywordsInteger programming; Time dependent TSP; Drones; Air traffic management
Showing items related by title and author.
State Space Reduced Dynamic Programming for the Aircraft Sequencing Problem with Constrained Position Shifting Furini, Fabio; Kidd, Martin Philip; Persiani, Carlo Alfredo; Toth, Paolo (2014) Communication / Conférence
Mathematical models for real-world production planning problems with sequence-dependent set-up costs Shen, Xueying; Focacci, Filippo; Furini, Fabio; Gabrel, Virginie; Godard, Daniel (2015-02) Communication / Conférence