Rolling Horizon Approach For Aircraft Scheduling
In The Terminal Control Area Of Busy Airports
Andrea D’Ariano, ROMA TRE University
ISTTT, 21/12/2015
Dipartimento di Ingegneria
1
Dipartimento
di Ingegneria
Junior
Consulting
Presentation outline
 Introduction
 Modeling
a Terminal Control Area
 Solution Framework and Algorithms
 Computational Experiments
 Conclusions and Ongoing Research
This work was partially supported by the Italian Ministry of Research, project
FIRB “Advanced tracking system in intermodal freight transportation”.
2
Dipartimento
di Ingegneria
Junior
Consulting
Air Traffic Control (ATC)
Air traffic control must ensure safe, ordered and rapid transit
of aircraft on the ground and in the air segments.
With the increase in air traffic [*],
aviation authorities are seeking
methods (i) to better use the
existing airport infrastructure,
and (ii) to better manage aircraft
movements in the vicinity of
airports during operations.
[*] Source: EUROCONTROL
Short-term forecast 2009
3
Dipartimento
di Ingegneria
Junior
Consulting
Status of the current ATC practise
• Airports are becoming a major bottleneck in ATC operations.
• The optimization of take-off/landing operations is a key factor
to improve the performance of the entire ATC system.
• ATC operations are still mainly
performed by human controllers
whose computer support is most
often limited to a graphical
representation of the current
aircraft position and speed.
• Intelligent decision support is
under investigation in order to
reduce the controller workload
(see e.g. recent ATM Seminars).
4
Dipartimento
di Ingegneria
Junior
Consulting
Literature: Aircraft Scheduling Problem (ASP)
Existing
Approaches
Basic
(e.g. Bertsimas, Lulli, Odoni )
Static
(e.g. Dear, Hu, Chen)
Detailed
Dynamic
(e.g. Bianco, Dell’Olmo, Giordani)
(e.g. Beasley, Ernst)
5
Dipartimento
di Ingegneria
Junior
Consulting
Literature: Research needs & directions
Aircraft Scheduling Problem (ASP) in Terminal Control Areas:
Most aircraft scheduling models in literature represent the
TCA as a single resource, typically the runway. These models
are not realistic since the other TCA resources are ignored.
We present the “alternative graph” approach for the accurate
modelling of air traffic flows at multiple runways and airways.
This approach has already been applied successully to
control railway traffic for metro lines and railway networks.
6
Dipartimento
di Ingegneria
Junior
Consulting
Our approach for TCAs
Design, implementation and testing of:
• a dynamic (rolling horizon) setting
• a detailed (alternative graph) modeling
• heuristic and exact (branch & bound) ASP algorithms
Research questions:
1. how does the traffic control system react when
disturbances arise,
2. when and how is it more convenient to reschedule
aircraft in the TCA,
3. which algorithm performs best in terms of delay and
travel time minimization,
4. which algorithm is the less sensitive to disturbances.
7
Dipartimento
di Ingegneria
Junior
Consulting
Presentation outline
 Introduction
 Modeling
a Terminal Control Area
 Solution Framework and Algorithms
 Computational Experiments
 Conclusions and Ongoing Research
