Algorithms for the quickest path problem and the reliable quickest path problem |
| |
Authors: | Herminia I Calvete Lourdes del-Pozo José A Iranzo |
| |
Institution: | 1. Dpto. de M??todos Estad??sticos, IUMA, Universidad de Zaragoza, Pedro Cerbuna 12, 50009, Zaragoza, Spain 2. Dpto. de M??todos Estad??sticos, Universidad de Zaragoza, Violante de Hungr??a 23, 50009, Zaragoza, Spain
|
| |
Abstract: | The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin
node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times
of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also
have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the
product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In
this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest
path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which
turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path
can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on
the number of arcs of the path, etc. can also be managed with the same algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|