An application of ILS heuristic to Periodic Vehicle Routing Problem with heterogeneous fleet and fixed costs

This paper addresses the Periodic Vehicle Routing Problem (PVRP) which is a variation of the classical Vehicle Routing Problem. The PVRP consists of assigning a combination of visiting days to each customer, and defining the set of routes for each day of a planning horizon. The objective of the problem is the minimization of the total length of the routes travelled by the vehicles and the fixed costs of using the vehicles on the time horizon. To solve the problem, we present an Integer Programming Model and two heuristic algorithms based on the meta-heuristic Iterated Local Search (ILS). The mathematical model is solved by using the CPLEX optimization solver and optimal solutions are obtained for small and medium-sized instances of the problem. The computational experiments show that the heuristic algorithms determine high quality approximate solutions at a low computational time. The results are validated by statistical tests.