A memetic algorithm for the flexible periodic vehicle routing problem

Banafsheh Amiri (), Koorush Ziarati () and Somayeh Sohrabi ()
Additional contact information
Banafsheh Amiri: Shiraz University
Koorush Ziarati: Shiraz University
Somayeh Sohrabi: Shiraz University

Journal of Heuristics, 2025, vol. 31, issue 1, No 7, 26 pages

Abstract: Abstract The flexible periodic vehicle routing problem (FPVRP) is an extension of the classic VRP in which customers are visited periodically in the course of a given time horizon. Periodicity and flexibility in providing services are two main features of the FPVRP, which introduce new challenges in solving this problem. To the best of our knowledge, there is only one single-solution-based algorithm in the literature for solving the FPVRP. In this paper, another technique called the MA-FPVRP is proposed for tackling this problem. Our population-based approach is a memetic algorithm made up of two main components: a genetic procedure that aims to find a suitable sequence of visits for each route, and a local search procedure consisting of four moves whose prime goal is to guide the search toward the promising areas. Considering 45 standard benchmark instances with unknown optimal solutions, the MA-FPVRP outperforms the preceding method in terms of both the solution quality and execution time. Using this evolutionary scheme, the average relative percent deviation (RPD) to the best-known solution values decreases from 0.52% to 0.15%, and the average execution time improves by approximately 31%. For all 10 large instances of the FPVRP, new best results are found using our algorithm. Considering the remaining 35 small and medium-size instances, our approach is superior to the previous method in terms of the solution quality, and it is more than two times faster. Besides, using the MA-FPVRP, new best solutions are obtained for 5 out of these 35 instances.

Keywords: Vehicle routing problem (VRP); Periodic vehicle routing problem (PVRP); Flexible periodic vehicle routing problem (FPVRP); Memetic algorithm (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-024-09536-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:1:d:10.1007_s10732-024-09536-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-024-09536-z

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().