A Branch-and-Repair Method for Three-Dimensional Bin Selection and Packing in E-Commerce.

The article focuses on optimizing parcel type portfolios to reduce unused space in transportation, particularly in e-commerce last-mile delivery. It introduces the three-dimensional bin selection problem (3D-BSP) to select an optimal set of parcel types minimizing the combined costs of unused space and parcel variety, and proposes a branch-and-repair decomposition method that significantly outperforms standard mixed-integer linear programming solvers in computational efficiency. The method decomposes the problem into a relaxed master problem and subproblems solving three-dimensional bin packing problems (3D-BPP) for individual orders, incorporating acceleration techniques such as bin and order hierarchies and solution repairing. Numerical experiments using real-world data from a Brazilian e-commerce company demonstrate that a small portfolio of parcel types can substantially reduce unused space, with diminishing returns beyond a few parcel types, and that allowing order splitting into multiple parcels has limited impact on reducing unused space. The study highlights the trade-offs between minimizing unused space and managing parcel variety costs, providing a scalable approach for companies to optimize packaging portfolios in logistics operations.