Skip to main content
Log in

Loading aircraft for military operations

  • Case-oriented Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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.

    Google Scholar 

  • Rappoport HK, Levy LS, Golden BL and Toussaint KJ (1992). A planning heuristic for military airlift. Interfaces 23(3): 73–87.

    Article  Google Scholar 

  • Rappoport HK, Levy LS and Toussaint KJ (1994). A transportation problem formulation for the MAC airlift planning problem. Ann Opns Res 50: 505–523.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Solanki RS and Southworth F (1991). An execution planning algorithm for military airlift. Interfaces 21(4): 121–131.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Sweeney PE and Paternoster ER (1992). Cutting and packing problems: a categorized, application-oriented research bibliography. J Opl Res Soc 43: 691–706.

    Article  Google Scholar 

  • Gehring H, Menshner K and Meyer M (1990). A computer-based heuristic for packing pooled shipment containers. Eur J Opl Res 44: 277–288.

    Article  Google Scholar 

  • Bischoff EE and Ratcliff MSW (1995). Issues in the development of approaches to container loading. OMEGA 23: 377–390.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Cochard DD and Yost KA (1985). Improving utilization of air force cargo aircraft. Interfaces 15(1): 53–68.

    Article  Google Scholar 

  • Larsen O and Mikkelsen G (1980). An interactive system for the loading of cargo aircraft. Eur J Opl Res 4: 367–373.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Tsang E (1993). Foundations of Constraint Satisfaction. Academic Press: New York.

    Google Scholar 

  • Christofides N and Whitlock C (1977). An algorithm for two-dimensional cutting problems. Ops Res 25: 30–44.

    Article  Google Scholar 

  • Martello S and Toth P (1990). Knapsack Problems. Wiley: New York.

    Google Scholar 

  • Chvatal V (1979). A greedy heuristic for the set-covering problem. Math Opns Res 4: 233–235.

    Article  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to N Jussien.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2601551

Keywords

Navigation