LARGE SCALE SYSTEMS OPTIMIZATION

FALL 2011

OM 380.9 – ORI 391Q.9

SESSION 10

 

1.      Learning Objectives

A.    Today’s discussions

a.       Cutting stock

b.      Airline crew scheduling

B.       Homework and reading Assignment

a.       Airline crew scheduling

2.      We finish our discussion of cutting stock models by doing items #3.C and 4 of the class 9 plan.

3.       (20-30 minutes)  We discuss the paper crew scheduling prob.pdf, with the following points emphasized:

A.    Important airline problems where mip models are employed

B.     The flight schedule

C.     The aircraft routing (only one type of aircraft)

D.    Pairing generation for crews.  We verify the hours and cost for pairing 1 on p. 428

E.     The problem in row-oriented form on p.429

F.      Part of the problem in column-oriented form in crewsched.xls

G.    Set partitioning, set covering, and set packing problems

H.    Locating fire stations using set covering

I.       We examine the spreadsheet “crewsched.xls”

4.      (15-20 minutes) Class discussion of “min cost flow example.pdf” on our website under course readings/column generation.  This is an example of DW decomposition applied to a min cost multicommodity flow problem. 

A.    The instructor describes the problem and notation.  It has a single source and sink for each commodity.

B.     How can you show that extreme points of the blocks correspond to chain flows from source to sink for each commodity?  (discuss in your learning groups)

C.     We develop the DW master and see that it’s a scaled version of the arc-chain form of the problem with convexity rows.  The subproblems are shortest path problems, with arc lengths modified costs for the arcs.  If there are many sources and sinks for some commodity, the sub is a min cost flow problem with modified costs.

5.       (rest of class) Class discussion of “Recent advances in crew-pairing optimization at American Airlines.” Several learning groups discuss what they thought was important.  We then proceed to discuss the following:

A.    How is a “crew” defined?

B.     What the time horizon is used by AA?

C.     About how long does a pairing last and why?

D.    Why is crew pairing important to AA?

E.     Why are pairings done separately for each aircraft fleet?

F.      What categories of flights are paired separately?

G.    What factors influence the cost of a pairing

H.    What is “pay and credit” (p.64 and 70).

I.       What is meant by Generating all possible combinations of pairings” in the middle of p. 66, 2nd column.

J.       What is a “subproblem”, and why does its size increase so fast (see table 2 p. 69).  Also see p.72 where it implies that current subproblems do not include all flight segments over a month.

K.    How are crew base limits modeled?

L.     How does the hub and spoke system increase the number of possible pairings?      

M.   What period of time is covered by the model, what flights are included, and how much time is available to formulate and solve it?

N.    What’s a bidline (p. 63)?

O.    We discuss the ways AADT speeded the system up (pp. 67-69).  Note the use of Lagrangian Relaxation, which we will study later

P.      How have ideas from metaheuristics helped (p. 69, Glover reference).

Q.    What benefits has AA obtained from all this?

R.     How can changes in the flight schedule affect crew pairing costs?

S.      Note that AADT sold TRIP to 11 airlines and one railroad (p. 71).  Think a little about doing this for a railroad.

T.      We discuss the “what-if” studies described on p. 72.

U.    Note the improvements generated by IBM’s OSL, and by Ellis Johnson (p. 72).

V.    How can parallel processing speed things up?

Note: for more information on OR applications in airlines, see “Operations Research in the Airline Industry”, Edited by Gang Yu, Kluwer Academic Publishers, 1998

6.       Homework for next class.

A.    Do homework 3, due  class 12

B.     Read the paper on our website under course readings/disruption management titled “new era for crew recovery at CA.pdf”.  Each group briefly describes at least 3 items or points in the paper which they thought were important, plus any questions that arose as they read it, and bring these to class.  I will call on groups at random to present their work.  This paper won the 2002 Edelman prize, awarded by INFORMS for the years best OR application.  The first author, Gang Yu, did the work while he was a professor in the IROM dept here.  He founded CALEB technologies, which is still based in Austin, and the CALEB authors were graduate students in IE/OR or IROM at UT.  I will try to get a speaker from CALEB this semester.

C.     Read “mixed-integer programming” on our website under course readings/mixed integer programming.  Note that there are both a Word doc and a PDF version of this.  This reading is chapter 9 of “Optimization of Chemical Processes” by Edgar, Himmelblau, and Lasdon.  Focus on the sections dealing with MIP models and with the branch and bound algorithm.  We discussed part of this in a previous class.