IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v193y2025ics1366554524004368.html
   My bibliography  Save this article

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

Author

Listed:
  • Xue, Guiqin
  • Wang, Zheng
  • Sheu, Jiuh-Biing

Abstract

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.

Suggested Citation

  • Xue, Guiqin & Wang, Zheng & Sheu, Jiuh-Biing, 2025. "Meal pickup and delivery problem with appointment time and uncertainty in order cancellation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    • Handle: RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004368
    DOI: 10.1016/j.tre.2024.103845
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554524004368
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2024.103845?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    2. Zhang, Dali & Li, Dong & Sun, Hailin & Hou, Liwen, 2021. "A vehicle routing problem with distribution uncertainty in deadlines," European Journal of Operational Research, Elsevier, vol. 292(1), pages 311-326.
    3. Quddus, Md Abdul & Kabli, Mohannad & Marufuzzaman, Mohammad, 2019. "Modeling electric vehicle charging station expansion with an integration of renewable energy and Vehicle-to-Grid sources," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 251-279.
    4. Xinshang Wang & Van-Anh Truong, 2018. "Multi-Priority Online Scheduling with Cancellations," Operations Research, INFORMS, vol. 66(1), pages 104-122, January.
    5. Lin, Na & Akkerman, Renzo & Kanellopoulos, Argyris & Hu, Xiangpei & Wang, Xuping & Ruan, Junhu, 2023. "Vehicle routing with heterogeneous service types: Optimizing post-harvest preprocessing operations for fruits and vegetables in short food supply chains," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    6. Bach, Lukas & Hasle, Geir & Schulz, Christian, 2019. "Adaptive Large Neighborhood Search on the Graphics Processing Unit," European Journal of Operational Research, Elsevier, vol. 275(1), pages 53-66.
    7. Xian Yu & Siqian Shen & Huizhu Wang, 2021. "Integrated Vehicle Routing and Service Scheduling Under Time and Cancellation Uncertainties with Application in Nonemergency Medical Transportation," Service Science, INFORMS, vol. 13(3), pages 172-191, September.
    8. Mühlbauer, Ferdinand & Fontaine, Pirmin, 2021. "A parallelised large neighbourhood search heuristic for the asymmetric two-echelon vehicle routing problem with swap containers for cargo-bicycles," European Journal of Operational Research, Elsevier, vol. 289(2), pages 742-757.
    9. Yao Chen & Yang Liu, 2023. "Integrated Optimization of Planning and Operations for Shared Autonomous Electric Vehicle Systems," Transportation Science, INFORMS, vol. 57(1), pages 106-134, January.
    10. Tu San Pham & Antoine Legrain & Patrick De Causmaecker & Louis-Martin Rousseau, 2023. "A Prediction-Based Approach for Online Dynamic Appointment Scheduling: A Case Study in Radiotherapy Treatment," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 844-868, July.
    11. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    12. Hasani, Aliakbar & Khosrojerdi, Amirhossein, 2016. "Robust global supply chain network design under disruption and uncertainty considering resilience strategies: A parallel memetic algorithm for a real-life case study," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 87(C), pages 20-52.
    13. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    14. Ruiwei Jiang & Siqian Shen & Yiling Zhang, 2017. "Integer Programming Approaches for Appointment Scheduling with Random No-Shows and Service Durations," Operations Research, INFORMS, vol. 65(6), pages 1638-1656, December.
    15. Özarık, Sami Serkan & Veelenturf, Lucas P. & Woensel, Tom Van & Laporte, Gilbert, 2021. "Optimizing e-commerce last-mile vehicle routing and scheduling under uncertain customer presence," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).
    16. Hai Long Duong & Junhong Chu & Dai Yao, 2023. "Taxi Drivers’ Response to Cancellations and No-Shows: New Evidence for Reference-Dependent Preferences," Management Science, INFORMS, vol. 69(1), pages 179-199, January.
    17. Tsang, Man Yiu & Shehadeh, Karmel S., 2023. "Stochastic optimization models for a home service routing and appointment scheduling problem with random travel and service times," European Journal of Operational Research, Elsevier, vol. 307(1), pages 48-63.
    18. Alexander Shapiro & Yi Cheng, 2023. "Dual Bounds for Periodical Stochastic Programs," Operations Research, INFORMS, vol. 71(1), pages 120-128, January.
    19. Xu, Xun & Yan, Nina & Tong, Tingting, 2021. "Longer waiting, more cancellation? Empirical evidence from an on-demand service platform," Journal of Business Research, Elsevier, vol. 126(C), pages 162-169.
    20. Jan Christiaens & Greet Vanden Berghe, 2020. "Slack Induction by String Removals for Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(2), pages 417-433, March.
    21. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    22. Avijit Mukherjee & Mark Hansen, 2007. "A Dynamic Stochastic Model for the Single Airport Ground Holding Problem," Transportation Science, INFORMS, vol. 41(4), pages 444-456, November.
    23. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    24. R A Russell & T L Urban, 2008. "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1220-1228, September.
    25. Maryam Haghi & Hossein Hashemi Doulabi & Ivan Contreras & Nadia Bhuiyan, 2023. "Integrated consultation and chemotherapy scheduling with stochastic treatment times," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 74(9), pages 2012-2027, September.
    26. Zhan, Xingbin & Szeto, W.Y. & Wang, Yue, 2023. "The ride-hailing sharing problem with parcel transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    27. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    28. Cristian Ramírez-Pico & Ivana Ljubić & Eduardo Moreno, 2023. "Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs," Transportation Science, INFORMS, vol. 57(5), pages 1252-1275, September.
    29. Özarık, Sami Serkan & Lurkin, Virginie & Veelenturf, Lucas P. & Van Woensel, Tom & Laporte, Gilbert, 2023. "An Adaptive Large Neighborhood Search heuristic for last-mile deliveries under stochastic customer availability and multiple visits," Transportation Research Part B: Methodological, Elsevier, vol. 170(C), pages 194-220.
    30. Michel Gendreau & Gilbert Laporte & René Séguin, 1995. "An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers," Transportation Science, INFORMS, vol. 29(2), pages 143-155, May.
    31. Saif Benjaafar & David Chen & Rowan Wang & Zhenzhen Yan, 2023. "Appointment Scheduling Under a Service-Level Constraint," Manufacturing & Service Operations Management, INFORMS, vol. 25(1), pages 70-87, January.
    32. Jean-François Cordeau, 2006. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem," Operations Research, INFORMS, vol. 54(3), pages 573-586, June.
    33. Rohleder, Thomas R. & Klassen, Kenneth J., 2000. "Using client-variance information to improve dynamic appointment scheduling performance," Omega, Elsevier, vol. 28(3), pages 293-302, June.
    34. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    35. Zhou, Shenghai & Li, Debiao & Yin, Yong, 2021. "Coordinated appointment scheduling with multiple providers and patient-and-physician matching cost in specialty care," Omega, Elsevier, vol. 101(C).
    36. Marlin W. Ulmer & Barrett W. Thomas & Ann Melissa Campbell & Nicholas Woyak, 2021. "The Restaurant Meal Delivery Problem: Dynamic Pickup and Delivery with Deadlines and Random Ready Times," Transportation Science, INFORMS, vol. 55(1), pages 75-100, 1-2.
    37. Fikar, Christian & Mild, Andreas & Waitz, Martin, 2021. "Facilitating consumer preferences and product shelf life data in the design of e-grocery deliveries," European Journal of Operational Research, Elsevier, vol. 294(3), pages 976-986.
    38. Yanlu Zhao & Felix Papier & Chung-Piaw Teo, 2024. "Market Thickness in Online Food Delivery Platforms: The Impact of Food Processing Times," Manufacturing & Service Operations Management, INFORMS, vol. 26(3), pages 853-872, May.
    39. Kenan, Nabil & Diabat, Ali, 2022. "The supply chain of blood products in the wake of the COVID-19 pandemic: Appointment scheduling and other restrictions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    40. Y Huang & P Zuniga, 2014. "Effective cancellation policy to reduce the negative impact of patient no-show," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(5), pages 605-615, May.
    41. Jiayi Liu & Diwas KC, 2023. "Nudging Patient Choice: Reducing No-Shows Using Waits Framing Messaging," Operations Research, INFORMS, vol. 71(3), pages 1004-1020, May.
    42. Jianzhe Luo & Vidyadhar G. Kulkarni & Serhan Ziya, 2012. "Appointment Scheduling Under Patient No-Shows and Service Interruptions," Manufacturing & Service Operations Management, INFORMS, vol. 14(4), pages 670-684, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Su, Yue & Dupin, Nicolas & Parragh, Sophie N. & Puchinger, Jakob, 2024. "A Branch-and-Price algorithm for the electric autonomous Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    2. Dong, Huichang & Luo, Zhixing & Huang, Nan & Hu, Hongjian & Qin, Hu, 2025. "The electric vehicle dial-a-ride problem: Integrating ride-sharing and time-of-use electricity pricing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 194(C).
    3. Su, Yue & Dupin, Nicolas & Puchinger, Jakob, 2023. "A deterministic annealing local search for the electric autonomous dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1091-1111.
    4. Dumez, Dorian & Tilk, Christian & Irnich, Stefan & Lehuédé, Fabien & Olkis, Katharina & Péton, Olivier, 2023. "A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows," European Journal of Operational Research, Elsevier, vol. 305(1), pages 64-84.
    5. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    6. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    7. Zhang, Li & Liu, Zhongshan & Yu, Lan & Fang, Ke & Yao, Baozhen & Yu, Bin, 2022. "Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    8. Amin Aghalari & Darweesh Ehssan Salamah & Carlos Marino & Mohammad Marufuzzaman, 2023. "Electric vehicles fast charger location-routing problem under ambient temperature," Annals of Operations Research, Springer, vol. 324(1), pages 721-759, May.
    9. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    10. Jean-François Cordeau & Manuel Iori & Dario Vezzali, 2024. "An updated survey of attended home delivery and service problems with a focus on applications," Annals of Operations Research, Springer, vol. 343(2), pages 885-922, December.
    11. Ma, Tai-Yu & Fang, Yumeng & Connors, Richard D. & Viti, Francesco & Nakao, Haruko, 2024. "A hybrid metaheuristic to optimize electric first-mile feeder services with charging synchronization constraints and customer rejections," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    12. Tang, Lianhua & Li, Yantong & Zhang, Shuai & Wang, Zheng & Coelho, Leandro C., 2025. "Mobile COVID-19 vaccination scheduling with capacity selection," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    13. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    14. Mohamed Amine Masmoudi & Manar Hosny & Emrah Demir & Erwin Pesch, 2020. "Hybrid adaptive large neighborhood search algorithm for the mixed fleet heterogeneous dial-a-ride problem," Journal of Heuristics, Springer, vol. 26(1), pages 83-118, February.
    15. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    16. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    17. Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    18. Molenbruch, Yves & Braekers, Kris & Caris, An, 2017. "Benefits of horizontal cooperation in dial-a-ride services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 107(C), pages 97-119.
    19. Imen Ben Mohamed & Walid Klibi & Olivier Labarthe & Jean-Christophe Deschamps & Mohamed Zied Babai, 2017. "Modelling and solution approaches for the interconnected city logistics," International Journal of Production Research, Taylor & Francis Journals, vol. 55(9), pages 2664-2684, May.
    20. Amirmahdi Tafreshian & Neda Masoud & Yafeng Yin, 2020. "Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions," Service Science, INFORMS, vol. 12(2-3), pages 44-60, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004368. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.