Transcript Optimizing Air and Rail Transportation Operations

Air Transportation Service
Design
Pamela H. Vance
Goizueta Business School
Emory University
Outline

Current State of Practice in domestic (U.S.)
passenger airlines
–
–
–
–

Schedule Development
Fleet Assignment
Routing
Crew Scheduling
Current active areas of research
– Overview of research on service design issues
– Focus on recent crew scheduling results
The Airline Planning Process

Flight Schedule Development
– Given:
» historical data on passenger OD demand
» air traffic and airport restrictions
» aggregate aircraft availability
– Find:
» departure/arrival times for each segment to maximize
potential revenue
– State of Practice
» schedules are usually generated by marketing
department with little or no input from operations
The Airline Planning Process

Fleet Assignment
– Given:
» Flight Schedule
 Each flight covered exactly once by one fleet type
» Number of Aircraft by Equipment Type
 Can’t assign more aircraft than are available, for each type
» FAA Maintenance Requirements
» Turn Times by Fleet Type at each Station
» Other Restrictions: Gate, Noise, Runway, etc.
» Operating Costs, Spill and Recapture Costs, Total Potential
Revenue of Flights, by Fleet Type
The Airline Planning Process

Fleet Assignment (cont.)
– Find:
» Cost minimizing (or profit maximizing) assignment of
aircraft fleets to scheduled flights such that maintenance
requirements are satisfied, conservation of flow (balance)
of aircraft is achieved, and the number of aircraft used
does not exceed the number available (in each fleet type)
– State of Practice
» IP models are used
 Deterministic demand representation
 Aggregate demand and fare class
 Approximate spill and recapture representation
The Airline Planning Process

Aircraft routing
– Given:
» set of flight legs assigned to each aircraft type
» through value associated with possible flight connections
– Find a routing that:
» provides sufficient maintenance opportunities
» maximizes total through value
– State of Practice
» typically performed manually once fleet assignment and
required throughs are set
 required throughs may be implied by fleet
assignment and/or required by marketing
The Airline Planning Process

Crew Planning
– Given:
» flight segments to be covered by a single fleet
» aircraft turns
» contractual/FAA work rules
– Find:
» minimum cost set of crew itineraries or pairings that
covers each flight exactly once
– State of Practice
» use of large-scale IP models
» problem is decomposed into several parts (more later)
The Airline Planning Proces
Process
Schedule
Selection
Fleet
Assign.
dep/arr
times
Crew
Planning
Routing
decomp.
by fleet
aircraft
turns
Current State of Practice


Hierarchical approach to service design
Little or no feedback between stages in the
process
– organizationally, decisions may be the
responsibility of different departments

Decisions at earlier stages may have
significant effects on the quality of solutions
at later stages
Opportunities for Improvement



Improvements in large-scale optimization
may someday allow simultaneous solution of
more than one part of the problem
Models that account for the interaction
between stages or allow feedback between
phases
Models that account for uncertainty in
operations
Research Overview

Combined Fleeting and Schedule Selection
– Fleeting with time windows
» Desaulniers et al. (1997)
» Rexing et al. (2000)
 discretize time window
 use multiple copies of each departure

Time windows can provide significant cost savings, as well
as a potential for freeing aircraft
– Incremental Schedule Design
» Lohatepanont and Barnhart (1999)
 Select flights from an expanded set of flight legs
Fleet Assignment Models
Min   ck ,i f k ,i
kK iL
Subject to:
 f k ,i  1
i  L
fk ,i  0
k , o , t
kK
yk ,o,t  

iI ( k ,o,t )
fk ,i  yk ,o,t  

iO( k ,o,t )
 yk ,o,tn   fk ,i  Nk k  K
oO
iCL ( k )
f k ,i  0,1
yk , o , t  0
Research Overview

Improved Fleet Assignment Models
– Itinerary-based fleet assignment
» Knicker (1998)
» Compensate for network effects due to multi-leg
itineraries
» More accurately capture revenue by fare class
» Iterates between solution of traditional Fleet Assignment
Model and a Passenger Flow model to calculate revenue
» Adjust cost coefficients to improve approximation
Network Effects
75
$300
75
$200
X
Request:
150
$225
Y
Z
150
225
Capacity: 100
200
Research Overview

