Portal de Periódicos da CAPES

The three-dimensional knapsack problem with balancing constraints

2012; Elsevier BV; Volume: 218; Issue: 19 Linguagem: Inglês

10.1016/j.amc.2012.03.052

1873-5649

Mauro Maria Baldi, Guido Perboli, Roberto Tadei,

Optimization and Search Problems

In this paper we introduce a new packing problem, the three-dimensional knapsack problem with balancing constraints (3BKP), the extension of the three-dimensional knapsack problem (3KP) where additional constraints related to the packing center of mass are given. The 3BKP consists in orthogonally packing a subset of three-dimensional weighted items into a knapsack in order to maximize the total profit of the loaded items. The items must not overlap and the packing center of mass must lie into a predefined boxed domain inside the knapsack. We assume that items can be rotated. We give a MIP model for the problem, upper bounds and an efficient heuristic to solve large size instances. The computational results show that the MIP model cannot find optimal solutions, except for small size instances, but it can be used to calculate upper and lower bounds. It is shown that our heuristic outperforms the solution quality both of the MIP model and the heuristics available in the literature explicitly designed to solve the 3KP.