Variable neighborhood search with path relinking for the periodic vehicle routing problem with driver consistency

The Periodic Vehicle Routing Problem (PVRP) and its variants, extend the well-known Capacitated Vehicle Routing Problem (CVRP) by adding characteristics of real scenarios in the logistic sector. In the PVRP, delivery routes are planned over multiple days, and each customer has to be served on certain days according to pre-specified visit combinations. The goal is to find the minimum cost routes satisfying customer requirements. We address a challenging extension of the PVRP in which each client must be served by the same vehicle (driver) in multiple visits during the planning horizon (driver consistency). The same-driver requirement addresses real-world situations in systems, such as beverage distribution, integrated order delivery, retail merchandising, and healthcare services, where managers seek to foster driver-customer relationships and maintain service quality. We propose several heuristics for the Periodic Capacitated Vehicle Routing Problem with Driver Consistency (PVRP-DC) based on the Variable Neighborhood Search methodology, and test their performance on a set of instances for which high-quality solutions, including optimal values, have been identified. Additionally, we propose a Path Relinking post-processing for improved outcomes. Our experimental testing shows the effectiveness of our heuristics compared with a recently published method as well as with known optimal solutions.