A NONLINEAR INTEGER PROGRAMMING FORMULATION FOR THE AIRLIFT LOADING PROBLEM WITH INSUFFICIENT AIRCRAFT

Abstract

The Airlift Loading Problem with Insufficient Aircraft (ALPIA) is frequently faced by members of the United States Department of Defense when conducting airlift missions. The ALPIA is a combination of knapsack, assignment, and packing problems; items are selected for shipment based on a utility measure, then assigned to pallets which will be loaded into an aircraft in a specific pallet position. These pallets are then packed in a manner to optimize both the pallet and aircraft characteristics, such as item utility, aircraft and pallet utilization, pallet center of gravity, aircraft center of balance, etc. Since not all items have the same destination, it is necessary to perform the packing in an intelligent fashion to ensure ease of unpacking at destination. This paper formulates the ALPIA as an integer programming problem which allows items to be stably packed onto pallets with any specified orientation (i.e., while considering any "this side up" constraints). Rather than addressing the knapsack, assignment, and packing problems separately in a hierarchical manner, this formulation simultaneously accounts for each of these problems.