Algorithms for the two dimensional bin packing problem with partial conflicts - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue RAIRO - Operations Research Année : 2012

Algorithms for the two dimensional bin packing problem with partial conflicts

Résumé

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.

Dates et versions

hal-02489864 , version 1 (24-02-2020)

Identifiants

Citer

Khaoula Hamdi-Dhaoui, Nacima Labadie, Alice Yalaoui. Algorithms for the two dimensional bin packing problem with partial conflicts. RAIRO - Operations Research, 2012, 46 (1), pp.41-62. ⟨10.1051/ro/2012007⟩. ⟨hal-02489864⟩

Collections

CNRS UTT LOSI
21 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More