Aero-Astro Magazine Highlight

Practical algoritihms for air transportation systems

By Hamsa Balakrishnan

The challenge lies in bridging the gap between theory and practice, and experience has taught us that overlooked operational issues often make theoretically sound ideas impractical.

Hamsa Balakrishnan's research is developing ways for next generation air transportation systems to run well in the face of increasing demands and external uncertainties.
(William Litant photograph)

These are truly exciting times for the air transport industry. The air transportation system, which began in the 1920s as a means of transporting passengers and mail among a handful of airports in the United States, has evolved into a large, complex system that interacts with global and regional economies, and which transports more than 2.1 billion passengers and 39 million tons of freight per year between almost 50,000 airports around the world. The steady increases in both passenger and cargo flights have led to an increase in flight delays, both in terms of the number of flights incurring delays and the total amounts of delay incurred, causing immense frustration to passengers and businesses. Moreover, with skyrocketing fuel prices, efficient air traffic operation has become more important than ever.

The demand for air traffic in the United States is expected to increase two- or three-fold over the next 15 years. Similar growth in demand is expected in Europe, while emerging markets such as China, India and the Middle East are expected to see a much larger demand spurt. With increasing demand comes reduced robustness to external conditions such as weather; for example, most of us have experienced flight delays flying from Boston to San Francisco because of weather in the Midwest.

My research aims to develop methods for next generation air transportation systems to ensure that they will run well in the face of increasing demands and external uncertainties. My students and I develop practical, implementable algorithms backed by sound methodologies that aim to avoid catastrophic delays, gridlock, and environmental damage. These topics are both intellectually challenging and affect the way we live and work; this combination greatly motivates me.

My interest in air traffic management began when I was working toward my Ph.D. at Stanford University. My dissertation developed surveillance algorithms for tracking aircraft trajectories and maintaining knowledge of their identities. That experience, a subsequent stint at the NASA Ames Research Center, and my research at MIT over the past year and a half have shown me how concepts from diverse fields such as aeronautics, systems engineering, operations research, computer science, and economics, when combined cleverly, can dramatically improve the world’s air transportation systems. In bringing together ideas from different fields to tackle fundamental air traffic challenges, my group collaborates with MIT, Lincoln Labs, and other groups.

Competition, uncertainty, environment impact

What do we want from the air transportation system? Clearly, efficiency (accommodating as many flights as necessary with limited delays), robustness (avoiding situations in which unexpected weather in a small portion of the country results in widespread delays and rescheduling), and safety (minimizing the potential for accidents) are all of paramount importance. Achieving all these goals is difficult because of the size and complexity of the system. In addition to sheer size (31,000 flights a day in the United States alone), three important real-world issues must be dealt with: the presence of significant uncertainty, competition among the different stakeholders, and concerns regarding aviation’s environmental impact.

In abstract terms, my work develops techniques that enable the efficient allocation of airspace and airport resources. These allocations are used to determine, for thousands of flights, the best departure times, the speeds to fly at, the routes to take and the optimal landing times. A good solution must recognize that when a flight departs from San Francisco, the arrival conditions at the time it reaches Boston (which depend on convective weather conditions, turbulence, icing, visibility, surface winds, etc.) have significant weather- and traffic-related uncertainties associated with them. Excessively conservative decisions, such as letting flights take off only when we are sure that a storm has dissipated, may mean that no flights land in Boston for hours after the weather clears, thereby causing unnecessary delays. Conversely, overly aggressive scheduling may mean that flights get to their destination before the storm clears, expending large amounts of time and fuel in holding patterns, even getting diverted to other airports, causing severe inconvenience to both passengers and the airlines.

weather images

Forecast weather (left) when a flight is 10 minutes from the outermost circle, and the actual weather (right) that materialized along routes into Atlanta airport at two different times on a day with significant convective weather. The outermost and the innermost rings are respectively 75 km and 10 km from Atlanta (the center of the circles). The distance between two consecutive circles represents about five minutes flying time. The colors denote the severity of convective weather: pilots generally avoid flying through Level 3 or greater weather. In the first case shown here, while the route determined in the forecast was actually impacted by weather, there was a route (solid line, top right) with limited deviation from the initial route that did not pass through adverse weather. This means that flights scheduled along that path could continue with only a minor modification to the path suggested by the forecast. In contrast, in the case shown at the bottom, any path that could avoid the weather that materialized would have required significant deviation from the original route. The forecast routes are denoted by dotted lines in the observed weather maps.

