Memoire Online - Optimisation heuristique du problème d'entreposage d'objets en trois dimensions.

Mémoire présenté et défendu en vue de l'obtention du grade de Licencié en Sciences économiques et de gestion

Epigraphe

`' Souvent le monde de l'industrie préfère une réponse approximative mais rapide et
efficace plutôt qu'une réponse parfaite »

`' La connaissance commence par la tension entre savoir et non-savoir : -pas de
problème sans savoir -pas de problème sans non-savoir »

`' Les ordinateurs sont comme les dieux de l'Ancien Testament : avec beaucoup de règles, et sans pitié `'

DEDICACE

REMERCIEMENTS

Personne ne peut tout faire seul. Sans le concours de bien de gens de bonne foi, nous ne serions pas là où nous sommes aujourd'hui. De ce fait, nous serons ingrat de finir ce modeste travail sans remercier tout effort autre que le nôtre à avoir concouru à la réussite de ce mémoire.

Je tiens tout d'abord à remercier Mr. le Docteur Osée MUHINDO MASIVI. Je le remercie pour l'intérêt qu'il a porté à mon travail, pour toutes ces discussions scientifiques et autres, qui m'ont permis d'avancer dans mes travaux, qui m'ont fait réfléchir et qui m'ont inspiré. Je voudrais encore le remercier infiniment pour avoir accepté d'être le directeur de ce travail de recherche.

Toute ma gratitude s'adresse à la famille RUHAMYA car c'est grâce à son soutient, sa patience et son amour que je suis là aujourd'hui. Je n'oublierais pas tous mes oncles, frères, soeurs, neveux et cousins pour les sacrifices qu'ils ont pu faire pendant mes longues années d'études et d'absence.

Aux camarades étudiants, compagnons de lutte avec qui nous avons partagé peines et joies, nous disons également merci pour l'ambiance chaleureuse de travail qu'ils maintiennent au quotidien.

Ce travail ne serait pas ce qu'il est sans la présence, la générosité, l'enthousiasme et les précieux conseils de tous mes amis dont je ne pourrais lister les noms qui m'ont toujours encouragés, soutenus et permis de travailler dans les meilleures conditions.

SIGLES ET ABBREVIATIONS

TABLE DES MATIERES

LISTE DES FIGURES

Figure 14 : Fichier des variables entrantes de l'interface graphique du programme 49

LISTE DES TABLEAUX

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.

Mots clés : 3D Bin packing, Heuristiques, optimisation combinatoire, Entreposage.

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

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.

- 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.

1. But et Objectif de recherche

Notre but dans la réalisation de ce travail de recherche est de répondre à la question posée ci-haut dans notre problématique, c'est-à-dire, de trouver une ou plusieurs méthode capable de modéliser et résoudre le problème lié à l'optimisation d'objets tridimensionnels dans des aires de stockage le plus effectivement possible. A la fin de ce travail nous devons aussi mettre en place un logiciel informatique d'entreposage d'objets en 3 dimensions.

Vu notre hypothèse de croire que le problème qui nous intéresse ici est une variante du problème de bin packing en trois dimensions, notre objectif principal est de : trouver l'algorithme le plus effectif au problème d'entreposage d'objet en 3 dimensions et capable de fournir des solutions réalisables de qualité acceptable, proches de l'optimal et déterminées en un temps raisonnable (complexité polynomiale).

- Lister un ou plusieurs algorithmes exactes pour les problèmes de même nature que le nôtre ;

- Trouver et analyser les heuristiques capables de résoudre notre problème en temps raisonnable ;

- Après que nous aurons jugé ces algorithmes optimaux, nous pourront traduire un de ces algorithmes en logiciel d'application pouvant représenter une potentialité d'amélioration intéressante.

2. Choix et intérêt du travail

Toute entreprise aspire à l'amélioration de sa trésorerie pour diverses raisons dont l'augmentation de sa capacité d'autofinancement. En vue d'aider nos entreprises nous avons jugé faire ce qui est à nos pouvoir pour contribuer à l'atteinte de cet objectif ; et c'est ainsi que nous avons eu l'idée de mettre à la disposition de tout responsable de la gestion des stocks cet outils qui pourra leur permettre de réduire les difficultés qu'ils rencontrent face au rangement des articles dans des entrepôts et la maximisation des espaces à utiliser.

Le choix de ce sujet a été motivé par notre souci de guider les prises de décisions des entreprises congolaises en particulier, et ceux de partout ailleurs en générale, quant à l'utilisation efficace des ressources toujours limitées qu'ont les entreprises, en vue d'accroître leurs niveaux d'activité.

3. Délimitation du sujet

Le monde de recherche étant assez vaste, nous limiterons ce travail à la gestion optimum des espaces de stockage des articles en trois dimensions dans des entrepôts afin d'en maximiser l'usage. Nous nous contenterons donc d'étudier et appliquer quelques heuristiques du problème classique de bin packing (remplissage de panier) en trois dimensions.

4. Méthodes et technique de recherche

Aktouf, (1992) a dit que toute recherche doit en principe aboutir à modéliser ce qu'elle a pris comme objet d'étude. Le principe directeur qui peut y mener, c'est ce qu'il est convenu d'appeler méthode. La méthode se définit donc, comme étant la procédure logique d'une science ; c'est-à-dire l'ensemble de pratiques particulières mises en oeuvre pour que le cheminement de ses démonstrations et de ses théorisations soit clair, évident et irréfutable. Les techniques quant à elles sont des moyens précis pour atteindre un résultat partiel, à un niveau et à un moment donné de la recherche. Elles ne sont que des outils mis à la disposition du chercheur et organisées par la méthode dans un but précis. Elles ne peuvent donc qu'être momentanées, conjoncturelles et limitées dans le cheminement de la recherche. La technique représente ces différentes phases d'opérations limitées, liées à des éléments pratiques concrets, adaptés à un but défini, alors que la méthode est une conception intellectuelle coordonnant un ensemble d'opération, en général plusieurs techniques.

Comme méthode, nous utiliserons la méthode algorithmique, ce qui nous permettra d'analyser notre problème et de transformer les entrées (valeurs entrées par l'utilisateur) en sorties (résultats). Les techniques documentaires nous aiderons à récupérer la plupart des documentations sur l'internet et dans des documents (livres, notes des cours, mémoires,...) pour nous permettre d'aboutir à nos objectifs.

5. Subdivision du travail

Cette recherche suit une progression ordonnée. Ce travail se décompose en effet en quatre chapitres mis à part cette introduction et la conclusion qui viendra plus tard acheminer notre démarche scientifique. Il s'agit de la revue de la littérature, la méthodologie du travail, les approches méthodologiques et la présentation et

discussion des résultats constitué du prototypage, des tests et de l'argumentation des résultats.

Chapitre premier : REVUE DE LA LITTERATURE

Des nombreux chercheurs avant nous se sont intéressés au domaine d'optimisation combinatoire, plus particulièrement dans la conception des logiciels d'optimisation de la coupe et entreposages des articles. Plusieurs méthodes ont été utilisées pour résoudre ce problème. Cette revue de littérature nous permettra de situer notre sujet par rapport à des recherches antérieures afin d'établir un créneau unique pour notre recherche. En plus de ça, cette partie sera pour nous, une occasion de fournir les informations de fond en ce qui concerne notre sujet pour comprendre les termes clés qui constituent notre thème.

I.1. Optimisation

D'après le petit Larousse (1980), l'optimisation c'est l'action de donner à un investissement, une entreprise ou une machine un rendement maximale. Selon Microsoft Encarta (2008), l'optimisation est une action de réguler (quelque chose) dans le but d'obtenir la plus grande efficacité possible.

Pour Nzalamingi (2012), l'optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d'un ensemble en fonction d'un critère quantitatif donné. Aujourd'hui, nombreux des systèmes susceptibles d'être décrits par un modèle mathématique sont optimisés. Ils sont extrêmement variés : optimisation d'un trajet, de la forme d'un objet, d'un prix de vente, d'une réaction chimique, du contrôle aérien, du rendement d'un appareil, du fonctionnement d'un moteur, de la

gestion des lignes ferroviaires, du choix des investissements économiques, de la construction d'un navire jusqu'à l'optimisation des espaces de stockage et de la coupe de matériel. L'optimisation de ces systèmes permet de trouver une configuration idéale, d'obtenir un gain d'effort, de temps, d'argent, d'énergie, de matière première, de satisfaction, des rebus ou encore d'espaces. Très loin de constituer une liste exhaustive, ces quelques exemples attestent la variété des formulations et préfigurent la diversité des outils mathématiques susceptibles de résoudre ces problèmes.

