Damage-Aware Bin Packing for Online Grocery Delivery

Abstract

Online grocery delivery has seen accelerated growth in the last decade. This growth introduced new challenges in operations, such as damaged groceries upon delivery. Companies have started collecting relevant data, yet operations remain largely disconnected from the data. Motivated by this gap in the industry, we formulated the main research question of this study: "How to improve quality of service by integrating customer feedback in a bin-packing model in the context of online groceries?". A review of recent literature revealed two complementary gaps: limited applications of machine learning in offline one-dimensional bin packing where ML directly assists with the packing process, and the lack of customer feedback integration in bin packing models to improve quality of service.

Therefore, we propose a novel two-part theoretical framework to process historical data of customer damage reports into quantifiable parameters that can be used by a bin packing model. In the first part, we formulate a predictive task and propose a classification machine learning model which provides a probability of damage for the bag, given a set of bag characteristics obtained from customer data. In the second part, we propose to integrate the machine learning component into a bin packing model as a weighted term in its objective function. This integrated model comprises our damage-aware bin packing model.

The proposed methodology was implemented and evaluated through a case study using real data from the daily operations of the online supermarket Picnic. As part of the experiments, we analysed over 60 million articles across 2.2 million deliveries. We started with a comprehensive data analysis to explore the relationships in the data and identify trends. We, then, developed and trained two machine learning variants, a logistic regression and an ensemble extreme gradient boost model (XGBoost) to fulfil the predicting task of bag-damage probability estimation. We applied random undersampling to the training dataset to mitigate the extreme class imbalance (0.41% damage rate). Then, we used the logistic regression model as the ML component and implemented a damage-aware bin packing model. We defined strategic empirical metrics to measure its performance and constructed an evaluation framework using counterfactual analysis on 6000 representative deliveries.

Our findings validate the technical feasibility of integrating customer feedback data into a bin packing algorithm. The damage-aware variant recorded a 14.1% relative reduction in the average probability of damage across all bags of the deliveries tested. On the other hand, extreme class imbalance severely limited the performance of the ML models trained (1% precision score in real operational conditions). As a result, a meaningful review of the economic impact of the model is not possible. The experiments illustrated sensible item movements across the bags tested, measured with some empirical key risk parameters, such as item categories, packaging types, and bag density. The implementation showed a tolerable computational overhead of around 18%, indicating that it is realistic to deploy an efficient model to real operations.