Computational Approaches for Grocery Home Delivery Services.

Grocery home delivery services require customers to be present when their deliveries arrive. Hence, the grocery retailer and the customer must mutually agree on a time window during which the delivery can be guaranteed. In the literature, this concept is referred to as the Attended Home Delivery (AHD) problem. The phase during which customers place orders, usually through a web service, constitutes the computationally most challenging part of the logistical processes behind such services. The system must determine potential delivery time windows that can be offered to incoming customers and incrementally build the delivery schedule, as new orders are placed. Typically, a Vehicle Routing Problem with Time Windows forms the underlying optimization problem. In this work, which is concerned with the use case given by the online grocery shopping service of an international grocery retailer, we present an analysis of efficient solution methods that can be employed to AHD services. We provide a comprehensive computational study comparing several algorithmic strategies, combining heuristics utilizing Local Search operations and Mixed-Integer Linear Programs, tackling the booking process. We analyze the scalability and suitability of the approaches. Further, we give managerial insights and policy recommendations for applying the approaches in real-life applications.