 Online minimum latency problem with edge uncertaintyHuili Zhang, Weitian Tong, Guohui Lin and Yinfeng Xu European Journal of Operational Research, 2019, vol. 273, issue 2, 418-429 Abstract: 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. Keywords: Routing; Minimum latency problem; Canadian traveler problem; Traffic blockage; Competitive ratio (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:273:y:2019:i:2:p:418-429 DOI: 10.1016/j.ejor.2018.08.017 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.