Solving the three-dimensional open-dimension rectangular packing problem: a constraint programming model

In this paper, we address the three-dimensional open-dimension rectangular packing problem (3D-ODRPP). This problem addresses a set of rectangular boxes of given dimensions and a rectangular container of open dimensions. The objective is to pack all boxes orthogonally into the container while minimizing the container volume. Real-world applications of the 3D-ODRPP arise in production systems with operations of shipping or moving. The literature has presented mainly mixed-integer programming (MIP) formulations and their linearization techniques for the problem allied with general-purpose optimization solvers. To model and solve the 3D-ODRPP, we propose a constraint programming model based on a position-free modeling approach with logic operators. We ran computational experiments to assess the performance of the proposed model compared to the benchmark MIP models from instances of the literature. The results show our approach is competitive in different sets of problem instances in terms of reaching optimality as well as providing satisfactory feasible solutions quickly.

Article

Download

View PDF