Meal Delivery Routing Problem with Stochastic Meal Preparation Times and Customer Locations

Kancharla, Surendra Reddy; Van Woensel, Tom; Waller, S. Travis; Ukkusuri, Satish V. Article — Published Version Meal Delivery Routing Problem with Stochastic Meal Preparation Times and Customer Locations Networks and Spatial Economics Provided in Cooperation with: Springer Nature Suggested Citation: Kancharla, Surendra Reddy; Van Woensel, Tom; Waller, S. Travis; Ukkusuri, Satish V. (2024) : Meal Delivery Routing Problem with Stochastic Meal Preparation Times and Customer Locations, Networks and Spatial Economics, ISSN 1572-9427, Springer US, New York, NY, Vol. 24, Iss. 4, pp. 997-1020, https://doi.org/10.1007/s11067-024-09643-1 This Version is available at: https://hdl.handle.net/10419/315347 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) Networks and Spatial Economics (2024) 24:997–1020 https://doi.org/10.1007/s11067-024-09643-1 RESEARCH Meal Delivery Routing Problem withStochastic Meal Preparation Times andCustomer Locations SurendraReddyKancharla1· TomVanWoensel2· S.TravisWaller1,3· SatishV.Ukkusuri4 Accepted: 25 July 2024 / Published online: 18 September 2024 © The Author(s) 2024 Abstract We investigate the Meal Delivery Routing Problem (MDRP), managing courier assignments between restaurants and customers. Our proposed variant considers uncertainties in meal preparation times and future order numbers with their locations, mirroring real challenges meal delivery providers face. Employing a rolling-horizon framework integrating Sample Average Approximation (SAA) and the Adaptive Large Neighborhood Search (ALNS) algorithm, we analyze modified Grubhub MDRP instances. Considering route planning uncertainties, our approach identifies routes at least 25% more profitable than deterministic methods reliant on expected values. Our study underscores the pivotal role of efficient meal preparation time management, impacting order rejections, customer satisfaction, and operational efficiency. Keywords Meal delivery routing· Uncertainty· Sample average approximation· Adaptive large neighborhood search 1 Introduction Integrating the gig economy into first and last-mile delivery services for freight and passenger sectors has significantly revolutionized urban transportation. This shift is in response to the escalating demands for efficient last-mile deliveries. * S. Travis Waller steven_travis.w[email protected] 1 “FRIEDRICH LIST” Faculty ofTransport andTraffic Sciences, Dresden University ofTechnology, Hettnerstraße 1-3, Dresden01069, Saxony, Germany 2 School ofIndustrial Engineering andInnovation Sciences, Eindhoven University ofTechnology, P.O. Box513, 5600 MB, Eindhoven, TheNetherlands 3 College ofEngineering, Computing andCybernetics, Australian National University, 108 North Rd, Canberra2601, Australia 4 Lyles School ofCivil Engineering, Purdue University, 550 W Stadium Ave., WestLafayette, IN47907, USA 998 S.R.Kancharla et al. Numerous startups specializing in restaurant meal delivery, such as Grubhub, Doordash, Deliveroo, Swiggy, and Ubereats, and on-demand transport services like Uber, Lyft, and Ola, have emerged to meet this growing need. Despite facing unique challenges, these services fundamentally address the same issue: they enable customers to conveniently request pickup and drop-off services through mobile apps or websites, typically ensuring delivery within a set timeframe. These companies charge a delivery fee, a portion of which is paid to the service provider. Success in this domain hinges on satisfying all parties involved: customers expect prompt, affordable, and reliable service; drivers aim for substantial earnings; and restaurants seek to expand their reach and customer base through these delivery services. Our research addresses a vital issue in the freight industry: the intricacies of routing for restaurant meal deliveries. This is an expanded form of the classical Pickup and Delivery Problem (PDP), known for its computational complexity. Unlike traditional PDP, which often focuses on the limitations of vehicle numbers, our study concentrates on the variable elements that can significantly affect the efficiency of operations. In the context of the gig economy, the concept of a fixed fleet size is replaced by a potentially limitless number of independent couriers who work on a flexible schedule. This flexibility, however, brings unpredictability in several aspects - such as the couriers’ working hours, their starting points for deliveries, and even their discretion to accept or decline orders. Additionally, the variable nature of meal preparation times adds complexity to the food delivery sector. Minor variations in these times can lead to significant delays, adversely affecting customer satisfaction and the efficiency of delivery operations. The unpredictability of future orders intensifies this challenge, as the specific locations and quantities of these orders, crucial for route optimization, remain uncertain. Existing approaches in the meal delivery sector, such as those by Reyes etal. (2018) and Yildiz and Savelsbergh (2019), primarily rely on deterministic models with fixed meal preparation times and delivery windows, failing to account for the variability and unpredictability in these factors. In contrast, Ulmer etal. (2021) and Zheng etal. (2023) attempted to incorporate uncertainties in meal preparation and travel times, yet their models still lacked the dynamic adaptability required for real-life, uncertain scenarios. Relying on average estimates for meal preparation and future orders is insufficient, as this method overlooks the extensive range of variability and its influence on decision-making processes. These variables’ complex and often unknown probability distributions render simple average-based approaches ineffective. This unpredictability dramatically expands the range of potential scenarios, making traditional deterministic solutions unfeasible. Such deterministic models, not accounting for this variability, tend to underestimate necessary resources, leading to operational inefficiencies and decreased profitability. Our goal is to develop a probabilistic model that accurately accounts for these uncertainties, allowing for the creation of more reliable and effective routing strategies that enhance the performance of the meal delivery sector. Given the intricate challenges of uncertain meal preparation times and the unpredictable flow of orders, we’ve identified a collection of methods particularly adept at navigating the Meal Delivery Routing Problem (MDRP). To address the dynamic 999 Meal Delivery Routing Problem withStochastic Meal Preparation… and uncertain aspects of MDRP, we utilize a rolling horizon framework that integrates the Sample Average Approximation (SAA) method with the Adaptive Large Neighborhood Search (ALNS), selected for its proven effectiveness in complex scenarios akin to MDRP. SAA, known for its strength in handling stochastic discrete optimization problems, uses a scenario-based approach to estimate the expected values of decision variables, considering various potential future states. This aspect is vital when relying on average estimates of uncertain factors, which could result in less optimal decisions. The SAA’s incorporation facilitates the dynamic modification of routes in response to new information, aligning with the constantly changing delivery environment. This process involves repeatedly applying the SAA on selected scenarios over different time horizons, assessing the solutions against a broader range of scenarios to approximate the expected value function better, and updating routes based on actual developments. Such a strategy ensures that the solutions are always relevant and adaptable to the immediate operational demands. The Adaptive Large Neighborhood Search (ALNS) algorithm, highly effective for large-scale routing problems (Li et al. 2016; Ghilas et al. 2016a, b; Zhu and Sheu 2018a), is an integral complement to the SAA method in our approach. ALNS (Ropke and Pisinger 2006) is adept at exploring and optimizing within extensive solution spaces, making it particularly well-suited for addressing the Meal Delivery Routing Problem (MDRP). This algorithm is tailored to quickly adjust to changes in routing parameters, aligning with the unpredictable work schedules of couriers and the varying patterns of order acceptance typical in MDRP. Combining ALNS with the SAA method within a rolling horizon framework merges the SAA’s ability to approximate stochastic elements with ALNS’s capacity to efficiently navigate and fine-tune solutions in a broad and intricate solution environment. This synergistic approach enables us to develop resilient routing solutions in the face of uncertainties and adapt and respond to the dynamic nature of meal delivery operations. The study primarily focuses on the challenges in the freight sector, particularly the restaurant meal delivery routing problem, a complex variant of the Pickup and Delivery Problem (PDP). This problem is characterized by unpredictable factors like varying courier availability, fluctuating working hours, and dynamic meal preparation times, significantly affecting operational efficiency. Traditional deterministic methods are inadequate due to the complexities and uncertainties involved, including the unpredictable nature of future orders. The study explores advanced methodologies like the Sample Average Approximation (SAA) and the Adaptive Large Neighborhood Search (ALNS) within a rolling horizon framework to address these challenges. These methods effectively handle the stochastic elements and complex solution spaces of the Meal Delivery Routing Problem (MDRP). The research includes developing tailored algorithms for the MDRP, conducting computational tests with real-world data, and performing sensitivity analysis to evaluate algorithm performance under varying levels of uncertainty. The main contributions are as follows: 1. We developed innovative solution algorithms crafted explicitly for the meal delivery routing problem. These algorithms are strategically designed to adeptly handle 1000 S.R.Kancharla et al. uncertainties, such as the variability in meal preparation times, the fluctuating number of orders, and their locations. This tailored approach ensures that the routing solutions are efficient and highly responsive to the dynamic nature of meal delivery operations. 2. Furthermore, we undertake comprehensive computational testing using data derived from real-world scenarios. These tests were extensive, covering a wide range of scenarios that included various combinations of uncertainties. This approach allowed us to rigorously evaluate the algorithms in conditions that closely mimic actual operational environments, thereby ensuring the robustness and reliability of our solutions in practical settings. 3. We conduct a detailed sensitivity analysis to scrutinize how the algorithms performed under different levels of uncertainty. This systematic and thorough analysis provided deep insights into the behavior and performance nuances of the algorithms when confronted with varying degrees and types of uncertainties. Through this sensitivity analysis, we identified strengths and potential areas for improvement in our algorithms, ensuring they are effective and adaptable to the complex and ever-changing landscape of meal delivery services. The paper’s organization is as follows: Section 2 presents the literature review related to the MDRP and related problems. Section3 formally introduces the MDRP and uncertainties considered. Section4 describes the proposed solution algorithm for MDRP with uncertainties. Section5 presents the test instances and discusses the computational results, followed by conclusions in Section6. 2 Literature Review We divide the literature into two parts. First, we review the work on Meal-delivery routing and related problems, followed by literature on stochastic Pickup and Delivery problems (PDPs). 2.1 Meal‑delivery Problems Reyes etal. (2018) proposed a dynamic deterministic variant of a pickup and delivery problem called the Meal Delivery Routing Problem (MDRP), and they solved it using a rolling-horizon approach. Later, Yildiz and Savelsbergh (2019) proposed a mathematical formulation for the static variant and solved it using a simultaneous row and column generation-based algorithm. Both articles assumed unlimited capacity for couriers, a fixed delivery window of 90 minutes from the order’s place, and fixed meal preparation times. Steever etal. (2019) relaxed the first two assumptions and allowed order placement from multiple restaurants. They proposed a heuristic that accounts for future orders using equity and dispersion metrics. Ulmer etal. (2021) relaxed the latter two assumptions and proposed an anticipatory customer assignment policy that accounts for the random meal preparation times. However, the above models (except Steever etal. (2019)) only match couriers 1001 Meal Delivery Routing Problem withStochastic Meal Preparation… with orders and assume the couriers take the best routes. Moreover, they Yildiz and Savelsbergh (2019); Steever etal. (2019); Ulmer etal. (2021) also enforce the constraint of visiting all the orders. Liu (2019) proposes a MILP model for a problem similar to MDRP, where drones are used instead of regular couriers. Using drones helps remove uncertainty related to travel times and adds additional complexity, like charging requirements and limited capacity. Liao etal. (2020) proposes a two-stage solution algorithm for a static and deterministic variant of the problem to minimize carbon footprint. Recently, Zheng etal. (2023) proposed an iterative greedy algorithm to solve a meal delivery problem with uncertainties in meal preparation times and travel time and also proposed two time-saving strategies to improve the computational effort. However, their instances are not for dynamic scenarios closer to the real-life application. 2.2 Stochastic Pickup andDelivery Problems Stochastic variants of VRP have been extensively studied (Laporte etal. 2002; Verweij etal. 2003; Secomandi and Margot 2009; Chu etal. 2015; Ghilas etal. 2016b; Zhu and Sheu 2018b; Shi etal. 2018; Györgyi and Kis 2019; Karoonsoontawong etal. 2020; Fachini etal. 2022). We can categorize the solution approaches for these variants into two groups. The first group uses stochastic programming with recourse, a well-known framework for modeling uncertainty optimization problems. In this method, some data is unknown at the moment of planning. First, a decision is made, and then the recourse costs of the consequences of the plan are minimized. The second group uses a multiscenario approach, followed in this study. This method approximates expected costs by evaluating a solution based on generated scenarios. Metaheuristic algorithms are generally used in implementing the multi-scenario stochastic optimization approach. A good review of metaheuristic algorithms for stochastic combinatorial optimization can be found in Bianchi etal. (2009) and Gutjahr (2011). Unlike the literature on stochastic VRP, literature on Pickup and Delivery Problems (PDP) with stochastic demands is limited. Powell etal. (1988) is one of the first studies that considered the dynamic PDP with stochastic demands. They also showed that considering uncertainty in the planning process results in substantial profits and increases the service level compared to the deterministic planning approach. In Ghilas et al. (2016b) integrated the PDP with the public transport system and considered stochastic demands. Zhu and Sheu (2018b) proposed a failure-specific cooperative recourse strategy for the simultaneous PDP with stochastic demand. Unlike the previous studies, Shi etal. (2018) considered uncertainty in travel and service times, Györgyi and Kis (2019) considered uncertainty in time windows. The typical result in all the above studies is that uncertainty in the planning process leads to significant improvements in objective over the deterministic case. In Zhang etal. (2023) introduced approximations based on the knapsack problem for estimating reward-to-go. These approximations serve as the foundation for creating efficient online scheduling policies and offline planning algorithms. In Wang etal. (2023), focused on meeting customer delivery punctuality expectations by estimating arrival times and success probabilities in uncertain scenarios. 1002 S.R.Kancharla et al. Their estimated success probabilities tended to be conservative lower bounds. They also introduced a solution approach based on a branch-price-and-cut framework. 3 Problem Description Given a graph G(N,A) , where N denotes the set of nodes representing locations such as restaurants and customers, and A represents the arcs between these nodes. We have a set T , which represents tasks, divided into Tp for pickups and Td for deliveries. The set V enumerates couriers involved in the delivery process. For each node i∈T , there are associated service times si and time windows defined by earliest ei and latest li arrival times. The demand at each node is given by di , where positive values indicate pickups and negative values represent deliveries. Couriers k∈V have specific on-times ek , off-times lk , and capacity constraints 𝛽k . They expect a minimum payment mk per unit time. The travel time between nodes i and j is denoted by tij . 𝛼 , the cost per unit time, serves a pivotal role in our model by converting time metrics, like delay and waiting times, into cost metrics. Unlike cij , which directly represents the travel cost between nodes i and j , and pi , which denotes the payment received for order i . Customers at node i∈Td have a maximum willingness to pay wi . 𝜇i represents the deterministic time associated with waiting times and delays at each node i . x k ij is a binary variable that is equal to 1 if courier k travels directly from node i to node j . ak ij is a continuous variable representing the arrival time of courier k at node j from node i . yk ij is a continuous variable representing the load carried by courier k when arriving at node j from node i . 𝜉 is a random vector. Subject to: (1) max ∑ i∈Td pi− ∑ i,j∈T cij −𝛼 (∑ i∈Td 𝜇i−E[Q(x,𝜉)] ) (2) pi≤wi ∑ j∈N ∑ k∈V xk ji ∀i∈T d (3) c ij ≥ ∑ k∈V mkxk ijtij ∀i,j∈T,i≠ j (4) ∑ k∈V(∑ j∈T�{i} xk ji ) ≤1∀i∈T (5) ∑ k∈ V (∑ j∈T�{i} xk ij ) = ∑ k ∈ V (∑ j∈T�{i} xk ji ) ∀i∈T 1003 Meal Delivery Routing Problem withStochastic Meal Preparation… The objective function Eq.1 is designed to maximize expected profit while accommodating the stochastic nature of demand and service times. It explicitly includes penalties for missed deliveries and service delays, addressed within the function’s third term. This term employs a cost factor, scaled by 𝛼 , that increases proportionally with the deviation from scheduled delivery times. By incorporating this penalty, the function effectively quantifies the financial and service quality impact of delays, ensuring that operational strategies seek to optimize profitability and uphold reliability and customer satisfaction. Constraints Eq.2 limit the maximum payment expected from the customer. Constraints Eq.3 ensure couriers receive at least the minimum expected payment. Constraints Eq.4 ensure each pickup and delivery pair is visited at most once. Constraints Eqs.5-6 ensure flow conservation at each node. Constraints Eq.7 track the arrival time at each node. Constraints Eq.8 ensure the earliest arrival time at a node is respected. Constraints Eq.9 ensure assignments to couriers are within their shift time. Constraints Eq.10 ensure that the arrival time at the delivery node is later than the pickup node. Constraints Eq.11 ensure demand satisfaction at each node. Constraints Eq.12 ensure courier capacity is not violated. Constraints Eq.13 ensure (6) ∑ j∈T ∑ i∈T p xk ij = ∑ j∈T ∑ i∈T d xk ji ∀k∈V,i≠ j (7) ∑ j∈N�{i} ∑ k∈V ak ji ≤ ∑ j∈N�{i} ∑ k∈V ak ij −(si+tij)xk ij ∀i∈T (8) e ix k ij ≤a k ij ∀k∈V,i∈T,j∈T�{i } (9) e kx k ij ≤a k ij ≤lkx k ij ∀k∈V,i∈N,j∈N�{i } (10) ∑ j∈N�{i} ak ji ≤ ∑ j∈T�{i+n} ak ji+n∀k∈V,i∈ P (11) ∑ k∈ V ∑ j∈N�{i} yk ij −dixk ij = ∑ k ∈ V ∑ j∈N�{i} yk ji ∀i∈T (12) yk ij ≤𝛽kx k ij ∀k∈V,i∈N,j∈N�{i } (13) 𝜇 i+li≥ ∑ k∈V ∑ j∈N ak ji +sixk ij ∀i∈T d (14) xk ij ∈{0, 1}∀k∈V,i∈N,j∈ N (15) yk ij ≥0, a k ij ≥0, pi≥0, cij ≥0∀k∈V,i∈N,j∈N 1004 S.R.Kancharla et al. that the actual delay experienced by the customer is at least as large as the service time plus the travel time, ensuring that no penalty is applied for early or on-time deliveries. Constraints Eqs.14 and 15 define the decision variables’ domains, ensuring that routes are binary decisions and all other variables are non-negative. Unlike the traditional vehicle routing problems, we allow the dropping of orders. Constraints Eq.4 make this dropping of orders possible. The xk ij terms in constraints Eqs.3, 4, 8 and 11 avoid considering the dropped order in the estimation of payment from the customers, payments made to couriers, arrival time tracking, and courier load tracking, respectively. 3.1 Recourse Action The meal preparation times are realized when the courier arrives at the restaurant, and future orders from a restaurant can be realized only when the order is placed. The longer waiting times due to delays in meal preparation can violate the time windows. Suppose the delay is within the given buffer. In that case, a delay penalty will be added to the objective, or when the delay is beyond the allowed buffer, the orders are dropped, and a penalty is applied to the objective. Unrealized orders also impact the availability of couriers for future orders because of the detours taken to meet the realized orders. 3.2 Modeling ofMeal Preparation Times We model the meal preparation time at each restaurant node as a random variable given by t+𝛿i , where 𝛿i≥0 is the duration of the stochastic disruption at node i and t is a deterministic meal preparation time. Specifically, 𝛿i follows a gamma distribution with a given shape parameter (k) and scale ( 𝜃 ) parameter that depends on the deterministic meal preparation time. The Gamma distribution is commonly used in the literature to describe stochastic times, as they follow convolution and non-negativity properties. The parameters k and 𝜃 allow for the generation of scenarios considering the degree by which preparation times vary, adjusted by the coefficient of variation ( cv ). For our analysis, c2 v = 0.25 gave the best fit for the meal preparation times. We derive parameters k and 𝜃 for a given value cv as follows: 3.3 Modeling ofFuture Orders andTheir Locations We assume that the number of orders within the upcoming interval follows a Poisson distribution with a mean arrival rate 𝜆 , represented by Ot+1∼Poisson(𝜆) . The Poisson distribution is commonly used in the literature to represent random occurrences. After determining the number of orders, Ot+1 , we identify their probable locations. We divide the customer base into central and peripheral segments using the Isolation Forests method, as described by Liu etal. (2008). The proportion of customers within each segment denoted as 𝛼central for the central segment and 𝛼peripheral for (16)  c v= 𝔼(𝛿 i ) Var(𝛿i)=k𝜃 k𝜃2 i ⇒k=1 c2 v ;𝜃i=tc 2 v 1011 Meal Delivery Routing Problem withStochastic Meal Preparation… study: a temperature setting of 50, a temperature reduction factor of 0.98, a maximum of 10 times the number of orders for temperature reduction iterations, and 20 times the number of orders for maximum iterations at a temperature. Additionally, we set the value of Ω� to 1000. It’s well-known that increasing the maximum number of replications (N) generally leads to improved results, albeit with a substantial increase in computational time. To strike a balance between solution quality and runtime efficiency, we tested various values of N, ranging from 20 to 100 with increments of 20, on three instances, each representing a different set (refer to Table2). Our experiments revealed that increasing N beyond 60 resulted in only marginal improvements in the objective, accompanied by a significant rise in runtime. Consequently, we opted for N=60 in this study, finding it to be the optimal compromise between solution quality and computational efficiency. Table 1 Instances Details Instance Orders Restaurants Couriers Time Window WTP Demand Mean Std Mean Std Mean Std 0o50t100s1p100mc1v1 126 64 40 57.02 8.94 7.40 3.38 1.99 0.80 0o50t100s1p100mc1v2 126 64 40 57.02 8.94 7.40 3.38 1.99 0.80 0o50t100s1p100mc2v1 126 60 40 56.17 8.60 7.43 3.41 1.91 0.79 0o50t100s1p100mc2v2 126 60 40 56.17 8.60 7.43 3.41 1.91 0.79 0o50t100s2p100mc1v1 126 64 47 57.02 8.94 7.40 3.38 1.99 0.80 0o50t100s2p100mc1v2 126 64 47 57.02 8.94 7.40 3.38 1.99 0.80 0o50t100s2p100mc2v1 126 60 47 56.17 8.60 7.43 3.41 1.91 0.79 0o50t100s2p100mc2v2 126 60 47 56.17 8.60 7.43 3.41 1.91 0.79 1o50t100s1p100mc1v1 134 64 35 56.78 9.33 7.31 3.30 2.09 0.80 1o50t100s1p100mc1v2 134 64 35 56.78 9.33 7.31 3.30 2.09 0.80 1o50t100s1p100mc2v1 134 66 35 56.40 8.83 6.81 3.39 2.16 0.80 1o50t100s1p100mc2v2 134 66 35 56.40 8.83 6.81 3.39 2.16 0.80 1o50t100s2p100mc1v1 134 64 35 56.78 9.33 7.31 3.30 2.09 0.80 1o50t100s2p100mc1v2 134 64 35 56.78 9.33 7.31 3.30 2.09 0.80 1o50t100s2p100mc2v1 134 66 35 56.40 8.83 6.81 3.39 2.16 0.80 1o50t100s2p100mc2v2 134 66 35 56.40 8.83 6.81 3.39 2.16 0.80 2o50t100s1p100mc1v1 177 93 61 58.25 9.49 7.30 3.34 1.90 0.79 2o50t100s1p100mc1v2 177 93 61 58.25 9.49 7.30 3.34 1.90 0.79 2o50t100s1p100mc2v1 177 88 61 58.67 9.54 7.25 3.17 2.04 0.85 2o50t100s1p100mc2v2 177 88 61 58.67 9.54 7.25 3.17 2.04 0.85 2o50t100s2p100mc1v1 177 93 70 58.25 9.49 7.30 3.34 1.90 0.79 2o50t100s2p100mc1v2 177 93 70 58.25 9.49 7.30 3.34 1.90 0.79 2o50t100s2p100mc2v1 177 88 70 58.67 9.54 7.25 3.17 2.04 0.85 2o50t100s2p100mc2v2 177 88 70 58.67 9.54 7.25 3.17 2.04 0.85 1012 S.R.Kancharla et al. 5.2 Stochasticity inBoth Meal Preparation Times andFuture Orders This problem lacks established benchmark results. Consequently, we employ our Stochastic Approximation Algorithm (SAA) framework to generate stochastic and deterministic solutions where all random variables are substituted with their expected values. Subsequently, we compare both solutions’ routing costs (first stage) and recourse costs (second stage). Algorithm2 is applied to compute the expected recourse cost, utilizing a scenario sample size of |Ω| = 1000. This experiment illustrates the impact of incorporating uncertainty on a stochastic solution’s first-stage decisions and costs. In Fig.1, we present a comparison between the deterministic and stochastic solutions for the instances detailed in Table1 using the recourse R. It is important to note that in R, no corrective actions are implemented; the second-stage costs solely account for penalties accrued due to missed orders and delays. This experiment generates scenarios with a coefficient of variance cv = 0.25. The results are averaged over three iterations of the SAA framework. Table 3 indicates that employing probabilistic information, rather than relying solely on expected values, substantially boosts the objective value. This increase is primarily attributed to a significant rise in the total number of orders served, with an average increase of more than 13% across all datasets. However, it’s important to note that the computational runtime experiences a substantial surge, exceeding 90% in all cases. This increase in runtime can be primarily attributed to the need for repeated solving for N replications of the SAA. We ran two scenarios to see which stochastic variable is causing the significant increase in the number of orders served and, thereby, the objective value. In the first case, stochastic information about the meal preparation time alone is considered, and future orders are not considered. In the second case, stochastic information about the number of future orders alone is considered, and meal preparation times are assumed to be known. 5.3 Stochasticity Only forMeal Preparation Times Like the previous scenario, we analyze the routing and recourse costs in stochastic and deterministic contexts. Figure2 and Table4 depict the outcomes. Interestingly, incorporating stochastic data solely for meal preparation times did not significantly Table 2 Effect of the value of N on objective and runtime N Objective Runtime (s) % ↑ Obj % ↑ runtime 20 1624.02 3052 − − 40 1642.56 3759 1.14 23.17 60 1773.14 5867 7.95 56.05 80 1777.79 7526 0.26 28.28 100 1780.33 11348 0.14 50.79 1013 Meal Delivery Routing Problem withStochastic Meal Preparation… enhance the solution compared to the deterministic approach. This was despite a considerable increase in runtime due to repeated problem-solving. Furthermore, not considering future orders led to a notable drop in the objective value, exceeding 20% compared to the scenario where both meal preparation time and future orders Objective RecourseCost RouteCost Set−0Set−1Set−2 Set−0 Set−1Set−2 Set−0 Set−1 Set−2 −1000 0 1000 2000 Instance set value Solution Deterministic Stochastic Fig. 1 Comparison of stochastic and deterministic solutions Table 3 Percentage change in Objective value, Orders missed, and runtime by including probabilistic information of both meal preparation time and future orders Instance set Percentage change ↑ Objective value ↓ Orders missed ↑ Runtime Set-0 36.79 15.67 90.22 Set-1 27.56 17.16 90.18 Set-2 34.43 13.56 90.24 Objective RecourseCost RouteCost Set−0Set−1 Set−2 Set−0 Set−1 Set−2 Set−0 Set−1 Set−2 −500 0 500 1000 1500 Instance set value Solution Deterministic Stochastic Fig. 2 Comparison of stochastic and deterministic solutions with meal preparation time as the only stochastic variable 1014 S.R.Kancharla et al. were considered stochastically. However, it is important to note that there was still an improvement over the purely deterministic solution. 5.4 Stochasticity Only forFuture Orders Here, we assume that meal preparation times are predetermined while the number of future orders follows a probability distribution. Figure3 and Table5 illustrate the impact of incorporating probabilistic information instead of relying solely on expected values. Notably, we observe a substantial improvement in the objective value, exceeding 32%, and an increase in the number of orders served by more than 13%. As expected, this enhancement comes at the cost of a significant runtime increase of over 90%. This approach yields superior solutions when considering meal preparation times and future orders as stochastic variables. The primary driver of this improvement is the precise knowledge of meal preparation times. 5.5 Variation intheLevel ofStochasticity forBoth Meal Preparation Times andFuture Orders Our study aimed to explore how varying degrees of randomness in the system affect its performance, specifically looking at meal preparation times and order Table 4 Percentage change in Objective value, Orders missed, and runtime by including probabilistic information only for meal preparation times Instance set Percentage change ↑ Objective ↓ Orders missed ↑ Runtime Set-0 0.73 0.40 66.37 Set-1 3.60 0.93 62.45 Set-2 6.45 0.42 64.99 Objective RecourseCost RouteCost Set−0Set−1Set−2 Set−0 Set−1Set−2 Set−0 Set−1 Set−2 −1000 0 1000 2000 Instance set value Solution Deterministic Stochastic Fig. 3 Comparison of stochastic and deterministic solutions with the number of future orders as the only stochastic variable 1015 Meal Delivery Routing Problem withStochastic Meal Preparation… frequencies. We employed two statistical distributions to achieve this: the gamma distribution for meal preparation times and the Poisson distribution for the number of orders. We adjusted a range of parameters within these distributions to simulate different levels of variability. Firstly, we altered the gamma distribution’s shape parameter, which controls the variability of meal preparation times. The idea was to mimic real-world scenarios where some meals might be prepared quickly while others take longer. By increasing the shape parameter, we introduced greater unpredictability in preparation times, reflecting a more realistic and challenging environment for the system. Secondly, we modified the lambda parameter in the Poisson distribution, which dictates the average frequency of orders. This allowed us to simulate high and loworder periods, examining how the system copes with fluctuating demand. Through these adjustments, we sought to understand the system’s resilience to uncertainty comprehensively. As illustrated in Fig.4, the results revealed a direct correlation: higher variability in both meal preparation times and order frequencies led to an increase in missing orders. This, in turn, had a ripple effect, causing a rise Table 5 Percentage change in Objective value, Orders missed, and runtime by including probabilistic information only for future orders Instance set Percentage change ↑ Objective ↓ Orders missed ↑ Runtime Set-0 46.06 16.67 91.19 Set-1 32.96 13.18 90.38 Set-2 47.11 14.50 90.30 Fig. 4 Comparison of solutions with variation in the level of stochasticity for both meal preparation times and future orders 1016 S.R.Kancharla et al. in both route and recourse costs as the system struggled to adapt to the heightened unpredictability. This finding highlights the challenge of dealing with increased uncertainty in the system. As the orders and meal preparation times became more unpredictable, the system had difficulty managing resources and planning routes effectively. Despite efforts to adapt, the system faced more missed orders, driving up costs. These observations, as illustrated in Fig.4, emphasize the delicate balance needed to handle the complexities of heightened uncertainty. 5.6 Variation intheLevel ofStochasticity Only forMeal Preparation Times To study the impact of stochasticity in meal preparation times, we maintained a consistent order distribution while varying the levels of uncertainty in meal preparation. As depicted in Fig.5, there was a substantial rise in the percentage of missed orders, exceeding 40% in certain instances, especially when the shape parameter was increased by 50%. This trend was consistently observed across all three sets of instances. As uncertainty increased and the distribution spread wider, meal preparation times grew longer. This extended waiting period affected delivery drivers, causing them to experience delays. Consequently, many orders had to be rejected due to the shortage of available drivers. This situation leads to delayed deliveries and results in lost sales opportunities and operational inefficiencies. Managing meal preparation times effectively is vital to optimizing resources, minimizing order rejections, and enhancing operational efficiency and customer satisfaction. Fig. 5 Comparison of solutions with variation in the level of stochasticity only for meal preparation times 1017 Meal Delivery Routing Problem withStochastic Meal Preparation… 5.7 Variation intheLevel ofStochasticity Only forFuture Orders To study the impact of stochasticity on the number of orders, we maintained consistent meal preparation times while introducing different levels of uncertainty in future order numbers. As illustrated in Fig.6, Surprisingly, the variation in future orders did not significantly influence the number of missed orders. A closer analysis reveals an interesting phenomenon: a slightly higher influx of orders within shorter intervals might have resulted in the occasional missing of a few orders during peak rush periods. However, because the total number of orders remained constant, this brief rush was followed by relatively quieter periods. During quieter periods, all orders were successfully delivered because more time was available to handle these orders, given that they were spread out over a longer time frame. 6 Conclusions We introduced uncertainties in meal preparation times and future order locations as stochastic variables, emphasizing the crucial need to incorporate these uncertainties in route planning. Our approach involved employing a Sample Average Approximation method within a rolling horizon framework, utilizing the Adaptive Large Neighborhood Search algorithm for the first-stage problem, and implementing a recourse action in the second stage. We made significant observations Through extensive experiments on instances derived from Grubhub MDRP instances. The utilization of variables, rather than Fig. 6 Comparison of solutions with variation in the level of stochasticity only for future orders 1018 S.R.Kancharla et al. expected values, resulted in notably profitable routes, primarily due to accommodating a larger number of orders. We explored scenarios where individual uncertainties were relaxed. Notably, the performance did not significantly improve when uncertainty was considered, only in meal preparation times and disregarding future orders. It was, in fact, 20% worse due to the absence of future order considerations. Conversely, when only future orders were regarded as uncertain and meal preparation was assumed known, performance significantly improved, displaying an average enhancement of over 30%. Furthermore, our study delved into the intricate dynamics of operational uncertainties. We discovered that increased stochasticity could lead to more missed orders and escalated operational costs. Interestingly, occasional order misses were observed during peak demand periods, but these were compensated for during quieter times. The effective management of meal preparation times emerged as a pivotal factor influencing order rejections, customer satisfaction, and overall operational efficiency. These findings underscore the necessity of adaptive strategies in balancing these trade-offs effectively, offering valuable insights for decision-makers in the operational management domain. Author Contributions The authors confirm contribution to the paper as follows: study conception and design: S.K and S.U; analysis and interpretation of results: S.K, T.W, S.U, and S.W; draft manuscript preparation: S.K. All authors reviewed the manuscript. Funding Open Access funding enabled and organized by Projekt DEAL. This research received no specific grant from funding agencies in the public, commercial, or not-for-profit sectors. Data Availability Publicly available data sources are used. Declarations Competing interests The authors declare no competing interests. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. References Bianchi L, Dorigo M, Gambardella LM, Gutjahr WJ (2009) A survey on metaheuristics for stochastic combinatorial optimization. Nat Comput 8:239–287. https:// doi. org/ 10. 1007/ s110470089098-4 Chu JC, Yan S, Huang HJ (2015) A multi-trip split-delivery vehicle routing problem with time windows for inventory replenishment under stochastic travel times. Netw Spat Econ 17:41–68. https:// doi. org/ 10. 1007/ s110670159317-3 1019 Meal Delivery Routing Problem withStochastic Meal Preparation… Fachini RF, Armentano VA, Toledo FMB (2022) A granular local search matheuristic for a heterogeneous fleet vehicle routing problem with stochastic travel times. Netw Spat Econ 22:33–64. https:// doi. org/ 10. 1007/ s1106702109553-6 Ghilas V, Demir E, Van Woensel T (2016a) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines. Comput Oper Res 72:12–30. https:// doi. org/ 10. 1016/j. cor. 2016. 01. 018 Ghilas V, Demir E, Woensel TV (2016b) A scenario-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands. Transp Res Part B: Methodological 91:34–51. https:// doi. org/ 10. 1016/j. trb. 2016. 04. 015 Gutjahr WJ (2011) Recent trends in metaheuristics for stochastic combinatorial optimization. Central Eur J Comput Sci 1:58–66. https:// doi. org/ 10. 2478/ s135370110003-3 Györgyi P, Kis T (2019) A probabilistic approach to pickup and delivery problems with time window uncertainty. Eur J Oper Res 274:909–923. https:// doi. org/ 10. 1016/j. ejor. 2018. 10. 031 Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput Oper Res 39:3215–3228. https:// doi. org/ 10. 1016/j. cor. 2012. 04. 007 Karoonsoontawong A, Punyim P, Nueangnitnaraporn W, Ratanavaraha V (2020) Multi-trip time-dependent vehicle routing problem with soft time windows and overtime constraints. Netw Spat Econ 20:549–598. https:// doi. org/ 10. 1007/ s1106701909492-3 Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J Optim 12:479–502. https:// doi. org/ 10. 1137/ S1052 62349 93632 20 Laporte G, Louveaux FV, van Hamme L (2002) An integer l-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper Res 50:415–423 Li Y, Chen H, Prins C (2016) Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests. Eur J Oper Res 252:27–38. https:// doi. org/ 10. 1016/j. ejor. 2015. 12. 032 Liao W, Zhang L, Wei Z (2020) Multi-objective green meal delivery routing problem based on a twostage solution strategy. J Clean Prod 258:120627. https:// doi. org/ 10. 1016/j. jclep ro. 2020. 120627 Liu FT, Ting KM, Zhou ZH (2008) Isolation forest. In: 2008 Eighth IEEE international conference on data mining, pp 413–422. https:// doi. org/ 10. 1109/ ICDM. 2008. 17 Liu Y (2019) An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Comput Oper Res 111:1–20. https:// doi. org/ 10. 1016/j. cor. 2019. 05. 024 Powell WB, Sheffi Y, Nickerson KS, Butterbaugh K, Atherton S (1988) Maximizing profits for north american van lines’ truckload division: A new framework for pricing and operations. Interfaces 18:21–41. https:// doi. org/ 10. 1287/ inte. 18.1. 21 Reyes D, Erera AL, Savelsbergh MWP, Sahasrabudhe S, O ’Neil RJ (2018) The meal delivery routing problem. Optimization Online, pp 1–70 Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40:455–472 Secomandi N, Margot F (2009) Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper Res 57:214–230. https:// doi. org/ 10. 1287/ opre. 1080. 0520 Shi Y, Boudouh T, Grunder O, Wang D (2018) Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care. Expert Syst Appl 102:218– 233. https:// doi. org/ 10. 1016/j. eswa. 2018. 02. 025 Steever Z, Karwan M, Murray C (2019) Dynamic courier routing for a food delivery service. Comput Oper Res 107:173–188. https:// doi. org/ 10. 1016/j. cor. 2019. 03. 008 Ulmer MW, Thomas BW, Campbell AM, Woyak N (2021) The restaurant meal delivery problem: Dynamic pickup and delivery with deadlines and random ready times. Transp Sci 55:75–100. https:// doi. org/ 10. 1287/ TRSC. 2020. 1000 Verweij B, Ahmed S, Kleywegt AJ, Nemhauser G, Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: A computational study. Comput Optim Appl 24:289–333. https:// doi. org/ 10. 1023/A: 10218 14225 969 Wang Z, Dessouky M, Van Woensel T, Ioannou P (2023) Pickup and delivery problem with hard time windows considering stochastic and time-dependent travel times. EURO J Transp Logist 12:100099. https:// doi. org/ 10. 1016/j. ejtl. 2022. 100099 Yildiz B, Savelsbergh M (2019) Provably High-quality solutions for the meal delivery routing problem. Transp Sci 53:1372–1388. https:// doi. org/ 10. 1287/ trsc. 2018. 0887 1020 S.R.Kancharla et al. Zhang J, Luo K, Florio AM, Van Woensel T (2023) Solving large-scale dynamic vehicle routing problems with stochastic requests. European J Oper Res 306:596–614. https:// doi. org/ 10. 1016/j. ejor. 2022. 07. 015 Zheng J, Wang L, Wang L, Wang S, Chen JF, Wang X (2023) Solving stochastic online food delivery problem via iterated greedy algorithm with decomposition-based strategy. IEEE Trans Syst Man Cybern: Systems 53:957–969. https:// doi. org/ 10. 1109/ TSMC. 2022. 31897 71 Zhu L, Sheu JB (2018a) Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands. European J Oper Res 271:896–912. https:// doi. org/ 10. 1016/j. ejor. 2018. 05. 049 Zhu L, Sheu JB (2018b) Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands. Eur J Oper Res 271:896–912. https:// doi. org/ 10. 1016/j. ejor. 2018. 05. 049 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.