Combined Routing and Fleeting
– Barnhart et al. (1998)
» use maintenance to maintenance strings of flights
» assign an aircraft type to a string rather than a single
flight

Crew Scheduling before Routing
– Klabjan et al (1999)
» add plane count constraints to the crew scheduling
problem
» implies certain aircraft turns
Crew Planning

Definitions
– duty period
– pairing

Restrictions on legal pairings
– FAA rules
» minimum rest
» maximum flying per duty
» 8-in-24
– Contractual rules
» max TAFB
» max sit
– Operational considerations
» min sit
Crew Planning

Pairing cost structure
– nonlinear and discontinuous
– duty cost = maximum of: flying time, minimum
guarantee, fraction of elapsed time
– pairing cost = maximum of: duty cost, minimum
per day, TAFB
– flying time in schedule provides a lower bound
– schedule quality is measured as % paid over
flying time
– each percentage point translates to millions
annually for major domestic carriers
Crew Planning

Problem is formulated as a set partitioning problem
min cx
Ax = 1
x binary



A has one row for each flight in the schedule and one
column for each potential pairing
Because of the hub-and-spoke network structure
used by most U.S. carriers, the number of columns in
A is HUGE so
column generation methods are used
Crew Planning

Typically crew planning problems are solved in
phases
– problem size may prohibit solving the entire weekly
schedule for a single fleet
» small problems may have a few hundred thousand possible
pairings which large problems (500+ flights) may have billions
of potential pairings
– for operational reasons, airlines would prefer to maintain
daily regularity of the pairings
– weekly solutions contain many more different pairings
which can create headaches for bidline generation or
rostering purposes
Crew Planning

Daily Problem
– Given:
» flights flown 4 or more times per week
– Find:
» low cost schedule assuming flights are flown every day

Exceptions
– Given:
» flights flown fewer than 4 times per week
» broken pairings from the daily solution
– Find:
» low-cost weekly solution for this subset of flights

Transition
– Provides pairings for monthly schedule changes
Crew Planning
Daily
Problem
Exceptions
broken
pairings
Transition
broken
pairings
Outline of Remainder of Talk


Recent research in column generation
methods
Combining phases of the crew pairing
solution process
Column Generation

Column generation is an approach for solving LPs
with a large number of variables
– basic concepts from sensitivity analysis are used to solve the
LP to optimality without explicitly considering all the
possible variable

Solve the linear programming relaxation of the crew
scheduling problem
min cx
A’x = 1
x binary
– A’ contains only a subset of the possible columns (pairings)
in A
– Identify new columns to add to A’ to improve the solution
Column Generation

Current state-of-the-art
– multi-label shortest path methods (dynamic programming)
on specially structured networks
» duty networks
 large number of arcs
– one arc per duty
– can be hundreds of connections per duty
– Ex: 363 flights, 7838 duties, 1.65 M connections
 fewer labels per path since duty rules are built in
» flight networks
 smaller number of arcs
– one arc per flight
– typically not more than 30 connections per flight
 larger number of labels
Generating Good Pairings
City A
City B
City C
City D
8:00
12:00
16:00
20:00
8:00
12:00
16:00
20:00
Column Generation
– enumeration and SPRINT Anbil et al. (1991)
» feasible pairings are enumerated up-front and stored offline
» after solving the LP relaxation, run through the list and
identify several thousand negative reduced cost columns
to add to A’
» use specialized data structures (Hu and Johnson (1999))
– random enumeration and SPRINT
» Klabjan et al. (1999)
» even when specialized data structures are used the
enumerated pairings may require too much memory
» use randomly enumerated pairings rather than
enumerating the full set
 include a potential connection with probability p, p
is a nonincreasing function of the connection time
Column Generation: On-going
Research

