An approximation algorithm for the capacitated arc routing problem. (English) Zbl 1322.90015
Summary: 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\over2}-{3\over W})\)-approximation algorithm for solving the problem and prove that this algorithm outperforms the previously proposed approximation algorithm for the problem. Furthermore, we give computational results showing that the new algorithm performs very well in practice.
MSC:
90B10 | Deterministic network models in operations research |
90C60 | Abstract computational complexity for mathematical programming problems |
90C35 | Programming involving graphs or networks |