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

Kurzfassung/Abstract

The number of shipped parcels is continuously growing and e-commerce retailers and logistics service providers are seeking to improve logistics, particularly last-mile delivery. Since unused transportation space is a major problem in parcel distribution, one option is to improve the selection of the right parcel size for an order and the optimal packing pattern, which is known as the three-dimensional bin packing problem (3D-BPP). Further, the available portfolio of parcel types significantly influences the unused space. Therefore, we introduce the three-dimensional bin selection problem (3D-BSP) to find a portfolio of parcel types for a large set of orders. To solve the 3D-BPP with rotation of items, we propose an efficient mixed-integer linear programming formulation and symmetry-breaking constraints that are also used in the 3D-BSP for the subproblem. To solve large instances of the latter, we introduce a branch-and-repair method that improves branch-and-check. We show that our decomposition allows to relax the majority of binary decision variables in the master problem and avoids weak combinatorial cuts without further lifting. Further, we use problem-specific acceleration techniques. The numerical results based on a real-world online retailer data set show that our reformulation reduces the run time compared with existing mixed-integer linear programs for 3D-BPPs by 30% on average. For the 3D-BSP, the branch-and-repair method reduces the run time by more than two orders of magnitude compared with the mixed-integer programming formulation and can even solve instances with millions of binary decision variables and constraints efficiently. We analyze the trade-off between the costs of variety (depending on the number of parcel types) and costs for unused space. Increasing the number of parcel types reduces the unused space significantly.