• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

State Space Reduced Dynamic Programming for the Aircraft Sequencing Problem with Constrained Position Shifting

Thumbnail
Date
2014
Notes
LNCS, Vol. 8596
Dewey
Modèles mathématiques. Algorithmes
Sujet
Aircraft sequencing problem; Dynamic programming; Integer programming; Completion bounds; Constrained position shifting
JEL code
C61
DOI
http://dx.doi.org/10.1007/978-3-319-09174-7_23
Conference name
ISCO 2014 - 3rd International Symposium on Combinatorial Optimization
Conference date
03-2014
Conference city
Lisbon
Conference country
Portugal
Book title
Combinatorial Optimization
Author
Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T.
Publisher
Springer International Publishing
Publisher city
Cham
Year
07-2014
Pages number
446
ISBN
978-3-319-09173-0; 978-3-319-09174-7
Book URL
10.1007/978-3-319-09174-7
URI
https://basepub.dauphine.fr/handle/123456789/16410
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Furini, Fabio
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kidd, Martin Philip
461036 D.E.I. - University of Bologna.
Persiani, Carlo Alfredo
status unknown
Toth, Paolo
461036 D.E.I. - University of Bologna.
Type
Communication / Conférence
Item number of pages
267-279
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.