IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v25y2025i3d10.1007_s12351-025-00955-9.html
   My bibliography  Save this article

Integrating incentive-driven delivery options and time-dependent routing decisions with availability profiles

Author

Listed:
  • Dong Lei

    (Xi’an Jiaotong University)

  • Zhen Yang

    (Xi’an Jiaotong University
    Xi’an Jiaotong University
    State Key Lab for Manufacturing Systems Engineering)

  • Tao Jia

    (Xi’an Jiaotong University)

Abstract

As e-commerce continues to evolve, the issue of first delivery failures due to customers not being at home has become increasingly prominent, significantly increasing the operational costs of logistics companies. This paper considers an incentive-driven (ID) strategy, whereby logistics companies offer cash rewards to encourage customers to choose a designated delivery location instead of home delivery. However, there is uncertainty regarding whether customers will accept this incentive. We model this problem as a two-stage stochastic programming problem with incentive uncertainty. Furthermore, considering the impact of urban traffic conditions on delivery efficiency, this paper embeds the ID strategy into a time-dependent routing decision problem with customer-individual availability profiles (APs), where the APs consist of a set of time windows (TWs). Each TW is associated with both the cost of delivery failure and the probability of successful delivery. We refer to this integrated decision problem as the incentive-driven delivery options and time-dependent vehicle routing problem with customer-individual APs (IDDO-TDVRPAP). To effectively solve this problem, valid inequality is introduced to enhance the performance of solving IDDO-TDVRPAP. Moreover, due to the limited performance of solvers in handling large-scale instances, we propose a novel hybrid solution-based tabu search with self-adaptive local search (HSBTS-SALS) and evaluate it on generated test instances. Finally, we summarize and discuss the experimental results. The research results indicate that the integration of the ID strategy and APs offers new methods for addressing last-mile delivery challenges, significantly enhancing customers’ perception of service quality.

