Optimization Online


The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

Fabio Furini(fabio.furini***at***dauphine.fr)
Carlo Alfredo Persiani(carlo.persiani***at***enav.it)
Paolo Toth(paolo.toth***at***unibo.it)

Abstract: 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.

Keywords: Integer Programming, Traveling Salesman Problem, Time Dependence, Unmanned Aerial Systems, Air Traffic Management

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 06/21/2015
Entry Accepted: 06/21/2015
Entry Last Modified: 06/21/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society