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

Pirmin Fontaine () and Stefan Minner
Additional contact information
Pirmin Fontaine: Catholic University of Eichstätt-Ingolstadt, Ingolstadt School of Management, 85049 Ingolstadt, Germany

Operations Research, 2023, vol. 71, issue 1, 273-288

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.

Keywords: Transportation; three-dimensional bin packing; three-dimensional bin selection; decomposition; reformulation; mixed-integer programming; e-commerce (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2369 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:1:p:273-288

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().