The Open Operational Research Journal
2008, 2 : 8-12Published online 2008 February 14. DOI: 10.2174/1874243200802010008
Publisher ID: TOORJ-2-8
An Approximation Algorithm for the Capacitated Arc Routing Problem
Department of Business Studies,
Aarhus School of Business, University of Aarhus, Fuglesangs Alle 4,
DK-8210 Aarhus V, Denmark.
ABSTRACT
In this paper we consider approximation of the Capacitated Arc Routing Problem, which is the problem of servicing a set of edges in a graph using a fleet of capacity constrained vehicles. We present a 7 3 2 W approximation algorithm for the problem and prove that this algorithm outperforms the only existing approximation algorithm for the problem. Furthermore, we give computational results showing that the new algorithm performs very well in practice.