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

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.

Cordeau, B. (2006). Cours d'algorithme et Langage C. IUT d'Orsay.

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.

Nebra, M. (2010). Apprenez à programmer en C. Paris, France: Simple IT.

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.

Wikimedia Foundation. (2000). Problème de Bin-Packing. Consulté en Mai 2013, sur Wikipedia: http://fr.wikipedia.org/bin_packing

56

ANNEXES

ANNEXE A : DONNEES DE TEST

Ensemble N^° 1

104, 96, 84

1. 3, 5, 7, 51

2. 20, 4, 6, 90

3. 11, 21, 16, 80

4. 51, 2, 60, 80

5. 6, 17, 8, 6

Ensemble N^° 3

104, 96, 84

1. 3, 5, 7, 200

2. 9, 11, 2, 29

3. 14, 6, 8, 30

4. 1, 4, 19, 51

5. 10, 13, 21, 12

6. 27, 23, 34, 5

7. 12, 9, 13, 10

8. 24, 15, 19, 50

9. 5, 16, 9, 100

10. 10, 20, 5, 100

11. 9, 18, 15, 50

Ensemble N^° 2

104, 96, 84

1. 3, 5, 7, 200

2. 9, 11, 2, 290

3. 14, 6, 8, 300

4. 1, 4, 19, 748

5. 10, 13, 21, 190

Ensemble N^° 4

104, 96, 84

1. 1, 2, 3, 200

2. 2, 4, 5, 200

3. 6, 7, 1, 200

4. 6, 8, 2, 29

5. 11, 2, 3, 29

6. 9, 4, 2, 29

7. 14, 5, 3, 30

8. 10, 4, 6, 30

9. 11, 8, 3, 30

10. 1, 2, 19, 50

11. 8, 13, 11, 50

12. 1, 3, 21, 10

13. 8, 9, 10, 30

14. 7, 13, 31, 115

15. 12, 66, 3, 30

16. 4, 15, 19, 90

17. 5, 16, 9, 100

18. 10, 2, 5, 100

19. 10, 10, 1, 90

20. 9, 18, 15, 50

21. 6, 9, 14, 1

Ensemble N^° 5

104, 96, 84

1. 28, 32, 18, 9

2. 24, 21, 35, 16

3. 19, 26, 20, 4

4. 19, 26, 16, 16

5. 16, 26, 20, 4

6. 20, 20, 26, 1

7. 16, 14, 25, 36

Ensemble N^° 6

104, 96, 84

1. 70, 45, 24, 4

2. 70, 59, 24, 4

3. 14, 40, 48, 2

4. 14, 64, 48, 2

57

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

58

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

//les directives du préprocesseur

#include <time.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <malloc.h>

#include <conio.h>

//fonction main

int main(int argc, char *argv[]) j

if (argc == 1) j

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);

}

else

j

printf("%s", argv[1]);

strcpy(filename, argv[1]);

}

initialize();

time(&start);

printf("\nAPPUIYEZ SUR Q POUR ARRETER L'ITERATION\n\n");

execiterations();

time(&finish);

report();

getch();

return 0;

}

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

void inputboxlist(void)j

short int n;

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

strcpy(strtemp, filename);

strcat(strtemp,".txt");

if ((ifp=fopen(strtemp,"r"))==NULL) j

printf("Impossible d'ouvrir le fichier %s", strtemp);

exit(1);

}

tbn=1;

if (fscanf(ifp,"%s %s %s",strxx, stryy, strzz)==EOF)j exit(1);

}

xx=atoi(strxx); yy=atoi(stryy); zz=atoi(strzz);

59

while (fscanf(ifp,"%s %s %s

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

boxlist[tbn].vol=boxlist[tbn].dim1*boxlist[tbn].dim2*boxlist[t bn].dim3;

n=atoi(boxn);

boxlist[tbn].n=n;

while (--n){

boxlist[tbn+n]=boxlist[tbn];

}

tbn=tbn+atoi(boxn);

}

--tbn;

fclose(ifp);

return;

}

//recherche de la caisse la plus appropriée en cherchant toutes les

//six orientations possibles, l'espace vide donnée, les caisses

//adjacentes et la limite de l'entrepôt

void findbox(short int hmx, short int hy, short int hmy, short

int hz, short int hmz)

