A memetic algorithm for the flexible periodic vehicle routing problem

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.