A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

The Cumulative Capacitated Vehicle Routing Problem is a variant of the classic routing problem in which the objective function is to minimize the sum of arrival times to customers. This article proposes a model for the problem that uses position indexes in order to calculate the contribution of the travel time of an edge to the arrival times of the remaining customers on a route. The model is implemented and solved by the branch-cut-and-price (BCP) algorithm in the VRPSolver package. Computational experiments indicate that the proposed BCP model is superior to the literature, being able to solve many open instances. Good results were also obtained for the Multi-Depot variant of the problem.