The cumulative capacitated vehicle routing problem: New formulations and iterated greedy algorithms

Abstract In this work, we address the Cumulative Capacitated Vehicle Routing Problem (CCVRP), a variant of the classical CVRP, which aims to minimize the sum of the arrival times to customers instead of the total traveled distance. This problem is relevant due to its applications in fields such as emergency logistics, transportation, wireless network and computing, among others. This paper presents the first two tractable integer formulations capable of solving instances with up to 44 nodes and two versions of an Iterated Greedy procedure for dealing with larger instances. Experimental results show that both formulations obtain optimal solutions in a reasonable amount of computational time. Regarding the two metaheuristic procedures, they were able to reach optimal and best known solutions and, in some cases, outperform the bounds obtained by exact methods for tested instances with up to 199 customers. Using larger instances, the proposed metaheuristics showed competitive results when compared to the best known values reported in the literature, with a significant reduction in computational time.