Approximate algorithms for the container loading problem
Mhand Hifi,
CERMSEM
Résumé.
Dans cet article, nous proposons plusieurs algorithmes pour la résolution du problème de découpe et
d'assemblage à trois dimensions. Dans un premier temps, nous proposons un algorithme qui peut être considéré
comme une adaptation de l'approche développée dans [19]. A partir de cet algorithme, nous construisons un
algorithme polynomial réalisant un rapport d'approximation constant pour le problèmes traités. Par la suite,
nous proposons une extension du premier algorithme pour construire un algorithme plus performant. L'algorithme
qui en résulte est une combinaison entre une recherche locale et une stratégie dite de
"hill-climbing". La performance de chaque algorithme proposé est évaluée sur un ensemble d'instances
de la littérature. Les résultats obtenus ont été comparés aux meilleurs résultats publiés par Morabito et
Arenales [26].
Mots clés :
Algorithmes approchés, optimisation combinatoire, problèmes de découpe et d'assemblage, programmation dynamique,
knapsack unidimensionnel.
Abstract.
In this paper we develop several algorithms for solving three-dimensional cutting/packing problems. We begin
by proposing and adaptation of the approach proposed in [19] for solving two-staged unconstrained
two-dimensional cutting problems. We show how the algorithm can be polynomially solved and produces a
constant approximation ratio for the three-dimensional problem. We then extend this algorithm for developing
better approximate algorithms. By using hill-climbing strategies, we construct some heuristics which produce
a good trade-off between the computational time and the solution quality. The performance of the proposed
algorithms is evaluated on different problem instances of the literature, with different sizes and densities
(a total of 144 problem instances). The obtained results are compared to the results published by Morabito
and Arenales [26].
Keywords :
Approximate algorithms, combinatorial optimization, cutting/packing problems, dynamic programming, single knapsack
problem.
JEL Classification :
C44, C61, C63.
