Weighted online minimum latency problem with edge uncertainty
Küçük Resim Yok
Tarih
2021
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
In the minimum latency problem, an undirected connected graph and a root node together with non negative edge distances are given to an agent. The agent looks for a tour starting at the root node and visiting all the nodes to minimise the sum of the latencies of the nodes, where the latency of a node is the distance from the root node to the node at its first visit on the tour by the agent. We study an online variant of the problem, where there are k blocked edges in the graph which are not known to the agent in advance. A blocked edge is learned online when the agent arrives at one of its end nodes. Furthermore, we investigate another online variant of the minimum latency problem involving k blocked edges where each node is associated with a weight to express its priority and the objective is to minimise the summation of the weighted latency of the nodes. In this paper, we prove that the lower bound of 2 k + 1 on the competitive ratio of deterministic online algorithms is tight for both weighted and non-weighted variations by introducing an optimal deterministic online algorithm which meets this lower bound. We also present a lower bound of k + 1 on the expected competitive ratio of randomized online algorithms for both problems. We then develop two polynomial time heuristic algorithms to solve these online problems. We test our algorithms on real life as well as randomly generated instances that are partially adopted from the literature. (c) 2021 Elsevier B.V. All rights reserved.
Açıklama
Anahtar Kelimeler
Routing, Online Optimisation, Minimum Latency Problem, Competitive Ratio, Online Algorithms, Traveling Salesman Problem, Routing-Problems, Shortest Paths, Connectivity, Time
Kaynak
European Journal of Operational Research
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
295
Sayı
1
