[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v143y2020ics1366554520307341.html
   My bibliography  Save this article

Request acceptance in same-day delivery

Author

Listed:
  • Klapp, Mathias A.
  • Erera, Alan L.
  • Toriello, Alejandro
Abstract
We study request acceptance dynamics in same-day delivery systems by formulating the Dynamic Dispatch Waves Problem with Immediate Acceptance, which models integrated management and distribution for dynamically arriving customer requests. We consider an e-commerce platform that attempts to serve most customers with same-day delivery service. When a shopper attempts to place an order, a decision is made immediately to offer same-day delivery service (accept the request) or to deny service. Accepted requests are not available for immediate dispatch; they must be processed (picked and packed) before they are loaded for delivery. Vehicle routes are updated dynamically and serve each accepted delivery request no later than the end of the service day. In this work, we limit the study to the case of a single vehicle serving requests, potentially using multiple trips from the distribution center. The objective is to make request acceptance and distribution decisions that minimize the expected sum of vehicle travel costs and penalties for service denials. We develop a framework for dynamic decision policies over continuous time for such systems, where a feasible vehicle dispatch plan is redesigned and used to guide decisions over time. We design methods for determining an initial optimal a priori plan and for updating the plan using a heuristic roll-out procedure. Our methods are tested on a family of simulated instances against two common-sense benchmarks and an infeasible relaxed policy that allows the dispatcher to delay the acceptance or rejection of a request until the end of the service day. We demonstrate in our computational study that the cost-per-request of the best benchmark policy is on average 9.7% higher than our proposed dynamic policy and furthermore that the dynamic policy leads to only a 4.4% cost increase over the infeasible relaxed policy lower bound.

Suggested Citation

  • Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2020. "Request acceptance in same-day delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    • Handle: RePEc:eee:transe:v:143:y:2020:i:c:s1366554520307341
    DOI: 10.1016/j.tre.2020.102083
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554520307341
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2020.102083?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. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    4. Nicola Secomandi & François Margot, 2009. "Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 57(1), pages 214-230, February.
    5. Ann Melissa Campbell & Martin W. P. Savelsbergh, 2005. "Decision Support for Consumer Direct Grocery Initiatives," Transportation Science, INFORMS, vol. 39(3), pages 313-327, August.
    6. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates," Transportation Science, INFORMS, vol. 50(2), pages 676-693, May.
    7. Irnich, S. & Schneider, M. & Vigo, D., 2014. "Four Variants of the Vehicle Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63514, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. Ulmer, Marlin W. & Soeffker, Ninja & Mattfeld, Dirk C., 2018. "Value function approximation for dynamic multi-period vehicle routing," European Journal of Operational Research, Elsevier, vol. 269(3), pages 883-899.
    9. Patrick Jaillet, 1988. "A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited," Operations Research, INFORMS, vol. 36(6), pages 929-936, December.
    10. Gilbert Laporte & François V. Louveaux & Hélène Mercure, 1994. "A Priori Optimization of the Probabilistic Traveling Salesman Problem," Operations Research, INFORMS, vol. 42(3), pages 543-549, June.
    11. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2018. "The Dynamic Dispatch Waves Problem for same-day delivery," European Journal of Operational Research, Elsevier, vol. 271(2), pages 519-534.
    12. Justin C. Goodson & Jeffrey W. Ohlmann & Barrett W. Thomas, 2013. "Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits," Operations Research, INFORMS, vol. 61(1), pages 138-154, February.
    13. Martin Savelsbergh & Tom Van Woensel, 2016. "50th Anniversary Invited Article—City Logistics: Challenges and Opportunities," Transportation Science, INFORMS, vol. 50(2), pages 579-590, May.
    14. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    15. Archetti, Claudia & Feillet, Dominique & Speranza, M. Grazia, 2015. "Complexity of routing problems with release dates," European Journal of Operational Research, Elsevier, vol. 247(3), pages 797-803.
    16. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.
    17. Nabila Azi & Michel Gendreau & Jean-Yves Potvin, 2012. "A dynamic vehicle routing problem with multiple delivery routes," Annals of Operations Research, Springer, vol. 199(1), pages 103-112, October.
    18. Goodson, Justin C. & Thomas, Barrett W. & Ohlmann, Jeffrey W., 2017. "A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 216-229.
    19. David B. Brown & James E. Smith & Peng Sun, 2010. "Information Relaxations and Duality in Stochastic Dynamic Programs," Operations Research, INFORMS, vol. 58(4-part-1), pages 785-801, August.
    20. Niels Agatz & Ann Campbell & Moritz Fleischmann & Martin Savelsbergh, 2011. "Time Slot Management in Attended Home Delivery," Transportation Science, INFORMS, vol. 45(3), pages 435-449, August.
    21. Paolo Toth & Daniele Vigo, 2003. "The Granular Tabu Search and Its Application to the Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 333-346, November.
    22. Marlin W. Ulmer & Dirk C. Mattfeld & Felix Köster, 2018. "Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests," Transportation Science, INFORMS, vol. 52(1), pages 20-37, January.
    23. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    24. Maria Battarra & Güneş Erdoğan & Daniele Vigo, 2014. "Exact Algorithms for the Clustered Vehicle Routing Problem," Operations Research, INFORMS, vol. 62(1), pages 58-71, February.
    25. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    26. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yuki Oyama & Daisuke Fukuda & Naoto Imura & Katsuhiro Nishinari, 2022. "E-commerce users' preferences for delivery options," Papers 2301.00666, arXiv.org, revised Aug 2023.
    2. Waßmuth, Katrin & Köhler, Charlotte & Agatz, Niels & Fleischmann, Moritz, 2023. "Demand management for attended home delivery—A literature review," European Journal of Operational Research, Elsevier, vol. 311(3), pages 801-815.
    3. Gilles Paché, 2023. "La Distribution Digitalisée À La Croisée Des Chemins," Post-Print hal-04341643, HAL.
    4. Côté, Jean-François & Alves de Queiroz, Thiago & Gallesi, Francesco & Iori, Manuel, 2023. "A branch-and-regret algorithm for the same-day delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    5. Banerjee, Dipayan & Erera, Alan L. & Stroh, Alexander M. & Toriello, Alejandro, 2023. "Who has access to e-commerce and when? Time-varying service regions in same-day delivery," Transportation Research Part B: Methodological, Elsevier, vol. 170(C), pages 148-168.
    6. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    7. Oyama, Yuki & Fukuda, Daisuke & Imura, Naoto & Nishinari, Katsuhiro, 2024. "Do people really want fast and precisely scheduled delivery? E-commerce customers' valuations of home delivery timing," Journal of Retailing and Consumer Services, Elsevier, vol. 78(C).
    8. Chen, Xinwei & Wang, Tong & Thomas, Barrett W. & Ulmer, Marlin W., 2023. "Same-day delivery with fair customer service," European Journal of Operational Research, Elsevier, vol. 308(2), pages 738-751.
    9. Klein, Vienna & Steinhardt, Claudius, 2023. "Dynamic demand management and online tour planning for same-day delivery," European Journal of Operational Research, Elsevier, vol. 307(2), pages 860-886.
    10. Chen, Xi & Li, Kaiwen & Lin, Sidian & Ding, Xiaosong, 2024. "Technician routing and scheduling with employees’ learning through implicit cross-training strategy," International Journal of Production Economics, Elsevier, vol. 271(C).
    11. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    12. Chen, Xinwei & Ulmer, Marlin W. & Thomas, Barrett W., 2022. "Deep Q-learning for same-day delivery with vehicles and drones," European Journal of Operational Research, Elsevier, vol. 298(3), pages 939-952.
    13. Scherr, Yannick Oskar & Gansterer, Margaretha & Hartl, Richard F., 2024. "Request acceptance with overbooking in dynamic and collaborative vehicle routing," European Journal of Operational Research, Elsevier, vol. 314(2), pages 612-629.

    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. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2018. "The Dynamic Dispatch Waves Problem for same-day delivery," European Journal of Operational Research, Elsevier, vol. 271(2), pages 519-534.
    2. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    3. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    4. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    5. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    6. Anirudh Subramanyam & Frank Mufalli & José M. Lí?nez-Aguirre & Jose M. Pinto & Chrysanthos E. Gounaris, 2021. "Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty," Operations Research, INFORMS, vol. 69(1), pages 30-60, January.
    7. Ulmer, Marlin W. & Thomas, Barrett W., 2020. "Meso-parametric value function approximation for dynamic customer acceptances in delivery routing," European Journal of Operational Research, Elsevier, vol. 285(1), pages 183-195.
    8. Zhang, Jian & Luo, Kelin & Florio, Alexandre M. & Van Woensel, Tom, 2023. "Solving large-scale dynamic vehicle routing problems with stochastic requests," European Journal of Operational Research, Elsevier, vol. 306(2), pages 596-614.
    9. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    10. Marlin W. Ulmer & Barrett W. Thomas, 2019. "Enough Waiting for the Cable Guy—Estimating Arrival Times for Service Vehicle Routing," Transportation Science, INFORMS, vol. 53(3), pages 897-916, May.
    11. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 53(5), pages 1334-1353, September.
    12. Ouyang, Zhiyuan & Leung, Eric K.H. & Huang, George Q., 2023. "Community logistics and dynamic community partitioning: A new approach for solving e-commerce last mile delivery," European Journal of Operational Research, Elsevier, vol. 307(1), pages 140-156.
    13. Côté, Jean-François & Alves de Queiroz, Thiago & Gallesi, Francesco & Iori, Manuel, 2023. "A branch-and-regret algorithm for the same-day delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    14. Klein, Vienna & Steinhardt, Claudius, 2023. "Dynamic demand management and online tour planning for same-day delivery," European Journal of Operational Research, Elsevier, vol. 307(2), pages 860-886.
    15. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    16. Avraham, Edison & Raviv, Tal, 2021. "The steady-state mobile personnel booking problem," Transportation Research Part B: Methodological, Elsevier, vol. 154(C), pages 266-288.
    17. Liu, Zeyu & Li, Xueping & Khojandi, Anahita, 2022. "The flying sidekick traveling salesman problem with stochastic travel time: A reinforcement learning approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    18. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    19. Marlin W. Ulmer, 2020. "Horizontal combinations of online and offline approximate dynamic programming for stochastic dynamic vehicle routing," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 279-308, March.
    20. Marlin W. Ulmer & Barrett W. Thomas & Dirk C. Mattfeld, 2019. "Preemptive depot returns for dynamic same-day delivery," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 327-361, December.

    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:143:y:2020:i:c:s1366554520307341. 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.