Flight routes
| Linear Programming | |
|---|---|
 | |
| MATH340 | |
| Section: | 921 |
| Instructor: | Tali Pinksky |
| Email: | tali@math.ubc.ca |
| Office: | Math 229a |
| Office Hours: | Wed 1-2 pm or by appointment |
| Class Schedule: | Tue-Thu-Fri 2-4 pm, Wed 2-3 pm |
| Classroom: | Math Annex 1100 |
| Important Course Pages | |
| Resources | |
| Assignments | |
| Discussion | |
| Projects | |
This is a classical application of designing flight routes- where should a flight company invest in direct flights and where to have a connection, which aircrafts should be used in what frequency atc. All major airlines use linear programming for these, as well as for pricing and crew scheduling problems.
Here is a nice toy model, and here is an application in an actual example.
Your first goal here would be to formulate what exactly the problem is and how does that translate to a linear programming problem, and you will probably compute a larger model using an appropriate software by the end of the term. Here's a relevant quote:
"Scheduling Planes at Delta Airlines with LP: It has been said that an airline seat is the most perishable commodity in the world. Each time an airliner takes off with an empty seat, a revenue opportunity is lost forever. For Delta Airlines, which flies over 2,500 domestic flight legs per day using about 450 aircraft of 10 different mod- els, its schedule is the very heartbeat of the airline. One flight leg for Delta might consist of a Boeing 757 jet assigned to fly at 6:21 A.M. from Atlanta to arrive in Boston at 8:45 A.M. Delta’s problem, like that of every competitor, is to match airplanes such as 747s, 757s, or 767s to flight legs such as Atlanta–Boston and to fill seats with paying passengers. Recent advances in linear pro- gramming algorithms and computer hardware have made it possible to solve optimization problems of this scope for the first time. Delta calls its huge LP model “Coldstart” and runs the model every day. Delta is the first airline to solve a problem of this scope. The typical size of a daily Coldstart model is about 40,000 constraints and 60,000 variables. The constraints include aircraft availability, balancing arrivals and departures at airports, aircraft maintenance needs, and so on. Coldstart’s objective is to minimize a combination of operating costs and lost passenger revenue, called “spill costs.” The savings from the model have been phenomenal, at $220,000 per day over Delta’s earlier schedule planning tool, which was nicknamed “Warmstart.” Delta saves $300 million per year through this use of linear programming." Sources: Interfaces (September–October, 1999): 123–131; Interfaces (January–February 1994): 104–120; and OR/MS Today (August 1995): 14–15.
Teams
Group 1: Thomas Roehrl, Henry Ye, Zoe Ren, Natalie So, Ruicong (Tony) Xu
Group 2: Ian Yihang Zhu, Ardy Ferguson, Jordan Bannister, Mauricio Valdivieso