1.206J/16.77J/ESD.215J
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.206J/16.77J/ESD.215J Airline
Schedule Planning
Outline
– Sign-up Sheet
– Syllabus
– The Schedule Planning Process
– Flight Networks
? Time-line networks
? Connection networks
– Acyclic Networks
– Shortest Paths on Acyclic Networks
– Multi-label Shortest Paths on Acyclic Networks
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Fleet Planning
Schedule Planning- Route Development
- Schedule Developmento Frequency Planning
o Timetable Developmento Fleet Assignment
o Aircraft Rotations
Crew Scheduling
Airport Resource Management
Pricing
Revenue Management
Sales and Distribution Operations Control
SH
OR
T
TER
M
LO
NG
T
ER
M
TA
CT
IC
AL
ST
RA
TEG
IC
Tim
e H
or
izon
Typ
es
of
De
cis
ion
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Route individual aircraft honoring
maintenance restrictions
Assign aircraft types to flight legs
such that contribution is maximized
A flight spe ifies origin,destination,
and departure ti e
Contribution = Revenue - Costs
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Select optimal set of flight legs
in a schedule
Assign crew (pilots and/or flight
attendants) to flight legs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Airline Schedule Planning,
Integration
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Airline Schedule Planning,
Integration
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Flight Schedule
? Minimum turn times = 30 minutes
Flight
No.
Origin Destin,Dep,
Time
Arrival
Time
1 A B 6:30 8:30
2 B C 9:30 11:00
3 C B 16:00 17:00
4 B A 18:00 20:00
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Time-Space Flight Network Nodes
? Associated with each node j is a location
l(j) and a time t(j)
? A Departure Node j corresponds to a
flight departure from location l(j) at time
t(j)
? An Arrival Node j corresponds to a
flight arrival at location l(j) at time t(j) –
min_turn_time
– t(j)= arrival time of flight + min_turn_time =
flight ready time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Time-Space Flight Network Arcs
? Associated with each arc jk (with
endnodes j and k) is an aircraft
movement in space and time
? A Flight Arc jk represents a flight
departing location l(j) at time t(j) and
arriving at location l(k) at time t(k) –
min_turn_time
? A Ground Arc or Connection Arc jk
represents an aircraft on the ground at
location l(j) (= l(k)) from time t(j) until
time t(k)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Time-Line Network
8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00
City A
City B
City C
City D
? Ground arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Connection Network
8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00
City A
City B
City C
City D
? Connection arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Time-Line vs,Connection Flight
Networks
? For large-scale problems,time-line network
has fewer ground arcs than connection arcs in
the connection network
– Further reduction in network size possible
through,node consolidation”
? Connection network allows more complex
relations among flights
– Allows a flight to connect with only a subset of
later flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Time-Line Network
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Node Consolidation
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Flight Networks and Shortest Paths
? Shortest paths on flight networks correspond
to:
– Minimum cost itineraries for passengers
– Maximum profit aircraft routes
– Minimum cost crew work schedules (on crew-
feasible paths only)
?Important to be able to determine shortest
paths in flight networks
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Shortest Path Challenges in Flight
Networks
? Flight networks are large
? Thousands of flight arcs and ground arcs; thousands of
flight arcs and tens of thousands connection arcs
? For many airline optimization problems,repeatedly
must find shortest paths
? Must consider only,feasible” paths when
determining shortest path
?,Ready time” (not,arrival time”) of flight arrival nodes
ensures feasibility of aircraft routes
? Feasible crew work schedules correspond to a small
subset of possible network paths
? Identify the shortest,feasible” paths (i.e.,feasible work
schedules) using multi-label shortest path algorithms
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Cyclic Networks
Acyclic Networks
Acyclic Directed Networks
? Time-line and Connection networks are
acyclic directed networks
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Acyclic Networks and Shortest
Paths
? Efficient algorithms exist for finding shortest
paths on acyclic networks
– Amount of work is directly proportional to the
number of arcs in the network
– Topological ordering necessary
? Consider a network node j and let n(j) denote its
number
? The nodes of a network G are topologically ordered if
for each arc jk in G,n(j) < n(k)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
1
2
3
6
5
4
1
2
3
4 5
6
7
1
3
7654
2 1
5
7643
2
Topological Orderings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Topological Ordering Algorithm
? Given an acyclic graph G,let n= 1 and
n(j)=0 for each node j in G
? Repeat until n=|N|+1 (where |N| is
the number of nodes in G)
– Select any node j with no incoming arcs
and n(j) = 0.
– Let n(j) = n
– Delete all arcs outgoing from j
– Let n = n+1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
1
2
3
4
5
6
7
8
9
10
Shortest Paths on Acyclic
Networks
1,inf,-1
n(j),l(j),p(j)
2,inf,-1
3,inf,-1
4,inf,-1
5,inf,-1
6,inf,-1
7,inf,-1
8,inf,-1
9,inf,-1
10,inf,-11,0,0
10 1
0,1
10 2
11,20,3
1,3
2,4
1,4
1,5
5 1,6
1,7
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Shortest Path Algorithm for Acyclic
Networks
? Given acyclic graph G,let l(j) denote the
length of the shortest path to node j,p(j)
denote the predecessor node of j on the
shortest path and c(jk) the cost of arc jk
? Set l(j)=infinity and p(j)= -1 for each node j in
G,let n=1,and set l(1)= 0 and p(1)=0
? For n<|N|+1
– Select node j with n(j) = n
– For each arc jk let l(k)=min(l(k),l(j)+c(jk))
? If l(k)=l(j)+c(jk),set p(k)=j
– Let n = n+1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Multiple Label (Constrained) Shortest
Paths on Acyclic Networks
? Consider the objective of finding the minimum cost path
with flying time less than a specified value F
? Let label tp(j) denote the flying time on path p to node j and
label lp(j) denote the cost of path p to node j,for any j
? Only paths with tp(j) < F,at any node j,are considered (the
rest are excluded)
? A label set must be maintained at node j for each non-
dominated path to j
– A path p’ is dominated by path p at node j if lp’(j) > lp(j) and tp’(j) > tp(j)
– If p’ is not dominated by any path p at node j,p’ is non-dominated at
j
– In the worst case,a label set is maintained at each node j for each
path p into j
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Constrained Shortest Paths and
Crew Scheduling
? Label sets are used to ensure that the shortest path
is a,feasible” path
– Labels are used to count the number of work hours in a
day,the number of hours a crew is away from their home
base,the number of flights in a given day,the number of
hours rest in a 24 hour period,etc…
– In some applications,there are over 2 dozen labels in a
label set
?Many paths are non-dominated
?Exponential growth in the number of label sets (one
set for each non-dominated path) at each node
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
1
2
3
4
5
6
7
8
9
10
Shortest Paths on Acyclic
Networks
1,inf,inf,-1,-1
p,lp1(j),lp2(j),pp(j),ppp(j)
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-10,0,0,0
10 0,1,
0,0,1,1
10 1,2,
11,1,2,0,1,3,1
1,1,3,1
2,2,3,4,1
1,3,4,1
1,3,5,1
5 1,6,6,1
1,1,7,7,1
2,2,4,7,1
2,11,6,8,1
3,3,8,8,2
Max value of label 2 = 7
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
Constrained Shortest Path Notation
for Acyclic Networks
? Given acyclic graph G,
– lpk(j) denotes the value of label k (e.g.,length,
flying time,etc.) on label set p at node j
– pp(j) denotes the predecessor node for label set p
at node j
– ppp(j) denotes the predecessor label set for label set
p at node j
– c(jk) denotes the cost of arc jk
– m denotes the maximum possible number of
non-dominated label sets at any node j
– np(j) denotes the number of non-dominated label
sets for node j
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Constrained Shortest Path Algorithm for
Acyclic Networks
? For p = 1 to m,let lpk(j)=infinity for each k,
and np(j)=0,pp(j)= -1 and ppp(j)= -1 for each
node j in G
? Let n=1 and set np(1)=1,l1k(1)= 0 for each k,
p1(1)=0 and pp1(1)=0
? For n<|N|+1
– Select node i with n(i) = n
– For each non-dominated p at node i
? For each arc ij,let np(j)= np(j)+1,pnp(j)(j)=i,ppnp(j)(j)=p
– For each k,let lnp(j)k(j) =lpk(i)+c(ij)
? If lnp(j)k(j)>lsk(j) for some s=1,..,np(j)-1,then dominated
and set np(j)= np(j)-1
– Let n = n+1
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.206J/16.77J/ESD.215J Airline
Schedule Planning
Outline
– Sign-up Sheet
– Syllabus
– The Schedule Planning Process
– Flight Networks
? Time-line networks
? Connection networks
– Acyclic Networks
– Shortest Paths on Acyclic Networks
– Multi-label Shortest Paths on Acyclic Networks
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Fleet Planning
Schedule Planning- Route Development
- Schedule Developmento Frequency Planning
o Timetable Developmento Fleet Assignment
o Aircraft Rotations
Crew Scheduling
Airport Resource Management
Pricing
Revenue Management
Sales and Distribution Operations Control
SH
OR
T
TER
M
LO
NG
T
ER
M
TA
CT
IC
AL
ST
RA
TEG
IC
Tim
e H
or
izon
Typ
es
of
De
cis
ion
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Route individual aircraft honoring
maintenance restrictions
Assign aircraft types to flight legs
such that contribution is maximized
A flight spe ifies origin,destination,
and departure ti e
Contribution = Revenue - Costs
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Select optimal set of flight legs
in a schedule
Assign crew (pilots and/or flight
attendants) to flight legs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Airline Schedule Planning,
Integration
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Airline Schedule Planning,
Integration
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Flight Schedule
? Minimum turn times = 30 minutes
Flight
No.
Origin Destin,Dep,
Time
Arrival
Time
1 A B 6:30 8:30
2 B C 9:30 11:00
3 C B 16:00 17:00
4 B A 18:00 20:00
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Time-Space Flight Network Nodes
? Associated with each node j is a location
l(j) and a time t(j)
? A Departure Node j corresponds to a
flight departure from location l(j) at time
t(j)
? An Arrival Node j corresponds to a
flight arrival at location l(j) at time t(j) –
min_turn_time
– t(j)= arrival time of flight + min_turn_time =
flight ready time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Time-Space Flight Network Arcs
? Associated with each arc jk (with
endnodes j and k) is an aircraft
movement in space and time
? A Flight Arc jk represents a flight
departing location l(j) at time t(j) and
arriving at location l(k) at time t(k) –
min_turn_time
? A Ground Arc or Connection Arc jk
represents an aircraft on the ground at
location l(j) (= l(k)) from time t(j) until
time t(k)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Time-Line Network
8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00
City A
City B
City C
City D
? Ground arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Connection Network
8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00
City A
City B
City C
City D
? Connection arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Time-Line vs,Connection Flight
Networks
? For large-scale problems,time-line network
has fewer ground arcs than connection arcs in
the connection network
– Further reduction in network size possible
through,node consolidation”
? Connection network allows more complex
relations among flights
– Allows a flight to connect with only a subset of
later flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Time-Line Network
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Node Consolidation
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Flight Networks and Shortest Paths
? Shortest paths on flight networks correspond
to:
– Minimum cost itineraries for passengers
– Maximum profit aircraft routes
– Minimum cost crew work schedules (on crew-
feasible paths only)
?Important to be able to determine shortest
paths in flight networks
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Shortest Path Challenges in Flight
Networks
? Flight networks are large
? Thousands of flight arcs and ground arcs; thousands of
flight arcs and tens of thousands connection arcs
? For many airline optimization problems,repeatedly
must find shortest paths
? Must consider only,feasible” paths when
determining shortest path
?,Ready time” (not,arrival time”) of flight arrival nodes
ensures feasibility of aircraft routes
? Feasible crew work schedules correspond to a small
subset of possible network paths
? Identify the shortest,feasible” paths (i.e.,feasible work
schedules) using multi-label shortest path algorithms
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Cyclic Networks
Acyclic Networks
Acyclic Directed Networks
? Time-line and Connection networks are
acyclic directed networks
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Acyclic Networks and Shortest
Paths
? Efficient algorithms exist for finding shortest
paths on acyclic networks
– Amount of work is directly proportional to the
number of arcs in the network
– Topological ordering necessary
? Consider a network node j and let n(j) denote its
number
? The nodes of a network G are topologically ordered if
for each arc jk in G,n(j) < n(k)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
1
2
3
6
5
4
1
2
3
4 5
6
7
1
3
7654
2 1
5
7643
2
Topological Orderings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Topological Ordering Algorithm
? Given an acyclic graph G,let n= 1 and
n(j)=0 for each node j in G
? Repeat until n=|N|+1 (where |N| is
the number of nodes in G)
– Select any node j with no incoming arcs
and n(j) = 0.
– Let n(j) = n
– Delete all arcs outgoing from j
– Let n = n+1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
1
2
3
4
5
6
7
8
9
10
Shortest Paths on Acyclic
Networks
1,inf,-1
n(j),l(j),p(j)
2,inf,-1
3,inf,-1
4,inf,-1
5,inf,-1
6,inf,-1
7,inf,-1
8,inf,-1
9,inf,-1
10,inf,-11,0,0
10 1
0,1
10 2
11,20,3
1,3
2,4
1,4
1,5
5 1,6
1,7
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Shortest Path Algorithm for Acyclic
Networks
? Given acyclic graph G,let l(j) denote the
length of the shortest path to node j,p(j)
denote the predecessor node of j on the
shortest path and c(jk) the cost of arc jk
? Set l(j)=infinity and p(j)= -1 for each node j in
G,let n=1,and set l(1)= 0 and p(1)=0
? For n<|N|+1
– Select node j with n(j) = n
– For each arc jk let l(k)=min(l(k),l(j)+c(jk))
? If l(k)=l(j)+c(jk),set p(k)=j
– Let n = n+1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Multiple Label (Constrained) Shortest
Paths on Acyclic Networks
? Consider the objective of finding the minimum cost path
with flying time less than a specified value F
? Let label tp(j) denote the flying time on path p to node j and
label lp(j) denote the cost of path p to node j,for any j
? Only paths with tp(j) < F,at any node j,are considered (the
rest are excluded)
? A label set must be maintained at node j for each non-
dominated path to j
– A path p’ is dominated by path p at node j if lp’(j) > lp(j) and tp’(j) > tp(j)
– If p’ is not dominated by any path p at node j,p’ is non-dominated at
j
– In the worst case,a label set is maintained at each node j for each
path p into j
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Constrained Shortest Paths and
Crew Scheduling
? Label sets are used to ensure that the shortest path
is a,feasible” path
– Labels are used to count the number of work hours in a
day,the number of hours a crew is away from their home
base,the number of flights in a given day,the number of
hours rest in a 24 hour period,etc…
– In some applications,there are over 2 dozen labels in a
label set
?Many paths are non-dominated
?Exponential growth in the number of label sets (one
set for each non-dominated path) at each node
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
1
2
3
4
5
6
7
8
9
10
Shortest Paths on Acyclic
Networks
1,inf,inf,-1,-1
p,lp1(j),lp2(j),pp(j),ppp(j)
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-1
1,inf,inf,-1,-10,0,0,0
10 0,1,
0,0,1,1
10 1,2,
11,1,2,0,1,3,1
1,1,3,1
2,2,3,4,1
1,3,4,1
1,3,5,1
5 1,6,6,1
1,1,7,7,1
2,2,4,7,1
2,11,6,8,1
3,3,8,8,2
Max value of label 2 = 7
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
Constrained Shortest Path Notation
for Acyclic Networks
? Given acyclic graph G,
– lpk(j) denotes the value of label k (e.g.,length,
flying time,etc.) on label set p at node j
– pp(j) denotes the predecessor node for label set p
at node j
– ppp(j) denotes the predecessor label set for label set
p at node j
– c(jk) denotes the cost of arc jk
– m denotes the maximum possible number of
non-dominated label sets at any node j
– np(j) denotes the number of non-dominated label
sets for node j
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Constrained Shortest Path Algorithm for
Acyclic Networks
? For p = 1 to m,let lpk(j)=infinity for each k,
and np(j)=0,pp(j)= -1 and ppp(j)= -1 for each
node j in G
? Let n=1 and set np(1)=1,l1k(1)= 0 for each k,
p1(1)=0 and pp1(1)=0
? For n<|N|+1
– Select node i with n(i) = n
– For each non-dominated p at node i
? For each arc ij,let np(j)= np(j)+1,pnp(j)(j)=i,ppnp(j)(j)=p
– For each k,let lnp(j)k(j) =lpk(i)+c(ij)
? If lnp(j)k(j)>lsk(j) for some s=1,..,np(j)-1,then dominated
and set np(j)= np(j)-1
– Let n = n+1
