Abstract
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.
References
Air Mobility Command (2004). AMC Affiliation Workbook 36-101 Vol 2 Airlift Planners Course, October 1.
Anderson DL (2008). AMC Airlift Data from GATES. (RL Nance, Interviewer), September 15.
Brenneman WA and Myers WR (2003). Robust parameter design with categorical noise variables. J Qual Tech 35: 335–341.
Chocolaad CA (1998). Solving geometric knapsack problems using tabu search heuristics. Master's thesis, Air Force Institute of Technology: Wright-Patterson AFB, OH.
Garey MR and Johnson DS (1979). Computers and Intractability. W.H. Freeman and Company: New York.
Glover F (1989). Tabu Search—Part I. Opns Res Soc Am 1: 190–207.
Harwig JM, Barnes JW and Moore JT (2006). An adaptive tabu search approach for 2-dimensional orthogonal packing problems. Mil Opns Res 11 (2): 5–26.
Heidelberg KR, Parnell GS and Ames IV JE (1998). Automated air load planning. Nav Res Log 45: 751–768.
Herbison LD (2008). Air Mobility Command A9 Deptuty Director. (MR Nance, Interviewer), September 16.
Hiremath CS and Hill RR (2007). New greedy heuristic for the multiple-choice multi-dimensional knapsack problem. Int J Opl Res 2: 495–511.
Misevicius A (2004). Using iterated tabu search for the traveling salesman problem. Informacines Technologijos IR Valdymas 32 (3): 29–40.
Ng KY (1992). A multicriteria optimization approach to aircraft loading. Opns Res 40: 1200–1205.
Roesener AG, Barnes JW, Moore JT and Van Veldhuizen D (2010). An advanced tabu search approach to the airlift loading problem. Mil Opns Res J 15 (1): 5–29.
Romaine JM (1999). Solving the multidimensional multiple knapsack problem with packing constraints using tabu search. Master's thesis, Air Force Institute of Technology: Wright-Patterson AFB, OH.
USTRANSCOM (2007, August). www.ustranscom.mil, http://www.transcom.mil/j5/pt/dtrpart3/dtr_part_iii_app_i.pdf, accessed 11 July 2008.
Wakefield SM (2008). Chief C-5 Loadmaster, Headquarters Air Mobility Command. (RL Nance, Interviewer), September 15.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nance, R., Roesener, A. & Moore, J. An advanced tabu search for solving the mixed payload airlift loading problem. J Oper Res Soc 62, 337–347 (2011). https://doi.org/10.1057/jors.2010.119
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.119