Beontra Scenario Planning

BEONTRA Scenario Planning
BEONTRA Scenario Planning:
Wie Kann Ein Flughafen Den Optimalen
Einsatz Begrenzter Ressourcen
(z. Bsp. Stands & Gates) Planen?
Dr. Daniel Binkele-Raible
Senior OR Developer
BEONTRA GmbH
Christoph Staab
Product Manager
BEONTRA GmbH
AGENDA
Thema
Einführung in die Problemstellung - Stand & Gate Allokation
Vorstellung BEONTRA
Zentrale Frag estellung der Stand & Gate Planung
Problemstellung
Methodischer Ansatz - Einsatz von Gurobi
Kostenbasierter Ansatz
Reduzierung der Kosten durch bessere Handling plans
Column Generation
BEONTRA Scenario Planning Wie Sieht Die Zukunft Meines Flughafens Aus?
Mögliche Zukünftige Entwicklungen Besser Verstehen.
Verbesserte Planung Durch Den Einsatz Von Szenariobasierten Softwaretools!
25
20
15
Most Likely
Szenario 1
10
Szenario 2
5
0
2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020
Global Airports End-to-End Solutions
Airport Operations
Control Centre
Strategic
Planning
Tactical
Planning
Operations
Planning
Operational
Day Prediction
3 years+
next season+
Next days+
today
Staff Planning
Master Plan
Forecasting
Capacity
Planning
Demand
Forecasting
Realtime
Forecasting
Airline Allocation
Evaluation
Seite 5
Februar 2016
Billing
BI
Air Traffic
Management
Budget
Forecasting
Route
Development
CDM
Passenger
Tracking
Retail
Planning
Tariff
Design
Ressource
Management
Turnaround
Management
Operations
Management
BEONTRA Stand and Gate Allocation
Post
Operation
BEONTRA Scenario Planning
Modul B Capacity
 Analyse der Kapazitäten eines Flughafens
 Wartezeiten an der Sicherheitskontrolle beim Einsatz neuer Scanner Technologien?
 Anzahl ankommender Passagiere je Stunde an der Passkontrolle an einem
Ferienwochenende?
 Wie groß muss mein Check-In Bereich
im Jahr 2020 sein?
 Optimierung vorhandener
Resourcen
 Personalplanung für
Sicherheitskontrollen
etc.
 Check-In Schalter
Allokation
 Stand & Gate
Allokation
Seite 6
Februar 2016
BEONTRA Stand and Gate Allocation
Was Sind Stands?
Parkplatz – Für Autos
Stand – Für Flugzeuge
"North Remote Apron" Area of Changi © Kentaro IEMOTO Quelle: Siehe Anhang
Seite 7
Februar 2016
BEONTRA Stand and Gate Allocation
Was Sind Stands?
Seite 8
Februar 2016
BEONTRA Stand and Gate Allocation
Eine Situation, Die Sie Als Passagier Nicht Erleben Wollen! (und auch nicht werden)
2
Stand 3
3
Pier A
Flug
Flugzeugtyp
# Passagiere
Aufenthalt
1
A320
100
10:00-10:45
2
A380
550
10:15-12:30
3
A320
100
11:00-12:00
Seite 9
Februar 2016
BEONTRA Stand and Gate Allocation
1
Wie Kann Ich Die Parkplätze Für Flugzeuge, Die Mein Flughafen Hat, Möglichst Gut
Belegen?
2
Stand 3
3
Pier A
1
Seite 10
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Kann Ich Die Parkplätze Für Flugzeuge, Die Mein Flughafen Hat, Möglichst Gut
Belegen?
2
Stand 3
3
Pier A
1
Seite 11
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Kann Ich Die Parkplätze Für Flugzeuge, Die Mein Flughafen Hat, Möglichst Gut
Belegen?
 Fokus unserer Stand & Gate Allokation liegt auf der Zuweisung der Stands
 Dabei müssen gewisse physische Restriktionen und strukturelle Abhängigkeiten berücksichtigt werden
Seite 12
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Kann Ich Die Parkplätze Für Flugzeuge, Die Mein Flughafen Hat, Möglichst Gut
Belegen?
Seite 13
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Kann Ich Die Parkplätze Für Flugzeuge, Die Mein Flughafen Hat, Möglichst Gut
Belegen?
Foto Stands FH
 Damit ist abgebildet welche Parkplätze mein Flughafen hat
Seite 14
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Kann Ich die Parkplätze für Flugzeuge, die Mein Flughafen Hat, Möglichst Gut
Belegen?
"North Remote Apron" Area of Changi by Kentaro IEMOTO Quelle: siehe Anhang
 Handling Scheme für Contact Stands
 Gutes Ranking
Niedrige Kosten
Seite 15
Februar 2016
VS.
 Handling Scheme für Remote Stands + Busse
 Schlechteres Ranking
