Abstract
The Two-dimensional Bin-Packing Problem (2BP) is a classical 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 safe 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 The a 2BP with distance constraints between given items to respect, if they are packed within the same bin. The problem is NP-hard since it generalizes the BP, already NP-hard. This study presents a mathematical model and a genetic algorithm for this new problem. The initial solutions are obtained with an adaptation of the Bottom-left-fill heuristic classically used for the BP. A local search is called to improve the quality of the generated solutions.