Airline Schedule Planning

Engineering > Aeronautics & Astronautics > Airline Schedule Planning

Airline Schedule Planning posted by member150_php on 2/23/2009

Add To Favorites

Abstract/Syllabus

Courseware/Lectures

Test/Tutorials

Airline Schedule Planning

Spring 2003

Air traffic management software. (Image courtesy of NASA: http://www.aerospace.nasa.gov.)

Course Highlights

This course site features a complete set of lecture notes and extensive readings.

Course Description

Explores a variety of models and optimization techniques for the solution of airline schedule planning and operations problems. Schedule design, fleet assignment, aircraft maintenance routing, crew scheduling, passenger mix, and other topics are covered. Recent models and algorithms addressing issues of model integration, robustness, and operations recovery 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.

Technical Requirements

File decompression software, such as Winzip® or StuffIt®, is required to open the .zip files found on this course site. Microsoft® Excel software is recommended for viewing the .xls files found on this course site. Free Microsoft® Excel viewer software can also be used to view the .xls files. Microsoft® Powerpoint software is recommended for viewing the .ppt files found on this course site. Free Microsoft® Powerpoint viewer software can also be used to view the .ppt files. Any number of software tools can be used to run the .dat files found on this course site. Any number of programs can be used to run the .dat, .mod, .prj, .txt, and .osc files found on this course site. Please refer to the course materials for any specific instructions or recommendations.

Syllabus

Lecturer

Prof. Cynthia Barnhart

Teaching Assistant

Stephane Bratu

Prerequisites

Permission of instructor

Description

Assignments

3 assignments, each representing 15% of the grade, a mid-term quiz representing 20% of the grade, and one project presentation and report representing 35% of the grade.

Academic Honesty Policy

The Department of Civil and Environmental Engineering adheres to the strictest standards of academic honesty. An important aspect of achieving these standards is to be sure that students are aware of expectations of faculty regarding academic honesty. This statement clarifies the faculty's expectations in 1.206J.

Assignments

Assignments performed by students for submission have a dual purpose. They are intended as educational devices, including the teaching of skills such as working in teams. They are also evaluation tools for the faculty in judging the quality of performance of individual students. Our policies are intended to balance these two purposes and, unless otherwise stated, these policies apply to all assignments.

Students currently taking this class can work together to conceptualize general approaches to assignments. However, unless otherwise specified for a particular assignment, the work you submit should be done completely on your own. This includes text, numerical calculations, mathematical derivations, diagrams, graphs, computer programs and output.

Reference any written source you use in your submission.

In-class Exams

All work on in-class exams should be performed only by you. Materials you can bring into the examination will be specified by the faculty for each exam.

If you have any questions about how these policies relate to a specific situation, you should speak to Professor Barnhart.

Source: Professor Sussman's academic honesty statement for 1.221J.

Calendar

LEC #	TOPICS	KEY DATES
1	Course Introduction and Overview Airline Schedule Planning, Links to Operations
2-6	Optimizing Flows on Networks Time-space Networks Constrained Shortest Path Problems on Acyclic Shortest Paths Multicommodity Flow Models (Node-arc, Path, Tree, Keypath-continuous and Integer) Column and Row Generation Techniques Branch-and-Bound Branch-and-Price-and-Cut Computational Experiences OPL Studio	Assignment 1 Handed Out Begin to Form Project Teams
7	The Passenger Mix Model Model Description and Solution Algorithms Review of Results by Kniker, et al. and Sensitivity Analysis of Lohatepanont
8-11	The Fleet Assignment Problem Basic Models and Solution Approaches, and their Shortcomings 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 Results	Assignment 1 Due
12-13	Review and Quiz	Assignment 2 Handed Out
14-17	Crew Scheduling, the Aircraft Routing Problem, and the Integrated Crew Pairing-Aircraft Routing Problem Crew Pairing 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	Assignment 2 Due Assignment 3 Handed Out
18	Integrated Fleeting Models Integrated Crew Pairing and Fleet Assignment Integrated Aircraft Routing and Fleet Assignment
19	The Schedule Design Problem Demand and Supply Interactions Network Wide, Schedule Improver Model and Solution Approach Review of Results	Assignment 3 Due Finalized Project Proposals Due
20-22	Operations Recovery Overview of Operations Control Center Aircraft and Passenger Delays Flight Postponement and Cancellation Model The Role of Simulation
23-24	Robust Scheduling Robust Crew Scheduling Robust Aircraft Routing Degradable Schedule Design
25-26	Project Presentations and Reports	Project Reports and Presentations Due

Readings

LEC #	TOPICS	READINGS
1	Course Introduction and Overview Airline Schedule Planning, Links to Operations	Barnhart, C., and K. Talluri. "Airline Operations Research." In Design and Operation of Civil and Environmental Engineering Systems. 1997, pp. 435-469.
2-6	Optimizing Flows on Networks Time-space Networks Constrained Shortest Path Problems on Acyclic Shortest Paths Multicommodity Flow Models (Node-arc, Path, Tree, Keypath-continuous and Integer) Column and Row Generation Techniques Branch-and-Bound Branch-and-Price-and-Cut Computational Experiences OPL Studio	Desrochers, M., and F. Soumis. "A Generalised Permanent Labelling Algorithm for the Shortest Path Problem with Time Windows." INFOR 26, 3 (1988): 191-212. Barnhart, C., C. L. Hane, E. L. Johnson, and G. Sigismondi. "A Column Generation and Partitioning Approach for Multi-Commodity Flow Problems." Telecommunication Systems 3 (1995): 239-258. Barnhart, C., C. L. Hane, and P. H. Vance (to appear). "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Problems." Operations Research 48, 2 (March-April 2000): 318-326. Barnhart, C., E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance. "Branch-and-Price: Column Generation for Solving Huge Integer Programs." Operations Research 46, 3 (1998): 316-329.
7	The Passenger Mix Model Model Description and Solution Algorithms Review of Results by Kniker, et al. and Sensitivity Analysis of Lohatepanont	Barnhart, C., C. L. Hane, E. L. Johnson, and G. Sigismondi. "A Column Generation and Partitioning Approach for Multi-Commodity Flow Problems." Telecommunication Systems 3 (1995): 239-258. Barnhart, C., C. L. Hane, and P. H. Vance (to appear). "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Problems." Operations Research 48, 2 (March-April 2000): 318-326. Barnhart, C., E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance. "Branch-and-Price: Column Generation for Solving Huge Integer Programs." Operations Research 46, 3 (1998): 316-329. Lohatepanont, M. "Passenger Mix Problem—portion of Ph.D. dissertation of Lohatepanont." Center for Transportation Studies, Massachusetts Institute of Technology, Cambridge, MA, 2001.
8-11	The Fleet Assignment Problem Basic Models and Solution Approaches, and their Shortcomings 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 Results	Hane, C. A., C. Barnhart, E. L. Johnson, R. E. Marsten, G. L. Nemhauser, and G. Sigismondi. "The Fleet Assignment Problem: Solving a Large-Scale Integer Program." Mathematical Programming 70, 2 (1995): 211-232. Barnhart, C., T. Kniker, and M. Lohatepanont. "Itinerary-Based Airline Fleet Assignment." 2000. Transportation Science 36, 2 (May 2002): 199-217. Barnhart, C., A. Farahat, and M. Lohatepanont. "Airline Fleet Assignment: An Alternative Model and Solution Approach Based on Composite Variables." 2001. Submitted to Operations Research (May 2001). Rexing, B., C. Barnhart, T. Kniker, A. Jarrah, and N. Krishnamurthy. "Airline Fleet Assignment with Time Windows." Transportation Science 34, 1 (2000): 1-20. Sabre Hand-out
12-13	Review and Quiz
14-17	Crew Scheduling, the Aircraft Routing Problem, and the Integrated Crew Pairing-Aircraft Routing Problem Crew Pairing 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	Anbil, R., C. Barnhart, L. Hatay, E. L. Johnson, and V. S. Ramakrishnan. "Crew Pairing Optimization at American Airlines Decision Technologies." In Optimization in Industry: Mathematical Programming and Modeling Techniques in Practice. Edited by T. Ciriano, and R. Leachman. England: John Wiley and Son, 1993, pp. 31-36. Barnhart, C., N. L. Boland, L. W. Clarke, E. L. Johnson, G. L. Nemhauser, and R. G. Shenoi. "Flight String Models for Aircraft Fleeting and Routing." Transportation Science 32, 3 (1998): 208-220. (Focused Issue on Airline Optimization). Barnhart, C., E. L. Johnson, G. L Nemhauser, and P. H. Vance. "Crew Scheduling." In Handbook of Transportation Science. Edited by Randolph W. Hall. Norwell, MA: Kluwer Academic Publisher, 1999, pp. 493-521. Barnhart, C., E. L. Johnson, R. Anbil, and L. Hatay. "A Column Generation Technique for the Long-Haul Crew Assignment Problem." In Optimization in Industry: Volume II. Edited by T. Ciriano, and R. Leachman. England: John Wiley and Son, 1994, 7-22. Desrochers, M., and F. Soumis. "A Generalised Permanent Labelling Algorithm for the Shortest Path Problem with Time Windows." INFOR 26, 3 (1988): 191-212. Cohn, A., and C. Barnhart. "Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions." 2000. Operations Research 51, 3 (May-June 2003): 387-396.
18	Integrated Fleeting Models Integrated Crew Pairing and Fleet Assignment Integrated Aircraft Routing and Fleet Assignment	Barnhart, C., F. Lu, and R. Shenoi. "Integrated Airline Scheduling." In Operations Research in the Air Industry. International Series in Operations Research and Management Science. Vol. 9. Edited by Prof. Gang Yu. Kluwer Academic Publishers, 1997, pp. 384-403. Barnhart, C., N. L. Boland, L. W. Clarke, E. L. Johnson, G. L. Nemhauser, and R. G. Shenoi. "Flight String Models for Aircraft Fleeting and Routing." Transportation Science 32, 3 (1998): 208-220. (Focused Issue on Airline Optimization). Klabjan Hand-out
19-20	The Schedule Design Problem Demand and Supply Interactions Network Wide, Schedule Improver Model and Solution Approach Review of Results	Lohatepanont, M., and C. Barnhart. "Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment." 2001. Transportation Science (June 2001).
21-22	Operations Recovery Overview of Operations Control Center Aircraft and Passenger Delays Flight Postponement and Cancellation Model The Role of Simulation	Bratu S., C. Barnhart. "Real Time Optimization Models to Recover Aircraft Schedules and Minimize Passenger Disruptions." MIT Working Paper, 2003. Jarrah, A., G. Yu, N. Krishnamurthy, and A. Rakshit. "A Decision Support Framework for Airline Flight Cancellations and Delays." Transportation Science 27, 3 (1993). Thengvall, B., Gang Y., and J. Bard. "Balancing User Preferences for Aircraft Schedule Recovery During Irregular Operations." IIE Transactions, 32 (1998): 181-193.
23-24	Robust Scheduling Robust Crew Scheduling Robust Aircraft Routing Degradable Schedule Design	Ageeva, Y. "Approaches to Incorporating Robustness into Airline Scheduling." Master's Thesis, Massachusetts Institute of Technology, 2000. Chebalov, S., and D. Klabjan. "Robust Airline Crew Scheduling: Move-up Crews." Proceedings of the 2002 NSF Design, Service, and Manufacturing Grantees and Research Conference, 2002. Kang, L. S., and J. P. Clarke. "Degradable Airline Scheduling." Working paper, Operations Research Center, Massachusetts Institute of Technology, 2002. Klabjan, D., A. J. Shaefer, E. L. Johnson, and G. L. Nemhauser. "Robust Airlines Crew Scheduling." White papers and reports series, the Logistics Institute, Georgia Institute of Technology, 2002. Rosenberger, J. M., E. L. Johnson, and G. L. Nemhauser. "A Robust Assignment Model with Hub Isolation and Short Cycles." White papers and reports series, the Logistics Institute, Georgia Institute of Technology, 2001. Schaefer, A. J., E. L. Johnson, A. J. Kleywegt, and G. L. Nemhauser. "Airline Crew Scheduling Under Uncertainty." White papers and reports series series, the Logistics Institute, Georgia Institute of Technology, 2001. Yen, J. W., and J. R. Birge. "A Stochastic Programming Approach to the Airline Crew Scheduling Problem." Submitted to Operations Research, 2001. Lan et al. Handout
25-26	Project Presentations and Reports