This work was partially supported by the Italian Ministry of Research, project
FIRB “Advanced tracking system in intermodal freight transportation”.
8
Dipartimento
di Ingegneria
Junior
Consulting
MXP TCA :
(MILAN,
ITALY)
FCO TCA :
(ROME,
ITALY)
9
Dipartimento
di Ingegneria
Junior
Consulting
The Alternative Graph (AG) Model
Mascis & Pacciarelli 2002
• The quality of a schedule is measured in terms of maximum delay
minimization (limiting the delay caused by potential conflicts).
• Fixed constraints in F model feasible timing for each aircraft on its
specific route, plus constraints on each resource of its route.
• Alternative constraints in A represent the aircraft ordering decision
at air segments and runways, plus decisions on holding circles.
• A feasible schedule is an event graph with no positive length cycles.
10
Dipartimento
di Ingegneria
Junior
Consulting
AG Model
Air
Segments
Holding Circles
A
1 4
TOR
2
5
6
7
MBR
3 8
SRN
Common
Runways
Glide Path
10
13
9
15
11
12
14
16
RWY 35L
17
RWY 35R
A1
αA
0
*
Release date αA
(αA = expected entry time of aircraft A)
11
Dipartimento
di Ingegneria
Junior
Consulting
Holding Circles
A
1 4
AG Model
TOR
2
5
6
7
MBR
3 8
SRN
Air
Segments
10
Common
Runways
Glide Path
13
9
15
11
14
12
16
RWY 35L
17
RWY 35R
A1
αA
βA
0
*
Entry due date βA
( βA = - αA )
12
Dipartimento
di Ingegneria
Junior
Consulting
Holding Circles
A
1 4
AG Model
TOR
2
5
6
7
MBR
3 8
δ
SRN
Air
Segments
10
Common
Runways
Glide Path
13
9
15
11
14
12
16
RWY 35L
17
RWY 35R
0
A1
αA
-δ
0
A4
βA
0
*
(A4, A1)
No holding circle (holding time = 0)
(A1, A4)
Yes holding circle (holding time = δ)
13
Dipartimento
di Ingegneria
Junior
Consulting
Holding Circles
A
1 4
AG Model
TOR
2
5
6
A1
αA
A4
- max
13
9
15
11
7
MBR
3 8
min
Common
Glide Path Runways
Air
Segments
10
14
12
16
RWY 35L
17
RWY 35R
SRN
A10
βA
0
*
Time window
for the travel time in each air segment
[min travel time; max travel time]
14
Dipartimento
di Ingegneria
Junior
Consulting
Holding Circles
A
1 4
AG Model
TOR
2
5
6
Common
Glide Path
Air
Segments
10
13
9
15
11
7
MBR
3 8
14
17
12
RWY 35R
SRN
A1
A4
A10
Runways
A
16
RWY 35L
A13
A15
A16
AOUT
γA
αA
βA
0
*
Exit due date γA
(γA = - planned landing time)
15
Dipartimento
di Ingegneria
Junior
Consulting
Holding Circles
A
1 4
AG Model
TOR
Potential conflict
on resource 15 !
2
B
5
6
Air
Segments
10
13
9
11
7
MBR
3 8
Common
Glide Path Runways
A
16
RWY 35L
15
14
17
B
RWY 35R
12
SRN
A1
A4
A10
A13
A15
A16
AOUT
γA
αA
βA
0
*
βB
γB
αB
B3
B8
B12
B14
B15
B17
BOUT
Aircraft ordering problem between A and B on the common glide path
(resource 15) : Longitudinal and diagonal distances have to be respected
16
Dipartimento
di Ingegneria
Junior
Consulting
AG Model
Aircraft ordering problem
between B and C for the
runway (resource 17):
This is a no-store resource!
Holding Circles
A
1 4
TOR
2
B
5
6
Common
Glide Path
Air
Segments
10
13
9
15
11
7
MBR
3 8
C
14
12
C
SRN
A1
A4
A10
A13
Runways
A
16
RWY 35L
A15
A16
17
B
RWY 35R
AOUT
γA
αA
βA
0
*
βB
γB
αB
B3
B8
B12
B14
B15
B17
BOUT
αC
C17
COUT
γC
17
Dipartimento
di Ingegneria
Junior
Consulting
Presentation outline
 Introduction
 Modeling
a Terminal Control Area
 Solution Framework and Algorithms
 Computational Experiments
 Conclusions and Ongoing Research
This work was partially supported by the Italian Ministry of Research, project
FIRB “Advanced tracking system in intermodal freight transportation”.
18
Dipartimento
di Ingegneria
Junior
Consulting
Developing a decision support tool
From a logical point of view, ATC decisions can be divided into:
• Routing decisions, where a route for each aircraft has to be
chosen in order to balance the use of TCA resources.
• Scheduling decisions, where routes are considered fixed,
and feasible aircraft scheduling solutions have to be determined.
In practice, the two decisions are taken simultaneously.
19
19
Dipartimento
di Ingegneria
Junior
Consulting
MILP (Mixed-Integer Linear Programming) model
FIXED AIRCRAFT ROUTES
min f (t , x)
(i, j )  F
t j  ti  wij

