An ILP-based exact approach for solving the variable cost and size bin packing problem with time-dependent cost modeling the shared satellite-based last-mile delivery

In the nowadays common two-tier logistic systems for delivering products in urban areas, the last leg of the distribution chain, the so-called last mile, is by far the most problematic. The modeling of the last-mile delivery problem as a variable cost and size bin packing problem with time-dependent costs emerged recently as the best solution for planning the delivery operations. No exact solution has been yet proposed for efficiently solving this variant of the bin packing problem. In this paper, we present a new problem formulation and devise an exact branch-and-bound method for effective and efficient problem resolution. Upon the resulting tailored solution approach, we devise a procedure to speed up the problem resolution further. Numerical results collected on large-sized instances reveal the dramatic reduction of the computation time obtained with our solution approach, which turns out to be up to ten times faster than the commercial solver. The improvement in solving large-sized instances with a relatively easy-to-implement approach is remarkably relevant for real-world applications.