Abstract
In this paper, we describe an aircraft loading problem submitted by the French military agency (DGA) as part of a more general military airlift planning problem. It can be viewed as a kind of bi-dimensional bin-packing problem, with heterogeneous bins and several additional constraints. We introduce two-phase methods for solving this NP-hard problem. The first phase consists in building good initial solutions, thanks to two fast algorithms: a list-based heuristic and a loading pattern generation method. Both algorithms call a constraint-based subroutine, able to determine quickly if the items already loaded can be reshuffled to accommodate a new object. The second phase improves these preliminary solutions using local search techniques. Results obtained on real data sets are presented.
Similar content being viewed by others
References
Dyckhoff H, Scheithauer G and Terno J (1997). Cutting and packing. In: Dell'Amico M, Maffioli F and Martello S (eds.). Annotated Bibliographies in Combinatorial Optimization. Wiley: New York.
Rappoport HK, Levy LS, Golden BL and Toussaint KJ (1992). A planning heuristic for military airlift. Interfaces 23(3): 73–87.
Rappoport HK, Levy LS and Toussaint KJ (1994). A transportation problem formulation for the MAC airlift planning problem. Ann Opns Res 50: 505–523.
Rappoport HK, Levy LS, Golden BL and Feshbach DS (1991). Estimating loads of aircraft in planning for the military airlift command. Interfaces 21(4): 63–78.
Solanki RS and Southworth F (1991). An execution planning algorithm for military airlift. Interfaces 21(4): 121–131.
Hong JD and Chandra MJ (1990). A heuristic algorithm to minimize the number of crews allocated in an airlift operation. Comput Opns Res 17: 389–396.
Sweeney PE and Paternoster ER (1992). Cutting and packing problems: a categorized, application-oriented research bibliography. J Opl Res Soc 43: 691–706.
Gehring H, Menshner K and Meyer M (1990). A computer-based heuristic for packing pooled shipment containers. Eur J Opl Res 44: 277–288.
Bischoff EE and Ratcliff MSW (1995). Issues in the development of approaches to container loading. OMEGA 23: 377–390.
Vasko FJ, McNamara JA, Newhart DD and Wolf FE (1994). A practical solution to a cargo loading problem at Bethlehem Steel. J Opl Res Soc 45: 1285–1292.
Cochard DD and Yost KA (1985). Improving utilization of air force cargo aircraft. Interfaces 15(1): 53–68.
Larsen O and Mikkelsen G (1980). An interactive system for the loading of cargo aircraft. Eur J Opl Res 4: 367–373.
Chauny F, Ratsirahonana L and Savard G (2000). A model and column generation algorithm for the aircraft loading problem. Report G-2000-68, GERAD.
Liu D and Teng H (1999). An improved bl-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur J Opl Res 112: 413–420.
Tsang E (1993). Foundations of Constraint Satisfaction. Academic Press: New York.
Christofides N and Whitlock C (1977). An algorithm for two-dimensional cutting problems. Ops Res 25: 30–44.
Martello S and Toth P (1990). Knapsack Problems. Wiley: New York.
Chvatal V (1979). A greedy heuristic for the set-covering problem. Math Opns Res 4: 233–235.
Acknowledgements
We wish to thank Patrick Journée and Franck Ouary for their helpful comments in writing this paper. This work was partially supported by the French Délégation Générate pour l'Armement (DGA) under contract 98 1107A000.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guéret, C., Jussien, N., Lhomme, O. et al. Loading aircraft for military operations. J Oper Res Soc 54, 458–465 (2003). https://doi.org/10.1057/palgrave.jors.2601551
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2601551