t  t  w  M (1  x )
ij , hk
ij
j i
((i, j ), (h, k )  A
t  t  w  Mx
ij , hk
hk
k h
xij ,hk
1 if

0 if
(i, j ) is selected
(h, k ) is selected
20
Dipartimento
di Ingegneria
Junior
Consulting
MILP (Mixed-Integer Linear Programming) model
FLEXIBLE AIRCRAFT ROUTES
min f (t , x, y )
 ns
s  1,..., na
 yrs  1
 r 1
t j  ti  wij  M (1  yrs )
(i, j )  Frs , r , s

t j  ti  wij  M (1  xij ,hk )  M (1  yrs )  M (1  yuv )

((i, j ), (h, k )  A
t k  t h  whk  Mxij ,hk  M (1  yrs )  M (1  yuv )
xij ,hk
1 if

0 if
(i, j ) is selected
(h, k ) is selected
ns: number of routes of aircraft s
1 if route r of aircraft s is selected
yrs  
otherwise
0
na: number of aircraft
21
Dipartimento
di Ingegneria
Junior
Consulting
Rolling Horizon (RH) approach
Time horizon T1
Roll period
Time horizon T2
Roll period
Time horizon T3
time
Length of the overall traffic prediction horizon
22
Dipartimento
di Ingegneria
Junior
Consulting
RH:
Stage 1
Air
Segments
10
Holding Circles
A
1 4
TOR
2
Time horizon T1 [0;15]
B
5
6
Common Runways
Glide Path
A
13
9
15
11
7
MBR
3 8
14
12
17
B
RWY 35R
SRN
A1
A4
A10
A13
A15
16
RWY 35L
A16
AOUT
αA = 10
βA = -10
0
*
βA = 0
αB = 0
B3
B8
B12
B14
B15
B17
BOUT
23
Dipartimento
di Ingegneria
Junior
Consulting
RH:
Stage 2
Air
Segments
10
Holding Circles
A
1 4
TOR
2
Roll Period = 5
Time horizon T2 [5;20]
5
13
9
6
7
MBR
3 8
A4
15
11
14
12
C
B
SRN
A1
Common Runways
Glide Path
A
A10
A13
A15
16
RWY 35L
C
17
B
RWY 35R
A16
AOUT
αA = 10
0
αB = 5
βA = -10
*
B14
B15
B17
BOUT
C17
COUT
αC = 17
βB = -5
Observation: At this stage the release time of A and C can
be updated dynamically if updated entry times are known
βC = -17
24
Dipartimento
di Ingegneria
Junior
Consulting
Decision Support System based
on the Rolling Horizon Approach
Aircraft entry times (dynamic information)
Airport Resources
Aircraft Times
Aircraft Routes
Instance
Generator
Time Horizon
Roll period
XML file
Aircraft not
fully processed
Single Stage
Solver
Feasible Solution
(if any)
Set new roll period
25
Dipartimento
di Ingegneria
Junior
Consulting
Single Stage Solver: AGLIBRARY
Heuristics (e.g. FCFS, AGH, JGH)
Branch and Bound (BB)
Airport Resources
Aircraft Times
Aircraft Routes
Time Horizon
Roll period
Aircraft
Scheduling
Module
New
Schedule
Yes
Stopping Criteria
Reached?
D’Ariano 2008
Return
Best Solution
Found
No
New
Routes
Aircraft
Rerouting
Module
Tabu Search (TS)
26
Dipartimento
di Ingegneria
Junior
Consulting
Presentation outline
 Introduction
 Modeling
a Terminal Maneuvering Area
 Solution Framework and Algorithms
Processor Intel i7
 Computational Experiments (2.84 GHz), 8 GB Ram
 Conclusions and Ongoing Research
This work was partially supported by the Italian Ministry of Research, project
FIRB “Advanced tracking system in intermodal freight transportation”.
32
Dipartimento
di Ingegneria
Junior
Consulting
Centralized vs Rolling Horizon
[20 instances]
33
Dipartimento
di Ingegneria
Junior
Consulting
Static/Dynamic Case: BB vs FCFS
1-hour horizon
[20 instances]
34
Dipartimento
di Ingegneria
Junior
Consulting
Presentation outline
 Introduction
 Modeling
a Terminal Control Area
 Solution Framework and Algorithms
 Computational Experiments
 Conclusions and Ongoing Research
This work was partially supported by the Italian Ministry of Research, project
FIRB “Advanced tracking system in intermodal freight transportation”.
35
Dipartimento
di Ingegneria
Junior
Consulting
Achievements
• Detailed ASP models have been investigated for MXP and FCO;
• The computational experiments proved the effectiveness of our
rolling horizon approach compared to a centralized approach;
• Optimization algorithms outperforms simple rules, both for static
and dynamic cases, in terms of delay and travel time minimization;
• The BB-based rolling horizon approach
solves the one-hour instances quickly.
[email protected]
Dipartimento
di Ingegneria
Junior
Consulting
Further research directions
• Evaluation of aircraft rescheduling and rerouting approaches for
optimal decision making in case of various traffic disturbances
• Study of multiple criteria for aircraft traffic control at busy TCAs
(e.g. delay, priority, fairness, environmental and other cost factors)
• Development of detailed models for the coordination & real-time
optimization of en-route, approach and TCA traffic management
• Transformative: Practical realization of integrated (closed-loop)
intelligent decision support systems at traffic control centers
[email protected]
37