En termes simples et pratiques, l'optimisation des processus consiste à améliorer les procédures d'usage et les manières de réaliser les tâches de manière à atteindre une productivité maximale l'entreprise. Cette optimisation vise donc à minimiser les couts et contraintes restreignant la productivité et à maximiser les gains favorisant l'efficacité. Pour ce qui concerne ce travail les contraintes sont constituées des places inutilisables dans les dépôts alors que les gains sont constitués des place ou case bien utilisées aux entrepôts.

La qualité des résultats et des prédictions du système optimisé dépendent de la pertinence du modèle, de l'efficacité de l'algorithme et des moyens pour le traitement numérique. Et ce travail est concerné par le modèle et l'algorithme du système de découpage et entreposage d'article.

D'après Nzalamingi (2012), les modèles d'optimisation sont repartis en plusieurs classes dont nous pouvons relever :

- L'optimisation linéaire qui étudie le cas où la fonction objectif et les contraintes caractérisant l'ensemble de possibilités sont linéaires. C'est une méthode très employée pour établir les programmes des raffineries pétrolières, mais aussi pour

déterminer la composition la plus rentable d'un mélange salé, sous contraintes, à partir des prix de marché du moment.

- L'optimisation linéaire en nombres entiers étudie les problèmes d'optimisation linéaire dans lesquels certaines ou toutes les variables sont contraintes de prendre des valeurs entières.

- L'optimisation quadratique étudie le cas où la fonction objectif est une forme quadratique (avec contraintes linéaires)

- L'optimisation non linéaire étudie le cas général dans lequel l'objectif ou les contraintes (ou les deux) contiennent des parties non linéaires, éventuellement non-convexes.

- L'optimisation stochastique étudie le cas dans lequel certaines des contraintes dépendent de variables aléatoires. En optimisation robuste, les aléas sont supposés être situés dans des intervalles autour de positions nominales et on cherche à optimiser le système soumis à de tels aléas, dans le pire des cas.

- L'optimisation combinatoire (optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Comme lu dans Wikimedia Foundation (2013), l'optimisation combinatoire est en fait une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. On parle également d'optimisation discrète. Dans sa forme la plus générale, un problème d'optimisation combinatoire (on dit aussi d'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif. Formellement, étant donnés :

L'ensemble des solutions réalisables ne saurait être décrit par une liste exhaustive car la difficulté réside ici précisément dans le fait que le nombre des solutions réalisables rend son énumération impossible, ou bien qu'il est NP-complet de dire s'il en existe ou non. La description de R est donc implicite, il s'agit en général de la

liste, relativement courte, des propriétés des solutions réalisables. La plupart du temps on est dans les cas particuliers suivants :

- R = conv (n) n Z ⁿ donc les propriétés de R se traduisent en contraintes linéaires,

L' Optimisation combinatoire consiste à trouver le meilleur entre un nombre fini de choix. Autrement dit, minimiser une fonction, avec contraintes, sur un ensemble fini. Quand le nombre de choix est exponentiel (par rapport à la taille du problème), mais que les choix et les contraintes sont bien structurées, des méthodes mathématiques doivent et peuvent intervenir, comme dans le cas " continu ", pour permettre de trouver la solution en temps polynomial (par rapport à la taille du problème). Le travail de l'équipe consiste à développer des algorithmes polynomiaux

et des théorèmes sur des structures discrètes qui permettent de résoudre ces problèmes.

Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d'essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure. Cependant, en pratique, l'énumération de toutes les solutions peut prendre trop de temps ; or, le temps de recherche de la solution optimale est un facteur très important et c'est à cause de lui que les problèmes d'optimisation combinatoire sont réputés si difficiles. La théorie de la complexité donne des outils pour mesurer ce temps de recherche. De plus, comme l'ensemble des solutions réalisables est défini de manière implicite, il est aussi parfois très difficile de trouver ne serait-ce qu'une solution réalisable.

Quelques problèmes d'optimisation combinatoire peuvent être résolus (de manière exacte) en temps polynomial par exemple par un algorithme glouton, un algorithme de programmation dynamique ou en montrant que le problème peut être formulé comme un problème d'optimisation linéaire en variables réelles.

Dans la plupart des cas, le problème est NP-difficile et, pour le résoudre, il faut faire appel à des algorithmes de branch and bound, à l'optimisation linéaire en nombres entiers ou encore à la programmation par contraintes. En pratique, on se contente très souvent d'avoir une solution approchée, obtenue par une heuristique ou une métaheuristique. Pour certains problèmes, on peut prouver une garantie de performance, c'est-à-dire que l'écart entre la solution obtenue et la solution optimale est borné. Chacune de ces méthodes sera exploitée d'avantage dans le deuxième chapitre de notre travail.

I.2. Entrepôt et Entreposage

`' Un entrepôt est un bâtiment logistique destiné au stockage de biens en vue de leur expédition vers un client (interne ou externe à l'entreprise). Il peut être détenu et géré en propre par l'entreprise ou faire l'objet d'une sous-traitance auprès d'un prestataire logistique `' (Wikimedia Foundation, 2013).

La nature des biens entreposables dépend de l'activité de l'entreprise, on trouvera : - activités de production :

? matières premières, encours de production, produits semi-finis destinés à la régulation du processus de production (de l'entreprise ou de son client : cas des entrepôts avancés fournisseurs dans l'automobile par exemple)

? produits dont l'entreprise a fait l'acquisition et qui ne subiront aucune transformation en vue de leur vente

L'entreposage est une étape très importante dans la chaine logistique. L'entreposage est le fait d'entreposer (donc de stocker et d'emmagasiner) des marchandises, des matières premières et des produits en très grande quantité. Afin de faciliter les opérations de manutention des marchandises, on trouvera fréquemment dans les entrepôt les engins de manutention suivants : transpalettes, chariots élévateurs, gerbeurs, préparateurs de commande, nacelles, diables,...

I.3. Les objets

Dans notre travail, nous considérons comme objets les articles qui constituent le stock dont nous optimiserons l'espace.

I.3.1. Objet en une dimension

Un objet en une dimension (1D), c'est un objet ne comprenant que la dimension de la longueur.

I.3.2. Objet en deux dimensions

On dit qu'un objet est en deux dimensions (2D) lorsqu'il ne comportant que les dimensions de la longueur et de la largeur.

I.3.3. Objet en trois dimensions

Trois dimensions (3D), se dit de tout objet ou espace possédant une longueur, une largeur et une épaisseur, tout en sachant que la largeur peut aussi être appelée profondeur et l'épaisseur est aussi désigné par la hauteur. Ce sont ces objets qui nous intéressent dans ce travail.

I.4. Quelques travaux de recherche étudiés

Dans cette section nous passeront en revue les mémoires, thèses et logiciels déjà proposés pour résoudre le problème d'optimisation d'aires d'entreposage des articles en différentes dimensions pour enfin apporter quelque chose d'originale à notre recherche.

Nzalamingi (2012), dans son travail intitulé "Optimisation de la coupe et entreposage en une et deux dimensions" est parvenu à de trouver un modèle mathématique d'optimisation du découpage et d'emmagasinage d'objets en une et deux dimensions pour les entreprises. Il a finalement traduit ce modelé mathématique en algorithme et mis en oeuvre un logiciel informatique pouvant être exploité pour la productivité des entreprises tant industrielles que commerciales en général et des Ets Tsang en particulier.

Gazdar (2009), a lui dans sa thèse d' "Optimisation Heuristique Distribuée du Problème de Stockage de Conteneurs dans un Port" étudié dans un contexte bien déterminé et selon les motivations et les enjeux qu'elle a défini, le modèle COSAH (COntainer Stacking via multi-Agent approach and Heuristic method), ce qui lui a permis d'optimiser le placement des conteneurs dans la zone de stockage (statique ou

dynamique selon les départs ou les arrivées de navires ou camions ou de conteneurs en import ou en export) en minimisant le nombre de mouvements improductifs respectant un nombre de contraintes spatio-temporelles et tenant compte de plusieurs paramètres pouvant catégoriser les conteneurs et définir une certaine priorité entre eux (destination, taille, date de départ, horizon des arrivées des barges ou navires associés).

Perrot (2005), dans sa thèse intitulée "Integer programming column generation strategies for the cutting stock problem and its variants", s'est intéressé au problème de découpe unidimensionnel où elle a présenté une formulation pour la minimisation du nombre de plans de découpe distincts jusqu'à ce que le déchet soit fixé à sa valeur optimale. Son objectif est principalement de réduire au minimum la perte correspondant à la partie inutilisée des rouleaux. Elle a proposé une solution donnée par un ensemble de plans de découpe réalisables, c'est à dire des façons de couper les petites pièces sur les rouleaux, de sorte que leur production totale couvre les demandes.

