The three-dimensional knapsack problem with balancing constraints

摘要

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.