IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v170y2023icp194-220.html
   My bibliography  Save this article

An Adaptive Large Neighborhood Search heuristic for last-mile deliveries under stochastic customer availability and multiple visits

Author

Listed:
  • Özarık, Sami Serkan
  • Lurkin, Virginie
  • Veelenturf, Lucas P.
  • Van Woensel, Tom
  • Laporte, Gilbert

Abstract

Attended Home Delivery, where customer attendance at home is required, is an essential last-mile delivery challenge, e.g., for valuable, perishable, or oversized items. Logistics service providers are often faced no-show customers. In this paper, we consider the delivery problem in which customers can be revisited on the same day by a courier in the case of a failed first delivery attempt. Specifically, customer presence uncertainty is considered in a two-stage stochastic program, where penalties are introduced as recourse actions for failed deliveries. We build on the notion of a customer availability profile defined as a profile containing historical time-varying probability information of successful deliveries. We tackle this stochastic program by developing an efficient parallelized Adaptive Large Neighborhood Search algorithm. Our results show that by achieving a right balance between increasing the hit rate and reducing travel cost, logistics service providers can realize costs savings as high as 32% if they plan for second visits on the same day.

Suggested Citation

  • Ö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.
    • Handle: RePEc:eee:transb:v:170:y:2023:i:c:p:194-220
    DOI: 10.1016/j.trb.2023.02.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261523000358
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2023.02.016?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. 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.
    2. Fei Gao & Xuanming Su, 2017. "Omnichannel Retail Operations with Buy-Online-and-Pick-up-in-Store," Management Science, INFORMS, vol. 63(8), pages 2478-2492, August.
    3. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    4. Florio, Alexandre M. & Feillet, Dominique & Hartl, Richard F., 2018. "The delivery problem: Optimizing hit rates in e-commerce deliveries," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 455-472.
    5. 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.
    6. Ö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).
    7. Wang, Yuan & Zhang, Dongxiang & Liu, Qing & Shen, Fumin & Lee, Loo Hay, 2016. "Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 279-293.
    8. Mike Hewitt & Barrett W. Thomas, 2018. "Special Issue on Uncertainty in Logistics and Transportation Systems," Transportation Science, INFORMS, vol. 52(1), pages 1-2, January.
    9. 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.
    10. Han, Shuihua & Zhao, Ling & Chen, Kui & Luo, Zong-wei & Mishra, Deepa, 2017. "Appointment scheduling and routing optimization of attended home delivery system with random customer behavior," European Journal of Operational Research, Elsevier, vol. 262(3), pages 966-980.
    11. Marlin W. Ulmer, 2020. "Dynamic Pricing and Routing for Same-Day Delivery," Transportation Science, INFORMS, vol. 54(4), pages 1016-1033, July.
    12. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    13. Strauss, Arne & Gülpınar, Nalan & Zheng, Yijun, 2021. "Dynamic pricing of flexible time slots for attended home delivery," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1022-1041.
    14. Michel Gendreau & Ola Jabali & Walter Rei, 2016. "50th Anniversary Invited Article—Future Research Directions in Stochastic Vehicle Routing," Transportation Science, INFORMS, vol. 50(4), pages 1163-1173, November.
    15. Shenle Pan & Vaggelis Giannikas & Yufei Han & Etta Grover-Silva & Bin Qiao, 2017. "Using Customer-related Data to Enhance E-grocery Home Delivery," Post-Print hal-01482901, HAL.
    16. Jin, Ming & Li, Gang & Cheng, T.C.E., 2018. "Buy online and pick up in-store: Design of the service area," European Journal of Operational Research, Elsevier, vol. 268(2), pages 613-623.
    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. Mo, Pengli & Yao, Yu & D’Ariano, Andrea & Liu, Zhiyuan, 2023. "The vehicle routing problem with underground logistics: Formulation and algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).

    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. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    2. 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.
    3. Ö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).
    4. 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.
    5. John Olsson & Daniel Hellström & Henrik Pålsson, 2019. "Framework of Last Mile Logistics Research: A Systematic Review of the Literature," Sustainability, MDPI, vol. 11(24), pages 1-25, December.
    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. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2020. "Two-echelon vehicle routing problem with time windows and mobile satellites," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 179-201.
    8. Maaike Hoogeboom & Yossiri Adulyasak & Wout Dullaert & Patrick Jaillet, 2021. "The Robust Vehicle Routing Problem with Time Window Assignments," Transportation Science, INFORMS, vol. 55(2), pages 395-413, March.
    9. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    10. 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.
    11. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    12. Ali, Ousmane & Côté, Jean-François & Coelho, Leandro C., 2021. "Models and algorithms for the delivery and installation routing problem," European Journal of Operational Research, Elsevier, vol. 291(1), pages 162-177.
    13. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "A review of recent research on green road freight transportation," European Journal of Operational Research, Elsevier, vol. 237(3), pages 775-793.
    14. Rahma Lahyani & Mahdi Khemakhem & Frédéric Semet, 2017. "A unified matheuristic for solving multi-constrained traveling salesman problems with profits," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 393-422, September.
    15. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    16. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2017. "A hybrid solution approach for the 3L-VRP with simultaneous delivery and pickups," FEMM Working Papers 170005, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    17. Franceschetti, Anna & Demir, Emrah & Honhon, Dorothée & Van Woensel, Tom & Laporte, Gilbert & Stobbe, Mark, 2017. "A metaheuristic for the time-dependent pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 259(3), pages 972-991.
    18. Alexandre M. Florio & Richard F. Hartl & Stefan Minner & Juan-José Salazar-González, 2021. "A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints," Transportation Science, INFORMS, vol. 55(1), pages 122-138, 1-2.
    19. Ran Liu & Zhibin Jiang, 2019. "A constraint relaxation-based algorithm for the load-dependent vehicle routing problem with time windows," Flexible Services and Manufacturing Journal, Springer, vol. 31(2), pages 331-353, June.
    20. TURKEŠ, Renata & SÖRENSEN, Kenneth & HVATTUM, Lars Magnus & BARRENA, Eva & CHENTLI, Hayet & COELHO, Leandro & DAYARIAN, Iman & GRIMAULT, Axel & GULLHAVE, Anders & IRIS, Çagatay & KESKIN, Merve & KIEFE, 2019. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," Working Papers 2019002, University of Antwerp, Faculty of Business and Economics.

    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:transb:v:170:y:2023:i:c:p:194-220. 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/548/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.