Accession Number : AD1030395

Title :   The Airlift Planning Problem

Descriptive Note : OSTP Journal Article


Personal Author(s) : Chang,Allison A ; Bertsimas,Dimitris ; Misic,Velibor V ; Mundru,Nishanth

Full Text :

Report Date : 02 Jan 2017

Pagination or Media Count : 30

Abstract : The United States Transportation Command (USTRANSCOM) is responsible for planning and executing the transportation of United States military personnel and cargo by air, land and sea. The airlift planning problem faced by the air component of USTRANSCOM is to decide how requirements (passengers and cargo) will be assigned to the available aircraft fleet and the sequence of pickups and dropos that each aircraft will perform in order to ensure that the requirements are delivered with minimal delay and with maximum utilization of the available aircraft. This problem is of significant interest to USTRANSCOM due to the highly time-sensitive nature of the requirements that are typically designated for delivery by airlift, as well as the very high cost of air-lift operations. At the same time, the airlift planning problem is extremely difficult to solve due to the combinatorial nature of the problem and the numerous constraints present in the problem (such as restrictions on weight and crew rest requirements). In this paper, we propose an approach for solving the airlift planning problem faced by USTRANSCOM based on modern, large-scale optimization. Our approach relies on solving a large-scale mixed-integer optimization model that disentangles the assignment decision (which aircraft will pickup and deliver which requirement) from the sequencing decision (in what order the aircraft will pickup and deliver its assigned requirements), using a combination of heuristics and column generation. Through computational experiments with both simulated and real data, we show that our approach leads to high-quality solutions for realistic instances (e.g., 100 aircraft and 100 requirements)within operationally feasible time frames. Compared to a baseline approach that emulates current practice at USTRANSCOM, our approach leads to reductions in total delay and aircraft time of 8 to 12% in simulated data instances and 16 to 40% in real data instances.

Descriptors :   united states transportation command , algorithms , transport aircraft , air traffic , aircrafts , mathematical programming , operations research , cargo aircraft , airlift operations

Subject Categories : Military Operations, Strategy and Tactics
      Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE