The Capacitated Arc Routing Problem (CARP) consists of determining a set of least cost capacitated vehicle routes servicing a set of arcs. In this paper the undirected CARP is formulated as a pure binary linear integer problem. Valid inequalities are generated and the problem is solved by branch-and-cut. All the benchmark instances proposed by DeArmon and Benavent et al. can be solved optimally without any branching, for the first time ever.
Published May 2007 , 18 pages