IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v31y2025i2d10.1007_s10732-025-09557-2.html
   My bibliography  Save this article

Hybrid iterated local search algorithm for the vehicle routing problem with lockers

Author

Listed:
  • Bruno Oliveira

    (Universidade Federal Fluminense)

  • Artur Pessoa

    (Universidade Federal Fluminense)

  • Marcos Roboredo

    (Universidade Federal Fluminense)

Abstract

In the Vehicle Routing Problem (VRP) with Lockers, the vertices in a graph are divided into two key subsets: a customer set and a locker set, with lockers serving as alternative delivery points for the customer’s parcel. This paper presents a generic VRP with lockers, where a customer’s parcel can be delivered either to its home within a time windows or to a nearby locker, where they can pick it up at any time. The objective is to design a set of routes for a fleet of homogeneous vehicles in order to minimize the total travel, vehicle and assignment costs in a such manner that each locker can be visited at most once, the capacities of the vehicles and lockers are not exceeded and the time windows constraints are ensured. To solve this problem. we propose a hybrid metaheuristic that combines Iterated Local Search with a Set Partitioning-like model. Our algorithm uses several classical and specific neighborhood operators. We demonstrate the effectiveness of the proposed methodology by evaluating it on benchmark literature instances from three problems that we show that are encompassed by the generic problem defined in this paper. The results show that we found or improved 432 out of 490 best known solutions.

Suggested Citation

  • Bruno Oliveira & Artur Pessoa & Marcos Roboredo, 2025. "Hybrid iterated local search algorithm for the vehicle routing problem with lockers," Journal of Heuristics, Springer, vol. 31(2), pages 1-25, June.
    • Handle: RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09557-2
    DOI: 10.1007/s10732-025-09557-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-025-09557-2
    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/s10732-025-09557-2?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. Mohammad Reihaneh & Ahmed Ghoniem, 2018. "A multi-start optimization-based heuristic for a food bank distribution problem," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(5), pages 691-706, May.
    2. Michel Gendreau & Alain Hertz & Gilbert Laporte & Mihnea Stan, 1998. "A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 46(3), pages 330-335, June.
    3. A Ghoniem & C R Scherrer & S Solak, 2013. "A specialized column generation approach for a vehicle routing problem with demand allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(1), pages 114-124, January.
    4. Mohammad Reihaneh & Ahmed Ghoniem, 2019. "A branch-and-price algorithm for a vehicle routing with demand allocation problem," Post-Print hal-02117608, HAL.
    5. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    6. Reihaneh, Mohammad & Ghoniem, Ahmed, 2019. "A branch-and-price algorithm for a vehicle routing with demand allocation problem," European Journal of Operational Research, Elsevier, vol. 272(2), pages 523-538.
    7. Niels A. Wouda & Leon Lan & Wouter Kool, 2024. "PyVRP: A High-Performance VRP Solver Package," INFORMS Journal on Computing, INFORMS, vol. 36(4), pages 943-955, July.
    8. 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.
    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. 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.
    2. Mahmoudi, Monirehalsadat & Shirzad, Khadijeh & Verter, Vedat, 2022. "Decision support models for managing food aid supply chains: A systematic literature review," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    3. Akkerman, Renzo & Buisman, Marjolein & Cruijssen, Frans & de Leeuw, Sander & Haijema, Rene, 2023. "Dealing with donations: Supply chain management challenges for food banks," International Journal of Production Economics, Elsevier, vol. 262(C).
    4. Chen, Yanru & Gao, Mujin & Zhang, Zongcheng & Li, Junheng & Wahab, M.I.M. & Jiang, Yangsheng, 2025. "Contextual bandits learning-based branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with conflicts and time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    5. Han, Jialin & Zhang, Jiaxiang & Guo, Haoyue & Zhang, Ning, 2024. "Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 316(3), pages 958-975.
    6. 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).
    7. Shahparvari, Shahrooz & Mohammadi, Mahsa & Peszynski, Konrad & Rickards, Lauren, 2024. "How contraflow enhances clearance time during assisted mass evacuation – A case study exploring the Australian 2013–14 Gippsland bushfires," Transportation Research Part A: Policy and Practice, Elsevier, vol. 189(C).
    8. Reihaneh, Mohammad & Abouei Ardakan, Mostafa & Eskandarpour, Majid, 2022. "An exact algorithm for the redundancy allocation problem with heterogeneous components under the mixed redundancy strategy," European Journal of Operational Research, Elsevier, vol. 297(3), pages 1112-1125.
    9. Carrese, Stefano & Cuneo, Valerio & Nigro, Marialisa & Pizzuti, Raffaele & Ardito, Cosimo Federico & Marseglia, Guido, 2022. "Optimization of downstream fuel logistics based on road infrastructure conditions and exposure to accident events," Transport Policy, Elsevier, vol. 124(C), pages 96-105.
    10. Mostafaei, Hossein & Castro, Pedro M. & Oliveira, Fabricio & Harjunkoski, Iiro, 2021. "Efficient formulation for transportation scheduling of single refinery multiproduct pipelines," European Journal of Operational Research, Elsevier, vol. 293(2), pages 731-747.
    11. Guido Marseglia & Carlo Maria Medaglia & Francisco A. Ortega & Juan A. Mesa, 2019. "Optimal Alignments for Designing Urban Transport Systems: Application to Seville," Sustainability, MDPI, vol. 11(18), pages 1-14, September.
    12. Reihaneh, Mohammad & Ansari, Sina & Farhadi, Farbod, 2023. "Patient appointment scheduling at hemodialysis centers: An exact branch and price approach," European Journal of Operational Research, Elsevier, vol. 309(1), pages 35-52.
    13. 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).
    14. Ohad Eisenhandler & Michal Tzur, 2019. "A Segment-Based Formulation and a Matheuristic for the Humanitarian Pickup and Distribution Problem," Transportation Science, INFORMS, vol. 53(5), pages 1389-1408, September.
    15. Sina Mohri, Seyed & Ghaderi, Hadi & Van Woensel, Tom & Mohammadi, Mehrdad & Nassir, Neema & Thompson, Russell G., 2024. "Contextualizing alternative delivery points in last mile delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).
    16. Olli Bräysy & Michel Gendreau, 2002. "Tabu Search heuristics for the Vehicle Routing Problem with Time Windows," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 10(2), pages 211-237, December.
    17. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    18. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    19. Majed G. Alharbi & Ahmed Stohy & Mohammed Elhenawy & Mahmoud Masoud & Hamiden Abd El-Wahed Khalifa, 2021. "Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features," Sustainability, MDPI, vol. 13(22), pages 1-12, November.
    20. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.

    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:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09557-2. 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.