vnd.ms-powerpoint, it, 1628 KB, 5/18/06

Operations Research
in
Air Transportation
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
1
Air Transportation System
Infrastructure
 Airports
 ATM
(Air Traffic Management)
 ATFM
(AT Flow Management)
 ATC (AT Control)
Superstructure
 Commercial
Flights
 Private Flights
 Military Flights
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
2
Eurocontrol ATFM area and
an example of Sectorization
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
3
ATM (AT Management)
Motivation for improvement
 New technologies
 CNS
(Communications Navigation Surveillance)
 Datalink
 Better weather forecasting
 New economic framework
 Deregulation
 Liberalization
 Competition
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
4
Aviation Authorities (ICAO, FAA,
Eurocontrol, National Aviation
Authorities)
are adopting new ATM concepts:
 FANS
(Future Air Navigation System)
 Free Flight
 CDM (Collaborative Decision Making)
and tools, for example:
 COMPAS
 MAESTRO
 CTAS
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
5
SAFETY
Primary objective of ATM system
Same separation rules in the last 15
years (except for vertical separation …)
Lack of quantitative models
Need for a greater flexibility
Implementation of new concepts
requires careful examination
(example: implications of Free Flight)
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
6
ATFM (AT Flow Management)
 Providers
 FAA
 Eurocontrol
CFMU (Central Flow Management
Unit)
 ATM is continuously evolving
 Excellent
information, elaboration and
visualization capabilities
 Lack of satisfactory decision support systems
 Need for real time tools able to handle
uncertainties (e.g., weather) and dynamically
changing reality.
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
7
Example of GUI
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
8
Over 95% of the total
EUROCONTROL
Route charges
revenues
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
9
Forecasted no. of IFR flights in CFMU area
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
10
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
11
ATFM
 Demand
 System Capacity
 Scheduled
flights
 Charter flights
 General Aviation
 Military flights
 State flights
…
Giovanni Andreatta
Padova University
 Airports
(number of
take-off/landings)
 Airways
 Sectors (no. of flights
entering the sector or
no. of flights in the
sector)
Verona 18 maggio 2006
12
ATFM
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
13
ATFM
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
14
First solution: Ground Holding
Ground holding safer than airborne
holding
Ground holding cheaper than
airborne holding
N.B.: Flight shift in time
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
15
Second solution: Rerouting
It is sometimes directly imposed by
the Aviation Authority (CFMU)
Could be in-directly imposed:
air traffic demand management
N.B.: flight shift in space
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
16
Ground Holding
Ground holding better than airborne
delay
History: 1981 USA AT controllers
strike
Dimensions (No. of daily flights):
 60,000
domestic flights in USA
 30,000 flights in Eurocontrol zone
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
17
Ground Holding Problem
MIT
Padova University
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
18
GH model
(meaning)
MIN Total Cost of (ground + airborne
delays)
subject to:
Capacity constraints
Assignment constraints
Coupling constraints
Integrality constraints
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
19
GH model
(type and dimensions)
The resulting model is a MIP (Mixed
Integer Programming) problem with a
few hundred thousands boolean
variables and constraints
The problem is NP-hard (i.e., difficult)
Yet, the instances using real data
were easy to solve
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
20
Rerouting
A rerouting is
sometimes imposed by
CFMU.
€€€
€€
Rerouting implies
different route charges!
€
€
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
21
EUROCONTROL
route charge formula
Total cost:
R   ri
n
where for each State i the
charge is given by:
MTOW
ri  d i 
 ti
50
Distance traveled in State i
Unit rate in State i
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
22
Critics to EUROCONTROL formula:
Fee  R * D * MTOW / 50
Should better reflect actual ATC costs:

Use time rather than distance?

Question the importance of weight
(augment the exponent from 0.5 to 0.87 ?)
 Efficiency in providing ATC services
should be taken into account

…
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
23
Air Navigation and
Airport User Charges
 Great interest internationally
 Background of rising infrastructure costs and
security costs at a time of global industry crisis
 Multiple objectives for charging systems:
 Cover
costs of service providers
 Cost-related charging formulae
 Provide incentives to improve efficiency/performance
of service providers
 Inform prioritization of investments
 Promote operational efficiency (e.g., reduce
congestion)
 Transparency and user participation
 etc.
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
24
IRCS project
(Trieste + Padova)
Innovative Route Charging Schemes
For more information see:
www.eurocontrol.int/care/innovative/projects2002/ircs/
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
25
IRCS Specific Issues (partial list)
Alternative charging formulae
 Common
unit rate
 Two-part charge, etc.
Impacts of alternative charging systems
Charge according to flight plan
Tax on tickets
Containment of service provider costs
Other?
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
26
General aim of IRCS project
the final purpose of the Innovative
Route Charging Schemes project is:
 to study the impact of changes in enroute charges
 with respect to the demand and
supply sides of ATM
 in a view to improve the overall
efficiency of the system
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
27
Market based
Flow Demand Management
and Rerouting
Odoni, Fan, … (MIT)
Andreatta, Lulli (Padova)
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
28
Optimal congestion fee
A congestion fee on a user is optimal when it
is equal to the external costs that the user
imposes on the other users.
For a M/G/1 queue:
dWq
dC
MC 
 c Wq  c
d
d
Marginal
=
cost
Internal +
cost
Giovanni Andreatta
Padova University
External
cost
Verona 18 maggio 2006
29
Idea under investigation
 Without congestion fee, BIG aircraft are
penalized
 With “optimal” congestion fee, SMALL
aircraft are penalized
Why not consider different
categories and compute the
“external” cost imposed within
each category?
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
30
Airports
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
31
Airport modeling
Landside (Passenger terminal)
Baggage handling
Apron stand allocation
Arrival aircraft sequencing
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
32
Airport landside modeling
European sponsored projects:
 IV UE framework program: “TAPE”
 V UE framework program: “OPAL”
 VI UE framework program: “SPADE”
Padova University
Rome “La Sapienza” University
Athens AUEB
Toulouse ONERA
Delft University
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
33
SLAM Implementation
• Program: ANSI C, LEX and YACC
• Graphic User Interface: JAVA
• Run under UNIX and WINDOWS
Output file
Output file
Output file
Input file
run
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
34
Apron stand allocation
Romanin-Jacur, Filippi
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
35
Arrival aircraft sequencing
Bianco, Rinaldi, Dell’Olmo, Lulli, …
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
36
AIRLINES
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
37
Airlines
Deregulation and Liberalization drive a
higher competition
Need to reduce costs
Need to enhance revenues
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
38
Airlines costs
The Passenger Mix Model
The Fleet Assignment Problem
The Crew Pairing Problem, the
Aircraft Routing Problem, and the
Integrated Crew Pairing-Aircraft
Routing Problem
The Schedule Design Problem
Integrated Models
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
39
Airlines revenues
Revenue management
Seat pricing
Seat categorization
Integration
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
40
Optimization Methods
Integer Linear Programming
Greedy algorithms
Genetic algorithms
Tabu search
Bi-linear programming models
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
41
Where in the USA ?
NEXTOR
 MIT
 Virginia
TECH
 U. of Maryland
 UC Berkeley
 GMU
 FAA
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
42
Where in Italy
Padova
 Andreatta,
…
Brunetta, Lulli, Romanin-Jacur,
Rome
 Dell’Olmo,
Bianco, …
Trieste
 Ukovich,
Castelli, Pesenti, …
Siena
 Marti
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
43
Thank You
Padova References:
www.dei.unipd.it/~brunetta/at_papers/
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
44
Giovanni Andreatta
Padova University
Verona 18 maggio 2006
45