# Computational Approaches for Grocery Home Delivery Services
###### Abstract  
The steadily growing popularity of grocery home-delivery services is most likely based on the convenience experienced by its customers. However, the perishable nature of the products imposes certain requirements during the delivery process. The customer must be present when the delivery arrives so that the delivery process can be completed without interrupting the cold chain. Therefore, the grocery retailer and the customer must mutually agree on a time window during which the delivery can be guaranteed. This concept is referred to as the attended home delivery (AHD) problem in the scientific literature. 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, the underlying optimization problem is a vehicle routing problem with a time windows. This work is concerned with a case given by an international grocery retailer's online shopping service. We present an analysis of several efficient solution methods that can be employed to AHD services. A framework for the operational planning tools required to tackle the order placement process is provided. However, the basic framework can easily be adapted to be used for many similar vehicle routing applications. 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. Finally, we analyze the scalability and suitability of the approaches. attended home delivery; grocery home delivery; vehicle routing problem with time windows +
Footnote †: journal: _Algorithms_  
0000-0001-9999-4000-0000-0000-0000-0000-00000-0000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-000000-000000-00000-000000-0  
Deliveries from restaurants or fast-food chains purchased online have spiked in 2021 due to the COVID-19 pandemic. While 17% of the individuals living in the EU ordered a meal online in 2020, this number increased dramatically to 24% in 2021 [3]. The Dutch were the most active in ordering meals online (53%). Internet sales of food and beverages (including meal kits) account only for a comparably small portion of e-commerce sales. Only 18% of the individuals of the EU member states ordered groceries online in 2021. This value varies strongly among the EU member states: 28% in The Netherlands, 10% in Germany, and only 3% in Serbia [3]. As a survey conducted by Nielsen [4] in 2015 shows, a similar strong trend towards the online sales of groceries can be observed worldwide. The global survey points out that around a quarter of all respondents are already ordering grocery products online for home delivery and that 55% are willing to do so in the future. Although only a small portion of grocery sales are currently conducted online, there is increasing pressure for all businesses, especially supermarket chains, to have an online presence. During the early stages of the COVID-19 pandemic, the home delivery of groceries and essential supplies became an effective measure to protect medically vulnerable persons [5]. In general, a large variety of groceries are sold online. Accordingly, there are several different delivery modes necessary due to the different transport requirements of the various grocery categories [6]. Beverages and non-perishable foods can be shipped with traditional parcel services. Some perishable products, such as meat, for which the correct temperature has to be maintained during shipment, can be shipped in isolated packages together with thermal packs or dry ice.