Improving Airlift Schedules with Algorithms

Splitting complex problems into parts simplifies and greatly speeds the task

Efficiency is an organizing principle in our everyday lives (however unconscious its pursuit may be). We’ll precariously juggle five plates of food from the kitchen to the living room just to save a trip. The more persnickety among us will even arrange folded laundry in the order of the rooms we walk past just to save the time it would take to retrace our steps.

The men and women working for the United States Transportation Command, or USTRANSCOM, perform the same type of optimization tasks in their daily work but on a much larger, more complex and financially consequential scale.

USTRANSCOM is responsible for planning and executing the transportation of U.S. military personnel and cargo by air, land and sea. While we’re performing amazing feats like balancing a plate of chicken wings in our elbow so that we don’t miss kickoff, they’re configuring the right mix of military personnel and cargo per plane to maximize use of space while also developing pickup and drop-off routes to minimize delays in getting time-sensitive, mission-critical deliveries to bases.

Depending on the type of aircraft, airlift missions can cost between $9,000 and $12,000 per flying hour so every minute of travel time that planning can trim pays off handsomely for the government and taxpayers.

Optimization Amid Complexity

In a paper published in Transportation Science, MIT’s Dimitris Bertsimas and Allison Chang, UCLA Anderson’s Velibor V. Mišić and the University of North Carolina’s Nishanth Mundru develop a methodology to improve the design of USTRANSCOM’s airlift schedules. Their automated approach improves efficiency by minimizing overall aircraft flight time in comparison with USTRANSCOM’s current (more manual and ad hoc) approach. With a simulated dataset, this improvement was 10%, on average.

Designing flight schedules to transport personnel and cargo is a case study in complexity.

Schedulers must choose among different aircraft to use and design multileg flight routes that have an enormous number of possibilities. Schedulers also have to accommodate for constraints that include:

• various plane weight capacities
• various sized pickup and drop-off loads
• crew rest requirements
• time window requirements for deliveries

Missing a time window can negatively impact missions dependent on the cargo and on personnel deliveries.

Computing every combination of variables to create schedules that would keep the aircraft in the air for the absolute least amount of time and meet all of the constraints can take anywhere from hours to years — depending on the number of variables and constraints involved. Missions would already be over before USTRANSCOM could even plan flight deliveries this way.

Avoiding the Pursuit of Perfection

The researchers meet the challenge by breaking it down into smaller, more manageable pieces. First, they optimize the assignment of cargo, personnel and the pickups and drop-offs to each aircraft. Then, they optimize the order of the pickups and drop-offs. This breaks the overall problem into simpler problems that can be solved independently.

The use of algorithms that employ approximations enables the researchers to solve the problem faster. These algorithms don’t give a perfect solution but, instead, quickly find a sufficient solution — think of it as an informed estimate.

They make an initial assignment of requirements (personnel, cargo and a series of pickup and drop-off locations) to each aircraft with an algorithm that ensures all constraints are met. They then improve those assignments with a second algorithm that tweaks the solution by adding or deleting a requirement (e.g., adding a new pickup location). Deleted requirements are added to other planes. The algorithm removes solutions that are no longer within the constraints after a tweak and keeps a change if it improves the overall time. This repeats until the solution no longer improves.

The final step of their approach addresses the order of the routes. This algorithm starts with a subset of the data and removes variables that do not improve the overall result and adds those that do. Using subsets enables the method to handle big data without running out of memory.

The researchers tested the performance of their method on a simulated dataset and a planning dataset provided by USTRANSCOM and compared their results with those realized using USTRANSCOM‘s current method. Their method reduced average aircraft usage time by 8% to 12% with the simulated dataset and 16% to 40% when run on USTRANSCOM’s more advanced internal planning dataset.