Modellierung und Berechnung von Flugplänen für Charterfluggesellschaften PG Air Seminararbeit März 2002 Jürgen Wieners

Modellierung Modellierung und Berechnung und Berechnung von Flugplänen von Flugplänen für Charterfluggesellschaftenfür Charterfluggesellschaften

PG AirSeminararbeit

März 2002Jürgen Wieners

PG-Air - März 2002Jürgen Wieners

2 / 30Flugpläne für Charterfluggesellschaften

Inhalte dieses SeminarsInhalte dieses Seminars

Problembeschreibung

Modellierung

Teilprobleme der Column Generation

Techniken für die Berechnung

Vorstellung der Ergebnisse

Problembeschreibung



Vom Problem zum SystemVom Problem zum System

Ziel:Ziel:Generierung eines Flugplans für Charterfluggesellschaften

Voraussetzungen:Voraussetzungen:Analyse des MarktbedarfsKosten pro Flug und PassagierFlugplanzyklus: eine Woche

Problembeschreibung



Die GegebenheitenDie Gegebenheiten

Charterfluggesellschaft mit Flotte K

K = Kfull Kpart

Flughäfen A = H A

Rotation: Folge von Flügen die ein

Flugzeug am Tag fliegt.

Direct Flights / Via Flights

Problembeschreibung



KostenbestandteileKostenbestandteile

Einnahmen je Passagier u. OD-PaarKosten für die FlugzeugeinsetzungMiete und Rücktransport für Flugzeuge aus Kpart

Servicekosten pro PassagierEvtl. Strafkosten für die nicht mitgenommen Passagiere (Spill)



AnnahmenAnnahmen

Stützpunkt bezogene Flugzeuge

Symmetrischer Bedarf

Symmetrische Kapazitäten

Indirekte Flüge

Passagierbezogene Flugrouten

Modellierung



RotationenRotationen

Bedingungen für RotationenÖffnungszeiten der FlughäfenReisezeiten der PassagiereBeschränkungenMinimum Ground Time

Modellierung

Beispielhafter Auszug aus zwei Rotationen



RotationssequenzRotationssequenz

Allgemeines Muster das ein Gerüst für jede Rotation liefert

H0 H1 A2 A3 H4 A5 H6 A7H8 H9

mit Hj H und Aj A.

Beispiel Rotation p11:

H01H02A02 A3 H4 A5 H6 H02H01

Modellierung



Passenger ItinerariesPassenger Itineraries

Die Reiserouten der Passagiere auf den Rotationen

Modellierung



ZielfunktionZielfunktion

Die Zielfunktion (1) minimiert die Gesamtkosten. Diese bestehen aus:Kosten für den Einsatz der FlugzeugeKosten pro genutztem Passenger Itinerary.



Bedingungen (2)-(3)Bedingungen (2)-(3)

(2) beschränkt die Anzahl der Passagiere auf die Kapazitäten der Flugzeuge.Die Bedingung (3) sichert ab, das nur vorhandene Flugzeuge eingesetzt werden.




Modellierung

(4) und (5) modellieren dieFlusserhaltung der Rotationen.




Modellierung

(6) beschränkt die Verfügbarkeit der Flugzeuge, insbesondere der gemieteten(7) setzt Passagierzahlen und Spill in Bezug zum gegebene Bedarf




Modellierung

(8) definiert die Lösungsvariablen binär(9) und (10) legen fest das die Anzahl der Passagiere und der nichtbeförderten Personen nicht negativ werden kann.



Column Generation (CG)Column Generation (CG)


Verschieden Ansätze zur Erstellung der Rotationen:Branch and Cut and PriceZ. B. zur Berechnung der Rotationen bei vielen Flughäfen oder wenn einige der Bedingungen entfallen bzw gelockert werdenBranch and CutZur Generierung der Rotationen für kleine bis mittlere Probleminstanzen.



Netzwerk der RotationenNetzwerk der Rotationen

Ein Netzwerk für jedes Flugzeug und jede BasisKnoten sind Flughäfen, werden zu Schichten zusammengefasstEinsetzungs- und FlugkantenTechnische Beschränkungen sind direkt modelliert




Netzwerk der RotationenNetzwerk der Rotationen




Ganzzahlige LösungenGanzzahlige Lösungen

Lösung des Problems erzeugt über-wiegend gebrochene Lösungen. Um dieses zu Umgehen werden u.a. folgende Techniken eingesetzt:KoeffizientenreduzierungDepth-First-Heuristik




Ursache der NichtganzzahligkeitUrsache der Nichtganzzahligkeit

Bedingung (2) erzeugt Nichtganzzahligkeit der Lösung:

Betrachte OD-Paare




Ursache der NichtganzzahligkeitUrsache der Nichtganzzahligkeit

Pfade und Betriebskosten

Ergebnisse:Optimal : -64.013 DMGanzzahlig:-46.910 DM


Gap: 26,7%



Koeffizienten ReduzierungKoeffizienten Reduzierung

Kapazitäten in (2) werden um die nicht besetzten Plätze reduziert.

Ergebnisse:Optimal : -64.013 DMKoeffizientenred.:-54.6891 DM


Gap: 14,2%



Depth First HeuristikDepth First Heuristik

Tiefensuche durch Selektion einer RotationArbeitet mit Rundung der Lösungen

Lösungswerte > Schwelle = 1Lösungen mit Hohen Kosten = 0

Column Generation wird nicht benötigt




LösungenLösungen

Daten im Beispiel :




1. Lösung1. Lösung

Parameter:Parameter:Ohne Via-Flights, Positionen der Flugzeuge vorgegeben

Ergebnisse:Ergebnisse:Anzahl der Verwendete Flugzeuge sinktSpilled Passenger nehmen zuLösungswert verbessert sich um ca 21%

(Verglichen mit vorgegebener Lösung)









Parameter:Parameter:Ohne Via-Flights, Freie Positionierung der Flugzeuge

Ergebnisse:Ergebnisse:Anzahl der Flugzeuge konstantSpilled Passenger nahmen fast immer ab(Verglichen mit der 1. Lösung)

Gap bei ca 0.84%







Parameter:Parameter:Mit Via-Flights, Positionen der Flugzeuge vorgegeben

Ergebnisse:Ergebnisse:Deutlich gesenkte Flugzeuganzahlgrößere Anzahl der Spilled Passengers(Verglichen mit 1. Lösung)

Gap bei ca 0.54%




Documents

Modellierung und Berechnung von Flugplänen für Charterfluggesellschaften PG Air Seminararbeit März 2002 Jürgen Wieners