{

short int y;

bfx = 32767; bfy = 32767; bfz = 32767;

bbfx = 32767; bbfy = 32767; bbfz = 32767;

boxi = 0; bboxi = 0;

for (y = 1; y <= tbn; y = y + boxlist[y].n)

{

for (x = y; x < x + boxlist[y].n - 1; x++)

{

if (!boxlist[x].packst) break;

}

if (boxlist[x].packst) continue;

if (x > tbn) return;

analyzebox(hmx, hy, hmy, hz, hmz, boxlist[x].dim1,

boxlist[x].dim2, boxlist[x].dim3);

if ( (boxlist[x].dim1 == boxlist[x].dim3) &&

(boxlist[x].dim3 == boxlist[x].dim2) ) continue;

analyzebox(hmx, hy, hmy, hz, hmz, boxlist[x].dim1,

boxlist[x].dim3, boxlist[x].dim2);

analyzebox(hmx, hy, hmy, hz, hmz, boxlist[x].dim2,

boxlist[x].dim1, boxlist[x].dim3);

analyzebox(hmx, hy, hmy, hz, hmz, boxlist[x].dim2,

boxlist[x].dim3, boxlist[x].dim1);

analyzebox(hmx, hy, hmy, hz, hmz, boxlist[x].dim3,

boxlist[x].dim1, boxlist[x].dim2);

analyzebox(hmx, hy, hmy, hz, hmz, boxlist[x].dim3,

boxlist[x].dim2, boxlist[x].dim1);

}

}

//analyses de chaque caisse non chargée pour trouver le meilleure

//emplacement dans l'entrepôt

//recherche de la couche ayant la hauteur la plus appropriées

60

void analyzebox (short int hmx, short int hy, short int hmy,

short int hz, short int hmz, short int dim1, short int dim2,

short int dim3)j

if (dim1<=hmx && dim2<=hmy && dim3<=hmz)j

if (dim2<=hy) j

if (hy-dim2<bfy) j

boxx=dim1;

boxy=dim2;

boxz=dim3;

bfx=hmx-dim1;

bfy=hy-dim2;

bfz=abs(hz-dim3);

boxi=x;

}

else if (hy-dim2==bfy && hmx-dim1<bfx) j

boxx=dim1;

boxy=dim2;

boxz=dim3;

bfx=hmx-dim1;

bfy=hy-dim2;

bfz=abs(hz-dim3);

boxi=x;

}

else if (hy-dim2==bfy && hmx-dim1==bfx && abs(hz-

dim3)<bfz) j

boxx=dim1;

boxy=dim2;

boxz=dim3;

bfx=hmx-dim1;

bfy=hy-dim2;

bfz=abs(hz-dim3);

boxi=x;

}

}

else j

if (dim2-hy<bbfy) j

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;

}

else if (dim2-hy==bbfy && hmx-dim1==bbfx && abs(hz-dim3)<bbfz) j

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

return *(long int*)i-*(long int*)j;

}

}

61

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

int findlayer( short int thickness) j

short int exdim,dimdif,dimen2,dimen3,y,z; long int layereval, eval;

layerthickness=0;

eval=1000000;

for(x=1;x<=tbn;x++)j

if (boxlist(x].packst) continue; for(y=1;y<=3;y++)j

switch(y) j

case 1:

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

case 2:

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

case 3:

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

}

layereval=0;

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-

boxlist(z].dim2)<dimdif)j

dimdif=abs(exdim-

boxlist(z].dim2);

}

if (abs(exdim-

boxlist(z].dim3)<dimdif)j

dimdif=abs(exdim-

boxlist(z].dim3);

}

layereval=layereval+dimdif;

}

}

if (layereval<eval) j

eval=layereval;

layerthickness=exdim;

}

}

}

}

if (layerthickness==0 || layerthickness>remainpy) packing=0;

return 0;

62

//recherche du premier vide à être chargée

//au bord de la couche

void findsmallestz(void) j

scrapmemb=scrapfirst;

smallestz=scrapmemb;

while (!((*scrapmemb).pos==NULL)) j

if((*((*scrapmemb).pos)).cumz<(*smallestz).cumz)j

smallestz=(*scrapmemb).pos;

}

scrapmemb=(*scrapmemb).pos;

}

return;

}

//utilisation des paramètres trouvées pour le chargement de la

meilleure solution trouvée et envoie du rapport à la console

et au fichier OUT

void report(void)j

quit=0;

switch(bestvariant) j

case 1:

px=xx; py=yy; pz=zz;

break;

case 2:

px=zz; py=yy; pz=xx;

break;

case 3:

px=zz; py=xx; pz=yy;

break;

case 4:

px=yy; py=xx; pz=zz;

break;

case 5:

