Approximation algorithms for two clustered arc routing problems

Given a strongly connected mixed graph $$G=(V,E,A)$$ G = ( V , E , A ) , where V represents the vertex set, E is the undirected edge set, and A is the directed arc set, $$R \subseteq E$$ R ⊆ E is a subset of required edges and is divided into p clusters $$R_1,R_2,\dots ,R_p$$ R 1 , R 2 , ⋯ , R p , and A is a set of required arcs and is partitioned into q clusters $$A_1,A_2,\ldots ,A_q$$ A 1 , A 2 , … , A q . Each edge in E and each arc in A are associated with a nonnegative weight and the weight function satisfies the triangle inequality. In this paper we consider two clustered arc routing problems. The first is the Clustered Rural Postman Problem, in which A is empty and the objective is to find a minimum-weight closed walk such that all the edges in R are serviced and the edges in $$R_i$$ R i ( $$1\le i \le p$$ 1 ≤ i ≤ p ) are serviced consecutively. The other is the Clustered Stacker Crane Problem, in which R is empty and the goal is to find a minimum-weight closed walk that traverses all the arcs in A and services the arcs in $$A_j$$ A j ( $$1\le j \le q$$ 1 ≤ j ≤ q ) consecutively. For both problems, we propose constant-factor approximation algorithms with ratios 13/6 and 19/6, respectively.