Le logiciel 3D Load Packer (2011), est l'optimiseur de l'espace conçu par Nikita Yurchenko pour aider à planifier rapidement et facilement le meilleur arrangement compact d'un certain nombre de différentes tailles d'objets 3D rectangulaire (dénommé "Boxes") dans une ou plusieurs enceintes rectangulaires (dénommé "conteneurs"). 3DLoad Parker peut être utilisé pour optimiser la charge multi-produit des plans pour tous les contenants rectangulaires (camions, remorques, wagons, palettes et caisses).

VitragePro (2007) est un logiciel d'optimisation de découpe de vitrage, développé par Patrice Rozet. Il est destiné aux vitriers, miroitiers et à tous les professionnels qui doivent régulièrement effectuer des découpes de vitrages. Il vous permet de générer

aisément et rapidement les plans de découpe. Il réalise en effet les plans de découpe en prenant en compte plusieurs matériaux d'épaisseurs différentes.

CubeMaster (2012) est une application destinée au monde de la logistique et de la supply chain. C'est une solution logicielle permettant de réduire les coûts et d'optimiser le chargement des camions, containers et autres contenants.

I.5. Conclusion partielle

Nous n'avons pas touché tous les travaux spécifiquement liés au nôtre. Mais, d'après ces quelques exemples, il est sied de noter que notre travail n'est pas le premier à aborder le problème d'optimisation d'espaces. Tous ces travaux répondent au problème d'optimisation d'entreposage mais dont les contextes d'utilisation et les conditions de stockage ne sont pas forcément les mêmes ni adaptées à celles que nous abordons dans le présent travail.

Chapitre deuxième : METHODOLOGIE DU TRAVAIL

Ce chapitre de notre travail nous permettra de donner une présentation générale des différentes méthodes que nous aurons à utiliser pour trouver solution à l'énoncé théorique de notre problème. Les concepts qui nous intéresserons dans ce chapitre sont : la méthode algorithmique, le prototypage, l'expérimentation et l'argumentation.

II.1.Methode Algorithmique

Un algorithme répond à un problème. Il est composé d'un ensemble d'étapes simples nécessaires à la résolution d'un problème, dont le nombre varie en fonction du nombre d'éléments à traiter. D'autre part, plusieurs algorithmes peuvent répondre à un même problème. Pour savoir quelle méthode est plus efficace il faut les comparer. Pour cela, on utilise une mesure que l'on appelle la complexité. Elle représente le nombre d'étapes qui seront nécessaires pour résoudre le problème pour une entrée de taille donnée.

II.1.1. Problèmes algorithmiques

Un problème algorithmique est un problème posé de façon mathématique, c'est-à-dire qu'il est énoncé rigoureusement dans le langage des mathématiques. On distingue deux types de problèmes :

- Les problèmes de décision : ils posent une question dont la réponse est oui ou non ;

- Les problèmes d'optimisation : ils comportent une question ou plutôt une injonction de la forme « trouver un élément tel que ...» dont la réponse consiste à fournir un tel élément.

La théorie de la complexité étudie principalement (mais pas uniquement) les problèmes de décisions. Dans ce travail le type de problème dont nous aurons à traiter est celui d'optimisation.

II.1.2. Classes de Complexité

La théorie de la complexité est un domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (en temps et en espace) nécessaire pour la résolution de problèmes au moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes posés mathématiquement.

Les classes de complexité sont des ensembles de problèmes qui ont la même complexité selon un certain critère. Dans ce qui suit nous allons définir trois classes de complexité les plus étudiées en une liste qui va de la complexité la plus basse à la complexité la plus haute : la classe P, la classe NP et la classe NP-C.

La classe NP possède une définition moins naturelle que celle de P, et ne signifie pas "non polynomial", mais polynomial non-déterministe. La classe NP est donc une

extension de la classe P, en autorisant des choix non déterministes pendant l'exécution de l'algorithme. Si le modèle de calcul est celui des machines de Turing, on autorise plusieurs transitions à partir d'un état et d'un symbole lu sur la bande.

En théorie de la complexité, un problème NP-complet est un problème vérifiant les propriétés suivantes :

- Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP.

- Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.

Un problème NP-difficile est un problème qui remplit la seconde condition, et donc peut être dans une classe de problème plus large et donc plus difficile que la classe NP.

Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas en trouver efficacement. C'est le cas, par exemple, du problème du voyageur de commerce, celui du sac à dos ou encore celui de remplissage des paniers.

Une question reste ouverte et fait partie des problèmes non résolus en mathématiques les plus importants à ce jour. Celui de prouver s'il existe un algorithme polynomial pour résoudre un quelconque des problèmes NP-complets, si oui, alors tous les problèmes de la classe NP peuvent être résolus en temps polynomial. Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ? NP.

En pratique, les informaticiens et les développeurs sont souvent confrontés à des problèmes NP-complets, ce qui est d'ailleurs le cas pour nous dans ce travail. Savoir que le problème sur lequel on travaille est NP-complet est une indication du fait que le problème est difficile à résoudre, donc qu'il vaut mieux chercher des solutions approchées en utilisant des algorithmes d'approximation ou des heuristiques pour trouver des solutions approximatives.

II.2. Le Prototypage

Même si la construction des programmes est au centre de l'informatique, il est surprenant que la programmation en elle seule ne constitue pas de recherche scientifique. Il y a après tout, des milliers de programmeurs qui, quelle que soit la haute technicité de leur travaux, écrivent des programmes sans nécessairement être des chercheurs.

Le prototypage des programmes est écrit à la fin d'une recherche en informatique pour démontrer que le modèle produit dans la recherche peut être implémenté dans un langage de programmation. Ainsi, les prototypes servent de véhicule d'expérimentation et leur construction fournit des nouveaux aperçus sur le modèle prototypé (Masivi, 2013).

II.3. L'Expérimentation

L'idée derrière la méthode expérimentale en informatique est de tester la modèle

- Chercher à trouver quelque chose d'intéressant : expérimentation exploratoire ;

En ce qui nous concerne, seule l'expérimentation de test nous sera utile car elle

II.4. L'Argumentation

Selon Masivi (2013), l'argumentation est généralement utilisée quand deux ou plusieurs alternatives sont comparées. L'objectif est donc de présenter certains arguments permettant le choix d'une solution en dépend de l'autre. Cette argumentation peut être présentée des faits évidents ou un raisonnement relevant et combinant des issues subtiles. Dans notre travail, nous utiliserons l'argumentation, si et seulement si on aura à utiliser deux ou plusieurs algorithmes de résolution d'un problème d'optimisation d'un espace de stockage.

Chapitre Troisième : APPROCHES METHODOLOGIQUES

Dans ce travail nous traitons un problème d'optimisation combinatoire appliqué au problème concret d'entreposage d'objets 3D dans un espace de stockage. De ce fait, nous aurons besoin d'au moins un algorithme pouvant nous permettre d'atteindre notre objectif, celui d'utiliser de la meilleure façon possible l'espace de stockage disponible.

Ce chapitre est consacré à la représentation et l'analyse des algorithmes pouvant résoudre le problème de 3DBP. De prime à bord, nous avons procédé à la présentation des algorithmes qui ont constitués notre objet de recherche, nous avons commencé par la présentation d'un algorithme exacte du problème de remplissage de paniers puis les algorithmes d'approximations qui nous ont permis de résoudre ce problème en donnant une solution acceptable en un temps convenable.

III.1. Modélisation algorithmique du problème de 3DBP

III.1.1. Formulation du problème

Le problème de 3D bin packing relève de la recherche opérationnelle et de l'optimisation combinatoire. Il s'agit 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, mais il existe de nombreuses variantes en deux ou trois dimensions.

Le problème de chargement d'entrepôts que nous tentons de modéliser est une variante du problème en trois dimensions. En fait, dans ce travail nous ne faisons

allusion qu'aux articles possédant chacun une largeur, une longueur (ou profondeur) et une hauteur c'est de là d'ailleurs que vient de concept 3D (figure 4).

Dans le problème classique, les données sont : Un nombre infini de paniers de taille C

On cherche à trouver le rangement valide pour tous ces objets de façon à minimiser le nombre de paniers à utiliser. Pour qu'un rangement soit valide, la

somme des tailles des objets affectés à un panier doit être inférieure ou égale à C.

Pour décrire une solution, on peut utiliser un codage binaire pour indiquer dans quel panier un objet est rangé.

