An advanced tabu search for solving the mixed payload airlift loading problem

This article describes a new, two-dimensional bin packing algorithm that feasibly loads a set of cargo items on a minimal set of airlift aircraft. The problem under consideration is called the Mixed Payload Airlift Loading Problem (MPALP). The heuristic algorithm, called the Mixed Payload Airlift Loading Problem Tabu Search (MPALPTS), surpasses previous research conducted in this area because, in addition to pure pallet cargo loads, MPALPTS can accommodate rolling stock cargo (ie tanks, trucks, HMMMVs, etc) while still maintaining feasibility. To demonstrate its effectiveness, the load plans generated by MPALPTS are directly compared to those generated by the Automated Air Load Planning Software (AALPS) for a given cargo set; AALPS is the load planning software currently mandated for use in all Department of Defense load planning. While more time consuming than AALPS, MPALPTS required the same or fewer aircraft than AALPS in all test scenarios.