1 CORAL - Centre for Operations Research Applications in Logistics, Aarhus School of Business, Aarhus BSS, Aarhus University2 Department of Business Studies, Aarhus School of Business, Aarhus BSS, Aarhus University3 Department of Economics and Business Economics, Aarhus BSS, Aarhus University4 Department of Economics and Business Economics, Aarhus BSS, Aarhus University
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/2 - 3/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.
Open Operational Research Journal, 2008, Vol 2, p. 8-12