Kolloquiumsvortrag: Erwin Pesch (Universität Siegen): Gate Scheduling at Airports

17.01.2014 von 14:15 bis 16:00

LMS2 Ü2/K

Abstract:

Flight­gate scheduling is concerned with finding an assignment of flights to terminal or ramp positions and an assignment of the start and completion times of the processing of a flight at its position. The key idea is a modified multi­mode resource­constrained project scheduling problem with a multi­criteria objective function. The most important goals are the maximization of a total flight­gate preference value and the minimization of the number of tows. The basic optimization algorithm is a truncated branch­and­bound procedure that branches over gate assignments and the disjunctive constraints used to model the capacity restrictions of the disjunctive resources (gates). The algorithm uses constraint propagation techniques to reduce the search space. To cope with large practical problems within the order of magnitude of thousand flights per day, the problem is decomposed into loosely coupled subproblems using a new generic problem partitioning technique. The subproblems are used within a layered branch­and­bound approach: In each layer, only decision variables of the current subproblem are selected for branching; limited backtracking is performed within the current layer before proceeding to the next layer. Initial solutions obtained are iteratively improved using a Large Neighbourhood Search. The model and algorithm have been evaluated using two weeks of a real­life flight schedule from a large international airport. A comparison of the computational results with a rule based approach shows that the algorithm greatly improves the solution quality.

Prof. Dr. Klaus Jansen

Diesen Termin meinem iCal-Kalender hinzufügen

zurück