Stephane Bratu, 35-217, x3-3507, sbratu@mit.edu

TBA

Description: Explores a variety of models and optimization techniques for the solution of airline schedule planning problems. Schedule design, fleet assignment, aircraft maintenance routing, crew scheduling, passenger mix, and other topics are covered. Recent models and algorithms integrating some of the schedule planning problems are introduced. Modeling and solution techniques designed specifically for large-scale problems, and state-of-the-art applications of these techniques to airline problems are detailed.

Lecture

Dates

Topic

9/5

Course Introduction and Overview

· Airline schedule planning

· Flight schedules: network representations, shortest path problems

Reading:

[BT], [DS]

2-3

9/10 -912

The Passenger Mix Model

· Model description and solution algorithms

· Column and row generation techniques

· Review of results by Kniker, et al. and sensitivity analysis of Lohatepanont

Reading:

[BHJS], [BHV], [BJNSV], [L]

4-7

9/19 -10/1

The Fleet Assignment Problem

· Basic models and solution approaches, and their shortcomings

· Review of branch-and-bound

· Itinerary-based fleet assignment- model and branch-and-price-and-cut solution techniques

· Subnetwork-based fleet assignment- model and solution approach

· Fleet assignment model extensions to include time windows

· Review of Kniker, et al., Lohatepanont, et al., Farahat, et al., and Rexing, et al. results

Reading:

[HBJMNS], [BKL], [BFL], [RBKJ]

Lecture

Dates

Topic

8-10

10/03 –10/15

The Crew Pairing Problem, the Aircraft Routing Problem, and the Integrated Crew Pairing-Aircraft Routing Problem

· Crew Paring Problem, Bidline generation/rostering

· Crew Pairing Problem models and solution approaches

· Branch on follow-ons

· Review of results of Barnhart, et al.

· Aircraft Routing Problem models and solution approach—constrained shortest paths, branch-and-price

· Integrated crew pairing and aircraft routing

Reading:

[ABHJR], [BJNV], [BJAH], [DS], [CB]

10/17

The Schedule Design Problem

· Demand and supply interactions

· Network wide, schedule improver model and solution approach

· Review of results of Lohatepanont, et al.

Reading:

[LB]

10/22

Integrated Models

· Integrated crew pairing and fleet assignment

· Integrated aircraft routing and fleet assignment

Reading:

[BLS], [BBCJNS]

10/24

Project Presentations

Problem Sets and Project:

	9/10			Assignment 1 handed out. Projects commence.
		10/03			Assignment 1 is due. Assignment 2 handed out.
10/17			Assignment 2 is due.
10/24			Project reports and presentations due.

Requirements:

You are responsible for completing two assignments, each representing 25% of your grade, and one project report representing 35% of your grade. The remaining 15% of your grade is based on your project presentation and participation in class.

References:

[ABHJR] R. Anbil, C. Barnhart, L. Hatay, E.L. Johnson and V.S. Ramakrishnan (1993). Crew Pairing Optimization at American Airlines Decision Technologies. T. Ciriano and R. Leachman (eds.). Optimization in Industry: Mathematical Programming and Modeling Techniques in Practice, John Wiley and Son, England, 31-36.

[BBCJNS] C. Barnhart, N.L. Boland, L.W. Clarke, E.L. Johnson, G.L. Nemhauser, and R.G. Shenoi (1998). Flight String Models for Aircraft Fleeting and Routing, Transportation Science, Focused Issue on Airline Optimization, Vol. 32, No. 3, 208-220.

[BFL] C. Barnhart, A. Farahat, and M. Lohatepanont (2001). Airline Fleet Assignment: An Alternative Model and Solution Approach Based on Composite Variables, submitted to Operations Research, May 2001.

[BKL] C. Barnhart, T. Kniker, and M. Lohatepanont (2000). Itinerary-Based Airline Fleet Assignment. submitted to Transportation Science.

[BHJS] C. Barnhart, C.L. Hane, E.L. Johnson and G. Sigismondi (1995). A Column Generation and Partitioning Approach for Multi-Commodity Flow Problems, Telecommunication Systems 3, 239-258.

[BHV] C. Barnhart, C.L. Hane, and P. H. Vance (to appear). Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Problems, Operations Research, Vol. 48, No., 2, 318-326, March-April 2000.

[BJAH] C. Barnhart, E.L. Johnson, R. Anbil, and L. Hatay (1994). A Column Generation Technique for the Long-Haul Crew Assignment Problem. T. Ciriano and R. Leachman (eds.) Optimization in Industry: Volume II, John Wiley and Son, England, 7-22.

[BJNSV] C. Barnhart, E.L. Johnson, G.L Nemhauser, M.W.P. Savelsbergh and P.H.Vance (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs, Operations Research, Vol. 46, No. 3, 316-329.

[BJNV] C. Barnhart, E.L. Johnson, G.L Nemhauser, and P.H.Vance (1999). Crew Scheduling, Handbook of Transportation Science, Randolph W. Hall (editor), Kluwer Academic Publisher, Norwell, MA pp. 493-521.

[BLS] C. Barnhart, F. Lu, and R. Shenoi (1997). Integrated Airline Scheduling. Operations Research in the Air Industry, International Series in Operations Research and Management Science, Vol. 9, pp.384-403, edited by Prof. Gang Yu, Kluwer Academic Publishers.

[BT] C. Barnhart and K. Talluri (1997). Airline Operations Research. Design and Operation of Civil and Environmental Engineering Systems, pp. 435-469.

[CB] A. Cohn, and C. Barnhart (2000). Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions, submitted to Operations Research, December 2000.

[DS] M. Desrochers and F. Soumis (1988). A Generalised Permanent Labelling Algorithm for the Shortest Path Problem with Time Windows. INFOR 26, 3, 191-212.

[HBJMNS] C.A. Hane, C. Barnhart, E.L. Johnson, R.E. Marsten, G.L. Nemhauser, and G. Sigismondi (1995). The Fleet Assignment Problem: Solving a Large-Scale Integer Program. Mathematical Programming, 70, 2, 211-232.

[L] M. Lohatepanont (2001). Passenger Mix Problem—portion of Ph.D. dissertation of Lohatepanont. Center for Transportation Studies, Massachusetts Institute of Technology, Cambridge, MA.

[LB] M. Lohatepanont, and C. Barnhart (2001). Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment, submitted to Transportation Science, June 2001.

[RBKJ] B. Rexing, C. Barnhart, T. Kniker, A. Jarrah, and N. Krishnamurthy (2000). Airline Fleet Assignment with Time Windows, Transportation Science, Vol. 34, No. 1, 1-20.