RESUME
L'obtention d'une grande surface pour l'entreposage des
produits est un facteur très important pour les entreprises. De nos
jours, la plus part d'entreprises commerciales et industrielles dispose des
espaces de stockage qui valent la peine d'être utilisé avec
délicatesse. Dans ce travail nous traitons le problème de
maximisation de l'utilisation d'espaces de stockage tridimensionnels par les
articles en trois dimensions. Nous faisons allusion dans ce travail aux
entrepôts et articles possédant chacun une longueur, une largeur
et une hauteur. L'objectif est d'utiliser de la meilleure façon possible
l'espace de stockage disponible.
Ce problème étant du type NP-C, nous avons
utilisé un heuristique pour le résoudre vu que l'algorithme
exacte exigerait plus de ressources temporelles. Pour résoudre ce
problème, nous avons utilisé l'algorithme `'Human Intelligence
Based on Heuristic Approach`', ce modèle nous a permis de trouver une
réponse près de l'optimum en temps raisonnable. Nous avons
ensuite implémenté cet algorithme en langage C. Le test et
l'argumentation des résultats nous ont permis de vérifier notre
objectif que nous avons jugé atteint.
viii
Mots clés : 3D Bin packing, Heuristiques,
optimisation combinatoire, Entreposage.
ix
ABSTRACT
Getting more space for storage of products is a very important
factor for the companies. Nowadays, more commercial and industrial companies
have spaces for storage of goods that are to be used tactfully. This study
addresses the problem of maximization of the three dimensional storage spaces
of three dimensions sized goods. This study considers length, width and height
of each article. The objective is to maximize used volume and minimize wasted
space.
In order to resolve this problem a heuristic method is
applied, since the exact algorithm would require more temporal resources. The
"Human Intelligence Based on Heuristic Approach" algorithm is applied. This
model lead to an answer close to the optimum in reasonable time. Then the
algorithm is implemented in C language. The test and argumentations of results
permitted to verify objective set for the study.
Keywords: 3D Bin packing problem, Heuristics,
combinatorial optimization, storage
INTRODUCTION GENERALE
0. Problématique de recherche
`' On assiste aujourd'hui à l'émergence d'une
nouvelle économie dite de l'information ou « Nouvelle
économie », où le travail en rapport avec l'information est
devenu plus important que le travail en rapport avec les autres secteurs. Ceci
sous-entend donc la mise en place d'un système représentant
l'ensemble des ressources (les hommes, le matériel, les logiciels)
utilisées pour collecter, stocker, traiter et communiquer les
informations au sein de l'entreprise : « Le système d'information
(SI) » de l'entreprise `' (Sanni, 2009). Les Systèmes d'information
peuvent mettre en jeu le succès et même la survie de l'entreprise,
par conséquent une gestion saine des systèmes d'information
constitue un défi pour les dirigeants. A nos jours, La croissance d'une
entreprise passe forcément par un grand volume d'activités et
donc une grande quantité d'informations à gérer et dont il
faudra tirer le meilleur parti pour prendre les bonnes décisions.
L'entreposage des marchandises est une des principales
tâches du commerce et de l'industrie. Afin qu'ils comprennent toutes les
connexions du flux des marchandises, les commerçants ainsi que les
industriels doivent disposer des connaissances de base à tous les
niveaux, même si les différentes activités sont
exécutées par des spécialistes. En effet, les
différentes compagnies et entreprises fournissent de grands efforts dans
le but de détecter des possibilités de réduction des
coûts associés aux entreposages de tous les produits
(Matières première, produits semi-ouvrés et
2
produits finis). C'est dans cette optique qu'une optimisation
d'entreposage d'articles tridimensionnels dans des aires de stockage permettra
sûrement aux entreprises tant commerciales qu'industrielles de
réduire au maximum les coûts liés au stockage des produits
(coûts de l'entrepôt ou de l'espace, coût des marchandises,
coûts des machines et autres instruments de travail utilisés,...),
ce qui engendra une amélioration de profits pour enfin rester flexible
et compétitive sur un marché ouvert.
En effet, la minimisation d'espaces d'entreposage peut induire
à la réduction des coûts liés aux investissements en
espace de stockage, à l'amortissement pour la dépréciation
des espaces de stockage, aux primes d'assurances des entrepôts, à
l'approvisionnement et entretien des équipements, à la
réduction des temps morts ou mouvements inutiles durant le processus de
déchargement, de stockage et des chargement des entrepôts et
à l'organisation du rangement des marchandises reçues. En effet,
pour être compétitif, les entreprises doivent baisser au maximum
l'ensemble des coûts liés à ses services.
Apparemment le problème d'optimisation d'entreposage
d'articles que nous tentons de modéliser fait partie de la classe des
problèmes NP-Difficile, il nous semble que c'est un problème qui
ne peut donc pas être résolu à l'aide d'un algorithme de
complexité polynomiale. En effet, ce problème peut être
rattaché au problème classique de remplissage de panier
appelé communément problème de Bin packing. Ce
problème relève de la recherche opérationnelle et de
l'optimisation combinatoire. Il s'agit en fait de trouver le rangement le plus
économique possible pour un ensemble d'articles dans des boîtes.
Le problème classique se définit en une dimension.
De ce fait, le travail se base sur les interrogations
suivantes :
3
- Existe-t-il les algorithmes exactes et les heuristique
pouvant être utilisés pour : assurer un meilleur entreposage de
marchandises, minimiser les retards et augmenter les capacités de
stockage des entrepôts ?
- Et, quel est l'algorithme le plus effectif en termes de
complexité temporelle et spatiale pour résoudre notre
problème ?
Toutes ces questions se posent au niveau des
différentes activités s'exerçant dans des entreprises
disposant des locaux d'entreposage, et constituent des objectifs soucieux des
théoriciens, praticiens et également les responsables de la
gestion de stock.
| 
