Lower and upper bounding procedures for the bin packing problem with concave loading cost

Abstract

We address the one-dimensional bin packing problem with concave loading cost (BPPC), which commonly arises in less-than-truckload shipping services. Our contribution is twofold. First, we propose three lower bounds for this problem. The first one is the optimal solution of the continuous relaxation of the problem for which a closed form is proposed. The second one allows the splitting of items but not the fractioning of bins. The third one is based on a large-scale set partitioning formulation of the problem. In order to circumvent the challenges posed by the non-linearity of the objective function coefficients, we considered the inner-approximation of the concave load cost and derived a relaxed formulation that is solved by column generation. In addition, we propose two subset-sum-based heuristics. The first one is a constructive heuristic while the second one is a local search heuristic that iteratively attempts to improve the current solution by selecting pairs of bins and solving the corresponding subset sum-problem. We show that the worst-case performance of any BPPC heuristic and any concave loading cost function is bounded by 2. We present the results of an extensive computational study that was carried out on large set of benchmark instances. This study provides empirical evidence that the column generation-based lower bound and the local search heuristic consistently exhibit remarkable performance.