Detailansicht
Variable neighborhood search for the static aircraft sequencing problem
Thomas Hermann
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.17664
URN
urn:nbn:at:at-ubw:1-29331.98065.343766-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das sogenannte "Aircraft Sequencing Problem" (ASP) wird für den Fall einer oder mehrerer zur Verfügung stehender Pisten unter Einbeziehung von startenden als auch landenden Flugzeugen betrachtet. Als Zielfunktion dient die Minimierung der Summe der gewichteten Abweichungen von individuellen Zielzeiten. Das zugrundeliegende Problem wird als Transportproblem betrachtet und eine sogenannte "Variable Neighborhood Search"-Metaheuristik (VNS) als Lösungsmethode vorgestellt. Die Leistungsfähigkeit des implementierten Verfahrens wird anhand von 13 Testdatensätzen der OR-Bibliothek von J.E. Beasley gemessen. Die Ergebnisse von 49 Instanzen, 10 bis 500 Flugzeuge umfassend, werden für den Ein- und Mehrpistenfall präsentiert. Zusätzlich wird eine Vergleichsanalyse mit den derzeit besten Heuristiken dargestellt. VNS liefert exzellente Resultate, die die Ergebnisse beinahe aller bislang bekannten Heuristiken übertreffen. Abschließend wird die Anwendung auf eine reale Problemstellung des Flughafen München erläutert.
Abstract
(Englisch)
This thesis deals with the single and multiple runway cases of the Aircraft Sequencing Problem (ASP) involving departing and arriving airplanes. The objective function adopted corresponds to the minimization of total weighted deviation from individual target times. The underlying problem is considered as routing problem and a Variable Neighborhood Search (VNS) metaheuristic is presented as solution method. The performance of the implemented algorithm is measured using 13 test set provided by the OR-library of J.E. Beasley. Computational results for all 49 test instances involving from 10 to 500 airplanes with a varying number of runways are reported. In addition a comparative analysis with current "state-of-the-art"-heuristics is shown. VNS provides excellent results outperforming almost all heuristics previously presented. Finally, the application to a real world scenario encountered at Munich International Airport is presented.
Schlagwörter
Schlagwörter
(Englisch)
Variable Neighborhood Search Aircraft Sequencing Problem
Schlagwörter
(Deutsch)
variable Nachbarschaftssuche Flugzeugreihenfolgeproblem
Autor*innen
Thomas Hermann
Haupttitel (Englisch)
Variable neighborhood search for the static aircraft sequencing problem
Paralleltitel (Deutsch)
Variables Nachbarschaftssuchverfahren für das statische Flugzeugreihenfolgeproblem
Publikationsjahr
2011
Umfangsangabe
82 S.
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikationen
55 Verkehrswesen > 55.88 Luftverkehr, Raumfahrt ,
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC08952051
Utheses ID
15830
Studienkennzahl
UA | 157 | | |