Applying the Multiple Multidimensional Knapsack Assignment Problem to a Cargo Allocation and Transportation Problem with Stochastic Demand
Date of Award
Master of Science in Operations Research
Department of Operational Sciences
Thomas P. Talafuse, PhD
Jeremy D. Jordan, PhD
The US military relies on airlift to not only deploy and sustain U.S. armed forces anywhere in the world but also to rapidly mobilize humanitarian efforts and supplies. Operations already impacted by the limited capacity of aircraft also fall prey to dynamic requirements and differing priorities of multiple global locations. A growing concern for the modern military budget is how to provide airlift functions expediently and economically while mitigating the costs of shortfalls and overages. Utilizing fiscal year 2017-2018 cargo data published by the 618th Air Operations Center and modeling this problem as a multiple multidimensional knapsack assignment problem (MMKAP), this work investigates how categorical assumptions about demand affect aircraft allocation and assesses the economic penalties associated with shorting or exceeding demand in the event of mis-estimation given a stochastic demand. This work starts with the general formulation of a new variant of the MMKAP and applies the MMKAP to a notional military airlift example with two supply, two demand nodes, two item types, and three aircraft types. After a deterministic solution is found, the effects of a stochastic demand are explored using different cost models and random draws from distribution functions based on reported cargo shipment data. This research concludes that there are levels at which demand expectations can be set to mitigate economic penalties given a fixed cost penalty and a variable cost penalty.
DTIC Accession Number
Maus, Jocelin S., "Applying the Multiple Multidimensional Knapsack Assignment Problem to a Cargo Allocation and Transportation Problem with Stochastic Demand" (2019). Theses and Dissertations. 2309.