Crew Pairing Optimization

WB33.1 Daily Consistency in Weekly Crew Pairing

• Diego Klabjan; Georgia Institute of Technology, Sch. of ISyE, 765 Ferst Dr., Atlanta, GA 30332-0205; diego@akula.isye.gatech.edu
• Ellis L. Johnson; Georgia Institute of Technology, Sch. of ISyE, Atlanta, GA 30332-0205; ejohnson@isye.gatech.edu
• George L. Nemhauser; Georgia Institute of Technology, Sch. of ISyE, 765 Ferst Dr., Atlanta, GA 30332-0205; gnemhaus@isye.gatech.edu
• Pamela H. Vance; Auburn University, Dept. of IE, 1364 Nerine Cir., Auburn, AL 30338; pvance@eng.auburn.edu

We present a new model for the weekly airline crew scheduling problem that captures daily regularity in a weekly schedule. The model results in an IP having a huge number of variables and rows. We present techniques for solving the model, some of which can be applied to general large-scale IPs.

WB33.2 Crew Scheduling Considering Operational Effects

• Andrew Schaefer; Georgia Institute of Technology, Sch. of ISyE, Atlanta, GA 30332-0205; schaefer@akula.isye.gatech.edu
• Ellis L. Johnson; Georgia Institute of Technology, Sch. of ISyE, Atlanta, GA 30332-0205; ejohnson@isye.gatech.edu
• Anton Kleywegt; Georgia Institute of Technology, Sch. of ISyE, Atlanta, GA 30332-0205; anton@isye.gatech.edu
• George L. Nemhauser; Georgia Institute of Technology, Sch. of ISyE, 765 Ferst Dr., Atlanta, GA 30332-0205; gnemhaus@isye.gatech.edu

We propose a crew scheduling model which considers possible disruptions, and develop schedules to reduce crew costs incurred during operations. The model estimates network and recovery effects through a simulation. We present preliminary computational results from a large domestic fleet.

WB33.3 Why Primary Line Construction Is Difficult

• Eric Gelman; United Airlines Corporate R&D, 1200 Algonquin Rd., Elk Grove Village, IL 60173; eric.gelman@ual.com
• Yanqi Xu; United Airlines, Corporate R&D WHQKB, 1200 E. Algonquin Rd., Elk Grove Village, IL 60007; xu@ual.com
• Connie Chen; United Airlines, Corporate R&D WHQKB, 1200 E Algonquin Rd., Elk Grove Village, IL 60007; connie.chen@ual.com
• Balan Chidambaram; United Airlines, Corporate R&D WHQKB, 1200 E. Algonquin Rd., Elk Grove Village, IL 60007; balan.chidambaram@ual.com
• Zaili Zhang; United Airlines, Corporate R&D WHQKB, 1200 E Algonquin Rd., Elk Grove Village, IL 60007; zaili.zhang@ual.com

Primary line construction has been driven mostly by 2 factors: efficiency (monthly crew utilization) and quality (purity and/or repeatability of monthly flying and/or days off patterns). We will discuss results produced by UAL's recently developed and deployed system - AFLYER. Related technical topics involve column generation/shortest path and LP.