TY - JOUR
T1 - Least possible time paths in stochastic, time-varying networks
AU - Miller-Hooks, Elise D.
AU - Mahmassani, Hani S.
N1 - Funding Information:
The authors are grateful to Dr Athanasios Ziliaskopoulos, presently at Northwestern University, for many useful discussions in the general area of multidimensional optimum path algorithm implementation and for the use of his random network generator (upon which the generator used in this research was based). The authors also appreciate the comments of an anonymous referee, which helped clarify several aspects of the presentation. Partial funding for the work reported herein came from a research contract through the Amarillo National Research Center for Plutonium, as well as through the Southwest University Transportation Center.
PY - 1998/12
Y1 - 1998/12
N2 - In this paper, two computationally efficient algorithms are presented for determining the least possible time paths for all origins to a single destination in networks where the arc weights are discrete random variables whose probability distribution functions vary with time. The first algorithm determines the least possible time path from each node for each departure time interval, the least possible travel time and a lower bound on the associated probability of the occurrence of this travel time. The second algorithm determines up to k least possible time paths, the associated travel times and the corresponding probabilities of occurrence of the travel times (or a lower bound on this probability). No such efficient algorithms for determining least time paths in stochastic, time-varying networks exist in the literature.
AB - In this paper, two computationally efficient algorithms are presented for determining the least possible time paths for all origins to a single destination in networks where the arc weights are discrete random variables whose probability distribution functions vary with time. The first algorithm determines the least possible time path from each node for each departure time interval, the least possible travel time and a lower bound on the associated probability of the occurrence of this travel time. The second algorithm determines up to k least possible time paths, the associated travel times and the corresponding probabilities of occurrence of the travel times (or a lower bound on this probability). No such efficient algorithms for determining least time paths in stochastic, time-varying networks exist in the literature.
KW - Shortest paths
KW - Stochastic dynamic networks
UR - http://www.scopus.com/inward/record.url?scp=0032358743&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032358743&partnerID=8YFLogxK
U2 - 10.1016/S0305-0548(98)00027-6
DO - 10.1016/S0305-0548(98)00027-6
M3 - Article
AN - SCOPUS:0032358743
VL - 25
SP - 1107
EP - 1125
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 12
ER -