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érenceDate
2014Conference title
ISCO 2014 - 3rd International Symposium on Combinatorial OptimizationConference date
2014-03Conference city
LisbonConference country
PortugalBook title
Combinatorial OptimizationBook 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
446Pages
267-279
Publication identifier
Metadata
Show full item recordAuthor(s)
Furini, FabioLaboratoire 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 shiftingRelated items
Showing items related by title and author.
-
Furini, Fabio; Kidd, Martin Philip; Persiani, Carlo Alfredo; Toth, Paolo (2015) Article accepté pour publication ou publié
-
Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
-
Furini, Fabio; Persiani, Carlo Alfredo; Toth, Paolo (2016) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
-
Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié