Effect of formulations over a Periodic Capacitated Vehicle Routing Problem with multiple depots, heterogeneous fleet, and hard time-windows

by Alejandro Arenas-Vasco, Juan Carlos Rivera, Maria Gulnara Baldoquín

This article presents a novel contribution to the Periodic Vehicle Routing Problem (PVRP) by introducing two new problem formulations which differ in the usage of the crucial flow variable. The formulations are tailored to meet the specific demands of the vending machine industry in Medellín, Colombia, and require considering a PVRP with time windows, a heterogeneous fleet, and multiple depots. This scenario, tailored to address real-world complexity and computational challenges, brings to light an exponential surge in integer variables as customer numbers increase. The research presents an analysis of PVRPs that include the four mentioned attributes, compares their similarities, and delves into their nuances. From the analysis it is derived that the variant of the PVRP presented has not been considered previously, taking into account not only these attributes, but also the restrictions involved. Empirical experiments are conducted to examine the intricate interplay between the two proposed formulations, highlighting their impact on the performance of the GUROBI solver. The study provides valuable insights into problem-specific adaptations and algorithmic approaches, emphasizing the significance of the proposed formulations in addressing multifaceted PVRPs. In essence, this research positions the introduction of these two formulations as a pioneering step, offering a new paradigm for approaching the PVRP.