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
TypeCommunication / Conférence
Conference titleISCO 2014 - 3rd International Symposium on Combinatorial Optimization
Book titleCombinatorial Optimization
Book authorFouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T.
Number of pages446
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kidd, Martin Philip
Persiani, Carlo Alfredo
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 / KeywordsAircraft sequencing problem; Dynamic programming; Integer programming; Completion bounds; Constrained position shifting
Showing items related by title and author.
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence