An approximation algorithm for the capacitated arc routing problem

An approximation algorithm for the capacitated arc routing problem

0.00 Avg rating0 Votes
Article ID: iaor20091362
Country: United States
Volume: 2
Issue: 1
Start Page Number: 8
End Page Number: 12
Publication Date: Jan 2008
Journal: The Open Operational Research Journal
Authors:
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/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.

Reviews

Required fields are marked *. Your email address will not be published.