The Airlift Planning Problem
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 ass...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129699 |
| _version_ | 1826194299515043840 |
|---|---|
| author | Bertsimas, Dimitris J Chang, Allison Mundru, Nishanth. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bertsimas, Dimitris J Chang, Allison Mundru, Nishanth. |
| author_sort | Bertsimas, Dimitris J |
| collection | MIT |
| description | 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 highquality 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. |
| first_indexed | 2024-09-23T09:53:54Z |
| format | Article |
| id | mit-1721.1/129699 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:53:54Z |
| publishDate | 2021 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1296992022-09-30T17:33:18Z The Airlift Planning Problem Bertsimas, Dimitris J Chang, Allison Mundru, Nishanth. Sloan School of Management Lincoln Laboratory Massachusetts Institute of Technology. Operations Research Center 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 highquality 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. 2021-02-08T14:22:45Z 2021-02-08T14:22:45Z 2019-05 2021-02-05T17:52:42Z Article http://purl.org/eprint/type/JournalArticle 0041-1655 https://hdl.handle.net/1721.1/129699 Bertsimas, Dimitris et al. “The Airlift Planning Problem.” Transportation Science, 53, 3 (May 2019): 623-916 © 2019 The Author(s) en 10.1287/TRSC.2018.0847 Transportation Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) Other repository |
| spellingShingle | Bertsimas, Dimitris J Chang, Allison Mundru, Nishanth. The Airlift Planning Problem |
| title | The Airlift Planning Problem |
| title_full | The Airlift Planning Problem |
| title_fullStr | The Airlift Planning Problem |
| title_full_unstemmed | The Airlift Planning Problem |
| title_short | The Airlift Planning Problem |
| title_sort | airlift planning problem |
| url | https://hdl.handle.net/1721.1/129699 |
| work_keys_str_mv | AT bertsimasdimitrisj theairliftplanningproblem AT changallison theairliftplanningproblem AT mundrunishanth theairliftplanningproblem AT bertsimasdimitrisj airliftplanningproblem AT changallison airliftplanningproblem AT mundrunishanth airliftplanningproblem |