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 metadatas

https://hal-utt.archives-ouvertes.fr/hal-02489864
Contributor : Daniel Gavrysiak <>
Submitted on : Monday, February 24, 2020 - 4:50:00 PM
Last modification on : Tuesday, February 25, 2020 - 1:32:17 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

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⟩

Share

Metrics

Record views

44