La variable binaire est égale à si la boîte est utilisée, sinon.
On cherche donc à minimiser le nombre de panier :

La première inégalité signifie qu'on ne peut dépasser la taille d'un panier pour un

rangement. À noter que la partie droite de l'inégalité oblige à prendre la valeur

dès qu'un article est rangé dans le panier . La deuxième inégalité impose à chaque objet d'être rangés dans une boîte et une seule. Toute solution pour laquelle la famille d'équations précédente est vérifiée est dite réalisable. (Kantorovitch, 1960).

Le problème de bin packing a été largement étudié dans la communauté de recherche opérationnelle. Il existe des heuristiques très efficaces pour le résoudre, et des méthodes exactes utilisant l'optimisation linéaire en nombre entiers, la formulation de Kantorovich, une résolution par génération de colonnes, la procédure par séparation et évaluation,... Les méthodes exactes permettent d'obtenir la solution optimale à chaque fois, mais le temps de calcul peut être long si le problème est compliqué à résoudre. Les méthodes approchées, encore appelées heuristiques, permettent d'obtenir rapidement une solution approchée, donc pas nécessairement optimale. Nous n'allons pas vraiment parler de toutes ces méthodes car ce qui nous intéresse dans ce travail c'est plutôt trouver une heuristique qui donne une solution acceptable en un temps convenable.

III.1.2. Méthodes exactes

Le problème de chargement d'entrepôt que nous tentons de modéliser dans ce chapitre est en fait rattachable au problème de 3D bin packing, une extension au problème de remplissage de sacs, ce qui explique son NP complétude.

Tous les algorithmes exactes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel en la taille des données d'entrée dans le pire cas, ils sont donc inexploitables en pratique car bien qu'ils résolvent les problèmes NP-C en donnant des réponses exactes, ils sont couteux en terme de temps d'exécution.

L'algorithme exact consiste à essayer toutes les combinaisons d'objets et choisir celle qui minimise le nombre de panier. Il faut d'abord deviner toutes les solutions réalisables puis vérifier chaque alternative. On parle alors d'un divin et d'un vérificateur, le divin propose un certificat, c'est-à-dire, une réponse probable ou encore un candidat-réponse et le vérificateur teste si le certificat remplit les conditions d'être une réponse.

En ce qui nous concerne ici, l'algorithme exact est donc celui dont le divin fournit plusieurs ensembles d'articles (caisses ou boîtes) provenant d'une liste de plusieurs articles. Il essaie toutes les combinaisons possibles, chaque ensemble constitue un candidat-réponse à la question de savoir quel ensemble d'articles maximise l'utilisation de l'entrepôt. Le vérificateur vérifie si chaque ensemble remplit les contraintes en se posant les questions ci-après :

- Dans un ensemble d'articles ni existe-t-il un article dont la hauteur (hi), la largeur (li) ou la profondeur (pi) est supérieur à la hauteur (H), la largeur (L) ou la profondeur (P) de l'entrepôt ? Tout en sachant que l'objet peut être roté et donc, on considère comme hi, li ou pi finale, sa valeur après dernière rotation.

- Est-ce que la taille (volume) d'un ensemble d'articles (ni) dépasse la taille de l'espace de stockage ?

Tout en sachant que l'objectif est de minimiser l'espace non utilisé, c'est-à-dire la différence entre le volume de l'espace de stockage et le volume de toutes les boîtes chargées.

Cette solution donne une réponse exacte mais malheureusement il est couteux. Pour pallier à ce problème lié au temps d'exécution, il existe les algorithmes d'approximation. Ceux-ci qui permettent de résoudre un problème NP-complet en donnant une solution presque optimale en temps polynomial.

III.1.3. Méthodes approximatives (heuristiques)

Les algorithmes d'approximations sont utilisés pour réduire la complexité des problèmes de classe NP-Hard.

Comme nous l'avons déjà dit dans notre introduction, nous présentons dans ce travail quelques algorithmes d'approximation que nous allons ensuite implémenter dans un langage de programmation et les soumettre à une expérimentation pour trouver le plus performant en terme de temps d'exécution et d'espace de l'entrepôt utilisé. Notre objectif est donc de répertorier quelques algorithmes existants pour le problème de 3D Bin packing et trouver le plus performant.

Dans cette section nous allons présenter 2 algorithmes de 3D Bin packing : l'algorithme HI-BHA (A Human Intelligence-Based Heuristic Approach) proposé par (Baltacioglu, 2002) et le LAFF (Largest Area First-Fit) développé par (Gürbüz, Akyokuþ, Emiroðlu, & Güran, 2009).

Le problème de 3DBP est toujours résolu en utilisant les algorithmes optimums et les méthodes heuristiques. Voici une méthode heuristique parmi plusieurs qui essaie de résoudre le problème en un temps polynomiale.

Cette approche a été qualifiée d'une approche basée sur l'intelligence humaine par son auteur du fait qu'elle simule l'intelligence humaine en chargeant les boîtes dans l'entrepôt comme un humain, de bas à haut et en construisant des couches.

Ce modèle utilise un outil puissant de l'heuristique et une structure de données dynamique qui lui permet d'imiter l'intelligence humaine. L'avantage de cet algorithme est qu'il est capable de charger l'article dans n'importe quelle orientation, tout en sachant qu'un article peut être roté de six manières différentes. Cette approche est basée sur la construction des couches ou murs. L'idée est qu'après la création d'une couche, avant qu'une boîte soit chargée dans la couche, l'algorithme analyse toutes les boîtes non chargées pour trouver celle qui conviendra le mieux au sein de la couche selon son épaisseur (hauteur) pour minimiser l'espace perdu. Cependant, l'épaisseur de la couche sélectionnée est flexible et peut augmenter pour s'adapter à la hauteur de la boîte sélectionnée.

Les premières variables entrants sont les coordonnées x, y et z qui représentent les dimensions de l'espace de stockage. Les informations suivantes représentent les caractéristiques des boîtes à entreposer. Dans chaque ligne le premier élément représente l'étiquette de la boîte contenant les articles, ces étiquettes n'ont aucun effet sur l'algorithme, ce n'est qu'une façon d'identifier chaque boîte, elles sont facultatives, le deuxième, troisième et quatrième élément correspondent respectivement aux coordonnées x, y et z de chaque boîte. Le cinquième élément

représente le nombre de boîte de même type, c'est-à-dire le nombre de boîtes ayant la même largeur (x), la même hauteur (y) et la même profondeur (z).

La structure de données est un critère assez important dans un programme, elle affecte de manière directe le résultat de la solution d'un algorithme que ce soit en terme de temps d'exécution ou en terme d'espace utilisé.

Cet algorithme utilise deux tableaux : la premier tableau est celui de la liste des boîtes dénommé `'BoxList[] Array`', il sert à garder toutes les dimensions, les coordonnées et d'autres informations nécessaires relatives aux boîtes dans une liste. Il a au total douze champs :

Cet algorithme stocke aussi le volume de chaque boîte, ainsi on n'a pas besoin de le recalculer à chaque instant qu'on en a besoin. Les champs 6 à 11 n'ont pas de sens si le premier (Packst) a comme valeur 0, ils deviennent importants une fois qu'on a chargé la première boîte et Packst devient égal à 1. Chaque boîte constitue une ligne d'enregistrement dans le tableau `'BoxList[] `'.

Un autre tableau est le `'Layers[]`'. Ce tableau stocke les différentes tailles de toutes les dimensions des boîtes. Chaque champ dénommé Layerdim représente l'épaisseur d'une couche créée au sein de l'espace de stockage. Avant le commencement de chaque boucle (itération), les différentes valeurs des dimensions des boîtes sont stockées dans ce tableau. Le deuxième champ de ce tableau est le Layereval, la valeur de ce champ est calculée par la fonction Listcanditlayers que nous allons expliquer plus tard dans le quatrième chapitre de ce travail. Voici donc les deux champs du tableau Layereval :

Les limites de l'algorithme HI-BHA sont d'après le concepteur dues à la capacité

Ceci est une représentation graphique de l'enchainement des opérations de ce qui

