René van Bevern, Christian Komusiewicz, and Manuel Sorge. A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: theory and experiments. Networks, 70(3):262–278, 2017. WARP 2 special issue.

We prove that any polynomial-time α(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson Problem yields a polynomial-time O(α(C))-approximation algorithm for the mixed and windy Capacitated Arc Routing Problem, where C is the number of weakly connected components in the subgraph induced by the positive-demand arcs—a small number in many applications. In conjunction with known results, we obtain constant-factor approximations for C∈O(log n) and O(log C/log log C)-approximations in general. Experiments show that our algorithm, together with several heuristic enhancements, outperforms many previous polynomial-time heuristics. Finally, since the solution quality achievable in polynomial time appears to mainly depend on C and since C=1 in almost all benchmark instances, we propose the Ob benchmark set, simulating cities that are divided into several components by a river.

bib | DOI | slides | source code | http ] Back

This file was generated by bibtex2html 1.98.