Suggested Citation

  • Dong Lei & Zhen Yang & Tao Jia, 2025. "Integrating incentive-driven delivery options and time-dependent routing decisions with availability profiles," Operational Research, Springer, vol. 25(3), pages 1-40, September.
    • Handle: RePEc:spr:operea:v:25:y:2025:i:3:d:10.1007_s12351-025-00955-9
    DOI: 10.1007/s12351-025-00955-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-025-00955-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12351-025-00955-9?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Grigorios D. Konstantakopoulos & Sotiris P. Gayialis & Evripidis P. Kechagias, 2022. "Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification," Operational Research, Springer, vol. 22(3), pages 2033-2062, July.
    2. Tikani, Hamid & Setak, Mostafa & Demir, Emrah, 2021. "A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 703-730.
    3. Fang Zhao & Bingfeng Si & Zhenlin Wei & Tianwei Lu, 2023. "Time-dependent vehicle routing problem of perishable product delivery considering the differences among paths on the congested road," Operational Research, Springer, vol. 23(1), pages 1-23, March.
    4. Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong, 2019. "Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 35-48.
    5. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    6. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    7. Ann Melissa Campbell & Martin Savelsbergh, 2006. "Incentive Schemes for Attended Home Delivery Services," Transportation Science, INFORMS, vol. 40(3), pages 327-341, August.
    8. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    9. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    10. 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.
    11. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.
    12. Robert Klein & Michael Neugebauer & Dimitri Ratkovitch & Claudius Steinhardt, 2019. "Differentiated Time Slot Pricing Under Routing Considerations in Attended Home Delivery," Service Science, INFORMS, vol. 53(1), pages 236-255, February.
    13. 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.
    14. Zhou, Lin & Baldacci, Roberto & Vigo, Daniele & Wang, Xu, 2018. "A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution," European Journal of Operational Research, Elsevier, vol. 265(2), pages 765-778.
    15. Maaike Hoogeboom & Wout Dullaert & David Lai & Daniele Vigo, 2020. "Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 54(2), pages 400-416, March.
    16. Hendrik Schaap & Maximilian Schiffer & Michael Schneider & Grit Walther, 2022. "A Large Neighborhood Search for the Vehicle Routing Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 56(5), pages 1369-1392, September.
    17. Wu, Qinghua & He, Mu & Hao, Jin-Kao & Lu, Yongliang, 2024. "An effective hybrid evolutionary algorithm for the clustered orienteering problem," European Journal of Operational Research, Elsevier, vol. 313(2), pages 418-434.
    18. Pedro Amorim & Nicole DeHoratius & Fredrik Eng-Larsson & Sara Martins, 2024. "Customer Preferences for Delivery Service Attributes in Attended Home Delivery," Management Science, INFORMS, vol. 70(11), pages 7559-7578, November.
    19. Diego Cattaruzza & Nabil Absi & Dominique Feillet & Jesús González-Feliu, 2017. "Vehicle routing problems for city logistics," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 51-79, March.
    20. Ruomeng Cui & Zhikun Lu & Tianshu Sun & Joseph M. Golden, 2024. "Sooner or Later? Promising Delivery Speed in Online Retail," Manufacturing & Service Operations Management, INFORMS, vol. 26(1), pages 233-251, January.
    21. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    22. Stanley Frederick W. T. Lim & Qingchen Wang & Scott Webster, 2023. "Do it right the first time: Vehicle routing with home delivery attempt predictors," Production and Operations Management, Production and Operations Management Society, vol. 32(4), pages 1262-1284, April.
    23. Ruomeng Cui & Meng Li & Qiang Li, 2020. "Value of High-Quality Logistics: Evidence from a Clash Between SF Express and Alibaba," Management Science, INFORMS, vol. 66(9), pages 3879-3902, September.
    24. Alexander Jungwirth & Guy Desaulniers & Markus Frey & Rainer Kolisch, 2022. "Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1157-1175, March.
    25. Robert Klein & Jochen Mackert & Michael Neugebauer & Claudius Steinhardt, 2018. "A model-based approximation of opportunity cost for dynamic pricing in attended home delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 969-996, October.
    26. Bernhard Fleischmann & Martin Gietz & Stefan Gnutzmann, 2004. "Time-Varying Travel Times in Vehicle Routing," Transportation Science, INFORMS, vol. 38(2), pages 160-173, May.
    27. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    28. Stefan Voigt & Markus Frank & Pirmin Fontaine & Heinrich Kuhn, 2023. "The Vehicle Routing Problem with Availability Profiles," Transportation Science, INFORMS, vol. 57(2), pages 531-551, March.
    29. Christian Tilk & Katharina Olkis & Stefan Irnich, 2021. "The last-mile vehicle routing problem with delivery options," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 877-904, December.
    30. Wang, Yang & Wu, Qinghua & Glover, Fred, 2017. "Effective metaheuristic algorithms for the minimum differential dispersion problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 829-843.
    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. Bonomi, Valentina & Manerba, Daniele & Mansini, Renata & Zanotti, Roberto, 2025. "Optimizing Attended Home Delivery: Multiple recovery options and customer availability profiles to face synchronization failures," International Journal of Production Economics, Elsevier, vol. 279(C).
    2. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    3. 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.
    4. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    5. Jean-François Cordeau & Manuel Iori & Dario Vezzali, 2023. "A survey of attended home delivery and service problems with a focus on applications," 4OR, Springer, vol. 21(4), pages 547-583, December.
    6. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    7. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    8. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    9. Lukas Janinhoff & Robert Klein & Daniel Scholz, 2024. "Multitrip vehicle routing with delivery options: a data-driven application to the parcel industry," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(2), pages 241-294, June.
    10. 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.
    11. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    12. Ö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).
    13. Rincon-Garcia, Nicolas & Waterson, Ben & Cherrett, Tom J. & Salazar-Arrieta, Fernando, 2020. "A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 429-446.
    14. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    15. Daqing Wu & Chenxiang Wu, 2022. "Research on the Time-Dependent Split Delivery Green Vehicle Routing Problem for Fresh Agricultural Products with Multiple Time Windows," Agriculture, MDPI, vol. 12(6), pages 1-28, May.
    16. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    17. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.
    18. Koch, Sebastian & Klein, Robert, 2020. "Route-based approximate dynamic programming for dynamic pricing in attended home delivery," European Journal of Operational Research, Elsevier, vol. 287(2), pages 633-652.
    19. 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.
    20. Sun, Peng & Veelenturf, Lucas P. & Dabia, Said & Van Woensel, Tom, 2018. "The time-dependent capacitated profitable tour problem with time windows and precedence constraints," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1058-1073.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:spr:operea:v:25:y:2025:i:3:d:10.1007_s12351-025-00955-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.