The Airlift Planning Problem

Dimitris Bertsimas (), Allison Chang (), Velibor V. Mišić () and Nishanth Mundru ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139; Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Allison Chang: Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02420
Velibor V. Mišić: Anderson School of Management, University of California, Los Angeles, Los Angeles, California 90095
Nishanth Mundru: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Transportation Science, 2019, vol. 53, issue 3, 773-773

Abstract: The U.S. Transportation Command (USTRANSCOM) is responsible for planning and executing the transportation of U.S. 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 drop-offs that each aircraft will perform 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 because of the highly time-sensitive nature of the requirements that are typically designated for delivery by airlift, as well as the very high cost of airlift operations. At the same time, the airlift planning problem is extremely difficult to solve because of the combinatorial nature of the problem and the numerous constraints present in the problem (such as weight restrictions 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 programming 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 a simulated data set and a planning data set provided by USTRANSCOM, 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 with a baseline approach that emulates current practice at USTRANSCOM, our approach leads to reductions in total delay and aircraft time of 8%–12% in simulated data instances and 16%–40% in USTRANSCOM’s planning instances.

Keywords: pickup and delivery with time windows; mixed-integer programming; column generation; local search; construction heuristics (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0847 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:3:p:773-795

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().