Algorithms for the two dimensional bin packing problem with partial conflicts
RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 41-62.

The two-dimensional bin packing problem is a well-known problem for which several exact and approximation methods were proposed. In real life applications, such as in Hazardous Material transportation, transported items may be partially incompatible, and have to be separated by a safety distance. This complication has not yet been considered in the literature. This paper introduces this extension called the two-dimensional bin packing problem with partial conflicts (2BPPC) which is a 2BP with distance constraints between given items to respect, if they are packed within a same bin. The problem is NP-hard since it generalizes the BP, already NP-hard. This study presents a mathematical model, two heuristics and a multi-start genetic algorithm for this new problem.

DOI : 10.1051/ro/2012007
Classification : 05-XX, 90-XX
Mots-clés : bin-packing, distance constraint, conflicts, genetic algorithm 
@article{RO_2012__46_1_41_0,
     author = {Hamdi-Dhaoui, Khaoula and Labadie, Nacima and Yalaoui, Alice},
     title = {Algorithms for the two dimensional bin packing problem with partial conflicts},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {41--62},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ro/2012007},
     mrnumber = {2934892},
     zbl = {1241.90109},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2012007/}
}
TY  - JOUR
AU  - Hamdi-Dhaoui, Khaoula
AU  - Labadie, Nacima
AU  - Yalaoui, Alice
TI  - Algorithms for the two dimensional bin packing problem with partial conflicts
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2012
SP  - 41
EP  - 62
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2012007/
DO  - 10.1051/ro/2012007
LA  - en
ID  - RO_2012__46_1_41_0
ER  - 
%0 Journal Article
%A Hamdi-Dhaoui, Khaoula
%A Labadie, Nacima
%A Yalaoui, Alice
%T Algorithms for the two dimensional bin packing problem with partial conflicts
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2012
%P 41-62
%V 46
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2012007/
%R 10.1051/ro/2012007
%G en
%F RO_2012__46_1_41_0
Hamdi-Dhaoui, Khaoula; Labadie, Nacima; Yalaoui, Alice. Algorithms for the two dimensional bin packing problem with partial conflicts. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 41-62. doi : 10.1051/ro/2012007. http://archive.numdam.org/articles/10.1051/ro/2012007/

[1] O. Beaumont, N. Bonichon and H. Larchevêque, Bin packing under distance constraint. Technical Report, Université de Bordeaux, Laboratoire Bordelais de Recherche en Informatique, INRIA Bordeaux Sud-Ouest (2010).

[2] S. Ben Messaoud, C. Chu and M.L. Espinouse, An approach to solve cutting stock sheets. Scottish Mathematical Council 6 (2004) 5109-5113.

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

[4] E.G. Coffman, M.R. Garey and D.S. Johnson, Approximation algorithms for bin-packing - an updated survey, in Algorithm design for computer system design, edited by G. Ausiello, M. Lucertini and P. Serafini. Springer, Vienna (2007). | Zbl

[5] Environment Canada, Compliance promotion bulletin (Compro No. 12), regulations for the management of hazardous waste (2002).

[6] A.E. Fernandes-Muritiba, M. Iori, E. Malaguti and P. Toth, Algorithms for the bin packing problem with conflicts. Informs J. Comput. 22 (2010) 401-415. | MR | Zbl

[7] M. Gendreau, G. Laporte and F. Semet, Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31 (2004) 347-358. | MR | Zbl

[8] J. Goupy, Les plans d'expériences. Revue Modulad 34 (2006) 74-116.

[9] J.H. Holland, Adaptation in natural and artifficial systems. University of Michigan Press, Ann Arbor, MI (1975) 1-211. | MR | Zbl

[10] K. Jansen, An approximation Scheme for Bin Packing with conflicts, Lect. Notes Comput. Sci. 1432. Springer, Berlin (1998). | MR | Zbl

[11] D. Johnson, Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9 (1974) 272-314. | MR | Zbl

[12] A. Khanafer, F. Clautiaux and E.G. Talbi, Tree-decomposition based tabu search for the bin packing problems with conflicts, in Metaheuristics International Conference, MIC09. Hamburg, Germany (2009).

[13] A. Khanafer, F. Clautiaux and E.G. Talbi, Algorithmes pour des problèmes de bin-packing mono et multi-objectif. Ph.D. thesis, Université des Sciences et Technologies de Lilles (2010).

[14] A. Khanafer, F. Clautiaux and E.G. Talbi, New lower bounds for bin packing problems with conflicts. Eur. J. Oper. Res. 206 (2010) 281-288. | MR | Zbl

[15] Y.G. Stoyan and A. Chugay, Packing cylinders and rectangular parallelepipeds with distances between them into a given region. Eur. J. Oper. Res. 360 (2009) 446-455. | Zbl

[16] Y.G. Stoyan and G.N. Yaskov, Mathematical model and solution method of optimization problem of placement of rectangles and circles taking account special constraints. Int. Trans. Oper. Res. 5 (1998) 45-57. | Zbl

[17] Università Di Bologna D.E.I.S., Operations Research, http://www.or.deis.unibo.it/ research.html.

Cité par Sources :