Abstract :
[en] According to the International Air Transport Association and Air Transport
Action Group, 51.3 million metric tons of goods were transported
by airlines in 2014. To transport luggage, freight and mail, special containers,
called Unit Load Devices (ULD), are used. The method of loading packages
into ULDs represents a key element for cargo safety and aircraft weight and
balance, as well as for the economy of airline companies.
This thesis aims to solve the problem of packing a set of boxes into containers
of various shapes without wasting loading space. The goal is to select
the best set of ULDs to pack all the boxes achieving a minimum unused
volume. As for all the packing problems, geometric constraints have to be
satis ed: items cannot overlap and have to lie entirely within the bins. The
richness of this application is to manage additional and common constraints:
the bin weight limit, rotations, stability and fragility of the boxes, and weight
distribution within a ULD. In practice, this problem is manually solved with
no strict guarantee that the constraints are met.
First, the problem is formulated as a mixed integer linear program. As
this problem is NP-hard, it opens the way to heuristics. A second approach
makes use of the formulation to apply three matheuristic methods, combining
exact approaches and heuristics. Third, a tailored two-phase constructive
heuristic is developed for this speci c problem; it aims to nd good initial
solutions in short computational times. These approaches contain parameters
that have been tuned using the irace parametrisation technique. For the
experiments, several instances have been created on the basis of a box data
set which stems from a real world case.
