Post on 05-Apr-2015
transcript
AG-Monien
Projektgruppe AIR
Optimierung von Planungsprozessen im Flugverkehr
PG-AIR AG-Monien
Prozess der Flugplanung
FleetAssignment
AircraftRotation
CrewScheduling
NetworkDesign
MarketModeling
RevenueManagement
Air TrafficControl
PG-AIR AG-Monien
Thema der Projektgruppe
Fleet Assignment auf Basisdes Connection Network.
Basierend auf dem Connection-Network, da bisherige Modelle keine Connection-abhängigen Bodenzeiten berücksichtigen können.
PG-AIR AG-Monien
Architektur
Objekte / Datenstruktur
en
Einlesen
Daten
Modellaufbau
Preprocessing
Concert
Regler
CPLEX
Löser
Ausgabe
Auswertung
Konfigurator
PG-AIR AG-Monien
Modellaufbau
Basis für die Problemmodellierung: Connection-Network
FRA
Arrival
Departure
340319
340 319, 340
PG-AIR AG-Monien
Zyklische und nicht-zyklischen Planungsperioden
Bei zyklischer Planung:Rückwärtskanten möglich
FRAArrival
Departure
Bei nicht-zyklischer Planung:Quelle und Senke
Quelle
Senke
PG-AIR AG-Monien
Basismodell
F = Menge aller Flotten xji
Ef = Menge aller Connections für die Flotte f FCf = Flugzeuganzahl der Flotte f F
1, falls Legs i und j von der Flotte f nacheinander geflogen werden
0 sonst
(Leg i wird von der Flotte f geflogen xfij = 1, wobei (i,j) Ef)
j
revfij = Profit für die Connection (i,j) Ef
costfij = Kosten für die Connection (i,j) Ef
Wobei Profit/Kosten für die Connections (i,j) Ef = Profit/Kosten für das Leg i,
geflogen von der Flotte f (für alle j mit (i,j) Ef)
xfij
PG-AIR AG-Monien
Basismodell – zyklisch
Für jede Connection xfij definiert man pf
ij N.Diese Variable gibt die Anzahl der Schnitte mit der Periodengrenze an.
PG-AIR AG-Monien
Basismodell – nicht-zyklisch
Zusätzliche Kontrolle der Flottenkapazität in Quelle (oder Senke).
PG-AIR AG-Monien
Erweiterungen
Realisierung verschiedener Modellerweiterungen mit folgenden Schwerpunkten:
Modifizierung der Planungsperiode
Einbeziehung von Gewichtungs- und
Strafkosten
Globale Beschränkungen
Berücksichtigung von initialen Lösungen
PG-AIR AG-Monien
Planungsperiode
Variable Planungsperiodenlänge
Das Modell basiert auf periodischer zeitlicher Planung.
Einstellen der Periodenlänge durch Angabe im Konfigurationsfile
Modell arbeitet auf Minutenbasis Standardperiodenlänge: 1 Woche (10080 Min)
FRA
0 10080
PG-AIR AG-Monien
Variable Gewichtung von (Leg-)Kosten und (Leg-)Erlösen in der Zielfunktion
- Gewichtungsfaktor für Erlöse - Gewichtungsfaktor für Kosten Anpassung der Zielfunktion
PG-AIR AG-Monien
Connection-Kosten und geänderte Mindestbodenzeiten
Möglichkeit zusätzliche Informationen für bestimmte Connections zu berücksichtigen:Für eine Connection zwischen zwei bestimmten LegsFür alle Connections zwischen Legs mit bestimmten
Typ (z.B. interkontinental kontinental)
Berücksichtigung von:eventuell vorhandenen zusätzlichen „Connection-
Kosten“eventuell geänderten Mindestbodenzeiten einzelner
Connections oder Connectionsgruppeneventuellem Verbieten bestimmter Connections
PG-AIR AG-Monien
Explizite Kostenobergrenze
Zusätzliche Restriktion:
(M = explizite Kostenobergrenze)
PG-AIR AG-Monien
Berücksichtigung von Fixkosten für Flugzeuge
Fixf – Fixkosten für ein Flugzeug der Flotte f
Nicht-Zyklisch
Zyklisch:
PG-AIR AG-Monien
Explizite Obergrenze für die Gesamtflugzeuganzahl
TotalCap –maximale Gesamtflugzeuganzahl
Zyklisch
Nicht-zyklisch
PG-AIR AG-Monien
Beschränkung der Blockstunden für ausgewählte Flotten
dfij – Anzahl der Blockstunden (reine Flugzeit)
für die Connection xfij (also, für
das Leg i)Hf – maximale Anzahl der Blockstunden für
die Flotte fF
PG-AIR AG-Monien
Beschränkung der Änderungen bezüglich der Vorgabelösung
Die Gesamtanzahl der geflogenen Legs ist immer konstant.
Sei mod fij – Anzahl der potenziellen Änderungen, falls Leg i
in der neuen Lösung geflogen wird (j mit (i,j)Ef). Also
Für ein zusammengesetztes Superleg i:N -> Anzahl der in Superleg i zusammengefassten
Legs, die in dermodf
ij Vorgabelösung NICHT von der Flotte f geflogen werden
0, falls alle Legs in i in der Vorgabelösung von der Flotte f geflogen werden
Für ein „normales“ Leg i:1, falls Leg i in der Vorgabelösung NICHT von der
modf
ij Flotte f geflogen wird
0 sonst.
PG-AIR AG-Monien
Beschränkung durch StrafkostenChangecost = Strafkosten für eine Änderung
Beschränkung der Änderungen bezüglich der Vorgabelösung
Explizite Beschränkung Change = maximal erlaubte Anzahl der Änderungen
PG-AIR AG-Monien
Zusammenfassung:Modellaufbau
Als Basis für die Problemmodellierung wurde das Connection-Network verwendet.
Dabei wurde folgende Erweiterungen berücksichtigt : Variable Planungsperiodenlänge Unterstützung von zyklischen und nicht-zyklischen Planungsperioden Variable Gewichtung von Kosten und Erlösen in der Zielfunktion Berücksichtigung von eventuell vorhandenen „Connection-Kosten“ und
gegenüber der Eingabe geänderten Mindestbodenzeiten einzelner Connections
Explizite Kostenobergrenze Berücksichtigung von Fixkosten für Flugzeuge Explizite Obergrenze für die Gesamtflugzeuganzahl Beschränkung der Blockstunden für ausgewählte Flotten Beschränkung der Änderungen bezüglich der Vorgabelösung,
sowohl explizit als auch durch Strafkosten
PG-AIR AG-Monien
Vielen Dank für Ihre Aufmerksamkeit!
Nun folgt Teil 2:
Preprocessing &Ergebnisse