Loading aircraft for military operations
- PDF / 152,909 Bytes
- 8 Pages / 595 x 794 pts Page_size
- 40 Downloads / 250 Views
r 2003 Operational Research Society Ltd. All rights reserved. 0160-5682/03 $25.00 www.palgrave-journals.com/jors
Loading aircraft for military operations C Gue´ret1,2, N Jussien*1, O Lhomme3, C Pavageau1 and C Prins4 1 ´ Ecole des Mines de Nantes, Nantes, France; 2IRCCyN—Institut de Recherche en Communications et Cyberne´tique de Nantes, Nantes, France; 3IPogSA, Valbonne, France; and 4Universite´ de Technologie de Troyes, Troyes, France
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. Journal of the Operational Research Society (2003) 54, 458–465. doi:10.1057/palgrave.jors.2601551 Keywords: transportation; military; aircraft loading; airlift; bin packing; constraint programming
Introduction In military context, force projection means fast and massive transportation of military equipment (vehicles, troops, ammunitions, etc) from a set of bases to a set of destinations, with the objective of minimizing both the total transportation time and the number of required vectors (aircraft, boats, trains, etc). Since force projection is concerned with the ability of military forces to rapidly alert, mobilise, deploy and operate anywhere in the world, it often takes the form of an airlift. In military airlifts, a set of requirements must be shipped by plane from a set of departure bases to a set of destination bases. Each requirement specifies a load (goods or passengers), ports of embarkation and debarkation, and time windows. Given a set of aircraft with limited capacities, the goal is to move each requirement within the time windows specified, using the aircraft fleet as efficiently as possible. Airlifts either at wartime or for humanitarian operations are usually scheduled by military logisticians. The French military agency in charge of prospective studies (the De´le´gation Ge´ne´rale pour l’Armement—DGA) may need to simulate airlifts at any time, for example to estimate deployment times, to evaluate a new aircraft or to find compatible dimensions for a new vehicle. DGA is currently developing computerized tools to perform these complex and combinatorial operations. In order to reduce the complexity of the task and also for project management reasons, they decided to split the problem into two subproblems: an aircraft loading problem (assigning items to be
*Correspondence: N. Jussien, Ecole de
Data Loading...