constituera le fruit de l'implémentation de l'algorithme HI-BHA (le programme

Avant l'exécution de l'algorithme, on doit s'assurer du respect des critères ci-

- Chaque espace de stockage doit posséder une largeur et une profondeur et une hauteur bien finie ;

- Chaque boîte à entreposer doit aussi avoir une largeur, une profondeur et une hauteur ;

- Toutes les boîtes peuvent être rotée et placée dans n'importe quel angle dans l'entrepôt ;

- Les boîtes peuvent se supporter les unes sur les autres sans créer des dommages.

Prise en compte d'un enregistrement du Layers[] comme l'épaisseur (hauteur) de la couche

Meilleur utilisation de l'espace de stockage garde l'orientation de la boîte et la hauteur de la couche

Nous allons expliquer dans ce point le fonctionnement et l'obtention des valeurs de différents champs des tableaux détaillés un peu plus haut dans ce troisième chapitre, il s'agit de `'BoxList[]» et de `'Layers[]». Ceci en nous basant d'un exemple typique.

Exemple : soit un entrepôt de 104 dm de long, 96 dm de haut et 84 dm de profondeur. On décide de ranger 9 caisses dans cet entrepôt dont 4 de dimensions (70, 104, 84), 2 de dimensions (14, 104, 48) et 3 de dimensions (40, 52, 36). BOXLIST[]Array

*Boxlist[x]*	*Packst*	N	*Dim1*	*Dim2*	*Dim3*	*Cox*	*Coy*	*Coz*	*Packx*	*Packy*	*Packz*	*Vol*
Boxlist[1]	0	4	70	104	24	0	0	0	0	0	0	174720
Boxlist[2]	0	4	70	104	24	0	0	0	0	0	0	174720
Boxlist[3]	0	4	70	104	24	0	0	0	0	0	0	174720
Boxlist[4]	0	4	70	104	24	0	0	0	0	0	0	174720
Boxlist[5]	0	2	14	104	48	0	0	0	0	0	0	69888
Boxlist[6]	0	2	14	104	48	0	0	0	0	0	0	69888
Boxlist[7]	0	3	40	52	36	0	0	0	0	0	0	74880
Boxlist[8]	0	3	40	52	36	0	0	0	0	0	0	74880
Boxlist[9]	0	3	40	52	36	0	0	0	0	0	0	74880

Après avoir entrée les variables entrantes, le modèle détermine les hauteurs des couches et les entre dans un tableau, le `'Layers[]». Ce tableau contient une dimension de chaque boîte moins la dimension y de l'espace de stockage. Le tableau LAYERS[] est créé après l'examen de chaque orientation des boîtes.

Avec le même exemple, voyons maintenant comment obtenir les valeurs des champs dans le tableau Layers[].

Normalement il y aurait 8 valeurs au total, mais comme la dimension y de certaines boîtes est supérieure à celle de l'espace de stockage, on ne peut pas évaluer ça comme une hauteur de la couche.

Après l'obtention des valeurs du Layer[], on les trie dans l'ordre croissant d'après chaque Layereval.

Comme la plus petite Layereval peut être la hauteur la plus convenable pour une couche, trier la liste de ces champs selon l'ordre croissant est un facteur important dans le but de réduire le temps d'exécution d'une solution, spécialement lorsqu'on veut charger un nombre élevé de boîte de différentes tailles.

Les itérations de cet algorithme sont liées aux six orientations possibles que peut prendre une boîte. Pendant les itérations, les boîtes sont d'abord chargées dans toutes les six orientations. Chaque orientation de la boîte est considérée comme une solution de chargement. Evidemment si toutes les trois dimensions d'une boîte sont identiques, c'est-à-dire si la boîte est carrée, il n'y a qu'une seule orientation possible. Généralement on a soit un, deux ou six orientations respectivement pour un, deux ou trois dimensions différentes. Dans chaque itération, chaque orientation de la boîte est chargé une fois dans chaque champs du tableau `'Layers[]».

Ainsi, comme dans notre exemple, nous avons sept différentes dimensions dans notre tableau `'Layers[]`' et que toutes nos boîtes on trois dimensions uniques,

l'algorithme va effectuer 6*7=42 itérations. Ainsi, le temps d'exécution de cet algorithme dépend du type de boîte (celles avec une dimension, deux dimensions ou trois dimensions) et du nombre total des boîtes à charger. Le nombre de boîtes identiques (celle avec les mêmes dimensions) n'affecte pas directement le temps d'exécution de cet algorithme.

Maintenant, nous pouvons déterminer la complexité de l'algorithme HI-BHA. Supposons que nous avons n boîtes dans un ensemble de boîtes et d, la valeur des dimensions de toutes les boîtes. Dans le pire de cas, le temps d'exécution sera :

Où E(t) est le temps utilisé pour examiner l'orientation d'une boîte. E(t) dépend

Ainsi, la complexité de cet algorithme est Ø(n^k) avec comme k une constante et toujours égale à 2.

Dans cette section de notre travail, nous présentons un autre algorithme heuristique que nous n'allons pas implémenter suite au temps qui nous est insuffisant mais dont les résultats seront comparés au premier. Le LAFF algorithme résout lui aussi le 3DBPP en un temps polynomial. Nous allons présenter cet algorithme en définissant de prime à bord les variables entrantes et sortantes. Cet algorithme est

appelé LAFF minimizing heigth. Il place les boîtes à une plus grande surface en minimisant la hauteur du container.

La première variable à entrer est le nombre de boîtes de taille différentes noté N. La deuxième entrée c'est les dimensions de chaque type des boites de tailles différentes. Nous notons cela par quatre paramètres (an, bn, cn, kn) où an est la largeur, bn est la profondeur, cn est la hauteur et kn, le nombre de boîtes pour une dimension donnée.

Comme vous pouvez le voir sur une boîte, chaque dimension peut être considérée en largeur, en hauteur ou profondeur. Si vous prenez bn comme la largeur, les autres dimensions c'est-à-dire an et cn peuvent être acceptés comme hauteur ou profondeur. Parce que, la boîte est tridimensionnelle et elle peut être roté et peut être envisagé en des perspectives différentes. La liste suivante montre les paramètres à entrer proposés par l'algorithme :

Après l'exécution de l'algorithme LAFF, le programme doit produire les outputs ci-après :

Comme déjà signalé le problème de 3D bin packing est du genre NP-Complet, c'est-à-dire que la solution optimum pour ce problème ne peut être trouvée qu'après avoir essayé toutes les combinaisons possibles. C'est donc un problème difficile. Cependant, si le nombre de boîtes augmente au fur et à mesure, le nombre d'itérations augmentent aussi au point qu'il ne peut pas être résolu en temps polynomial même par l'ordinateur le plus rapide possible qui puisse exister à nos jours. Mais alors, avec quelques suppositions, ces genres de problèmes peuvent être résolus par des algorithmes heuristiques en un temps presque polynomial et fournir une solution près de l'optimum.

L'algorithme LAFF minimizing hieght proposé ci-dessus utilise une heuristique qui place la boîte dans le container en ne prenant pas en compte sa hauteur. Cet algorithme fonctionne de la manière ci-après :

De prime à bord, la largeur et la profondeur de l'espace de stockage doivent être déterminées. Ainsi, en donnant un ensemble de boîtes de tailles différentes, on calcule la profondeur et la largeur de l'espace de stockage et on trouve le plus long des deux bords des boîtes. La largeur et la profondeur de l'espace sont déterminées au début de l'algorithme et restent fixes jusqu'à la fin de son exécution. On suppose ici que la hauteur reste illimitée, elle augmente au fur et à mesure que l'algorithme s'exécute.

Etant ainsi, la largeur (ak) et la profondeur (bk) de l'espace sont trouvées en sélectionnant le premier et deuxième plus long bord des boîtes (ai, bi et ci). Le plus long est pris comme largeur (ak) et le deuxième comme profondeur (bk). Donc ak et bk ne changent jamais.

Après avoir déterminé les valeurs de la largeur et de la profondeur de l'espace de stockage, les boîtes peuvent être placées dans le contenant. Dans cet algorithme, deux méthodes de placement sont utilisés. Le premier est alloue un espace à chaque boîte entrante, ce qui augmente la hauteur du contenant. La deuxième méthode alloue un espace aux boîtes restantes s'il y a une boîte qui convient parfaitement dans l'espace encore disponible autour des boîtes déjà placées sans dépasser la hauteur de la boîte placé.

Dans la première méthode de placement, les boîtes ayant la plus grande surface sont déterminées, les boîtes sont sélectionnées pour essayer de trouver la boîte qui a la hauteur minimum dans toutes boîtes sélectionnées. Ainsi, la boîte ayant la hauteur minimum est placée dans le contenant. La plus grande boite sélectionnée doit être en parallèle avec le fond du contenant.

Dans la seconde méthode, les objets sont placés dans un ordre et l'algorithme essaie d'allouer un espace aux boîtes restantes autour de la boîte déjà placée (selon la première méthode). Ainsi, pour les espaces restants autour de la boîte déjà placée comme le montre la figure 7, l'algorithme essaie de les remplir d'après la deuxième méthode de placement. Selon cette méthode, étant donné que les boîtes ont des

dimensions ai, bi et ci sur un niveau, l'espace de stockage aura deux espaces vides autour de la boîte déjà placé avec les dimensions ((ak-ai),bk,ci) et (ak,(bk-bi),ci). Donc s'il y a une boîte qui convient parfaitement dans l'espace non alloué, ça peut être une boîte ou plus, on place la boîte qui a le volume maximum à côté de la boîte comme le montre la figure 7. Cette répétition continue jusqu'à ce qu'il n'y ait aucune boîte qui convient dans l'espace vide.

Dans la deuxième méthode de placement, s'il n'y a pas d'espace autour de la boîte placée, alors l'algorithme continue d'après la première méthode.

A chaque fois qu'il y a des boîtes non encore placées, l'algorithme va à la première méthode de placement et ainsi de suite jusqu'à ce que toutes les boîtes soient placées. À la fin de l'algorithme, une solution possible comme le montre la figure 8 est produite.

Etape 2 : Déterminer la largeur (ak) et la profondeur (bk) de l'espace de stockage

Etape 3 : choisir la boîte la plus volumineuse. S'il y en a beaucoup, choisir celle

ayant la plus petite hauteur. Placer cette boîte (ith) à l'endroit le plus large en

Etape 3.1 : Déterminer la hauteur de l'espace de stockage et décrémenter le nombre

Etape 3.3 : si l'espace (ak-ai)=0 et (bk-bi)=0 aller à l'étape 3. Par contre, choisir la boîte capable de remplir convenablement l'espace restant. S'il y a plus d'une boîte capable de convenir dans l'espace restant, choisir la boîte la plus volumineuse. Cette boîte est appelée jth.

Etape 3.3.3 : si le nombre des boîtes devient égal à 0 alors terminer. Sinon, aller à l'étape 3.3.

Si on considère n comme le nombre de toutes les boîtes à être placées dans l'espace de stockage et k comme le type de différentes boîtes de tailles différentes, la durée d'exécution pour le cas le pire de cette exécution est exprimé de la manière suivante :

Chapitre Quatrième : PROTOTYPAGE, EXPERIMENTATION
ET ARGUMENTATION DES RESULTATS

Ce chapitre sera pour nous une opportunité de présenter la traduction de l'algorithme HI-BHA dans le langage C, nous allons présenter les fonctions utilisées dans le programme et les fichiers des données. Cette partie de notre travail sera pour nous aussi une occasion de présenter le test de l'algorithme HI-BHA et l'argumentation du résultat, c'est-à-dire l'évaluation de celui-ci par rapport au LAFF algorithme.

VI.1. Prototypage

VI.1.1. Les fonctions du programme

Findsmallestz Détermine le vide ayant la valeur z le plus petite dans la courante

Findbox Sert à trouver la boîte qui remplit le mieux le vide courant dans la
couche

Analyzebox Cette fonction est utilisée par la précédente pour analyser les
dimensions des boîtes

Checkfound Détermine quelle boîte charger d'après sa capacité à remplir le
vide

Outputboxlist Ecrit les informations de la solution de chargement dans un fichier

La fonction `'Findbox» analyse les boîtes non encore chargées en utilisant la fonction `'Analyzebox». Pour chaque orientation de la boîte non encore chargée, la fonction Analyzebox utilise les paramètres suivants :

Hz : profondeur (dimension z) de la courante couche pour le chargement
Hmz : profondeur maximum (dimension z) disponible pour le chargement

Dim2 : dimension y de la boîte à examiner après orientation Dim1 : dimension z de la boîte à examiner après orientation

La fonction AnalyzeBox cherche, par ordre de priorité, une boîte ayant une hauteur qui est proche de Hy mais pas supérieur à Hmy, une longueur proche mais pas supérieure à Hmx et une largeur proche de Hz mais pas supérieur à Hmz. Ceci

veut dire que cette fonction considère d'abord la hauteur (y dimension), donc, parmi les boîtes qui ont une même hauteur, elle vérifie les longueurs (x dimension) et finalement parmi les boîtes ayant la même longueur et la même hauteur, elle vérifie la profondeur (z dimension). Cette fonction calcule les différences entre le volume encore disponible dans la couche (c'est-à-dire le vide) et le volume de chaque boîte, à la fin, elle récupère la boîte qui génère une moindre différence pour un meilleure remplissage. Elle cherche aussi les boîtes ayant une y-dimension supérieure mais proche de la hauteur de la couche courante. Les boîtes qui conviennent, celle qui ont la hauteur appropriée sont chargées. Celles qui ne conviennent pas nécessitent, en effet, une autre considération.

