Article ID: | iaor20041068 |
Country: | United Kingdom |
Volume: | 54 |
Issue: | 5 |
Start Page Number: | 458 |
End Page Number: | 465 |
Publication Date: | May 2003 |
Journal: | Journal of the Operational Research Society |
Authors: | Prins C., Jussien N., Lhomme O., Guret C., Pavageau C. |
Keywords: | transportation: air |
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.