These problems are not new, but my approach is different from previous research. Rather than treat each component of the system (e.g., route and schedule optimization, modeling weather uncertainty) in isolation, my methods bridge the gap among these different sub-problems by efficiently integrating information from various sub-problems into decision-making and robust optimization algorithms. The solutions to the sub-problems take the overarching system-level goals and context into account. For example, by comparing data from past aviation weather forecasts to the actual weather that materialized, we determine our ability to predict if a route will be blocked by a storm; using the stochastic weather models thus obtained, we can schedule traffic through the most viable routes in order to achieve robust operations. This approach avoids the pitfalls of prior efforts, which often resulted in robust route optimization algorithms that made invalid assumptions either about the uncertainty or about the information available in the weather forecasts.

Multiple stakeholders, competing interests

The presence of multiple stakeholders and competing interests is an interesting challenge. The objectives themselves may differ among stakeholders; for example, on a weather-impacted day at a congested airport, air traffic control may be interested in maximizing the rate at which aircraft arrive and depart (the throughput), the airlines may be interested in minimizing either fuel costs, or the total delays incurred by them, or the delay incurred by high-priority flights, while travelers may care about the delay per passenger or the number of missed connections. These objectives are not necessarily aligned; for example, the schedule that maximizes throughput may not be the fuel-optimal or delay-optimal schedule. My solution is to develop techniques that determine the tradeoffs among the different objectives to support traffic managers and airport operators in their decision-making.

Another aspect of this issue that I address is that of airline competition. Airlines are inherently self-interested entities that compete for congested airspace and airport resources. System-level planning decisions require cooperation from the airlines in areas such as flight schedules, and mechanical delay and cancellation reports. Airlines are likely to cooperate only if they believe that the system is equitable and if an attempt is made to accommodate their preferences. Therefore, using concepts from game theory and mechanism design, we develop equitable scheduling algorithms and techniques for resource allocation (and reallocation) that incentivize information-sharing and truthful reporting by the airlines.

Aviation is one of the fastest growing contributors in the developed world to greenhouse gas emissions. The projected increase in air traffic demand is likely to make this worse; for this reason, there is growing regulatory and societal pressure to mitigate aircraft noise and emissions. My research aims at incorporating environmental objectives (e.g., the fuel burn or carbon emissions) into the problem of scheduling both airspace and airport ground operations, and determining what the potential trade-offs may be with other objectives such as system efficiency. The challenge lies in bridging the gap between theory and practice, and experience has taught us that overlooked operational issues often make theoretically sound ideas impractical. A recent example of this is Virgin Atlantic airline’s widely publicized green initiative to potentially cut thousands of tons of carbon emissions by towing its Boeing 747s to the end of runways before departure: the program had to be suspended after Boeing determined that pulling the landing gear would seriously weaken it. My research investigates such potential operational barriers associated with current airport operations, including prevailing gate-use agreements and infrastructure constraints. In conjunction with such near-term efforts on operational improvements, I am also involved with research on reducing the environmental footprint of the airports of the future.

I believe that my research is an important step toward enabling safe, efficient, robust, and green air transportation. And that is ultimately what will make air travel fun once again for everyone!

Hamsa Balakrishnan is the T. Wilson Career Development Assistant Professor of Aeronautics and Astronautics and of Engineering Systems in the MIT Aeronautics and Astronautics Department. She received a B. Tech in Aerospace Engineering from the Indian Institute of Technology in 2000 and a Ph.D. in Aeronautics and Astronautics from Stanford University in 2006. Prior to joining MIT in January 2007, she was a researcher at the University of California, Santa Cruz and the Terminal-Area Air Traffic Management Research Branch of NASA Ames Research Center. Her research interests include algorithms for the scheduling and routing of air traffic, techniques for the collection and processing of air traffic data, and mechanisms for the allocation of airport and airspace resources. She may be reached at hamsa@mit.edu