Dans l'algorithme HI-BHA, une méthode appelée `'Layer-in-layer packing`' ceci pour dire chargement d'une couche dans une couche. Layer-in-Layer est une fonction qui crée une couche au sein d'une autre. Cette fonction permet de loger la boîte ayant la hauteur qui ne convient pas à la couche. Si aucune boîte de convient dans le vide, ce vide est considérée comme perdue.

Dans la fonction `'FindBox`', la hauteur de la couche est adaptée au y-dimension de la plus haute boîte. Quand la hauteur de la courante couche augmente, le total des incrémentations de la couche du début à la fin du chargement des boîtes dans cette couche est stocké dans la variable layerinlayer. A la fin du chargement des boites dans cette couche, si la variable layerinlayer est supérieure à zéro, un autre chargement dans la couche est entrepris. Quand, le Layer-in-layer packing`' est utilisé, le modèle utilise beaucoup de volume.

Après chaque chargement, le volume des boîtes chargées ainsi que le volume des boîtes non chargé sont calculés afin d'obtenir le taux d'utilisation de l'entrepôt et la

pourcentage du volume des boîtes chargées. La solution avec un meilleur taux d'utilisation est considérée comme la solution finale.

Après qu'on ait obtenu tous les paramètres de la meilleure solution, la fonction `'Report`' est appelée. Cette fonction ré exécute le chargement avec les paramètres de la meilleure solution trouvée et appelle la fonction `'Outputboxlist`' pour générer le rapport (fichier) et `'Graphunpackedout`' pour générer le fichier input de la visualisation. Les informations sur les boîtes non chargées sont affichées à la fin du rapport.

IV.1.2. Formulaire d'entrées des données

Avant de lancer le programme console codé en C, il faut s'assurer que toutes les informations concernant l'entrepôt et les articles (boîtes 3D) à entreposé sont déjà spécifiées par l'utilisateur dans un fichier texte (avec l'extension .txt). Ce fichier doit être enregistré dans le même répertoire que l'exécutable (fichier .exe).

paramètres x, y et z qui sont respectivement la longueur, la hauteur et la profondeur

de l'entrepôt. L'ordre la succession de ces valeurs est d'une importance capitale. Toutes les lignes suivantes comportent les informations concernant les boîtes. Dans chaque ligne, la première valeur représente l'étiquette de la boîte, cette valeur n'a aucun effet sur l'algorithme. La deuxième, troisième et quatrième valeur sont les dimensions x, y et z de la boîte. Ces valeurs sont prises comme tel lorsque le programme aura jugé une orientation comme étant convenable. Le cinquième élément c'est le nombre de boîte de ce type. De toute façon, les virgules entre les chiffres ne sont pas obligatoires, même un simple espacement peut délimiter deux valeurs.

IV.1.3. Les rapports

Ce programme génère au total trois fenêtres. Le premier c'est le console, elle nous permet d'entrer le nom du fichier (.txt) à traiter.

La deuxième fenêtre contient le rapport de la meilleure solution et l'orientation de chaque boîte après chargement. A la fin de ce rapport, on trouve la liste de toutes les boîtes qui n'ont pas eu de place dans l'entrepôt. Ce rapport est du type .OUT, il peut être ouvert avec Mozilla firefox, google chrome, etc, il est créé après exécution du fichier des variables entrantes dans le même dossier que le fichier exécutable du programme et porte le même nom que le fichier d'entrées des variables. Il comporte toutes les informations nécessaires sur le chargement.

La troisième fenêtre est un fichier du type (.txt) qui est créée lui aussi après exécution d'un cas. Elle comporte les coordonnées et les orientations des boites chargées et celles de l'entrepôt. C'est ce qui fichier qui permet à l'interface graphique que nous n'avons pu créer d'avoir une vue 3D de la solution. Il comporte, en effet, toutes les variables entrantes dont le programme de l'interface graphique a besoin. Il est enregistré dans le même répertoire que le fichier exécutable et porte le nom du fichier d'entrée des données privé de la première initiale pour éviter le doublon.

Figure 14 : Fichier des variables entrantes de l'interface graphique du programme

IV.2. Expérimentation et Argumentation

L'informatique reste une science de l'ingénieur, ce qui signifie ici, que malgré toutes les études ou les critères théoriques permettant de comparer l'efficacité de deux algorithmes dans l'absolu, dans la pratique nous ne pourrons pas dire qu'il y a un meilleur algorithme pour résoudre tel type de problème. Une méthode pouvant être lente pour certaines configurations de données et dans une autre application qui travaille systématiquement sur une configuration de données favorables la méthode peut s'avérer être la "meilleure".

IV.2.1. Environnement de travail

L'efficacité d'un algorithme est directement liée au programme à implémenter sur un ordinateur. Le programme va s'exécuter en un temps fini et va mobiliser des ressources mémoires pendant son exécution; ces deux paramètres se dénomment complexité temporelle et complexité spatiale.

Le programme de résolution du problème d'optimisation d'entreposage des articles 3D a été conçu en utilisant le langage de programmation C. L'expérimentation a été effectuée sur une machine de configuration suivante :

(IDE), nous l'avons trouvé idéal parce qu'il combine en lui seul l'éditeur de code, le compilateur et le débugger, il nous a permis d'écrire facilement le code source du programme (en C), de transformer ("compiler") notre code source en code binaire et de traquer les erreurs dans notre code.

IV.2.2. Données de test

Nous avons testé notre problème en utilisant douze ensembles différents d'articles. Nous avons pris ces ensembles aléatoirement, mais en respectant les limites numériques de l'algorithme et nous nous sommes arrangés de manière à ce que les boites à entreposer contiennent exactement dans l'espace de stockage pour mieux tester la performance de l'algorithme. Vous pouvez trouver en annexe 1, les détails sur chaque cas que nous avons testé comprenant la liste d'articles et les dimensions de l'entrepôt.

IV.2.3. Résultat de l'algorithme HI-BHA

Apres usage du logiciel issu de cette recherche les résultats suivants ont été observés des chacun des algorithmes (Tableau 6).

Vous pouvez trouver en annexe 1, les détails sur chaque cas que nous avons testé.

IV.2.4. Argumentation sur les résultats de l'algorithme HI-BHA

De ce tableau, nous constatons que cet algorithme donne des bons résultats par apport aux facteurs temps et espace utilisé. En effet, pour presque toutes les instances, les temps d'exécution de l'algorithme sont tous inférieurs à une minute, et les pourcentages de l'espace utilisé sont généralement supérieurs à 85%, sauf pour le pire de cas où, la performance de l'algorithme baisse mais reste acceptable. Donc, Plus le nombre de types de boîtes augmente, plus la performance de l'algorithme diminue et son temps d'exécution augmente. Nous avons jeté un coup d'oeil sur les résultats de l'algorithme LAFF et avons constaté que les deux algorithmes semblent identiques au point de vue temps d'exécution et espace utilisé, ce qui est normal vu leurs complexités qui sont toutes d'ordre n². Mais alors, un autre paramètre comme le non pris en charge de la hauteur de l'espace d'entreposage nous pousse à opter pour l'algorithme HI-BHA vu que les entrepôts dont nous faisons allusion dans ce travail sont tous en 3 dimensions, c'est-à-dire qu'ils possèdent tous une longueur, une largeur et une hauteur finie.

IV.3. DIFFICULTES RENCONTREES

Au cours de l'élaboration de ce travail nous nous sommes heurtés à des difficultés ci-après :

- Nous n'avons pas pu implémenter l'algorithme LAFF, faute de ressources temporelles, mais nous avons pris les résultats de cet algorithme testé sur un environnement presque similaire au nôtre à partir de l'article de (Gürbüz, Akyokuþ, Emiroðlu, & Güran, 2009), ce qui nous a permis d'avoir une idée sur les performances de l'algorithme.

- Nous avons eu du mal à produire l'interface graphique du modèle HI-BHA, faute du compilateur qui manquait les bibliothèques graphics.h et Xlib.h que nous n'avons pas pu nous procurer. Mais nous avons réussi à générer un fichier (.OUT) où une zone présentant une sélection de colis avec leurs positions et leurs orientation, qui remplit plutôt bien l'entrepôt est disponible.

- Nous n'avons pas pu tester l'algorithme en fonction des cas réels de la ville de Butembo. Nous nous sommes heurtés à des difficultés dans la récolte des données, en fait, beaucoup de magasinier d'ont aucune idée sur les dimensions des entrepôts, moins encore des articles. Mais nous avons testé l'algorithme sur des données générées aléatoirement tout en respectant les contraintes liées à l'algorithme.

CONCLUSION

L'optimisation d'entreposages des articles tridimensionnels dans des aires d'entreposage est un facteur assez important pour réduire les coûts liés à l'emmagasinage des produits commerciaux et industriels. Afin d'être compétitif sur le marché, les entreprises ont besoin d'un outil puissant pour réduire l'ensemble de leurs dépenses.

Dans ce travail intitulé `'Optimisation heuristique du problème d'entreposage d'objets en trois dimensions`', notre soucis était de trouver réponse à la question de savoir s'il existe une méthode capable de ranger les objets 3D dans des espaces de stockage 3D de manière maximiser l'espace disponible, le but étant de proposer une méthode efficace pour optimiser le chargement des boîtes. La grande complexité de ce problème et la présence de nombreuses littératures dans ce domaine nous ont dissuadées de construire nos idées à partir des méthodes déjà prouvés et jugés performantes.

