Dynamic Assignment of Delivery Order Bundles to In-Store Customers

Abstract

Many larger grocery stores offer home delivery services. However, the delivery cost is usually high and such services are rarely profitable. One way of reducing cost is by outsourcing some orders to in-store customers for a compensation. While initially single orders were dynamically assigned to customers, companies started exploring the assignment of order bundles instead to reduce per-order compensation and exploit consolidation potential. We investigate the value of dynamic assignment of bundles in this work. To this end, we consider a setting where all orders are known and, over time, unknown in-store customers enter the system for a short time and offer transportation of bundles of orders for compensation. The store decides dynamically which bundle to assign to which in-store customer (if any). At the end of the time horizon, the remaining orders are delivered by a dedicated fleet of store employees. The goal of the store is to minimize the compensation prices together with the delivery cost. We propose a threshold based policy tuned by a stochastic lookahead procedure. Popularity and compensation price thresholds are determined a priori by solving a set of perfect information scenarios. In every state, bundles are only assigned if they are popular enough and the compensation is comparably low. The thresholds are adapted over time to account for the decrease in assignment opportunities. We show the effectiveness of our policy in a comprehensive computational study and highlight the value of bundle assignments compared to assigning individual orders. We further show that our strategy not only reduces the compensation paid to in-store customers but also the final routing cost