Algorithms for the two dimensional bin packing problem with partial conflicts - Archive ouverte HAL Access content directly
Journal Articles RAIRO - Operations Research Year : 2012

Algorithms for the two dimensional bin packing problem with partial conflicts

(1) , (1) , (1)
1

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.

Dates and versions

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

Identifiers

Cite

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
13 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More