Iterative approaches for solving a multi-objective 2-dimensional vector packing problem

• We study a new bi-objective packing problem.
• We compare two iterative approaches for this problem.
• We propose several methods to implement the two iterative methods.

In this paper, we address a bi-objective 2-dimensional vector packing problem (Mo2-DBPP) that calls for packing a set of items, each having two sizes in two independent dimensions, say, a weight and a height, into the minimum number of bins. The weight corresponds to a “hard” constraint that cannot be violated while the height is a “soft” constraint. The objective is to find a trade-off between the number of bins and the maximum height of a bin. This problem has various real-world applications (computer science, production planning and logistics). Based on the special structure of its Pareto front, we propose two iterative resolution approaches for solving the Mo2-DBPP. In each approach, we use several lower bounds, heuristics and metaheuristics. Computational experiments are performed on benchmarks inspired from the literature to compare the effectiveness of the two approaches.