Like many people, I’ve been fascinated by great unsolved problems. Fermat’s Last Theorem? Simple, elegant, easy-to-state, but it eluded solution for over 350 years. In fact, Fermat himself claimed to have solved it, but supposedly only the lack of margin space prevented him from articulating it. It was first solved just 25 years ago.
Expressing pi to more and more digits is another unsolved problem. Of course, piis a limitless series of non-repeating numbers and available technology limits how much we can know about this number. Recently, piwas expressed to over31 trillion digits. I can’t imagine the technology necessary to do that nor what a trillion digits actually looks like. But there’s still more digits to go.
The airline scheduling problem
The airline scheduling problem is another great unsolved problem. Simply stated, airline scheduling has the objective of finding the most profitable schedule that is reliable and satisfies all operational constraints. The decision space to this problem is immense:airlines can choose any combination of where to fly, when to fly, and what to fly. For a large airline, they can offer more possible schedules than there are atoms in the universe. Expressing profitability is complex and highly non-linear with many interacting effects. And there are many different dimensions of operational constraints that must be respected. This problem has been and still is too difficult to completely solve.
I’ve been thinking about and working on this problem for over 30 years. I blush to admit it now, but when I first started on this problem, I actually thought that a complete solution to the problem would soon be possible. I had an image of a keyboard with one button on it called “schedule”. At the appropriate time, all the scheduler had to do was press this button and the perfect schedule would shortly pop out. At that point, everyone would just applaud.
Of course, it never worked out this way. Instead, we’ve made slow but steady progress on approximating the solution to this problem over the years. We’ve solved the problem of fleet assignment, or optimally determining the appropriate aircraft type to be assigned to each flight. We’ve been able to estimate the profitability of a proposed schedule with more accuracy. We’ve gathered more and betterdata. And we decomposed the larger problem into smaller sub problems and solved those problems. We’ve gotten better over the years!
Getting closer to the “holy grail”
By working this way, I’ve gained a greater appreciation for the role of schedulers and planners at airlines. These people work on this difficult problem under immense time pressure, with incomplete data, and under the scrutiny of many people at the airline. In the airline business, the schedule is the core product and everyone is interested in it. Schedulers and planners have found ways to develop their schedule acceptably close to an unachievable ideal by using the skills of their people, some interesting tools, a diverse set of data, and some pretty creative business processes.
But the problem still hasn’t been solved. This problem is a kind of “holy grail”, but unlike many other great unsolved problems, being able to determine the optimal airline schedule will generate huge commercial benefits. The airlines that do this should expect many margin points of improvement in their business. It would help them gain a tremendous competitive advantage and unlock latent profit potential.
So this problem is still important. Which is why some recent breakthroughs in solving this problem are really exciting to me. In fact, there are seven breakthroughs that collectively have given us a big leap forward in network planning technology. We’ve chipped away at this problem for many years and, all of a sudden, have made a lot of progress. This result shouldn’t be surprising – success in most human endeavors doesn’t happen smoothly, but instead comes in major, “step-function” jumps. We’re now in the middle of one such jump.
So, we’ve written a paper!
It was with a sense of appreciation for this moment that I was delighted to collaborate with my teammates at Amadeus andOptym towrite a paper introducing these breakthroughs. In order to give these breakthroughs some context, we defined the problem itself, discussed how airlines solve it today, and then analyzed the weaknesses in how it’s solved today. Of course, we don’t mean to be critical in discussing these weaknesses, I think most airlines would agree with our assessment of how the problem is solved today. In my experience of working with airlines around the world, I’ve found airline schedulers and planners to be hungry for new approaches and technologyinnovation in this area.
Adding further context, we also discussed the key trends such as greater IT processing power and new data that have led to the breakthroughs in question. These breakthroughs didn’t happen in a vacuum, but instead are the result of innovation in other areas. To appreciate the nature of the breakthroughs, I think it’s helpful to have that perspective.
We then spent most of the paper in reviewing the seven breakthroughs themselves. We wanted to give our readers a sense of how the breakthroughs work and why they contribute towards a solution to this great problem. All seven of them are important and all seven are worthy of attention.
Of course, there’s a limit to the level of detail we can provide in a paper like this one. To anyone who wants to understand more about the breakthroughs, or how they could be applied at their airline, I urge them to talk to people at Amadeus and Optym, who will be delighted to discuss these points in greater depth.
We feel the industry is collectively moving in this direction – airlines, ourselves, our partners, data providers, etc. Everyone plays a role in pushing boundaries forward and creating innovation in network planning. Still, the great unsolved problem hasn’t been solved. We’ve made progress, but there’s still more value to be unlocked. At Amadeus and Optym, we’ll continue to push state-of-the-art technology forward and invite any and all interested parties to join us.
I invite you to download a copy of the Breakthroughs in Airline Scheduling: Building Better Schedules report here.
TO TOP