Algorithms for the two dimensional bin packing problem with partial conflicts

Khaoula Hamdi-Dhaoui; Nacima Labadie; Alice Yalaoui

RAIRO - Operations Research (2012)

  • Volume: 46, Issue: 1, page 41-62
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Hamdi-Dhaoui, Khaoula, Labadie, Nacima, and Yalaoui, Alice. "Algorithms for the two dimensional bin packing problem with partial conflicts." RAIRO - Operations Research 46.1 (2012): 41-62. <http://eudml.org/doc/276394>.

@article{Hamdi2012,
abstract = {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.},
author = {Hamdi-Dhaoui, Khaoula, Labadie, Nacima, Yalaoui, Alice},
journal = {RAIRO - Operations Research},
keywords = {Bin-packing; distance constraint; conflicts; genetic algorithm; bin-packing},
language = {eng},
month = {5},
number = {1},
pages = {41-62},
publisher = {EDP Sciences},
title = {Algorithms for the two dimensional bin packing problem with partial conflicts},
url = {http://eudml.org/doc/276394},
volume = {46},
year = {2012},
}

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
DA - 2012/5//
PB - EDP Sciences
VL - 46
IS - 1
SP - 41
EP - 62
AB - 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.
LA - eng
KW - Bin-packing; distance constraint; conflicts; genetic algorithm; bin-packing
UR - http://eudml.org/doc/276394
ER -

References

top
  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 Council6 (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.  
  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).  
  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.  
  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.  
  8. J. Goupy, Les plans d’expériences. Revue Modulad34 (2006) 74–116.  
  9. J.H. Holland, Adaptation in natural and artifficial systems. University of Michigan Press, Ann Arbor, MI (1975) 1–211.  
  10. K. Jansen, An approximation Scheme for Bin Packing with conflicts, Lect. Notes Comput. Sci.1432. Springer, Berlin (1998).  
  11. D. Johnson, Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.9 (1974) 272–314.  
  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.  
  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.  
  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.  
  17. Università di Bologna D.E.I.S., Operations Research,  URIhttp://www.or.deis.unibo.it/ research.html.

NotesEmbed ?

top

You must be logged in to post comments.