An exact algorithm for the container loading problem

Mhand Hifi, CERMSEM

Résumé. Dans cet article, nous proposons un algorithme exact pour le problème du "chargement". Cet algorithme paraît très performant dans le sens où l'on arrive à résoudre des instances de taille assez importante en un temps d'exécution très raisonable. Le problème est décomposé sous forme d'une série de problèmes de knapsack bi-dimensionnels. L'approche s'appuie principalement sur une méthode de séparation et d'évaluation, habituellement utilisée en recherche opérationnelle. L'approche utilise la stratégie par le meilleur d'abord. A chaque niveau de l'arborescence créée, des bornes inférieures et supérieures sont obtenues par l'application d'une recherche locale. La performance de l'algorithme proposé est évaluée sur un ensemble d'instances de taille assez importante pour ce problème.
Mots clés : Optimisation combinatoire, problème de chargement, algorithme exact.

Abstract. In this paper we propose an exact algorithm for solving the container loading problem. We study a particular case of the problem, by considering the unconstrained three-dimensional packing problem. The algorithm is principally based upon a branch and bound procedure using a depth-first search strategy. Performance of branch-and-bound procedure depends highly on particular implementation of that algorithm. Programs of this kind are often accelerated drastically by employing some sophisticated techniques. At each node of the developed tree, the lower and upper bounds are computed by using local search procedures. These bounds are applied in order to reduce some useless branches. The performance of the proposed algorithm is evaluated on randomly-generated problem instances with different sizes and densities. Computational results show that the algorithm is able to solve small and medium problem instances within reasonable computational times.
Keywords : Combinatorial optimization, packing problems, exact algorithms.

JEL Classification : C44, C61, C63.