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

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.