Amongst the most important features of supply chain management are those related to interconnecting various companies within a supply network. While the performance of these interconnections is greatly influenced by information technology and information management we still face another important issue regarding logistics performance which is transportation, routing, and network design. In this paper we consider an important problem within this frame, the capacitated arc routing problem (CARP), and provide a new lower bounding scheme to obtain bounds on the quality of heuristically obtained solutions. Given a network with demands on the arcs the CARP is to find a set of minimum cost routes for a set of vehicles to service all arcs with positive demands without violating the capacities of the vehicles. Based on benchmark instances from the literature as well as real-world problem instances we can show that our bounds are more effective than other bounds available from the literature.