Skip to Main content Skip to Navigation
Journal articles

Algorithms for the two dimensional bin packing problem with partial conflicts

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Monday, February 24, 2020 - 4:50:00 PM
Last modification on : Sunday, June 26, 2022 - 1:38:38 AM

Links full text





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



Record views