Show simple item record

dc.contributor.authorFurini, Fabio
dc.contributor.authorKidd, Martin Philip
dc.contributor.authorPersiani, Carlo Alfredo
dc.contributor.authorToth, Paolo
dc.date.accessioned2017-03-20T14:18:49Z
dc.date.available2017-03-20T14:18:49Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16410
dc.descriptionLNCS, Vol. 8596en
dc.language.isoenen
dc.subjectAircraft sequencing problemen
dc.subjectDynamic programmingen
dc.subjectInteger programmingen
dc.subjectCompletion boundsen
dc.subjectConstrained position shiftingen
dc.subject.ddc518en
dc.subject.classificationjelC61en
dc.titleState Space Reduced Dynamic Programming for the Aircraft Sequencing Problem with Constrained Position Shiftingen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages267-279en
dc.relation.ispartoftitleCombinatorial Optimizationen
dc.relation.ispartofeditorFouilhoux, Pierre
dc.relation.ispartofeditorGouveia, Luis Eduardo Neves
dc.relation.ispartofeditorMahjoub, A. Ridha
dc.relation.ispartofeditorPaschos, Vangelis T.
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2014-07
dc.relation.ispartofpages446en
dc.relation.ispartofurl10.1007/978-3-319-09174-7en
dc.subject.ddclabelModèles mathématiques. Algorithmesen
dc.relation.ispartofisbn978-3-319-09173-0; 978-3-319-09174-7en
dc.relation.conftitleISCO 2014 - 3rd International Symposium on Combinatorial Optimizationen
dc.relation.confdate2014-03
dc.relation.confcityLisbonen
dc.relation.confcountryPortugalen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-09174-7_23en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-03-20T13:54:13Z
hal.person.labIds989
hal.person.labIds461036
hal.person.labIds36796
hal.person.labIds461036
hal.identifierhal-01492753*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record