Using stochastic and dynamic routing models to improve the performance of an e-grocer’s delivery service

Abstract

E-grocers are grocery markets which offer their assortment online and deliver a customer's groceries at home. For an e-grocer the quality of their delivery service is a crucial asset to create and maintain a loyal customer-base. Because the online share of the grocery market has grown rapidly over the last decade, there is an urgent need for e-grocer specific routing models. In parallel, the research community has made rapid developments in the fields of stochastic and dynamic routing models during the past decade. Those studies suggest that the use of stochastic and dynamic elements improves the performance of routing models for a large variety of applications. However, it is yet unresearched how these stochastic and dynamic routing models can be used to improve the last-mile delivery for e-grocers specifically. The intended outcome of this research is the formulation of a promising modelling approach to use stochastic and dynamic routing model elements to improve the performance of an e-grocer's routing model. In this thesis, first the objectives and requirements for an e-grocer's routing model are determined in more detail by means of a case-study at Dutch e-grocer Picnic. The strict requirements for an e-grocer's routing model are: \begin{enumerate*}[label=(\arabic*)] \item Offer customers a free one-hour delivery time window when they place an order. \item Offer free communication of a 20-minute delivery time window at the morning of the delivery. \item Calculation of the combinations of customers in a trip has to be completed within 45 minutes. \item The trip planning has to be calculated within 5 hours. \end{enumerate*} When these requirements are met, the objectives for the routing model are to maximize the on-time delivery performance and to minimize the operational costs. The on-time delivery performance is quantified by means of the on-time delivery rate and the rate of extreme lates (\geq 15 minutes late). The operational costs are quantified by means of the average time spent per delivery. Next, scientific literature on the topic of dynamic and stochastic routing models is studied. Based on the findings in this literature study, it is suggested to make a distinction between ``regular” deliveries and ``flexible” deliveries. Regular deliveries have to be delivered within a 20-minute delivery time window. Flexible deliveries allow for larger delivery time windows. Once the trip has departed, the presence of these flexible deliveries allows for dynamic re-optimization of the customer sequence in that trip. This strategy has the potential to improve the on-time delivery performance. Moreover, this approach does not incur large additional operational costs because the number of vehicles used for delivery remains the same. At e-grocers, limited computation time is available for the calculation of the combinations of customers in a trip. However, plenty of time is available to determine the exact trip planning. Therefore, the traditional vehicle routing problem is split into two separate problems which are solved one after the other: The customer-trip assignment problem and the sequencing problem. Then, different approaches for implementing the concept of flexible deliveries in an e-grocer's routing model are designed. Three different sequencing models are formulated to get insights in the benefits of a stochastic routing model: A deterministic sequencing model which resembles the current operations at Picnic (benchmark model), a stochastic sequencing model which uses a-priori simulation to choose the best solution out of a set of good solutions (simulation-based model), and a deterministic sequencing model which positions the flexible deliveries in the customer sequence of a trip in such a way that the effectiveness of re-optimization is maximized (heuristics-based model). In order to study the added value of a dynamic routing model, a deterministic re-optimization model is designed. In order to quantify the performance of a routing model which makes use of flexible deliveries and compare the different model variants, four different routing model configurations are investigated by means of a computational experiment. A configuration consists of a sequencing model and, in some cases, a re-optimization model. The computational experiment uses real historic test instances from e-grocer Picnic to evaluate the performance of the configurations. In addition, historic data from Picnic is used to simulate realisations of planned trip times. Two different types of customer-trip assignments are investigated: customer-trip assignments for a small vehicle and for a large vehicle. Moreover, two different sizes of the flexible delivery windows are studied: 60 minutes and 75 minutes. From the experimental results it can be concluded that the configurations including a re-optimization model outperform the static and deterministic benchmark configuration in terms of on-time delivery performance. However, re-optimization comes at the price of an increased average time spent per delivery. This can be explained by the fact that the re-optimization model optimizes the on-time delivery performance instead of the trip duration, resulting in larger average travel times. The effects of re-optimization become significant when 10\% or more of all deliveries is flexible. For this percentage of flexible deliveries, the number of late deliveries can be reduced by up to 18\% and the number of extreme lates can be reduced by up to 27\%, depending on the type of vehicle and the size of the flexible delivery windows. The simulation-based sequencing model proves to be effective without re-optimization for the large vehicle type. For the small vehicle type it needs the re-optimization model to significantly outperform the static and deterministic benchmark configuration. When the re-optimization model is included in the configuration, the simulation-based and heuristics-based sequencing models show similar performance in terms of on-time delivery rate. The configuration with the simulation-based approach results in a lower average time spent per delivery. However, the heuristics-based approach results in fewer extreme lates. In order to decide on the optimal routing model configuration for a specific e-grocer, the relative importance of the on-time delivery performance and the operational costs have to be specified. If an e-grocer is very cost-sensitive, the configuration consisting of the simulation-based sequencing model and the real-time re-optimization model would be optimal. However, if an e-grocer has more financial possibilities for an increase in operational costs the configuration including the heuristics-based sequencing model would be a better fit. Extending the flexible delivery windows results in a significant improvement of the on-time delivery performance of the configurations. However, the increased number of successful re-optimizations comes at the expense of an increased average time spent per delivery. The added value of extended flexible delivery windows is largest for the small vehicle type. When comparing the two types of vehicles studied, it becomes evident that the use of stochastic and dynamic routing model elements is more effective for the large vehicle type than for the small vehicle type.