Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :