Meal pickup and delivery problem with appointment time and uncertainty in order cancellation

Online-ordered meal logistics services (OMLSs) that accept online bookings and make vehicle plans to deliver meals from restaurants to customers have recently emerged. Customers have the option to cancel orders that are not delivered by appointment times, leading to significant financial, reputational, and customer losses for the OMLS providers. This study aims to make an appropriate vehicle plan for OMLS providers to minimize the expected total cost under the uncertainty of order cancellations. The problem is formulated as a two-stage stochastic programming model, and sample average approximation equivalent problems are generated using Monte Carlo simulation. To solve the equivalent problems, a parallel adaptive large neighborhood search (pALNS) with statistical guarantees is developed. Experiment results show that the vehicle plan derived from the ALNS is much better than the solution found by Gurobi within 10,800 s, with an average improvement of 14.90%. Additionally, the pALNS provides better statistical bounds in a shorter time compared to both the ALNS and the unsynchronized pALNS. Analytical experiments reveal that earlier cancellations lead to more severe consequences, offering valuable insights for OMLS providers to implement proactive measures to retain “urgent” customers.