Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions
RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 87-101.

Nous nous intéressons dans cet article au problème de découpe guillotine en deux dimensions noté 2BP/O/G. Il s'agit de découper un certain nombre de pièces rectangulaires dans un ensemble de plaques de matière première, elles même rectangulaires et identiques. Celles-ci sont disponibles en quantité illimitée. L'objectif est de minimiser le nombre de plaques utilisées pour satisfaire la demande, en appliquant une succession de coupes, dites guillotines, allant de bout en bout. Nous proposons une approche de résolution combinant l'optimisation par colonies de fourmis (ACO) et l'heuristique SHF-FF de Ben Messaoud et al. [2] pour résoudre ce problème NP-difficile.

In this paper, we are interested in the guillotine bin packing problem (2BP/O/G). The aim of this problem is to cut a set of rectangular pieces (items) from a set of identical large rectangular pieces (stock sheets). We try to minimize the number of stock sheets used in order to satisfy the demand. This is done applying edge to edge cut, which is called the guillotine constraint. We propose in this paper a resolution approach using Ant Colony Optimization (ACO) and the SHF-FF heuristic of Ben Messaoud et al. [2] in order to solve this NP-hard problem. We improve the best known results.

DOI : 10.1051/ro/2009006
Classification : 05B40, 52C15, 90C27
Mots-clés : colonies de fourmis, découpe, guillotine, optimisation, bin packing 
@article{RO_2009__43_1_87_0,
     author = {Yalaoui, Alice and Chu, Chengbin},
     title = {Optimisation hybride par colonies de fourmis pour le probl\`eme de d\'ecoupe \`a deux dimensions},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {87--101},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     doi = {10.1051/ro/2009006},
     mrnumber = {2502326},
     zbl = {1158.05313},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2009006/}
}
TY  - JOUR
AU  - Yalaoui, Alice
AU  - Chu, Chengbin
TI  - Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 87
EP  - 101
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2009006/
DO  - 10.1051/ro/2009006
LA  - en
ID  - RO_2009__43_1_87_0
ER  - 
%0 Journal Article
%A Yalaoui, Alice
%A Chu, Chengbin
%T Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 87-101
%V 43
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2009006/
%R 10.1051/ro/2009006
%G en
%F RO_2009__43_1_87_0
Yalaoui, Alice; Chu, Chengbin. Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 87-101. doi : 10.1051/ro/2009006. http://www.numdam.org/articles/10.1051/ro/2009006/

[1] S. Ben Messaoud, C. Chu and M.L. Espinouse, Une nouvelle heuristique pour le problème de découpe guillotine en 2D, in Proc.MOSIM'03, Toulouse, France (2003) 116-121.

[2] S. Ben Messaoud, C. Chu and M.L. Espinouse, New concept of the classic shelf algorithm. Proc. IEPM'03, Porto, Portugal (2003) 465-471.

[3] J.O. Berkey and P.Y. Wang, Two dimensional finite bin-packing algorithms. J. Oper. Res. Soc. 38 (1987) 423-429. | Zbl

[4] F. Chung, M. Garey and D. Johnson, On packing two-dimensional bins. SIAM J. Algebr. Discrete Methods 3 (1982) 66-76. | MR | Zbl

[5] M. Dorigo, V. Maniezzo and A. Colorni, The ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26 (1996) 29-71.

[6] H. Dyckhoff, A typology of cutting and packing problems. Eur. J. Oper. Res. 44 (1990) 145-159. | MR | Zbl

[7] J. Levine and F. Ducatelle, Ant Colony optimization and local search for bin packing and cutting stock problems. J. Oper. Res. Soc. 55 (2004) 705-716. | Zbl

[8] A. Lodi, S. Martello and D. Vigo, Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, in Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I.H. Osman, C. Roucairol, Kluwer academic Publishers, Boston (1998) 125-139. | MR | Zbl

[9] A. Lodi, S. Martello and D. Vigo, Recent advances on two-dimensional bin packing problems. Discrete Appl. Math. 123 (2002) 379-396. | MR | Zbl

[10] A. Lodi, S. Martello and D. Vigo, Two-dimensional packing problems: A survey. Eur. J. Oper. Res. 141 (2002) 241-252. | MR | Zbl

Cité par Sources :