Branch-and-repair for the stochastic three-dimensional bin selection problem: A multi-stage stochastic programming application

• Introducing stochastic demand into the planning of a parcel portfolio • Formulating a multi-stage stochastic program • Developing an efficient branch-and-repair method • Providing insights based on a case study using real-world data Increasing e-commerce has been one of the major trends in the last decades. One of the key elements is the packing of items where the company has to decide which parcel type to choose for packing all items of an order. To reduce the unused space in parcels, the essential part is the available parcel type portfolio. Since order demand is uncertain, it is important to account for this uncertainty in the strategic decision process. Therefore, we address the strategic design of the parcel type portfolio under stochastic demand and introduce the stochastic three-dimensional bin selection problem (S3D-BSP). We formulate the S3D-BSP as a multi-stage stochastic program in which recourse decisions allow for reordering parcels of the chosen portfolio and balance inventory and procurement decisions. To solve larger instances, we introduce a branch-and-repair method. Specifically, we develop a fast approximated and a slow but optimal repair strategy and discuss how to balance the trade-off between those two. In the numerical study, we show the efficiency of our approach and show that optimal portfolios can largely vary depending on the demand structure in a case study based on real-world data.