New formulation and valid inequalities for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows

This paper presents a new formulation and valid constraints for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows (MDHFPCVRP-TW). The problem raises from a real-world application in the vending machine industry in Medellín, Colombia. Our main contribution is a novel formulation that replaces binary depot-client assignment variables with continuous auxiliary variables and implements depot replication, achieving both model simplicity and computational efficiency. We introduce preprocessing techniques and valid constraints, particularly focusing on capacity-based constraints with client combinations, which significantly strengthen the formulation’s linear relaxation. Computational experiments demonstrate that our formulation consistently outperforms previous approaches across different instance sizes, achieving optimality for small instances and maintaining single-digit optimality gaps for medium-sized instances where earlier formulations showed gaps above 12%. The formulation shows particularly strong performance in solution time, often requiring less time to find feasible solutions. While limitations persist for very large instances, our results suggest promising directions for developing hybrid exact-heuristic methods for industrial-scale problems.