Online minimum latency problem with edge uncertainty

Given a tour in a metric space, the latency of the vertex v is the distance traveled along the tour starting from the root and arriving at v for the first time. The minimum latency problem (MLP) is to find a tour visiting all given vertices such that the total latency of these vertices is minimized. We consider an online variant in traffic networks, where as many as ℓ edges are to be blocked during the traversal, for a non-negative integer ℓ. We first prove a lower bound on the competitive ratio for any online algorithm and then propose an online algorithm GoodTreeTraversal, which is demonstrated to be near optimal if there is a good k-tree for every k in the range from 2 to n and the number of blockages is large enough. We also present a polynomial time heuristic algorithm called Detour, which is much faster than GoodTreeTraversal. The numerical experiments demonstrate the efficiency and effectiveness of our two algorithms.