Online covering salesman problem

Given a graph G= (V, E, D, W) , the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex i∈ D is either on the tour or within a predetermined distance L to an arbitrary vertex j∈ W on the tour, where D⊂ 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 11+(k+2)Lk+1 and a CoverTreeTraversal algorithm for online CSP which is proved to be k+ α-competitive, where α=0.5+(4k+2)LOPT+2γρ, γ is the approximation ratio for Steiner tree problem and ρ is the maximal number of locations that a customer can be served. When LOPT→0, our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.