The Steiner Traveling Salesman Problem with online edge blockages

Highligts•The Steiner Traveling Salesman Problem with as many as k online edge blockages is considered.•First a lower bound on the competitive ratio is shown; then an exponential-time online optimal algorithm for the problem is presented; and lastly a polynomial-time online asymptotically optimal algorithm is presented.•Experimental results show that the polynomial-time online algorithm takes only a fraction of the running time of the offline optimal algorithm, yet produces solutions of competitive quality to the offline optimal solutions.

We consider the online Steiner Traveling Salesman Problem. In this problem, we are given an edge-weighted graph G = (V, E) and a subset D⊆V of destination vertices, with the optimization goal to find a minimum weight closed tour that traverses every destination vertex of D at least once. During the traversal, the salesman could encounter at most k non-recoverable blocked edges. The edge blockages are real-time, meaning that the salesman knows about a blocked edge whenever it occurs. We first show a lower bound on the competitive ratio and present an online optimal algorithm for the problem. While this optimal algorithm has non-polynomial running time, we present another online polynomial-time near optimal algorithm for the problem. Experimental results show that our online polynomial-time algorithm produces solutions very close to the offline optimal solutions.