• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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

Type
Article accepté pour publication ou publié
Date
2016
Journal name
Transportation Research Part B: Methodological
Volume
90
Pages
38-55
Publication identifier
10.1016/j.trb.2016.04.009
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Persiani, Carlo Alfredo

Toth, Paolo
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 / Keywords
Integer programming; Time dependent TSP; Drones; Air traffic management
JEL
C61 - Optimization Techniques; Programming Models; Dynamic Analysis

Related items

Showing items related by title and author.

  • Thumbnail
    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
  • Thumbnail
    Improved rolling horizon approaches to the aircraft sequencing problem 
    Furini, Fabio; Kidd, Martin Philip; Persiani, Carlo Alfredo; Toth, Paolo (2015) Article accepté pour publication ou publié
  • Thumbnail
    Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows 
    Cazenave, Tristan; Teytaud, Fabien; Rimmel, Arpad (2011) Communication / Conférence
  • Thumbnail
    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
  • Thumbnail
    Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows 
    Cazenave, Tristan; Teytaud, Fabien (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo