Solving Periodic Vehicle Routing Problem with Time Windows using Variable Neighborhood Search and Local Search

With the rise of e-commerce, the volume of deliveries has increased significantly in recent years. In this paper, we investigate a variant of the Vehicle Routing Problem with Time Windows (VRPTW) for modelling delivery of goods to customers, that considers a longer planning horizon and the frequency of customer service requests within that horizon - the so-called Periodic VRPTW (PVRPTW). To solve the problem, the Variable Neighborhood Search (VNS) method is combined with local search operators: inter- and intra-route exchange, relocate, and 2-Opt. The solution methods are further enhanced to balance the number of vehicles across days within the planning horizon. To validate the approach, several well-known test instances were solved and used to analyze the performance of the proposed method.