.png){kind=icon}
.png){kind=icon}
Return
Online minimum latency problem with edge uncertainty
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2018.08.017.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 l edges are to be blocked during the traversal, for a non-negative integer l. 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. (C) 2018 Elsevier B.V. All rights reserved.
Keywords:
Routing
Minimum latency problem
Canadian traveler problem
Traffic blockage
Competitive ratio
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
View more organizations