Rethinking Flight Schedules for the Post-Pandemic World

By Vikrant Vaze

The ongoing COVID-19 pandemic has had severe debilitating effects on the travel industry, with air transportation in particular feeling the pandemic’s onslaught. After a precipitous drop in air travel during the early phases of the pandemic, demand is finally showing some signs of recovery. However, industry experts and academic researchers predict major disruptions and transformations in a post-pandemic world, perhaps including increased hygienic operating procedures for passenger and crew safety and reconfigured aircraft seating to allow for social distancing. 

Early signs also indicate a strong possibility of three additional lasting effects: significant rethinking of aircraft fleets by the airlines themselves; major redesign of flight networks and schedules; and a dramatic, long-term shift in passenger travel demand patterns, which may necessitate the two preceding effects. These modifications may lead travelers and the industry to wonder whether financially sustainable airlines will continue to offer convenient and affordable long-distance travel options in a post-pandemic world.

Just before the pandemic, I co-authored a paper in Transportation Science in which my collaborators and I investigated whether it would be possible to design—from scratch—profitable flight schedules that align well with passenger preferences. Flight schedule design refers to the decisions surrounding how many airplanes of each type (e.g. Boeing 737, Airbus 320, etc.) will depart and arrive at which airports, and at what times. We believe our research on this matter is applicable in a post-pandemic world as well.

While conducting this study, my co-authors and I immediately encountered two major challenges. First, the sheer size of the number of possible flight schedules, as well as the number of mandatory rules, is stunningly large. Consider for a moment a relatively small airline with less than 400 flights per day (as opposed to the largest US airlines, which operate thousands of flights daily). Even for such a “small” airline, we observed over 45 million decisions that one had to make while following nearly 75 million rules! The number of possible flight schedules from which to choose had more than 1 million digits, so identifying the best flight schedule was akin to picking a very small needle from a gargantuan haystack.

Luckily, operations researchers and computer scientists have developed excellent algorithms over the past several decades to handle this type of large-scale optimization problem. These ideas are collectively called mixed-integer linear optimization (MILO) methods, and they are known to work well for mathematical problems that are similar to our flight scheduling challenge.

Alas, we then faced yet another issue. Most of these algorithms assume that the relationships between variables are linear. Unfortunately, as many of us know quite well, people’s choices and preferences are often far from linear or simple. In fact, the well-accepted models of passenger choice are nonlinear. Therefore, if we really wanted to align flight schedules with passenger preferences, we could not directly use any of these existing algorithms.

So we set out to solve these two problems sequentially. We first observed that some researchers in a related field—revenue management, which focuses on determining ticket prices—had faced a similar problem in that they needed to convert nonlinear passenger choice models into linear relationships. They did this successfully using a clever, though approximate, technique, and we quickly realized that we could borrow and adopt this idea to fit our own needs.

This was an exciting step because our problem was suddenly linear, meaning that we could use already-known MILO algorithms to solve it. If only life were that simple! We promptly discovered that even after running these algorithms on very fast computers for 48 hours, the resulting solution was not very good, and definitely not our best.

We decided to start thinking outside of the box. Could we be missing something obvious? Couldn’t we use common sense and conventional wisdom to break down the problem in some intelligent way? After all, we reasoned that airline schedule designers certainly do not waste time evaluating obviously weird schedules. For example, it wouldn’t make sense to schedule four flights for departure from the same airport within an hour, and none for the rest of the day. We thus concluded that a better schedule would distribute departure times more evenly throughout the day. 

Inspired by this thought and other similar ideas, we divided our hopelessly complicated optimization problem into multiple phases. We identified the broad time windows in which a particular flight should be scheduled for each phase; subsequent phases of our approach progressively narrowed the width of these windows. In essence, we first optimized the number of flights departing in the morning versus the afternoon or evening, and then determined the appropriate number of flights for each hour of the day, and so forth.

Voila! Arming the algorithms with industry common sense seemed to do the trick! We had found the breakthrough we needed; our multi-phase approach, combined with a few other computational tricks, enabled us to solve the problem much more quickly and efficiently. Instead of yielding a bad solution after 48 hours, we were able to obtain a solution within just two hours with up to 40 percent higher profits. 

We were now ready to conquer the flight network and schedule design challenges. First, we showed that our new approach outperformed actual airline schedules—as well as all known scheduling approaches in scientific literature—primarily due to a dramatic increase in the number of connection opportunities and the resulting number of connecting passengers. Our schedules aligned each flight’s timetable with nonstop passenger demand patterns, then coordinated all timetables across multiple segments to enhance connection opportunities.

Looking beyond flight scheduling, we found that such techniques are also helpful when answering many seemingly unrelated questions, such as “How useful it is for two airlines to merge with each other?” Or “How should airlines price tickets?” These techniques will likely be particularly relevant to airlines—many of which have already started rethinking their corporate strategy, flight networks, and pricing structures—in a post-pandemic world. Our biggest takeaway from this study is that challenging decision-making problems sometimes require a combination of mathematical and algorithmic knowhow, along with good ol’ common sense. Airlines will likely need a lot of both if they plan to keep flights accessible, affordable, and profitable after COVID-19.

Vikrant Vaze is the Stata Family Career Development Associate Professor at Thayer School of Engineering at Dartmouth College. He is interested in developing optimization, game theory, and analytics approaches for improving large-scale complex systems, such as transportation and healthcare. He holds two master’s degrees and a Ph.D. from the Massachusetts Institute of Technology in transportation and operations research, and a bachelor’s degree in civil engineering from the Indian Institute of Technology in Mumbai.