Modelling Robust Flight-Gate Scheduling as a Clique Partitioning Problem

Ulrich Dorndorf (), Florian Jaehn () and Erwin Pesch ()
Additional contact information
Ulrich Dorndorf: INFORM GmbH, 52076 Aachen, Germany
Florian Jaehn: Institute of Information Systems, University of Siegen, Siegen, 57068, Germany
Erwin Pesch: Institute of Information Systems, University of Siegen, Siegen, 57068, Germany

Transportation Science, 2008, vol. 42, issue 3, 292-301

Abstract: This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation in which certain gate assignments may cause the blocking of neighboring gates. The objectives include maximization of the total assignment preference score, minimization of the number of unassigned flights during overload periods, minimization of the number of tows, as well as maximization of the robustness of the resulting schedule with respect to flight delays. We are presenting a simple transformation of the flight-gate scheduling (FGS) problem to a graph problem, i.e., the clique partitioning problem (CPP). The algorithm used to solve the CPP is a heuristic based on the ejection chain algorithm by Dorndorf and Pesch [Dorndorf, U., E. Pesch. 1994. Fast clustering algorithms. ORSA J. Comput. 6 141--153]. This leads to a very effective approach for solving the original problem.

Keywords: airport gate scheduling; clique partitioning; robustness; ejection chain (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1070.0211 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:42:y:2008:i:3:p:292-301

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().