ILS Metaheuristic to solve the Periodic Vehicle Routing Problem

Abstract

This article presents a methodology for solving the Periodic Vehicle Routing Problem (PVRP) with an Iterated Local Search Metaheuristic (ILS). The problem is solved in two phases: the first step is to assign days of visit to each customer, and in the second step to determine the routes that each vehicle must perform each day. The heuristic for local improvement in ILS is Clarke & Wright Heuristic, and perturbation is made on the days of visit assigned to some customers. The instances generated by Cordeau for PVRP with 51, 102 and 153 customers are used. The results are compared to the best known solutions. The gap between the results presented by the proposed metaheuristic range from 15% to 5% above the best known solutions. The time to find the solutions with the proposed metaheuristic goes from 6.76 seconds for instances of 51customers, to 172.09 seconds for instances of 153 customers.