Iterative Solution Strategy for the Periodic Vehicle Routing Problem

Abstract

Given a planning horizon and a limited and heterogeneous fleet, the Periodic Vehicle Routing Problem (PVRP) seeks to determine a set of routes that minimizes the total transportation cost while satisfying both the demand and the visit frequency required by each customer. The complexity of this problem lies in the vast combinatorial number of alternatives, since decisions must be made simultaneously regarding which days to visit each customer, which vehicles to use each day, and what routes those vehicles should follow. This work proposes an efficient methodology based on the decomposition of the problem into two subproblems: an assignment model and a daily routing model of a vehicle fleet. An iterative strategy is developed using two mixed-integer linear programming models. The first model assigns customers to visit days in order to minimize the fixed costs of vehicles usage, while the second optimizes both the assignment of vehicles to customers and their daily routes, based on the allocation obtained in the first model, with the goal of minimizing total transportation cost. The proposed strategy is compared with a previously developed approach, showing that high-quality solutions can be obtained in significantly reduced computation times. The proposed solution strategy represents a useful decision-support tool for optimizing logistics tasks and is applicable to both distribution and collection problems.