Abstract
When the "length" of a link is not deterministic and is governed by a stochastic process, the "shortest" path between two points in the network is not necessarily always composed of the same links and depends on the state of the network. For example, in communication and transportation networks, the travel time on a link is not deterministic and the fastest path between two points is not fixed. This paper presents an algorithm to compute the expected shortest travel time between two nodes in the network when the travel time on each link has a given independent discrete probability distribution. The algorithm assumes the knowledge of all the paths between two nodes and methods to determine the paths are referenced. In reliability (i.e. the probability that two given points are connected by a path) computations, associated with each link is a probability of "failure" and a probability of "success". Since "failure" implies infinite travel time, the algorithm simultaneously computes reliability. The paper also discusses the algorithm's capability to simultaneously compute some other performance measures which are useful in the analysis of emergency services operating on a network.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 347-355 |
| Number of pages | 9 |
| Journal | Computers and Operations Research |
| Volume | 3 |
| Issue number | 4 |
| DOIs | |
| State | Published - Dec 1976 |
| Externally published | Yes |
ASJC Scopus subject areas
- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research