Periodic Vehicle Routing Problem with Time and Driver Consistency
We study an extension of the Periodic Vehicle Routing Problem that incorporates both driver consistency and temporal consistency in customer visits. To model time consistency, we explore two different approaches. The first follows the traditional definition, where a fixed upper bound limits the maximum deviation between arrival times at the same customer throughout the planning horizon, leading to the ConPVRP. The second introduces a new penalty-based framework, referred to as the PenPVRP, in which temporal inconsistencies are not strictly constrained but instead penalized within the objective function. For each variant, we develop two compact mathematical formulations: a flow-based model and a MTZ formulation, along with two sets of valid inequalities to reinforce them. The formulations are analyzed from both theoretical and computational perspectives.
Keywords: periodic vehicle routing consistency mathematical formulations branch-and-cut