Modelling robust flight-gate scheduling as a clique partitioning problem
Publication date
2008-03-24
Document type
Forschungsartikel
Author
Organisational unit
Institute of Information Systems, University of Siegen
Scopus ID
Publisher
INFORMS
Series or journal
Transportation Science
ISSN
Periodical volume
42
Periodical issue
3
First page
292
Last page
301
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Keyword
Airport gate scheduling
Clique partitioning
Ejection chain
Robustness
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.
Version
Not applicable (or unknown)
Access right on openHSU
Metadata only access