Etant donné que le problème d'entreposage que nous traitons dans ce travail est un problème NP-Difficile et par conséquent très complexe à résoudre en un temps polynomiale, nous avons proposé dans ce travail une méthode heuristique du problème 3D Bin packing. Nous avons analysé deux algorithmes d'approximation, le Largest Area First-Fit et le fameux Human Intelligence-Based Heuristic Approach. Tous les deux algorithmes ont été jugés polynomiaux. Mais alors, nous avons proposé un seul algorithme qui est le Human Intelligence-Based Heuristic Approach

pour les avantages qu'il offre, entre autre la prise en compte des rotations d'articles et la considération de la hauteur du contenant.

Nous avons proposé l'algorithme HI-BHA qui est une méthode d'approximation qui résout le problème 3DBP ; nous l'avons présenté sous forme d'ordinogramme. Un prototype d'application codé en langage C a été mis en place pour traduire l'algorithme en programme d'application. Nous avons testé ce modèle et les résultats nous ont montré que le modèle est bel et bien efficace en donnant des réponses près de l'optimum allant jusqu'à utiliser 100% de l'espace de stockage en temps très réduit. Si le modèle proposé venait à être concrétisé dans les entreprises commerciales et industriels qui sont concernées par les entreposages d'objets en 3D, nous osons croire qu'il sera capable de résoudre le problème ci-haut évoque, celui de permettre à chaque entrepôt de contenir plus d'articles 3D possible et ainsi réduire les coûts liés à l'entreposage d'articles.

Loin d'imaginer avoir touché tous les aspects, nous restons ouverts à toutes les avancées sur ce domaine. En effet, nous ne prétendons pas avoir proposé le modèle le plus parfait qui puisse exister. Ainsi donc, tout autre chercheur intéressé dans ce domaine pourra trouver une autre méthode plus efficace que celui-ci. Nous suggérons aussi à tous les travaux futurs de prendre en compte d'autres paramètres comme le poids des boîtes, le prix et la durée de vie des produits qui est limitée, l'idéal serait de pouvoir ranger d'abord les boîtes avec un prix élevé et une courte durée de vie dans l'entrepôt. Ainsi, nous invitons tous les autres chercheurs à nous emboîter le pas et restons réceptifs à toutes les remarques et suggestion.

BIBLIOGRAPHIE

Baltacioglu, E. (2002). The distributer's Three-dimensional pallet-packing. Washington DC: Air force institute of technologie.

Clautiaux, F. (2010). New collaborative approaches for bin-packing problems. Lille, France: Université des sciences et technologies de Lille.

Divay, M. (2004). Algorithmes et structures de données génériques. Paris, France: Dunod.

Dube, E., & Kanavathy, L. R. (2006). Optimizing three-dimensional bin packing through simulation. Durban, South Africa: University of KwaZulu-Natal.

Gazdar, M. (2008). Optimisation heuristique distribuée du problème de stockage de conteneurs dans un port. Lille, France: Ecole centrale de lille.

Gürbüz, Z., Akyokuþ, S., Emiroðlu, t., & Güran, A. (2009). An efficient Algorithm for 3D Rectangular Box packing. Republic of Macedonia: Society for ETAI.

Masivi, O. (2012). Cours de Laboratoire informatique II. Butembo, RDC: UNILUK.