Höhere Kosten
BEONTRA Stand and Gate Allocation
Wie Kann Ich die Parkplätze für Flugzeuge, die Mein Flughafen Hat, Möglichst Gut
Belegen?
Wunsch
Notlösung
Nie
Foto Stands FH
 Außerdem werden die Kosten durch differenzierte Prioritäten für die verschiedenen
Stand Bereiche beeinflusst
 Oder die Nutzung generell untersagt
Seite 16
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Kann Ich Die Parkplätze Für Flugzeuge, Die Mein Flughafen Hat, Möglichst Gut
Belegen?
Seite 17
Februar 2016
BEONTRA Stand and Gate Allocation
Wie Immer, Ist Die Realität Etwas Komplizierter


> 1000 Flüge zuweisen auf
> 250 Stands, die mit Gates an 3 verschiedenen Terminals verbunden sind
Seite 18
Februar 2016
BEONTRA Stand and Gate Allocation
AGENDA
Thema
Einführung in die Problemstellung - Stand & Gate Allokation
Vorstellung BEONTRA
Zentrale Frag estellung der Stand & Gate Planung
Problemstellung
Methodischer Ansatz - Einsatz von Gurobi
Kostenbasierter Ansatz
Reduzierung der Kosten durch bessere Handling plans
Column Generation
Seite 19
Februar 2016
BEONTRA Stand and Gate Allocation
Was Ist Ein Handlingplan Und Was Soll Er Kosten!
 Spezifiziert das Handling eines Flugzeugs bzgl:
 Gate bei Ankunft und Abflug.
 Stand bei Ankunft und Abflug .
 Zwischparken auf einem ‚IdleStand‘.
 ‚Boarding‘ mittels Bus oder Fluggastbrücke [*].
 ‚Deboarding‘ mittels Bus oder Fluggastbrücke [**].
 Handlingscheme legt fest:
 ([*], [**],
 Anzahl Umparkvorgänge.
 Aufenthaltsdauer auf Stands und Gates
 Welche Stand und Gates benutzt werden dürfen.
 Hierarchische Kostenstruktur aus:
1. Kosten Handlingscheme
2. Prioritäten der Airlines für Stands und Gates.
3. Rangfolge der Airlines für Stands und Gates (festgelegt durch Flughafen).
Seite 20
Februar 2016
BEONTRA Stand and Gate Allocation
Lösungsansatz
• Mathematische Formulierung (Master Problem):
• Jeder Handling Plan eine Binärvariable xi  {0,1}
• Objective
min c1 x1  .....  cn xn
• Turnround-Constraints:
• Turnround 1: x1  x4  x12  x200  1
x7  x20  x45  1
• Turnound n:
• Resource-Time-Constraints:
• Stand1/12:00 x1  x5  x10  x5031  1
• Stand1/12:05 x7  x12  x20  x344  1
• Stand8/14:10 x13  x5  x56  1
Seite 21
Februar 2016
BEONTRA Stand and Gate Allocation
Column Generation:
• Problem: zuviele Handling Plans (Columns)!
• Lösung: Column Generation
1. Starte mit Teilmenge an Handling Plans (Heuristik).
2. Löse relaxiertes Problem als LP.
3. Generiere weitere Handling Plans mittels reduzierter Kosten
4. Gehe zu 2, falls kein Abbruch.
5. Löse Master Problem beschränkt auf erzeugte Handling Plans (Restricted Master Problem).
 Wie Schritt 3 lösen?
 Kürzeste Wege auf Graphen!
Seite 22
Februar 2016
BEONTRA Stand and Gate Allocation
Und Wieder Mal Die Realität…..
Seite 23
Februar 2016
BEONTRA Stand and Gate Allocation
Seite 24
Februar 2016
BEONTRA Stand and Gate Allocation
Anhang
Bilderquellen:
"North Remote Apron" Area of Changi by Kentaro IEMOTO
Quelle: https://www.flickr.com/photos/kentaroiemoto/4429472266/in/photolist-7KqcMu-eihM5j-eihMg3-6CDCL6-s9Htiw-5GVwVc-pw67XC-8XDrjG-ALRzf-8XDGmQ-wMRu8-7DM6nF-b4CiK-8XAutT-8XAsA68XDvFm-8XArHv-8XDFq7-8XAsiM-8XAsSM-8XDv6m-8XAuaM-8XAuLM-8XDuMu-8XDx6N-8XAtTF-8XDqWo-k7VDYq-8XAqLg-8XAq3X-8XAmBg-8XDsRE-8XDugm-8XDtvq-8XAoMF-8XDtdE-8XAvHt-8XDzZL8XAwEp-8XDzEy-8XDyR1-7DBzG7-pxceES-8XDBrG-8XDC8C-8XAxp2-8XAx5v-8XDCs5-8XAy8H-8XAADi
https://creativecommons.org/licenses/by-sa/2.0/
Seite 25
Februar 2016
BEONTRA Stand and Gate Allocation

Download Report