The Capacitated Arc Routing Problem: Lower bounds

In this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q , must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds are compared on a set of test problems, are included.