Group for Research in Decision Analysis


A Branch-and-Cut Algorithm for the Undirected Capacitated Arc Routing Problem

, , , and

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.

, 18 pages