Masivi, O. (2013). Approches méthodologiques de la recherche scientifique en informatique. Butembo, RDC: UNILUK.

Nzalamingi, F. (2012). Optimisation de la coupe et entreposage en une et deux dimensions.(memoire) Butembo, RDC: UNILUK.

Perrot, N. (2005). Integer Programming column generation strategies for the cutting stock problem and its variants. Bordeaux, France: University Bordeaux I.

Rohaut, S. (2007). Algorithmique: Techniques fondamentales de programmation. Edition ENI.

Sanni, L. (2009). Le rôle du système d'information dans les entreprises d'aujourd'hui. Consulté en Mars 2013, sur lookouster: http://www.lookouster.org/blog/ role_systeme_information

Scala, R. d. (2004). Les bases de l'informatique et de la programmation. Alger: Edition Berti.

Wattebled, P. (2010). Résolution heuristique d'un problème de conception de modules automatiques de rangement. Lille, France: INRIA.

ANNEXES

ANNEXE A : DONNEES DE TEST

Ensemble N^° 7				Ensemble N^° 8
104, 96, 84				104, 96, 84
1. 19, 20, 42,		2		1.	1, 2, 3, 1
2.	25, 20, 30,	1		2.	4, 5, 6, 1			3.
25, 20, 25,	1		3.	7, 8, 9, 1
4.	25, 20, 29,	1		4.	10,	11, 12,	1
5.	8, 20, 21, 4			5.	13,	14, 15,	1
6.	36, 46, 84,	1		6.	16,	17, 18,	1
7.	16, 46, 10,	2		7.	19,	20, 21,	1
8.	16, 46, 32,	2		8.	22,	23, 24,	1
9.	20, 30, 15,	1		9.	25,	26, 27,	1
10.	20, 30, 69,	1		10.	28,	29, 30,	1
11.	20, 30, 21,	4		11.	31,	32, 33,	1
12.	12, 30, 7,	12		12.	34,	35, 36,	1
13.	52, 60, 42,	2		13.	37,	38, 39,	1
14.	26, 36, 21,	4		14.	40,	41, 42,	1
15.	26, 36, 84,	1		15.	43,	44, 45,	1
				16.	46,	47, 48,	1
				17.	2,	3, 4, 1
				17.	2,	3, 4, 1
				18.	5,	6, 7, 1
				19.	8,	9, 10, 1
				20.	11,	12, 13,	1
				21.	14,	15, 16,	1
				22.	17,	18, 19,	1
				23.	20,	21, 22,	1
				24.	23,	24, 25,	1
				25.	26,	27, 28,	1
				26.	29,	30, 31,	1
				27.	32,	33, 34,	1
				28.	35,	36, 37,	1
				29.	38,	39, 40,	1
				30.	41,	42, 43,	1
				31.	44,	45, 46,	1

ANNEXE B : CODES C DE QUELQUES FONCTIONS DE L'ALGORITHME HUMAN INTELLIGENCE - BASED HEURISTIC APPROACH

printf("(ASSUREZ VOUS QUE VOUS AVEZ UN FICHIER .TXT CONTENANT LES VARIABLES ENTRANTES)\n");

printf ("ENTREZ LE NOM DU FICHIER D'ENTREES S.V.P :"); scanf ("%s",filename);

//lectures des coordonnées largeur, hauteur et profondeur entrées dans le fichier txt

char lbl[5], dim1[5], dim2[5], dim3[5], boxn[5], strxx[5], stryy[5], strzz[5];

%s",lbl,dim1,dim2,dim3,boxn)!=EOF){ boxlist[tbn].dim1=atoi(dim1); boxlist[tbn].dim2=atoi(dim2); boxlist[tbn].dim3=atoi(dim3);

bboxx=dim1; bboxy=dim2; bboxz=dim3; bbfx=hmx-dim1; bbfy=dim2-hy; bbfz=abs(hz-dim3); bboxi=x;

else if (dim2-hy==bbfy && hmx-dim1<bbfx) j bboxx=dim1; bboxy=dim2; bboxz=dim3; bbfx=hmx-dim1; bbfy=dim2-hy; bbfz=abs(hz-dim3); bboxi=x;

bboxx=dim1; bboxy=dim2; bboxz=dim3; bbfx=hmx-dim1; bbfy=dim2-hy; bbfz=abs(hz-dim3); bboxi=x;

//fonction exigée pour le fonctionnement de la fonction QSORT int complayerlist(const void *i, const void *j)j

//en cherchant les boites non encore chargées et l'espace vide //encore disponible

exdim=boxlist(x].dim1; dimen2=boxlist(x].dim2; dimen3=boxlist(x].dim3; break;

exdim=boxlist(x].dim2; dimen2=boxlist(x].dim1; dimen3=boxlist(x].dim3; break;

exdim=boxlist(x].dim3; dimen2=boxlist(x].dim1; dimen3=boxlist(x].dim2; break;

if ((exdim<=thickness) && (((dimen2<=px) && (dimen3<=pz)) || ((dimen3<=px) && (dimen2<=pz)))) j for(z=1;z<=tbn;z++)j

if (!(x==z) && !(boxlist(z].packst))j dimdif=abs(exdim-boxlist(z].dim1); if (abs(exdim-

itoa(px, strpx, 10); itoa(py, strpy, 10); itoa(pz, strpz, 10); fprintf(gfp,"%5s%5s%5s\n",strpx,strpy,strpz); strcat(filename,".out"); if ((ofp=fopen(filename,"w"))==NULL) j

percentagepackedbox=bestvolume*100/totalboxvol; percentageused=bestvolume*100/totalvolume;

fprintf(ofp," UTILISATION DU VOLUME :%.0f
SUR %.0f\n", bestvolume, totalvolume);

fprintf(ofp," POURCENTAGE DES BOITES CHARGEES (VOLUME) : %.6f %%\n",percentagepackedbox);

fprintf(ofp," NO: PACKSTA DIMEN-1 DIMEN-2 DIMEN-3 COOR-X COOR-Y COOR-Z PACKEDX PACKEDY PACKEDZ\n");

remainpy=layerthickness-prelayer; packedy=packedy-layerthickness+prelayer; remainpz=lilz; layerthickness=layerinlayer;

printf(" POURCENTAGE DES BOITES CHARGEES (VOLUME): %.6f %%\n",percentagepackedbox);

Optimisation heuristique du problème d'entreposage d'objets en trois dimensions.

Epigraphe

DEDICACE

REMERCIEMENTS

SIGLES ET ABBREVIATIONS

TABLE DES MATIERES

LISTE DES FIGURES

LISTE DES TABLEAUX

RESUME

ABSTRACT

INTRODUCTION GENERALE

0. Problématique de recherche

1. But et Objectif de recherche

2. Choix et intérêt du travail

3. Délimitation du sujet

4. Méthodes et technique de recherche

5. Subdivision du travail

Chapitre premier : REVUE DE LA LITTERATURE

I.1. Optimisation

I.2. Entrepôt et Entreposage

I.3. Les objets

I.3.1. Objet en une dimension

I.3.2. Objet en deux dimensions

I.3.3. Objet en trois dimensions

I.4. Quelques travaux de recherche étudiés

I.5. Conclusion partielle

Chapitre deuxième : METHODOLOGIE DU TRAVAIL

II.1.Methode Algorithmique

II.1.1. Problèmes algorithmiques

II.1.2. Classes de Complexité

II.2. Le Prototypage

II.3. L'Expérimentation

II.4. L'Argumentation

Chapitre Troisième : APPROCHES METHODOLOGIQUES

III.1. Modélisation algorithmique du problème de 3DBP

III.1.1. Formulation du problème

III.1.2. Méthodes exactes

III.1.3. Méthodes approximatives (heuristiques)

Chapitre Quatrième : PROTOTYPAGE, EXPERIMENTATIONET ARGUMENTATION DES RESULTATS

VI.1. Prototypage

VI.1.1. Les fonctions du programme

IV.1.2. Formulaire d'entrées des données

IV.1.3. Les rapports

IV.2. Expérimentation et Argumentation

IV.2.1. Environnement de travail

IV.2.2. Données de test

IV.2.3. Résultat de l'algorithme HI-BHA

IV.2.4. Argumentation sur les résultats de l'algorithme HI-BHA

IV.3. DIFFICULTES RENCONTREES

CONCLUSION

BIBLIOGRAPHIE

ANNEXES

ANNEXE A : DONNEES DE TEST

Chapitre Quatrième : PROTOTYPAGE, EXPERIMENTATION
ET ARGUMENTATION DES RESULTATS