Mathematical models for the periodic vehicle routing problem with timewindows and time spread constraints

Abstract

The periodic vehicle routing problem (PVRP) is an extension of the well-knownvehicle routing problem. In this paper the PVRP with time windows and timespread constraints (PVRP-TWTS) is addressed which arises in the high-valueshipment transportation area. In the PVRP-TWTS period-specific demands of thecustomers must be delivered by a fleet of heterogeneous capacitated vehicles overthe several planning periods. Additionally the arrival times to a customer shouldbe irregular within its time window over the planning periods and the waiting timeis not allowed for the vehicles due to the security concerns. This study proposes novel mixed-integer linear programming (MILP) and constraint programming(CP) models for the PVRP-TWTS. Furthermore we develop several validinequalities to strengthen the proposed MILP and CP models as well as a lowerbound. Even though CP has successful applications for various optimizationproblems it is still not as well-known as MILP in the operations research field.This study aims to utilize the effectiveness of CP in solving the PVRP-TWTS. This study presents a CP model for PVRP-TWTS for the first time in the literature to the best of our knowledge. Having a comparison of the CP and MILP models can help in providing a baseline for the problem. We evaluate the performance ofthe proposed MILP and CP models by modifying the well-known benchmark setfrom the literature. The extensive computational results show that the CP modelperforms much better than the MILP model in terms of the solution quality. 4