TY - JOUR

T1 - A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem

T2 - Theory and experiments

AU - van Bevern, René

AU - Komusiewicz, Christian

AU - Sorge, Manuel

N1 - Publisher Copyright: © 2017 Wiley Periodicals, Inc.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - 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.

AB - 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.

KW - Chinese Postman

KW - combinatorial optimization

KW - fixed-parameter algorithm

KW - NP-hard problem

KW - Rural Postman

KW - transportation

KW - vehicle routing

KW - EULERIAN EXTENSION

KW - BOUNDS

UR - http://www.scopus.com/inward/record.url?scp=85017443169&partnerID=8YFLogxK

U2 - 10.1002/net.21742

DO - 10.1002/net.21742

M3 - Article

AN - SCOPUS:85017443169

VL - 70

SP - 262

EP - 278

JO - Networks

JF - Networks

SN - 0028-3045

IS - 3

ER -