Hybrid networks
– Duty-flight network
» create a departure and arrival node for each flight
» Two types of arcs
 duty arcs connect first and last flights in the duty
period
 overnight arcs connect flight arrivals to departures
the next day
» has the same number of connection arcs as the flight
network
» explicitly builds duty rules into the network
Hybrid Network
Day 1
Day 2
f1
f2
f3
f4
Dep.
Arr.
Duty Arcs
Dep.
Overnight Arcs
Arr.
Duty Arcs
Column Generation: On-going
Research

Another hybrid network
– strings
» a string might be a duty or portion of a duty
» typically a string of flights between two “busy” places in
the network
» Ongoing work by Tina Shaw
Interaction Between Phases

Daily and Exceptions crew pairing
– the exceptions problem is partially defined by
broken pairings from the daily solution
» Ex: Daily Pairing:
LAX-ORD
1405
1945
ORD-DCA
2030
2315
overnight
DCA-LAX
1410
1800
» the second leg is not flown on Saturday or Sunday and
the third is not flown on Saturday
» the copies of this daily pairing beginning on Friday,
Saturday, and Sunday will all be broken. The remaining
flights will end up in the exceptions problem.
Combined Daily and Exceptions
Crew Pairing


Experience with daily problems has shown
that there may be many near-optimal
solutions
Current practice does not explicitly consider
the number of daily pairings that will be
broken when assessing the quality of the
daily solution
A Combined Model


Klabjan et al. (1999)
Consider the special case where we wish to increase
the number of daily pairings that can actually be
flown 7 days per week
Let: xi = 1 if all 7 copies of flight i are covered by daily pairings

yp = 1 if pairing p is used in the solution
Two kinds of constraints
– if xi = 1, we must cover the flight with a daily pairing
– if xi = 0 or the flight is a less than 7-day flight, we must cover
the flight with a dated pairing
A Combined Model
min
c
pP
s.t.
p
yp 
 xi 
xi 
pP7
y
pP7 :i p
y
pP:i p
y
pP:i p
 7c
p
p
p
xi , y p  0,1
y p  iL bxi
0
1
1
p
7
i  L7
i  L7 , d  D
i  L
A Combined Model
daily
pairings
7-day flights
(not dated)
all flights
(dated)
-1
-1
-1
...
1
1
1
1
1
1
1
1
1
1
1
...
dated
pairings
1
0
1
...
=0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
=1
Computational Challenges



If we included all possible columns in the previous
special case, we would have as many pairings as the
combined daily and weekly problems
This modeling idea can be extended by creating
separate blocks depending on the number of
consecutive times per week a flight repeats in the
same pairing
Solve a relaxed problem where crew base to crew
base paths are substituted for pairings in some of the
blocks
Problem Instances
Name
Fs
Fm
Fl
7-day
90
273
331
6-day
24
64
104
5-day
5
5
15
Daily
0
38
42
Total
119
380
492
Computational Results
Name
Fs
Fm
Fl
Method
d/e
relax1
relax2
d/e
relax1
relax2
d/e
relax1
relax2
FTC
9.2%
7.0%
5.6%
4.2%
3.8%
2.5%
2.3%
2.2%
2.0%
Reg.
276
120
127
622
318
390
1365
520
567
Insights into Schedule Regularity



Models are extremely large and impractical for
planning use on all but small problems
Computational results show that there is potential to
improve regularity and cost simultaneously
Open question: can we develop more tractable
models that will enable reliable construction of more
regular crew schedules?
Another Model for Crew
Schedule Regularity


Use traditional weekly (dated) set
partitioning model
Columns are now “super-pairings”
– a super pairing may contain 1 or more copies of a
daily pairing
– Consider a daily pairing
» suppose all flights operate 7 days per week
» there are  7    7    7    7    7    7    7 
potential super
0
1
2
3
4
5
6
pairings              
» is there a sensible way to control the combinatorial
explosion?
Conclusion

Major opportunities for improvement in air
transport service design
–
–
–
–
closer integration of stages of the planning process
improvements in model accuracy
advances in large-scale optimization
incorporation of stochasticity