Online covering salesman problem

Given a graph $$G=(V,E,D,W)$$ G = ( V , E , D , W ) , the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex $$i\in D$$ i ∈ D is either on the tour or within a predetermined distance L to an arbitrary vertex $$j\in W$$ j ∈ W on the tour, where $$D\subset V$$ D ⊂ V , $$W\subset V$$ W ⊂ V . In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound $$\frac{1}{1 + (k + 2)L}k+1$$ 1 1 + ( k + 2 ) L k + 1 and a CoverTreeTraversal algorithm for online CSP which is proved to be $$k+\alpha $$ k + α -competitive, where $$\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho $$ α = 0.5 + ( 4 k + 2 ) L OPT + 2 γ ρ , $$\gamma $$ γ is the approximation ratio for Steiner tree problem and $$\rho $$ ρ is the maximal number of locations that a customer can be served. When $$\frac{L}{\texttt {OPT}}\rightarrow 0$$ L OPT → 0 , our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.