Upload
elisabeth-during
View
113
Download
3
Embed Size (px)
Citation preview
PG-AIR
Rotation Planning for the Continental Service of a European Airline
Seminararbeit
Vitali Gintner
Vitali Gintner 2PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Agenda
Prozess der Flugplanung Amerikanisch Europäisch Rotation Regeln Der Graph ILP Exkurs: Lagrange-Relaxation Lagrange-Relaxation Lösung des Unterproblems Ergebnisse
Vitali Gintner 3PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Prozess der Flugplanung
Rotation Planning – Bestimmung von Routen
(Route – eine Legfolge, die mit einem Flugzeug geflogen werden kann)
Network DesignRevenue
Management
Market Modelling
Fleet Assignment Aircraft
Rotation CrewScheduling Air Traffic
Control
Vitali Gintner 4PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Amerikanisch Europäisch
Das amerikanische ModellHub-and-Spoke – Struktur
(Passagiere müssen häufig während ihrer Reise umsteigen)
Ziel – „through value“–Maximierung(der erwartete Ertrag + „die Attraktivität“ der
Verbindung)
Plus spezielle Wartungsrestriktionen(Besuch einer Wartungsstation nach bestimmter Zeit)
Vitali Gintner 5PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Das europäische ModellKeine Hub-and-Spoke – Struktur
Eine kleine Flughafenanzahl in eigenem Land und viele in anderen Teilen Europas
Fahrtunterbrechungen selten „through value“ uninteressant.
Wartungsarbeiten als virtuelle Flüge schon im Flugplan modelliert
Ziel – Reduzierung des Verspätungsrisikos
Amerikanisch Europäisch
Vitali Gintner 6PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Das europäische Modell Eine relativ geringe Anzahl der
Nachflüge
Verspätungen können sich nicht über die Nacht anhäufen
Zerlegung in Teilprobleme (Optimierung für jeden Tag)
Amerikanisch Europäisch
Vitali Gintner 7PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Rotation Regeln
Man definiert bestimmte Regeln für Rotationen
Regelverletzung = Strafkosten
Man sucht Rotationen mit der minimalen Summe von Strafen aus (geringe Verspätungsgefahr)
Vitali Gintner 8PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Rotation Regeln
Lokale Regeln (2-Leg-Regel) eine bestimmte minimale Bodenzeit zwischen 2
Legs (Treibstoff, Inspektionen), Meidung der luftverkehrskritischen Flughäfen, 4 weitere Regeln.
Nicht-lokale Regeln (n-Leg-Regel) nur bis zur x Besuchen der luftverkehrs-
kritischen Flughäfen für ein Flugzeug pro Tag, nur eine bestimmte Anzahl von aufeinander-
folgenden Legs mit nur minimaler Bodenzeit, eine propagierte minimale Bodenzeit für eine
Route (Bodenzeit-Puffer).
Vitali Gintner 9PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Der Graph
Für jeden Flughafen i{1,...,n}Ai – Menge der Ankunftsknoten
Di – Menge der Abflugknoten
Ei – Menge der Kanten
Falls es möglich ist ein Leg (mit dem Ankunftsknoten aAi) mit einem anderen Leg (mit dem Abflugknoten dDi) zu verbinden, fügt man eine Kante eadEi ein.
Vitali Gintner 10PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Der Graph
• Man ordnet jedem startenden Leg ein ankommendes Leg zu. Ergebnis ist ein D-perfektes Matching
• Integration von lokalen Regeln – man gewichtet jede Kante (a,d)E mit bestimmten Strafkosten c(a,d)R+, falls eine lokale Regel verletzt wurde.
Rotationsproblem ein minimales gewichtetes D-perfektes Matchingsproblem
Vitali Gintner 11PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
ILP
Sei P eine Menge von Teilpfaden.
Jeder PP bestehet aus einer Folge von Kanten P=e1e2...ek.
Sei |P|:=k die Länge des Pfades P
Für jeden Pfad PP definiert man Strafkosten PR+ (bei einer Verletzung von nicht-lokalen Regeln)
Für jede Kante (a,d)E definiert man eine binäre Variable 1, falls Kante (a,d) zu der Lösung gehört
X(a,d)= 0, sonst.
1, falls jede Kante e aus dem Pfad P in der Lösung yP= vorkommt
0, sonst.
Für jeden Pfad PP definiert man eine binäre Variable
Vitali Gintner 12PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
ILP
Vitali Gintner 13PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
ILP
...
Bei yP=1 für alle PP , ist diese Restriktion immer gültig und beeinflusst den x-Teil der Lösung nicht. Es gibt immer eine gültige Lösung des ILP‘s.
Da P0 für alle PP und Z minimiert werden soll, ist yP nur dann ungleich 0,wenn
(d.h. wenn der x-Teil der Lösung eine Route definiert, die den Pfad P enthält)
Vitali Gintner 14PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Problem Flugpläne enthalten Tausende
solcher Teilpfade.
Sie belasten das ganzzahlige lineare Programm mit einer sehr großen Zahl der Restriktionen und Variablen
ILP
Vitali Gintner 15PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Exkurs: Lagrange-Relaxation
Gegeben ist ein gemischt-ganzzahliges Programm
A ist eine mxn und D eine kxn-Matrix• Angenommen, das Problem lässt sich ohne die Menge der
Ungleichungen Ax b relativ einfach lösen.
• Sei uRm ein Vektor der nicht-negativen Multiplikatoren
Entferne Ax b und erweitere die Zielfunktion um den nicht-negativen Term u(b-Ax)
Vitali Gintner 16PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Die optimale Lösung für einen festen u ist eine obere Schranke für Z (da u(b-Ax)0). Also,
Wie bestimmt man nun u, so dass die obere Schranke möglichst „eng“ zu der optimalen Lösung wäre?
Idealerweise soll u das folgende duale Problem lösen:
Exkurs: Lagrange-Relaxation
ZD(u) Z für alle u 0
Vitali Gintner 17PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
ZD(u) ist konvex und differenzierbar, bis auf die Punkte, an denen das Lagrage-Problem mehrere optimale Lösungen liefert.
Subgradientenverfahren Nutzt die Steigung der Funktion ZD(u)
An differenzierbaren Punkten ist die Steigung durch b-Ax gegeben
An nicht differenzierbaren Punkten sucht man eine beliebige alternative optimale Lagrage-Lösung aus.
Exkurs: Lagrange-Relaxation
Vitali Gintner 18PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Subgradientenverfahren- Definiert eine Folge, die rekursiv definiert ist:
Wobeitk – Schrittgrößexk – eine optimale Lösung des Lagrange-Problems Z(uk).
Für die Schrittgröße tk ist folgende Formel effektiv
Z* - Zielfunktionswert der best erreichten zulässigen optimalen Lösung des Hauptproblems
Exkurs: Lagrange-Relaxation
Vitali Gintner 19PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Lagrange-Relaxation
Zurück zu unserem Problem
Vitali Gintner 20PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Subgradienten-Optimierung
Die Schrittgröße ist definiert:
Lagrange-Multiplikatoren:
mit
Wobei (x(k),y(k)) – optimale Lösung der Lagrange-Relaxation ZD(uk)
Vitali Gintner 21PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Starte mit P=0 und =1,9 Keine Verbesserung nach 5 Iterationen
halbiere Wurde Z* aktualisiert setzte =1,9 Setze nur positive Multiplikatoren ein und
entferne sie, sobald ihren Wert gleich 0 ist.
Subgradienten-Optimierung
In jeder Iteration wird das Lagrange-Problem gelöst und eine zulässige Lösung des Rotationsproblems geliefert.
(immer gegeben, da der x-Teil immer ein gültiges D-perfektes Matching liefert)
Vitali Gintner 22PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Lösung des Unterproblems
Bis zu 98% der Laufzeit wird zur Lösung des Unterproblems verbraucht (ein bipartites Matchingproblem)
Problemreduktion viele Kanten können nicht einen Teil der Lösung
sein Preprocessing
Effektive Lösungsansätze für das Matchingproblem
Oft nur kleine Änderungen der Kantengewichte „nächste“ optimale Lösung ändert sich nur
leicht
Das bipartites Matchingproblem als unkapazitiertes Transportproblem formulieren und mit einer speziellen Variante des Netzwerk-Simplex lösen.
Vitali Gintner 23PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Ergebnisse
Getestet für 7 verschiedene Flotten (4 große und 3 kleine)
Laufzeit für jede Flotte <5 sec. (SUN Ultra 4 Workstation mit 300 Mhz)
Durchschnittlich 30%-60% weniger Regelnverletzungen
Vitali Gintner 24PG-AIR
Agenda
Prozess der Flugplanung
Amerikanisch Europäisch
Rotation Regeln
Der Graph
ILP
Exkurs
Lagrange-Relaxation
Lösung des Unterproblems
Ergebnisse
Vielen Dank!
Fragen?