Master Student, Department of Computer Science & Engineering & IT, Shiraz University

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 that introduce some new challenges in planning the routes. As the FPVRP is rather a new problem, to the best of our knowledge, there is only one heuristic method available to solve this problem that is single-solution based. In this paper, we propose the first population-based algorithm to tackle the FPVRP. Our 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 an embedded iterated local search consisted of four moves that focus on guiding the search toward promising areas. In this algorithm, we take advantage of some operators which have been fundamentally designed for solving the other variants of VRP. In addition, to improve the efficiency of the method, some changes are made in the local search operators that have been used in the previous studies. The proposed algorithm is tested on ۴۵ standard benchmark instances with unknown optimal solutions, and is compared with the state-of-the-art algorithm in the literature. In terms of solution quality, our approach proves to be competitive with preceding method on these instances. Besides, it improves the best-known results of six instances.

کلیدواژه ها:

Periodic Vehicle Routing Problem (PVRP) ، Flexible Periodic Vehicle Routing Problem (FPVRP) ، Memetic Algorithm (MA) ، Vehicle Routing Problem (VRP)