Synchronized Scheduling Case Study - Part 1

Synopsis 
When a low-cost airline (LCA) entered a short-haul aviation market many, many years ago, a legacy airline carrier (LEG) decided to compete with LCA on its own turf by matching the LCA's fare, frequency and super-quick aircraft turn-around times on ground ('turns' for short). This required a high degree of coordination between LEG's in-flight crews (pilots and flight-attendants), ground-crew, airplane maintenance planners, and the airline schedulers (including their scheduling optimization system). In particular, the utilization of the pilots and the flight-attendants had to be maximized. The challenge however was that all these different resources were part of separate organizational structures and were governed by different contractual rules, and the LEG idea eventually turned out to be cost-prohibitive and unreliable due to poor synchronization of resources.  On the other hand, the Operations Research (O. R) team built a specialized scheduling system for LEG (far ahead of the literature available at that time) that would've achieved the needful. Unfortunately, the silo-ed organizational structure hindered adoption.  Result:  Unlike the legendary revenue optimization contest where the legacy carrier triumphed, the tables were turned here, and the LCA flourished. The low-cost LEG idea was resuscitated many years later in a different context and market, and did a better job using the lessons learned from this early setback. In the next few posts, we will compare the two approaches used to synchronize these resource scheduling tasks and summarize the lessons learned.

Airline Scheduling Basics
Given an aircraft schedule, the resource planning is done sequentially in order of their profitability (or cost) to the airline. Thus:
LEG flight schedule → pilot schedule→ flight attendant schedule → aircraft maintenance routing

The cost-critical task here is the construction of "pairings" (or "strings" for aircraft), which denote partial (unassigned) solutions that represents partial tours of a resource. For LEG pilots (set of two persons), and FAs (set of three persons), this represents a tour in a time-space network that starts from a crew domicile (a small subset of airports in the LAC schedule), traverses a bunch of different airports over 1-5 duty days with intervening periods of rest known as layovers, before returning to the home domicile, while satisfying a myriad of contractual and FAA rules for work hours, rest time, etc. In short, the cost and constraints that determine each pairing is an extremely complicated nonlinear, non-smooth, non-convex, nonplussing mixture of on-duty + rest + reliability + crew work life balance + other path-dependent factors. 

Good quality pairings can be created using a dynamic column-generation procedure. A column here represents a pairing, and during an optimization run, thousands of pairings are generated and selected from among the many trillions of possibilities using a "branch and price" scheme. Eventually a subset of the generated columns are selected such that every flight in the time-space network is covered by exactly one pairing, and such that the total cost is minimized (where the actual 'cost' being optimized is a combination of a hundred-odd objective function components).

Note: An airline crew-pairing solver's set partitioning problem is arguably the easiest optimization model in the world to represent on paper:
{SPP: Minimize cx : Ax = 1, x binary, x ∈ X}

In contrast, the real-life computer code used to manage this simple model can easily run in the order of many hundred thousand lines (largely due to the complicated and detailed nature of X), with expensive parallel-processing machines, and an embarrassment of CPLEX licenses to match. Why? A small percentage point reduction in crew pairing cost (cx) can easily recover all these infrastructure costs and then some. Since crews get paid the max of planned and actual costs, these numbers are actual bottom-line savings. Furthermore, such scheduling tools can be mission-critical systems that run 365 days a year, requiring O.R product support staff to be on call like primary care doctors. 

Solution Approach
Downstream systems, and not of immediate interest to this post, combine these pairings into actual monthly schedules with pilot, first officer, and flight attendants assigned by solving yet another set-partitioning problem. Thus cost-effectively scheduling even a single resource requires a sophisticated solution approach. In those days, academic literature often contained interesting approaches that looked good on paper but proved to non-implementable because of the highly context-driven and data-driven nature of this problem that requires developers to pay careful attention to problem size, exploit special structures in SPP and X, and keep in mind certain carrier-specific objectives. On the other hand, interested readers can refer to this journal paper - the first one I read on the job. It is also the #1 cited INFORMS paper based on a recent ranking. Today, this portion of airline planning is typically outsourced to specialized airline crew-scheduling software vendors.

Pairings and Strings
A set of pilot pairings tell you, for any given LEG flight: the in-bound flight that the pilots arrived in, and the out-bound flight on which they will depart. Of course, if a LEG flight schedule is built with lots of tight turns (say 30 minutes or less) at an airport, then it makes sense from the point of view of operational reliability and cost, for the crews to stay with, and depart on the same airplane, assuming of course, that the aircraft routers will assign the same aircraft (tail number) to these flights. This is a resource synchronization rule: Keep crews and aircraft together to the extent possible while also keeping costs low and satisfying all contractual duty, rest, and maintenance rules.

The FA scheduling system can take pilot pairings as inputs to try and keep the FAs with the pilots. Unfortunately, since these crews have different operating hours and safety rules give the varying nature of their job descriptions, very often, pilots and FAs have to break up and depart on different flights. This is an operational nightmare when you are trying to work with tight turns to compete with LCA, and actual costs shoot up if you 'over-synchronize'. To make matters worse, the strings (partial aircraft maintenance routing solutions) also have to be tightly woven with crew pairings. It's a planners nightmare.  Believe it or not, LEG folks actually built much of these schedules separately ("legacy approach"), with each scheduler anticipating what the other person will do, often coordinating via phone-calls in this multi-person game. Result: an expensive and sometimes operationally brittle schedule that increased operational costs and ate up some customer goodwill, which eventually resulted in the plug being pulled. In the next part, we'll see how LEG's OR team analyzed this problem.

to be continued .....