px=xx; py=zz; pz=yy;

break;

case 6:

px=yy; py=zz; pz=xx;

break;

}

packingbest=1;

if ((gfp=fopen(graphout,"w"))==NULL) j

printf("Impossible de lire le fichier %s", filename); exit(1);

}

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

printf("Impossible d'ouvrir le fichier %s", filename); exit(1);

}

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

elapsedtime = difftime( finish, start);

fprintf(ofp," *** RAPPORT DE LA MEILLEURE SOLUTION ***\n\n");

fprintf(ofp," TEMPS ECOULE

:environ %.0f sec\n", elapsedtime);

}

63

fprintf(ofp," itenum); fprintf(ofp,"	NOMBRE TOTAL D'ITERATIONS MEILLEURE SOLUTION TROUVEE A LA	: :	%d\n", %d
ITERATION\n", bestite); fprintf(ofp," NOMBRE TOTAL DE BOITES tbn); fprintf(ofp," NOMBRE DE BOITES CHARGEES bestpackednum);		: :	%d\n", %d\n",
fprintf(ofp,"	VOLUME TOTAL DE TOUTES LES BOITES:

%.0f\n",totalboxvol);

fprintf(ofp," VOLUME DE L'ENTREPOT :
%.0f\n",totalvolume);

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

fprintf(ofp," POURCENTAGE DE L'ESPACE UTILISE : %.6f
%%\n", percentageused);

fprintf(ofp," DIMENSIONS DE L'ENTREPOT :

X=%d; Y=%d; Z=%d\n", px, py, pz);

fprintf(ofp,"

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

\n");

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

fprintf(ofp," \n");

listcanditlayers();

layers[0].layereval=-1;

qsort(layers,layerlistlen+1,sizeof(struct

layerlist),complayerlist);

packedvolume=0.0;

packedy=0;

packing=1;

layerthickness=layers[bestite].layerdim;

remainpy=py;

remainpz=pz;

for (x=1; x<=tbn; x++){

boxlist[x].packst=0;

}

do{

layerinlayer=0; layerdone=0;

packlayer();

packedy=packedy+layerthickness;

remainpy=py-packedy;

if(layerinlayer){

prepackedy=packedy;

preremainpy=remainpy;

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

layerdone=0; packlayer();

packedy=prepackedy;

remainpy=preremainpy;

remainpz=pz;

}

if (!quit){

findlayer(remainpy);

}

64

while (packing && !quit);

fprintf(ofp,"\n\n*** LISTE DES BOITES NON CHARGEES ***\n");

unpacked=1;

for (cboxi=1; cboxi<=tbn; cboxi++)j if(!boxlist[cboxi].packst)j

graphunpackedout();

}

}

unpacked=0;

fclose(ofp);

fclose(gfp);

printf("\n");

for (n=1; n<=tbn; n++)

if (boxlist[n].packst)

printf("%d %d %d %d %d %d %d %d %d %d\n",n,

boxlist[n].dim1,boxlist[n].dim2,boxlist[n].dim3,boxlist[n].cox

,boxlist[n].coy,boxlist[n].coz,boxlist[n].packx,boxlist[n].pac

ky,boxlist[n].packz);

printf(" TEMPS ECOULE : environ
%.0f sec\n",elapsedtime);

printf(" NOMBRE TOTAL D'ITERATIONS : %d\n",

itenum);

printf(" MEILLEUR RESULTAT TROUVE A :

ITERATION: %d\n", bestite);

printf(" NOMBRE TOTAL DES BOITES : %d\n",

tbn);

printf(" NOMBRE TOTAL DES BOITES CHARGEES : %d\n",bestpackednum);

printf(" VOLUME TOTAL DE TOUTES LES BOITES : %.0f\n",totalboxvol);

printf(" VOLUME DE L'ENTREPOT : %.0f\n",
totalvolume);

printf(" UTILISATION DU L'ESPACE : %.0f SUR
%.0f\n", bestvolume, totalvolume);

printf(" POURCENTAGE SU VOLUME TOTAL UTILISE: %.6f %%\n",percentageused);

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

printf(" DIMENSIONS DE L'ENTREPOT : X=%d;
Y=%d; Z= %d\n\n\n", px, py, pz);

printf(" POUR VOIR CETTE SOLUTION EN GRAPHIQUE, EXECUTEZ 'VISUAL.EXE'\n");

}

printf(" DESOLE QUE CELA N'ACCEPTE PAS POUR LE MOMENT, NOUS NOUS EXCUSONS\n");