• 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

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), State Space Reduced Dynamic Programming for the Aircraft Sequencing Problem with Constrained Position Shifting, in Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T., Combinatorial Optimization, Springer International Publishing : Cham, p. 267-279. 10.1007/978-3-319-09174-7_23

Type
Communication / Conférence
Date
2014
Conference title
ISCO 2014 - 3rd International Symposium on Combinatorial Optimization
Conference date
2014-03
Conference city
Lisbon
Conference country
Portugal
Book title
Combinatorial Optimization
Book author
Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T.
Publisher
Springer International Publishing
Published in
Cham
ISBN
978-3-319-09173-0; 978-3-319-09174-7
Number of pages
446
Pages
267-279
Publication identifier
10.1007/978-3-319-09174-7_23
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]
Kidd, Martin Philip
D.E.I. - University of Bologna.
Persiani, Carlo Alfredo

Toth, Paolo
D.E.I. - University of Bologna.
Abstract (EN)
In this paper we present state space reduction techniques for a dynamic programming algorithm applied to the Aircraft Sequencing Problem (ASP) with Constrained Position Shifting (CPS). We consider the classical version of the ASP, which calls for determining the order in which a given set of aircraft should be assigned to a runway at an airport, subject to minimum separations in time between consecutive aircraft, in order to minimize the sum of the weighted deviations from the scheduled arrival/departure times of the aircraft. The focus of the paper is on a number of ways of improving the computation times of the dynamic programming algorithm proposed. This is achieved by using heuristic upper bounds and a completion lower bound in order to reduce the state space in the dynamic programming algorithm. We compare our algorithm to an approach based on mixed integer linear programming, which was adapted from the literature for the case of CPS. We show using real-world air traffic instances from the Milan Linate Airport that the dynamic programming algorithm significantly outperforms the MILP. Furthermore, we show that the proposed algorithm is capable of solving very large instances in short computation times, and that it is suitable for use in a real-time setting.
Subjects / Keywords
Aircraft sequencing problem; Dynamic programming; Integer programming; Completion bounds; Constrained position shifting
JEL
C61 - Optimization Techniques; Programming Models; Dynamic Analysis

Related items

Showing items related by title and author.

  • 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
    An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
  • Thumbnail
    The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace 
    Furini, Fabio; Persiani, Carlo Alfredo; Toth, Paolo (2016) Article accepté pour publication ou publié
  • Thumbnail
    Mathematical formulations for the Balanced Vertex k-Separator Problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
  • Thumbnail
    Exact approaches for the knapsack problem with setups 
    Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
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